350 rub
Journal Neurocomputers №9 for 2014 г.
Article in number:
Modern Residue Number System Moduli Sets: Efficiency vs. Complexity
Keywords: Residue Number System Chinese Remainder Theorem Moduli Sets Reverse Converter
Authors:
Azadeh Alsadat Emrani Zarandi - Department of Computer Engineering, Tehran Science and Research Branch, Islamic Azad University, Tehran, Iran. E-mail: a.emrani@srbiau.ac.ir
Amir Sabbagh Molahosseini - Department of Computer Engineering, Kerman Branch, Islamic Azad University, Kerman, Iran. E-mail: sabbagh@iauk.ac.ir
Mehdi Hosseinzadeh - Department of Computer Engineering, Tehran Science and Research Branch, Islamic Azad University, Tehran, Iran. E-mail: hosseinzadeh@srbiau.ac.ir
Abstract:
The residue number system (RNS) is an exceptional non-weighted number system which can provide carry-free and consequently parallel addition and multiplication operations on residue numbers. In contrast to these arithmetic operations, non-modular RNS operations such as division, reverse conversion, scaling, sign detection and magnitude comparison are difficult RNS operations. The performance of modular as well as non-modular RNS operations are mainly dependent to the selected moduli set. Due to these many different moduli sets with different kind of moduli as well as variant numbers of moduli have been suggested for RNS. Different applications need different types of the moduli sets. For instance, digital signal processing systems need moduli sets with less moduli than cryptography. However, using a specific moduli set effect on different RNS parts. In this paper, we aim to investigate the modern RNS moduli sets and their effects on different parts of RNS. Particularly, we want to show how modern RNS moduli sets can gain efficiency while taming complexity. Besides, as a case study, we will analyze application-specific integrated circuit (ASIC) implementation results of residue to binary converters based on some modern RNS moduli sets in terms of latency, chip area and power-consumption.
Pages: 9-12
References

  1. Bayoumi M. A. and Srinivasan P., Parallel Arithmetic: From Algebra to Architecture // In Proceedings of IEEE International Symposium on Circuits and Systems, 1990.
  2. Stouratitis T. and Paliouras V.,Considering the alternatives in low-power design // IEEE Circuits Devices. 2001. V. 7. P. 23-29.
  3. Garner H. L., The Residue Number System // IRE Transactions on Electronic Computers. 1959. V. 8. № 2. P. 140-147.
  4. Omondi A.and Premkumar B., Residue Number Systems: Theory and Implementations // Imperial College Press. London. 2007.
  5. Mohan P.V.A.,Residue Number Systems: Algorithms and Architectures. Kluwer Academic. 2002.
  6. Parhami B.,Computer Arithmetic: Algorithms and Hardware Designs. 2nd edition. Oxford University Press. 2010.
  7. Soderstrandet M. A. al., Residue Number System Arithmetic: Modern Applications in Digital Signal Processing. Piscataway, NJ // IEEE Press. 1986.
  8. Cardarilli G. C., Nannarelli A., and Re M., Residue number system for low-power DSP applications // In Proc. 41nd Asilomar Conf. Signals. Syst., Comput. 2007. P. 1412-1416.
  9. Chen J. and Hu J., Energy-Efficient Digital Signal Processing via Voltage-Over scaling-Based Residue Number System // IEEE Transactions on Very Large Scale Integration (VLSI) Systems. 2013. V. 21. № 7., P. 1322-1332.
  10. Posch K. C. and Posch R., Residue number systems: a key to parallelism in public key cryptography // Proceedings of the Fourth IEEE Symposium on Parallel and Distributed Processing. 1992. P. 432-435.
  11. Bajard J. C. and Imbert L., A Full RNS Implementation of RSA // IEEE Transactions on Computers. 2004. V. 53. № 6. P. 769-774.
  12. Schinianakis D. M., Kakarountas A. P.and Stouraitis T., A new approach to elliptic curve cryptography: an RNS architecture // Proceedings of IEEE Mediterranean Conference on Electrotechnical. 2006. P. 1241-1245.
  13. Pontarelli S., Cardarilli G. C., Re M., and Salsano A., Totally Fault Tolerant RNS Based FIR Filters // In Proc. IEEE International On-Line Testing Symposium. 2008. P. 192-194.
  14. Chu J. and Benaissa M., Error detecting AES using polynomial residue number systems // Microprocessors and Microsystems. 2013. V. 37. № 2. P. 228-234.
  15. Goh V. T. and Siddiqi M. U., Multiple Error Detection and Correction Based on Redundant Residue Number Systems // IEEE Transactions on Communications. 2008. V. 56. № 3. P. 325-330.
  16. Navi K., Molahosseini A. S., Esmaeildoust M., How to Teach Residue Number System to Computer Scientists and Engineers // IEEE Transactions on Education. Feb. 2011. V. 54. № 1, P. 156-163.
  17. Molahosseini A. S., Navi K., Study of the Reverse Converters for the Large ynamic Range Four-Moduli Sets // Invited Chapter in the Book - Applications of Digital Signal Processing?,C. C. Laborde (Ed.), Chapter 16, InTech Press, Nov. 2011.
  18. Abdallah M. and Skavantzos A., A systematic approach for selecting practical moduli sets for residue number systems // In Proc. 27th IEEE Int. Symp. Syst. Theory. 1995. P. 445-449.
  19. Wang W., M. Swamy N. S., and Ahmad M. O., Moduli selection in RNS for efficient VLSI implementation // In Proc. IEEE Int. Symp. Circuits Syst. 2003. V. 4. P. IV-512-IV-515.
  20. Liu Y. and Lai E., Moduli Set Selection and Cost Estimation for RNS-Based FIR Filter and Filter Bank Design // Design Automation for Embedded Systems. 2004. V. 9. P. 123-139.
  21. Kalampoukas L., Nikolos D., Efstathiou C., Vergos H. T., and Kala-matianos J., High-speed parallel-prefix modulo 2n- 1 adders // IEEE Transactions on Computers. 2000. V. 49. № 7. P. 673-679.
  22. Efstathiou C., Vergos H. T., and Nikolos D., Fast parallel-prefix modulo 2n+1 adder // IEEE Transactions on Computers. Sep. 2004. V. 53. № 9. P. 1211-1216.
  23. Patel R. A., Benaissa M., Powell N.,and Boussakta S., Novel power-delay-area-efficient approach to generic modular addition // IEEE Transactions on Circuits and Systems I. 2007. V. 54. P. 1279-1292.
  24. Hiasat A. A., High-speed and reduced area modular adder structures for RNS // IEEE Transactions on Computers. Jan. 2002. V. 51. № 1. P. 84-89.
  25. Szabo N. and Tanaka R., Residue Arithmetic and its Applications to Computer Technology. New York: McGraw-Hill. 1967.
  26. Premkumar B., An RNS to binary converter in 2n+ 1, 2n, 2n - 1 moduli set // IEEE Transactions on Circuits and Systems II. July 1992. V. 39. P. 480-482.
  27. Pourbigharaz F. and Yassine H. M., A signed-digit architecture for residue to binary transformation // IEEE Transactions on Computers. Oct. 1997. V. 46. P. 1146-1150.
  28. Hiasat A. A. and Abdel-Aty-Zohdy H. S., Residue-to-binary arithmetic converter for the moduli set (2k, 2k- 1, 2k - 1 - 1) // IEEE Transactions on Circuits and Systems II. Feb. 1998. V. 45. P. 204-208.
  29. Mathew J., Radhakrishnan D., Srikanthan T., Fast residue-to-binary converter architectures // In Proc. of IEEE International Midwest Symposium on Circuits and Systems. 1999. P. 1090-1093.
  30. Molahosseini A. S., Navi K., Rafsanjani M. K., A new residue to binary converter based on mixed-radix conversion // In Proc. of IEEE International Conference on Information and Communication Technologies: From Theory to Applications. 2008.
  31. Hariri A., Navi K., Rastegar R., A new high dynamic range moduli set with efficient reverse converter // Elsevier Journal of Computers and Mathematics with Applications. 2008. V. 55. № 4. P. 660-668.
  32. Molahosseini A.S., Navi K., Hashemipour O., Jalali A., An efficient architecture for designing reverse converters based on a general three-moduli set // Elsevier Journal of Systems Architecture. 2008. V. 54. P. 929-934.
  33. Bhardwaj M., Srikanthan T., Clarke C.T., A reverse converter for the 4-moduli superset {2n ? 1, 2n, 2n+ 1, 2n+ 1 + 1} // In Proc. of IEEE Symposium on Computer Arithmetic. 1999.
  34. Vinod A. P., Premkumar A. B., A residue to binary converter for the 4-moduli superset {2n - 1, 2n, 2n+ 1, 2n+ 1 + 1} // Journal of Circuits, Systems and Computers. 2000. V. 10. P. 85 - 99.
  35. Cao B., Chang C.H., Srikanthan T., An Efficient Reverse Converter for the 4-Moduli Set {2n - 1, 2n, 2n+ 1, 22n + 1} Based on the New Chinese Remainder Theorem // IEEE Transactions on Circuits and Systems-I. 2003. V. 50. № 10. P. 1296-1303.
  36. Sheu M.H., Lin S.H., Chen C., and Yang S.W., An Efficient VLSI Design for a Residue to Binary Converter for General Balance Moduli {2n - 1, 2n+ 1, 2n - 3, 2n+ 3} // IEEE Transactions on Circuits and Systems-II. 2004. V. 51. № 3. P. 152-155.
  37. Zhang W., Siy P., An efficient design of residue to binary converter for four moduli set {2n - 1, 2n+ 1, 22n - 2, 22n + 1 - 3} based on new CRT II // Elsevier Journal of Information Sciences. 2008. V. 178. № 1. P. 264-279.
  38. Molahosseini A.S., Navi K., Dadkhah C., Kavehei O., Timarchi S., Efficient Reverse Converter Designs for the New 4-Moduli Sets {2n - 1, 2n, 2n+ 1, 22n+ 1 - 1} and {2n- 1, 2n + 1, 22n, 22n+ 1} Based on New CRTs // IEEE Transactions on Circuits and Systems-I. 2010. V. 57. № 4. P. 823-835.
  39. Molahosseini A.S. and Navi K., A Reverse Converter for the Enhanced Moduli Set {2n? 1, 2n+ 1, 22n, 22n+ 1 - 1} Using CRT and MRC // In Proc. of IEEE Computer Society Annual Symposium on VLSI. 2010. P. 456 - 457.
  40. Patronik P. and Piestrak S.J., Design of Reverse Converters for General RNS Moduli Sets {2k, 2n - 1, 2n+ 1, 2n+ 1 + 1} and {2k, 2n - 1, 2n + 1, 2n?1- 1} // IEEE Transactions on Circuits and Systems I, to appear. 2014.
  41. Hiasat A. A., VLSI implementation of new arithmetic residue to binary decoders // IEEE Transactions on Very Large Scale Integration (VLSI) Systems. 2005. V. 13. № 1. P. 153 - 158.
  42. Cao B., Chang C.-H., and Srikanthan T., A residue-to-binary converter for a new five-moduli set // IEEE Transactions on Circuits and Systems I. May 2007. V. 54. № 5. P. 1041-1049.
  43. Molahosseini A.S.,Dadkhah C., Navi K., A new five-moduli set for efficient hardware implementation of the reverse converter // IEICE Electronics Express. 2009. V. 6. № 4. P. 1006-1012.
  44. Pettenghi H., Chaves R., Sousa L., RNS Reverse Converters for Moduli Sets With Dynamic Ranges up to (8n+ 1)-bit // IEEE Transactions on Circuits and Systems I. 2013. V. 60. № 6. P. 1487-1500.
  45. Pettenghi H., Chaves R., Sousa L., Method to Design General RNS Reverse Converters for Extended Moduli Sets // IEEE Transactions on Circuits and Systems II. 2013. V. 60. № 12. P. 877 - 881.
  46. Parhami B., On Equivalences and Fair Comparisons among Residue Number Systems with Special Moduli // In Proc. of 44thAsilomar Conf. Signals, Systems, and Computers. 2010. P. 1690-1694.
  47. Zarandi A. A. E., Molahosseini A.S., Hosseinzadeh M., Sorouri S., Antao S., and Sousa L.,Reverse Converter Design via Parallel-Prefix Adders: Novel Components, Methodology and Implementations // IEEE Transactions on Very Large Scale Integration (VLSI) Systems, to appear. 2014.