198
D. M. Miller and M. Soeken
The coefficients in (9.5) are in Hadamard order. In this work we use what is
commonly called Rademacher-Walsh order [7] which groups the coefficients by the
number of variables in the XOR function. For n = 3, this order is
S =
s 0 |s 1 s 2 s 3 |s 12 s 13 s 23 |s 123
t
(9.6)
As can be seen, the coefficients are ordered with the 0-order coefficient first,
followed by the first-order, second-order, third-order coefficients and so on. We shall
refer to this as RW order for brevity. In general RW order is as follows:
S = [s 0 |s 1 s 2 s 3 . . . s n |s 12 s 13 s 23 s 14 s 24 s 34 . . . s (n−1)n |
s 123 s 124 s 134 s 234 . . . s (n−2)(n−1)n | . . . |s 12...n ]
t
(9.7)
The following definitions introduce key concepts for our approach to function
classification.
Definition 9.4 Given two Boolean functions f (x 1 , x 2 , . . . , x n ) and g(x 1 , x 2 , . . . ,
x n ) with spectra S f and S g , respectively, we say f precedes g, denoted f ≺ g if for
the first coefficient position (in RW order) for which the coefficients from S f and S g
differ, the coefficient from S f has larger magnitude, or if the two coefficients have
the same magnitude, the coefficient from S f is positive. Note that for convenience
we will also write S f ≺ S g .
Definition 9.5 Clearly, a function equivalence class must contain a function f R that
precedes every other function in the class. We term f R the representative function
for the class.
9.2.2 Spectral Translations
Five spectral translations [3, 7, 8] will be used for the linear, affine or spectral
classification of Boolean functions. Given a Boolean function f (x 1 , x 2 , . . . , x n )
with spectrum S, the translations are defined as follows:
Translation 1 Interchange of the input variables x i and x j . This interchanges the
2 n−2 pairs of spectral coefficients given by
s iα ↔ s jα
for all α ⊆ {1, 2, .., i − 1, i + 1, . . . , j − 1, j + 1, . . . , n}.
D. M. Miller and M. Soeken
The coefficients in (9.5) are in Hadamard order. In this work we use what is
commonly called Rademacher-Walsh order [7] which groups the coefficients by the
number of variables in the XOR function. For n = 3, this order is
S =
s 0 |s 1 s 2 s 3 |s 12 s 13 s 23 |s 123
t
(9.6)
As can be seen, the coefficients are ordered with the 0-order coefficient first,
followed by the first-order, second-order, third-order coefficients and so on. We shall
refer to this as RW order for brevity. In general RW order is as follows:
S = [s 0 |s 1 s 2 s 3 . . . s n |s 12 s 13 s 23 s 14 s 24 s 34 . . . s (n−1)n |
s 123 s 124 s 134 s 234 . . . s (n−2)(n−1)n | . . . |s 12...n ]
t
(9.7)
The following definitions introduce key concepts for our approach to function
classification.
Definition 9.4 Given two Boolean functions f (x 1 , x 2 , . . . , x n ) and g(x 1 , x 2 , . . . ,
x n ) with spectra S f and S g , respectively, we say f precedes g, denoted f ≺ g if for
the first coefficient position (in RW order) for which the coefficients from S f and S g
differ, the coefficient from S f has larger magnitude, or if the two coefficients have
the same magnitude, the coefficient from S f is positive. Note that for convenience
we will also write S f ≺ S g .
Definition 9.5 Clearly, a function equivalence class must contain a function f R that
precedes every other function in the class. We term f R the representative function
for the class.
9.2.2 Spectral Translations
Five spectral translations [3, 7, 8] will be used for the linear, affine or spectral
classification of Boolean functions. Given a Boolean function f (x 1 , x 2 , . . . , x n )
with spectrum S, the translations are defined as follows:
Translation 1 Interchange of the input variables x i and x j . This interchanges the
2 n−2 pairs of spectral coefficients given by
s iα ↔ s jα
for all α ⊆ {1, 2, .., i − 1, i + 1, . . . , j − 1, j + 1, . . . , n}.