350 руб
Журнал «Нейрокомпьютеры: разработка, применение» №9 за 2014 г.
Статья в номере:
Современные наборы модулей системы остаточных классов: сравнение эффективности и сложности
Ключевые слова: система остаточных классов китайская теорема об остатках наборы модулей обратный преобразователь
Авторы:
Азадех Алзадат Эмрани Заранди - кафедра вычислительной инженерии, Исламский университет Азад, Тегеран, Иран. E-mail: a.emrani@srbiau.ac.ir. Амир Саббаг Молахосеини - кафедра вычислительной инженерии, Исламский университет Азад, Керман, Иран. E-mail: sabbagh@iauk.ac.ir Мехди Хоссеинзаде - кафедра вычислительной инженерии, Исламский университет Азад, Тегеран, Иран. E-mail: hosseinzadeh@srbiau.ac.ir
Аннотация:
Система остаточных классов (СОК) является исключительной непозиционной системой счисления, без межразрядных переносов и с возможностью параллельного выполнения операций сложения и умножения чисел. В отличие от этих операций, немодульные операции в СОК, такие как деление, обратное преобразование, масштабирование, определение знака и сравнение чисел являются весьма сложными. Время выполнения как модульных, так и немодульных операций в СОК зависит в основном от выбранного набора модулей. В связи с этим в СОК предложено много различных наборов модулей разного вида с разным количеством модулей. Для разных приложений требуются разные типы наборов модулей. Например, для цифровой обработки сигналов требуется меньше модулей, чем для криптографии. Тем не менее, использование конкретного набора модулей оказывает влияние на различные составляющие СОК. В настоящей статье мы стремимся исследовать современные наборы модулей в СОК и их влияние на различные составляющие СОК. В частности, мы хотим показать, как современные наборы модулей СОК могут повысить эффективность за счет сокращения сложности. В качестве примера, мы проанализируем результаты реализации на интегральных схемах специального назначения (ASIC) обратных преобразователей СОК с разными наборами модулей по таким критериям, как задержка, занимаемая площадь и энергопотребление.
Страницы: 9-12
Список источников

  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.