218
P. Kerntopf et al.
Correspondingly, a reversible circuit is a circuit that realizes a reversible function,
i.e., performs a bijective mapping of n input signals onto n output signals in a manner
specified by the function to be realized.
Recently in [6, 7], we discussed the question if it is possible to extend a Boolean
function f : {0, 1} n → {0, 1} into a reversible function F: {0, 1} n → {0, 1} n ,
under the condition that all its component functions have a homogeneous property.
The term homogeneous property means that all component functions express the
same particular property Boolean functions might have, e.g., all the component
functions belong to the same equivalence class in a particular classification of
Boolean functions. The motivation was that if such an embedding of a Boolean
function into a reversible function is possible, then new classes of reversible
functions can be defined. In [8, 9] the same question is explored for ternary functions
F: {0, 1, 2} n → {0, 1, 2} n . Notice that there are significant differences in the theory
of binary and ternary reversible functions, especially in the case of linear component
functions.
As homogeneous properties we have chosen typical ones considered in classical logic synthesis: symmetry, affinity, linearity, nonlinearity, self-duality, selfcomplementarity, monotonicity, and unateness (see, e.g., [10]). In our previous
papers [6–9] the exemplary functions used in proofs of the results were obtained
by a constructive manner. Here we present new results on properties of component
functions of Boolean reversible functions obtained by the extrapolation approach.
The presentation is organized as follows. For the sake of completeness, necessary
definitions and basic results from the theory of standard Boolean as well as
reversible Boolean functions are provided in Sect. 10.2. In Sect. 10.3, a brief
overview of related and background work is presented. Section 10.4 demonstrates
our approach to extrapolating desired properties of reversible functions. Sections
10.5 and 10.6 describe the main results of our research on the existence of Boolean
reversible functions with all component functions having at least one linear variable
or belonging to different equivalence classes. The presented research is summarized
in Sect. 10.7.
10.2 Preliminaries
In this section the basic definitions and known results are provided for the
convenience of the reader. Let us first briefly survey fundamental notions related
to standard Boolean functions and reversible Boolean functions. Any Boolean
function f : {0, 1} n → {0, 1} can be described using an EXOR-sum of products
(ESOP) expression. In ESOPs each variable may appear in both uncomplemented
and complemented forms. The positive polarity Reed–Muller (PPRM) expression is
an ESOP expression which uses only uncomplemented variables. It is a canonical
expression and for small functions can be easily generated from a truth table or
another representation of the Boolean function.
P. Kerntopf et al.
Correspondingly, a reversible circuit is a circuit that realizes a reversible function,
i.e., performs a bijective mapping of n input signals onto n output signals in a manner
specified by the function to be realized.
Recently in [6, 7], we discussed the question if it is possible to extend a Boolean
function f : {0, 1} n → {0, 1} into a reversible function F: {0, 1} n → {0, 1} n ,
under the condition that all its component functions have a homogeneous property.
The term homogeneous property means that all component functions express the
same particular property Boolean functions might have, e.g., all the component
functions belong to the same equivalence class in a particular classification of
Boolean functions. The motivation was that if such an embedding of a Boolean
function into a reversible function is possible, then new classes of reversible
functions can be defined. In [8, 9] the same question is explored for ternary functions
F: {0, 1, 2} n → {0, 1, 2} n . Notice that there are significant differences in the theory
of binary and ternary reversible functions, especially in the case of linear component
functions.
As homogeneous properties we have chosen typical ones considered in classical logic synthesis: symmetry, affinity, linearity, nonlinearity, self-duality, selfcomplementarity, monotonicity, and unateness (see, e.g., [10]). In our previous
papers [6–9] the exemplary functions used in proofs of the results were obtained
by a constructive manner. Here we present new results on properties of component
functions of Boolean reversible functions obtained by the extrapolation approach.
The presentation is organized as follows. For the sake of completeness, necessary
definitions and basic results from the theory of standard Boolean as well as
reversible Boolean functions are provided in Sect. 10.2. In Sect. 10.3, a brief
overview of related and background work is presented. Section 10.4 demonstrates
our approach to extrapolating desired properties of reversible functions. Sections
10.5 and 10.6 describe the main results of our research on the existence of Boolean
reversible functions with all component functions having at least one linear variable
or belonging to different equivalence classes. The presented research is summarized
in Sect. 10.7.
10.2 Preliminaries
In this section the basic definitions and known results are provided for the
convenience of the reader. Let us first briefly survey fundamental notions related
to standard Boolean functions and reversible Boolean functions. Any Boolean
function f : {0, 1} n → {0, 1} can be described using an EXOR-sum of products
(ESOP) expression. In ESOPs each variable may appear in both uncomplemented
and complemented forms. The positive polarity Reed–Muller (PPRM) expression is
an ESOP expression which uses only uncomplemented variables. It is a canonical
expression and for small functions can be easily generated from a truth table or
another representation of the Boolean function.