RNS representations with redundant residues

Residue number system (RNS) representations that contain redundant moduli have been extensively studied with regard to their error checking properties. A second form of redundancy in RNS, that of redundant residues, has been applied in certain application contexts to gain speed and cost benefits. Such applications are developed in an ad hoc manner and there does not exist a theoretical framework for the latter variety of redundant RNS. We develop a theory of RNS representations with redundant residues and show how representation parameters affect the speed and complexity of various arithmetic operations. The theory parallels that of redundant signed-digit representations in that at issue are choice of ´residue sets´ (akin to digit sets), encoding of residue sets, conversions between residue sets with different degrees of redundancy, including none, and algorithms for arithmetic on redundant-residue operands.