Classification of Boolean Functions where Affine Functions are Uniformly Distributed

2013/03/12 by Ranjeet Kumar Rout, Rout, Ranjeet Kumar, Pabitra Pal Choudhury +3
Computer Science · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #cs.DM #cs.LO

paper · pdf · doi:10.48550/arxiv.1303.3527

12 pages

arxiv created 2013/03/12 · arxiv updated 2013/03/15

Abstract

Classification of Non-linear Boolean functions is a long-standing problem in the area of theoretical computer science. In this paper, effort has been made to achieve a systematic classification of all n-variable Boolean functions, where only one affine Boolean function belongs to each class. Two different methods are proposed to achieve this classification. The first method is a recursive procedure that uses the Cartesian product of sets starting from the set of 1-variable Boolean function and in the second method classification is achieved through a set of invariant bit positions with respect to an affine function belonging to that class. The invariant bit positions also provide information concerning the size and symmetry properties of the classes/sub-classes, such that the members of classes/sub-classes satisfy certain similar properties.

Related

• Yet another algorithm to compute the nonlinearity of a Boolean function
• Computing the Number of Equivalent Classes on R(s,n)/R(k,n)
• 9-variable Boolean Functions with Nonlinearity 242 in the Generalized Rotation Class
• Nearest neighbor representations of Boolean functions
• A Quantum Algorithm for the Classification of Patterns of Boolean Functions