Устройство для умножения в системе остаточных классов Советский патент 1985 года по МПК G06F7/49 

ройства соответственно, вход коэффициента изоморфизма которого соединен с первыми входами первого и второго блоков умножения, вторые входы котррых соединены с первыми выходами третьего и четвертого входных регистров соответственно, вторые выходы которых соединены с входами первого слагаемого первого и второго сумматоров по модулю N соответственно, входы второго слагаемого которого соединены с выходами первого и второго блоков умножения соответственно, а выходы - с первыми входами: элементов ИЛИ четвертой и пятой групп соответственно, вторые входы которых соединены с выходами первого и второго входных регистров соответственно, а выходы - с входами первого и второго дешифраторов соответственно, выходы элементов ИЛИ третьей группы соединены с первыми выходами элементов И первой и второй групп, вторые входы элементов И первой группы и первые входы пятого и шестого элементов И соединены с входом управления признаком определения результата в тев1ественной области устройства, вход управления признаком определения результата в комплексной области которого соединен с вторыми входами элементов И второй группы и первыми входами седьмого и восьмого элементов И, вторые входы которых соединены с выходами седьмого и восьмого элементов ИЛИ и вторыми входами пятого и шестого элементов И соответственно, выходы элементов И первой группы и выходы пятого и шестого элементов И соединены с входами первого выходного регистра, выходы элементов И второй группы и выходы седьмого и восьмого элементов И соединены с входами шифратора, выходы которого соединены с входами второго выходного регистра, выход которого соединен с вторым выходом устройства.

УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ В СИСТЕМЕ ОСТАТОЧНЫХ КЛАССОВ, содержащее два входных регистра, два дешифратора, восемь элементов ИЛИ, первый выходной регистр, сумматор по модулю два, три группы элементов ИЛИ, две группы ключевых элементов, коммутатор, четыре элемента И, причем входы первого и второго входных регистров соединены с входами первого и второго операндов в коде табличного умножения устройства соответственно, первая группа выходрв. первого и второго дешифраторов соединена с первыми входами элементов ИЛИ первой и второй групп и с входами первого и второго элементов ШШ соответственно, выхода которых соединены соответственно с первым и вторым нулевыми входами сумматора по модулю два, первый и второй еди- ничные входы которого соединены с выходами третьего и четвертого элементов ИЛИ, входы которых соединены с второй группой выходов первого и второго деишфраторов, и вторыми ВХОД4МИ элементов ИЛИ первой и второй групп соответственно, выходы которых соединены с информационными вxoдa И ключевых элементов первой и второй групп соответственно, управляющие входы которых соединены с вxoдa ffi управления устройства, а выходы - с первой и второй группами входов коммутатора, первая и вторая группы выходов которого соединены с первыми и вторыми входами элементов ИЛИ третьей группы и с входамипятого и шестого элементов ИЛИ соответственно, выходы которых соединены с первыми в содами всех четвертых элементов И, вторые входы первого и третьего элементов И соединены с нулевым выходом сумматора по модулю два, единичный выход которого соеди- ; нен с вторыми входа№1 второго и чет(Л вертого элементов И, выходы первого и второго элементов И соединены с .первыми входами седьмого и восьмого элементов ИЛИ соответственно, вторые входы которых соединены с выходами четвертого и третьего элементов И соответственно, выход первого выходного регистра соединен с выходом С5 устройства, отличающееся О) тем, что, с целью расширения функциональных возможностей за счет умо со ножения комплексных чисел по модулю jYi р +qj , в него введены третий. 00 и четверть входные регистры, два блока умножения, два сумматора по модулю N, четвертая и пятая группы элементов ИЛИ,две группы элементов И, И, пятый, шестой, седьмой и восьмой элементы И, шифратор и второй выходной регистр, причем входы третьего и четвертого ..входных регистров соединены с входами первого и второго операндов в комплексной форме уст

