Chapter 9
An Algorithm for Linear, Affine
and Spectral Classification of Boolean
Functions
D. Michael Miller and Mathias Soeken
9.1 Introduction
The classification of Boolean functions has been a topic of interest for some
time. Two Boolean functions are equivalent with respect to a particular class of
translations if there is a sequence of translations that maps one function to the other.
Function equivalence partitions the Boolean functions for a particular number of
variables into equivalence classes. Such classes are of interest since, for example,
if one has an inexpensive implementation for one function f in the class, knowing
that and a sequence of translations to map g to f provides a potentially efficient
implementation for g. Finding the least costly translation sequence affects the
overall cost.
NPN equivalence which allows for negation of inputs, permutation of inputs and
negation of the function was considered in 1963 by Harrison [5]. NPN equivalence
has been applied in technology mapping [19] and a variety of other applications in
logic design.
A Boolean function can be transformed to the Rademacher-Walsh spectral
domain [7–9, 14, 19, 20]. Unlike the functional domain where the individual 2 n
function values provide local information, each of the 2 n integer-valued spectral
coefficients provide global information about the function. Two XOR-based spectral
translations added to the NPN operations allow for the spectral classification of
Boolean functions where the number of equivalence classes is far smaller than for
NPN equivalence [3, 7–9]. In addition, by restricting the translations used, Boolean
functions can be partitioned into linear or affine equivalence classes [6, 15].
D. M. Miller
Department of Computer Science, University of Victoria, Victoria, BC, Canada
M. Soeken ()
Integrated Systems Laboratory, EPFL, Lausanne, Switzerland
e-mail: mathias.soeken@epfl.ch
© Springer Nature Switzerland AG 2020
R. Drechsler, M. Soeken (eds.), Advanced Boolean Techniques,
https://doi.org/10.1007/978-3-030-20323-8_9
195
An Algorithm for Linear, Affine
and Spectral Classification of Boolean
Functions
D. Michael Miller and Mathias Soeken
9.1 Introduction
The classification of Boolean functions has been a topic of interest for some
time. Two Boolean functions are equivalent with respect to a particular class of
translations if there is a sequence of translations that maps one function to the other.
Function equivalence partitions the Boolean functions for a particular number of
variables into equivalence classes. Such classes are of interest since, for example,
if one has an inexpensive implementation for one function f in the class, knowing
that and a sequence of translations to map g to f provides a potentially efficient
implementation for g. Finding the least costly translation sequence affects the
overall cost.
NPN equivalence which allows for negation of inputs, permutation of inputs and
negation of the function was considered in 1963 by Harrison [5]. NPN equivalence
has been applied in technology mapping [19] and a variety of other applications in
logic design.
A Boolean function can be transformed to the Rademacher-Walsh spectral
domain [7–9, 14, 19, 20]. Unlike the functional domain where the individual 2 n
function values provide local information, each of the 2 n integer-valued spectral
coefficients provide global information about the function. Two XOR-based spectral
translations added to the NPN operations allow for the spectral classification of
Boolean functions where the number of equivalence classes is far smaller than for
NPN equivalence [3, 7–9]. In addition, by restricting the translations used, Boolean
functions can be partitioned into linear or affine equivalence classes [6, 15].
D. M. Miller
Department of Computer Science, University of Victoria, Victoria, BC, Canada
M. Soeken ()
Integrated Systems Laboratory, EPFL, Lausanne, Switzerland
e-mail: mathias.soeken@epfl.ch
© Springer Nature Switzerland AG 2020
R. Drechsler, M. Soeken (eds.), Advanced Boolean Techniques,
https://doi.org/10.1007/978-3-030-20323-8_9
195