Page 485 - DSP Integrated Circuits

470 Chapter 11 Processing Elements

A string of Is in the two's-complement representation of a number can be
replaced by a 1, followed by Os, followed by a —1. For example, (0.011111)2c =
(3l/64)io corresponds to (O.lOOOO-l)csDC = ((32-l)/64)i 0.
A two's-complement number can be converted to CSDC in an iterative manner
by the following algorithm. Strings of consecutive Is separated by Os are first iden-
tified. A string of two or more Is,— for example, (...00111100...)2c, is converted into
(...01000-100...)CSDO Isolated Is are left unchanged. After this first step, the entire
string is reexamined and pairs of type (-1,1) are changed to (0, -1) and triplets of type
(0,1, 1) are changed to (1, 0, -1). This process is repeated until no two adjacent non-
zero digits remain. For example, (0.110101101101) 2 c = (1.00-10-100-10-101) C SDC-
An alternative algorithm for converting two's-complement numbers into CSDC
that is suitable for hardware implementation is given in [17, 33].

Conversion of SDC to Two's-Complement Numbers
A conversion of an SDC number into a representation where the numbers are
ordered according to size is often necessary. For example, in a recursive algorithm
the word length increases and must be quantized (rounded or truncated) and
checked for overflow. The standard method of converting an SDC number into
two's-complement representation is to separate the SDC number into two parts.
One part holds the digits that are either 0 or 1 and the other part the -1 digits.
Finally, these two numbers are subtracted. This carry propagation in this opera-
tion causes a significant delay. Notice that adding (subtracting) a two's-comple-
ment number to an SDC number can be performed directly and does not require
any conversion.

11.3.3 On-Line Arithmetic
On-line arithmetic refers to number systems with the property that it is possible
to compute the ith digit of the result, using only the first (i+8)th digits, where 8 is a
small positive constant [42]. Thus, after that the first 8 digits have become avail-
able, the first digit of the result can be computed and the following digits can suc-
cessively be computed for each new digits of the operands become available. Thus,
the latency corresponds to 8 digits. This property can be favorable in recursive
algorithms using numbers with very long word lengths.
Obviously, the signed digit code, just discussed can be used for on-line addi-
tion and subtraction since the carry propagation is only one position, 5=1, regard-
less of the word length. Multiplication and division can also be computed on-line
using SDC. A more efficient and faster method of converting an SDC number into
two's-complement representation that even allows on-line operations is described
in [15].

11.4 RESIDUE NUMBER SYSTEMS

Another way of performing arithmetic operations that avoids carry propagation is
based on RNSs (residue number systems). This old Chinese technique has gained
renewed interest as the VLSI technique has become available. In fixed-point RNS
a number is represented by a set of residues obtained after an integer division by
mutual prime factors (moduli), m^ i = 1, 2, ...,p.