Изобретение относится к вычислительной технике и может быть использовано в вычислительных устройствах, работающих в системе остаточных классов (сок). Известно устройство для умножения чисел по модулю, содержащее входные регистры, дешифраторы, элементы ИЛИ, элементы И, коммутатор, сумматоры по модулю два, ключи, шифратор сумматор по модулю Р, выходной ре-. гистр, обрабатьшающёе по модулю как положительные, так и отрицательные числа l Недостатком этого устройства является невозможность обработки комплексньк чисел, . Наиболее близким к изобретению является устройство, содержащее входные регистры, дешифраторы, ключи коммутатор, выходной регистр, а также сумматор по модулю два, группы элементов ИЛИ, элементы И и ИЛИ. Известнбе устройство позволяет осу,ществить операцию модульного умножения двух операндов А, и А, т.е. A AjCmod N), используя код табличного умножения (КТУ). При этом реализуется всего 0,25 части общей таблицы модульного умножения 2 . Однако известное устройство позволяет производить операцию модульного умножения только в вещественной области и не позволяет производить модульного умножения . в комплексной области.. Цель изобретения - расширение функциональных возможностей за счет умножения комплексных чисел по модулю . Поставленная цель достигается тем, что в устройстве для умножения в системе остаточных классов, содержащее два входных регистра, два дешифратора, восемь элементов ИЛИ, первьй выходной регистр, сумматор по модулю два, три группы элементов ИЛИ, две группы ключевых элементов, коммутатор, четыре элемента И, причем входы первого и второго входных ре-

гистров соединены с входами первого и второго операндов в коде табличного умножения устройства соответственно, первая группа выходов первого, и второго дешифраторов соединены с первыми входами элементов ИЛИ первой и второй групп и с входами первого и второго элементов ИЛИ соответственно, выходы которых соединены соответственно с первым и вторым нулевым входами сумматора по модулю два, первый и второй единичные входы, которого соединены с выходами третьего и четвертого элементов ИЛИ, входы.которых соединены с второй, группой выходов первого и второ.го дешифраторов-, и вторыми входами, элементов ИЛИ первой и второй групп соответственно, выходы которых соединены с информационными входами ключевых элементов первой и второй групп ..соответственно, управляющие входы которьк соединены с.входами управления устройства, а выходы - с первой и второй группами входов коммутатора, первая и вторая группы выходов которого соединены с первыШ1 и вторыми входами элементов ИЛИ третьей группы и с входами пятого и шестого элементов ИЛИ соответственно, выходы которых соединены с . первыми входами всех четьфех элементов И, вторые, входы первого и третьего элементов И соединены с нулевым выходом сумматора по модулю, два, единичный выход которого соединен с вторыми входами второго и четвертого элементов И, вьссодуз первого и второго элементов И соединены с первыми входами седьмого и восьмого элементов ИЛИ соответственно, вторые входы которых соединены с выходами четвертого и третьего элементов И соответственно, выход первого выходного регистра соединен с выходом устройства, введены третий и четвертый входные регистры, два блока умножения, два сумматора по модулю N, четвёртая и пятая группы элементов ИЛИ, две группы элементов И, пятый, шестой, седьмой .и восьмой элементы И, шифратор и второй выходной регистр, причем входы третьего и четвертого входных регистров соединены с входами первого и второгооперандов в комплексной форме устройства соот,ветственно, вход коэффициента изоморфизма i oToporo соединен

