9 An Algorithm for Linear, Affine and Spectral Classification of Boolean Functions
203
TRANSFORM implements a recursive search of depth n + 1 that chooses
appropriate translations to assign in order values to S R
0 , S R
1 , S R
2 , . . . , S R
n . Parameter
v identifies which coefficient of S R is under consideration so the initial call to
TRANSFORM should be TRANSFORM(S, n, 0). The operation of TRANSFORM
is as follows:
– Lines 2–5: v = 0 is the top of the search so S R is initialized to S, the spectrum
of interest, and T R , the sequence of translations to map S to S R , is set to empty.
– Lines 6–8: The min and max absolute coefficient values are found by a simple
linear search. All coefficients are considered if v = 0; otherwise, the coefficients
with v or greater in their index are considered.
– Lines 9–18: This is the terminal case for the recursion which is when v > n or
when max = 0. The latter indicates that all coefficients left to be considered
are 0 in which case no translations are available to further modify the spectrum.
Specific steps are as follows:
• 10–12: If S 0 < 0 a type 3 translation is applied to invert the function.
• 13–15: Type 2 translations are applied as needed so that all first-order
coefficients are ≥ 0.
• 16: PRECEDES is called and if S ≺ S R or S = S R and cost (S) < cost (S R ),
S will be copied into S R and T will be copied into T R .
• 17: Return because this is a terminal case in the recursion.
– Lines 19–47: The coefficients are considered in RW order. S 0 is only considered
if v = 0 which is the case for choosing the appropriate value for S R
0 .
• 21: Consider the coefficients where |S α | = max.
• 22–25: Make S 1 a copy of S and if v = 0 (the top of the recursion) set the
sequence of translations T to empty. S 1 is needed so that upon return from a
recursion S is unchanged.
• 26: Save the current length of T . This is necessary to restore the sequence of
translations upon return from a recursion.
• 27–40: If α = 0 translations may be required to move S 1
α to S 1
v .
– 28–32: Set k to be the lowest index in α and then apply type 4 translations
to move S 1
α to S 1
k .
– 33–34: If v = 0, a type 5 translation is applied to move S 1
k to S 1
0 .
– 35–38: Else if k = v, apply a type 1 translation to move S 1
k to S 1
v .
• 41: This is the recursive call to transform S 1 for v + 1, the next level of
recursion.
• 42–44: At the top of the recursion (v = 0) this avoids excessive searching of
a ‘flat’ spectrum (min = max) which is when all coefficients have the same
absolute value.
• 45: Restore the length of T to its value before the last coefficient considered
in preparation for the next S α to be considered.
– Line 48: The recursion options are exhausted so return.
203
TRANSFORM implements a recursive search of depth n + 1 that chooses
appropriate translations to assign in order values to S R
0 , S R
1 , S R
2 , . . . , S R
n . Parameter
v identifies which coefficient of S R is under consideration so the initial call to
TRANSFORM should be TRANSFORM(S, n, 0). The operation of TRANSFORM
is as follows:
– Lines 2–5: v = 0 is the top of the search so S R is initialized to S, the spectrum
of interest, and T R , the sequence of translations to map S to S R , is set to empty.
– Lines 6–8: The min and max absolute coefficient values are found by a simple
linear search. All coefficients are considered if v = 0; otherwise, the coefficients
with v or greater in their index are considered.
– Lines 9–18: This is the terminal case for the recursion which is when v > n or
when max = 0. The latter indicates that all coefficients left to be considered
are 0 in which case no translations are available to further modify the spectrum.
Specific steps are as follows:
• 10–12: If S 0 < 0 a type 3 translation is applied to invert the function.
• 13–15: Type 2 translations are applied as needed so that all first-order
coefficients are ≥ 0.
• 16: PRECEDES is called and if S ≺ S R or S = S R and cost (S) < cost (S R ),
S will be copied into S R and T will be copied into T R .
• 17: Return because this is a terminal case in the recursion.
– Lines 19–47: The coefficients are considered in RW order. S 0 is only considered
if v = 0 which is the case for choosing the appropriate value for S R
0 .
• 21: Consider the coefficients where |S α | = max.
• 22–25: Make S 1 a copy of S and if v = 0 (the top of the recursion) set the
sequence of translations T to empty. S 1 is needed so that upon return from a
recursion S is unchanged.
• 26: Save the current length of T . This is necessary to restore the sequence of
translations upon return from a recursion.
• 27–40: If α = 0 translations may be required to move S 1
α to S 1
v .
– 28–32: Set k to be the lowest index in α and then apply type 4 translations
to move S 1
α to S 1
k .
– 33–34: If v = 0, a type 5 translation is applied to move S 1
k to S 1
0 .
– 35–38: Else if k = v, apply a type 1 translation to move S 1
k to S 1
v .
• 41: This is the recursive call to transform S 1 for v + 1, the next level of
recursion.
• 42–44: At the top of the recursion (v = 0) this avoids excessive searching of
a ‘flat’ spectrum (min = max) which is when all coefficients have the same
absolute value.
• 45: Restore the length of T to its value before the last coefficient considered
in preparation for the next S α to be considered.
– Line 48: The recursion options are exhausted so return.