Высокоскоростной метод перевода чисел из системы остаточных классов в позиционную систему счисления

Система остаточных классов – это распространенная непозиционная система счисления. Система остаточных классов может эффективно использоваться в приложениях с преобладающей долей операций сложения, вычитания и умножения благодаря параллельному выполнению операций и отсутствию битовых сдвигов. Обратное преобразование числа из системы остаточных классов в позиционную систему счисления требует использования специальных алгоритмов. Основное внимание в данной статье уделено представлению нового метода преобразования, который использует Китайскую теорему об остатках, функцию ядра Акушского и ранг числа. Подробно описан алгоритм преобразования, представлены числовые примеры. Представлено доказательство связи между рангами позиционных характеристик с помощью Китайской теоремы об остатках. В результате тщательного анализа и сравнения с существующими методами преобразования сделан вывод, что представленный подход занимает в среднем на 8 % меньше времени, чем приближенный метод.

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.