2.3. PRIMAL DECOMPOSITION 31
controlled circuit:
U
11
U
11
D
;
an equality that also can be written in matrix form:
U
11
I
D
I
I
I
U
11
I
I
:
e matrix
I
I
is a matrix of the form (2.3), however with exclusively
0 1
1 0
blocks. It is
a controlled NOT gate with constant control function f D 1. In other words, it is an uncontrolled
NOT
:
We thus are allowed to say that the negatively controlled circuit is decomposed here into
• a member of P
x
(n),
• a member of P
z
(n), and
• a second member of P
x
(n).
2.3 PRIMAL DECOMPOSITION
De Vos and Van Rentergem [24] have demonstrated that it is always possible to decompose
an arbitrary classical reversible circuit acting on w bits into three controlled circuits acting on
w 1 bits and one controlled NOT gate:
U
D
D
B A
:
(2.4)
32 2. BOTTOM
e proof is based on the remarkable theorem of Section 1.8, with n D 2
w
, q D 2 and p D 2
w1
.
In matrix form
3
the theorem reads
U D
A
B
C
I
D
;
where C stands for a matrix of the form (2.3), in other words, a member of P
x
(n). Whereas
the submatrices A, B, and D correspond to the “horizontal” permutations of Section 1.8, the
matrix C corresponds to the “vertical” permutation.
Because of the identity
A
B
D
I
I
I
A
I
I
I
B
;
we can say that any member U of the group P(n) can be decomposed into three matrices of the
group P
x
(n) and three matrices of the group P
z
(n). is proves that the closure of the groups
P
x
(n) and P
z
(n) equals P(n).
According to Section 1.8, one of the two “horizontal permutations” performs not q D 2
but only q 1 D 1 permutations of p D 2
w1
objects, such that one of its two permutations is
a non-permutation. Hence, this step consists not of two but of only one controlled .w 1/-bit
circuit (i.e., controlled circuit D in circuit (2.4)).
e detailed algorithm is as follows [24]. We add to the given truth table (consisting of
w input columns A and w output columns P ) w extra columns F and w extra columns J . en,
these new columns are filled in, in five steps.
• First, we fill in two columns: column F
1
by copying column A
1
and column J
1
by copying
column P
1
.
• en, in the rows satisfying A
1
D 0, we fill in .F
2
; F
3
; : : : ; F
w
/ D .J
2
; J
3
; : : : ; J
w
/ by
copying .A
2
; A
3
; : : : ; A
w
/ from the same rows.
• en, in the remaining rows which satisfy P
1
˚ P
0
1
D 1, we also fill in .F
2
; F
3
; : : : ; F
w
/ D
.J
2
; J
3
; : : : ; J
w
/ by copying .A
2
; A
3
; : : : ; A
w
/ from the same rows.
• en, in the still remaining rows which satisfy P
1
D 0, we fill in .F
2
; F
3
; : : : ; F
w
/ D
.J
2
; J
3
; : : : ; J
w
/ by copying .A
2
; A
3
; : : : ; A
w
/ from the remaining rows with P
1
D 1.
• Finally, in the still remaining rows, we fill in .F
2
; F
3
; : : : ; F
w
/ D .J
2
; J
3
; : : : ; J
w
/ by copy-
ing the still remaining .A
2
; A
3
; : : : ; A
w
/ rows.
Above, that is, in the third step, P
0
1
denotes the bit value in column P
1
, but 2
w1
rows above
the row under consideration.
3
Whereas in a matrix product, subsequent matrices are applied from right to left, in a logic circuit bits are transformed
from left to right, according to tradition in engineering. Again it is no surprise that this sometimes (if not often) leads to
confusion/errors.
2.3. PRIMAL DECOMPOSITION 33
Table 2.3: Expanding the truth table
A
1
A
2
A
3
P
1
P
2
P
3
A
1
A
2
A
3
F
1
F
2
F
3
J
1
J
2
J
3
P
1
P
2
P
3
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
1 1 1
1 1 0
1 0 0
0 0 0
1 0 1
0 1 0
0 0 1
0 1 1
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
0 0 0
0 0 1
0 1 0
0 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 0 0
1 0 1
1 1 0
0 1 1
1 1 1
0 1 1
0 1 1
0 1 1
1 1 1
1 1 0
1 0 0
0 0 0
1 0 1
0 1 0
0 0 1
0 1 1
Table 2.4: Filling in the expanded truth table according to the primal algorithm
A
1
A
2
A
3
F
1
F
2
F
3
J
1
J
2
J
3
P
1
P
2
P
3
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
0 0 0
0 0 1
0 1 0
0 1 1
1 1 1
1 0 1
1 1 0
1 0 0
1 0 0
1 0 1
1 1 0
0 1 1
1 1 1
0 0 1
0 1 0
0 0 0
1 1 1
1 1 0
1 0 0
0 0 0
1 0 1
0 1 0
0 0 1
0 1 1
We illustrate the full procedure for the circuit in Table 2.2a with w D 3. Table 2.3 shows
the expansion of the table, followed by the first two steps of the procedure. By applying the whole
procedure, we obtain Table 2.4. Note that the third step of the procedure is emphasized in italic
and the fourth and fifth steps are boldfaced. We see that automatically, between the bits F and
the bits J , a controlled NOT is synthesized. Inspection of the F and J columns reveals that here
the control function f .F
2
; F
3
/ equals F
2
C F
3
.
We thus have reduced the synthesis of one 3-bit circuit to the synthesis of three 2-bit
circuits and one controlled NOT:
:
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.