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 .
PROOF: We shall prove, by induction, that for ,
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
Our main theorem is formulated as generally as possible so that it may be applied in other contexts.
PROOF: Let . A straightforward reformulation of Definition 12.1.2 yields
This argument underlies the present proof. By Definition 12.1.3, the left-hand side of the conclusion of the theorem is
In our first application of Theorem 12.1, we substitute for and invoke Corollary 12.1.1.
PROOF: Since ,
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 :
PROOF: The only difference between and is that
David Russinoff 2017-08-01