New Results on Reversible Boolean Functions Having Component Functions with Specified Properties

Abstract

In the traditional logic synthesis different classifications of non-reversible Boolean functions have found many applications. Recently, some attempts to deal with classifications of reversible functions have been published. In this paper, solutions of two problems which have not been addressed yet are presented. The solutions were found by extrapolation of cycle structures for 3-and 4-variable reversible functions obtained in the course of enumerative computations.

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ⁿ → Aⁿ, 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ⁿ, and can be viewed as a vector of n functions called the component functions (CFs), i.e., F = (f₁, f₂,..., 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.

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}ⁿ → {0, 1} into a reversible function F: {0, 1}ⁿ → {0, 1}ⁿ, 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}ⁿ → {0, 1, 2}ⁿ. 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, self-complementarity, monotonicity, and unateness (see, e.g., [10]). In our previous papers [6,7,8,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}ⁿ → {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.

Definition 10.1

A Boolean function f: {0, 1}ⁿ → {0, 1} is called balanced if it takes value 1 the same number of times as value 0.

In the case of Boolean functions, depending on the operations allowed in a particular classification, the P-equivalent, NP-equivalent, and NPN-equivalent functions are distinguished. In some applications, equivalence classes defined with respect to a restricted set of operations are of a particular interest, as for example, in [11, 12]. In the present paper, we are particularly interested in P-equivalent functions when studying properties of component functions.

Definition 10.2

Two Boolean functions are

• 1. P-equivalent if they can be converted to each other by the permutation of variables,

• 2. NP-equivalent if they can be converted to each other by the negation and/or permutation of variables,

• 3. NPN-equivalent if they can be converted to each other by negation of variables, permutation of variables, and negation of the function.

Definition 10.3

A Boolean function f is self-complementary (SC) if f and f’ are NP-equivalent, where f’ denotes negation of f.

Definition 10.4

A Boolean function f is self-dual (SD) if

$$ f\ \left({x}_1,{x}_2,\dots, {x}_n\right)={f}^{'}\left({x_1}^{'},{x_2}^{'},\dots, {x_n}^{'}\right). $$

Definition 10.5

A Boolean function f is linear with respect to a variable x_i if the function f can be expressed in the form f = x_i ⊕ g, where g is a function independent of x_i (then the variable x_i is called linear in f). A function f is called linear (L) if all its variables are linear in f. Otherwise it is called nonlinear. A function has property LV if it contains at least one linear variable.

Example 10.1

f₁(x, y, z) = x ⊕ y ⊕ yz is linear with respect to x as then g = y ⊕ yz is independent of x, but f₁ is not linear with respect to y as then g = x ⊕ yz is dependent of y. Similarly, f₂(x, y) = x ⊕ y ⊕ xy is linear with respect to neither x nor y.

The following results are well known:

Lemma 10.1

• 1. All self-complementary functions are balanced,

• 2. All self-dual functions are self-complementary,

• 3. All functions having property LV are self-complementary,

• 4. If a Boolean function f is linear with respect to a variable x _i, then

