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⩾3 with digit values ranging over the set {-α. . .,-1,0,1. . .,α}, where α is an arbitrary integer in the range r/2<α<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_i as a function of the digits x_i, y_i, x_i-1, y_i-1 , x_i-2 and y_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 α>0 and β>0) explicitly. Zero detection, sign detection, and overflow handling are also treated in depth