Arithmetic - Signal Processing Systems - page 603

a b c

>>3 >>5

>>3 >>5 >>8

>>5 >>3

00 10100 ¯ 1using( a ) no sharing, ( b ) sharing of
the subexpression 100 1, and ( c ) sharing of the subexpression 10001

Fig. 27 Constant multiplication with 231 / 256 = 1 .

bits that are zero, all the corresponding partial product bits will also be zero, and,
hence, these are not required to be added. To obtain more zero positions, the use of
a minimum signed digit representation such as CSD is useful.
It is also possible to utilize potential redundancy in the computations to further
reduce the complexity. How this is done in detail depends on which type of addition
is assumed to the basic operation. As both addition and subtraction have the same
complexity, we will refer to both as addition. In the following we will assume carry-
propagation addition, i.e., two input and one output, realized in any way discussed
in Sect. 2 . Furthermore, for ease of exposition, we will assume that the standard
sign-extension is used. For carry-save addition we refer to [ 17 ] .
Consider a signed-digit representation of a multiplier coefficient X such as shown
in ( 1 ) with x i

. Each non-zero position will produce a partial result row
and these partial result rows can be added in an arbitrary order. Now, if the same
pattern of non-zero positions, called subexpression, occurs in more than one position
of the representation, we only need to compute the corresponding partial result once
and use it for all the instances where it is required. Figure 27 a , b show examples of
multiplication with the constant 231

∈{− 1 , 0 , 1 }

00 10100 1 with and without utilizing
redundancy, respectively. In this case we extract the subexpression 100 1, but we
might just as well have chosen 10001 and subtracted one of the subexpressions as
shown in Fig. 27 c .
This can be performed is a systematic way as described below. However, first
we note that if we multiply the same data with several constant coefficients, as
in a transposed direct form FIR filter [ 56 ] , the different coefficients can share
subexpressions. Hence, the systematic way is as follows [ 20 , 43 ] :

/ 256 = 1 .

1. Represent the coefficients in a given representation.
2. For each coefficient find and count possible subexpressions. A subexpression is
characterized by the difference in non-zero position and if the non-zeros have the
same or opposite signs.