Addition and overflow handling in a class of redundant RNS with magnitude index

The presence of a magnitude index in the residue representation of numbers is considered here in an attempt to drastically reduce the need for intermodular operations in detecting additive overflow. To this purpose, a redundant number system whose representation consists of residue, magnitude index (MI) and control (C) digits is defined and its arithmetic properties are investigated. It is shown that repeated modular additions with a high degree of overflow detection are possible in such a system, while the control digit signals the needs for intermodular operations which must be carried out if no overflow has been detected. An adding, overflow-detecting procedure is presented together with several examples. A probabilistic evaluation of the performance of the procedure is given for a particular class of applications.