Устройство для умножения в системе остаточных классов

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН (19) (< ) ) 4У)) G 06 F 7/49

ГОСУДАРСТВЕННЫЙ НОМИТЕТ CCCP

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

t Ъ.1

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К ABTOPCHOMY СВИДЕТЕЛЬСТБУ . 1РЪ" . (21) 3695050/24-24 (22) 27 ° 01.84 (46) 07.07.85. Вюл. В 25 (72) В.А.Краснобаев (53) 681.325(088.8) в(56) 1. Авторское свидетельство СССР к- 976440, кл. G 06 F 7/49, 1981.

2. Авторское свидетельство СССР

Ф 922731, кл. G 06 F 7/52, 1978 (прототип). (54)(57) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ

В СИСТЕМЕ ОСТАТОЧНЫХ КЛАССОВ, содержащее два входных регистра, два дешифратора, восемь элементов ИЗИ, первый выходной регистр, сумматор по модулю два, три группы элементов

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

ИЛИ первой и второй. групп. и с входами первого и второго элементов

ИЛИ соответственно, выходы которых соединены соответственно с первым и вторым нулевыми входами сумматора по модулю два, первый и второй еди- ничные входы которого соединены с выходами третьего и четвертого элементов ИЛИ, входы которых соединены с второй группой выходов первого и .второго дешифраторов, и вторыми входами элементов HJIH первой и второй групп соответственно, выходы которых соединены с информационными входами ключевых элементов первой и второй групп соответственно, упра ляющие входы которых соединены с входами управления устройства, а выходы — с первой и-BvopoA группами входов коммутатора, первая и вторая группы выходов которого соединены с первыми и вторыми входами элементов

ИЛИ третьей группы и с входами пятого и шестого элементов ИЛИ соответственно, выходы которых соединены с первыми входами всех четвертых элементов.И, вторые входы первого и третьего элементов И соединены с нулевым выходом сумматора по модулю два, единичный выход которого соединен с вторыми входами второго и четвертого элементов И, выходы первого и второго элементов И соединены с

:первыми входами седьмого и восьмого

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

re= ) + и;, в него введены третий. и четвертый входные регистры, два блока умножения, два сумматора по модулю N, четвертая и пятая группы элементов ИЛИ,две группы элементов И, И, пятый, шестой, седьмой н восьмой элементы И, шифратор и второй выходной регистр, причем входы трегьего и четвертого ..входных регистров соединены с входами первого и второго операндов в комплексной форме уст11 ройства соответственно, вход коэффициента изоморфизма которого соединен с первыми входами первого и второго блоков умножения, вторые входы котррых соединены с первыми выходами третьего и четвертого входных регистров соответственно, вторые выходы которых соединены с входами первого слагаемого первого и второго сумматоров по модулю N соответственно, входы второго слагаемого которого соединены с выходами первого и второго блоков умножения соответственно, а выходы — с первыми входами элементов ИЛИ четвертой и пятой групп соответственно, вторые входы которых соединены с выходами первого и второго входных регистров соответственно, а выходы — с входами первого и второго дешифраторов соответственно, выходы элементов ИЛИ третьей группы соединены с первыми выходами элементов И первой и второй групп, вторые входы элементов И пер66098 вой группы и первые входы пятого и шестого элементов И соединены с входом управления признаком определения результата в вещественной области устройства, вход управления признаком определения результата в комп-. лексной области которого соединен с вторыми входами элементов И второй группы и первыми входами седьмого и восьмого элементов И, вторые входы которых соединены с выходами седьмого и восьмого элементов ИЛИ и вторыми входами пятого и шестого элементов И соответственно, выходы эле-. ментов И первой группы и выходы пятого и шестого элементов И соединены с входами первого выходного регистра, выходы элементов И второй группы и выходы седьмого и восьмого элементов И соединены с входами шифратора, выходы которого соединены с входами второго выходного регистра, выход которого соединен с вторым выходом устройства.

Изобретение относится к вычислительной технике и может быть использовано в вычислительных устройствах, работающих в системе остаточг ньи классов (COK) . 5

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

Недостатком этого устройства является невозможность обработки комплексных чисел.

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

Известнде устройство позволяет осу. —, ществить операцию модульного умноже25 ния двух операндов А и А2, т.е.

