High Speed Method of Conversion Numbers from Residue Number System to Positional Notation
https://doi.org/10.15514/ISPRAS-2024-36(4)-9
Abstract
The Residue Number System is a widely used non-positional number system. Residue Number System can be effectively used in applications and systems with a predominant proportion of addition, subtraction and multiplication operations, due to the parallel execution of operations and the absence of inter-bit carries. The reverse conversion of a number from Residue Number System to positional notation requires the use of special algorithms. The main focus of this article lies in introducing the new conversion method, which incorporates Chinese Remainder Theorem, Akushsky Core Function and rank of number. The step-by-step procedure of the conversion process is detailed, accompanied by numerical examples. The proof of the relationship between the ranks of positional characteristics using the Chinese Remainder Theorem is presented. Through careful analysis and comparison with existing transformation methods, it is concluded that the presented approach takes on average 8 % less time than the Approximate Method.
Keywords
residue number system,
Chinese remainder theorem, approximate method,
Akushsky core functions,
non-modular operations.
Supporting agencies: The research was supported by the Russian Science Foundation Grant No. 19-71-10033, https://rscf.ru/en/project/19-71-10033/.
About the Authors
Vladislav Vyacheslavovich LUTSENKO
North-Caucasus Federal University
Russian Federation
Russian Federation
Postgraduate student, Department of Computational Mathematics and Cybernetics, Faculty of Mathematics and Computer Science named after Professor N.I. Chervyakov, North Caucasus Federal University. Research interests: high-performance computing, residue number system, smart city, neural networks, Internet of Things.
Mikhail Grigoryevich BABENKO
North-Caucasus Federal University
Russian Federation
Russian Federation
Dr. Sci. (Phys.-Math.), Head of the Department of Computational Mathematics and Cybernetics, Faculty of Mathematics and Computer Science named after Professor N.I. Chervyakov, North Caucasus Federal University. His research interests include cloud computing, high-performance computing, residue number systems, neural networks, cryptography.
Munis Musinovich KHAMIDOV
Samarkand State University named after Sharof Rashidov
Uzbekistan
Uzbekistan
Assistant Professor at Samarkand State University named after
Sharof Rashidov.
References
1. Mohan P.A., Ananda Mohan P.V. Error Detection, Correction and Fault Tolerance in RNS-Based Designs. Residue Number Systems: Theory and Applications, Birkhäuser: Cham, Switzerland, 2016, pp. 163-175.
2. Guo Z., Gao Z., Mei H., Zhao M., Yang J. Design and optimization for storage mechanism of the public blockchain based on redundant residual number system. IEEE Access, 2019, vol. 7, pp. 98546-98554.
3. Al Badawi A., Polyakov Y., Aung K. M. M., Veeravalli B., Rohloff K. Implementation and performance evaluation of RNS variants of the BFV homomorphic encryption scheme. IEEE Transactions on Emerging Topics in Computing, 2019, vol. 9, no. 2, pp. 941-956.
4. Molahosseini A. S., De Sousa L. S., Chang C. H. Embedded systems design with special arithmetic and number systems. Cham, Switzerland: Springer, 2017, p. 390.
5. Valueva M. V., Nagornov N. N., Lyakhov P. A., Valuev G. V., Chervyakov N. I. Application of the residue number system to reduce hardware costs of the convolutional neural network implementation. Mathematics and computers in simulation, 2020, vol. 177, pp. 232-243.
6. Dong X. A multi-secret sharing scheme based on the CRT and RSA. International Journal of Electronics and Information Engineering, 2015, vol. 2, no. 1, pp. 47-51.
7. Van Vu T. Efficient implementations of the Chinese remainder theorem for sign detection and residue decoding. IEEE Transactions on Computers, 1985, vol. 100, no. 7, pp. 645-651.
8. Chervyakov N. I., Molahosseini A. S., Lyakhov P. A., Babenko M. G., Deryabin M. A. Residue-to-binary conversion for general moduli sets based on approximate Chinese remainder theorem. International journal of computer mathematics, 2017, vol. 94, no. 9, pp. 1833-1849.
9. Chervyakov N. I., Babenko M. G., Kuchukov V. A. Research of effective methods of conversion from positional notation to RNS on FPGA. In Proceedings of the 2011 45th Annual Conference on Information Sciences and Systems, 1-3 February 2017, IEEE: St. Petersburg/Moscow, Russia, 2017, pp. 371-375.
10. Soderstrand M., Vernia C., Chang J. H. An improved residue number system digital-to-analog converter. IEEE transactions on circuits and systems, 1983, vol. 30, no. 12, pp. 903-907.
11. Babenko M., Golimblevskaia E. About One Property of Number Rank in RNS. In Proceedings of the 2021 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering, 26-29 January 2021, St. Petersburg, FL, USA, 2021, pp. 212-216.
12. Isupov K. High-Performance Computation in Residue Number System Using Floating-Point Arithmetic. Computation, 2021, vol. 9, no. 2, 9.
13. Chervyakov N.I., Averbukh V.M., Babenko M.G., Lyakhov P.A., Gladkov A.V., Gapochkin A.V. An Approximate Method for Performing Non-Modular Operations in a System of Residual Classes. Fundam. Res., 2012, vol. 6, pp. 189-193.
14. Yassine H. M., Moore W. R. Improved mixed-radix conversion for residue number system architectures. IEE Proceedings G (Circuits, Devices and Systems), 1991, vol. 138, no. 1, pp. 120-124.
15. Gladkov A., Gladkova N., Kucherov N. Analytical Review of Methods for Detection, Localization and Error Correction in the Residue Number System. In Proceedings of the International Conference on Mathematics and its Applications in New Computer Systems, 25-28 October 2022, Munich, Germany, Springer: Berlin/Heidelberg, 2022, pp. 507-514.
16. Babenko M., Piestrak S. J., Chervyakov N., Deryabin M. The study of monotonic core functions and their use to build RNS number comparators. Electronics, 2021, vol. 10, no. 9, p. 1041.
17. Piestrak, S. J. A note on RNS architectures for the implementation of the diagonal function. Information Processing Letters, 2015, vol. 115, no. 4, pp. 453-457.
18. Акушский И. Я., Бурцев В. М., Пак И. Т. О новой позиционной характеристике непозиционного кода и ее приложении. Теория кодирования и оптимизация сложных систем. Алма-Ата, Наука, КазССР, 1977, стр. 8–16. / Akushsky, I.Y., Burtsev, V.M., Pak, I.T. (1977) About the New Positional Characteristic of the Non-Positional Code and Its Application. In Theory of Coding and Optimization of Complex Systems, Alma-Ata, Nauka, KazSSR, 1977, pp. 8-16 (in Russian).
19. Shiriaev E., Kucherov N., Babenko M., Lutsenko V., Al-Galda S. Algorithm for Determining the Optimal Weights for the Akushsky Core Function with an Approximate Rank. Applied Sciences, 2023, vol. 13, no. 18, p. 10495.
Review
For citations:
LUTSENKO V.V., BABENKO M.G., KHAMIDOV M.M. High Speed Method of Conversion Numbers from Residue Number System to Positional Notation. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2024;36(4):117-132. https://doi.org/10.15514/ISPRAS-2024-36(4)-9
Email this article 