# Classification of Boolean Functions Where Affine Functions Are Uniformly Distributed

Authors: Ranjeet Kumar Rout; Pabitra Pal Choudhury; Sudhakar Sahoo
Journal: Journal of Discrete Mathematics
 (2013)

---

## Abstract

The present paper on classification ofn-variable Boolean functions highlights the process of classification in a coherent way such that each class contains a single affine Boolean function. Two unique and different methods have been devised for this classification. The first one is a recursive procedure that uses the Cartesian product of sets starting from the set of one variable Boolean functions. In the second method, the classification is done by changing some predefined bit positions with respect to the affine function belonging to that class. The bit positions which are changing also provide us information concerning the size and symmetry properties of the classes/subclasses in such a way that the members of classes/subclasses satisfy certain similar properties.


---

## Body

## 1. Introduction

Classification of non-linear Boolean functions has been a long standing problem in the field of theoretical computer science. A systematic classification of Boolean functions withn-variable having a representative in each class is a welcomed step in this area of study. It has been very accurately considered as vital and meaningful because of two important well-defined reasons: (a) equivalent functions in each class possess similar properties and (b) the number of representatives in each class is much less than that of Boolean functions.Earlier, when two Boolean functions ofn-variable differ only by permutation or complementation of their variables, they fall into equivalence classes. The formula for counting the number of such equivalence classes is given in [1]. Further, it has also been elaborated in [2] about the procedures of selection of a representative assembly, with one member from each equivalence class. In [3], the linear group and the affine Boolean function group of transformations have been defined and an algorithm has been proposed for counting the number of classes under both groups. The classification of the set of n-input functions is specifically based on three criteria: the number of functions, the number of P classes, and the number of NPN classes, which are first introduced in [4]. Classification of the affine equivalence classes of cosets of the first order Reed-Muller code with respect to cryptographic properties such as correlation immunity, resiliency, and propagation characteristics has been discussed in [5–8]. Heuristic design of cryptographically strong balanced Boolean function was envisaged in [9]. In [10], three variable Boolean functions in the name of 3-neighborhood cellular automata rules have been classified on the basis of hamming distance with respect to linear rules. The characterization of 3-variable non-linear Boolean functions has been undertaken in three different ways, by Boolean derivatives, by deviant states, and by matrices as elaborated in the papers [10–12], respectively.In this paper, two methods have been proposed for generating equivalence classes of Boolean functions with a specific objective in our mind that, in each class, exactly one affine Boolean function is present. The first method is a recursive approach to classifyn-variable Boolean functions starting from 1-variable to higher variables. In the second method, the classification is done through changing some variable bit positions with respect to the affine function belonging to that class.In the following sections, the paper is organized in a precise methodical manner. In Section2, the literature of Boolean functions of different variables relevant to our work is reviewed. In Section 3, the method of recursive classification of n-variable Boolean functions is introduced and the properties of these classes are discussed. Based on these properties another efficient method has also been proposed for generating the same classes of n-variable Boolean functions. In Section 4, we have studied the behavior of those classes by using different binary operations such as Hamming distance (HD), XOR operation, and Carry value transformation (CVT) [13]. Section 5 deals with concluding remarks emphasizing the key factors of the entire analysis.


## 2. Relevant Review

Ann-variable Boolean function f is a mapping from the set of all possible n-bit strings {0,1}n into {0,1}. The number of different n-variable Boolean functions is 22n, where each function can be represented by a truth table output as a binary string of length 2n. The decimal equivalent of the binary string starting from bottom to top (least significant bit) in the truth table is called the rule number of that function [14]. The complement of f is denoted as f¯.A Boolean function with algebraic expression, where the degree is at most one is called an affine Boolean function. The general form forn-variable affine function is
(1)faffine(x1,x2,x3,…,xn)=knxn⊕kn-1xn-1⊕⋯⊕k2x2⊕k1x1⊕k0,
where the coefficients are either zero or one.If the constant termk0 of an affine function is zero then the function is called a linear Boolean function. Thus, affine Boolean functions are either linear Boolean functions or their complements. The number of different n-variable affine Boolean functions is 2n+1 out of which 2n are linear. As an example, the 16 affine Boolean functions in 3-variables are 0, 60, 90, 102, 150, 170, 204, 240, 15, 51, 85, 105, 153, 165, 195, and 255 out of which the first eight are linear and the remaining Boolean functions are their corresponding complements [3].The concatenation of the Boolean functionf with itself and the concatenation of f with its complement f¯ are denoted as ff and ff¯, respectively. For example,
(2)iff=(00),thenff=(0000),ff¯=(0011).Note that iff is a Boolean function of n-variable, then ff and ff¯ are Boolean functions of (n+1)-variable.Theorem 1.
fis linear if and only if ff and ff¯ are linear.Apart from the above concatenations as stated in Theorem1, all other concatenations give non-linear Boolean functions [15].Corollary 2.
f is an affine Boolean function if and only if ff, ff¯, f¯f, and f¯f¯ are affine Boolean functions.Proof.
The proof of the corollary easily follows from Theorem1 as affine Boolean functions are either linear Boolean functions or their complements.


