next up previous contents
Next: Radix-4 Booth Encoding Up: Implementation of Elementary Operations Previous: Trailing One Prediction   Contents


Multiplication

While the RTL implementation of integer multiplication is more complex than that of integer addition, the extended problem of floation-point multiplication does not present any significant difficulties that have not already been addressed in earlier chapters. The focus of this chapter, therefore, is the multiplication of integers.

Let $ x$ and $ y$ be natural numbers, which we shall call the multiplicand and the multiplier, respectively. A natural approach to the computation of $ x \cdot y$ begins with the bit-wise decomposition of the multiplier,

$\displaystyle y = \verb!b!\beta_{w-1}\cdots \beta_0 = \sum_{i=0}^{w-1}2^i\beta_i,$

where $ 0 \leq y < 2^w$ and for $ i=0,\ldots,w-1$ , $ \beta_i = y[i]$ . The product may then be computed as

$\displaystyle xy = \sum_{i=0}^{w-1}2^i\beta_ix.$

Thus, the computation is reduced to the summation of at most $ w$ nonzero terms, called partial products, each of which is derived by an appropriate shift of $ x$ . In practice, this summation is performed with the use of a tree of compressors similar to the 3:2 compressor shown in Figure 6.1. It is clear that two such compressors may be combined to form a 4:2 compressor, and that $ 2^{k-2}$ 4:2 compressors may be used to reduce a sum of $ 2^k$ terms to $ 2^{k-1}$ in constant time. Consequently, the hardware needed to compress $ w$ terms to two grows linearly with $ w$ , and the required time grows logarithmically.

Naturally, any reduction in the number of partial products generated in a multiplication would tend to reduce the latency of the operation. Booth encoding [BOO51] is based on the observation that if we allow $ -1$ , along with 0 and 1, as a value of the coefficient $ \beta_i$ in the above expression for $ y$ , then the representation is no longer unique. Thus, we may seek to minimize the number of nonzero coefficients and consequently the number of partial products in the expression for $ xy$ , at the expense of introducing a negation along with the shift of $ x$ in the case $ \beta_i = -1$ .

In the following section, we shall present a refinement of Booth's original algorithm known as the radix-4 modified Booth algorithm [KOR93], which limits the number of partial products to half the multiplier width. Each of the three subsequent sections contains a variant of this algorithm.


Subsections
next up previous contents
Next: Radix-4 Booth Encoding Up: Implementation of Elementary Operations Previous: Trailing One Prediction   Contents
David Russinoff 2007-01-02