Page 493 - DSP Integrated Circuits

478 Chapter 11 Processing Elements

Booth's algorithm reduces the number of additions/subtractions cycles to W^/2
= 8, which is only half that required in the ordinary shift-and-add algorithm.
Notice that the reduction of the number of cycles directly corresponds to a reduc-
tion in the power consumption. Typically, decoding, shifting, and addition are pipe-
lined in order to achieve higher throughput. Typically, an Ilxl6-bit multiplier can
be operated with a cycle time of about 20 ns and requiring about 4200 devices and
2
about 0.6 mm using a standard 0.8-um CMOS process. Booth's algorithm is also
suitable for bit-serial or digit-serial implementation.

11.5.5 Tree-Based Multipliers
In order to simplify the illustra-
tion of a multiplication algorithm
we will sometimes use the short-
hand version of the bit-products
shown in Figure 11.8 instead of
the one shown in Figure 11.5.
In tree-based multipliers the
bit-products are added using full-
adders. A full-adder can be consid-
ered as a counter, denoted (3,
2)-counter, that adds three inputs
and forms a two-bit result. The
Figure 11.8 Simplified notation for multiplication
output equals the number of Is in
the inputs. A half-adder is denoted
(2,2)-counter.
In 1964 Wallace showed that
a tree structure of such counters is
an efficient method, O(log2(W^)),
to add the bit-products. Figure
11.9 illustrates how the number of
bit-products can be accumulated
successively.
In the first stage, eight
(3,2)-counters and three
(2,2)-counters are used. The largest
number of partial products in any
column is reduced to four. In the
second stage, we need, as shown in
Figure 11.10, five (3, 2)-counters
and three (2, 2)-counters to reduce
the largest number of products to
three, as shown in Figure 11.10. In
the third stage, we need three Figure 11.9 Reduction of the number of partial
(3,2)-counters and three products
(2,2)-counters to reduce the largest
number of products to two.
Finally in the fourth stage, an RCA or a CLA can be used to obtain the prod-
uct. For a 6x6 multiplier 13 (3,2)-counters and nine (2, 2)-counters are needed, not
counting the final carry—look—ahead adder.