On the implementation of arithmetic support functions for generalized signed-digit number systems

摘要

Ordinary signed-digit (OSD) number representation systems have been defined for any radix r alpha >r. The most important property of OSD number representation systems is the possibility of performing carry-free addition and (by changing all the digit signs in the subtrahend) borrow-free subtraction. Generalized signed-digit (GSD) number systems cover all useful redundant number representations as special cases. Most GSD number systems support carry-free addition and borrow-free subtraction, and even those that do not can be dealt with using limited-carry or limited-borrow algorithms which yield the ith sum or difference digit z/sub i /as a function of the digits x/sub i/, y/sub i/, x/sub i-1/, y/sub i-1/, x/sub i-2/ and y/sub i-2/ of the operands x and y. Additional topics that are important for practical implementation of arithmetic functions using GSD number systems are treated. Because GSD number systems may have asymmetric digit sets, one must consider subtraction (or at least sign change for representations with alpha <0 and beta <0) explicitly. Zero detection, sign detection, and overflow handling are also treated in depth.