## 3. Proposed Methods for Classification of Boolean Functions

In this section, two different methods have been proposed to classify the set of all possiblen-variable Boolean functions such that each class is of equal cardinality and contains only a single affine function.


### 3.1. A Recursive Procedure to Classifyn-Variable Boolean Functions

LetS1={{00},{10},{11},{01}} be a set of all 1-variable Boolean functions. Here all the Boolean functions are affine. Let S1′={{00},{10}} be a set containing all linear Boolean functions of 1-variable, and S1′′={{11},{01}} is the complement of the set S1′. The Cartesian product of the sets S1 with S1′ and S1′′ is defined successively as follows:
(3)S1×S1′={{0000,0010},{1000,1010},{1100,1110},{0100,0110}},S1×S1′′={{0011,0001},{1011,1001},{1111,1101},{0111,0101}}.
Note that, S1 contains four classes each containing a 1-variable Boolean functions whereas, the set (S1×S1′)∪(S1×S1′′) contains eight disjoint classes of all 2-variable Boolean functions. Here, each class contains exactly one 2-variable affine Boolean function as highlighted above in (3). This process is repeated for the next higher variable, using the recursive formula of the following.(i)
Base case: (forn=1)
(4)S1′={{00},{10}},S1′′={{11},{01}},S1=(S1′∪S1′′)={{00},{10},{11},{01}}.(ii)
Recursion: (forn≥2)
(5)Sn′=(Sn-1×Sn-1′),Sn′′=(Sn-1×Sn-1′′),Sn=(Sn-1′∪Sn-1′′),where Sn contains the classes of all n-variable Boolean functions, where each class contains exactly one n-variable affine function. Here both the sets Sn′ and Sn′′ are complement to each other.Theorem 3.
The recursive procedure of (4) and (5), when repeated up to (n-1) times, classifies the set of all n-variable Boolean functions into 2n+1 number of disjoint classes. such that each class contains exactly one n-variable affine Boolean function along with some n-variable non-linear Boolean functions.Proof.
The result follows because of the fact that(Sn-1×Sn-1′)∪(Sn-1×Sn-1′)=Sn-1×(Sn-1′∪Sn-1′′)=Sn-1×Sn-1=Sn and (Sn-1×Sn-1′)∩(Sn-1×Sn-1′′)=Sn-1×(Sn-1′∩Sn-1′′)=Sn-1×ϕ=ϕ. And the property that each class contains exactly one n-variable affine Boolean function can be ascertained on using Corollary 2 of Section 2.Illustration (from 2-variable classes to 3-variable classes).From (4) and (5) the set
(6)S2={{0000,0010},{1000,1010},{1100,1110},{0100,0110}{0011,0001},{1011,1001},{1111,1101},{0111,0101}},
and this set contains the classes of all 2-variable Boolean functions. The set S2′={{0000,0010},{1000,1010},{1100,1110},{0100,0110}} is the first four classes of S2 and S2′′={{0011,0001},{1011,1001},{1111,1101},{0111,0101}} is the set containing the remaining classes of S2 and complement of the set S2′. Now, the classes of 3-variables are generated using the formula as S3′=(S2×S2′),  S3′′=(S2×S2′′), and S3=(S3′∪S3′′). Some of the class members are shown in the following:(7)S3′={00000000,00000010,00001000,00001010,00001100,00001110,00000100,00000110,Class2,…,Class800100000,00100010,00101000,00101010,00101100,00101110,00100100,00100110},S3′′={00000011,00000001,00001011,00001001,00001111,00001101,00000111,00000101,Class10,…,Class1600100011,00100001,00101011,00101001,00101111,00101101,00100111,00100101}.
The naming of the classes is given as class 1, class 2,…, class 2n+1 such that the complement of class k is the class (2n+k) where k=1,2,3,…,2n. In (7), only the members of 1 and 13 are shown and other classes of Boolean functions are shown in Appendix A.Theorem 4.
The number of different classes in the above classification is2n+1.Proof.
As each class contains exactly one affine Boolean function, the number of classes ofn-variable is the same as the number of affine Boolean functions and equals to 2n+1.Theorem 5.
The classes are of equal size and the cardinality of each class is equal to22n-(n+1).Proof.
The equal size of the classes easily follows from the cardinality of the two setsSn′ and Sn′′. On using Theorem 4, the cardinality of each class = (totalnumberofn-variableBooleanfunctions)/(totalnumberofn-variableaffineBooleanfunctions)=(22n)/(2n+1)=22n-(n+1).Theorem 6.
The least significant bit of all the Boolean functions inSn′ is 0, whereas in Sn′′ it is 1.Proof.
Whenn=1, that is for the base case of the recursion, the least significant bit position of all the Boolean functions in the set S1′ is 0 and for the set S1′′ it is 1. Therefore, the recursive procedure using the Cartesian product also preserves the same property for the next higher variable.Interestingly, the relation defined in the recursive procedure is operating on the set of(n-1)-variable Boolean functions, but the partition is obtained in the set of n-variable Boolean functions. Therefore, an equivalence relation must exist on the set of n-variable Boolean functions, which divides the set into disjoint equivalence classes.Theorem 7.
For each class ofn-variable, the length of a Boolean function is 2n, out of which (n+1) bits are fixed and the remaining (2n-(n+1)) bits are changing with respect to the affine Boolean function of that class. The (n+1) bit positions of a Boolean function which are fixed in a class are calculated using the formula Pn-2k, where Pn=(2n+1) and the values of k=0,1,2,…,n.Proof (using mathematical induction).
Basis. For n=1, each class contains a single Boolean function of length 2. Hence both the first and second bit positions are fixed and it satisfies the formula P1-2k=(21+1)-2k for k=0 and 1. So, the bit positions are 3-20=2 and 3-21=1. Hence the formula is valid for n=1.
Induction Hypothesis. Assume that the formula is valid for the classes of (n-1)-variable Boolean functions, Sn-1. From recursive definition, the formula is also valid for all the classes of Sn-1′ and Sn-1′′. Thus, by induction hypothesis, the invariant bit positions of a class of Sn-1 is calculated using the formula as given below:
(8)Pn-1-2k,wherePn-1=2n-1+1,k=0,1,2,…,n-1.
Induction. Here we have to prove that the formula is true for all classes in Sn. According to the recursive formula Sn=(Sn′∪Sn′′) where Sn′=(Sn-1×Sn-1′) and Sn′′=(Sn-1×Sn-1′′). Consider a particular class of Sn-1 and let it be C1. The corresponding classes of Sn′ which will be generated using (C1×Sn-1′) must contain the Boolean functions of length 2n, where the first 2n-1 (starting from most significant bit) bit positions are from a single class C1. And hence by induction hypothesis, n number of bit positions is fixed and satisfies (9). From Theorem 6, the least significant bit position of the remaining string of length 2n-1 is 0 for all the members of the classes of Sn′. Therefore, the bit positions of a Boolean function, which are fixed in a class of Sn′ is calculated by adding 2n-1 to all the numbers generated from (9). Along with this, we have to include the least significant bit position (or the first position) in the formula, which gives (n+1) invariant positions of a class in Sn. Thus for Sn, the formula is calculated as follows:
fork=0,1,2,…,n-1,
(9){Pn-1-2k}+2n-1={(2n-1+1)-2k}+2n-1={2n+1}-2k=Pn-2k;
for k=n, the value is 1:
(10)1=(2n+1)-2n=Pn-2n=Pn-2k.
So the formula is true for all the values ofk=0,1,2,…,n. The above formula is also true for all the classes of Sn, as any class in Sn is either generated using the formula (Sn-1×Sn-1′) or (Sn-1×Sn-1′′). Hence, by the principle of mathematical induction, we conclude that Pn-2k is true for all positive integers n.
Illustration. For every 1-variable Boolean function, all the bit positions are fixed and the bit positions are (21+1)-20=2 and (21+1)-21=1. For every 2-variable Boolean function, three bit positions are fixed and the bit positions are (22+1)-20=4, (22+1)-21=3, and (22+1)-22=1. Similarly, for every 3-variable Boolean function, four bit positions are fixed and the bit positions are (23+1)-20=8, (23+1)-21=7, (23+1)-22=5, and (23+1)-23=1. For 3-variable functions, all classes and their subclasses are given in Appendix A.
The set of bit positions which are changing in a class can be calculated by subtracting the set of invariant bit positions from the set{1,2,3,…,2n}.Corollary 8.
The bit positions which are fixed or changing are invariant for all classes with respect to the concerned affine function of that class.Proof.
The formula given in Theorem7 is used to calculate the bit positions which are fixed or changing and valid for an arbitrary class. Hence, it is also valid for all classes.Using the result of Theorem7, an equivalence relation has been defined on the set of all possible n-variable Boolean functions by which the same class or classes can be generated without using recursion.Letf and g be two n-variable Boolean functions, and R is a binary relation on the set of n-variable Boolean functions defined as fRg if and only if “there exist (n+1) bit positions calculated on using Theorem 7 and the calculated bit positions are the same for the functions f and g.” Clearly, (1)
fRf∀f. So, R is reflexive.(2)
IffRg then gRf. So, R is symmetric.(3)
IffRg and gRh then fRh. So, R is transitive. Hence, R is an equivalence relation. The next procedure uses the above equivalence relation and can efficiently generate the same class or classes without using the recursive procedure.


