BINARY EXPONENT DIVISION METHOD FOR CONVERSION OF THE MINIMALLY REDUNDANT MODULAR CODE TO THE POSITIONAL CODE
- Authors: Kolyada A.A1, Chervyakov N.I1, Kuchynski P.V1, Chernyavsky A.F1, Shabinskaya E.V1
-
Affiliations:
- Issue: Vol 12, No 3 (2014)
- Pages: 4-10
- Section: Articles
- URL: https://journals.eco-vector.com/2073-3909/article/view/55915
- ID: 55915
Cite item
Full Text
Abstract
Full Text
Введение. В настоящее время арифметика модулярных систем счисления (МСС) - модулярная арифметика (МА) активно применяется в цифровой обработке сигналов, обработке изображений, в спутниковых, сотовых инфокоммуникацион-ных системах, беспроводных сенсорных сетях, множественном доступе с кодовым разделением каналов, облачных вычислениях, в средствах обнаружения и исправления ошибок, контроля отказов и сбойных ситуаций, криптосистемах, других приложениях. Это обусловлено тем, что кодовый параллелилизм модулярных вычислительных структур (МВС) обеспечивает им ряд существенных преимуществ над позиционными структурами. Практическая реализация данных преимуществ в максимальной мере составляет определяющую стратегию всех проводимых разработок по МВС. Чаще всего модулярные средства обработки информации используются совместно с позиционными. Поэтому эффективность МА-приложе-ний в значительной степени зависит от характеристик сложности и быстродействия применяемых методов и алгоритмов сопряжения разнотипных (по кодовой организации) компонент вычислительных систем, то есть средств позиционно-мо дулярного интерфейса гибридных систем рассматриваемого класса. Представляемые в настоящей статье исследования относятся к проблематике оптимизации процедур образования кода МСС в позиционный код (ПК). Для решения проставленной задачи применен принцип минимально избыточного модулярного кодирования [1]. Ключевой отличительной особенностью минимально избыточных МСС (МИМСС) является использование так называемых интервально-индексных интегральных характеристик модулярного кода (МК), которые отличаются от известных характеристик - ранга, цифр полиадического кода и других [25] предельной простотой базовых расчетных соотношений. Фундаментальные преимущества интервально-индексной технологии синтеза алгоритмов модулярно-позиционного кодового преобразования далее наглядно демонстрируются на примере метода деления на двоичные экспоненты. Особое внимание при этом уделяется оптимизационным аспектам, охватывающим приложения МА на диапазонах больших чисел, и прежде всего криптографические МА-приложе-ния [6-12]. Принцип минимально избыточного модулярного кодирования Введем обозначения: - LflJ и Га! - наибольшее и наименьшее целые числа (ЦЧ) соответственно не большее и не меньшее вещественной величины a; - Ъш = {0;1 ... m-1}, Z“ ={-Lrn/2j; -Ьи/2>1; ... Гт/2І-1} - множества вычетов по натуральному модулю m; - \A\m - элемент кольца Z сравнимый с A (в общем случае рациональным числом) по модулю m; - М = {mû m2 ... ти*} - базис МСС, состоящий из k>1 попарно простых модулей mi;m2 ... mk. В МСС с базисом M ЦЧ X представляется кодом (ХіїХг ••• Х*)(Х/ Н^Ц; І = U). Максимальная мощность множества Dmcc чисел X, на «Инфокоммуникационные технологии» Том 12, № 3, 2014 Коляда А.А., Кучинский П.В., Червяков Н.И., Чернявский А.Ф., Шабинская Е.В. 5 котором отображение X-взаимно к однозначно составляет Мк=^^т( элементов. В этом случае Dmcc выполняет роль диапазона МСС. Обычно в качестве диапазона используют ЪМк или ТГщ . Из Китайской теоремы об остатках следует, что ЦЧ XéDmcc может быть получено по своему МК (Xi.X2»-,Xjfc) с помощью равенства x = ZMi,k-1 Mtk-Ui +Мк_1І(ХУ, (1) і=1 m‘ где M k-l k-l Ylmj’ 7=1 I(X) = Ik(X) - интервальный индекс (ИИ) числа X [1]. Выражение (1) называется интервально-модулярной формой (ИМФ) ЦЧ X. При | иМСС | = Мк МСС с базисом M является неизбыточной. Между тем использование в системах счисления кодовой избыточности, как правило, позволяет существенно улучшить их арифметические и иные свойства [1; 7-9]. Так называемое минимально избыточное модулярное кодирование: Ищшсс ->ZfflixZm2X...xZщ предусматривает применение диапазона БМИМСС, мощность которого меньше мощности диапазона БМСС неизбыточной (классической) МСС с базисом M. Сущность реализуемого принципа раскрывает нижеследующее утверждение. Теорема1.Оминимальноизбыточноммодулярном кодировании. Для того, чтобы в МСС с попарно простыми основаниями mû m2 ... Шк ИИ I(X)=I^X) каждого элемента Х=(%1,%2>-,%к) диапазона Z,2m = {-М, -М+ 1 ... M - 1}, где М = т$Мк_і ; т0 - вспомогательный модуль, полностью определялся компьютерным ИИ - вычетом Ik(X) = \l(X) I , необходимо и достаточно, чтобы к-ое основание удовлетворяло условию: тк > 2то + к - 2 (то > к - 2). При этом для I(X) верны расчетные соотношения: ît (X), если îk (X) < тп ; 1{Х)= h Г 0 (2) Iік (X) - тк » если Ik (X) > т0 ; 1(Х) = 1к(Х) = 2Х*(&) i=1 (3) щ Кі,кШ ~ті1 Mi,lat m, (і Ф к), тк RkAXk) = \мк-іХк\ Переход от МСС с базисом М и ZMk к МИМСС с тем же базисом и диапазоном Х2м предельно упрощает базовой интегральной характеристики модулярного кода (ИХМК) - ИИ I(X) согласно (2)-(4)). Это приводит к адекватной оптимизации и немодульных процедур, базирующихся на ИМФ (1). Количество необходимых таблиц и модульных операций для таких процедур при расчете базовых ИХМК сокращается в к/2 раз [1-2]. С увеличением мощности рабочего диапазона МИМСС получаемый выигрыш становится особенно значимым. Формализация метода деления на двоичную экспоненту для преобразования минимально избыточного модулярного кода в ПК Пусть в МИМСС с базисом М и диапазоном Ъ~гм задано число X = (%û h • •• X*) и пусть требуется получить его представление в ПСС с основанием r - дополнительный r-ичный код (Xn-\Xn-2- *o)r (*7 eZr U = 0,n-1)) длины п. Необходимым условием корректности преобразования (Хь Х2) •••> Цк) ^ (Хп-1Хп-2- хо)г является включение диапазона МИМСС в диапазон -г' і.» +l;... M .2 . .2 . 2 -і ПСС. Из отношения Z2м ^ Х~п вытекает неравенство 2М<гп. Следовательно, дополнительный r-ич-ный ПК должен иметь длину (п>\^%г(2Мк)]} цифр. Поскольку компьютерная позиционная арифметика ЦЧ, в частности в персональных ЭВМ, фактически представляет собой арифметику по модулям вида 2b (b = 8; 16; 32; 64), то в качестве основания базовой ПСС целесообразно использовать гє{28,21 б,232, 264}. Нетрудно видеть, что вычисление выражений вида (1) с использованием (2)-(4) по указанным модулям r в рамках применяемой таблично-сумматорной технологии осуществляется весьма просто. Благодаря реализационным преимуществам ИМФ (1) и отмеченному обстоятельству преобразование МИМК в ПК эффективно может быть выполнено методом деления на двоичную экспоненту - основание r ПСС. Представляемый метод преобразования кода МИМСС в дополнительный r-ичный ПК базируется на операционном кортеже рекурсивного типа: (4) «Инфокоммуникационные технологии» Том 12, № 3, 2014 6 Коляда А. А., Кучинский П.В., Червяков Н.И., Чернявский А.Ф., Шабинская Е.В. (Х0 = X, х0 =1 Х0 |г; = LX/r\, X! =| X! |г; Х2 = |*i /гі; Х2=\х2 \г ... Хй_! = Lx„_2/rJ; (5) хп-\ -\Хп-1 Ir)- На j-ой итерации процесса реализации (5) сначала формируется минимально избыточный модулярный код (МИМК) ЦЧ Xj, а затем находится цифра xj его дополнительного r-ичного ПК путем расширения полученного МИМК на модуль г согласно правилу \Mk-iX\r при Х = 0, то к-1 х]=\х]\г=\Ъмг,к-1 a\j) ;=1 + (6) + \Mk_1I(Xj)\r\rÜ = 0,n-l). Что касается числа Xj, то в соответствии с (5) для цифр его МИМК верна формула ЛЛ - XJ-1 Zi при 7 = 0; 11 X,0'_1) - Xj-1 Ц • k"1 Ц Ц при 7 = 1, /г-1; 0 -1, к). Конкретный выбор способа компьютерной реализации расчетных соотношений (6)-(7) рассматриваемого метода кодового преобразования в первую очередь определяется величиной основания г ПСС. Если r = 28 или r = 216, то вычисление выражений (6) с использованием (7) в рамках таблично-сумматорной технологии, предполагающей ограничение модулей т. МИМСС порогом m_max = 216 (mt < 216 (і = 1, к) ), наиболее просто и эффективно осуществляется с помощью таблиц TMpl і модульного умножения на константы С,- =| г-1 \т, и таблиц TE_i расширения МК. Необходимые таблицы генерируются по правилам: TMplJ [%] =| са \т, (х = О, т( -1; і = 1, к) ; (8) те_i[z\ =\ мік_х і м~1а ц I, ; (Х = 0, т{ - 1; г = 1, Лг - 1), (9) ТЕ_%] = _ (Ю) \МкАх-Щ)\г при Х = Щ>тк-\. Расчетное соотношение (10) базируется на формуле (2) для ИИ ЦЧ в МИМСС. Аргументом таблицы TE_k при фиксированном j служит компьютерный ИИ X = 7(Х ) числа X - см. (6). a J Для вычисления I(Xj) воспользуемся таблицами ИИ - TII і, в которых хранятся наборы вычетов вида (4) согласно правилу TIIJ [х] - fyjc (х) (х - 0, rrii -l;i-l,k). (11) С учетом (11) из (3)-(4) для компьютерного ИИ Ik(Xj) следует расчетное соотношение h(Xj) = £тп_і[хР] і=1 (12) щ Таблично-сумматорная технология предполагает получение модульных сумм (12) аккумулятивно-табличным методом [10]. Это требует использования еще двух таблиц: (7) TRes _ црад =|216x|mt (х = 0, 216-1), TRes&[x] =|х\т (х = 0, 216 +тк-2) (13) ™к для приведения ЦЧ к остаткам по модулю тк. Таблично-сумматорная алгоритмизация схемы деления на двоичную экспоненту для преобразования МИМК в ПК Из изложенных базовых положений метода деления на двоичную экспоненту и принципов его компьютерной реализации вытекает нижеследующий алгоритм преобразования кода МИМСС в ПК. Параметры алгоритма: модули т\, т2,..., Шк МИМСС, выбираемые из множества простых чисел промежутка (215; 216) с минимизацией к [10], и основание r = 2b (b=16 бит) используемой ПСС. Входные данные алгоритма: МИМК (Хь Хъ ... %к) произвольного элемента X диапазона Х‘2М. Выходные данные: дополнительный r-ичный код (хп-\хп-2••• хо)г длины п = Г1оёД2М)1 ЦЧ X. Предварительно получаемые данные: константы Сх=\г~1\т, (i = l,k), а также таблицы ТМрІ г, ТЕ /, ТП г (i = l,k), TRes UPA: и TRes& - см. (8)-(11) и (13). «Инфокоммуникационные технологии» Том 12, № 3, 2014 Коляда А.А., Кучинский П.В., Червяков Н.И., Чернявский А.Ф., Шабинская Е.В. 7 Тело алгоритма модулярно-позиционного кодового преобразования по методу деления на основание ПСС с применением таблиц расширения МИМК. МП_Д.1. Положить Х0 =(%l(0),Z20)’-’ xi0)) = (Xi,%2>-> Hk)- МП_Д.2. Порядковому номеру очередной цифры дополнительного r-ичного кода ЦЧ X присвоить начальное значение j = 0. МП_Д.3. В соответствии с (6) с помощью таблиц (9), (10) расширить МК (хР>хР>-> хР) числаX. (см. (5), (7)) на основание r ПСС, выполняя операции: МП_Д.3а. Применяя таблицы (11), вычислить входящую в расчетное соотношение (12) сумму * = Ітп_г-[ХР]. i=l МП_Д.3б. Получить компьютерный ИИ ЦЧ X приводя s к остатку по модулю тк согласно правилу î{Xj) =| s \щ = TRes^[s(0) + TRes_UP£[s(1)]] О(0) = = sa(216-\), sm=s» 16. МП_Д.3в. Вычислить j-ую цифру дополнительного r-ичного ПК входного числа: XJ =|ZTE_/[xP)] + TE_A:[/(X7.)]|,. (14) i=1 МП_Д.4. По достижении равенства j = n - 1 завершить работу алгоритма. МП_Д.5. Инкрементировать переменную j (j = j + 1). МП_Д.6. Следуя (7), сформировать МИМК (хР> хР»-» хР) числа Xj =\_Xj-\!r\, реализуя для всех i - \,k операционную последовательность: МП_Д.6а. Найти х = хР ^ ~xj-\ ■ МП_Д.6б. Если X < 0 j то положить X = X + Щ. В противном случае - перейти к МП_Д.6г. МП_Д.6в. При х<0 текущее значение переменной X нарастить на ( X - X + Щ )• МП_Д.6г. Из таблицы TMpl_/ (см. (8)) по адресу X искомое значение /-ой цифры МК числа Xj: хР = TMplJtx]. МП_Д.7. Перейти к МП_Д.3. Для временных затрат на выполнение в ПЭВМ модулярно-позиционного кодового преобразования с помощью процедуры МП_Д.1-МП_Д.7 справедлива оценка: *мп_д.пэвм(^>п) - 2(2кп-к-и)/сл + (15) + (к(п -1) + 5n)t4 , где /сл и t4 - длительности операций сложения и чтения двухбайтового слова из таблицы соответственно. Объем памяти для таблиц, используемых в алгоритме МП_Д.1-МП_Д.7, не превышает Мхмп^(*)Л(А; + 1)Мб. (16) О Предположим, что полумощность M диапазона МИМСС удовлетворяет условию M >21024. В этом случае минимальное число к оснований базиса M принимает значение к = 65 [10]. Согласно теореме 1 2/wo< miç- к + 2. Поэтому ввиду Ші< г (і = 1,к) неравенство 2М<гр, обеспечивающее минимум разности rn - 2M, достигается при n < к. Пусть n = к = 65, тогда оценочные выражения (15)-(16) в случае tл = 2 нс, t4 = 1,14 нс дают: ^мп_д.пэвм(65,65) = 38392,9 не, ■^т.мп_д = 24,75 Мб. Приведем оценки (15)-(16) для еще одной конфигурации алгоритма МП_Д. 1 - МП_Д.7, которая определяется условием M >22462. Отвечающая данному равенству МИМСС имеет к = 155 оснований; и при n = к = 155, t = 2 нс, t4 = 1,14 нс искомые значения характеристик (15)-(16) составляют: ^мп_д.пэвм(155,155) = 219055,3 нс, MT Mnjj = 59,5 Мб. Пусть теперь г є {232, 2м}. Так как в этом случае цифры r-ичного ПК (х„_1д:и_2... х0)г достаточно велики, то при реализации (7) они должны быть преобразованы в остатки по модулям ш;. Для выполнения операции Xj-\-* \ Xj_\ \т, воспользуемся представлением ЦЧ Xj_\ eZr в ПСС с основанием г = 2 (Ь =16 бит) : Y _ (Лп-\) (п-2) (0)ч _ 7-І “ \xj-\ j-\ -xj-\)7~ = Z4-1F/ = 4-і +r(xj\ + r(...r(xf_-l2) + (17) 1=0 + г(4”р))...)) (п=ЫЬ; Вычисление выражений вида (17) по модулям т/ весьма просто осуществляется с помощью таблиц TRes _ UPz'fjc] = І гх \щ, TReszfjc] =| x \m. - - (18) (jc = 0,r +m, -2); i = \,k). «Инфокоммуникационные технологии» Том 12, № 3, 2014 8 Коляда А. А., Кучинский П.В., Червяков Н.И., Чернявский А.Ф., Шабинская Е.В. Искомое расчетное соотношение для остатков %Р ^ =| Xj_i I , базирующееся на (17)-(18), имеет вид уО-1) = ы JResi[xf\ + TResJJPzIx^,]], если r = 232, TResilxf\+TResJJPilxf\+TResJJPi[xf\ + (19) + TRes_UPz'[;e^1]]]], если г = 264, (І - 1,&) . Поскольку с увеличением разрядности p основания r используемой ПСС длина n кода (xn_iXn_2... Xq)t уменьшается, причем достигаемое за счет этого сокращение временных затрат на преобразование МИМК в ПК при достаточно большом r становится более значимым, чем их возрастание, обусловленное выполнением операций (19), то с точки зрения проблемы повышения скорости процедур модулярно-позиционного ко -дового преобразования рассматриваемого класса весьма эффективным является совместное использование таблиц TE_/ (i = l,&) расширения кода и ПСС с большими основаниями. Модификация алгоритма преобразования МИМК в ПК, реализующая обозначенную концепцию, заключается в нижеследующем. Параметры алгоритма: модули m1, m2, ..., mkбазовой МИМСС, основание r=2b (йє{32, 64}) используемой ПСС и основание г -2Ь (Ь -16 бит) ПСС для представления цифр дополнительного r-ичного ПК. Входные данные алгоритма: МИМК (Хъ Ил, ... %к) ЦЧXиз диапазона Ъ~1М . Выходные данные: дополнительный r-ич-ный код (хп_ххп_2... Х0)г длины n = \\ogr{2M)\ числа X. Предварительно получаемые данные: таблицы TMplz, TEz, THz, TRes UP/ и TResz ( i = \,k), формируемые согласно (8)-(11) и (18). Тело алгоритма модулярно-позиционного ко -дового преобразования с применением таблиц расширения МИМК на модули r разрядностью b=32, 64 бита. _МП_Д.1. Положить ^o=(xi(0);%20) - xi0))=(xi;x2 - х*)- _МП_Д.2. Порядковому номеру очередной цифры ПК числа X присвоить начальное значение: у=0. _МП_Д.3. С помощью соотношения (6) и таблиц (9), (10) расширить МИМК (хР^Хр0 ••• Х*°) числа Xj (см. (5), (7)) на основание г ПСС, выполняя операции: _МП_Д.3а. Применяя таблицы (11) и (18), вычислить компьютерный ИИ /(Ху) ЦЧ Xj, определяемый по расчетному соотношению (12), согласно схеме: Is = ^TII_z'[%P]; 5^°-) - sл(г -1), = s»b; i=i I(X,) =| ^ I = TResÆ[s(0) + TRes UPÆ|>W]]). J mk / _МП_Д.3б. Найти j-ую цифру ПК (хп_ххп_2... х0)г исходного ЦЧXпо правилу: Ді)і к-1 Xj =| ^ ТЕ _ i[%j ] + ТЕ _ k[I(Xj )] |г. 1=1 _МП_Д.4. При j=n-1 завершить работу алгоритма. _МП_Д.5. Переменную j увеличить на 1 (/=/+1). МП Д.6. Согласно (7) сформировать МИМК (Хр\ Хр^-ОСр^ числа Ху=[_Ху_і/г_|, реализуя для і = \,к действия: _МП_Д.6а. По формуле (19) выполнить преобразование Xj_x -> (хР-1^ • _МП_Д.6б. Найти % - хР_1^ -хР_1) . _МП_Д.6в. Если Х<0> то положить Х = Х + ™г- _МП_Д.6г. Получить искомое значение /-ой цифры МИМК числа Xf. %р^ = ТМр1_/[%]. _МП_Д.7. Перейти к шагу _МП_Д.3. При реализации на ПЭВМ алгоритм _ МП_Д.1-_МП_Д.7 требует временных затрат £ *_]Ш_д.пэвм(^и>^)= Л(^сл + 4ґч + + b + *сл(*) + (к~ 2)тах{ТтЦ,/сл(6)}) + (20) ъ +к(п - 1)(/по(*) + 2/Сл + *ч) > где t- время чтения двухбайтового слова из таблицы; t (b) - время сложения двух b-битовых ЦЧ; t^ =сл (32); tПО (b) - длительность операции приведения к остатку цифры r-ичного ПК по модулю m. (i-l,k) МИМСС. Из (19) следует, что Г/сл + 2t4 при b - 32 бита, /по(6)Н„ „ , ^ _ (21) [3/сл + 4/ч при b = 64 бита. Быстродействие современных схем сложения несущественно зависит от разрядности b. С учетом этого положим tUb) = ten. «Инфокоммуникационные технологии» Том 12, № 3, 2014 Коляда А.А., Кучинский П.В., Червяков Н.И., Чернявский А.Ф., Шабинская Е.В. 9 Пусть b = 32 бита, а мощность диапазона Z 2м МИМСС удовлетворяет условию 2M > 2-21024. В этом случае к = 65, п = 33 и оценка (20) с учетом (21) при їл = 2 нс, їц = 1,14 нс принимает значение *_мп^.пэвм (65,33,32) - 28990,68 нс.В случае, когда b = 64 бита, 2M > 21025, длина r-ичного ПК составляет 17 цифр и t мпл.пэвм (65,17,64) = 236883 нс. Если мощность диапазона МИМСС удовлетворяет условию 2M > 2-22462, которому отвечает к = 155, то при b = 32 бита длина r-ич-ного ПК составляет п = 77 цифр и t мп_д.пэвм (155,77,32) = 162554,52 нс. В случае, когда b = 64 бита, код ПСС с основанием r =264 имеет длину п = 39 цифр и f_Mnjj.roBM (155,39,64) = 132384,04 нс. Объем табличной памяти для алгоритма _ МП_Д_1-_МП_Д_7 не превышает Мт мп_д,(к>Ь) = к■ 217(6 + Ь/16) байт. (22) Для пар (*,*) = (65,32); (65,64); (155,32); (155,64) оценка (3.61) принимает значения: Мт._мп_д (65,32) = 65 Мб; -^т._мп_д (65,64) = 81,25 Мб; ^т._мпл(155,32) = 155 Мб; •Л/т мп_д (155,64) = 193,75 Мб. Приведенные оценочные данные по производительности и суммарному объему табличной памяти для приведенных конфигураций алгоритмов преобразования МИМК в ПК по методу деления на основание r ПСС позволяют заключить, что с ростом r четко просматривается тенденция к увеличению скорости осуществляемого преобразования. При рассматриваемых значениях параметров к и b (£є{65, 155}, èe {16, 32, 64}) характер и уровень достигаемого повышения производительности наглядно иллюстрируют ко -эффициенты: ?мп_д.пэвм (65,65,16)/^ мп_дпэвм (65,33,32) = 1,3; ?мп_д.пэвм (65,65,16)/^ мп_д.пэвм (65,17,64) -1,6; ?мп_д.пэвм (155,155,16)/мп_д.пэвм (155,77,32) = = 1,35; ?мп_^.пэвм (155,155,16)/ ^_мпл .пэвм (155,39,64) = = 1,7. Благодаря возможности применения принципа обобществления таблиц при формировании базового КТ системы, что допускает использование одних и тех же таблиц разными немодульными процедурами, сопровождаемое отмеченный рост быстродействия алгоритмов модулярно-позиционного кодового преобразования, увеличение объема необ ходимой табличной памяти фактически оказывается несущественным и для МА-приложений вполне приемлемо. Заключение Наиболее значимые результаты представленной разработки по оптимизации методологических и алгоритмических средств модулярно-позиционного кодового преобразования кратко можно охарактеризовать следующим образом. 1. Проведена математическая формализация метода деления ЦЧ в МСС на двоичную экспоненту, который положен в основу процедур модулярно-позиционного кодового преобразования. Главной отличительной особенностью реализуемого подхода при синтезе процедур исследуемого класса является применение минимально избыточного модулярного кодирования. Это позволяет сократить объем табличной памяти и временные затраты, приходящиеся на вычисление базовых интегральных характеристик МК в к/2 раз. 2. Синтезированы два новых алгоритма модулярно-позиционного кодового преобразования. Один из них ориентирован на ПСС с основанием r = 216, а другой - на ПСС с основаниями r = 232 и 264. Алгоритм с r = 216 прост в реализации, но формирует ПК максимальной длины. С увеличением r количество цифр ПК уменьшается. При этом, однако, в реализуемом вычислительном процессе на каждой итерации выполняется операция приведения последней полученной цифры ПК к остаткам по модулям МСС, что снижает производительность соответствующего алгоритма. 3. Исследована эффективность компьютерной реализации рекурсивной схемы деления на основание ПСС в рамках двух стратегий, первая из которых предполагает расширение МК преимущественно с помощью системных средств, а вторая с использованием таблиц расширения. Анализ разработанных конфигураций процедур преобразования МИМК в ПК с точки зрения проблемы повышения производительности при установленном верхнем пороге для размера табличной памяти показывает, что оптимальный результат достигается в случае совместного применения таблиц расширения и ПСС с большими основаниями r. При r = 264 получаемый выигрыш в быстродействии (в сравнении r = 216, 232) является (1,3-1,7)-кратным.About the authors
A. A Kolyada
Email: razan@tut.by
N. I Chervyakov
Email: niipfp@bsu.by
P. V Kuchynski
Email: k-fmf-primath@stavsu.ru
A. F Chernyavsky
Email: niipfp@bsu.by
E. V Shabinskaya
Email: shabinskaya@rambler.ru
References
- Коляда А.А., Пак И.Т. Модулярные структуры конвейерной обработки цифровой информации. Мн.: Университетское, 1992. - 256 с.
- Коляда А.А., Чернявский А.Ф. Интегрально-характеристическая база модулярных систем счисления // Информатика. №1, 2013. - С. 106-119.
- Червяков Н.И., Лавриненко А.Н. Исследования немодульных операций в системе остаточных классов // Научные ведомости БелГУ. Сер.: История. Политология. Экономика. Информатика. Вып. 21/1, №1 (120), 2012. - С. 110-121.
- Siewobr H., Gbolade K.A. Modulo operation free reverse conversion in the {22n+1-1, 22n, 22n-1} moduli set // Int. J. of Computer Applications. Vol. 85, N1, 2014. - P. 11-14.
- Исупов К.С. Алгоритм вычисления интервально-позиционной характеристики для выполнения немодульных операций в системах остаточных классов // Вестник ЮжУрГУ. Сер.: Компьютерные технологии, управление, радиоэлектроника. Вып. 1, Т.14, 2014. - С. 89-97.
- Инютин С.А. Основы модулярной алгоритмики. Ханты-Мансийск: Полиграфист, 2009. - 347 с.
- Чернявский А.Ф., Коляда А.А., Коляда Н.А. и др. Умножение по большим модулям методом Монтгомери с применением минимально избыточной модулярной арифметики // Нейрокомпьютеры: разработка, применение. № 9, 2010. - С. 3-8.
- Коляда А.А., Чернявский А.Ф. Умножение по большим модулям с использованием минимально избыточной модулярной схемы Монтгомери // Информатика. №3, 2010. -С. 31-48.
- Каленик А.Н., Коляда А.А., Коляда Н.А., Чернявский А.Ф., Шабинская Е.В. Умножение и возведение в степень по большим модулям с использованием минимально избыточной модулярной арифметики // Информационные технологии. №4, 2012. - С. 37-44.
- Каленик А.Н., Коляда А.А., Коляда Н.А., Протько Т.Г., Шабинская Е.В. Компьютерно-арифметическая и реализационная база быстрых процедур умножения по большим модулям на основе модифицированной модулярной схемы Монтгомери // Электроника инфо. №7, 2012. -C. 114-118.
- Червяков Н.И., Евдокимов А.А., Галушкин А.И. и др. Применение искусственных нейронных сетей и системы остаточных классов в криптографии. M.: Физматлит, 2012. - 280 с.
- Tao Wu, Shoguo Li, Litian Liu. Improved RNS Montgomery modular multiplication with residue recovery // Proc. Int. Cons. on Soft. Computing Techniques and Engineering Application Advances in Intelligence Systems and Computing. Vol. 250, 2014. - P. 233-245.