A Canonical-Based NPN Boolean Matching Algorithm Utilizing Boolean Difference and Cofactor Signature

This paper presents a new compact canonical-based algorithm to solve the problem of single-output completely specified input negation and/or input permutation and/or output negation Boolean matching. We propose a new signature vector Boolean difference and cofactor signature vector. Our algorithm utilizes the Boolean difference, cofactor signature, and symmetry properties to search for canonical transformations. The use of symmetry and Boolean difference notably reduces the search space and speeds up the Boolean matching process compared with the algorithm proposed by Adbollahi and Pedram. We tested our algorithm on a large number of circuits. The experimental results showed that the average runtime of our algorithm 37% higher and its average search space 67% smaller compared with Adbollahi and Pedram, when tested on general circuits.