Preview

Труды Института системного программирования РАН

Расширенный поиск

Эффективное сравнение чисел в системе остаточных классов на основе позиционной характеристики

https://doi.org/10.15514/ISPRAS-2019-31(2)-13

Аннотация

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

Об авторах

Михаил Григорьевич Бабенко
Кафедра прикладной математики и математического моделирования Северо-Кавказского федерального университета
Россия
Преподаватель кафедры прикладной математики и математического моделирования Северо-Кавказского федерального университета. Кандидат тезнических наук.


Андрей Николаевич Черных
Центр научных исследований и высшего образования Энсенада, Мексика; Институт системного программирования РАН им. В.П. Иванникова, Россия; Южно-Уральский государственный университет, Россия
Мексика
Профессор Центра научных исследований и высшего образования в Энсенаде


Николай Иванович Червяков
Северо-Кавказский федеральный университет
Россия
Доктор технических наук, профессор, заведующий кафедрой прикладной математики и информатики Северо-Кавказского федерального университета


Виктор Андреевич Кучуков
Северо-Кавказский федеральный университет
Россия
Специалист отдела научно-технической информации, наукометрии и экспортного контроля Управления науки и технологий Северо-Кавказского федерального университета.


Ванесса Миранда-Лопес
Центр научных исследований и высшего образования Энсенада, Мексика
Мексика


Рауль Ривера Родригес
Центр научных исследований и высшего образования Энсенада, Мексика
Мексика
Директор отделения телематики в исследовательском центре CICESE, B.C., Мексика


Чжихуэй Ду
Университет Цинхуа, КНР
Китай
Доцент на факультете Компьютерных наук и технологий университета Цинхуа.


Список литературы

1. Chang C.H., Molahosseini A.S., Zarandi A.A.E., Tay T.F. Residue number systems: A new paradigm to datapath optimization for low-power and high-performance digital signal processing applications. IEEE circuits and systems magazine, vol. 15, № 4, 2015, pp. 26-44.

2. Chervyakov N., Babenko M., Tchernykh A., Kucherov N., Miranda-López V., Cortés-Mendoza J. M. AR-RRNS: Configurable reliable distributed data storage systems for Internet of Things to ensure security. Future Generation Computer Systems, vol. 92, 2019, pp. 1080-1092.

3. Sousa L., Antao S., Martins P. Combining residue arithmetic to design efficient cryptographic circuits and systems. IEEE Circuits and Systems Magazine, vol. 16, № 4, 2016, pp. 6-32.

4. Chervyakov N.I., Lyakhov P.A., Babenko M. Digital filtering of images in a residue number system using finite-field wavelets. Automatic Control and Computer Sciences, vol. 48, № 3, 2014, pp. 180-189.

5. Ye R., Boukerche A., Wang H., Zhou X., Yan B. RESIDENT: a reliable residue number system-based data transmission mechanism for wireless sensor networks. Wireless Networks, vol. 24, № 2, 2018, pp. 597-610.

6. Tchernykh A., Schwiegelsohn U., Talbi E. G., Babenko M. Towards understanding uncertainty in cloud computing with risks of confidentiality, integrity, and availability. Journal of Computational Science, 2016 (in Press), DOI: 10.1016/j.jocs.2016.11.011.

7. Miranda-López V., Tchernykh A., Cortés-Mendoza J.M., Babenko M., Radchenko G., Nesmachnow S., Du Z. Experimental Analysis of Secret Sharing Schemes for Cloud Storage Based on RNS. In Proc. of the Latin American High Performance Computing Conference, 2017, pp. 370-383.

8. Tchernykh A., Babenko M., Chervyakov N., Cortés-Mendoza J. M., Kucherov N., Miranda-López V., Deryabin M., Dvoryaninova I., Radchenko G. Towards mitigating uncertainty of data security breaches and collusion in cloud computing. In Proc. of the 28th International Workshop on Database and Expert Systems Applications (DEXA), 2017, pp. 137-141.

