ПОСТРОЕНИЕ СИСТЕМЫ ОСТАТОЧНЫХ КЛАССОВ С ДИАГОНАЛЬНОЙ ФУНКЦИЕЙ СПЕЦИАЛЬНОГО ВИДА

Система остаточных классов (СОК) - это непозиционная система счисления, которая является перспективным инструментом для улучшения производительности цифровых устройств. Хотя, так как СОК является непозиционной системой счисления, операция сравнения чисел в ней невозможна, а следовательно операция деления, а так же обратного преобразования в позиционную систему счисления тоже невозможны. Одним из подходов к решению данной проблемы является использование диагональной функции (ДФ). В данной статье предлагается метод построения СОК с 2П 2И _1 2П . 1 ДФ удобного вида, который приводит к вычислениям по модулям² ,²¹ или² "т"¹ и позволяет проектировать эффективные аппаратные реализации. В работе проведено аппаратное моделирование операции сравнения и обратного преобразования в позиционную систему счисления с использованием СОК с различными наборами модулей, построенными с использованием предлагаемого метода и различных подходов к выполнению данных операций: ДФ, китайская теорема об остатках (КТО), и КТО с дробными величинами (КТОд). Аппаратная реализация операции сравнения показала, что для набора из трех модулей, предлагаемый метод позволяет 5 98% 49 72% сократить аппаратные затраты на - по сравнению с известными методами. Для набора из четырех модулей предлагаемый метод позволяет сократить задержку устройства на 4 92% 21 95% -r.^z,/u ^i../^/u, а аппаратные затраты в 2 раза по сравнению с известными методами. Сравнение результатов моделирования для предложенных наборов модулей и сбалансированных наборов модулей показало, что использование предложенных наборов модулей позволяет в 2 раза сократить задержку устройства, хотя, в некоторых случаях требует больше аппаратных затрат, чем при использовании сбалансированных наборов модулей. Система остаточных классов (СОК) является перспективным инструментом для увеличения производительности цифровых устройств, которые позволяют реализовывать операции сложения и умножения быстро и параллельно. Хотя, операции сравнения, деления и обратного преобразования являются проблематичными в СОК. Одним из подходов для решения данной проблемы является использование диагональной функции (ДФ). В данной статье предлагается метод построения СОК с ДФ удобного вида. который приводит к вычислениям по модулям 2 , 2 _1 или и позволяет разрабатывать эффективные аппаратные реализации.

система остаточных классов, диагональная функция, китайская теорема об остатках

1. Akkal M., Siy P. A new Mixed Radix Conversion algorithm MRC-II // J. Syst. Archit. 2007. Т. 53. № 9. С. 577-586.

2. Rami rez J. и др. RNS-enabled digital signal processor design // Electron. Lett. 2002. Т. 38. № 6. С. 266.

3. Chang C.-H. и др. Residue Number Systems: A New Paradigm to Datapath Optimization for Low-Power and High-Performance Digital Signal Processing Applications // IEEE Circuits Syst. Mag. 2015. Т. 15. № 4. С. 26-44.

4. Kaplun D. и др. Optimization of the FIR Filter Structure in Finite Residue Field Algebra // Electronics. 2018. Т. 7. № 12. С. 372.

5. Esmaeildoust M. и др. Efficient RNS Implementation of Elliptic Curve Point Multiplication Over GF(p) // IEEE Trans. Very Large Scale Integr. Syst. 2013. Т. 21. № 8. С. 1545-1549.

6. Bajard J.-C., Imbert L. a full RNS implementation of RSA // IEEE Trans. Comput. 2004. Т. 53. № 6. С. 769-774.

7. Sousa L., Antao S., Martins P. Combining Residue Arithmetic to Design Efficient Cryptographic Circuits and Systems // IEEE Circuits Syst. Mag. 2016. Т. 16. № 4. С. 6-32.

8. Chervyakov N.I., Lyakhov P.A., Babenko M.G. Digital filtering of images in a residue number system using finite-field wavelets // Autom. Control Comput. Sci. 2014. Т. 48. № 3. С.180-189.

