Boolean Matching for Incompletely Specified Functions

Boolean matching is to check the equivalence of two functions under input permutation and input/output phase assignment. In this paper, we will address Boolean matching problem for incompletely specified functions. We will formulate the searching of input variable mapping between two target functions as a logic equation by using multiple-valued function. Based on this equation, a Boolean matching algorithm will be proposed. Delay and power dissipation can also be taken into consideration when this method is used for technology mapping. Experimental results on a set of benchmarks show that our algorithm is indeed very effective in solving Boolean matching problem for incompletely specified functions.