Научный журнал

Современные наукоемкие технологии

ISSN 1812-7320

"Перечень" ВАК

ИФ РИНЦ = 0,940

• Авторы
• Резюме
• Файлы
• Ключевые слова
• Литература

Коржавина А.С. 1 Князьков В.С. 1

---

1 ФГБОУ ВО «Вятский государственный университет»

Расширение базиса системы остаточных классов – одна из наиболее важных немодульных операций, которая используется, когда необходимо выполнить расширение диапазона представления чисел дополнительными модулями или полную смену базиса, а также при выполнении операции деления и масштабирования, сравнения, контроля четности, определения знака или абсолютной позиционной величины числа. В работе проводится обзор методов расширения базиса, основанных на вычислении коэффициентов системы счисления со смешанными основаниями, и анализ их вычислительной сложности с целью выбора направления для разработки метода расширения базиса, имеющего оптимальное соотношение времени выполнения и аппаратных затрат. Методы расширения базиса, основанные на вычислении коэффициентов системы счисления со смешанными основаниями, наиболее целесообразно использовать для массового выполнения операций расширения базиса, полной или частичной смены базиса.

Статья в формате PDF

0 KB

система остаточных классов

расширение базиса системы остаточных классов

система счисления со смешанными основаниями

1. Gerard B., Kammerer J.-G., Merkiche N. Contributions to the Design of Residue Number System Architectures // Proceedings of the 22nd IEEE International Symposium on Computer Arithmetic. – France, 2015. – Р. 105–112.

2. Szabo N., Tanaka R. Residue Arithmetic and Its Applications to Computer Technology. – NY: McGraw Hill, 1967. – 236 p.

3. Omondi A., Premkumar B. Residue Number Systems: Theory and Implementation. – London: Imperial College Press, 2007. – 296 p.

4. Czyzak M., Smyk R., Ulman Z. Pipelined scaling of signed residue numbers with the mixed-radix conversion in the programmable gate array // Poznan University of Technology Academic Journals. Electrical Engineering. – 2013. – no. 8. – Р. 89–99.

5. Cardarilli G.C., Nannarelli A., Re M. Residue number system for low-power DSP applications // Proc. of 41st Asilomar Conference on Signals, Systems, and Computers, IEEE. – 2007. – Р. 1412–1416.

6. Bigou K. Tisserand A. RNS modular multiplication through reduced base extensions // In Proc. 25th IEEE International Conference on Application-specific Systems, Architectures and Processors (ASAP), IEEE. – 2014. – Р. 57–62.

7. Bajard J.C., Eynard J., Merkiche N. Montgomery reduction within the context of residue number system arithmetic // Journal of Cryptographic Engineering. – 2017. – Р. 1–12.

8. Hitz M., Kaltofen E. Integer division in Residue Number Systems // IEEE Trans. on Computers. – 1995. – vol. 44(8). – Р. 983–989.

9. Sachenko A., Zhengbing H., Yatskiv V. Increasing the data transmission robustness in WSN using the modified error correction codes on residue number system // Elektronika i Elektrotechnika. – 2015. – vol. 21(1). – Р. 76–81.

10. Xiao H., Garg H. K., Hu J., Xiao G. New Error Control Algorithms for Residue Number System Codes // ETRI Journal. – 2016. – vol. 38(2). – Р. 326–336.

11. Kawamura S. I., Yonemura T., Komano Y., Shimizu H. Exact Error Bound of Cox-Rower Architecture for RNS Arithmetic // IACR Cryptology ePrint Archive. – 2016. – Р. 266.

12. Akkal M., Siy P. A new mixed radix conversion algorithm MRC-II // Journal of Systems Architecture. – 2007. – vol. 53(9). – Р. 577–586.

13. Gbolagade K.A., Cotofana S.D. An O (n) residue number system to mixed radix conversion technique // IEEE International Symposium on Circuits and Systems (24–27 May, 2009), IEEE. – 2009. – Р. 521–524.

14. Huang C.H. Fully parallel mixed-radix conversion algorithm for residue number applications // IEEE Trans. Comput. – 1983. – vol. 32(4). – Р. 398–402.

15. Mohan P.V. Residue Number Systems // Theory and Applications. Springer. – 2016. – 351 p.

Система остаточных классов (СОК) – это непозиционная система счисления, которая позволяет заменить последовательные методы выполнения арифметических операций над «длинными» целыми числами в позиционных системах счисления на параллельные методы выполнения арифметических операций над наборами «коротких» целых чисел [1–3]. Преимуществом СОК является простота выполнения операций сложения, вычитания, умножения (так называемых модульных операций) по сравнению с арифметикой в позиционных системах счисления, а существенным недостатком – сложность выполнения немодульных операций, таких как операции масштабирования, деления, определения знака, сравнения и определения переполнения диапазона представления чисел и т.д. Другим существенным преимуществом вычислений с применением СОК является более простая аппаратно-техническая реализация вычислительных устройств и, как следствие, их более низкое энергопотребление по сравнению с устройствами на основе вычислений в позиционных системах счисления. Учитывая особенности организации вычислений в СОК, их применение наиболее эффективно для решения задач, алгоритмизация которых реализована с существенным преобладанием модульных операций, например, задач цифровой обработки сигналов [4, 5], криптографии [6, 7].