с первыми входами первого и второго блоков умножения, вторые входы которых соединены с первыми выходами Третьего и четвертого входньк регистров соответственно, вторые выходы которых соединены с входами первого слагаемого первого и второго сумматоров по модулю N соответственно, входы второго слагаемого которого соединены с выходами перврго и второго блоков умножения соответственно, а выходы - с первыми входами элементов ИЛИ четвертой и пятой групп соответственно,- вторые входы которых соединены с выходами первого и второго входных регистров соответственно, а выходы - с входами перво.го и второго дешифраторов соответственно, выходы элементоз ИЛИ третьей группы соединены с первыми входами элементов И первой и второй групп, вторые входы элементов И первой группы и первые входы пятого и шестого элементон И соединены с входом управления признаком определения результата в вещественной области устройства,вход управления признаком определения резу.льтата в комплексной области которого соединен с вторыми входами элементов И второй группы и первыми входами седьмого и восьмого элементов И, вторые входы которых соединены с выходами седьмого и.восьмого элементов ИЛИ и вторыми входами пятого и шестого элементов И соответственно, выходы элементов И первой группы и выходы пятого и шестого элементов И соединены с входами первого выходного регистра, выходы элементов И второй группы и выходы седьмого и восьмого элементов И соединены с входами шифратора, выходы которого соединены с входами второго выходного регистра, выход которого соединен с вторым выходом устройства.

На фиг. 1-3 представлена структурная схема устройства для умножения в системе остаточных классов. .

Устройство содержит входы 1 и 2 первого и второго операндов в коде табличного умножения устройства, входы 3 и 4 первого и второго операндов в комплексной форме устройства, первый 5, второй 6, третий 7, четвертый 8 входные регистры, первый 9, и второй 10 блоки умножения, вход 11 коэффициента изоморфизма устройства, первый 12 и второй 13 сумматоры

.5по модулю N, группы 14-18 элементов ИШ, первый 19 и второй 20 дешифраторы, сумматор 21 по модулю два, элв менты ИЛИ 22-29, первая 30 и вторая 31 группы ключевых элементов, коммутатор 32, элементы И 33-40, первая 41 и вторая 42 группы элементов И, пшфратор 43, первый 44 и второй 45 выходные регистры, входы 46 управления устройства, входы 47 и 48 управления признаком определения результата в вещественной и комплексной областях устройства, первый 49 и. второй 50 выходы устройства.

Информационные входы 1-4 устройст эа подключены к входам соответственно первого 5, второго 6, третьего 7 и четвертого 8 входных регистров. Первые выходы третьего 7 и четвертого 8 входных регистров подключены к первым входам соответственно первого 9 и второго 10 блоков умножения, к вторым входам которых подключен вход 11 подачи значения коэффициента изоморфизма и . Второй выход третьего входного регистра 7 и выход первого блока 9 умножения подключены к входам первого сумматора 12 по модулю N, выходы которого одновременно с выходами первого входного регистра 5 через группу элементов ИЛИ 14 подключены к входам первого дешифратора 19. Второй выход четвертого входного регистра 8 и выход второго блока 10 умножения подключен к входам второго сумматора 13 по модулю N, выходы которого одновременно с выходами второго входного регистра 6 через группу элементов : .ИЛИ 15 подключены к входам второго

N 1

L)

дешифратора 20. Первая (1 N + 1

-.N - 1) группы выи вторая (

2

ходов, дешифратора 19 через соответ1

ствённо элементы ИЛИ 22 и 24 подключены соответственно к первым нулевому и единичному входам сумматора 21 по модулю два, одновременно пары (сумма значений, присвоенная каждой паре выходов равна N) выходов дешифратора 19 через группу элементов ИЛИ 16, через ключевые элементы 30 подключены к первой группе входов

N - 1

коммутатора 32. Первая (1 )

группы вы66098 .6

ходов дешифратора 20 через соответственно элементы ИЛИ 23 и 25 подключены соответственно к вторым нулевому и единичному входам сумматора 21 по модулю два, одновременно пары Осумма значений, присвоенная каждой выходов равна N) выходов дешифратора 20 через труппу элементоБ ИЛИ 17 через ключевые элементы 10 31 подключены к второй группе входов коммутатора 32. К входам управления ключевых элементов 30 и 31 подключены входы 46 управления устройства.