### 3.2. Procedure to Generate the Same Class without Using Recursion

Letf be an n-variable affine Boolean function. Let B be an array which is used to store the bit positions, which are fixed for a Boolean function with respect to the affine function. Array B can be calculated using Algorithm 9. The worst case time complexity of the Algorithm is O(n).Algorithm 9 (fixed-bit positions (f)).
(1)
InitializeX=2n
(2)
for(i=0 to n)
(3)
{
(4)
B
[
i
] = X
(5)
X = B[i]-2i
(6)
}
(7)
returnB.By invoking the above function in an algorithm, we can get other non-linear functions in a class. For this purpose, one has to put all possible binary sequences of length2n-(n+1), except those fixed bit positions of f. Taking different affine functions as input, different classes can be generated.


### 3.3.  List of Inferences Drawn from the above Classification Method

(1)
The method of keeping some of the bit positions fixed and varying other bit positions with respect to a Boolean function will be a handle to find out equivalence classes of equal cardinality.
(2)
The number of equivalence classes is equal to2k, where k is the number of fixed positions.
(3)
Different set of fixed positions generates different classes of Boolean functions.
(4)
The number of members in a particular class is2l for 0≤l≤2n-k, where l is the number of changing bit positions.
(5)
How to select the set of representative functions that generate disjoint equivalence classes of equal cardinality? The generators are all possiblek bit sequences in the fixed positions and the rest of the positions are arbitrarily filled up by 0/1. Any Boolean function generated through this procedure can be a representative for the class. The number of generators for the proposed classification is 2k.
(6)
Any Boolean function of a class can be a representative of that class. In fact, taking affine function as the representative of a class will provide us with the guarantee of the inclusion of that affine function in that class.


