Computing Affine Equivalence Classes of Boolean Functions by Group Isomorphism

被引：14

作者：

Zhang, Yan ^{[1
]}

Yang, Guowu ^{[1
]}

Hung, William N. N. ^{[2
]}

Zhang, Juling ^{[1
]}

机构：

[1] Univ Elect Sci & Technol China, Big Data Res Ctr, Chengdu 611731, Peoples R China

[2] Synopsys Inc, Mountain View, CA 94043 USA

来源：

IEEE TRANSACTIONS ON COMPUTERS | 2016年 / 65卷 / 12期

基金：

中国国家自然科学基金;

关键词：

Logic synthesis; Boolean functions; affine equivalence classification; group isomorphism; REED-MULLER CODE; CLASSIFICATION; COSETS; DECOMPOSITION;

D O I：

10.1109/TC.2016.2557329

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：3606 / 3616

页数：11

共 32 条

[1] WEIGHT DISTRIBUTIONS OF COSETS OF (32,6) REED-MULLER CODE [J].

BERLEKAMP, ER ;

WELCH, LR .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1972, 18 (01) :203-+

[2]

Biryukov A, 2003, LECT NOTES COMPUT SC, V2656, P33

[3] ON IDENTIFICATION OF TOTALLY SYMMETRIC BOOLEAN FUNCTIONS [J].

BISWAS, NN .

IEEE TRANSACTIONS ON COMPUTERS, 1970, C 19 (07) :645-&

[4]

Braeken A, 2005, LECT NOTES COMPUT SC, V3580, P324

[5] Bi-decomposition of multi-valued logical functions and its applications [J].

Cheng, Daizhan ;

Xu, Xiangru .

AUTOMATICA, 2013, 49 (07) :1979-1985

[6] Boolean matching for LUT-based logic blocks with applications to architecture evaluation and technology mapping [J].

Cong, J ;

Hwang, YY .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 2001, 20 (09) :1077-1090

[7]

CURTIS HA, 1976, IEEE T COMPUT, V25, P1033

[8] Affine equivalence of quartic homogeneous rotation symmetric Boolean functions [J].

Cusick, Thomas W. ;

Cheon, Younhwan .

INFORMATION SCIENCES, 2014, 259 :192-211

[9] APPLICATION OF RADEMACHER - WALSH TRANSFORM TO BOOLEAN FUNCTION CLASSIFICATION AND THRESHOLD LOGIC SYNTHESIS [J].

EDWARDS, CR .

IEEE TRANSACTIONS ON COMPUTERS, 1975, C 24 (01) :48-62

[10]

Falkowski B. J., 2006, IEEE T COMPUT, V55, P1067

← 1 2 3 4 →