Page 484 - DSP Integrated Circuits

11.3 Redundant Number Systems 469

K r x n n n i A 1 A_1 A_1 1 1 I t 1 1
iyi° yi i
xi+iyt+i — Neither is —1 At least one is —1 Neither is -1 At least one is -1 — — —
Ci 0 1 0 0 -1 0 1 -1
zi 0 -1 1 -1 1 0 0 0
Table 11.1 Rules for adding SDC numbers

Apply the rules in Table 11.1
i 0 1 2 3
from right to left. The carries have
been shifted one step to the left in *i 1 -1 1 -1
order to align the digits for the final yi 0 -1 1 1
summation. The result of the addition c 0 -1 1 0 —
is (OlOO)sDC = (4)io; see Table 11.2. i+i 1
Notice that all of the intermediate *i 0 0 0
terms zi and carries can be generated s i 0 1 0 0
in parallel by considering two succes-
Table 11.2 Obtained result
sive sets of digits.

11.3.2 Canonic Signed Digit Code

A canonic signed digit code (CSDC) is a special case of a signed digit code in that
each number has a unique number representation. CSDC has some interesting
properties that make it useful in the mechanization of multiplication. A number, x,
W
in the range -4/3 + Q < x < 4/3-Q, where Q = 2T , W = W d-l for W d = odd, and
W = Wrf-2, for Wd = even, is represented in canonic signed digit code by

where no two consecutive digits are nonzero— i.e.,

For example, the number (15/32)i 0 is represented by (O.lOOO-l)csDC an d
(-15/32)io by (O.-lOOOl)csDO Furthermore, the CSDC has a minimum number of
nonzero digits. It can be shown that the average number of nonzero digits is

Hence, for moderately large W d the average number of nonzero bits is about
W^/3 as opposed to W^/2 in the usual (nonsigned) binary representations.

Conversion of Two's-Complement to CSDC Numbers
The conversion from two's-complement representation to CSDC is straightfor-
ward. It is based on the identity