## 3.1. A Recursive Procedure to Classifyn-Variable Boolean Functions

LetS1={{00},{10},{11},{01}} be a set of all 1-variable Boolean functions. Here all the Boolean functions are affine. Let S1′={{00},{10}} be a set containing all linear Boolean functions of 1-variable, and S1′′={{11},{01}} is the complement of the set S1′. The Cartesian product of the sets S1 with S1′ and S1′′ is defined successively as follows:
(3)S1×S1′={{0000,0010},{1000,1010},{1100,1110},{0100,0110}},S1×S1′′={{0011,0001},{1011,1001},{1111,1101},{0111,0101}}.
Note that, S1 contains four classes each containing a 1-variable Boolean functions whereas, the set (S1×S1′)∪(S1×S1′′) contains eight disjoint classes of all 2-variable Boolean functions. Here, each class contains exactly one 2-variable affine Boolean function as highlighted above in (3). This process is repeated for the next higher variable, using the recursive formula of the following.(i)
Base case: (forn=1)
(4)S1′={{00},{10}},S1′′={{11},{01}},S1=(S1′∪S1′′)={{00},{10},{11},{01}}.(ii)
Recursion: (forn≥2)
(5)Sn′=(Sn-1×Sn-1′),Sn′′=(Sn-1×Sn-1′′),Sn=(Sn-1′∪Sn-1′′),where Sn contains the classes of all n-variable Boolean functions, where each class contains exactly one n-variable affine function. Here both the sets Sn′ and Sn′′ are complement to each other.Theorem 3.
The recursive procedure of (4) and (5), when repeated up to (n-1) times, classifies the set of all n-variable Boolean functions into 2n+1 number of disjoint classes. such that each class contains exactly one n-variable affine Boolean function along with some n-variable non-linear Boolean functions.Proof.
The result follows because of the fact that(Sn-1×Sn-1′)∪(Sn-1×Sn-1′)=Sn-1×(Sn-1′∪Sn-1′′)=Sn-1×Sn-1=Sn and (Sn-1×Sn-1′)∩(Sn-1×Sn-1′′)=Sn-1×(Sn-1′∩Sn-1′′)=Sn-1×ϕ=ϕ. And the property that each class contains exactly one n-variable affine Boolean function can be ascertained on using Corollary 2 of Section 2.Illustration (from 2-variable classes to 3-variable classes).From (4) and (5) the set
(6)S2={{0000,0010},{1000,1010},{1100,1110},{0100,0110}{0011,0001},{1011,1001},{1111,1101},{0111,0101}},
and this set contains the classes of all 2-variable Boolean functions. The set S2′={{0000,0010},{1000,1010},{1100,1110},{0100,0110}} is the first four classes of S2 and S2′′={{0011,0001},{1011,1001},{1111,1101},{0111,0101}} is the set containing the remaining classes of S2 and complement of the set S2′. Now, the classes of 3-variables are generated using the formula as S3′=(S2×S2′),  S3′′=(S2×S2′′), and S3=(S3′∪S3′′). Some of the class members are shown in the following:(7)S3′={00000000,00000010,00001000,00001010,00001100,00001110,00000100,00000110,Class2,…,Class800100000,00100010,00101000,00101010,00101100,00101110,00100100,00100110},S3′′={00000011,00000001,00001011,00001001,00001111,00001101,00000111,00000101,Class10,…,Class1600100011,00100001,00101011,00101001,00101111,00101101,00100111,00100101}.
The naming of the classes is given as class 1, class 2,…, class 2n+1 such that the complement of class k is the class (2n+k) where k=1,2,3,…,2n. In (7), only the members of 1 and 13 are shown and other classes of Boolean functions are shown in Appendix A.Theorem 4.
The number of different classes in the above classification is2n+1.Proof.
As each class contains exactly one affine Boolean function, the number of classes ofn-variable is the same as the number of affine Boolean functions and equals to 2n+1.Theorem 5.
The classes are of equal size and the cardinality of each class is equal to22n-(n+1).Proof.
The equal size of the classes easily follows from the cardinality of the two setsSn′ and Sn′′. On using Theorem 4, the cardinality of each class = (totalnumberofn-variableBooleanfunctions)/(totalnumberofn-variableaffineBooleanfunctions)=(22n)/(2n+1)=22n-(n+1).Theorem 6.
The least significant bit of all the Boolean functions inSn′ is 0, whereas in Sn′′ it is 1.Proof.
Whenn=1, that is for the base case of the recursion, the least significant bit position of all the Boolean functions in the set S1′ is 0 and for the set S1′′ it is 1. Therefore, the recursive procedure using the Cartesian product also preserves the same property for the next higher variable.Interestingly, the relation defined in the recursive procedure is operating on the set of(n-1)-variable Boolean functions, but the partition is obtained in the set of n-variable Boolean functions. Therefore, an equivalence relation must exist on the set of n-variable Boolean functions, which divides the set into disjoint equivalence classes.Theorem 7.
For each class ofn-variable, the length of a Boolean function is 2n, out of which (n+1) bits are fixed and the remaining (2n-(n+1)) bits are changing with respect to the affine Boolean function of that class. The (n+1) bit positions of a Boolean function which are fixed in a class are calculated using the formula Pn-2k, where Pn=(2n+1) and the values of k=0,1,2,…,n.Proof (using mathematical induction).
Basis. For n=1, each class contains a single Boolean function of length 2. Hence both the first and second bit positions are fixed and it satisfies the formula P1-2k=(21+1)-2k for k=0 and 1. So, the bit positions are 3-20=2 and 3-21=1. Hence the formula is valid for n=1.
Induction Hypothesis. Assume that the formula is valid for the classes of (n-1)-variable Boolean functions, Sn-1. From recursive definition, the formula is also valid for all the classes of Sn-1′ and Sn-1′′. Thus, by induction hypothesis, the invariant bit positions of a class of Sn-1 is calculated using the formula as given below:
(8)Pn-1-2k,wherePn-1=2n-1+1,k=0,1,2,…,n-1.
Induction. Here we have to prove that the formula is true for all classes in Sn. According to the recursive formula Sn=(Sn′∪Sn′′) where Sn′=(Sn-1×Sn-1′) and Sn′′=(Sn-1×Sn-1′′). Consider a particular class of Sn-1 and let it be C1. The corresponding classes of Sn′ which will be generated using (C1×Sn-1′) must contain the Boolean functions of length 2n, where the first 2n-1 (starting from most significant bit) bit positions are from a single class C1. And hence by induction hypothesis, n number of bit positions is fixed and satisfies (9). From Theorem 6, the least significant bit position of the remaining string of length 2n-1 is 0 for all the members of the classes of Sn′. Therefore, the bit positions of a Boolean function, which are fixed in a class of Sn′ is calculated by adding 2n-1 to all the numbers generated from (9). Along with this, we have to include the least significant bit position (or the first position) in the formula, which gives (n+1) invariant positions of a class in Sn. Thus for Sn, the formula is calculated as follows:
fork=0,1,2,…,n-1,
(9){Pn-1-2k}+2n-1={(2n-1+1)-2k}+2n-1={2n+1}-2k=Pn-2k;
for k=n, the value is 1:
(10)1=(2n+1)-2n=Pn-2n=Pn-2k.
So the formula is true for all the values ofk=0,1,2,…,n. The above formula is also true for all the classes of Sn, as any class in Sn is either generated using the formula (Sn-1×Sn-1′) or (Sn-1×Sn-1′′). Hence, by the principle of mathematical induction, we conclude that Pn-2k is true for all positive integers n.
Illustration. For every 1-variable Boolean function, all the bit positions are fixed and the bit positions are (21+1)-20=2 and (21+1)-21=1. For every 2-variable Boolean function, three bit positions are fixed and the bit positions are (22+1)-20=4, (22+1)-21=3, and (22+1)-22=1. Similarly, for every 3-variable Boolean function, four bit positions are fixed and the bit positions are (23+1)-20=8, (23+1)-21=7, (23+1)-22=5, and (23+1)-23=1. For 3-variable functions, all classes and their subclasses are given in Appendix A.
The set of bit positions which are changing in a class can be calculated by subtracting the set of invariant bit positions from the set{1,2,3,…,2n}.Corollary 8.
The bit positions which are fixed or changing are invariant for all classes with respect to the concerned affine function of that class.Proof.
The formula given in Theorem7 is used to calculate the bit positions which are fixed or changing and valid for an arbitrary class. Hence, it is also valid for all classes.Using the result of Theorem7, an equivalence relation has been defined on the set of all possible n-variable Boolean functions by which the same class or classes can be generated without using recursion.Letf and g be two n-variable Boolean functions, and R is a binary relation on the set of n-variable Boolean functions defined as fRg if and only if “there exist (n+1) bit positions calculated on using Theorem 7 and the calculated bit positions are the same for the functions f and g.” Clearly, (1)
fRf∀f. So, R is reflexive.(2)
IffRg then gRf. So, R is symmetric.(3)
IffRg and gRh then fRh. So, R is transitive. Hence, R is an equivalence relation. The next procedure uses the above equivalence relation and can efficiently generate the same class or classes without using the recursive procedure.


