NPN Boolean Matching Algorithm Based on Symmetry and Signature

The paper proposes a pairwise NPN (Input Negation and/or Input Permutation and/or Output Negation) Boolean matching algorithm based on symmetry and signature.The algorithm utilizes variable symmetry, the first order signature vector and Shannon decomposition to design and implement NPN Boolean matching.The candidate NP transformations between two functions are searched and verified through two necessary conditions:1) two NP equivalent Boolean functions must have the same the first order signature vector and 2) two variables having a mapping relation must have the same the first order signature.The use of symmetry and signature reduces the search space of the candidate NP transformations and speeds up NPN Boolean matching process.