204
D. M. Miller and M. Soeken
It is important to note that all coefficients, except for S 0 when v > 0, are
considered in line 19. This may seem odd since for v > 0 choices have already
been made for positions 0, 1, . . . , v − 1 and one might think only coefficients in
positions v or higher need to be considered. The consideration of already placed
coefficients is necessary to ensure potential variable swaps are properly considered.
As noted earlier, the above describes using TRANSFORM for spectral classification, and that linear and affine classification can be implemented by simply
‘turning off’ certain translations. TRANSFORM cannot be easily adapted for NPN
classification. The reason is that TRANSFORM relies on using type 4 translations
to move spectral coefficients from one order to another. This is applicable to linear,
affine and spectral classification, but type 4 translations are not available in NPN
classification. A key result of using type 4 translations is that for linear, affine
and spectral classification the representative function f R for a class always has a
nonzero first-order coefficient for a variable, unless all coefficients involving that
variable are zero. That is not true for the NPN classification case.
NPN classification requires using type 1 translations (permutations) to move
spectral coefficients within a group. NPN classification thus requires the choice of
appropriate negations and sorting of coefficients within orders. An NPN classification algorithm thus has a structure and approach quite different from TRANSFORM.
9.5 Experimental Results
All experiments were performed on a PC with an Intel i5 2 Core processor running
at 3.2 GHz and 3.0 GB RAM.
Our first experiment was to generate the linear, affine and spectral classes for
n = 1, 2, 3, 4. The execution times and the number of classes (in brackets) are
given in Table 9.3. In each case we found the number of classes given in Table 9.2.
The results for n = 1, 2, 3, 4 were found by applying TRANSFORM to all
Boolean functions of the given number of variables and maintaining a list of
the representative functions found in each case. The classes found are shown in
Tables 9.4, 9.5, and 9.6 except for the linear case for n = 4 which has 92
classes. For each class, we show the representative function f R coded as a decimal
number, the count of the number of functions in the class and the spectrum for
Table 9.3 CPU sec. for class
generation
n Linear classes Affine classes Spectral classes
1 0.003 (4)
0.002 (3)
0.002(1)
2 0.005 (8)
0.003 (5)
0.002(2)
3 0.019 (20)
0.100 (10)
0.006(3)
4 8.298 (92)
9.212 (32)
12.53(8)
D. M. Miller and M. Soeken
It is important to note that all coefficients, except for S 0 when v > 0, are
considered in line 19. This may seem odd since for v > 0 choices have already
been made for positions 0, 1, . . . , v − 1 and one might think only coefficients in
positions v or higher need to be considered. The consideration of already placed
coefficients is necessary to ensure potential variable swaps are properly considered.
As noted earlier, the above describes using TRANSFORM for spectral classification, and that linear and affine classification can be implemented by simply
‘turning off’ certain translations. TRANSFORM cannot be easily adapted for NPN
classification. The reason is that TRANSFORM relies on using type 4 translations
to move spectral coefficients from one order to another. This is applicable to linear,
affine and spectral classification, but type 4 translations are not available in NPN
classification. A key result of using type 4 translations is that for linear, affine
and spectral classification the representative function f R for a class always has a
nonzero first-order coefficient for a variable, unless all coefficients involving that
variable are zero. That is not true for the NPN classification case.
NPN classification requires using type 1 translations (permutations) to move
spectral coefficients within a group. NPN classification thus requires the choice of
appropriate negations and sorting of coefficients within orders. An NPN classification algorithm thus has a structure and approach quite different from TRANSFORM.
9.5 Experimental Results
All experiments were performed on a PC with an Intel i5 2 Core processor running
at 3.2 GHz and 3.0 GB RAM.
Our first experiment was to generate the linear, affine and spectral classes for
n = 1, 2, 3, 4. The execution times and the number of classes (in brackets) are
given in Table 9.3. In each case we found the number of classes given in Table 9.2.
The results for n = 1, 2, 3, 4 were found by applying TRANSFORM to all
Boolean functions of the given number of variables and maintaining a list of
the representative functions found in each case. The classes found are shown in
Tables 9.4, 9.5, and 9.6 except for the linear case for n = 4 which has 92
classes. For each class, we show the representative function f R coded as a decimal
number, the count of the number of functions in the class and the spectrum for
Table 9.3 CPU sec. for class
generation
n Linear classes Affine classes Spectral classes
1 0.003 (4)
0.002 (3)
0.002(1)
2 0.005 (8)
0.003 (5)
0.002(2)
3 0.019 (20)
0.100 (10)
0.006(3)
4 8.298 (92)
9.212 (32)
12.53(8)