Arithmetic - Signal Processing Systems - page 596

− x 0 x 1 x W f −3 x W f −2 x W f −1 x W f

y W f − y 0 y 1 y W f −3 y W f −2 y W f −1

1

x W f y 0 x W f y 1 x W f y W f −3 x W f y W f −2 x W f y W f −1 x W f y W f

x W f −1 y 0 x W f −1 y 1 x W f −1 y 2 x W f − 1 y W f −2 x W f − 1 y W f −1 x W f −1 y W f

x 1 y 0 x 1 y 1

x 0 y 2

x 1 y 2 x 1 y 3

x 0 y 4

+

1 x 0 y 0 x 0 y 0 x 0 y 3

z −1 z 0 z 1 z 2 z 3 z 4 z 2 W f −3 z 2 W f −2 z 2 W f −1 z 2 W f

Fig. 19 Partial product array without sign-extension

of dealing with the varying word lengths in two's complement multiplication is to
sign-extend the partial results to obtain the same word length for all rows.
To avoid this excessive sign-extension it is possible to either perform the
summation from top to bottom and perform sign-extension of the partial results to
match the next row to be added. This is further elaborated in Sects. 3.2.1 and 3.2.2 .
However, if we want to be able to add the partial products in an arbitrary order using
a multi-operand adder as discussed in Sect. 2.4 , the following technique, proposed
initially by Baugh and Wooley [ 1 ] , can be used. Note that for a negative partial
product we have

− = −

1. Hence, we can replace all negative partial products
with an inverted version. Then, we need to subtract a constant value from the result,
but as there will be several constants, one from each negative partial product, we
can sum these up and form a single compensation vector to be added. When this is
applied we get the partial product array as shown in Fig. 19 .

p p

3.1.2 Reducing the Number of Rows

As discussed in Sect. 1.3.1 , it is possible to reduce the number of non-zero positions
by using a signed-digit representation. It would be possible to use e.g. a CSD
representation to obtain a minimum number of non-zeros. However, the drawback
is that the conversion from two's complement to CSD requires carry-propagation.
Furthermore, the worst case is that half of the positions are non-zero, and, hence,
one would still need to design the multiplier to deal with this case.
Instead, it is possible to derive a signed-digit representation that is not nec-
essarily minimum but has at most half of the positions being non-zero. This is
referred to modified Booth encoding [ 33 ] and is often described as being a radix-
4 signed-digit representation where the recoded digits r i ∈{− .An

alternative interpretation is a radix-2 signed-digit representation where d i d i − 1 ,

2 ,− 1 , 0 , 1 , 2 }

i ∈

{ . The logic rules for performing the modified Booth encoding

are based on the idea of finding strings of ones and replace them as 011

W f , W f − 2 , W f − 4 ,...}

... 11 =

0 1 and are illustrated in Table 2 . From this, one can see that there is at most
one non-zero digit in each pair of digits ( d 2 k d 2 k + 1 ).

100 ...