An efficient RNS parity checker for moduli set {2^n-1, 2^n＋1, 2^2n＋1} and its applications

Residue number system （RNS） has received considerable attention since decades before, because it has inherent carry-free and parallel properties in addition, sub- traction, and multiplication operations. For an odd moduli set, the fundamental problems in RNS, such as number comparison, sign determination, and overflow detection, can be solved based on parity checking. The paper proposes a parity checking algorithm along with related propositions and the certification based on the celebrated Chinese remainder theory （CRT） and mixed radix conversion （MRC） for the moduli set {2^n-1, 2^n＋1, 2^2n＋1}. The parity checker consists of two modular adders and a carry-look-ahead chain. The hardware implementation requires less area and path delay. Besides, the implementations of number comparison, sign determination, and overflow detection, which are based on this parity checker, are also performed in this paper. And this kind of parity checker can be used as a basic element to design ALUs and DSP module in RNS.