## 3.2. Procedure to Generate the Same Class without Using Recursion

Letf be an n-variable affine Boolean function. Let B be an array which is used to store the bit positions, which are fixed for a Boolean function with respect to the affine function. Array B can be calculated using Algorithm 9. The worst case time complexity of the Algorithm is O(n).Algorithm 9 (fixed-bit positions (f)).
(1)
InitializeX=2n
(2)
for(i=0 to n)
(3)
{
(4)
B
[
i
] = X
(5)
X = B[i]-2i
(6)
}
(7)
returnB.By invoking the above function in an algorithm, we can get other non-linear functions in a class. For this purpose, one has to put all possible binary sequences of length2n-(n+1), except those fixed bit positions of f. Taking different affine functions as input, different classes can be generated.


## 3.3.  List of Inferences Drawn from the above Classification Method

(1)
The method of keeping some of the bit positions fixed and varying other bit positions with respect to a Boolean function will be a handle to find out equivalence classes of equal cardinality.
(2)
The number of equivalence classes is equal to2k, where k is the number of fixed positions.
(3)
Different set of fixed positions generates different classes of Boolean functions.
(4)
The number of members in a particular class is2l for 0≤l≤2n-k, where l is the number of changing bit positions.
(5)
How to select the set of representative functions that generate disjoint equivalence classes of equal cardinality? The generators are all possiblek bit sequences in the fixed positions and the rest of the positions are arbitrarily filled up by 0/1. Any Boolean function generated through this procedure can be a representative for the class. The number of generators for the proposed classification is 2k.
(6)
Any Boolean function of a class can be a representative of that class. In fact, taking affine function as the representative of a class will provide us with the guarantee of the inclusion of that affine function in that class.


## 4. Different Operations in Classes

In this section, classes are divided into several subclasses on using the Hamming distance (HD) between the Boolean functions and the affine function in that class. Also, the classes are analyzed on performing XOR and CVT operations among the functions of a class.


### 4.1. Subclassification

Hamming distance (HD) between two Boolean functions is denoted asHD(f,g)=k, where k can be 0,1,2,…,2n-(n+1) where f is a Boolean function and g is an affine Boolean function and both belong to the same class of n-variable. Further, Boolean functions in a class having HD=k with respect to the corresponding affine Boolean function form subclasses whose cardinality isbinomial coefficients of the form Ck2n-(n+1), where k=0,1,2,…,2n-(n+1).Illustration. Table 1 shows the 3-variable Boolean functions belonging to class 1, where the affine Boolean function is 0=(00000000). There are five subclasses having cardinality 1, 4, 6, 4, and 1 with Hamming distance (HD)0, 1, 2, 3, and 4, respectively. For 3-variables all classes and their subclasses are given in Appendix A.Table 1
Different subclasses of class 1.
Boolean functions
Decimal value
HD wrt affine Boolean function
No. of Boolean function
00000000(Affine)
0
0
1
00000010
2
1
4
00100000
32
00001000
8
00000100
4
00100010
34
2
6
00001010
10
00101000
40
00001100
12
00000110
4
00100100
36
00101010
42
3
4
00001110
14
00101100
44
00001100
12
00100110
38
00101110
36
4
1


### 4.2. XOR Operation in Classes

Leta=(a2n,a2n-1,…,a1) and b=(b2n,b2n-1,…,b1) be two n-variable Boolean functions belonging to a particular class. The XOR operation of all the classes when arranged in a table only gives those entries given by class 1 functions, as (a+k)⊕(b+k)=(a⊕b)+(k⊕k)=(a⊕b), where, the XOR operation of a and b is defined as a⊕b=(a2n⊕b2n,a2n-1⊕b2n-1,…,a1⊕b1).Illustration. Suppose we want the XOR operation of (44)10 = (00101100)2 and (34)10 = (00100010)2 both belonging to class 1 of 3-variables. And 44⊕34 =(00101100)⊕(00100010)=(00001110)= 14. Table 2 is constructed for all classes of n-variable Boolean functions that contain only the XOR values of all the functions in a class. The functions are arranged in ascending order in both rows and columns of the table. It can be proved that the content of each table remain invariant under the XOR operation and the decimal values of the content in the table are same as in class 1. For 3-variables the XOR operation of other classes are given in Appendix B.Table 2
XOR values of class 1 of 3-variable Boolean functions.
XOR
0
2
4
6
8
10
12
14
32
34
36
38
40
42
44
46
0
0
2
4
6
8
10
12
14
32
34
36
38
40
42
44
46
2
2
0
6
4
10
8
14
12
34
32
38
36
42
40
46
44
4
4
6
0
2
12
14
8
10
36
38
32
34
44
46
40
42
6
6
4
2
0
14
12
10
8
38
36
34
32
46
44
42
40
8
8
10
12
14
0
2
4
6
40
42
44
46
32
34
36
38
10
10
8
14
12
2
0
6
4
42
40
46
44
34
32
38
36
12
12
14
8
10
4
6
0
2
44
46
40
42
36
38
32
34
14
14
12
10
8
6
4
2
0
46
44
42
40
38
36
34
32
32
32
34
36
38
40
42
44
46
0
2
4
6
8
10
12
14
34
34
32
38
36
42
40
46
44
2
0
6
4
10
8
14
12
36
36
38
32
34
44
46
40
42
4
6
0
2
12
14
8
10
38
38
36
34
32
46
44
42
40
6
4
2
0
14
12
10
8
40
40
42
44
46
32
34
36
38
8
10
12
14
0
2
4
6
42
42
40
46
44
34
32
38
36
10
8
14
12
2
0
6
4
44
44
46
40
42
36
38
32
34
12
14
8
10
4
6
0
2
46
46
44
42
40
38
36
34
32
14
12
10
8
6
4
2
0


### 4.3. CVT Operation in Classes

Leta=(ak,ak+1,…,a1) and b=(bk,bk+1,…,b1) be two Boolean functions in a Class. Then the Carry Value Transform (CVT) of a and b is defined in [13] as CVT(a,b)=(ak∧bk,ak-1∧bk-1,…,a1∧b1,0). Carry Value Transformation (CVT) is a kind of representation of n-variable Boolean functions and is used to produce many interesting patterns [13]. Under the CVT operation, we have observed some interesting self-similar fractal patterns which are invariant for all classes of n-variable Boolean functions.Illustration. The CVT operation of (44)10=(00101100)2 and (34)10=(00100010)2 is 64. The patterns for class 1 functions using CVT operation is shown in Table 3 and others are shown in Appendix C.Table 3
CVT patterns of class 1 of 3-variable Boolean functions.


## 4.1. Subclassification

