# 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 and be natural numbers, which we shall call the multiplicand and the multiplier, respectively. A natural approach to the computation of begins with the bit-wise decomposition of the multiplier,

where and for , . The product may then be computed as

Thus, the computation is reduced to the summation of at most nonzero terms, called partial products, each of which is derived by an appropriate shift of . 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 4:2 compressors may be used to reduce a sum of terms to in constant time. Consequently, the hardware needed to compress terms to two grows linearly with , 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 , along with 0 and 1, as a value of the coefficient in the above expression for , 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 , at the expense of introducing a negation along with the shift of in the case .

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
David Russinoff 2017-08-01