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,
We define a sequence of coefficients as follows.
It is not obvious that the lie within the range required by Theorem 12.1.
PROOF: Let and let , , , and be as specified in Definition 12.3.1. Then
We may now apply Theorem 12.1.
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