Fast Boolean matching under permutation using representative

Abstract

This paper presents an efficient method to check the equivalence of two Boolean functions under permutation of the variables. 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 develop a breadth-first search technique to quickly compute the P-representative. On an ordinary 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.