26 2. BOTTOM
2.2 TWO IMPORTANT YOUNG SUBGROUPS OF S
2
w
Table 2.2a shows the truth table of an arbitrary reversible gate of width w D 3. It has w input bits
and w output bits and consists of 2
w
D 8 rows. Its eight output words are merely a permutation
of its eight input words 000, 001, …, 111. It therefore is a member of the symmetric group S
n
with n equal to 2
w
.
2.2.1 CONTROLLED CIRCUITS
If n is even, then S
n
has a particular Young subgroup S
n=2
1
S
n=2
(or simply S
n=2
), represented
by n n permutation matrices U consisting of two n=2 n=2 blocks I and U
22
on the diagonal:
U D
I 0
0 U
22
; (2.1)
where 0 denotes the n=2 n=2 zero matrix, I denotes the n=2 n=2 unit matrix, and U
22
is
an arbitrary n=2 n=2 permutation matrix. We recall that the elements of S
2
w
describe all re-
versible circuits acting on w bits. ey are represented by the 2
w
2
w
permutation matrices.
Among these 2
w
Š matrices, 2
w1
Š are represented by matrices of type (2.1). An example for
w D 3 is
0
B
B
B
B
B
B
B
B
B
B
B
@
1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0
1
C
C
C
C
C
C
C
C
C
C
C
A
:
We can stress its membership of S
4
1
S
4
by writing
0
B
B
B
B
B
B
B
B
B
B
B
@
1
1
1
1
1 0 0 0
0 0 0 1
0 1 0 0
0 0 1 0
1
C
C
C
C
C
C
C
C
C
C
C
A
; (2.2)
where empty spaces represent zeroes. In the corresponding truth table, that is, Table 2.2b, output
column P
1
is identical to input column A
1
. In other words, the reversible circuit does not alter
the first bit. Submatrix I tells what happens with the remaining w 1 bits if bit A
1
equals 0: bits
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.