Arithmetic - Signal Processing Systems - page 582

Fig. 1 ( a ) Full adder: truth
table. ( b ) Full adder: symbol

a

a i b i d i s i c i
00000
00110
01010
01101
10010
10101
11001
11111

b

a i b i d i

FA

c i s i

1.3.1 Signed-Digit Representation

In a signed-digit (SD) number representation, the digits may have either positive
or negative sign. For a radix-2 representation we have x i ∈{−

1 , 0 , 1 } .Using W f

fractional bits as in ( 1 ) the range of X is − 1 + Q ≤ X ≤ 1 − Q . A number may

now have more than one representation. Consider the number 0 . 25 10 which can be

1 1 SD ,where ¯ 1isusedtodenote written as 1.

In some applications as, for instance, digital filters [ 30 ] , FFTs [ 4 ] andDCTs
[ 28 ] as well as general DSP algorithms [ 44 ] , it is of interest to find a signed-
digit representation with a minimum number of non-zero positions to simplify
the corresponding multiplication (see Sect. 3.5 ) . This is referred to as a minimum
signed-digit (MSD) representation. However, in general it is non-trivial to determine
if a representation is minimum. A specific minimum signed-digit representation is
obtained if the constraint x i x i + 1 =

. 01 SD or . −

i is imposed. The resulting representation is
called canonic signed-digit (CSD) representation and is apart from being minimum
also unique (as the name indicates).

0 ,∀

1.3.2 Carry-Save Representation

The carry-save representation stems from the ripple-carry adder, which will be
further discussed in Sect. 2.1 . Instead of propagating the carries in the addition, these
bits are stored and the data is represented using two vectors. This also leaves an
additional input of the full adder cells unused, so it is possible to add three vectors.
A full adder cell is illustrated in Fig. 1 b and the truth table is given in Fig. 1 a . From
this we can see that

s i = parity ( a i ⊕ b i ⊕ d i )= a i ⊕ b i ⊕ d i (3)

where ⊕ is the exclusive-OR operation, and

= ( , , )= + + .

c i majority a i b i d i a i b i a i d i b i d i (4)