This section considers multipliers that can perform two’s complement multiplication in time *O*(*W*) using regular structures, including multiplication with sign extension (derived from Horner’s rule) and Baugh-Wooley multiplication [9]. Two regular implementation styles, carry-ripple and and carry-save array, are introduced.

It has been proved that multiplications cannot be performed in a time smaller than *O*(*log*_{2}*W*). Such a bound is attainable by the *binary-tree* and *Wallace-tree* multipliers (see Appendix E) [10]. However, their corresponding architectures are very irregular.

Let the multiplicand and multiplier be *A* and *B*:

where −1 < *A*, *B* < 1 and the case when both *A* and *B* is equal to −1 is excluded. The value of their product *P* = *A* × *B* is given by:

where the radix point is to the right of the msb *p*_{2w−2}. Since the product of 2 numbers within [−1, 1) is also in this range, all higher order bits to the left of bit-position 2*W* − 2 in the result are ignored.

In constant wordlength multiplication, the *W* − 1 lower order bits in the product *P* are discarded, and the product is denoted as *X* ⇐ *P* = *A* × *B*, where

The product *X* is used when a constant wordlength multiplier ...

Start Free Trial

No credit card required