Научный журнал
Современные наукоемкие технологии
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,909

МЕТОДЫ РАСШИРЕНИЯ БАЗИСА В СИСТЕМЕ ОСТАТОЧНЫХ КЛАССОВ: ОБЗОР И АНАЛИЗ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ

Коржавина А.С. 1 Князьков В.С. 1
1 ФГБОУ ВО «Вятский государственный университет»
Расширение базиса системы остаточных классов – одна из наиболее важных немодульных операций, которая используется, когда необходимо выполнить расширение диапазона представления чисел дополнительными модулями или полную смену базиса, а также при выполнении операции деления и масштабирования, сравнения, контроля четности, определения знака или абсолютной позиционной величины числа. В работе проводится обзор методов расширения базиса, основанных на вычислении коэффициентов системы счисления со смешанными основаниями, и анализ их вычислительной сложности с целью выбора направления для разработки метода расширения базиса, имеющего оптимальное соотношение времени выполнения и аппаратных затрат. Методы расширения базиса, основанные на вычислении коэффициентов системы счисления со смешанными основаниями, наиболее целесообразно использовать для массового выполнения операций расширения базиса, полной или частичной смены базиса.
система остаточных классов
расширение базиса системы остаточных классов
система счисления со смешанными основаниями
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 остатков korg01.wmf от деления числа A на каждый из n модулей korg02.wmf [1–3]:

korg03.wmf,

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

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

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

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

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

korg20.wmf. (1)

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

korg21.wmf, (2)

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

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

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

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

korg27.wmf,

korg28.wmf,

korg29.wmf,

korg30.wmf. (3)

korgavin1.tif

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

korgavin2.tif

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

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

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

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

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

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

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

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

Метод

Количество и объем таблиц

ADD/SUB

MUL

Время вычисления

korg36.wmf

Сабо, Танака [2], классические

korg37.wmf

korg38.wmf

korg39.wmf

Сабо, Танака [2], конвейеризированный

korg40.wmf, korg41.wmf

korg42.wmf

korg43.wmf

Хуанг [14]

korg44.wmf, korg45.wmf

korg46.wmf

korg47.wmf

Хитц, Калтофен [8]

korg48.wmf, korg49.wmf

korg50.wmf

korg51.wmf

korg52.wmf

Чакраборти и др. [15], последовательный

korg53.wmf, korg54.wmf

korg55.wmf

korg56.wmf

Чакраборти и др. [15], параллельный

korg57.wmf, korg58.wmf

korg59.wmf

korg60.wmf

Миллер [15]

korg61.wmf, korg62.wmf

korg63.wmf

 

korgavin3.tif

Рис. 3. Схема работы алгоритма Хитц, Калтофен [8]

Как видно из таблицы, самые быстрые методы вычисления коэффициентов СС со смешанными основаниями требуют O(n2) арифметических устройств и подстановочных таблиц, время же вычисления коэффициентов ограничивается O(log n).

Вычисление остатка от деления по формуле (2) требует n модулярных умножителей, работающих параллельно и (n – 1) модулярных сумматоров, включенных по каскадной схеме, при этом время вычисления составляет korg64.wmf [8] или один модулярный умножитель с накоплением (состоящий из одного умножителя по модулю, одного сумматора по модулю и регистра для хранения промежуточного результата), время при этом составляет korg65.wmf. Общее время выполнения операции расширения базиса методом [8] составляет korg66.wmf, при этом для его реализации потребуется korg67.wmf подстановочных таблиц, korg68.wmfмодулярных сумматоров/вычитателей, korg69.wmf модулярных умножителей, m – количество дополнительных модулей, на которые необходимо расширить базис.

Заключение

Для преобразования числа x1,x2,…,xn, представленного в СОК с основаниями korg70.wmf к xn+1 ,xn+2, …, xn+m в СОК с основаниями pn+1, pn+2, …, pn+m, необходимо вычислить коэффициенты СС со смешанными основаниями korg71.wmf, затем m раз вычислить остатки от деления по модулям pn+1, pn+2, …, pn+m по формуле (2). Вычисления остатка от деления по каждому модулю независимы и могут быть выполнены параллельно.

В качестве дальнейшего направления исследований планируется разработка метода расширения базиса, имеющего оптимальное соотношение времени выполнения и аппаратных затрат, основанного на том, что при вычислении коэффициентов СС со смешанными основаниями на каждом шаге последовательно вычисляется очередной разряд korg72.wmf, который может сразу же использоваться для вычисления остатка по формуле (2). Таким образом, можно совместить во времени процесс получения коэффициентов korg73.wmf и вычисления остатков от деления.

Методы расширения базиса, основанные на вычислении коэффициентов системы счисления со смешанными основаниями, наиболее целесообразно использовать для массового выполнения операций расширения базиса, полной или частичной смены базиса. Для вычисления единичного остатка от деления по новому основанию лучше выбирать способы, позволяющие максимально быстро вычислить остаток, например, [8], или методы, основанные на Китайской теореме об остатках [11]. В случае использования метода [8] необходим дополнительный анализ целесообразности его использования, поскольку аппаратные затраты для его реализации достаточно велики.


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

Коржавина А.С., Князьков В.С. МЕТОДЫ РАСШИРЕНИЯ БАЗИСА В СИСТЕМЕ ОСТАТОЧНЫХ КЛАССОВ: ОБЗОР И АНАЛИЗ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ // Современные наукоемкие технологии. – 2017. – № 12. – С. 37-42;
URL: http://www.top-technologies.ru/ru/article/view?id=36868 (дата обращения: 08.12.2019).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074