Fast Boolean matching under permutation using representative
説明
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.
収録刊行物
-
- Proceedings of the ASP-DAC '99 Asia and South Pacific Design Automation Conference 1999 (Cat. No.99EX198)
-
Proceedings of the ASP-DAC '99 Asia and South Pacific Design Automation Conference 1999 (Cat. No.99EX198) 359-362 vol.1, 1999-01-01
IEEE