Устройство для умножения чисел по модулю @

 

УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЧИСЕЛ ПО МОДУЛЮ Р, содержащее два входных регистра, два дешифратора, шесть элементов ИЛИ, два элемента И, две группы элементов И, две группы ключей, сумматор по модулю два, коммутатор, выходной триггер, причем вход первого входного регистра соединен с входом первого операнда устройства, вход второго входного регистра соединен с входом второго операнда устройства, выход первого и второго входных регистров соединены соответственно с входами первого и второго дешифраторов, выходы первого дешифратора соединены с соответствуй)щими входами элементов ИЛИ первой группы, выходы которых соединены соответственно с информационными вхо .дами ключей первой группы, управляющие входы которых соединены с управляющими входами ключей второй группы и с шиной логической единицы, первые и вторые группы, выходов первого и BTOpcfro дешифраторов подключены соответственно к входам первого, второго, третьего и четвертого элементов ИЛИ, выходы которых подключены к соответствующим входам сумматора по модулю два, выходы второго дешифратора соединены с соответствующими входами элементов ИЛИ второй группы, выходы которых соединены соответственно с информационными входами ключей второй группы, выходы котЬрых соединены соответственно с первой группой входов коммутатора, вторая группа входов которого соединена соответственно с выходами ключей первой группы, первых выход сумматора по модулю два i (Л соединен с первым входом первого элемента И, второй выход сумматора по модулю два соединен с первым вхо- . дом второго элемента И, выходы первогЪ и второго элементов И соединены с перQ вьгми входами соответственно пятого С и шестого элементов ИЛИ, выход вы кодного регистра является выходом устройства, о т л и чающееся СО СП, :тем, что, с целью упрощения устройства , в него введены третий и четвертый элементы И, причем управляющий выход кх)Ш1утатора соединен с запрещающими м входами третьего и четвертого эле00 ментов И, с вторыми входами первого и второго элементов И, выходы третьего и четвертого элементов И соединены с вторыми входами соответственно пятого и шестого элементов ИЛИ, информационные выходы коммутатора, шестого и пятого элементов ИЛИ соединены с соответствующими входами выходного регистра.

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

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

РЕСПУБЛИК

0% 01) 3 G 06 F 7/72

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

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

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

К ABTOPCHONIV ВПИВВТВЛЬФТВЪ (21) 3569036/18-24 (22) 29.03.83 (46) 30.05.84. Бюл. N 20 (72) В.АВКраснобаев, Е.И.Бороденко, В.И.Стеценко и А.Ю.Семенов

{53) 681.325(088.8) (56) 1. Авторское свидетельство СССР

Р 550636, кл. G 06 F 7/52, 1977.

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

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

ЧИСЕЛ ПО МОДУЛЮ Р, содержащее два входных регистра, два дешифратора, шесть элементов ИЛИ, два элемента И, две группы элементов И, две группы. ключей, сумматор по модулю два, коммутатор, выходной триггер, причем вход первого входного регистра соединен с входом первого операнда устройства, вход второго входного регистра соединен с входом второго операнда устройства, выход первого и второго входных регистров соединены соответственно с входами первого и второго дешифраторов, выходы первого дешифратора соединены с соответству1о" щнми входами элементов ИЛИ первой группы, выходы которых соединены соответственно с информационными входами ключей первой группы, управляющие входы которых соединены с управляющими входами ключей второй группы и с шиной логической единицы, первые и вторые группы. выходов первого и второго дешифратороз подключены соответственно к входам первого, второго, третьего и четвертого элементов ИЛИ, выходы которых подключены к соответствующим входам сумматора по модулю два, выходы второго дешифратора соединены с соответствующими входами элементов ИЛИ второй группы, выходы которых соединены соответственно с информационными входами ключей второй группы, выходы которых соединены соответственно с первой группой входов коммутатора, вторая группа входов которого соединена соответственно с выходами ключей первой группы, первых выход сумматора по модулю два соединен с первым входом первого ф элемента И, второй выход сумматора по модулю два соединен с первым вхо- . г дом второго элемента И, выходы первого и второго элементов И соединены с первыми входами соответственно пятого е и шестого элементов ИЛИ, выход выходного регистра является выходом устройства, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства, в него введены третий и четвертый элементы И, причем управляющий выход коммутатора соединен с запрещающими входами третьего и четвертого элементов И, с вторыми входами первого и второго элементов И, выходы третвего и четвертого элементов И соединены с вторыми входами соответственно пятого и шестого элементов ИЛИ, информационные выходы коммутатора, шестого и пятого элементов ИЛИ соединены е соответствующими входами выходного регистра.

1095178

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

1 классов.

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

Недостаток устройства — сложность

его построения. f5

