Next: Bibliography Up: Multiplication Previous: Encoding Redundant Representations   Contents

As we shall see in this section, a partitioning of our multiplier into slices of four bits instead of three leads to a decomposition

where is an encoding of the slice. While the number of terms of this sum is only 1/4 (rather than 1/3) of the width of , the range of encodings is now , and hence the value of each term is no longer guaranteed to be a power of 2 in absolute value. Consequently, a multiplier based on this radix-8 scheme generates fewer partial products than a radix-4 multiplier, but the computation of each partial product is more complex. In particular, a partial product corresponding to an encoding requires the computation of , and therefore a full addition.

The choice between radix-8 and radix-4 multiplication is generally decided by the timing details of a hardware design. In a typical implementation, the partial products are computed in one clock and the compression tree is executed in the next. If there is sufficient time during the first clock to perform the addition required for radix-8 encoding (which is more likely to be the case, for example, for a low-precision operation), then this scheme is feasible. Since most of the silicon area allocated to a multiplier is associated with the compression tree, the resulting reduction in the number of partial products may represent a significant gain in efficiency.

For the purpose of this analysis, which is otherwise quite similar to that of Section 7.1, we shall assume that and are bit vectors of widths and , respectively. The multiplier is now partitioned into 3-bit slices, , , and encoded as follows.

Definition 7.4.1   (eta) For and ,

The proof of the following identity is essentially the same as that of Lemma 7.1.1.

(sum-eta-lemma) Let , , and let be a bit vector of width . Then

PROOF: We shall prove, by induction, that for ,

where . The claim is trivial for . Assuming that it holds for some , we have
 +- + +- ++- ++- +

which completes the induction. In particular, substituting for , we have

The partial products are computed with an 9-1 multiplexer.

Definition 7.4.2   (bmux8) Let , , let be a bit vector of width , and let satisfy . Then

Definition 7.4.3   (pp8) Let , , and , . Let be a bit vector of width and let satisfy for . Then for , the radix-8 partial product with respect to and for the sequence is

where

and .

Once again, our theorem is formulated as generally as possible, although in this case, we shall use it only once, in order to establish Corollary 7.4.2.

(booth8-thm) Let , , and , . Let be a bit vector of width and let satisfy for . Then

where and

PROOF: Let . After a trivial reformulation of Definition 7.4.2, we have

Thus, the left-hand side of the conclusion of the theorem is

We first consider the constant terms of this sum:

Next, we observe that the final term of the sum may be rewritten as

Thus, we have

(booth8-corollary) Let , , and , . Let and be bit vectors of widths and , respectively. Then

where .

PROOF: Since ,

i.e., in Theorem 7.2. The result follows from the theorem and Lemma 7.4.1

Next: Bibliography Up: Multiplication Previous: Encoding Redundant Representations   Contents
David Russinoff 2007-01-02