46 2. BOTTOM
2.8 VARIABLE ORDERING
For each of the three synthesis methods, a lot of fine-tunings exist in order to improve their
performance, i.e., to further reduce the resulting gate costs. For example, for the primal syn-
thesis method, we may apply eorem 1.3 instead of eorem 1.2. We thus can reposition the
controlled circuits, i.e., substitute decomposition
(2.8)
by decomposition
:
At each of the w 1 steps of the iterative procedure, we can choose the cheaper of the two
options.
We can also replace (2.8) by
;
where the bottom bit A
w
takes over the role of the top bit A
1
. In fact, at each step of the iterative
procedure, we can choose which of the remainig bits will act as a controlling/controlled bit.
An interesting optimization of both the primal and the dual synthesis methods consists
of applying the following identities:
B A
A
1
B
A
B
1
A
B
D D
A
BA
1
B
AB
1
D D
;
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.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.