Hamming distance (HD) between two Boolean functions is denoted asHD(f,g)=k, where k can be 0,1,2,…,2n-(n+1) where f is a Boolean function and g is an affine Boolean function and both belong to the same class of n-variable. Further, Boolean functions in a class having HD=k with respect to the corresponding affine Boolean function form subclasses whose cardinality isbinomial coefficients of the form Ck2n-(n+1), where k=0,1,2,…,2n-(n+1).Illustration. Table 1 shows the 3-variable Boolean functions belonging to class 1, where the affine Boolean function is 0=(00000000). There are five subclasses having cardinality 1, 4, 6, 4, and 1 with Hamming distance (HD)0, 1, 2, 3, and 4, respectively. For 3-variables all classes and their subclasses are given in Appendix A.Table 1
Different subclasses of class 1.
Boolean functions
Decimal value
HD wrt affine Boolean function
No. of Boolean function
00000000(Affine)
0
0
1
00000010
2
1
4
00100000
32
00001000
8
00000100
4
00100010
34
2
6
00001010
10
00101000
40
00001100
12
00000110
4
00100100
36
00101010
42
3
4
00001110
14
00101100
44
00001100
12
00100110
38
00101110
36
4
1


## 4.2. XOR Operation in Classes

Leta=(a2n,a2n-1,…,a1) and b=(b2n,b2n-1,…,b1) be two n-variable Boolean functions belonging to a particular class. The XOR operation of all the classes when arranged in a table only gives those entries given by class 1 functions, as (a+k)⊕(b+k)=(a⊕b)+(k⊕k)=(a⊕b), where, the XOR operation of a and b is defined as a⊕b=(a2n⊕b2n,a2n-1⊕b2n-1,…,a1⊕b1).Illustration. Suppose we want the XOR operation of (44)10 = (00101100)2 and (34)10 = (00100010)2 both belonging to class 1 of 3-variables. And 44⊕34 =(00101100)⊕(00100010)=(00001110)= 14. Table 2 is constructed for all classes of n-variable Boolean functions that contain only the XOR values of all the functions in a class. The functions are arranged in ascending order in both rows and columns of the table. It can be proved that the content of each table remain invariant under the XOR operation and the decimal values of the content in the table are same as in class 1. For 3-variables the XOR operation of other classes are given in Appendix B.Table 2
XOR values of class 1 of 3-variable Boolean functions.
XOR
0
2
4
6
8
10
12
14
32
34
36
38
40
42
44
46
0
0
2
4
6
8
10
12
14
32
34
36
38
40
42
44
46
2
2
0
6
4
10
8
14
12
34
32
38
36
42
40
46
44
4
4
6
0
2
12
14
8
10
36
38
32
34
44
46
40
42
6
6
4
2
0
14
12
10
8
38
36
34
32
46
44
42
40
8
8
10
12
14
0
2
4
6
40
42
44
46
32
34
36
38
10
10
8
14
12
2
0
6
4
42
40
46
44
34
32
38
36
12
12
14
8
10
4
6
0
2
44
46
40
42
36
38
32
34
14
14
12
10
8
6
4
2
0
46
44
42
40
38
36
34
32
32
32
34
36
38
40
42
44
46
0
2
4
6
8
10
12
14
34
34
32
38
36
42
40
46
44
2
0
6
4
10
8
14
12
36
36
38
32
34
44
46
40
42
4
6
0
2
12
14
8
10
38
38
36
34
32
46
44
42
40
6
4
2
0
14
12
10
8
40
40
42
44
46
32
34
36
38
8
10
12
14
0
2
4
6
42
42
40
46
44
34
32
38
36
10
8
14
12
2
0
6
4
44
44
46
40
42
36
38
32
34
12
14
8
10
4
6
0
2
46
46
44
42
40
38
36
34
32
14
12
10
8
6
4
2
0


## 4.3. CVT Operation in Classes

Leta=(ak,ak+1,…,a1) and b=(bk,bk+1,…,b1) be two Boolean functions in a Class. Then the Carry Value Transform (CVT) of a and b is defined in [13] as CVT(a,b)=(ak∧bk,ak-1∧bk-1,…,a1∧b1,0). Carry Value Transformation (CVT) is a kind of representation of n-variable Boolean functions and is used to produce many interesting patterns [13]. Under the CVT operation, we have observed some interesting self-similar fractal patterns which are invariant for all classes of n-variable Boolean functions.Illustration. The CVT operation of (44)10=(00101100)2 and (34)10=(00100010)2 is 64. The patterns for class 1 functions using CVT operation is shown in Table 3 and others are shown in Appendix C.Table 3
CVT patterns of class 1 of 3-variable Boolean functions.


## 5. Conclusion

The novelty of this paper lies in its systematic classification of Boolean functions with focal emphasis on the prominent binary operations like Hamming distance, XOR, and CVT. The present analytical study introduces a new way towards the formulation of an universal classifier of arbitrary length which is being actively pursued. The procedures followed in this paper are very handy and useful even for our future experimental research in this domain of theoretical computer science. A number of tables have been incorporated in this paper for easy reference and clear comprehension showing varied subclasses, patterns, and values of different classes.



---

*Source: 270424-2013-10-31.xml*