9 An Algorithm for Linear, Affine and Spectral Classification of Boolean Functions
199
Translation 2 Negation of the input variables x i . This negates the 2 n−1 spectral
coefficients with i in their subscripts.
Translation 3 Negation of the function. This negates all the spectral coefficients.
Translation 4 Replacement of input variable x i by x i ⊕ x j . This interchanges the
2 n−2 pairs of spectral coefficients given by
s iα ↔ s ij α
for all α ⊆ {1, 2, .., i − 1, i + 1, . . . , j − 1, j + 1, . . . , n}.
Translation 5 Replacement of the function f by f ⊕x i . This interchanges the 2 n−1
pairs of spectral coefficients given by
s iα ↔ s α
for all α ⊆ {1, 2, .., i − 1, i + 1, . . . , n}.
It is important to note that Translation 1 reorders certain coefficients within the
same orders, Translations 4 and 5 reorder certain coefficients between adjacent
orders and Translations 2 and 3 change the signs of certain coefficients leaving them
in the same positions in the spectrum.
Application of these translations leads to the following key concept:
Definition 9.6 Two Boolean functions f (x 1 , x 2 , . . . , x n ) and g(x 1 , x 2 , . . . , x n ) are
equivalent with respect to a particular subset of the 5 spectral translations if f can
be transformed into g by the application of some sequence of those translations.
Note that the translations are all self-inverse, so the reverse sequence of translations
will transform g to f . Also as shown in the definitions of the translations they can
be directly carried out in the spectral domain, i.e. it is straightforward to transform
between the spectra of f and g.
9.3 Classification of Boolean Functions
NPN classification [5], which uses negation of variables, permutation of variable
and negation of the function, is well known and well studied [17]. We make use
of NPN classes for the case n = 5. We consider the linear, affine and spectral
classification schemes in detail. As shown in Table 9.1, each classification scheme
involves the application of particular translations. The algorithm presented below
does not apply for the NPN case for reasons explained after the algorithm is
presented. The sizes of the various equivalence classes up to n = 6 are given in
Table 9.2.
199
Translation 2 Negation of the input variables x i . This negates the 2 n−1 spectral
coefficients with i in their subscripts.
Translation 3 Negation of the function. This negates all the spectral coefficients.
Translation 4 Replacement of input variable x i by x i ⊕ x j . This interchanges the
2 n−2 pairs of spectral coefficients given by
s iα ↔ s ij α
for all α ⊆ {1, 2, .., i − 1, i + 1, . . . , j − 1, j + 1, . . . , n}.
Translation 5 Replacement of the function f by f ⊕x i . This interchanges the 2 n−1
pairs of spectral coefficients given by
s iα ↔ s α
for all α ⊆ {1, 2, .., i − 1, i + 1, . . . , n}.
It is important to note that Translation 1 reorders certain coefficients within the
same orders, Translations 4 and 5 reorder certain coefficients between adjacent
orders and Translations 2 and 3 change the signs of certain coefficients leaving them
in the same positions in the spectrum.
Application of these translations leads to the following key concept:
Definition 9.6 Two Boolean functions f (x 1 , x 2 , . . . , x n ) and g(x 1 , x 2 , . . . , x n ) are
equivalent with respect to a particular subset of the 5 spectral translations if f can
be transformed into g by the application of some sequence of those translations.
Note that the translations are all self-inverse, so the reverse sequence of translations
will transform g to f . Also as shown in the definitions of the translations they can
be directly carried out in the spectral domain, i.e. it is straightforward to transform
between the spectra of f and g.
9.3 Classification of Boolean Functions
NPN classification [5], which uses negation of variables, permutation of variable
and negation of the function, is well known and well studied [17]. We make use
of NPN classes for the case n = 5. We consider the linear, affine and spectral
classification schemes in detail. As shown in Table 9.1, each classification scheme
involves the application of particular translations. The algorithm presented below
does not apply for the NPN case for reasons explained after the algorithm is
presented. The sizes of the various equivalence classes up to n = 6 are given in
Table 9.2.