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,
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.