Page 491 - DSP Integrated Circuits

476 Chapter 11 Processing Elements

array multipliers. Of these types, the array multiplier takes up the least amount of
area, but it is also the slowest with a latency proportional to O(W^) where W^ is
the word length of the operands. The parallel (tree-based) multipliers have laten-
cies of O(log2(W^)), but they take up more area due to more irregular wiring.

11.5.3 Shift-and-Add Multiplication
A sequential multiplier is obtained by generating the bit-products row-wise. Con-
sider the multiplication of two numbers, y = a • x. Using two's-complement repre-
sentation we have

The multiplication can be performed by generating the partial products (for
example, rowwise) as illustrated in Figure 11.6. A shift-and-add multiplier is
obtained by using only one bit-parallel adder and successively adding the partial
products row or columnwise. Figure 11.7 shows the block diagram of a shift-and-
add multiplier in which the partial products are implemented using a multiplexer
instead of AND gates.
Addition starts with the partial products corresponding to the LSB. If X{ = 0,
zero is accumulated via the multiplexer, while if JCj = 1, then the partial product,
g
a • Xi, is accumulated. Starting with bit xyf d_i, the bit-products (a • ^w^-l) i added
to the initially cleared accumulator register and the sum is shifted one step to the
right, which corresponds to division by 2.
s
Next, the row of bit-products (a • x\v d-2) * added to the accumulator register.
Upon reaching XQ, the bit-products (a • XQ) are subtracted from the value in the accu-
mulator. In practice it is more common to add the bit-products (-a • XQ) instead.
2
A multiplication between two W^-bit numbers will require W^ AND operations
and W^-l add and shift operations. The result will be a (Wd+W c—l)-bit number.
Notice that division by 2, accomplished by shifting a two's-complement num-
ber one step to the right, requires that the sign bit be copied. For example, (0.5)io =
(1.100)2c- Shifting one step to the right and copying the sign bit gives (l.lW^c =
(0.25)io-

Figure 11.6 Sequential forming of partial bit-products