9. Babenko M., Chervyakov N., Tchernykh A., Kucherov N., Shabalina M., Vashchenko I., Radchenko G., & Murga D. Unfairness correction in P2P grids based on residue number system of a special form. In Proc. of the 28th International Workshop on Database and Expert Systems Applications (DEXA), 2017, pp. 147-151.

10. Szabo N.S., Tanaka R.I. Residue arithmetic and its applications to computer technology. N.Y., McGraw-Hill, 1967, 236 p.

11. Bi S., Gross W.J. The mixed-radix Chinese remainder theorem and its applications to residue comparison. IEEE Transactions on Computers, vol. 57. № 12, 2008, pp. 1624-1632.

12. Wang Y. Residue-to-binary converters based on new Chinese remainder theorems. IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, vol. 47, № 3, 2000, pp. 197-205.

13. Dimauro G., Impedovo S., Pirlo G. A new technique for fast number comparison in the residue number system. IEEE transactions on computers, vol. 42, № 5, 1993, pp. 608-612.

14. Burgess N. Scaling an RNS number using the core function. In Proc. of the 16th IEEE Symposium on Computer Arithmetic, 2003. pp. 262-269.

15. Dimauro G., Impedovo S., Modugno R., Pirlo G., Stefanelli R. Residue-to-binary conversion by the" quotient function". IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing. vol. 50. № 8, 2003, pp. 488-493.

16. Pirlo G., Impedovo D. A new class of monotone functions of the residue number system. International Journal of Mathematical Models and Methods in Applied Sciences, vol. 7. № 9, 2013, pp. 803-809.

17. 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, vol. 94. № 9, 2017, pp.1833-1849.

18. Patronik P., Piestrak S.J. Design of Reverse Converters for General RNS Moduli Sets {2^k,2^n-1,2^n+ 1,2^(n+ 1)-1} and {2^k,2^n-1,2^n+ 1,2^(n-1)-1} (n even). IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 61, № 6, 2014, pp.1687-1700.

19. Phatak D.S., Houston S.D. New distributed algorithms for fast sign detection in residue number systems (RNS). Journal of Parallel and Distributed Computing, vol. 97, issue C, 2016, pp. 78-95.

20. Акушский И.Я., Юдицкий Д.И. Машинная арифметика в остаточных классах. М., Советское радио, 1968, 440 c. / Akushsky I. Ya., Yuditsky D. I. Computer arithmetic in residual classes. Moscow, Soviet Radio, 1968, 440 p. (in Russian).

21. Omondi A.R., Premkumar B. Residue number systems: theory and implementation. L., Imperial College Press, 2007, 296 p.

22. Isupov K. An Algorithm for Magnitude Comparison in RNS based on Mixed-Radix Conversion II. International Journal of Computer Applications, vol. 141, № 5, 2016.

23. Van Vu T. Efficient implementations of the Chinese remainder theorem for sign detection and residue decoding. IEEE Transactions on Computers, vol. 100, № 7, 1985, pp. 646-651.

24. Mohan P.A. RNS to binary conversion using diagonal function and Pirlo and Impedovo monotonic function. Circuits, Systems, and Signal Processing, vol. 35, № 3, 2016, pp. 1063-1076.


Рецензия

Для цитирования:


Бабенко М.Г., Черных А.Н., Червяков Н.И., Кучуков В.А., Миранда-Лопес В., Ривера Родригес Р., Ду Ч. Эффективное сравнение чисел в системе остаточных классов на основе позиционной характеристики. Труды Института системного программирования РАН. 2019;31(2):187-201. https://doi.org/10.15514/ISPRAS-2019-31(2)-13

For citation:


Babenko M.G., Tchernykh A., Chervyakov N.I., Kuchukov V.A., Miranda-Lopes V., Rivera Rodriguez R., Du Zh. Efficient Number Comparison in the Residue Number System based on Positional Characteristics. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2019;31(2):187-201. (In Russ.) https://doi.org/10.15514/ISPRAS-2019-31(2)-13



Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)