Chapter 10
New Results on Reversible Boolean
Functions Having Component Functions
with Specified Properties
Paweł Kerntopf, Krzysztof Podlaski, Claudio Moraga, and Radomir Stankovi´ c
10.1 Introduction
Recent advances in nanotechnology, low-power design, and quantum computing
have renewed interest in reversible logic synthesis since they allow reducing
the power dissipation in related circuits and the potential speed-up in quantum
computations. More details can be found in [1, 2] and the references therein.
A reversible function is defined as a bijective mapping f : A n → A n , where A is
any finite set of elements which can be conveniently identified with non-negative
integers {0, 1, . . . , p−1}. In particular, for p = 2 and p = 3, we speak about binary
or Boolean and ternary reversible functions, respectively. Therefore, an n-variable
reversible function is actually a permutation on A n , and can be viewed as a vector of
n functions called the component functions (CFs), i.e., F = (f 1 , f 2 ,..., f n ). In [3], the
term components is applied in the similar meaning, meanwhile in the literature on
cryptography the term coordinate functions is used, see, e.g., [4, 5]. However, in [5]
the term component function means a linear combination of coordinate functions.
P. Kerntopf ()
Institute of Computer Science, Warsaw University of Technology, Warsaw, Poland
e-mail: pawel.kerntopf@gazeta.pl
K. Podlaski
Faculty of Physics and Applied Informatics, University of Łód´ z, Łód´ z, Poland
e-mail: podlaski@uni.lodz.pl
C. Moraga
Faculty of Computer Science, Technical University of Dortmund, Dortmund, Germany
e-mail: claudio.moraga@tu-dortmund.de
R. Stankovi´ c
Department of Computer Science, Faculty of Electronic Engineering, University of Niš, Niš,
Serbia
© Springer Nature Switzerland AG 2020
R. Drechsler, M. Soeken (eds.), Advanced Boolean Techniques,
https://doi.org/10.1007/978-3-030-20323-8_10
217
New Results on Reversible Boolean
Functions Having Component Functions
with Specified Properties
Paweł Kerntopf, Krzysztof Podlaski, Claudio Moraga, and Radomir Stankovi´ c
10.1 Introduction
Recent advances in nanotechnology, low-power design, and quantum computing
have renewed interest in reversible logic synthesis since they allow reducing
the power dissipation in related circuits and the potential speed-up in quantum
computations. More details can be found in [1, 2] and the references therein.
A reversible function is defined as a bijective mapping f : A n → A n , where A is
any finite set of elements which can be conveniently identified with non-negative
integers {0, 1, . . . , p−1}. In particular, for p = 2 and p = 3, we speak about binary
or Boolean and ternary reversible functions, respectively. Therefore, an n-variable
reversible function is actually a permutation on A n , and can be viewed as a vector of
n functions called the component functions (CFs), i.e., F = (f 1 , f 2 ,..., f n ). In [3], the
term components is applied in the similar meaning, meanwhile in the literature on
cryptography the term coordinate functions is used, see, e.g., [4, 5]. However, in [5]
the term component function means a linear combination of coordinate functions.
P. Kerntopf ()
Institute of Computer Science, Warsaw University of Technology, Warsaw, Poland
e-mail: pawel.kerntopf@gazeta.pl
K. Podlaski
Faculty of Physics and Applied Informatics, University of Łód´ z, Łód´ z, Poland
e-mail: podlaski@uni.lodz.pl
C. Moraga
Faculty of Computer Science, Technical University of Dortmund, Dortmund, Germany
e-mail: claudio.moraga@tu-dortmund.de
R. Stankovi´ c
Department of Computer Science, Faculty of Electronic Engineering, University of Niš, Niš,
Serbia
© Springer Nature Switzerland AG 2020
R. Drechsler, M. Soeken (eds.), Advanced Boolean Techniques,
https://doi.org/10.1007/978-3-030-20323-8_10
217