Computing Affine Equivalence Classes of Boolean Functions by Group Isomorphism

作者：Zhang, Yan^*; Yang, Guowu; Hung, William N. N.; Zhang, Juling

来源：IEEE Transactions on Computers, 2016, 65(12): 3606-3616.

DOI：10.1109/TC.2016.2557329

• Logic synthesis
• Boolean functions
• affine equivalence classification
• group isomorphism

Affine equivalence classification of Boolean functions has significant applications in logic synthesis and cryptography. Previous studies for classification have been limited by the large set of Boolean functions and the complex operations on the affine group. Although there are many research on affine equivalence classification for parts of Boolean functions in recent years, there are very few results for the entire set of Boolean functions. The best existing result has been achieved by Harrison with 15768919 affine equivalence classes for 6-variable Boolean functions. This paper presents a concise formula for affine equivalence classification of the entire set of Boolean functions as well as a formula for affine classification of Boolean functions with distinct ON-set size respectively. The method outlined in this paper greatly simplifies the affine group's action by constructing an isomorphism mapping from the affine group to a permutation group. By this method, we can compute the affine equivalence classes for up to 10 variables. Experiment results indicate that our scheme for calculating the affine equivalence classes for more than 6 variables is a significant advancement over previous published methods.

• 出版日期2016-12-1
• 单位电子科技大学