- Наиболее близким по технической сущности к изобретению является устройство для умножения в системе остаточных классов, содержащее два входных регистра, два дешифратора, 2О шесть элементо» ЙЛИ, два элемента И, две группы элементов И, две группы ключей, сумматор по модулю два, коммутатор, выходной регистр, причем вход первого входного регистра соеди- 15 нен с входом первого операнда устройства, вход второго входного регистра соединен с входом второго операнда устройства, выход первого и второго входных регистров соединены ЗО соответственно с входами первого и второго дешифраторов, выходы первого, дешифратора соединены с соответству-, юп ими входами элементов ИЛИ первой группы, выходы которых соединены соответственно с информационными входами ключей первой группы, управляющие входы которых соединены с управляющими входами ключей второй группы и с шиной логической единицы, 4О первые и вторые группы выходов первого и второго дешифраторов подключены соответственно к входам первого, второго, третьего и четвертого элементов ИЛИ, выходы которых подключены к соответствующим входам сумматора по модулю два, выходы второго дешифратора соединены с соответствующими входами элементов ИЛИ второй группы, выходы которых соединены соответственно с информационными входами клю-: чей второй группы, выходы которых соединены соответственно с первой группой входов коммутатора, вторая группа входов которого соединена соответственно с выходами ключей пер55 вой группы, первый выход сумматора по модулю два соединен с первым входом первого элемента И, второй выход сумматора по модулю два соединен с первым входом второго элемента И, выходы первого и второго элементов И соединены с первыми входами соответственно пятого и шестого элементов

ИЛИ, выход выходного регистра является выходом устройства. Это устройство осуществляет операцию, умножения чисел по модулю P в табличном коде умножения (2) .

Недостаток устройсcBR — сложность построения. Этот недостаток обусловлен тем, что входным шинам коммутатора присвоены значения в диапазоне

Р 1

1 — ††вЂ, а узлам коммутатора и

:выходным шинам в диапазоне 1-P-1 (P — модуль).

Цель изобретения — упрощение устройства.

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

ИЛИ второй группы, выходы которых соединены соответственно с информаЪ ционными входами ключей второй группы, выходы которых соединены соответственно с первой группой входов коммутатора, вторая группа входов которого соединена соответственно с

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

Сущность изобретения состоит в том, что элементам И в узлах комму- 25 татора присвоены значения, лежащие в диапазоне p — 1

1- — вЂ, т.е. результат

2 операции а„ „(шой Г) коммутатора определяется в диапазоне от единицы

Р-1 до †††. При этом результат опера2 ции А B(mod. P) определяется в коде табличного умножения (КТУ), где

