This paper presents an efficient method to check the equivalence of two Boolean functions under permutation of the variable.s The problem is also known as Boolean matching. As a basis of the Boolean matching, we use the notion P-representative. If two functions have the same P-representative then they match. We develo pa breadth-first search technique to quickly compute the P-representative. On an orcinary workstation, on the average, our method requires several microseconds to test the Boolean matching for functions with up to eight variables. This approach is promising for Boolean matching of multiplexor-based field-programmable gate arrays (FPGAs) and for library matching with many large cells.
展开▼
