BINARY EXPONENT DIVISION METHOD FOR CONVERSION OF THE MINIMALLY REDUNDANT MODULAR CODE TO THE POSITIONAL CODE

Abstract


The paper is dedicated to the optimization procedures of the modular-positional conversion, which are based on the binary exponent division method. The optimization provides minimization of summary time spent and applying of accessible memory for tables. It is achieved by using of minimally redundant modular coding, and number systems with large bit radix, as well as the table-summatory technology of calculation.

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)-кратным.

References

  1. Коляда А.А., Пак И.Т. Модулярные структуры конвейерной обработки цифровой информации. Мн.: Университетское, 1992. - 256 с.
  2. Коляда А.А., Чернявский А.Ф. Интегрально-характеристическая база модулярных систем счисления // Информатика. №1, 2013. - С. 106-119.
  3. Червяков Н.И., Лавриненко А.Н. Исследования немодульных операций в системе остаточных классов // Научные ведомости БелГУ. Сер.: История. Политология. Экономика. Информатика. Вып. 21/1, №1 (120), 2012. - С. 110-121.
  4. 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.
  5. Исупов К.С. Алгоритм вычисления интервально-позиционной характеристики для выполнения немодульных операций в системах остаточных классов // Вестник ЮжУрГУ. Сер.: Компьютерные технологии, управление, радиоэлектроника. Вып. 1, Т.14, 2014. - С. 89-97.
  6. Инютин С.А. Основы модулярной алгоритмики. Ханты-Мансийск: Полиграфист, 2009. - 347 с.
  7. Чернявский А.Ф., Коляда А.А., Коляда Н.А. и др. Умножение по большим модулям методом Монтгомери с применением минимально избыточной модулярной арифметики // Нейрокомпьютеры: разработка, применение. № 9, 2010. - С. 3-8.
  8. Коляда А.А., Чернявский А.Ф. Умножение по большим модулям с использованием минимально избыточной модулярной схемы Монтгомери // Информатика. №3, 2010. -С. 31-48.
  9. Каленик А.Н., Коляда А.А., Коляда Н.А., Чернявский А.Ф., Шабинская Е.В. Умножение и возведение в степень по большим модулям с использованием минимально избыточной модулярной арифметики // Информационные технологии. №4, 2012. - С. 37-44.
  10. Каленик А.Н., Коляда А.А., Коляда Н.А., Протько Т.Г., Шабинская Е.В. Компьютерно-арифметическая и реализационная база быстрых процедур умножения по большим модулям на основе модифицированной модулярной схемы Монтгомери // Электроника инфо. №7, 2012. -C. 114-118.
  11. Червяков Н.И., Евдокимов А.А., Галушкин А.И. и др. Применение искусственных нейронных сетей и системы остаточных классов в криптографии. M.: Физматлит, 2012. - 280 с.
  12. 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.

Statistics

Views

Abstract - 25

PDF (Russian) - 3

Cited-By


Article Metrics

Metrics Loading ...

Copyright (c) 2014 Kolyada A.A., Chervyakov N.I., Kuchynski P.V., Chernyavsky A.F., Shabinskaya E.V.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies