CONSTRUCTION OF RESIDUE NUMBER SYSTEM USING DIAGONAL FUNCTION OF SPECIAL TYPE

Residue Number System (RNS) is a non-positional number system, which is a promising tool for increasing performance of digital devices. However, because of RNS is non-positional number system, magnitude comparison of numbers in RNS form is impossible, so division operation and operation of reverse conversion into positional form containing magnitude comparison operation that they are impossible too. One of the approaches to solve this problem is using Diagonal Function (DF). In this paper we propose the method of RNS construction with convenient form of DF, which leads to the calculations modulo² ,²¹ or² ~r¹ and allows to design efficient hardware implementations. We constructed the hardware simulation of magnitude comparison and reverse conversion into positional form using RNS with different moduli sets construct by proposed method and using different approaches to perform magnitude comparison and reverse conversion: DF, Chinese Reminder Theorem (CRT) and CRT with fractional values (CRTf). The hardware simulation of magnitude comparison shows that, for three moduli, proposed method allows to reduce 5 98% 49 72% hardware resources by - in comparison with known methods. For four moduli, proposed method reduces delay by⁴-⁹²% -²¹-⁹⁵% and hardware costs to 2 times by comparison to known methods. Comparing of simulation results of proposed moduli sets and balanced moduli sets shows that using of proposed moduli sets allows to 2 times reduce circuit delay, although, in several cases it is required more hardware resources than balanced moduli sets. Residue Number System (RNS) is a promising tool for increasing performance of digital devices, which allows performing addition and multiplication operations fast and in parallel. However, RNS has disadvantages that some operations in RNS such as reverse conversion into positional form, magnitude comparison and division of numbers are problematic. One of the approaches to solve this problem is using Diagonal Function (DF). In this paper we propose the method of RNS construction with convenient form of DF, which leads to the calculations modulo 2ⁿ , 2 _1 or 2" + 1 and allows to design efficient hardware implementations.

Residue Number System, Diagonal Function, Chinese Remainder Theorem

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 с.