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,