Chapter  start   Previous  page  Next  page

2.6.5   Other Arithmetic Systems

There are other schemes for addition and multiplication that are useful in special circumstances. Addition of numbers using redundant binary encoding avoids carry propagation and is thus potentially very fast. Table 2.13 shows the rules for addition using an intermediate carry and sum that are added without the need for carry. For example,

    binary            decimal            redundant                  CSD                        binary                 vector      1010111               87                                      addend  + 1100101              101       +               +              augend = 10111100            = 188                                      intermediate sum                                                 intermediate carry                     =              =              sum

The redundant binary representation is not unique. We can represent 101 (decimal), for example, by (binary and CSD vector) or . As another example, 188 (decimal) can be represented by (binary), , , or (CSD vector). Redundant binary addition of binary, redundant binary, or CSD vectors does not result in a unique sum, and addition of two CSD vectors does not result in a CSD vector. Each n -bit redundant binary number requires a rather wasteful 2 n -bit binary number for storage. Thus is represented as 010010, for example (using sign magnitude). The other disadvantage of redundant binary arithmetic is the need to convert to and from binary representation.

Table 2.14 shows the (5, 3) residue number system . As an example, 11 (decimal) is represented as [1, 2] residue (5, 3) since 11R ₅  = 11 mod 5 = 1 and 11R ₃  = 11 mod 3 = 2. The size of this system is thus 3  ¥  5 = 15. We add, subtract, or multiply residue numbers using the modulus of each bit positionwithout any carry. Thus:

     4        [4, 1]              12        [2, 0]               3        [3, 0]   +  7      + [2, 1]              4       [4, 1]             ¥  4       ¥  [4, 1]   = 11      = [1, 2]            =  8      = [3, 2]            = 12      = [2, 0]

The choice of moduli determines the system size and the computing complexity. The most useful choices are relative primes (such as 3 and 5). With p prime, numbers of the form 2 p and 2 ^p   1 are particularly useful (2 ^p   1 are Mersenne's numbers ) [Waser and Flynn, 1982].

Chapter  start   Previous  page  Next  page