Page 483 - DSP Integrated Circuits

468 Chapter 11 Processing Elements

number representations are time consuming. In this section we will discuss three
such representations:
Signed-digit code
Canonic signed digit code
On-line arithmetic
Signed-digit codes (SDCs) differ from the binary representations, just dis-
cussed, since each digit is allowed to have a sign. Typically digits can take one of
three values: -1, 0, or +1.
One advantage of these number systems is that long carry propagations can
be eliminated in additions and subtractions. Another advantage is that the
required number of addition/subtraction cycles can be reduced in some multiplica-
tion algorithms.
On-line arithmetic refers to redundant number systems that allow arithmetic
operations to be performed by using the most significant bit first. These properties
can be exploited to reduce the latency inherent in long sequential computations
and operations involving very long word lengths.

11.3.1 Signed-Digit Code
w +1
A number, x, in the range — 2 + Q <x <2 — Q, where Q = 2~ ^ , is represented in
signed digit code by

For example, the decimal number (15/32)io = (0.01111)2c can be represented
by (O.lOOO-l)sDC or by (O.Ollll)sDO The decimal number (-15/32) 10 = (1.10001) 2 c
or
can be represented by (O.-lOOOl)sDC (O.O-l-l-l-l)gDC-
A minimal SDC number has a minimum number of nonzero digits. Obviously,
the signed digit code is not unique. This causes problems when a number shall be
quantized (rounded or truncated). In practice, a signed digit code is therefore con-
verted to a "conventional" representation before it is quantized. In a conventional
number system the numbers are inherently ordered according to the values. It is
therefore simple to compare the magnitude of two numbers or to round a number
to the "closest" number with appropriate word length. In practice it may be too
costly to convert SDC numbers for the necessary quantization and overflow checks
in every recursive loop. However, the SDC has an advantage that the time taken
for addition of two numbers is independent of the word length.
Notice also that the quantization step for SDC is not equidistant. The resolu-
tion is higher for small numbers. The maximum and minimum step size depend on
the number of nonzero bits and the word length.

EXAMPLE 11.4
Show that carry propagation can be avoided when adding two numbers in SDC rep-
resentation using the algorithm described in Table 11.1 [40]. Assume for simplicity
that the two numbers are (l-ll-l)sDC = (5)io and (O-lll)sDC = (-l)io- The sum is