9 An Algorithm for Linear, Affine and Spectral Classification of Boolean Functions
205
Table 9.4 Linear equivalence classes n = 1, 2, 3
Spectrum
Class (n = 1)
f R
Count
0
1
1
0
1
2
0
2
1
1
0
−2
3
2
1
0
2
4
3
1
−2
0
Spectrum
Class (n = 2)
f R
Count
0
1
2
12
1
0
1
4
0
0
0
2
1
1
2
−2
−2
−2
3
5
3
0
−4
0
0
4
8
3
2
2
2
−2
5
10
3
0
4
0
0
6
11
3
−2
2
−2
−2
7
14
1
−2
2
2
2
8
15
1
−4
0
0
0
Spectrum
Class (n = 3) f R
Count
0
1
2
3
12
13 23 123
1
0
1
8
0
0
0
0
0
0
0
2
1
1
6
−2
−2
−2
−2
−2 −2
−2
3
17
7
4
−4
−4
0
−4
0
0
0
4
43
28
0
4
−4
−4
0
0
0
−4
5
69
21
2
−6
2
−2
2
−2 −2
−2
6
84
7
2
−6
2
2
2
2
2
2
7
85
7
0
−8
0
0
0
0
0
0
8
128
7
6
2
2
2
−2
−2 −2
2
9
136
21
4
4
4
0
−4
0
0
0
10
168
28
2
6
2
2
−2
−2
2
−2
11
170
7
0
8
0
0
0
0
0
0
12
171
7
−2
6
−2
−2
−2
−2 −2
−2
13
187
21
−4
4
−4
0
−4
0
0
0
14
213
28
−2
−6
2
2
−2
−2 −2
2
15
232
28
0
4
4
4
0
0
0
−4
16
234
21
−2
6
2
2
2
2 −2
−2
17
238
7
−4
4
4
0
4
0
0
0
18
239
7
−6
2
2
−2
2
−2 −2
−2
19
254
1
−6
2
2
2
2
2
2
2
20
255
1
−8
0
0
0
0
0
0
0
the representative function. Note the significantly different sizes of the equivalence
classes. The distribution of the linear class sizes for n = 4 is shown in Fig. 9.1.
For n = 5 there are 2 2 5 = 4,294,967,296 Boolean functions which makes the
above approach impractical. We thus consider one function from each of the 616,126