Fast Boolean matching under permutation by efficient computation of canonical form
Debatosh Debnath, Tsutomu Sasao · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · 2004
Checking the equivalence of two Boolean functions under permutation of the variables is an important problem in the synthesis of multiplexer-based field-programmable gate arrays (FPGAs), and the problem is known as Boolean matching. This paper presents an efficient breadth-first search technique for computing a canonical form-namely P-representative-of Boolean functions under permutation of the variables. Two functions match if they have the same P-representative. On an ordinary workstation, on the average, the method requires several microseconds to check the Boolean matching of functions with up to eight variables against a library with tens of thousands of cells.