Geodesy

Algorithm

Benchmark (surveying)

Boolean circuit

Discrete mathematics

Statistics

Boolean function

Theoretical computer science

Variable (mathematics)

Boolean data type

Computer science

Acoustics

Physics

Signature (topology)

Mathematics

Geography

Mathematical analysis

Geometry

Matching (statistics)

Symmetric group

Permutation (music)

Random permutation

Cluster Computing

An efficient pairwise Boolean matching algorithm for solving the problem of matching single-output specified Boolean functions under input negation and/or input permutation and/or output negation (NPN) is proposed in this paper. We present the structural signature (SS) vector, which comprises a first-order signature value, two symmetry marks, and a group mark. As a necessary condition for NPN Boolean matching, the SS is more effective than the traditional signature. A symmetry mark can distinguish symmetric variables and asymmetric variables and be used to search for multiple variable mappings in a single variable-mapping search operation, which reduces the search space significantly. Updating the SS vector via Shannon decomposition provides benefits in distinguishing unidentified variables, and the group mark and phase collision check can be used to discover incorrect variable mappings quickly, which also speeds up the NPN Boolean matching process. Using the algorithm proposed in this paper, we test both equivalent and non-equivalent matching speeds on the MCNC benchmark circuit sets and random circuit sets. In the experiment, our algorithm is shown to be 4.2 times faster than competitors when testing equivalent circuits and 172 times faster, on average, when testing non-equivalent circuits.

An efficient NPN Boolean matching algorithm based on structural signature and Shannon expansion