Первая (1г:-) и вторая (-

- N - 1) группы выходов коммутатора 32 подключены к входам элементов 11ПИ 26 и 27 соответственно и одновременно пары (сумма значений присвоена каждой паре вьпсодов равна N) выходов коммутатора 32 через элементы ИЛИ 18 подключены к первым входам соответствующих элементов И 41 и 42 групп. Выход элемента 26 подключен

5 к первым входам элементов И 33 и 34, а выход элемента ИЛИ 27 подключен к первым входам элементов И 35 и 36. Нулевой выход сумматора 21 подключен к вторым входам элементов И 33

Q и 35, а единичный выход сумматора 21 к вторым входам элементов И 34 и 36. Выходы элементов И 33, 36 и 34,35 подключены соответственно к входам элементов ЮШ 28 и 29, выходы которых .подключены к первым входам соответствуюг1их элементов И 37-40. К вторым входам элементов И 31 группы и элементов И 37 и 38 подключен вход 47 управления, а к вторым входам элементов И 42 группы и элемен-

тов И 39 и 40 - вход 48 управления. .Выходы элементов И 42 группы и элементов И 39 и 40 подключены к входам шифратора 43. Выходы элементов

, И 41 группы и элементов И 3 и 38

подключен к входам первого выходного регистра 44, а выходы шифратора 43 подключены к входам второго выходно. го регистра 45, выходы49 и 50 котоJJ рых являются выходами устройства.

Входные операнды в комплексной форме представлены в виде Ai а, +

. . 1

