Boolean matching in logic synthesis

A new formulation for finding the existence of a Boolean match between two functions with `don´t cares´ is presented. An algorithm for Boolean matching is developed based on this new foundation and is used within a technology mapper as a substitute for tree matching algorithms. The new algorithm is fast and uses symmetries of the gates in the library to speed up the matching process. Local `don´t cares´ are computed for each function being mapped in terms of its inputs. To reduce the frequency in which Boolean matching is used, the gates in the library are grouped into classes such that it is sufficient to try to match a function with the class representative. Experimental results show significant improvement in the final area of the mapped circuits