Search

Affine equivalent classes of Boolean functions have many applications in modern cryptography and circuit design. Previous publications have shown that affine equivalence on the entire space of Boolean functions can be computed up to 10 variables, but not on the quotient Boolean function space modulo functions of different degrees. Computing the number of equivalent classes of cosets of Reed-Muller code R (1 , n) is equivalent to classifying Boolean functions modulo linear functions, which can be computed only when n ≤ 7. Based on the linear representation of the affine group A G L (n , 2) on the quotient space R (s , n) / R (k , n) , we obtain a useful counting formula to compute the number of equivalent classes. Instead of computing the conjugacy classes and representatives directly in A G L (n , 2) , we reduce the computation complexity by introducing an isomorphic permutation group Pn and performing the computation in Pn. With the proposed algorithm, the number of equivalent classes of cosets of R(1,n) can be computed up to 10 variables. Furthermore, the number of equivalent classes on R (s , n) / R (k , n) can also be computed when − 1 ≤ k < s ≤ n ≤ 10, which is a major improvement and advancement comparing to previous methods. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]