A Group Algebraic Approach to NPN Classification of Boolean Functions

Authors

Juling Zhang, University of Electronic Science and Technology of China
Guowu Yang, Guangxi University for NationalitiesFollow
William N. N. Hung, Synopsys Inc.Follow
Tian Liu, Peking University
Xiaoyu Song, Portland State UniversityFollow
Marek A. Perkowski, Portland State UniversityFollow

Sponsor

We would like to thank the National Natural Science Foundation of China (Grant No. 61572109) and the Special Fund for Bagui Scholars of Guangxi for the technology support

Published In

Theory of Computing Systems

Document Type

Citation

Publication Date

8-1-2019

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.

Description

© Springer Science+Business Media, LLC, part of Springer Nature 2018

Locate the Document

https://doi.org/10.1007/s00224-018-9903-0

DOI

10.1007/s00224-018-9903-0

Persistent Identifier

https://archives.pdx.edu/ds/psu/29639

Citation Details

Zhang, J., Yang, G., Hung, W. N. N., Liu, T., Song, X., & Perkowski, M. A. (2019). A Group Algebraic Approach to NPN Classification of Boolean Functions. Theory of Computing Systems, 63(6), 1278–1297.