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