, А а + Ьг , а модуль имеет вид m р + i. При этом наиболь5 ший об1щй делитель (НОД) компонент Р, модуля m равен единице, т.е. (р ) 1. В соответствии с первой фундаментальной теоремой Гаусса по заданному комплекслому модулю п, норма которого равна N р + о и при НОД (р. О,) 1 комплексное числ А а + Ы сравнимо с одним и толь ко одним вычетом из ряда О, 1, 2, ..., N - 1, т.е. Л h(mod m), гдеh вещественное целое число. Определение результата операции умножения комплексных чисел А., Aj по модулю m можно заменить выполнением этой операции над соответствующими им вещественными вычетами по модулю N, т.е. h,h2(niod N). Таким об разом, А| , AJ hCtnod т),гле h hjhjCmod N). Значения вещественны вычетов определяются так (а + j9 Ь, h,(riod N), (aj + ) - h (mod N где D UQ, - Vp - коэффициент изом физма. Значения целых чисел U и V определяются из равенства Up - Vp Изоморфизм между комплексными чи лами и их вещественными вычетами дает возможность реализовать- операцию модульного умножения в комплекс ной области посредством алгоритмов, реализующих операцию модульного умножения в вещественной области. В предлагаемом устройстве используются свойства симметрии арифметическо таблицы относительно диагонали, вер тикали и горизонтали. Это и определяет возможность реализации в схеме модульного умножения только 0,25 полной табли №1. :1ри этом используется код табличного умножения (КТУ) Блоки 9 и 10 умножения служат дпя реализации операции дЬ (UcbVp) b (mod N). Сумматоры 12 и 13 реализуют операцию (а + рЪ) mod N Дешифраторы 19 и 20 служат для преобразования чисел из двоичного кода в десятичный. Сумматор 21 по модулю два реализует операцию 9 (Oh + S hj )mod 2 где h (Oh,, X,), hj -(h, x опера щы в КТУ (таблица). Отметим, что lib. N - 1, 1 ix, , -5, 57 п, , п hj - индексы КТУ, ih N - 1 Коммутатор 32 представляет двухвходовое ПЗУ, реализующее 0,25 части общей таблицы Ь, Ь(mod N) ф 988 (второй квадрант). Количество входов в каждой группе входов коммутатора 32 равно:г-, а количество вьосодов равно N. Шифратор 43 служит для определения комплексного вычета х х + yi, изоморфного вещественному вычету h hjhj (mod N), по значению П (яЬ, +nh,,)mod 2 или J2 (1 + + ( ЯЬ, )mod 2)mod 2 и .по значению х х, Xj(mod N) или х N - XjX2(mod N) и представляет собой ( + 2) - входовое ПЗУ. Количество выходов шифратора 43 равно количеству возможных наименьших вычетов ПО модулю m р + ai. Устройство работает следующим образом. .. Определение результата операции модульного умножения в вещественной области (присутствует сигнал со входа 47), т.е. h/hj(mod N), . На первый 1 и второй 2 входы устройства поступают соответственно входные операнды h (Qh., х.), hj (szhj, Xj) в двоичном коде. которые через соответственно первый 5 и второй 6 регистры, через элемен- . ты ИЛИ группы 14 и 15 поступают на соответствующие дешифраторы 19 и 20, С выхода дешифраторов 19 и 20 значения X, и X 2 через соответствующие элементы ИЛИ групп 16 и 17, ключевые элементы групп 30 и 31 поступают на входы коммутатора 32 (сигнал входа 28 открывает соответствующую пару ключевых элементов групп 30 и 31). Выходной сигнал коммутатора 32, соответствующий значению х, x,j (mod N) , через элементы ИЛИ группы 18, через открытый соответствукир1й элемент И группы 41 поступает во входной регистр 44. Выходной сигнал сумматора 21, соответствующий значению (ПЬ, + + rzhj)mod 2, открывает один из элементов И 33-36, через который выходной сигнал одного из элементов ИЛИ 26 и 27 через элементы ИЛИ 28 и 29, через соответствуюп1ий открытый элемент И .37 или 38 поступает на нулевой или единичный вход регистра 44. Таким образом, в выходном регистре 44 содержится результат модульного умножения в КТУ, т.е. h,h2(mod N)« ((nh, +52bj)mod 2, x,Xj (mod N))при ,X2(mod N) $ -п- (d ( 5г h-, -t- nhj) hjhjCmod N) mod 2)raod 2, N - x,X2(mod N)) при x,x.j(raod N) N - 1 Определение результата операции модульного умножения в комплексной области (присутствует сигнал со вхо да 48), т.е. А AJ(mod т). По входным шиНам 3 и 4.во входны регистры 7 и 8 заносятся соотвественно числа , + Ь,1и f a,j bji. Значение b, в, двоичном коде поступает на первый вход перво блока 9 умножения, на второй.вход .которого с входа 11 в двоичном коде поступает значение коэффициента изо морфизма р ил/- Vp. Выходной сигнал блока 9, соответствующий значению Ъ, р(mod N), поступает на первый вход сумматора 12, на второй вход которого поступает значение а, в дв ичном коде. С выхода сумматора 12 на элементы ИЛИ группы 14 поступает значение (а, + Ь, р) h,(mod N). Аналогично, получим на выходе сумма тора 13 значение hj(mod N). Далее устройство работает как описано выш Таким образом, значение h,h2(mod N) в КТУ через открытые элементы И группы 42 и элементы V 39 или 40 поступает на входы шифратора 43, где по значениям ( Г2 h + hj )mod 2 (или по значению (1 + (ЯЬ, + 5Zh,,)mod 2) mod 2) и N) (или по значению N- x,Xj(mod N) ) выбирается комплексное число, изоморфное вещественному вычету h,hj(mod N). В этом случае в регистре 45 содержится результат операции (mod m). Техническое преимущество изобретения, по сравнению с известным состоит в существенном расширении функциональных возможностей за счет доI полнительного выполнения операции модульного умножения в комплексной области.Положительный эффект заключается в уменьшении количества оборудования за счет совмещения в одном устройстве (посредством одного коммутатора) выполнения операции модульного умножения как в вещественной, так и в комплексной областях, что приводит к уменьшению стоимости машинной операции модульного умножения и повьпиению надежности ЭВМ в СОК.

V г

W

it9