2.8. VARIABLE ORDERING 47
corresponding to the matrix identities
A
B
D
A
A
I
A
1
B
D
B
B
B
1
A
I
D
I
BA
1
A
A
D
AB
1
I
B
B
;
where I again stands for the 2
w1
2
w1
unit matrix. ese templates do not lower the number
of final controlled NOTs, but lower the number of controlling bits.
In Figure 2.4b, we have started the decomposition of Figure 2.4a by applying two con-
trolled NOTs controlling the first bit. en, in Figure 2.4c, we have applied two control gates
controlling the second bit, and so on. ere really is no reason to follow this downward order.
We may equally well apply any other order. is will lead to wŠ (usually different) syntheses of
the same truth table. For example,
shows the result of applying the upward order to Table 2.2a. In contrast to circuit (2.7), the five
symbols in the present circuit are not located in V-shape, but in ƒ-shape. e gate cost
of the two hardware implementations is the same: five units.
For a particular synthesis problem, the wŠ synthesis solutions may have different hardware
cost. On average, however, solving all .2
w
/Š synthesis problems of width w, with application of
the optimal among the wŠ wire orders instead of a single constant wire order, gives a moderate
cost gain. For example, synthesizing all 24 circuits of width 2, trying both wire orderings, yields
cascades with average gate cost of about 1.8, only 4% better than the 1.9 result in the previous
section. Synthesizing all 40,320 circuits of width 3, trying all six wire orderings, yields cascades
with average gate cost of about 3.9, i.e., 11% better than the 4.4 result in the previous section.
Variable ordering and post-synthesis optimizations are automated by RevKit [36, 37], an
open-source algebra tool for synthesizing reversible circuits.