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

 

О П И С А Н И Е (95)2М

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советсииа

Социапистмчесииа

Республик (61) Дополнительное к авт. свид-ву (22) Заявлено 08 12.80 (21) 3213272/18 — 24 с присоединением заявки йа (23) Приоритет (51)/Й. Кл.

G 06 F 7/49

1ткуАафатаакяЫ1 комитат

СССР ае двлаи изобретений к отаритий

Опубликовано 15.08.82- Бюллетень М 30

Дата опубликования описания 15.08.82 (53) УДK 681.325 (088.8) (72) Авторы изобретения

t.

А. В. Королев, В. А. Краснобаев и Б. И. Сергеев ., т:,-. ь-., (7l ) Заявитель (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ПО МОДУЛЮ

Изобретение относится к вычислительной технике.

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

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

1о

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

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

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

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

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

Недостатком устройства является узкая область применения. Это обусловлено тем, что в выходном регистре результат операции модульного умножения получается в коде табличного умножения, а это не позволяет н.".пользовать его непосредственно в цепи последующих операций ЦВМ, 15

Цель изобретения — расширение области применения за счет получения результата умножения в.двоичном коде, Поставленная цель достигается тем, что устройство, содержащее первый и второй входные 20 регистры, входы которых являются первыми информационными входами устройства, первый и второй дешифраторы, коммутатор, три группы элементов ИЛИ, пять элементов ИЛИ, . три группы элементов И, выходной регистр, вы- 5 ходы которого являются выходом устройства, входы первого и второго дешифраторов подключены к выходам соответствующих регистров, а i-ый и (Р— i)-ый выходы (i = О, 1, 2,... Р— 1) подключены соответственно к первому и вто- .30 рому входам j-ого элемента ИЛИ (j = 1, 2,... (Р— 1) /2) соответственно первой и второй групп, первые группы к-х выходов (k =О, 1, 2, (P 1)/2) соответственно первого и второго дешифраторов подключены к входам соответственно первого и второго элементов ИЛИ, вторые группы r-ых выходов (г=(Р+1) /2, Р— 1) соответственно первого и второго дешифраторов подключены к входам соответственно третьего и четвертого элементов ИЛИ, выходы элементов ИЛИ первой и второй групп подключены tc первым входам соответствующих элементов И первой и второй групп, вторые входы которых объединены и являются управляющим входом устройства, а выходы подключены соот-, ветственно к первой и второй группам входов коммутатора, содержит первый и второй элементы И, четвертую и пятую группы элементов И, шифратор, сумматор, по модулю Р, причем, первые входы элементов И третьей группы объединены с первыми входами соответствующих элементов И, четвертой группы и подключены к соответствующим выходам шифратора, входами подключенного к выходам коммутато-ч первые входы элементов И пятой группы

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

96 4

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

В предложенном устройстве используются свойства симметрии арифметической таблицы относительно диагонали, вертикали и горизонтали, проходящих между величинами (Р— 1)/2 и (Р+1)/2, где Р— модуль таблицы. Это и определяет возможность реализации в схеме табличного умножения только 0,25 таблицы (табл. 1, для Р 11).

Операция модульного умножения выполняется в коде табличчого умножения (табл. 2).

Алгоритм получения результата операции определяется следующим соотношением: если два числа Х и У заданы по модулю в коде табличного умножения X =.()„, х), (f+, у), то для того, чтобы получить произведение этих чисел по модулю Р, достаточно получить произведение х (mod P) в коде табличного умножения и инвертировать его индекс в случае, если отлично от $>, где . т,, )" — индексы кода табличного умножения. О,ВСКИ ОХ(Р- )/2, (.1,Если (р+ цg » y < 1»

На чертеже представлена блок — схема устройства.

Блок схема включает первый и второй входные регистры 1 и 2, первый и второй дешифраторы 3 и 4, первую, вторую и третью группы элементов ИЛИ 5, 6 и 7, первый, второй, третий, четвертый и пятый элементы ИЛИ 8 — 12, первую, вторую, третью, четвертую и пятую группы элементов И 13 — 17, коммутатор 18, шифратор 19, сумматор по модулю Р 20, выходной регистр 21, первый и второй элементы

H 22 и 23. !

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

