Page 510 - DSP Integrated Circuits

LI.9 Minimum Number of Basic Operations 495

11.9.2 Multiple-Constant Multiplications
Most DSP algorithms involve multiplication of
one variable with several constants as shown in
Figure 11.31 or the transposed version shown in
Figure 11.32. Such composite operations can be
significantly simplified by eliminating common
subexpressions as illustrated in Figure 11.33
[321. The aim is to reduce the number of basic
operations (i.e., add/sub-and-shift operations), by
factoring out common factors in the coefficients
c;. By first generating a set of common subex-
pressions that in the next step are multiplied with simple coefficients or
added/subtracted to generate new subexpressions, the overall complexity of the
implementation can be reduced.
For multiple-constant multiplication
with many coefficients (for example, for
long FIR filters), the average increase of the
number of adders/subtracters approaches
one for an increase of the length of the filter
by one. This is due to the fact that most sub-
expressions have already been generated
and only a single addition/subtraction is Figure 11.32 Transposed multiple-
needed to generate another coefficient. constant multiplication
In a particular case, a more irregular
strategy for generating common subexpres-
sions than the one shown in Figure 11.33 may be more efficient. Note, however, that
the wiring may become very complex and irregular and in practice this may signifi-
cantly offset the savings in adders/subtracters and make the layout and transistor
sizing very time consuming.
The resulting composite operation can
either be implemented using bit-parallel or
bit-serial arithmetic. In the former case,
the number of adds/subs are the most
important, since shifts can be imple-
mented virtually free of cost by fixed wir-
ing. In the bit-serial case, both the number
of adds/subs and shifts are important,
since they correspond to hardware that
consumes chip area and power.
The problem of finding optimal solu-
tions to the multiple-constant multiplica- Figure 11.33 Exploiting common
tion problem is NP-complete. Heuristic subexpressions to
algorithms have therefore been derived [6, simplify a multiple-
13, 14]. Note, however, many practical constant multiplication
problems are very small and a complete
search can be performed with a reasonable execution time.