Name
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 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. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1007/s00224-018-9903-0 | Theory of Computing Systems |
Keywords | Field | DocType |
NPN classification, Group theory, Boolean function, Cycle type of a permutation, Nonequivalent coloring | Logic synthesis,Boolean function,Discrete mathematics,Algebraic number,Group theory,Mathematical proof,Algebraic properties,Equivalence class,Very-large-scale integration,Mathematics | Journal |
Volume | Issue | ISSN |
63 | 6 | 1433-0490 |
Citations | PageRank | References |
2 | 0.37 | 13 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Juling Zhang | 1 | 10 | 1.88 |
| Guowu Yang | 2 | 20 | 6.39 |
| William N. N. Hung | 3 | 304 | 34.98 |
| Tian Liu | 4 | 17 | 4.81 |
| Xiaoyu Song | 5 | 471 | 51.61 |
| Marek A. Perkowski | 6 | 2 | 3.08 |