10 New Results on Reversible Boolean Functions Having Component. . .
227
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 n (x n , x n−1 , . . . , x 1 ), n ≥ 3, is
defined in such a manner that all non-identical mappings of variable assignments in
G n 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 n consists of the
following six transpositions:
63
31
61
59
55
47
111111 011111 111101 111011 110111 101111
111110 011101 111001 110011 100111 001111
62
29
57
51
39
15
By a projection function it is meant a function of one variable. Notice that the ith
component function g i of G n 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 n is reversible for any n ≥ 3.
Proof. The function G n is reversible because it is a bijective mapping. Namely,
non-identical mappings of variable assignments in G n form a set of transpositions.
Lemma 10.2 The values of the ith component function of the n ∗ n reversible
function G n 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 n ).
Proof. This property follows from the manner in which the transpositions for
function G n are constructed (see Definition 10.8 and Example 10.3).
Theorem 10.2 Any component function f i of the reversible Boolean function G n is
linear with respect to the variable x i for n ≥ 3.
227
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 n (x n , x n−1 , . . . , x 1 ), n ≥ 3, is
defined in such a manner that all non-identical mappings of variable assignments in
G n 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 n consists of the
following six transpositions:
63
31
61
59
55
47
111111 011111 111101 111011 110111 101111
111110 011101 111001 110011 100111 001111
62
29
57
51
39
15
By a projection function it is meant a function of one variable. Notice that the ith
component function g i of G n 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 n is reversible for any n ≥ 3.
Proof. The function G n is reversible because it is a bijective mapping. Namely,
non-identical mappings of variable assignments in G n form a set of transpositions.
Lemma 10.2 The values of the ith component function of the n ∗ n reversible
function G n 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 n ).
Proof. This property follows from the manner in which the transpositions for
function G n are constructed (see Definition 10.8 and Example 10.3).
Theorem 10.2 Any component function f i of the reversible Boolean function G n is
linear with respect to the variable x i for n ≥ 3.