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

RNS Scaling Algorithm for a New Moduli Set {2^(2n+1) +1, 2^(2n+1), 2^(2n+1)-1}

Print
PDF
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Year of Publication: 2017
Authors:
Khalid Shahabdeen Mustapha, Edem Kwedzo Bankas
10.5120/ijca2017913974

Khalid Shahabdeen Mustapha and Edem Kwedzo Bankas. RNS Scaling Algorithm for a New Moduli Set 2^(2n+1) +1, 2^(2n+1), 2^(2n+1)-1. International Journal of Computer Applications 165(10):21-28, May 2017. BibTeX

@article{10.5120/ijca2017913974,
	author = {Khalid Shahabdeen Mustapha and Edem Kwedzo Bankas},
	title = {RNS Scaling Algorithm for a New Moduli Set {2^(2n+1) +1, 2^(2n+1), 2^(2n+1)-1}},
	journal = {International Journal of Computer Applications},
	issue_date = {May 2017},
	volume = {165},
	number = {10},
	month = {May},
	year = {2017},
	issn = {0975-8887},
	pages = {21-28},
	numpages = {8},
	url = {http://www.ijcaonline.org/archives/volume165/number10/27609-2017913974},
	doi = {10.5120/ijca2017913974},
	publisher = {Foundation of Computer Science (FCS), NY, USA},
	address = {New York, USA}
}

Abstract

Scaling is one of the difficult operations in Residue Number System (RNS) and also one of the most important units and a necessary operation used to avoid overflow in RNS based systems. In this paper, a scaling algorithm for a new moduli set {22n+1 +1, 22n+1, 22n+1 - 1} using the Chinese Remainder Theorem (CRT) is presented. In the design of digital systems, the goal of designers is to increase performance and decrease the amount of hardware resources. In order to achieve this, a new moduli sets is proposed to obtain a larger dynamic range and less complex hardware architecture. The CRT is further simplified for the selected moduli set to reduce the hardware complexity of the scaling algorithm. The scaling algorithm does not introduce any scaling errors and thus is efficient. When compared with the state of the art scaling algorithm using the Unit- Gate model, the results show that, the proposed scaling algorithm outperforms the state of the art scaling algorithm in terms of dynamic range (DR), area consumption, and delay by 98%, 18.4% and 21.7% respectively.

References

  1. Neha, S. 2008. An Overview of Residue Number System. National Seminar on Devices, Circuits and Communication.
  2. Stouraitis, T. and Paliouras, V. 2001. Considering the Alternatives in low-power design,” Circuits and Devices Magazine, IEEE, Vol. 17, No. 4, Pp. 22–29.
  3. Soudris, D., Dasygenis, M., Mitroglou, K., Tatas, K., and Thanailakis 2002. A Full adder Based Methodology for Scaling Operations in Residue Number System, Electronics, Circuits and Systems. 9th International Conference on Vol. 3, 891-894.
  4. Molahosseini, A. S., Navi, K., Dadkhah, C., Kavehei, O., and Timachi 2010. Efficient Reverse converter Designs for the New 4- Moduli Sets and based on new CRTs Circuits and Systems I: Regular Papers, IEEE Transactionson Vol. 57 No. 4. 823-835.
  5. Chang, C. H. and Low, J. 2011. Simple, Fast, and Exact RNS Scaler for the Three-Moduli Set, Circuits and Systems I: Regular Papers, IEEE Transactions on, Vol. 58, No. 11, 2686–2697.
  6. Safari, A. and Kong, Y. 2012. Simple, fast and synchronous hybrid scaling scheme for the 8-bit Moduli Set, Journal of Emerging Trends in Computing and Information Sciences, Vol. 3, No. 6, 949–956.
  7. Kong, Y. and Philip, B. 2009. Fast Scaling in the Residue Number System, IEEE Trans. Very Large Scale Integer (VLSI) Syst. Vol. 17 No. 3, (Mar. 2009) 443- 447.
  8. Gbolagade, K. A. 2010. Efficient Reverse Conversion in Residue Number System Processors. PhD. Thesis Delft University of Technology the Netherlands.
  9. Szabo N. S. and Tanaka R. I. (1967), Residue Arithmetic and its Applications to Computer Technology. McGraw-Hill New York, 1967, Vol. 24.
  10. O’Keefe, K. H. and Wright, J. L. 1973. Remarks on Base Extension for Modular Arithmetic. Computers, IEEE Transactions on, Vol. 100, No. 9, 833–835.
  11. Jullien, G. A. 1978. Residue Number Scaling and Other Operations Using ROM Arrays, Computers, IEEE Transactions on, Vol. 100, No. 4, 325–336.
  12. Taylor F. J. and Huang C. H (1981), a Floating-Point Residue Arithmetic Unit. Journal of the Franklin Institute, Vol. 311, No. 1, Pp. 33–53, 1981.
  13. Taylor, F. J. and Huang, C. H. 1982. An Auto Scale Residue Multiplier. Computers, IEEE Transactions on, Vol. 100, No. 4, 321–325.
  14. Miller, D. D. and Polky, J. N. 1984. An Implementation of the LMS Algorithm in the residue number system. Circuits and Systems, IEEE Transactions, Vol. 31, No. 5, Pp. 452–461.
  15. Griffin, M. S. M. and Taylor, F. 1989. Efficient Scaling in the Residue Number System, in Int. Conf. Acoust. Speech, Signal Process, Glasgow, U.K. 1075–1078.
  16. Shenoy, M. A. P and Kumaresan, K. 1989. A Fast and Accurate RNS Scaling Technique for high Speed Signal Processing. IEEE Trans. Acoust. Speech, Signal Process, Vol. 37, No. 6. (June 1989), 929 – 937.
  17. Ulman, Z. D. Czyzak, M. and Zurida, J. M. 1993. Effective RNS Scaling Algorithm with the Chinese Remainder Theorem Decomposition. in Proc. IEEE Pacific Rim Conf. Commun. Computers, Signal Process., Victoria, BC, (May 1993), 528-531.
  18. Barsi, F. and Pinotti, M. C. 1995. Fast base extension and precise Scaling in RNS for Look- up Table implimentations. IEEE Trans. Systems and Process, Vol. 43, No. 10, (October 1995), 2427- 2430.
  19. Garcia, A. and Lloris, A. 1999. A look- up Scheme for Scaling in RNS. IEEE Transactions Comput. Vol. 48, No.7, (July1999), 748-751.
  20. Meyer-Base, U. and Stouraitis, T. 2003. New Power -of -2 RNS Scaling Scheme for Cell-based IC Design, IEEE Trans. Very Large Scale Integer, (VLSI) Syst., Vol. 11, No. 2, (April 2003), 280-283.
  21. Benardson, P. 1985. Fast Memoryless, Over 64 bits, Residue-to-Binary converter. Circuits and Systems IEEE Transactions on Vol. 32. No. 3, (Mar. 1985), 298-300.
  22. Mohan, P. V. A. 2007. RNS -To Binary Converter for a New Three-Moduli set. IEEE Transaction on Circuits and Systems-II, Vol. 54 No. 9, 775-779.
  23. Dasygenis, M., Mitroglou, K., Soudris, D., and Thanailakis, 2008. A Full Adder Based Methodology for the Design of Scaling Operations in Residue Number System. Circuits and Systems I: Regular Papers, IEEE Transactions on Vol. 55, No. 2, (Mar. 2008), 546-558.
  24. Bernocchi, G. L., Cardarili, G. C., Nannarelli, A., Re M. 2007. Low Power Adaptive Filter Based on RNS Components. Proc. IEEE International Symposium Circuits Systems, New Orleans, LA, 3211-3214.
  25. Bankas, E. K., and Gbolagade, K. A., 2013. An Effective New CRT Based Reverse Converter for a Novel Moduli Set {22n+1- 1, 22n+1, 22n- 1}. International Journal of VLSI Design and Communication Systems (December, 2013), 4(6):1-11.
  26. Omondi, A. and Premkumar, B. 2007. Residue Number System Theory and Implementation. Imperial College Press.
  27. Gbolagade, K. A. and Cotofana, S.D. 2009b. A Reverse Converter for the new 4 – Moduli set {2n+3, 2n +2, 2n+1, 2n}. Submitted to IEEE Newcastaisa Toulouse, France. (July, 2009).
  28. Daabo, M. I. and Gbolagade, K. A. 2012. Overflow Detection Scheme in RNS Multiplication before Forward Convertion. Journal of computing. 4(12):13-16.
  29. Bankas, E. K., and Gbolagade, K. A., 2015. New MRC Adder-Based Reverse Converter for the Moduli Set {2n, 22n+1 − 1, 22n+2 − 1}. Oxford Journals, Science & Mathematics, Computer Journal Volume 58, Issue 7, 1566-1572.
  30. Dimitrakopoulos, G., Nikolos, D. G., Vergos, H. T., Nikolos, D., Efstathiou, C. 2005. New Architectures for modulo 2n - 1 Adders. in Proc. IEEE Int. Conf. Electrn., Circuits, Syst., Gammarth, Tunisia. (Dec. 2005). 1- 4.
  31. Vergos, H. T., Efstathiou, C., and Nikolos, D. 2002. Diminished – One Modulo 2n + 1 Adder Design. IEEE Transaction Computers, Vol. 51, No. 12, (Dec. 2002), 1389-1399.

Keywords

Scaler, RNS, Chinese Remainder Theorem, Moduli Set, Dynamic Range.