Arithmetic - Signal Processing Systems - page 601

Fig. 24 Operation on bits in
a dot diagram with ( a )full
adder and ( b ) half adder

a b

Inputs

Result

a b c

Stage 1 Stage 1

Stage 1

Stage 2 Stage 2 Stage 2

Stage 3 3 Stage 3

Stage 4 4 Stage 4

Fig. 25 Reduction trees for a 6 × 6-bits multiplier: ( a ) Wallace [ 53 ] , ( b ) Dadda [ 7 ] , and

( c ) Reduced area [ 2 ]

Tabl e 3 Complexity of the three reduction trees in Fig. 25
Tree structure Full adders Half adders VMA length

Wallace [ 53 ] 16 13 8

Dadda [ 7 ] 15 5 10

Reduced area [ 2 ] 8 5 7

To illustrate the operation of the reduction tree approaches we use dot diagrams,
where each dot corresponds to a bit (partial product) to be added. Bits with the same
weight are in the same column and bits in adjacent columns have one position higher
or lower weight, with higher weights to the left. The bits are manipulated by either
full or half adders. The operation of these are illustrated in Fig. 24 .
The reduction schemes are exemplified based on an unsigned 6 6-bits multi-

plication in Fig. 25 . The complexity results are summarized in Table 3 . It should be
noted that the positioning of the results in the next level is done based on ease of
illustration. From a functional point of view this step is arbitrary, but it is possible
to optimize the timing by carefully utilizing different delays of the sum and carry
outputs of the adder cells [ 38 ] . Furthermore, it is possible to reduce the power
consumption by optimizing the interconnect ordering [ 40 ] .
The reduction trees in Fig. 25 does not provide any regularity. This means that
the routing is complicated and may become the limiting factor in an implementation.
Reduction structures that provide a more regular routing, but still a small number of
stages, include the Overturned stairs reduction tree [ 35 ] and the HPM tree [ 12 ] .

×