А,A,(mod N), используя код табличного умножения (КТУ). При этом реализуется всего 0,25 части общей таблицы модульного умножения f2) .

Однако известное устройство позволяет производить операцию модульного умножения только в вещественной области и не позволяет производить модульного умножения в комплексной области.

Цель изобретения — расширение функциональных возможностей за счет умножения комплексных чисел по модулю tn= p + ;

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

11660 гистров соединены с входами первого и второго операндов в коде табличного умножения устройства соответственно, первая группа выходов перво"

ro и второго дешифраторов соединены. с первыми входами элементов ИЛИ первой и второй групп и с входами первого и второго элементов ИЛИ соответственно, выходы которьм соединены соответственно с первым и вторым нулевым входами сумматора по модулю два, первый и второй единичные входы которого соединены с выходами третьего и четвертого элементов

ИЛИ, входы которых соединены с вто15 рой группой вьмодов первого и второ.го дешифраторов; и вторыми входами элементов ИЛИ первой и второй групп соответственно, выходы которых соединены с информационными входами ключевых элементов первой и второй групп. соответственно, управляющие . входы которых соединены с входами управления устройства, а выходы — с первой и второй группами входов ком-.

25 мутатора, первая и вторая группы выходов которого соединены с первыми и вторыми входами элементов ИЛИ третьей группы и с входами пятого и шестого элементов ИЛИ соответст- венно, выходы который соединены с первыми входами всех четырех элементов И, вторые. входы первого и третьего элементов И соединены с нулевым выходом сумматора по модулю, два, 35 единичный выход которого соединен с втОрыми входами второго и четвертога элементов И, выходы первого и второго элементов И соединены с первыми входами седьмого и восьмого элемен- 40 тов ИЛИ соответственно, вторые входы которых соединены с выходами четвертого и третьего элементов И соответственно, .выход первого выходного регистра соединен с выходом устройства, введены третий и четвертый входные регистры, два блока умножения, два сумматора по модулю

К; четвертая и пятая группы элемен50 тов ИЛИ, две группы элементов И, пятый, шестой, седьмой и восьмой элементы И, шифратор и второй выходной регистр, причем входы третьего и четвертого входных регистров сое-. динены с входами первого и второго операндов s комплексной форме устройства соответственно, вход коэффи-:, I циента изоморфизма которого соединен

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

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

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

11 коэффициента изоморфизма устройст ва, первый 12 и второй 13 сумматоры

5 1166 по модулю N, группы 14-18 элементов

ИЛИ, первый 19 и второй 20 дешифраторы, сумматор 21 по модулю два, элементы ИЛИ 22-29, первая 30 и вторая

31 группы ключевых элементов, коммутатор 32, элементы И 33-40, первая

41 и вторая 42 группы элементов И, шифратор 43, первый 44 и второй 45 выходные регистры, входы 46 управления устройства, входы 47 и 48 управ- 10 ления признаком определения результата в вещественной и комплексной областях устройства, первый 49 и. второй 50 выходы устройства.

Информационные входы 1-4 устройст-15 ва подключены к входам соответственно первого 5, второго 6, третьего 7 и четвертого 8 входных регистров.

Первые выходы третьего 7 и четвертого 8 входных регистров подключены к 20 первым входам соответственно первого

9 и второго 10 блоков умножения, к вторым входам которых подключен .вход 11 подачи значения коэффициента изоморфизма p . Второй выход 25 третьего входного регистра 7 и выход первого блока 9 умножения подключены к входам первого сумматора 12 по модулю N, выходы которого одновременно с выходами первого входного щ регистра 5 через группу элементов

HJIH 14 подключены к входам первого дешифратора 19. Второй выход четвертого входного регистра 8 и выход второго блока 10 умножения подключен к входам второго сумматора 13 по модулю N, выходы которого одновременно с выходами второго входного регистра 6 через группу элементов: .ИЛИ 15 подключены к входам второго 40

N-1 дешифратора 20. Первая (1 —, ) N+ 1 и вторая (†. - N — 1) группы вы2 ходов. дешифратора 19 через соответственно элементы ИЛИ 22 и 24 подключены .соответственно к первым нулевому и единичному входам сумматора

