Call for Paper - November 2022 Edition
IJCA solicits original research papers for the November 2022 Edition. Last date of manuscript submission is October 20, 2022. Read More

An Algorithm for Magnitude Comparison in RNS based on Mixed-Radix Conversion II

Print
PDF
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Year of Publication: 2016
Authors:
Konstantin Isupov
10.5120/ijca2016909626

Konstantin Isupov. An Algorithm for Magnitude Comparison in RNS based on Mixed-Radix Conversion II. International Journal of Computer Applications 141(5):1-4, May 2016. BibTeX

@article{10.5120/ijca2016909626,
	author = {Konstantin Isupov},
	title = {An Algorithm for Magnitude Comparison in RNS based on Mixed-Radix Conversion II},
	journal = {International Journal of Computer Applications},
	issue_date = {May 2016},
	volume = {141},
	number = {5},
	month = {May},
	year = {2016},
	issn = {0975-8887},
	pages = {1-4},
	numpages = {4},
	url = {http://www.ijcaonline.org/archives/volume141/number5/24777-2016909626},
	doi = {10.5120/ijca2016909626},
	publisher = {Foundation of Computer Science (FCS), NY, USA},
	address = {New York, USA}
}

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

  1. N. S. Szabo and R. I. Tanaka. Residue Arithmetic and its Application to Computer Technology. McGraw-Hill, New York, NY, USA, 1967.
  2. B. Parhami. Computer Arithmetic: Algorithms and Hardware Designs. Oxford Univ. Press, New York, NY, USA, 2000.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. Mi Lu and J.-S. Chiang. A novel division algorithm for the residue number system. IEEE Trans. Comput., 41(8):1026–1032, August 1992.
  10. 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.
  11. 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.
  12. 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.
  13. M. Akkal and P. Siy. A new mixed radix conversion algorithm MRC-II. J. Syst. Arch., 53(9):577–586, September 2007.
  14. 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.
  15. C. H. Huang. A fully parallel mixed-radix conversion algorithm for residue number applications. IEEE Trans. Comput., C-32(4):398–402, April 1983.
  16. 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.

Keywords

Residue number system, magnitude comparison, mixed-radix conversion, MRC-II