$$ f\ \left({x}_i=1\right)={f}^{'}\left({x}_i=0\right). $$

Definition 10.6

A mapping F: {0, 1}ⁿ → {0, 1}ⁿ is called an n^∗ n reversible function if it is bijective. It will also be considered as a vector of standard Boolean functions that we will called component functions f_i: {0, 1}ⁿ → {0, 1}, 1 ≤ i ≤ n. They are defined at every x ϵ {0, 1}ⁿ by F(x) = (f₁(x), …, f_n(x)).

Since F is bijective hence component functions f_i: {0, 1}ⁿ → {0, 1}, 1 ≤ i ≤ n, are balanced Boolean functions.

By an analogy with the definition of NPN-equivalence classes for standard Boolean functions, the following definition of equivalence classes for Boolean reversible functions can be given.

Definition 10.7

Two reversible Boolean functions are NPNP-equivalent if they can be transformed to each other by the following operations (including the combinations that do not use all of these operations):

• 1. Negation of variables,

• 2. Permutation of variables,

• 3. Negation of component functions, and

• 4. Permutation of component functions.

Example 10.2

The component functions of a reversible Boolean function F = ( f₁, f₂, f₃) are as follows:

$$ {f}_1\left(x,y,z\right)=x\oplus yz\vspace*{-12pt} $$

$$ {f}_2\left(x,y,z\right)=x\oplus y\oplus xz\vspace*{-12pt} $$

$$ {f}_3\left(x,y,z\right)=x\oplus y\oplus z\oplus xy $$

After negating variables x in F we obtain the reversible function G = (g₁, g₂, g₃):

$$ {g}_1\left(x,y,z\right)={f}_1\left({x}^{'},{y},z\right)=\left(1\oplus x\right)\oplus yz=1\oplus x\oplus yz\vspace*{-12pt} $$

$$ {g}_2\left(x,y,z\right)={f}_2\left({x}^{'},{y},z\right)=\left(1\oplus x\right)\oplus y\oplus \left(1\oplus x\right)z=1\oplus x\oplus y\oplus z\oplus xz\vspace*{-12pt} $$

$$ \begin {array} {cccc} {{g}_3\left(x,y,z\right) ={f}_3\left({x}^{'},{y},z\right)=\left(1\oplus x\right)\oplus y\oplus z\oplus \left(1\oplus x\right)y} \qquad \qquad \\ {=1\oplus x\oplus y\oplus z\oplus y\oplus xy=1\oplus x\oplus z\oplus xy} \end {array} $$

The permutation of variables (x, y, z) → (x, z, y) in G leads to the function H(h₁, h₂, h₃):

$$ {h}_1\left(x,y,z\right)={g}_1\left(x,z,y\right)=1\oplus x\oplus yz\vspace*{-12pt} $$

$$ {h}_2\left(x,y,z\right)={g}_2\left(x,z,y\right)=1\oplus x\oplus z\oplus y\oplus xy\vspace*{-12pt} $$

$$ {h}_3\left(x,y,z\right)={g}_3\left(x,z,y\right)=1\oplus x\oplus y\oplus xz $$

Negating all three functions h₁, h₂, and h₃ leads to the function K = (k₁, k₂, k₃):

$$ {k}_1\left(x,y,z\right)={h_1}^{'}\left(x,y,z\right)=1\oplus \left(1\oplus x\oplus yz\right)=x\oplus yz\vspace*{-12pt} $$

$$ {k}_2\left(x,y,z\right)={h_2}^{'}\left(x,y,z\right)=1\oplus \left(1\oplus x\oplus z\oplus y\oplus xy\right)=x\oplus z\oplus y\oplus xy\vspace*{-12pt} $$

$$ {k}_3\left(x,y,z\right)={h_3}^{'}\left(x,y,z\right)=1\oplus \left(1\oplus x\oplus y\oplus xz\right)=x\oplus y\oplus xz $$

Finally, the following permutation of component functions (k₁, k₂, k₃) → (k₃, k₁, k₂) is performed leading to the function L(l₁, l₂, l₃):

$$ {l}_1\left(x,y,z\right)={k}_3\left(x,y,z\right)=x\oplus y\oplus xz\vspace*{-12pt} $$

$$ {l}_2\left(x,y,z\right)={k}_1\left(x,y,z\right)=x\oplus yz\vspace*{-12pt} $$

$$ {l}_3\left(x,y,z\right)={k}_2\left(x,y,z\right)=x\oplus z\oplus y\oplus xy $$

Thus the functions F = (f₁, f₂, f₃), G = (g₁, g₂, g₃), H = (h₁, h₂, h₃), K = (k₁, k₂, k₃), and L = (l₁, l₂, l₃) are pairwise NPNP-equivalent.

Each reversible function can be treated as a permutation. This is why we also recall basic notions connected with permutations. Let A be any set of numbers. A permutation on a set A is a bijective mapping from A to itself. Every permutation can be considered as collection of disjoint cycles. Here such a collection will be called a cycle structure. We will write a cycle in the form <a₁, a₂, ..., a_k>, meaning that a₁ is mapped onto a₂, ..., a_k is mapped onto a₁. It could be written in different ways, e.g., <a₂, a₃, ..., a_k , a₁>. The number of elements in a cycle is called the length of the cycle. A cycle with the length k is called a k-cycle. A 2-cycle is also called a transposition.

10.3 Previous Work

The motivation for our studies of reversible functions toward constructing their classifications is borrowed from the classical logic synthesis by referring to an analogy with related problems. For example, in classical logic synthesis, the equivalence of two functions under permutation of the variables is an important problem due to applications in the synthesis of multiplexer-based field-programmable gate arrays [11, 12]. The problem is called Boolean matching, and two functions match if they have the same P-representative. The extension to NP-representatives is done in [13, 14] in solving the Boolean matching problem in cell-library binding.

Classification of Boolean functions is a classical problem in logic synthesis due to its various applications, with fast prototyping and unification of testing procedures being just two of them [15]. However, a considerably smaller amount 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₁(x) and f₂(x) are equivalent if for each n-tuple x, there is a g ϵ G and an h ϵ H such that f₁(x) = h( f₂(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,19,20,21,22,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]).

10.4 Extrapolation Based on Cycle Structures

In [29, 30] it has been demonstrated that it is possible to extrapolate some properties of reversible functions by considering their cycle structures. This is why we tried to exploit the same approach to discover infinite sequences of reversible functions with all their component functions having at least one linear variable. First, we were able to check how many such reversible functions exist for n = 3. Namely, in Table 2 of our earlier paper [6] there are 52 NPNP classes of 3-variable reversible functions (denoted R1-R52) and 26 out of these 52 classes of functions possess all component functions depending essentially on all these variables. Among them three classes consist of reversible functions F(c, b, a) all whose component functions have at least one linear variable (let us call such functions in short RevFunCFLVs). Below PPRMs expressions for representatives of these three classes are listed together with the following information:

• Sets of linear variables for all component functions.

• Cardinality of a class.

NPNP Class R28 (Cardinality = 384)

$$ A=a\oplus bc\ \left(\mathrm{the}\ \mathrm{set}\ \mathrm{of}\ \mathrm{linear}\ \mathrm{variables}=\left\{a\right\}\right)\quad\quad $$

$$ B=a\oplus b\oplus ac\ \left(\mathrm{the}\ \mathrm{set}\ \mathrm{of}\ \mathrm{linear}\ \mathrm{variables}=\left\{b\right\}\right)\quad\quad $$

$$ C=a\oplus b\oplus c\oplus ab\ \left(\mathrm{the}\ \mathrm{set}\ \mathrm{of}\ \mathrm{linear}\ \mathrm{variables}=\left\{c\right\}\right)\vspace*{8pt} $$

NPNP Class R29 (Cardinality = 1152)

$$ A=a\oplus bc\ \left(\mathrm{the}\ \mathrm{set}\ \mathrm{of}\ \mathrm{linear}\ \mathrm{variables}=\left\{a\right\}\right)\quad\quad $$

$$ B=a\oplus b\oplus ac\ \left(\mathrm{the}\ \mathrm{set}\ \mathrm{of}\ \mathrm{linear}\ \mathrm{variables}=\left\{b\right\}\right)\quad\quad $$

$$ C=a\oplus b\oplus c\oplus ac\ \left(\mathrm{the}\ \mathrm{set}\ \mathrm{of}\ \mathrm{linear}\ \mathrm{variables}=\left\{b\right\}\right)\vspace*{8pt} $$

NPNP Class R32 (Cardinality = 576)

$$A=a\oplus bc\ \left(\mathrm{the}\ \mathrm{set}\ \mathrm{of}\ \mathrm{linear}\ \mathrm{variables}=\left\{a\right\}\right)\quad\quad $$

$$ B=a\oplus b\oplus bc\ \left(\mathrm{the}\ \mathrm{set}\ \mathrm{of}\ \mathrm{linear}\ \mathrm{variables}=\left\{a\right\}\right)\vspace*{-12pt} $$

$$ C=a\oplus c\oplus bc\ \left(\mathrm{the}\ \mathrm{set}\ \mathrm{of}\ \mathrm{linear}\ \mathrm{variables}=\left\{a\right\}\right) $$

The above listed PPRM expressions show some regular features. However, our experience is so that extrapolation of such features of PPRMs is very difficult because: (1) usually a component function is obtained which is not balanced, (2) even if all PPRMs correspond to balanced functions, then their collection does not constitute a reversible function. Therefore we have decided to apply extrapolation based on cycle structures. By considering the appropriate mappings {0, 1}³ → {0, 1}³ it is easy to establish that the above three representatives have the following cycle structures (note that here and later on we use the reverse order of variables and component functions and instead of a 3-tuple of binary values (a₃ , a₂ , a₁) or (c, b, a) we use its decimal equivalent):

• The representative of the NPNP class R28: < 0 > < 4 > < 1, 7, 2, 6, 3, 5 >,

• The representative of the NPNP class R29: < 0 > < 4 > < 5 > < 1, 7, 2, 6, 3 >,

• The representative of the NPNP class R32: < 0 > < 2 > < 4 > < 1, 7, 6 > < 3, 5 >.

However, these cycle structures do not help in formulating conjectures for n > 3. How to get similar results for n = 4 as checking all NPNP classes of 4-variable reversible functions is not possible because of their enormous number?

In [6] we calculated all NPN classes of balanced 4-variable functions (presented in Table 1 of [6]). Then we have performed a computational experiment reported in [6]. Let us quote:

We have checked that only for the following 18 out of 58 NPN-equivalence classes of balanced Boolean functions up to 4 variables (B1.1, B2.1, B3.1-B3.4, B4.1-B4.52) it is not possible to find four functions belonging to the same class which would constitute a 4-variable reversible function: B2.1, B3.2, B4.2, B4.3, B4.4, B4.7 (this class includes only 2 functions), B4.13, B4.15, B4.27, B4.28, B.4.31, B4.33, B4.34, B4.35, B4.38, B4.42, B4.48, B4.51.

Later we found a single representative for each of the NPNP-classes of 4-variable functions which consists of four non-degenerate component functions from the same NPN class of 4-variable balanced functions. Then we have checked that among 52 NPN-equivalence classes of 4-variable balanced functions (Table 1 of [6]) there are 10 classes having at least one linear variable: B4.1, 4.2, B4.3, B4.4, B4.7, B4.8, B4.9, B4.13, B4.15, B4.17. Only four of them lead to RevFunCFLVs depending on all four variables. They are listed below in the same manner as previously 3-variable RevFunCFLVs.

NPNP Class Built of Balanced Functions from Class B4.1 (Cardinality = 64)

$$A=a\oplus bcd\ \left(\mathrm{the}\ \mathrm{set}\ \mathrm{of}\ \mathrm{linear}\ \mathrm{variables}=\left\{a\right\}\right)\quad\quad$$

$$ B=b\oplus ac\oplus ac d\ \left(\mathrm{the}\ \mathrm{set}\ \mathrm{of}\ \mathrm{linear}\ \mathrm{variables}=\left\{b\right\}\right)\vspace*{-12pt} $$

$$ C=c\oplus ad\oplus abd\ \left(\mathrm{the}\ \mathrm{set}\ \mathrm{of}\ \mathrm{linear}\ \mathrm{variables}=\left\{c\right\}\right)\vspace*{-12pt} $$

$$ D=d\oplus ab\oplus ab c\ \left(\mathrm{the}\ \mathrm{set}\ \mathrm{of}\ \mathrm{linear}\ \mathrm{variables}=\left\{d\right\}\right)\vspace*{6pt} $$

NPNP Class Built of Balanced Functions from Class B4.8 (Cardinality = 192)

$$ A=a\oplus b\oplus c\oplus bc\oplus bc d\ \left(\mathrm{the}\ \mathrm{set}\ \mathrm{of}\ \mathrm{linear}\ \mathrm{variables}=\left\{a\right\}\right)\quad\quad $$

$$ B=a\oplus b\oplus bc\oplus bd\oplus cd\oplus bc d\ \left(\mathrm{the}\ \mathrm{set}\ \mathrm{of}\ \mathrm{linear}\ \mathrm{variables}=\left\{a\right\}\right)\vspace*{-12pt} $$

$$ C=a\oplus c\oplus bc\oplus bd\oplus cd\oplus bc d\ \left(\mathrm{the}\ \mathrm{set}\ \mathrm{of}\ \mathrm{linear}\ \mathrm{variables}=\left\{a\right\}\right)\vspace*{-12pt} $$

$$ D=a\oplus d\oplus ab\oplus ac\oplus bc\oplus ab c\ \left(\mathrm{the}\ \mathrm{set}\ \mathrm{of}\ \mathrm{linear}\ \mathrm{variables}=\left\{d\right\}\right)\vspace*{8pt} $$

NPNP Class Built of Balanced Functions from Class B4.9 (Cardinality = 96)

$$ A=a\oplus b\oplus bd\oplus cd\ \left(\mathrm{the}\ \mathrm{set}\ \mathrm{of}\ \mathrm{linear}\ \mathrm{variables}=\left\{a\right\}\right)\quad\quad $$

$$ B=a\oplus c\oplus bc\oplus bd\ \left(\mathrm{the}\ \mathrm{set}\ \mathrm{of}\ \mathrm{linear}\ \mathrm{variables}=\left\{a\right\}\right)\quad\quad $$

$$ C=a\oplus d\oplus bc\oplus cd\ \left(\mathrm{the}\ \mathrm{set}\ \mathrm{of}\ \mathrm{linear}\ \mathrm{variables}=\left\{a\right\}\right)\quad\quad $$

$$ D=a\oplus c\oplus d\oplus bd\oplus cd\ \left(\mathrm{the}\ \mathrm{set}\ \mathrm{of}\ \mathrm{linear}\ \mathrm{variables}=\left\{a\right\}\right)\vspace*{8pt} $$

NPNP Class Built of Balanced Functions from Class B4.17 (Cardinality = 32)

$$ A=a\oplus b\oplus bc\oplus bd\oplus cd\ \left(\mathrm{the}\ \mathrm{set}\ \mathrm{of}\ \mathrm{linear}\ \mathrm{variables}=\left\{a\right\}\right)\quad\quad\quad $$

$$ B=b\oplus c\oplus ac\oplus ad\oplus cd\ \left(\mathrm{the}\ \mathrm{set}\ \mathrm{of}\ \mathrm{linear}\ \mathrm{variables}=\left\{b\right\}\right)\quad\quad\quad $$

$$ C=a\oplus c\oplus ab\oplus ad\oplus bd\ \left(\mathrm{the}\ \mathrm{set}\ \mathrm{of}\ \mathrm{linear}\ \mathrm{variables}=\left\{c\right\}\right)\quad\quad\quad $$

$$ D=a\oplus b\oplus c\oplus d\oplus ab\oplus ac\oplus bc\ \left(\mathrm{the}\ \mathrm{set}\ \mathrm{of}\ \mathrm{linear}\ \mathrm{variables}=\left\{d\right\}\right) $$

The above 4 representatives of RevFunCFLVs have the following cycle structures:

$$ <0> <1> <2> <4> <6> <8> <10> <12>\\<3,11> <5,7> <9,13> <14,15> $$

$$ <0> <8> <1,15> <2,3,4,5> <6,9,7,14> <10,13,12,11>\vspace*{-12pt} $$

$$ <0> <5> <4,10,6,13> <1,15,8,12,11,9,3,14,7,2>\vspace*{-12pt} $$

$$ <0> <7> <8> <15> <1,13,4,14,2,11> <3,10,6,12,5,9>, $$

respectively.

It is possible to extrapolate the information collected by us about 3- and 4-variable RevFunCFLVs in many ways. First, let us note that there are no simple similarities between cycle structures for 3-variable and 4-variable functions. However, it can be noticed that the cycle structure of the first of the 4-variable representatives is the simplest one, consisting of just 4 transpositions (besides 1-element cycles):

$$ <3,11> <5,7> <9,13> <14,15> $$

Let us look closer at these transpositions expressing their elements as binary strings and change the order of transpositions in the following way:

$$ {\displaystyle \begin{array}{cccc}15& 7& 13& 11\\ {}111\mathbf{1}& 01\mathbf{1}1& 1\mathbf{1}01& \mathbf{1}011\\ 111\mathbf{0} & 01\mathbf{0}1 & 1\mathbf{0}01 & \mathbf{0}011 \\ 14& 5& 9& 3\end{array}} $$

In each of the pairs of binary strings forming a transposition the strings differ exactly in one bit. Moreover, we can observe the following property:

• In the first transposition the value of the first position from right is changing.

• In the second transposition the value of the second position from right is changing.

• In the third transposition the value of the third position from right is changing.

• In the fourth transposition the value of the fourth position from right is changing.

It is easy to extrapolate these properties and below we show that it leads to the desired infinite sequence of RevFunCFLVs.

10.5 Component Functions Having Linear Variables

In this section the existence of Boolean reversible functions with all component functions having at least one linear variable will be proved.

Definition 10.8

The reversible Boolean function Gⁿ(x_n , x_n−1 , …, x₁), n ≥ 3, is defined in such a manner that all non-identical mappings of variable assignments in Gⁿ can be partitioned into transpositions as follows:

• 1. one of the elements of the first transposition has weight n,

• 2. one of the elements of the other transpositions has weight n−1 and the only bit 0 in them is moving in a cycle:

  • (a) In the second transposition 0 is at the first position from left;

  • (b) In the third transposition 0 is at the second position from right;

  • (c) In the fourth transposition 0 is at the third position from right;

    …

  • (d) In the nth transposition 0 is at the (n−1)th position from right (another words, at the second position from left).

• 3. the second element of the ith transposition differs from the first element of the same transposition in ith bit from right.

Example 10.3

Let n = 6. Then the cycle structure of function Gⁿ consists of the following six transpositions:

$$ {\displaystyle \begin{array}{llllll}63& 31& 61& 59& 55& 47\\ {}11111\mathbf{1}& 0111\mathbf{1}1& 111\mathbf{1}01& 11\mathbf{1}011& 1\mathbf{1}0111& \mathbf{1}01111\\ {}11111\mathbf{0}& 0111\mathbf{0}1& 111\mathbf{0}01& 11\mathbf{0}011& 1\mathbf{0}0111& \mathbf{0}01111\\ {}62& 29& 57& 51& 39& 15\end{array}} $$

By a projection function it is meant a function of one variable. Notice that the ith component function g_i of Gⁿ differs from the projection function x_i only in two bits which are swapped according to (n−i + 1)th transposition above.

Theorem 10.1

Each n ^∗ n function G ⁿ is reversible for any n ≥ 3.

Proof.

The function Gⁿ is reversible because it is a bijective mapping. Namely, non-identical mappings of variable assignments in Gⁿ form a set of transpositions.

Lemma 10.2

The values of the ith component function of the n^∗ n reversible function Gⁿ differ from the values of the projection function x_i only for two assignments (as a result of swapping two values according to definition of Gⁿ).

Proof.

This property follows from the manner in which the transpositions for function Gⁿ are constructed (see Definition 10.8 and Example 10.3).

Theorem 10.2

Any component function f _i of the reversible Boolean function G ⁿ is linear with respect to the variable x _i for n ≥ 3.

Proof.

A function f is linear with respect to the variable x_i iff negating x_i is equivalent to negating the function itself (see Lemma 10.1). It can be easily shown that swapping two values (see Lemma 10.1) of component function f_i of the reversible function Gⁿ does not influence the property formulated in the first sentence of this proof.

10.6 Component Functions Belonging to Different P-Classes

Now we are going to show that for n ≥ 3 there exist Boolean reversible functions whose all component functions belong to different P-classes. Again, first we study cycle structures of selected functions of small numbers of variables and next try to apply extrapolation. We have checked in Table 2 of our paper [6] how many such reversible functions exist for n = 3.

It was noted in Sect. 10.4 that there are 26 NPNP-classes of 3-variable functions (R27–R52) that possess all component functions depending essentially on all three variables. Among them there is only one class that consists of reversible functions all whose component functions belong to different NPN-classes. It is shown below in the same manner as previously 3-variable RevFunCFLVs.

NPNP Class R40 (Cardinality = 2304)

$$ A=a\oplus bc\qquad\quad\quad\quad\quad $$

$$ B=b\oplus ac\oplus bc\qquad\quad\quad $$

$$ C=a\oplus c\oplus ab\oplus ac\oplus bc $$

Its cycle structure is as follows:

$$ <0> <2> <3> <4> <1,5,7,6>. $$

Let us note that binary n-tuples in the unique cycle having more than one element form a regular pattern:

$$ {\displaystyle \begin{array}{l}001\\ {}101\\ {}111\\ {}110\end{array}} $$

Namely, it is easy to note that

• The first and the second n-tuples differ only in the 1st bit position,

• The second and the third n-tuples differ only in the 2nd bit position,

• The third and the forth n-tuples differ only in the 3rd bit position.

Thus we observe here a certain periodicity which can be easily extrapolated leading to the desired infinite sequence of reversible functions as will be seen later. In this case extrapolating was even simpler than in the previous section.

Definition 10.9

A set of variable assignments over {0, 1} with specified numbers of m 0s and n 1s is called a block and denoted by b_m,n.

Example 10.4

The set of all 8 variable assignments for three variable Boolean functions can be partitioned into the following four blocks:

$$ {b}_{3,0}=\left\{000\right\}\ {b}_{2,1}=\left\{001,010,100\right\}\ {b}_{1,2}=\left\{011,101,110\right\}\ {b}_{0,3}=\left\{111\right\}. $$

Definition 10.10

For any Boolean function f let B⁰(f) and B¹(f) denote the sets of blocks including all variable assignments for which f is equal 0 and 1, respectively.

Example 10.5

Let us consider the following Boolean projection functions:

$$ f\left({x}_3,{x}_2,{x}_1\right)={x}_3,g\left({x}_3,{x}_2,{x}_1\right)={x}_2,h\left({x}_3,{x}_2,{x}_1\right)={x}_1. $$

Then

$$ {B}^0(f)=\left\{\ \left\{000\right\},\left\{001,010\right\},\left\{011\right\}\ \right\} \vspace*{-12pt}$$

$$ {B}^1(f)=\left\{\ \left\{100\right\},\left\{101,110\right\},\left\{111\right\}\ \right\} \vspace*{-12pt}$$

$$ {B}^0(g)=\left\{\ \left\{000\right\},\left\{001,100\right\}\ \left\{101\right\}\ \right\} \vspace*{-12pt}$$

$$ {B}^1(g)=\left\{\ \left\{010\right\},\left\{011,110\right\},\left\{111\right\}\ \right\} \vspace*{-12pt}$$

$$ {B}^0(h)=\left\{\ \left\{000\right\},\left\{010,100\right\},\left\{110\right\}\ \right\} \vspace*{-12pt}$$

$$ {B}^1(h)=\left\{\ \left\{001\right\},\left\{011,101\right\},\left\{111\right\}\ \right\} $$

Notice that for each 3-variable Boolean reversible function k the union of B⁰(k) and B¹(k) is equal to the set of all 8 Boolean variable assignments. For each of the component functions of an arbitrary reversible function cardinalities of unions of their Bⁱ sets are the same.

Example 10.6

Let us consider a 3-variable Boolean reversible function F(x₃, x₂, x₁) = (f₃, f₂, f₁) defined in such a manner that the only non-identical mappings of variable assignments in F are as follows:

$$ {\displaystyle \begin{array}{l}001\to 101\\ {}101\to 111\\ {}111\to 110\\ {}110\to 001\end{array}} $$

When we consider the reversible function F as a permutation of output assignments it is a single cycle of four elements:

$$ <001,101,111,110> $$

Notice that in the above mappings

• In the first row the leftmost bit is being negated,

• In the second row the second bit is being negated.

• In the third row the third bit is being negated.

• In the fourth row all bits are being negated.

This observation will be generalized later to functions of any number of variables.

Now let us note what changes have been done in the sets Bⁱ, 0 ≤ i ≤ 1, for functions f₃, f₂, and f₁, in comparison with the sets for the function in Example 10.5 (only assignments moved to another block are shown bolded and underlined):

$$ {B}^0\left({f}_3\right)=\left\{\ \left\{000\right\},\left\{010\right\},\left\{011,\underline{\mathbf{110}}\right\}\ \right\},\ {B}^1\left({f}_3\right)=\left\{\ \left\{\underline{\mathbf{001}},100\right\},\left\{101\right\},\left\{111\right\}\ \right\}, $$

$$ {B}^0\left({f}_2\right)=\left\{\ \left\{000\right\},\left\{001,100\right\},\left\{\underline{\mathbf{110}}\right\}\ \right\},\ {B}^1\left({f}_2\right)=\left\{\ \left\{010\right\},\left\{011,\underline{\mathbf{101}}\right\},\left\{111\right\}\ \right\}, $$

$$ {B}^0\left({f}_1\right)=\left\{\ \left\{000\right\},\left\{010,100\right\},\left\{\underline{\mathbf{111}}\right\}\ \right\},\ {B}^1\left({f}_1\right)=\left\{\ \left\{001\right\},\left\{011,101\right\},\left\{\underline{\mathbf{110}}\right\}\ \right\}. $$

Let us summarize the above observations (notation from Example 10.5 is used below).

The values of the function f₃ differ from the values of the projection function x₃ only for the assignments 001 and 110. Namely, we can notice that

$$ f\left(0,0,1\right)=0,\ {f}_3\left(0,0,1\right)=1,\vspace*{-8pt} $$

$$ f\left(1,1,0\right)=1,\ {f}_3\left(1,1,0\right)=0. $$

As a result, the function f₃ can be obtained from the projection function x₃ by swapping its values for variable assignments 001 and 110.

Values of each of the other two component functions, f₂ and f₁, also differ from the values of the corresponding projection functions only for two assignments.

Swaps for f₂ in comparison with the projection function x₂ are as follows:

$$ g\left(1,0,1\right)=0,\ {f}_2\left(1,0,1\right)=1, $$

$$ g\left(1,1,0\right)=1,\ {f}_2\left(1,1,0\right)=0, $$

Swaps for f₁ in comparison with the projection function x₁ are as follows:

$$ h\left(1,1,1\right)=1,\ {f}_1\left(1,1,1\right)=0, $$

$$ h\left(1,1,0\right)=0,\ {f}_1\left(1,1,0\right)=1. $$

Let us show that component functions f₂ and f₁ belong to different P-equivalence classes. Assume that f₂ and f₁ belong to the same P-equivalence class. Then, since any permutation over the variable set {x₃, x₂, x₁} does not change the assignment 111 there should be f₁(1, 1, 1) = f₂(1, 1, 1); however, f₁(1, 1, 1) = 0 and f₂(1, 1, 1) = 1. It is in contradiction with our assumption that f₂ and f₁ belong to the same P-equivalence class. Thus f₂ and f₁ belong to different P-equivalence classes.

In a similar manner it can be shown that the other two pairs of component functions of F, (f₃, f₂) and (f₃, f₁), belong to different P-equivalence classes. Let us show that component functions f₃ and f₂ belong to different P-equivalence classes. Assume that f₃ and f₂ belong to the same P-equivalence class. Then, any permutation over the variable set {x₃, x₂, x₁} changes variable assignments with specified numbers of 0s and 1s only within one block. Let us consider the block

$$ {b}_{1,2}=\left\{011,101,110\right\}. $$

Note that f₂(0, 1, 1) = f₂(1, 0, 1) = 1, f₂(1, 1, 0) = 0. However, f₃(0, 1, 1) = f₃(1, 0, 1) = f₃(1, 1, 0) = 1. Hence f₂ cannot be transformed to f₃ by permutation of variables. It is in contradiction with our assumption that f₃ and f₂ belong to the same P-equivalence class. Thus f₃ and f₂ belong to different P-equivalence classes.

Now let us show that component functions f₃ and f₁ belong to different P-equivalence classes. Assume that f₃ and f₁ belong to the same P-equivalence class. Consider the block

$$ {b}_{1,2}=\left\{011,101,110\right\}. $$

Note that f₁(0, 1, 1) = f₁(1, 0, 1) = f₁(1, 1, 0) = 1. However, f₃(0, 1, 1) = 0, f₃(1, 0, 1) = f₃(1, 1, 0) = 1. Hence f₁ cannot be transformed to f₃ by permutation of variables. It is in contradiction with our assumption that f₃ and f₁ belong to the same P-equivalence class. Thus f₃ and f₁ belong to different P-equivalence classes.

Now the above presented methodology of proving that two component functions of F belong to different P-equivalence classes will be extended to Boolean reversible functions of any number of variables.

To prove that Boolean reversible functions with all component functions belonging to different P-equivalence classes exist for any number of variables n ≥ 3, we will define the following infinite sequence of reversible functions.

Definition 10.11

The reversible Boolean function Hⁿ(x_n , x_n−1 ,…, x₁) = ( f_n , f_n−1 ,…, f₁), n ≥ 3, is defined in such a manner that the only non-identical mappings of variable assignments in Hⁿ are as follows (N denotes negation):

$$ {\displaystyle \begin{array}{l}{a}_n,{a}_{n-1},\dots, {a}_1\to {Na}_n,{a}_{n-1},\dots, {a}_1\\ {}{Na}_n,{a}_{n-1},\dots, {a}_1\to {Na}_n,{Na}_{n-1},\dots, {a}_1\\ {}\dots \\ {}{Na}_n,{Na}_{n-1},\dots, {Na}_2,{a}_1\to {Na}_n,{Na}_{n-1},\dots, {Na}_2,{Na}_1\\ {}{Na}_n,{Na}_{n-1},\dots, {Na}_2,{Na}_1\to {a}_n,{a}_{n-1},\dots, {a}_1,\end{array}} $$

where the starting variable assignment is as follows:

$$ {a}_n\ {a}_{n-1}\ {a}_{n-2}\dots {a}_2\ {a}_1=0\ 0\ 0\dots 0\ 1. $$

Notice that in the ith row of the mappings in Definitions 10.1 and 10.11 ≤ i ≤ n, the ith bit is being negated, and in the last mapping all bits are being negated.

When we consider the function Hⁿ as a permutation of variable assignments it is a single cycle of n + 1 elements:

$$ \begin{array}{l}<{a}_n,{a}_{n-1},\dots, {a}_1,\\ {N}{a}_n,{a}_{n-1},\dots, {a}_1,\\ {N}{a}_n, {N}{a}_{n-1},\dots, {a}_1,\\ \dots,\\ {N}{a}_n, {N}{a}_{n-1},\dots, {N}{a}_2,{a}_1,\\ {N}{a}_n, {N}{a}_{n-1},\dots, {N}{a}_2,{N}{a}_1>.\end{array} $$

Theorem 10.3

Each n^∗ n function Hⁿ is reversible for any n ≥ 3, where Hⁿ is formulated in Definition 10.11 .

Proof.

Because non-identical mappings of variable assignments in Hⁿ form a single cycle so this function is bijective for any n ≥ 3. Hence it is reversible.

Lemma 10.3

The values of the ith component function of the n^∗ n reversible function Hⁿ differ from the values of the projection function x_i only for two assignments (it is a result of swapping two values).

Proof.

This property follows from the manner in which the cycle for function Hⁿ is constructed in Definition 10.11 (e.g., compare sets B⁰, B¹ in Examples 10.5 and 10.6).

Theorem 10.4

Any two component functions f _r and f _s of the Boolean reversible function H ⁿ belong to different P-equivalence classes for n ≥ 3.

Proof.

Let us write the cycle defining the function Hⁿ(x_n , x_n−1 ,…, x₁) = ( f_n , f_n−1 ,…, f₁) in the form: <u₁ , u₂ , u₃ ,…,u_n−1, u_n, u_n+1>, where

$$ {\displaystyle \begin{array}{l}{u}_1=000\dots 001\\ {}{u}_2=100\dots 001\\ {}{u}_3=110\dots 001\\ {}\dots \\ {}{u}_{n-1}=111\dots 101\\ {}{u}_n=111\dots 111\\ {}{u}_{n+1}=111\dots 110.\end{array}} $$

Thus the only non-identical mappings of variable assignments in Hⁿ are as follows:

$$ {\displaystyle \begin{array}{l}0,0,\dots, 01\to 1,0,\dots, 0,1\\ {}1,0,\dots, 01\to 1,1,\dots, 0,1\\ {}\dots \\ {}1,1,\dots, 0,1\to 1,1,\dots, 1,1\\ {}1,1,\dots, 1,1\to 1,1,\dots, 1,0\\ {}1,1,\dots, 1,0\to 0,0,\dots, 0,1.\end{array}} $$

Thus Hⁿ(u_i) = u_i+1 for 1 ≤ i ≤ n and Hⁿ(u_n+1) = u₀. Notice that u_i ∈ b_{n − i, i}, 1 ≤ i ≤ n and u_n + 1 ∈ b_{1, n − 1}. For any n the number of all assignments in the block b_{n − i, i} is equal $\frac{n!}{\left(n-i\right)!i!}$ and the block b_{1, n − 1} contains exactly n assignments. For an arbitrary selected k-th bit, 1 ≤ k ≤ n, there are $\frac{\left(n-1\right)!}{\left(n-i-1\right)!(i)!}$ assignments belonging to b_{n − i, i} and having this k-th bit equal 0. Similarly, there are $\frac{\left(n-1\right)!}{\left(n-i\right)!\left(i-1\right)!}$ assignments belonging to b_{n − i, i} and having the k-th bit equal 1. Also, f_k(u) = 0 if the k-th bit in the input assignment is 0 (e.g., for n > 3: f₂(u₁) = 0; f₃(u₁) = 0,..., f_n−1(u₁) = 0, f_n(u₁) = 1). For 1 < k ≤ n we have f_k(u_n−k+1) = 1 and f₁(u_n) = 0.

Let us consider the following two cases with respect to i:

• A. 1 ≤ i < n

  • B⁰(f_{k ≠ n−i+1}) contains $\frac{\left(n-1\right)!}{\left(n-i-1\right)!i!}$ assignments from b_{n − i, i},

  • B¹(f_{k ≠ n−i+1}) contains $\frac{\left(n-1\right)!}{\left(n-i\right)!\left(i-1\right)!}$ assignments from b_{n − i, i}.

On the other hand, since f_k = i(u_i) = 1, so

• B ⁰(f_{k = n−i+1}) contains $\frac{\left(n-1\right)!}{\left(n-i-1\right)!i!}-1$ assignments from b_{n − i, i},

• B ¹(f_{k = n−i+1}) contains $\frac{\left(n-1\right)!}{\left(n-i\right)!\left(i-1\right)!}+1$ assignments from b_{n − i, i}.

Thus for any i, 1 ≤ i < n, B¹(f_{k ≠ n−i + 1}) and B¹(f_{k = n−i + 1}) have different numbers of assignments from the block b_n-i,i so the function f_{k ≠ n−i+1} cannot be transformed to f_{k = n−i+1} by permutation of variables, as it only changes assignments within the block b_n-i,i.

• B. i = n (i.e., n–i + 1 = 1)

  • B¹(f_k ≠ 1) contains one assignment from b_0,n,

  • B¹(f_k = 1) contains no assignments from b_0,n,

  • B⁰(f_k ≠ 1) contains n assignments from b_1,n−1,

  • B⁰(f_k = 1) contains n + 1 assignments from b_1,n−1.

Thus B¹(f_k ≠ 1) and B¹(f_k = 1) as well as B¹(f_k ≠ 1) and B¹(f_k = 1) have different numbers of assignments from the blocks b_0,n and b_1,n−1, respectively.

So the function f_{k ≠ n−i + 1} cannot be transformed to f_{k = n−i + 1}, for any 1 ≤ i ≤ n, by permutation of variables, as it changes assignments within the corresponding blocks. Hence, if i ≠ j, then f_i and f_j belong to different P-equivalence classes.

It is obvious that by Theorem 10.4 the following result holds.

Corollary 10.1

For any n ≥ 3 there exist ternary reversible functions having all component functions that belong to different P-equivalence classes.

10.7 Conclusions and Future Work

The paper presents two new results on properties of component functions of Boolean reversible functions. The main subject of the paper is showing that the solutions in this area can be found by extrapolation of cycle structures for 3- and 4-variable Boolean reversible functions obtained in the course of enumerative computations. Namely, the solutions of the two problems have been discovered by using our extrapolation approach. The solved problems are as follows: (1) for any n ≥ 3 there exists a Boolean reversible function with all component functions having at least one linear variable, (2) for any n ≥ 3 there exists a Boolean reversible function with all component functions belonging to different P-equivalence classes. We plan using the abovementioned results together with our previous results presented in [6, 7] to construct a classification of reversible Boolean functions which would be useful in the synthesis of reversible circuits.