12  Multiplication

While the RTL implementation of integer multiplication is more complex than that of integer addition, the extended problem of floating-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 = \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 11.4. 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.

David Russinoff 2017-08-01