210
D. M. Miller and M. Soeken
Table 9.8 Average
translations per function
n
1
2
3
4
5
Linear
0
0.875 2.609 6.006 12.693
Affine
0.250 1.187 2.969 6.382 13.657
Spectral 1
1.5
3.504 6.765 13.908
Table 9.9 CPU sec. for class generation
Linear
Affine
Spectral
n
Runtime
Classes
Runtime
Classes
Runtime
Classes
1
0.00007
4
0.00005
3
0.00004
1
2
0.00013
8
0.00010
5
0.00006
2
3
0.00115
20
0.00108
10
0.00063
3
4
0.13561
92
0.21747
32
0.10147
8
5
126.44800
2744
254.95300
382
122.68800
48
As noted above, the TRANSFORM procedure attempts to find a low cost
translation sequence. Table 9.8 reports the average number of translations per
function for linear, affine and spectral classification for each n.
9.6 An Alternate Approach to Class Generation
The approach above is limited by the rate at which the number of Boolean functions
grows with n. Even for n = 5 we had to use NPN class representatives rather than
all functions. In this section, we outline an alternate approach which is much more
efficient. That raises the possibility of applying it for n > 5. Its limitation is that,
because it does not examine all functions or all NPN classes, this approach does not
yield information on the size of a class.
Rather than checking all function or NPN classes, the alternate approach uses
a search procedure based on Algorithm 4.2.1 from J. E. Fuller’s PhD thesis [4]
to generate all linear, affine or spectral class representatives for Boolean functions
with n variables. Note that the presentation in [4] considered only what we have
here termed the spectral case which in her work Fuller refers to as the affine case.
The search procedure employs the concept of the 1-neighbourhood of a Boolean
function [4].
Definition 9.7 A function g is in the 1-neighbourhood of function f , if g differs
from f for precisely one input assignment.
The search begins with a stack containing the single class representative constant0 function. A recursive search is employed and whenever a neighbourhood function
is not equivalent to any of the representatives found so far, it is added to the
stack. The procedure terminates when no more new representatives are found in the
neighbourhoods of the representatives on the stack. The advantage of the approach
is that not all Boolean functions need to be explored.
D. M. Miller and M. Soeken
Table 9.8 Average
translations per function
n
1
2
3
4
5
Linear
0
0.875 2.609 6.006 12.693
Affine
0.250 1.187 2.969 6.382 13.657
Spectral 1
1.5
3.504 6.765 13.908
Table 9.9 CPU sec. for class generation
Linear
Affine
Spectral
n
Runtime
Classes
Runtime
Classes
Runtime
Classes
1
0.00007
4
0.00005
3
0.00004
1
2
0.00013
8
0.00010
5
0.00006
2
3
0.00115
20
0.00108
10
0.00063
3
4
0.13561
92
0.21747
32
0.10147
8
5
126.44800
2744
254.95300
382
122.68800
48
As noted above, the TRANSFORM procedure attempts to find a low cost
translation sequence. Table 9.8 reports the average number of translations per
function for linear, affine and spectral classification for each n.
9.6 An Alternate Approach to Class Generation
The approach above is limited by the rate at which the number of Boolean functions
grows with n. Even for n = 5 we had to use NPN class representatives rather than
all functions. In this section, we outline an alternate approach which is much more
efficient. That raises the possibility of applying it for n > 5. Its limitation is that,
because it does not examine all functions or all NPN classes, this approach does not
yield information on the size of a class.
Rather than checking all function or NPN classes, the alternate approach uses
a search procedure based on Algorithm 4.2.1 from J. E. Fuller’s PhD thesis [4]
to generate all linear, affine or spectral class representatives for Boolean functions
with n variables. Note that the presentation in [4] considered only what we have
here termed the spectral case which in her work Fuller refers to as the affine case.
The search procedure employs the concept of the 1-neighbourhood of a Boolean
function [4].
Definition 9.7 A function g is in the 1-neighbourhood of function f , if g differs
from f for precisely one input assignment.
The search begins with a stack containing the single class representative constant0 function. A recursive search is employed and whenever a neighbourhood function
is not equivalent to any of the representatives found so far, it is added to the
stack. The procedure terminates when no more new representatives are found in the
neighbourhoods of the representatives on the stack. The advantage of the approach
is that not all Boolean functions need to be explored.