A Boolean Function NPN Equivalent Matching Algorithm Based on Canonical Form

By studying the operation of the cofactor of Shannon decomposition, six attributes of symmetric variables and independent variables in NP equivalent transformation are found. By making full use of the invariance of the symmetry and independence of variables after NP transformation, the phase uncertainty of independent variables, the unavailability of both independent variables to identify other variables and other variables to identify independent variables in the process of matching, we propose an NPN equivalent matching algorithm based on canonical form. We performed matching experiments on the 7-22 variable Boolean functions of a large number of MCNC benchmark circuits and randomly generated circuits.. The experimental results show that the algorithm of this paper reduces the search space in the matching process by 58.8% and increases matching speed by 45.6% on the two experimental circuit sets compared with the algorithm based on higher order general signature. This indicates that the algorithm of this paper can provide faster and more effective Boolean matching for circuit optimization and circuit mapping.