Title

A Group Algebraic Approach to NPN Classification of Boolean Functions

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

DOI

10.1007/s00224-018-9903-0

Persistent Identifier

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

Share

COinS