9. Kar A. и др. Secuirity in cloud storage: An enhanced technique of data storage in cloud using RNS // 2016 IEEE 7th Annual Ubiquitous Computing, Electronics & Mobile Communication Conference (UEMCON). : IEEE, 2016. С. 1-4.

10. NAVI K., ESMAEILDOUST M., MOLAHOSSEINI A.S. A General Reverse Converter Architecture with Low Complexity and High Performance // IEICE Trans. Inf. Syst. 2011. Т. E94-D. № 2. С. 264-273.

11. Chang C.-C. и др. Signature Gateway: Offloading Signature Generation to IoT Gateway Accelerated by GPU // IEEE Internet Things J. 2018. С. 1-1.

12. Chervyakov N.I. и др. An Approximate Method for Comparing Modular Numbers and its Application to the Division of Numbers in Residue Number Systems* // Cybern. Syst. Anal. 2014. Т. 50. № 6. С. 977-984.

13. Mohan P.V.A. Residue number systems : theory and applications. : В irkh auser, 2016.

14. Matos R. de и др. Efficient implementation of modular multiplication by constants applied to RNS reverse converters // 2017 IEEE International Symposium on Circuits and Systems (ISCAS). : IEEE, 2017. С. 1-4.

15. Dimauro G., Impedovo S., Pirlo G. A new technique for fast number comparison in the residue number system // IEEE Trans. Comput. 1993. Т. 42. № 5. С. 608-612.

16. Kalampoukas L. и др. High-speed parallel-prefix module 2/sup n/-1 adders // IEEE Trans. Co put. 2000. Т. 49. № 7. С. 673-680.

17. Efstathiou C., Vergos H.T., Nikolos D. Fast parallel-prefix modulo 2/sup n/+1 adders // IEEE Trans. Comput. 2004. Т. 53. № 9. С. 1211-1216.

18. Vergos H.T., Dimitrakopoulos G. On Modulo 2An+1 Adder Design // IEEE Trans. Comput. 2012. Т. 61. № 2. С. 173-186.

19. Hiasat A. Efficient RNS Scalers for the Extended Three-Moduli Set {2 -1,2 p,2 +1} // ieee Trans. Comput. 2017. Т. 66. № 7. С. 1253-1260.

20. Chaves R., Sousa L. Improving residue number system multiplication with more balanced moduli sets and enhanced modular arithmetic structures // IET Comput. Digit. Tech. 2007. Т. 1. № 5. С. 472.

21. Jaberipur G., Nejati S. Balanced Minimal Latency RNS Addition for Moduli Set {2 -1,2 ,2 +1} // 18th int. Conf. Syst. Signals Im age Process. 2011. С. 1-7.

22. Kumar S., Chang C.-H., Tay T.F. New Algorithm for Signed Integer Comparison in {2n+k 2n 1 2n +1 2n~1 1} , , , } and Its Efficient Hardware Implementation // IEEE Trans. Circuits Syst. I Regul. P ap. 2017. Т. 64. № 6. С. 1481-1493.

23. Mohan P.V.A., Premkumar A.B. RNS-to-Binary Converters for Two Four-Moduli {2n +1,2n-1,2n,2n+1 -1} {2n + 1,2n-1,2n,2n+1 +1} ^ _. _ T., , Sets и. // IEEE Trans. Circuits Syst. I Regul. P ap. 2007. Т. 54. № 6. С. 1245-1254.

24. Vayalil N.C., Paul M., Kong Y. A Residue Number System Hardware Design of Fast-Search Variable-Motion-Estimation Accelerator for HEVC/H.265 // IEEE Trans. Circuits Syst. Video Technol. 2019. Т. 29. № 2. С. 572-581.

25. Chervyakov N.I. и др. Effect of RNS dynamic range on grayscale images filtering // 2016 XV International Symposium Problems of Redundancy in Information and Control Systems (REDUNDANCY). : IEEE, 2016. С. 33-37.

26. Molahosseini A.S., Sorouri S., Zarandi A.A.E. Research challenges in next-generation residue number system architectures // 2012 7th International Conference on Computer Science & Education (ICCSE). : IEEE, 2012. С. 1658-1661.

27. P arhami В. Computer arithm etic : algorithms and hardware designs. : Oxford University Press, 2010. 672 с.