9 An Algorithm for Linear, Affine and Spectral Classification of Boolean Functions
201
9.4 Transformation Algorithm
Procedure TRANSFORM maps a function f , with RW spectrum S, to the representative function f R , with spectrum S R , for the equivalence class that contains f . In
doing so it finds a low cost sequence of translations but does not necessarily find
the minimal cost sequence as the algorithm does not search all possible translation
sequences. The parameters to the procedure are the spectrum S, the number of
function variables n and a third parameter v explained below.
When the procedure completes the result is the spectrum S R and the sequence of
translations is in T R . T is used to record a sequence of translations as it is built. S R ,
T R and T are for simplicity and implementation efficiency global to the procedures.
TRANSFORM uses a secondary procedure called PRECEDES. It accepts a
spectrum, parameter S, and compares it to the spectrum S R which as noted above
is a global. S R is replaced by S and the sequence of translations T replaces T R if
S ≺ S R , see Definition 9.4. If S and S R are the same, PRECEDES T R by T if the
latter has lower cost.
TRANSFORM also employs five procedures trans1 . . . trans5 associated with
the five spectral translations described above. Each applies a translation to the
parameter spectrum S. The translation is also appended to end of the global T .
Note that it is important that T is maintained in the order the translations are to be
applied.
Note that TRANSFORM as described here employs all five spectral translations.
It thus implements spectral classification, see Table 9.1. For linear or affine
classification, TRANSFORM has to be modified to only generate type 1 and 4
translations (linear) or type 1, 2 and 4 translations (affine). This can be implemented
by adding appropriate conditional compilation or, more simply, by adding execution
time switches to disable the unwanted translations.
1: procedure TRANSFORM(S, n, v)
2:
if v = 0 then
3:
S R ← S
4:
T R ← φ
5:
end if
6:
find the min and max absolute coefficient values
7:
consider all coefficients if v = 0
8:
otherwise consider all S α with a p ∈ α, p ≥ v
9:
if v > n or max = 0 then
10:
if S 0 < 0 then
11:
trans3(S, n)
12:
end if
13:
for every first order coefficient S i < 0 do
14:
trans2(S, n, i)
15:
end for
16:
precedes(S, n)
17:
return
201
9.4 Transformation Algorithm
Procedure TRANSFORM maps a function f , with RW spectrum S, to the representative function f R , with spectrum S R , for the equivalence class that contains f . In
doing so it finds a low cost sequence of translations but does not necessarily find
the minimal cost sequence as the algorithm does not search all possible translation
sequences. The parameters to the procedure are the spectrum S, the number of
function variables n and a third parameter v explained below.
When the procedure completes the result is the spectrum S R and the sequence of
translations is in T R . T is used to record a sequence of translations as it is built. S R ,
T R and T are for simplicity and implementation efficiency global to the procedures.
TRANSFORM uses a secondary procedure called PRECEDES. It accepts a
spectrum, parameter S, and compares it to the spectrum S R which as noted above
is a global. S R is replaced by S and the sequence of translations T replaces T R if
S ≺ S R , see Definition 9.4. If S and S R are the same, PRECEDES T R by T if the
latter has lower cost.
TRANSFORM also employs five procedures trans1 . . . trans5 associated with
the five spectral translations described above. Each applies a translation to the
parameter spectrum S. The translation is also appended to end of the global T .
Note that it is important that T is maintained in the order the translations are to be
applied.
Note that TRANSFORM as described here employs all five spectral translations.
It thus implements spectral classification, see Table 9.1. For linear or affine
classification, TRANSFORM has to be modified to only generate type 1 and 4
translations (linear) or type 1, 2 and 4 translations (affine). This can be implemented
by adding appropriate conditional compilation or, more simply, by adding execution
time switches to disable the unwanted translations.
1: procedure TRANSFORM(S, n, v)
2:
if v = 0 then
3:
S R ← S
4:
T R ← φ
5:
end if
6:
find the min and max absolute coefficient values
7:
consider all coefficients if v = 0
8:
otherwise consider all S α with a p ∈ α, p ≥ v
9:
if v > n or max = 0 then
10:
if S 0 < 0 then
11:
trans3(S, n)
12:
end if
13:
for every first order coefficient S i < 0 do
14:
trans2(S, n, i)
15:
end for
16:
precedes(S, n)
17:
return