Title: A Canonical-based NPN Boolean Matching Algorithm Utilizing Boolean Difference and Cofactor Signature,
Abstract: This paper presents a new compact canonical-based algorithm to solve the
problem of single-output completely specified NPN Boolean matching. We propose
a new signature vector Boolean difference and cofactor (DC) 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 to the algorithm proposed in [1]. 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 to [1] when tested on general circuits.