222
P. Kerntopf et al.
of work has been done in classification of reversible functions. In [16, 17] it is
presented an approach to enumerate equivalence classes of reversible functions
with the equivalence classes defined as follows. Denote by G and H the groups
of permutations acting on the inputs and outputs of Boolean reversible functions,
respectively. Two functions f 1 (x) and f 2 (x) are equivalent if for each n-tuple x,
there is a g G and an h H such that f 1 (x) = h( f 2 (g(x))). It is provided a list
of all NPNP-equivalence classes of 3-variable reversible functions as well as a
classification based on properties of the inverses of the representative functions for
the equivalence classes considered. The lists consist of triples of balanced Boolean
functions specified by ESOPs.
A technical report from 1962 by Lorens [16] and an article by the same author
[17] can be viewed as a starting point of subsequent work on enumeration of equivalence classes of reversible functions by several authors [18–23]. With exception of
[22], these publications consider classification of binary reversible functions. These
publications were discussed mainly by researchers in combinatorial mathematics
and cryptography but hardly used and correspondingly rarely if at all referred within
the reversible functions community, the main reason probably being that the term
invertible instead of reversible functions has been used. A classification scheme for
reversible functions was the subject of a profound study in [24], however, without a
concrete solution proposed.
Recently, certain aspects of the classification problem have been addressed. In
[25], the list of all NPNP-equivalence classes for three variable reversible functions
from [17] is presented in the context of a study of complexity of reversible circuits
with the representative functions for equivalence classes given in the form of
permutations. The minimal number of nonlinear gates needed in the implementation
of reversible functions is used as a classification criterion in [26]. The structure
of closed classes of reversible functions is described in [27]. Enumeration of
equivalence classes under the action of permutation of the inputs and outputs on
the domain and the range is presented in [28].
In [6] we showed that the lists published in [17] included (probably typographic)
errors and we corrected them. We also solved in [6, 7] several problems of the
existence of binary reversible functions with all component functions having the
same known property (e.g., symmetry, affinity, linearity, nonlinearity, self-duality,
self-complementarity, monotonicity, and unateness). Solutions of such problems for
ternary reversible functions are presented by us in [8]. In [9] we presented results
on the existence of ternary/multiple-valued reversible functions with all component
functions belonging to different P-equivalence classes. In this paper two problems
are considered whose solutions have not been published earlier: showing that there
exist (1) a reversible Boolean function with all component functions having a linear
variable, (2) a reversible Boolean function with all component functions belonging
to different P-equivalence classes. We also show how we discovered solutions of
these problems by extrapolating some properties of previously found reversible
functions of 3- and 4-variables (see [6]).
P. Kerntopf et al.
of work has been done in classification of reversible functions. In [16, 17] it is
presented an approach to enumerate equivalence classes of reversible functions
with the equivalence classes defined as follows. Denote by G and H the groups
of permutations acting on the inputs and outputs of Boolean reversible functions,
respectively. Two functions f 1 (x) and f 2 (x) are equivalent if for each n-tuple x,
there is a g G and an h H such that f 1 (x) = h( f 2 (g(x))). It is provided a list
of all NPNP-equivalence classes of 3-variable reversible functions as well as a
classification based on properties of the inverses of the representative functions for
the equivalence classes considered. The lists consist of triples of balanced Boolean
functions specified by ESOPs.
A technical report from 1962 by Lorens [16] and an article by the same author
[17] can be viewed as a starting point of subsequent work on enumeration of equivalence classes of reversible functions by several authors [18–23]. With exception of
[22], these publications consider classification of binary reversible functions. These
publications were discussed mainly by researchers in combinatorial mathematics
and cryptography but hardly used and correspondingly rarely if at all referred within
the reversible functions community, the main reason probably being that the term
invertible instead of reversible functions has been used. A classification scheme for
reversible functions was the subject of a profound study in [24], however, without a
concrete solution proposed.
Recently, certain aspects of the classification problem have been addressed. In
[25], the list of all NPNP-equivalence classes for three variable reversible functions
from [17] is presented in the context of a study of complexity of reversible circuits
with the representative functions for equivalence classes given in the form of
permutations. The minimal number of nonlinear gates needed in the implementation
of reversible functions is used as a classification criterion in [26]. The structure
of closed classes of reversible functions is described in [27]. Enumeration of
equivalence classes under the action of permutation of the inputs and outputs on
the domain and the range is presented in [28].
In [6] we showed that the lists published in [17] included (probably typographic)
errors and we corrected them. We also solved in [6, 7] several problems of the
existence of binary reversible functions with all component functions having the
same known property (e.g., symmetry, affinity, linearity, nonlinearity, self-duality,
self-complementarity, monotonicity, and unateness). Solutions of such problems for
ternary reversible functions are presented by us in [8]. In [9] we presented results
on the existence of ternary/multiple-valued reversible functions with all component
functions belonging to different P-equivalence classes. In this paper two problems
are considered whose solutions have not been published earlier: showing that there
exist (1) a reversible Boolean function with all component functions having a linear
variable, (2) a reversible Boolean function with all component functions belonging
to different P-equivalence classes. We also show how we discovered solutions of
these problems by extrapolating some properties of previously found reversible
functions of 3- and 4-variables (see [6]).