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
The definition of involves a pair of mutually recursive auxiliary functions.
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
Thus, we may assume that
The desired result now follows from Lemma 12.2.1 and Definitions 12.2.1 and 12.2.2.
Lemma 12.2.1 is also needed for the following.
PROOF: Let , , and . First note that , for if , then
Thus, our multiplier may be statically encoded as a vector of width ,
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.
PROOF: This follows from Theorem 12.1, Corollary 12.2.2, and Lemma 12.2.3.
David Russinoff 2017-08-01