42 2. BOTTOM
P
w1
D A
w1
. ese properties reveal that g
w1
is nothing but a control gate with controlled
bit A
w
. erefore, Figure 2.4d is equivalent to Figure 2.4e, such that we have decomposed g into
2w 1 controlled NOT gates. is procedure automatically leads us to the refined algorithm.
We add to the given truth table (consisting of w input columns A and w output
columns P ) not two extra sets of columns, but 2.w 1/ sets of columns. We call them A
1
, A
2
,
…, A
w2
, A
w1
, P
w1
, P
w2
, …, P
2
, and P
1
. Together they make 2.w 1/w new columns.
ese are filled in, in the following steps.
• First, we fill in all A
1
columns except column A
1
1
by copying the w 1 corresponding
A columns, and analogously, we fill in all P
1
columns except column P
1
1
by copying the
w 1 corresponding P columns.
• en we fill in the two columns A
1
1
and P
1
1
by constructing a coil, starting from bit A
1
1
.1/,
then constructing a new coil, starting at the non-filled-in A
1
1
.j / with lowest j , and so on,
until all A
1
1
(and thus also all P
1
1
) are filled in.
• en, we fill in all A
2
columns except column A
2
2
by copying the w 1 corresponding
A
1
columns, and analogously, we fill in all P
2
columns except column P
2
2
by copying the
w 1 corresponding P
1
columns.
• en we fill in the two columns A
2
2
and P
2
2
by constructing the appropriate number of
coils, starting from bit A
2
2
.1/, until all A
2
2
(and thus also all P
2
2
) are filled in.
• We do so, until finally all A
w1
w1
(and thus also all P
w1
w1
) are filled in. At that moment, we
have all 2w
2
2
w
entries of the extended table.
We end the present section with a historical perspective. e Birkhoff theorem, the basis
of the above synthesis procedure, also is the basis of the existence of Clos networks [30], more
precisely, rearrangeable (non-blocking) Clos networks [31–33]. e approach has been applied
successfully in telephone switching systems and Internet routing [34]. ese conventional ap-
plications of the Birkhoff theorem are concerned with permutations of wires (or communication
channels). Here we apply the theorem not to the w wires, but to the 2
w
possible messages.
2.7 EXAMPLES
We illustrate our “refined” procedure by the example circuit in Table 2.2a. By applying the table
expansion and the first procedure step, we obtain Table 2.10. By applying the full procedure, we
obtain Table 2.11. e second step of the procedure is displayed in italic. is step was already
applied in Table 2.8. e third step of the algorithm is underlined.
e above procedure thus yields a decomposition of the logic circuit into five logic circuits
(one computing A
1
from A, one computing A
2
from A
1
, …, and one computing P from P
1
).
All five subcircuits are automatically controlled NOT gates. By merely inspecting Table 2.11,
2.7. EXAMPLES 43
Table 2.10: Expanded truth table according to the refined algorithm
A
1
A
2
A
3
A
1
A
2
A
3
A
1
A
2
A
3
P
1
P
2
P
3
P
1
P
2
P
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 0 0
1 0 1
1 1 0
1 1 1
1 0 0
1 0 1
1 1 0
1 1 1
1 1 1
1 1 0
1 0 0
1 0 0
1 0 1
1 1 0
1 0 1
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
1 1 1
2 2 2
2 2 2 1 1 1
Table 2.11: Filling in the expanded truth table according to the refined algorithm
A
1
A
2
A
3
A
1
A
2
A
3
A
1
A
2
A
3
P
1
P
2
P
3
P
1
P
2
P
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
1 1 0
0 1 1
1 0 0
1 0 1
0 1 0
1 1 1
0 0 0
0 0 1
1 0 0
0 1 1
1 1 0
1 1 1
0 1 0
1 0 1
0 0 1
0 0 0
1 0 0
0 1 0
1 1 1
1 1 0
0 1 1
1 0 1
0 1 1
0 1 0
1 0 0
0 0 0
1 0 1
1 1 0
0 0 1
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
1 1 1
2 2 2
2 2 2 1 1 1
we find their subsequent control functions: f .A
2
; A
3
/ D A
2
A
3
, f .A
1
1
; A
1
3
/ D A
1
1
, f .A
2
1
; A
2
2
/ D
A
2
1
C A
2
1
A
2
2
, f .P
2
1
; P
2
3
/ D P
2
1
C P
2
1
P
2
3
, and f .P
1
2
; P
1
3
/ D P
1
2
. e circuit hence looks like
:
(2.7)
Note that the gate cost of 2w 1 D 5 is lower than the gate costs of 9 in both Sections 2.3
and 2.4. Noteworthy is the automatic V-shape of the positions of the five symbols in the
schematic (2.7).
If we apply the same procedure to each of the 4! = 24 circuits of width w D 2, then some-
times one or more of the three control functions equals 0. is means that one or more of the
44 2. BOTTOM
three controlled NOTs is a never-applied NOT gate and is thus in fact absent, such that there is a
total of less than three gates. is fact yields a statistical distribution of gate costs ranging from 0
to L D 2w 1 D 3. e average gate cost turns out to be about 1.9. An example for w D 2 is
the so-called SWAP gate. It swaps two bits: the first output bit equals the second input bit and
the second output bit equals the first input bit:
P
1
D A
2
P
2
D A
1
:
Its truth table is given in Table 2.12; its circuit symbol is
:
We find an L D 3 decomposition consisting of three controlled NOTs:
:
Table 2.12: Truth table of the SWAP function
A
1
A
2
P
1
P
2
0 0
0 1
1 0
1 1
0 0
1 0
0 1
1 1
When we apply the same procedure to each of the 8! = 40,320 circuits of width w D 3,
then we obtain a statistical distribution of gate costs ranging from 0 to L D 2w 1 D 5. e
average gate cost turns out to be about 4.4. is number is substantially smaller than 6.6, i.e.,
the average number found with the method of Section 2.3, and even smaller than 5.9, i.e., the
average number found with the method of Section 2.4. Table 2.13 gives an overview of the
results for w D 3 for each of the three synthesis methods.
A circuit like Figure 2.4e is known as a .2w 1/-sandwich [27]. We stress that a gate cost
2w 1 is very close to optimal. One can prove [9] that no synthesis method can guarantee better
than 2w 3. As the controlled NOTs lead to (almost) optimal decompositions, we conclude that
they form a natural library for synthesis. We stress that such a library is larger than libraries
with merely TOFFOLI gates. We recall that the latter are of the type of Figure 2.2b, i.e., a NOT
controlled by some AND function. In the synthesis approach presented here, we fully make use
of building blocks of the type of Figure 2.2a, controlled by arbitrary control functions.
2.7. EXAMPLES 45
Table 2.13: Gate cost of 3-bit circuits, according to the three synthesis methods: minimum cost,
average cost, and maximum cost
Method Min Ave Max
Primal
Dual
Refi
ned
0
0
0
6.6
5.9
4.4
13
10
5
Sometimes, for practical purposes, the library of controlled NOT gates is considered too
large. en a library consisting of only TOFFOLI gates is a possibility. In that case, we may
proceed as follows: each controlled NOT is decomposed into TOFFOLI gates by merely replacing
the control function by its Reed–Muller expansion. From (1.3), we know that such expansion
may contain up to R.w 1/ D 2
w1
terms. Better results can be obtained by one of the ESOP
expansions: only E.w 1/ terms. As an example, we consider the controlled NOT gate with
control function f D A
2
C A
3
, i.e., an OR function:
D
D
:
Indeed, its Reed–Muller expansion reads
f D A
2
˚ A
3
˚ A
2
A
3
;
whereas one of the minimal ESOP expansions is
f D A
2
˚ A
2
A
3
:
e minimal ESOP expansion thus often leads to cheaper circuits than the Reed–Muller ex-
pansion. For w D 3, the Reed–Muller approach can lead to up to R.2/ D 4 controlled NOTs,
whereas the ESOP approach is limited by E.2/ D 2. e ESOP strategy, however, also has a dis-
advantage: no efficient algorithm for finding the minimal ESOP exists if w > 6. Applying either
the Reed–Muller decomposition or a minimal ESOP expansion to the circuit (2.7) yields
;
with seven TOFFOLI gates. We conclude that any reversible circuit acting on w bits needs at most
.2w 1/E.w 1/
TOFFOLI gates [35], where the function E.n/ satisfies (1.4).
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.