Abstract

The residue number system (RNS) has computational advantages for large integer arithmetic because of its parallel carry free, and high-speed arithmetic nature. However, magnitude comparison is a very complex operation for RNS. This paper presents a new comparison algorithm based on the modification of Mixed-Radix Conversion II technique. The new algorithm uses small modulo operations only and has a linear time complexity in terms of the size of the moduli set.

References

• N. S. Szabo and R. I. Tanaka. Residue Arithmetic and its Application to Computer Technology. McGraw-Hill, New York, NY, USA, 1967.
• B. Parhami. Computer Arithmetic: Algorithms and Hardware Designs. Oxford Univ. Press, New York, NY, USA, 2000.
• P. Albicocco, G. C. Cardarilli, A. Nannarelli, and M. Re. Twenty years of research on RNS for DSP: Lessons learned and future perspectives. In Proc. 14th Int. Symp. Integrated Circuits (ISIC), pages 436–439, Singapore, December 2014.
• M. Esmaeildoust, D. Schinianakis, H. Javashi, T. Stouraitis, and K. Navi. Efficient RNS implementation of elliptic curve point multiplication over GF(p). IEEE Trans. VLSI Syst., 21(8):1545–1549, August 2013.
• Vik Tor Goh and M. U. Siddiqi. Multiple error detection and correction based on redundant residue number systems. IEEE Trans. Commun., 56(3):325–330, March 2008.
• G. C. Cardarilli, A. Del Re, A. Nannarelli, and M. Re. Programmable power-of-two RNS scaler and its application to a QRNS polyphase filter. In Proc. IEEE Int. Symp. Circuits Syst., pages 1102–1105, Kobe, Japan, May 2005.
• S. Bi and W. J. Gross. The mixed-radix chinese remainder theorem and its applications to residue comparison. IEEE Trans. Comput., 57(12):1624–1632, December 2008.
• G. Dimauro, S. Impedovo, and G. Pirlo. A new technique for fast number comparison in the residue number system. IEEE Trans. Comput., 42(5):608–612, May 1993.
• Mi Lu and J.-S. Chiang. A novel division algorithm for the residue number system. IEEE Trans. Comput., 41(8):1026–1032, August 1992.
• D. D. Miller, R. E. Altschul, J. R. King, and J. N. Polky. Analysis of the residue class core function of Akushskii, Burcev, and Pak. In M. A. Soderstrand, W. K. Jenkins, G. A Jullien, and F. J. Taylor, Eds. Residue Number System Arithmetic: Modern Applications in Digital Signal Processing, pages 390–401. IEEE Press, NJ, USA, 1985.
• L. Sousa. Efficient method for magnitude comparison in RNS based on two pairs of conjugate moduli. In Proc. 18th IEEE Int. Symp. Comput. Arithmetic, pages 240–250, Montpellier, France, June 2007.
• H. M. Yassine and W. R. Moore. Improved mixed-radix conversion for residue number system architectures. IEE Proc.-G, 138(1):120–124, February 1991.
• M. Akkal and P. Siy. A new mixed radix conversion algorithm MRC-II. J. Syst. Arch., 53(9):577–586, September 2007.
• K. A. Gbolagade and S. D. Cotofana. An O(n) residue number system to mixed radix conversion technique. In Proc. IEEE Int. Symp. Circuits Syst., pages 521–524, Taipei, Taiwan, May 2009.
• C. H. Huang. A fully parallel mixed-radix conversion algorithm for residue number applications. IEEE Trans. Comput., C-32(4):398–402, April 1983.
• N.B. Chakraborti, J. S. Soundararajan, and A. L. N. Reddy. An implementation of mixed-radix conversion for residue number applications. IEEE Trans. Comput., 35(8):762–764, August 1986.