12.2  Statically Encoded Multiplier Arrays

In a practical implementation of the algorithm described above, although the coefficients are not actually computed arithmetically as suggested by Definition 12.1.1, some combinational logic is required to derive an encoding of each from the corresponding multiplier bits . If the value of the multiplier is known in advance, i.e., at design time, then these encoded values may be stored instead of the multiplier itself, thereby saving the time and hardware associated with the encoding logic. However, since the range of consists of 5 values, 3 bits are required for each encoding, and therefore bits in total, as compared to bits for unencoded multiplier. For a single multiplier, this is a negligible expense, but if the multiplier is to be selected from a array of vectors, then the penalty incurred by such static encoding could be a increase in the size of a large ROM.

In this chapter. we present an alternative encoding scheme that involves 4 rather than 5 encoded values, which allows 2-bit encodings and thereby eliminates any increase in space incurred by statically encoded arrays. Again we assume that the multiplicand is an -bit vector, but the bound on the multiplier is weakened, requiring only that

which implies that is a -bit vector. Under this scheme, the coefficients are replaced with the values defined below. Note that the recursive nature of this definition precludes parallel computation of the values. Consequently, this technique is not suitable for designs that require dynamic encoding.

The definition of involves a pair of mutually recursive auxiliary functions.

Definition 12.2.1   (mu, chi) For all and ,

where

Definition 12.2.2   (phi) For all and ,

where

The requirement that be limited to a set of 4 values is satisfied as an immediate consequence of the Definition 12.2.2. On the other hand, the proof that involves a nontrivial induction.

PROOF: Let and . More generally, we shall prove that for , if , then . Assuming that the claim holds for some , , and proceeding by induction, we must show that if , then .

First, suppose that . Then

and hence

Thus, we may assume that . Since

we must have and . Now, the inductive hypothesis yields . Hence,

and once again,

The desired result now follows from Lemma 12.2.1 and Definitions 12.2.1 and 12.2.2.

Corollary 12.2.2   (phi-m-1) If , then .

Lemma 12.2.1 is also needed for the following.

PROOF: Let , , and . First note that , for if , then

and in all other cases,

We shall show that for ,

The claim is trivial for . For , by induction, we have

In particular, substituting for , we have

Thus, our multiplier may be statically encoded as a vector of width ,

from which each may be readily recovered as

Applying Theorem 12.1 and invoking Corollary 12.2.2 and Lemma 12.2.3, we have the following result. Note that as a further optimization, which is not pursued here, could be replaced with a 4-to-1 multiplexer.

(static-booth) Let , , and , . Let be a bit vector of width and let satisfy . Then

where .

PROOF: This follows from Theorem 12.1, Corollary 12.2.2, and Lemma 12.2.3

David Russinoff 2017-08-01