А=(gа, а), В=((„P„) входные операнды устройства

P—

4 (1 с а с — — — Y (g ) - индекс КТУ уо 40

2 равен 0 или I. В предлагаемой схеме модульного умножения используются свойства симметрии арифметической таблицы АВ (mod P) относительно

45 диагоналей, вертикали и горизонтали.

Это и определяет возможность реализа. ции в схеме модульного умножения ,всего 0,25 части полной арифметичес кой таблицы AB(mod P), т.е. достига1 ется упрощение устройства.

Структурная схема устройства представлена на чертеже.

Устройство содержит входы 1 и 2 первого и второго операндов, первый,Я и второй входные регистры 3 и 4, первый и второй дешифраторы 5 и 6 » первую и вторую группы элементов

78 4

ИЛИ 7 и 8, .первую и вторую группы ключей 9 и 10, коммутатор 11 шину

12 логической единицы, элементы ИЛИ

13-16, сумматор 17 по модулю два, элементы 18-21 И,элементы 22 и 23 ИЛИ, .выходной регистр 24, выход 25 уст,ройства.

Коммутатор 11 состоит из эле4 ,ментов И. Количество входных шин в каждой группе входов коммутатора 11 равно колйчеству выходных шин и

P-:1 .равно . Количество элементов И

1 узлах коммутатора 11 равно

P - 1

В табл. 1 приведены эна2 чения AS (mod P) для Р *11.

В табл.- 2 приведены зачения а, й; (mod P), присвоенные соответствующим узлам коммутатора 11

Р -,1 (1аа,, )

Р-1

Значения а;а (mod P )(Р-1, 2

1 представляются в виде Р-.а„ p, (mod P) и отмечены в табл. 2 знаком "+". Узлы коммутатора 11, которым присвоен одинаковый результат операции

a; p„(mod P), объединяются общей выходной управляющей шиной. Результат операции представлен ниже в КТУ. (J

КТУ (О, 1) (0,2) 7 (1,4)

8 (1,3) (0,3) (О, 4) 9 (1,2) .

10 (1,1) (0,5) Устройство работает следующим о образом.

Входные операнды А и В по соответ« . ствующим входам 1 и 2 первого и второго операнда в двоичном коде поступают в соответствующие входные регистры 3 и 4, и далее через соответствующие дешифраторы 5 и 6. через соответствующую пару элементов ИЛИ

7 и 8 операнды О; и 31 поступают на соответствующую пару ключей 9 и 10.

1095178

Сигнал шины 12 логической единицы открывает эту пару ключей 9 и 10 и сигналы, соответствующие значениям

0 и Й, поступают соответственно на первый и второй входы коммутатора 11. 5

Если в, тогда на нулевом выходе сумматора 17 по модулю два присутствует сигнал, который поступает на первые входы элементов 18 и 19 И.

Если на выходной управляющей шине коммутатора 11 отсутствует сигнал, то элемент 18 И открыт, и сигнал нулевого выхода сумматора 17 по модулю два через элемент ИЛИ 22 поступает на нулевой вход выходного регистра 24.15

Если на выходной управляющей шине коммутатора 1 1 присутствует сигнал, то элемент И 19 открыт, и сигнал нулевого выхода сумматора 17 по модулю два через элемент ИЛИ 23 поступает на единичный вход выходного регистра 24. Когда о ф у, то сигнал единичного выхода поступает на первые входы элементов 20 и 21И.

Если на выходной управляющей шине коммутатора 11 отсутствует сигнал, то элемент 20 И открыт, и сигнал единичного выхода сумматора 17 по модулю два через элемент, ИЛИ 23 поступает на единичный вход выходногоЗО регистра 24. Если на выходной управляющей шине коммутатора 11 присутствует сигнал, то элемент И 21 открыт, и сигнал единичного выхода сумматора 17 по модулю два через з5 элемент ИЛИ 22 поступает на нулевой вход выходного регистра 24. Одновременно результат операции a„P;(mod P)

r выхода коммутатора 11 поступает на соответствующий вход выходного 40 регистра 24. Таким образом, в выходном регистре 24 содержится результат операции АВ (mod P) в КТУ.

Пример. Выполнение операции

АВ (шой Р) для Р=11. А=7, В 2. 45

По входу 1 во входной регистр 3 заносится операнд А=0111, à по входу 2 во входной регистр 4 заносится операнд В=0010. С выхода дешифратора 5 значение А=7 поступает на . щ четвертый (4-7=Р) элемент ИЛИ 7 и через элемент .ИЛИ 14 {6-10) на первый единичный вход (/а =1) сумматора 17 по модулю два. С выхода четвертого элемента ИЛИ ? значение а;= 4

55 (А» (1,4)) поступает на четвертый ключ 9. С выхода дешифратора 6

1 значение В2 поступает на второй элемент ИЛИ 8 и -через элемент ИЛИ 15 (1-5) на второй нулевой вход .(= О) сумматора 17 по модулю два. С выхода второго элемента ИЛИ 8 значение

2 (В (0,2)) поступает на второй ключ 10. Сигнал шины 12 логической единицы открывает четвертый 9 и второй 10 ключи и значения а = 4 и ! — 2 поступают на входы коммутатора 11. С выхода коммутатора 11 значение а, P; (mod P) (табл. 2) поступает на третий вход выходного регистра 24. Так как go= 1, = 0 ((д + ) = 1 (mod 2)),то сигнал единичного выхода сумматора 17 по модулю два поступает на первые входы элементов 20 и 21 И. Сигнал выходной управляющей шины коммутатора 11 (табл. 2, где в узле а; = 4,P„.= 2, цифра 3 со знаком "+") закрывает элемент 20 И и открывает элемент И 21.

Таким образом, сигнал единичного выхода сумматора 17 по модулю два через элемент И 21, элемент ИЛИ 22 на нулевой вход выходного регистра

24, в котором и содержится результат операции в КТУ АВ (mod P) = (0,3).

Проверка (табл. 1 и 2): 7 2(mod t1)=

3.

Техническое преимущество изобретения по сравнению с базовым объектом состоит в упрощении устройства. Это достигается. во-первых, за счет

Р-1 сокращения (-- — — — входовых элемен2 тов ИЛИ, за счет сокращения группы двухвходовых элементов ИЛИ, за счет уменьшения (вдвое) количества выходных шин коммутатора; во-вторых, эа счет представления результата операции а„ P; (mod Р) только в диапазоне

Р-1

1 — ††вЂ, значительно упрощается

2 коммутация узлов в таблице коммутатора. Например, для модуля Р=11 сокращается приблизительно на 15% количество оборудования. Ожидаемый экономический эффект в результате использования предлагаемого изобретения заключается в уменьшении количества оборудования устройства, уменьшении веса и габаритов, что приводит к уменьшению стоимости устройства в целом.

1095178

Таблица 1

5 6 7 8

I»

4 5 6 7 8 .9 10

8 10 1 3 5 7 9

1 4 7 10 2 5 8

2 6 10 3 7

8 2 7 1 6

3 9 4 10 5

9 5 1 8 4

8 5

10 7 4 1

3 1 10 8

7 6 5 4

9 7

10 9

Таблица .2

3+

2+. 1. J 8 1

10 4

1 7

5 9

9 3

2 8

6 2

9 6 3

6 4 2

3 2 1

1095178

Заказ 3599/31 Тираж 699

Подписное

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

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

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

Составитель Л. Чедведева

Редактор Т. Колб Техред A,Ац Корректор С. И1екмар