Одной из важных и сложно реализуемых операций является операция расширения базиса СОК, которая необходима для выполнения операций расширения диапазона представления чисел, например, при реализации алгоритма Монтгомери в приложениях криптографии [6, 7], деления и масштабирования [4, 8], контроля ошибок вычислений [9, 10].

Задача расширения базиса

Система остаточных классов является непозиционной системой счисления, в которой значения позиционного числа A число представлено набором n остатков от деления числа A на каждый из n модулей [1–3]:

,

где – целая часть частного , – набор оснований или базис СОК.

Произведение определяет диапазон представления чисел в СОК, причем, если все числа являются попарно взаимно простыми, то между любым положительным целым числом A из диапазона [0; P) и числом, представленным в СОК, имеется взаимно однозначное соответствие.

Расширение базиса, или смена базиса – это процедура, в которой осуществляется поиск значения числа в СОК с новыми основаниями , представленного изначально в виде в СОК с основаниями . Частным случаем является вычисление остатка от деления числа, представленного в СОК, по новому основанию pn+1. Для вычисления остатка от деления xn+1 числа, представленного в СОК, по новому основанию pn+1, используются два подхода: вычисление xn+1 с помощью Китайской теоремы об остатках (КТО) [11] и вычисление коэффициентов системы счисления со смешанными основаниями [2, 8, 12–15].

Система счисления со смешанными основаниями

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

. (1)

Точный метод определения остатка от деления по новому модулю, основанный на преобразовании числа в СССО, был предложен Сабо и Танакой [2]:

, (2)

где , вычислены заранее и занесены в таблицу.

Таким образом, для вычисления остатка от деления по новому модулю pn+1 необходимо сначала вычислить коэффициенты СС со смешанными основаниями , затем вычислить остаток от деления по формуле (2).

Вычислительная сложность методов расширения базиса на основе вычисления коэффициентов системы счисления со смешанными основаниями

Коэффициенты представления вычисляются следующим образом [2]:

,

,

,

…

. (3)

Рис. 1. Схема конвейеризированного метода Сабо и Танаки [14]

Рис. 2. Схема параллельного метода Хуанга [14]

Для вычисления коэффициентов по формулам (3) требуется выполнение операций модулярного вычитания и столько же операций модулярного умножения [2].

Методы, представленные в работах [12, 13], основаны на классических методах [2], имеющих сложность O(n2), и ориентированы на оптимизацию числа арифметических операций.

Параллельные методы [8, 14, 15] также основаны на классических методах [2] и позволяют сократить время вычисления коэффициентов за счет введения дополнительных вычислительных устройств. Например, Хуангом [14] предложен конвейеризированный метод Сабо и Танаки [2] (рис. 1), а также параллельный алгоритм преобразования в систему счисления со смешанными основаниями, использующий дополнительные подстановочные таблицы (рис. 2). На рисунках использованы следующие обозначения: R – регистр для хранения промежуточных результатов, fij – функциональный блок, состоящий из вычитателя («–») и таблицы (T), T – подстановочная таблица, С – каналы передачи единиц переноса, ADD mod pi – каскадные сумматоры по модулю pi.

В [14] время выполнения представлено как (где tT – время выборки из таблицы, tA – время выполнения операции сложения), что, как было показано в [8], не достигается в связи с формированием переносов. Данный метод был улучшен в [8] за счет введения дополнительных умножителей, сложность алгоритма при этом показана как O(log n). Схема формирования коэффициентов СС со смешанными основаниями [8] представлена на рис. 3. Использованы следующие обозначения: mij – значения коэффициентов СС со смешанными основаниями для чисел , вычислены заранее и хранятся в таблицах, *i – умножители по модулю pi, ADD mod pi – каскадные сумматоры по модулю pi, С – каналы передачи единиц переноса, ADD – позиционный двоичный каскадный сумматор для формирования старшей единицы переноса.

Алгоритм Чакраборти и др. [15] использует каскадную схему подстановочных таблиц и сумматоров, при этом таблицы имеют два входа и два выхода, таким образом, таблиц в общей сложности требуется меньше. При конвейерной обработке время преобразования равно времени выборки из таблицы плюс время одного модулярного сложения. Метод хорошо работает для разрядности модулей 4–6 бит, поскольку при большей разрядности значительно увеличивается объем подстановочных таблиц. Параллельный алгоритм Миллера и МакКормика [15] использует только подстановочные таблицы и основан на решении линейных диофантовых уравнений. Алгоритм медленнее, чем [14], однако он не требует дополнительных арифметических устройств, и в случае конвейерной обработки время одного преобразования равно времени выборки из таблицы.

В таблице представлены следующие характеристики наиболее быстрых методов вычисления коэффициентов СС со смешанными основаниями [2, 8, 14, 15]: количество и объем требуемых подстановочных таблиц, сумматоров/вычитателей (ADD/SUB) и модулярных умножителей (MUL), а также время выполнения; при этом использованы следующие обозначения: n – количество модулей, tT – время выборки из таблицы, tA – время выполнения операции сложения/вычитания, tM – время выполнения операции умножения.

Характеристики методов вычисления коэффициентов СССО

Библиографическая ссылка