Операнды в двоичном коде поступают на входные регистры 1 и 2. С выходов регистров 1 и 2 операнды чисел поступают на свои дешифраторы 3 и 4. Сигналы с выходов дешифраторов 3 и 4 одновременно поступают

5 95129 на элементы ИЛИ первой и второй группы

5 и 6 и .элементы ИЛИ 8 — 11. Сигналы с выходов элементов ИЛИ первой и второй группы

5 и 6 через элементы И первой и второй групп

13 и 14 поступают на входы коммутатора 1S.

Управляющий сигнал от устройства управления

ЦВМ открывает по вторым входам элементы И первой и второй группы. Еслифх= ;„, тогда элементы И 22 и 23 закрыты (сигналы одновременно присутствуют на выходных шинах первого 11 третьего или второго и четвертого элементов ИЛИ 8 — 11) и таким образом, выходной сигнал элемента ИЛИ 12 отсутствует, элементы И четвертой и пятой групп 16 и 17 закрьпы, а третьей группы 15 открыты. Сигнал,15 определяющий результат операции модульного умножения, по одной из выходных шин коммутатора 18 поступает на вход шифратора 19.

С выхода шифратора 19 результат операции модульного умножения (в двоичном коде) че- 2В реэ открытые элементы И третьей группы 15, группу элементов ИЛИ 7 поступает на вход выходного регистра 21. Если Щс Ф 3"у, тогда !

-.. х 1 у

6 7

7 8 9

3 6 7

10 2 5

6 10 3

7 1

4 10 .1 8

9 6

6 4

3 2

10

Таблица 2

Цифра

Код в двоичном представлении в десятичном представлении

001

010

0010 б 9

8 2

10 4

1 7

3 10

5 2

7 5

9 8

6 6 открыт один hs элементов И 22 или 23 (сигналы одновременно присутствуют на выходных шинах первого и четвертого или второго и третьего элементов И S — 11, и на выходе элемента ИЛИ 12 присутствует сигнал. Этот сигнал открывает элементы И пятой группы 17, четвертой группы 16 и закрывает элементы И первой группы 15. Таким образом, с выхода шифратора 19 на вторую группу входов сумматора 20 поступает результат операции (в двоичном коде) модульного умножения, а на вторую группу входов сумматора 20 по третьему входу поступает число Р в двоичном коде.

Результат операции модульного сложения (т.е. инвертированное по модулю P значение результата операции модульного умножения) через третью группу элементов ИЛИ 7 поступает на вход регистра 21.

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

Таблица 1

4 5 б

8 10 1

1 4

5 9 2

9 3 8

2 8 3

6 2 9

10 7 4

3 1 10

7 6 5

951296

Г1родолжение табл. 2

Цифра

Символ

Код в десятичном представлении в двоичном. представлении

0011

011

0100

0101

101

0100

101

0111

100

1000

011

1001

010

1010

ФорМула изобретения

Устройство для умножения по модулю, содержащее первый и второй входные регистры, входы которых являются первым и вторым информационными входами устройства, первый

H aropoA дешифраторы, KoMMyrarop, rpH груапы элементов ИЛИ, пять элементов ИЛИ, три группы элементов И, выходной регистр, выходы которого являются выходом устройства, входы первого и второго дешифраторов подключены к выходам соответствующих входных регистров, а i-й и (р — i)-й выходы (i = О, 1, ..., р — i; р — модуль) подключены соответственно к первому и второму входам j-го элемента ИЛИ (j = 1, 2,... (р — 1)/2) соответственно первой и второй групп, первые группъ „ к-х выходов (k = О, 1, 2 ... (р — 1)/2) соответственно первого и второго дешифраторов подключены ко входам соответственно перво о и второго элементов ИЛИ, вторые группы r-x выходов (r = (р+1)/2),... р — 1) соответственно первого и второго дешифргторов повключены ко входам соответственно третьего и четвертого элементов ИЛИ, выходы элементов

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

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

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

9 входам выходного регистра, выход которого является выходом устройства.

Источники информации, принятые во внимание при экспертизе

951296

1. Авторское свидетельство СССР N 550636, кл. G 06 F 7/5 2, 1977.

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

Р 2675156/18 — 24, кл. G 06 F 7/39, 1979

5 (прототип) .

ВНИИПИ Заказ 5948/55 Тираж 731 Подписное

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