Page 507 - DSP Integrated Circuits

492 Chapter 11 Processing Elements

are replaced by elementary operations. The most interesting cases are when the
multiplication is realized by only using the following operations:
Addition only
Addition and subtraction
Addition and shift
Addition and subtraction and shift
As before, we will not differentiate between addition and subtraction, since
their implementation cost is roughly the same. A shift operation corresponds to a
multiplication with a power-of-two. A shift operation can be implemented in bit-
parallel arithmetic either by a barrel shifter if the number of shifts varies or sim-
ply by a skewed wiring if the number of shifts is fixed. In bit-serial arithmetic a
shift operation corresponds to a cascade of D flip-flops. Thus, in parallel arithmetic
a fixed amount of shift may have almost negligible cost while both the chip area
and power consumption are significant in bit-serial arithmetic.
In this section we will discuss various schemes to reduce the number of
add/sub-and-shift operations. We will mainly discuss the bit-serial case with inte-
ger coefficients, since the case with fractional bits can be obtained by a simple
modification of the algorithms. Further, the bit-parallel case is almost the same as
the bit-serial case.

11.9.1 Multiplication with a Fixed Coefficient
As discussed before, a multiplication with a
fixed coefficient (multiplicand) can be simpli-
fied if the latter is expressed in canonic signed
digit code (CSDC). The number of add/sub
operations equals the number of nonzero digits
in the multiplicand minus one. However, the
number of adders/subtractors required by this
approach is not always a minimum if the multi-
plicand is larger than 44. For example, the
number (45)io = (10-10-10!)CSDC re( u res three
l i
additions (subtractions) using the technique
discussed in section 11.8.1. Another more effi-
cient alternative representation is (45)io =
3
2
(2 +1)(2 + 1), which requires only two addi-
tions. Hence, it is of great interest to find the
best algorithm to perform the multiplication
with fewest basic operations. Figure 11.26 Alternative graphs
To this purpose it is useful to use the representing
graphs such as those in Figure 11.26 to
describe the various ways in which a multiplicand can be represented. The left-
most and rightmost nodes are the initial node and terminal node, respectively.
n
They are connected with branches with associated binary weights—i.e., ±2 .
These weights correspond to shift operations. Each intermediate node, which rep-
resents an addition or subtraction, must have two input branches and at least one
output branch. The uppermost graph describes the CSDC representation while the
other two describe the more efficient algorithms.