As a notational convenience, we shall assume that and are bit vectors of widths and , respectively. Our objective is an efficient computation of as a sum of partial products. Conceptually, the multiplier is partitioned into 2-bit slices, , . Corresponding to each slice, we define an integer encoding in the range .

Definition 12.1.1   (theta) For and ,

(sum-theta-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

Since , Lemma 12.1.1 expresses as a sum of at most nonzero terms, each with absolute value a power of 2. Our goal is to compute

Each term of this sum will correspond to a partial product, which is constructed by means of a 5-to-1 multiplexer.

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

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

where

and .

Our main theorem is formulated as generally as possible so that it may be applied in other contexts.

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

where and

PROOF: Let . A straightforward reformulation of Definition 12.1.2 yields

In order to understand Definition 12.1.3, note that whenever , we must correct for the discrepancy between and by (1) adding and (2) subtracting . The first is achieved simply by the insertion of at index of . The second may be viewed as a two-step process. First, we insert 1's at indices and of . In the final sum described below, the cumulative result of this is merely a carry-out to a high-order bit (index ), which may ultimately be ignored. But the motivation for this step is that the at index may now be subtracted off in the case . Thus, in the second step, we replace that 1 with .

This argument underlies the present proof. By Definition 12.1.3, 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

In our first application of Theorem 12.1, we substitute for and invoke Corollary 12.1.1.

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

where .

PROOF: Since ,

i.e., in Theorem 12.1. The result follows from the theorem and Lemma 12.1.1

Note that computing a product as an application of Corollary 12.1.2 requires injecting an extra bit (with value ) into the partial product array. This requirement can be eliminated through a minor modification of the low-order entry :

(booth4-corollary-2) Let , , and , . Let and be bit vectors of widths and , respectively. for , lLet be defined just as except that

-

Then

where .

PROOF: The only difference between and is that

while

Thus,

and

David Russinoff 2017-08-01