12.3  Encoding Redundant Representations

In the context of an iterative multiplication-based algorithm, it often occurs that the result of a multiplication is used as the multiplier in the next iteration. In this case, if the Booth encoding of can be derived directly from the redundant representation produced by the compression tree, then need not be computed explicitly and the expensive final step of addition may be avoided.

In this section, we shall assume once again that is an -bit vector, but now the multipler to be encoded is expressed as a sum of two vectors and two carry bits,

where and are bit vectors of width and and are of width 1. As a consequence,

In particular, is a bit vector of width .

We define a sequence of coefficients as follows.

Definition 12.3.1   (gamma,delta,psi) Let , , , and . For all , let

and

and let and be defined recursively as follows: , , and for ,

and

Then for all ,

(sum-psi-lemma) Let , , and , where and are -bit vectors and and are 1-bit vectors. Then

PROOF: Let and let , , , and be as specified in Definition 12.3.1. We shall prove, by induction, that for ,

Assume that the statement holds for some . Then

Note that and therefore, as a consequence of Definition 12.3.1, . Thus,

It is not obvious that the lie within the range required by Theorem 12.1.

(psi-bnd) Let , , let and be -bit vectors, and let and be 1-bit vectors. Then for , .

PROOF: Let and let , , , and be as specified in Definition 12.3.1. Then

where and are functions of , , and . Thus, we may express as a function of , , , and . The inequality may then be trivially verified for each of the possible sets of values of these arguments.

We may now apply Theorem 12.1.

(redundant-booth) Let , , and , . Let be an -bit vector and let , where and are -bit vectors and and are 1-bit vectors. Then

where .

PROOF: Let , , , and be as specified in Definition 12.3.1. Since , , and hence , i.e., in Theorem 12.1. The result follows from the theorem and Lemmas 12.3.1 and 12.3.2

David Russinoff 2017-08-01