34 2. BOTTOM
In other words, we find a controlled NOT, sandwiched between controlled .w 1/-bit circuits.
By applying our procedure to each of the three new circuits, we end up with nine controlled
1-bit circuits and four controlled NOTs:
:
We thus have a total of 13 controlled 1-bit gates. We say that we have a gate cost of 13. In
the general problem of synthesizing a w-bit circuit, we find a cascade of .3
w
1/=2 controlled
single-bit gates [24]. However, some of the 1-bit circuits turn out to be controlled IDENTITY
gates. In our example:
X
I X
I
X X I
I X
:
Because a controlled IDENTITY gate equals an uncontrolled IDENTITY gate, we are allowed to
delete it from the schematic:
:
us our example synthesis consists of only nine controlled NOT gates,
4
of which at least five are
simply TOFFOLI gates.
For an arbitrary reversible circuit acting on w bits, we can equally repeat our decomposition
procedure until all controlled circuits are members of S
2
, i.e., equal either 1-bit NOT gates or 1-
bit IDENTITY gates, with the latter allowed to be ignored. When we apply the approach to each
of the 8! = 40,320 circuits of width w D 3, we thus obtain a statistical distribution of gate costs,
ranging from 0 to .3
w
1/=2 D 13, with about 6.6 average gate cost [12].
2.4 DUAL DECOMPOSITION
Instead of sandwiching a member of S
8
2
between two members of S
2
8
, as in (2.4), De Vos and
Van Rentergem [12, 25, 26] have demonstrated that we can also work the other way around:
4
e reader may verify that here, in fact, only eight gates are necessary. Post-synthesis optimization indeed can merge two
gates:
D
:
2.4. DUAL DECOMPOSITION 35
sandwich a member of S
2
8
between two members of S
8
2
:
U
D
B A
:
(2.5)
is is indeed always possible. Again, a proof is provided by Birkhoff’s theorem (Section 1.8),
however this time with n D 2
w
, p D 2 and thus q D 2
w1
. erefore, we may conclude that a
synthesis of an arbitrary circuit of width
w
may consist of the cascade of
• a first controlled NOT gate,
• two controlled circuits, and
• a second controlled NOT gate.
Note that circuit (2.5) is like (2.4) inside out. Both circuits are called 3-sandwiches [27]. We say
that the two circuits are each other’s dual. ey are indeed based on two dual Young subgroups.
ese subgroups are based on two dual partitions of the number
2
w
:
2
w
D 2
w1
C 2
w1
D 2 C 2 C::: C 2 (2
w1
terms) ;
in accordance with (1.12).
e detailed algorithm of the dual decomposition is as follows [12]. Like in the primal
decomposition, in the present dual decomposition, 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 .
We use F
p
.q/ for the value of bit F
p
in the q th row of the truth table and analogously J
p
.q/
for the value of bit J
p
. e columns F
p
and J
p
are filled in, in three steps.
• First, we fill in 2.w 1/ columns: columns F
2
, F
3
, …, F
w
by copying columns A
2
, A
3
,
…, A
w
and columns J
2
, J
3
, …, J
w
by copying columns P
2
, P
3
, …, P
w
.
• en we construct a “coil” of 0’s and 1’s, starting from bit F
1
.1/ using a zero label.
• en we construct a coil starting from the non-filled-in F
1
.j / with lowest j , using a zero
label, and so on, until all F
1
(and thus also all J
1
) are filled in.
Above, a coil consists of a finite number of “windings.” Here, a winding is a four-bit sequence
F
1
.k/ D X, F
1
.l/ D X, J
1
.l/ D X, and J
1
.m/ D X, where l results from the condition that the
string F
2
.l/; F
3
.l/; : : : ; F
w
.l/ has to be equal to the string F
2
.k/; F
3
.k/; : : : ; F
w
.k/ and where m
results from the condition that the string J
2
.m/; J
3
.m/; : : : ; J
w
.m/ has to be equal to the string
36 2. BOTTOM
J
2
.l/; J
3
.l/; : : : ; J
w
.l/. e number X (with X 2 f0; 1g) we call the “label” of the winding. e
first winding of a coil starts at some F
1
.k
1
/; the second winding starts at F
1
.k
2
/, with k
2
equal
to m
1
, i.e., the row number of the end of the first winding. We continue, winding after winding
(all using the same label), until we find an m equal to k
1
, i.e., until the coil arrives at J
1
.k
1
/,
next to the starting point of the first winding. en the coil is closed. As all windings of a same
coil have the same label, we can refer to it as the label of the coil.
Although the above text might suggest that the algorithm is complicated, it is in fact very
straightforward. Tables 2.5 and 2.6 introduce an illustration of this fact by presenting a reversible
circuit of width w D 2, i.e., the circuit with two inputs (A
1
and A
2
) and two outputs (P
1
D A
2
and P
2
D A
1
, in this particular case). First, between the columns .A
1
; A
2
/ and .P
1
; P
2
/ of the
truth table, we insert the four empty columns .F
1
; F
2
/ and .J
1
; J
2
/. Subsequently, columns
F
2
and J
2
are filled in by simply copying columns A
2
and P
2
, respectively. is step is shown
in Table 2.5 and repeated in Table 2.6. Next comes the tricky part: filling in the columns F
1
and J
1
. For the reader’s convenience, the boldfaced bits F
1
and J
1
in Table 2.6 are provided
with subscripts that tell in which order the bit values are filled in. We start at F
1
.1/. We may
set this bit arbitrarily, but we choose to set it to 0. is starting choice (i.e., the label of the
coil) is marked by the subscript 1 in Table 2.6. As a consequence, we automatically can fill in
a lot of other bits in columns F
1
and J
1
. Indeed, as all computations need to be reversible,
F
1
.1/ D 0 automatically leads to F
1
.3/ D 1 (with subscript 2). en we impose J
1
.3/ D F
1
.3/,
i.e., J
1
.3/ D 1 (with subscript 3). Again, reversibility requires that J
1
.3/ D 1 infers J
1
.4/ D 0,
Table 2.5: Expanding a 2-bit truth table
A
1
A
2
P
1
P
2
A
1
A
2
F
1
F
2
J
1
J
2
P
1
P
2
0 0
0
1
1 0
1 1
0 1
1 1
0 0
1 0
0 0
0 1
1 0
1 1
0
0
0 1
0 0
0 1
0 1
0 1
0 0
0 0
0
1
1 1
0 0
1 0
Table 2.6: Filling in the expanded 2-bit truth table according to the dual algorithm
A
1
A
2
F
1
F
2
J
1
J
2
P
1
P
2
0
0
0
1
1 0
1 1
0
1
0
1
6
1
1
2
0
0
5
1
0
8
1
1
7
1
1
3
0
0
4
0
0 1
1 1
0 0
1 0
2.4. DUAL DECOMPOSITION 37
and so on, until we come back at the starting point F
1
.1/. In the present example, everything
is filled in when the traveling around is closed. So, this synthesis is finished after a single coil
(with two windings). is example illustrates that during the application of the algorithm, we
“walk in circles,” while assigning the bit sequence
0; 1; 1; 0; 0; 1; 1; : : : ; 1; 1; 0; 0; 1; 1; 0 :
In case the first coil would be closed before the two columns J
1
and F
1
are completely filled in,
the designer just has to start a second coil, and so forth.
We will now apply our procedure for the circuit in Table 2.2a with w D 3. Table 2.7
shows the expansion of the table, followed by the first step of the procedure. By applying the
full procedure, we obtain Table 2.8. In this example, we have two coils. e former coil (with
subscripts from 01 to 12) consists of three windings, whereas the latter coil (with subscripts
from 13 to 16) consists of merely one winding.
e above procedure thus yields a decomposition of the logic circuit into three logic cir-
cuits, two of which are automatically controlled NOTs. Inspection of Table 2.8 leads to the cor-
responding control functions f .A
2
; A
3
/ D A
2
A
3
and f .J
2
; J
3
/ D J
2
. e third circuit (i.e., the
middle circuit) consists of one positively controlled 2-bit circuit and one negatively controlled
2-bit circuit.
We thus have reduced the synthesis of one 3-bit circuit to the synthesis of two 2-bit circuits
and two controlled NOTs:
:
By applying our procedure to each of these two new circuits, we end up with four controlled
1-bit circuits and six controlled NOTs:
:
We thus have a total gate cost of 10. In the general problem of synthesizing a w-bit circuit,
we find a cascade of
3
2
2
w
2 controlled single-bit gates [12, 28]. However, some of the 1-bit
circuits may be controlled IDENTITY gates:
X X
X I
:
38 2. BOTTOM
Table 2.7: Expanding the 3-bit 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 1
1 0
1 1
0 0
0 1
1 0
1 1
1 1
1 0
0 0
0 0
0 1
1 0
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
Table 2.8: Filling in the expanded 3-bit truth table according to the dual 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
01
0 0
0
13
0 1
1
06
1 0
0
09
1 1
1
02
0 0
1
14
0 1
0
05
1 0
1
10
1 1
0
12
1 1
0
16
1 0
1
07
0 0
0
08
0 0
1
03
0 1
1
15
1 0
0
04
0 1
1
11
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
Because a controlled IDENTITY gate equals an uncontrolled IDENTITY gate, we are allowed to
delete it from the schematic:
:
us our example synthesis consists of only nine controlled NOT gates, of which at least three are
simply TOFFOLI gates. For an arbitrary reversible circuit acting on w bits, we can equally repeat
our decomposition procedure until all controlled circuits are members of S
2
, in other words,
equal either a 1-bit NOT gate or a 1-bit IDENTITY gate, with the latter allowed to be ignored.
When we apply the approach to each of the 8! = 40,320 circuits of w D 3, we thus obtain a
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.