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]

The classification of Boolean functions plays an underpinning role in logic design and synthesis of VLSI circuits. This paper considers a underpinning question in Boolean function classification: how many distinct classes are there for k-input Boolean functions. We exploit various group algebraic properties to efficiently compute the number of unique equivalent classes. We have reduced the computation complexity from 2mm! to (m + 1)!. We present our analysis for NPN classification of Boolean functions with up to ten variables and compute the number of NP and NPN equivalence classes for 3-10 variables. This is the first time to report the number of NP and NPN classifications for Boolean functions with 9-10 variables. We demonstrate the effectiveness of our method by both theoretical proofs and numeric experiments. [ABSTRACT FROM AUTHOR]