Page 492 - DSP Integrated Circuits

11.5 Bit-Parallel Arithmetic 477

The number of shift-and-add cycles
can be reduced for fixed coefficients if
the coefficients are represented by
CSDC. On average the number of cycles
reduced to W^/3, with worst case is
W<£/2. However, it may be difficult to
use PEs with variable execution time.

11.5.4 Booth's Algorithm

Most modern general-purpose proces-
sors—for example, the MIPS R4000™—
contain a dedicated processor for han-
Figure 11.7 Block diagram for a shift-
dling integer arithmetic operations.
Multiplication in such integer proces- and-add-multiplier
sors, as well as in floating-point pro-
cessors, usually uses some version of Booth's modified receding algorithm.
Consider the multiplication involving a 16-bit two's-complement number. The
multiplicand can be rewritten

Since XIQ = 0, the second and third terms can be rewritten

Finally, we get

The multiplication x • y can now be written

Thus, three bits at a time from one of the input operands, x, is used to recede
the other input operand, y, into partial products that are added (subtracted) to
form the result. The value of the term in parentheses is either 0, ±1, or ±2. Hence,
the number of partial products generated is reduced and they are simple multiples
of the input operand (-2y, -y, 0, y, 2y). A partial product of the type ±2y (i.e., a mul-
tiplication by a factor two) is achieved with a left, or right, shift.