2i по модулю два, одновременно пары (сумма значений, присвоенная каждой 50 паре выходов равна N) выходов дешифратора 19 через группу элементов

ИЛИ 16, через ключевые элементы 30 подключены к первой группе входов

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

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

098 6 ходов дешифратара 20 через соответственно элементы ИЛИ 23 и 25 подключены соответственно к вторым нулевому и единичному входам сумматора 21 по модулю два, одновременно пары (сумма значений, присвоенная каждой паре выходов равна N) выходов дешифратора 20 через группу элементоп HJIH 17 через ключевые элементы

31 подключены к второй группе входов коммутатора 32. К входам управления ключевых элементов 30 и 31 подключены входы 46 управления устройства.

N — 1 N — 1

Первая (1 — —.— } и вторая (2 2

N — - 1) группы выходов коммутатора

32 подключены к входам элементов

ИЛИ 26 и 27 соответственно и одновременно пары (сумма значений присвоена каждой паре выходов равна N) выходов коммутатора 32 через элементы ИЛИ 18 подключены к первым входам соответствующих элементов И 4 1 и 42 групп. Выход элемента 26 подключен к первым входам элементов И 33 и 34, а выход элемента ИЛИ 27 подключен к первым входам элементов И 35 и 36.

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

Выходы элементов И 33, ЗЬ и 34,35 подключены соответственно к входам элементов HJIH 28 и 29, выходы которых .подключены к первым входам соот-. ветствующих элементов И 37-40. К вторым входам элементов И 31 группы и элементов И 37 и 38 подключен вход 47 управления, а к вторым входам элементов И 42 группы и элементов И 39 и 40 — вход 48 управления.

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

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

Входные операнды в комплексной форме представлены в виде AI = .а + !

+ b,;, А, = а, + Ь,, а модуль имеет вид m = р + д. При этом наибольший общий делитель (НОД) компонент р, ф модуля ш равен единице, т.е. (р, $) = 1. В соответствии с первой фундаментальной теоремой Гаусса по

1166098 8 заданному комплексному модулю pl норма которого равна М = р + и. и при НОД (р, 9) = 1 комплексное число

А = а + bi сравнимо с одним и только одним вычетом из ряда О, 1, 2, N — 1, т.е. А = h(mod m), где h— вещественное целое число. Определение результата операции умножения комплексных чисел А, A по модулю

m можно заменить выполнением этой 10 операции над соответствующими им вещественными вычетами h! h по модулю N, т.е. h,h,(mod N). Таким образом, А1, А, = h(mod m),где h =

= Ь<Ь (шой И). Значения .вещественных 15 вычетов определяются так (а< + p Ь, )-"

=h< (mod N), (а + /Ь,) = h,(mod N), где fl = !!< — Чр — коэффициент изоморфизма. Значения целых чисел U и Ч определяются из равенства Up — Чр =1.2п

Изоморфизм между комплексными числами и их вещественными вычетами дает возможность реализовать операцию модульного умножения в комплексной области посредством алгоритмов, 25 реалиэукиких операцию модульного умножения в вещественной области. В предлагаемом устройстве используются свойства симметрии арифметической таблицы относительно диагонали, вер- ЗО тикали и горизонтали. Это и опреде- . ляет возможность реализации в схеме модульного умножения только 0,25 полной таблицы..!ри этом используется код табличного умножения (КТУ).

Блоки 9 и 10 умножения служат

35 .для реализации операции рЬ = (цс —

Чр) Ь (mod N). Сумматоры 12 и 13 реализуют операцию (а + рЬ) mod N. .Дешифраторы 19 и. 20 служат для преобразования чисел из двоичного кода в десятичный.

Сумматор 2 1 по модулю два реализует операцию 9 (й h + 9 h, ) mod 2 где h = (nh, х,), h =.(g h, x )-4 операнды в КТУ (таблица) .

Отметим, что c Ь1, h, c N — 1, N — 1

1 к!, х 2, h<, szh, — индекс ы КТУ, N — 1

О, если 1 h

N +

1, если .. h N — 1.

Коммутатор 32 представляет двухвходовое ПЗУ, реализующее 0,25 части общей таблицы Ь|Ь,(mod N) (второй квадрант) . Количество входов в каждой группе входов коммута° »

