Page 508 - DSP Integrated Circuits

11.9 Minimum Number of Basic Operations 493

For sake of simplicity we
will only discuss multiplication
with integers. Hence, n > 0. Mul-
tiplication with the correspond-
ing fractional coefficient is easily
obtained from the same graph
and we need only to consider
positive numbers, since the neg-
Figure 11.27 Graphs with one and two
ative counterparts can be
adders/subtracters multipliers
obtained by changing the sign of
the branch weights. As men-
tioned before, we do not differentiate between the two since adders and subtrac-
ters are assumed to have equal costs.
Figures 11.27 and 11.28 show all possible graphs with up to three adders
or subtracters. There is only one graph with a single adder/subtractor and two
graphs with two adders/subtracters. There are eight different graphs with
three adders/subtracters and 32 different graphs with four adders/subtrac-
tors. The number of possible graphs grows rapidly with the number of
adders/subtracters.
Obviously there must exist a representation that yields a minimum number of
elementary operations (add/subtract-shift), but this number may not be unique.
Heuristic algorithms for determining the best representation for a given set of
basic operations are given in [6, 14, 23]. Note that for some numbers the CSDC
representation is still the best.
All numbers in the range [-4096, 4095], which correspond to a 12-bit word
length, and, of course, many outside this range can be realized with only four
adder/subtractors.

Figure 11.28 Graphs for three adder multipliers