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.
The proof of the following identity is essentially the same as that of Lemma 7.1.1.
PROOF: We shall prove, by induction, that for ,
where . The claim is trivial for . Assuming that it holds for some , we have
The partial products are computed with an 9-1 multiplexer.
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.
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:
Thus, we have
PROOF: Since ,
i.e., in Theorem 7.2. The result follows from the theorem and Lemma 7.4.1.