И-1 тора 32 равно, а количество выходов равно N.

Иифратор 43 служит для определения комплексного вычета х х + yi изоморфного вещественному вычету

h = h,h, (mod N), по значению A — (аЬ! + Oh )mod 2 или p = (1 +

+ (qh, + рЬ;.)mod 2)mod 2 и,по значению х = х, х (mod N) или х N— — x x2(mod N) и представляет собой

N — 1 (— + 2) — входовое ПЗУ. Полевеот2 во выходов шифратора 43 равно количеству возможных наименьших вычетов по модулю in = р + ф .

Устройство работает следующим образом.

Определение результата операции модульного умножения в вещественной области (присутствует сигнал со входа 47), т.е. ЬрЬ (mod N).

На первый 1 и второй 2 входы уст- . ройства поступают соответственно входные операнды h = (Oh, х. ), h, = (52 Ь,, х,) в двоичном коде, которые через соответственно первый

5 и второй 6 регистры, через элемен- . ты ИЛИ группы 14 и 15 поступают на соответствующие дешифраторы 19 и 20. С выхода дешифраторов 19 и 20 значения х, и х, через соответствующие элементы ИЛИ групп 16 и 17, ключевые элементы групп 30 и 3 1 поступают на входы коммутатора 32 (сигнал входа

28 открывает соответствующую пару ключевых элементов групп 30 и 31).

Выходной сигнал коммутатора 32, соответствующий значению х,х (mod N), через элементы ИЛИ группы 18, через открытый соответствукиций элемент И группы 41 поступает во входной регистр 44. Выходной сигнал сумматора

2 1, соответствующий з начению (Я h q +

+ Р Ь2)пюй 2, открывает один из элеме нтов И 33-36, чере з который выходной сигнал одного из элементов

ИЛИ 26 и 27 через элементы ИЛИ 28 и 29, через соответствующий открытый элемент И .37 илн 38 поступает на нулевой или единичный вход регистра

44, Таким образом, в выходном регистре 44 содержится результат модульного умножения в КТУ, т.е. h

00010 14 01110 1

01100. 00001

0001 1

00100

01011

01001

01000

00011 15 01111

00100 16 10000

00101 1 7 10001

00110 18 10010

00101

00111

00110

10011

00110

00111 19

001 1 1

00101

00011

00010

01000 20 10100

01001 21 10101

01010 22 10110

01011 23 I0111

01000

01001

01010

01011

01100 24 11000 1

00001

01100

К-1 при 144 х,х, (mod N) «с . или

h

mod 2)mod 2, N - х,х, (mod N) ) при

N+ 1

5 с х х, (mod N) < N - 1.

Определение результата операции модульного умножения в комплексной области (присутствует сигнал со вхо-, да 48), т.е. А А (mod m).

По входным шийам 3 и 4 во входные регистры 7 и 8 заносятся соотвественно числа A< = а + Ь

15 коде поступает на первый вход первого блока 9 умножения, на второй. вход которого с входа 1 1 в двоичном коде поступает значение коэффициента изоморфизма P = Uy — Vp. Выходной сиг20 нал блока 9, соответствующий значению Ь p(mod N), поступает на первый вход сумматора 12, на второй вход которого поступает значение а в двоичном коде. С выхода сумматора 12 на элементы ИЛИ группы 14 поступает значение (а < + Ь, р ) = h (mod N).

Аналогично, получим на выходе сумматора 13 значение Ь (mod N). Далее устройство работает как описано выше.

098 10

Таким образом, значение Ь 1Ь (mod N) в КТУ через открытые элементы И группы 42 и элементы И 39 или 40 поступает на входы шифратора 43, где по значениям (Й h + 17 h,)mod 2 (или по значению (1 + (Я h< + 52 h, )mod 2)

mod 2) и х,+mod N) (или по значению N— х, х, (mod N) ) выбирается комплексное число, изоморфное вещественному вычету h

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

116б098

Составитель Е.Захарченко

Техред А.Бабинец Корректор С.Черни

Редактор Г.Волкова.

Тираж 710 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Заказ 4310/43

Филиал ППП "Патент", r. Ужгород, ул. Проектная, 4