| Title | A Group Algebraic Approach to NPN Classification of Boolean Functions |
| Authors | Zhang, Juling Yang, Guowu Hung, William N. N. Liu, Tian Song, Xiaoyu Perkowski, Marek A. |
| Affiliation | Univ Elect Sci & Technol China, Sch Comp Sci & Engn, Big Data Res Ctr, Chengdu 611731, Sichuan, Peoples R China Univ Xinjiang Finance & Econ, Sch Comp Sci & Engn, Urumqi 830000, Peoples R China Guangxi Univ Nationalities, Guangxi Key Lab Hybrid Computat & IC Design Anal, Nanning 530006, Peoples R China Synopsys Inc, Mountain View, CA USA Peking Univ, Minist Educ, Key Lab High Confidence Software Technol, Beijing, Peoples R China Portland State Univ, ECE Dept, Portland, OR 97207 USA |
| Keywords | NPN classification Group theory Boolean function Cycle type of a permutation Nonequivalent coloring |
| Issue Date | 2019 |
| Publisher | THEORY OF COMPUTING SYSTEMS |
| Abstract | 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 2(m)m! 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. |
| URI | http://hdl.handle.net/20.500.11897/546327 |
| ISSN | 1432-4350 |
| DOI | 10.1007/s00224-018-9903-0 |
| Indexed | SCI(E) EI |
| Appears in Collections: | 高可信软件技术教育部重点实验室 |
