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

 

Союз Советских

Социалистических

Республнк

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

<>896620

К АВТОИЖОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву (22) Заявлено 23. 04.80 (2!) 2916541/18-24 с присоединением заявки Мо (23) Приоритет

Опубликован@070182 Бюллетень Но 1

Дата опубликования описания 07 01 82 я)м. к,.з

G F 7/72

Государственный комитет

СССР но делам изобретений и открытий (53) УДК 681. 325 (088.8 ) (72) Автор изобретения

В.A- Краснобаев (71) Заявитель (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ПО МОДУЛЮ входы ключей являются входами управления устройства, первая группа выходов коммутатора подключена ко входам пятого элемента ИЛИ и первым входам шестого, седьмого, восьмого и девятого элементов ИЛИ, ко вторым входам которых подключены вторая группа выходов коммутатора и входы одиннадцатого элемента ИЛИ, выход которого подключен к первым входам первого и второго элементов И,выход пятого элемента ИЛИ подключен к первым входам третьего и четвертого элементов И, вторые входы первого и третьего элементов И и второго и четвертого элементов И подключены соответственно к нулевому и единичному выходам сумматора по модулю два, а выходы первого и четвертого элементов И и соответственно второго и третьего элементов И подключены к соответствующим входам двенадцатого и тринадцатого элементов ИЛИ,выходы шестого, седьмого, восьмого, девятого, десятого, двенадцатого и тринадцатого элементов ИЛИ соединены с соответствующими входа-ми выходного, регистра, выход которого является выходом устройства f2 g.

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

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

Недостатком устройства является большой объем оборудования.

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

896620

4 5 б 7 8 9 10

3 4 5 6 7 8 9 10 б 8 10 1 3 5 7 9

9 1 4 7 10 2 5 8

1 1 2

2 2 4

3 3 б

4 4 8

5 5 10 б 10 3 7

2 7 1 6

9 4 10 . 5

5 1 8 - 4

1 9 б 3

8 6 - 4 9

4 3 2 1

1 5 9 2

4 9 3

7 2 8 3

10 6 2 9 б б 1

7 7 3

8 8 5

2 10 7

9 9 ° 7 10. 10 9

5 3 1 10

9 7 6

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

Цель изобретения — уменьшение объема оборудования.

Поставленная цель достигается тем, что устройство для умножения по модулю, содержащее первый и второй входные регистры, дешифраторы, две группы элементов ИЛИ, первую группу элементов И, две группы ключей, первый, второй, третий, четвертый и пятый элементы ИЛИ, первый и второй элементы И, выходной регистр, первый и второй входные регистры подключены выходами ко входам соответствующих дешифраторов, .выходы первой и второй групп которых подключены к соответствующим входам элементов ИЛИ первой и второй групп, выходы которых подключены к соответствующим входам ключей соответственно первой и второй групп, первые и вторые группы выходов первого и в орого дешифраторов подключены соответственно ко входам первого и второго, третьего и четвертого элементов ИЛИ, оно содержит и коммутаторов (n pi 1og Р, где Р— модуль), сумматор по модулю

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

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

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

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

Рл -1 Рл +1 между числами 2 и

В табл.1 показана реализация выполнения операции модульного умноже40 ния для P = 11, где Р„.- 1-ый модуль выбранной СОК.

Таблица 1

89б620!

Таблица 2

Цифра

Символ Код

0001

001

0010

010

011 .

0011

100

0100

0101

101

1 01

0110

100

0111

011

1000

010

1001

1010

001

Симметричность относительно левой диагонали определяется коммутативностью операции умножения, симметричность относительно правой диагонали определяется тем, что (p. -а .) ° (Р„.- Ь. ) а„p, . (mod Р1) .

Симметричность относительно вертикали и горизонтали определяется тем, что сумма симметричных чисел кратна Р;, т.е. а ° . p, + а (Р - „) 0(ао4 Р. ) а . >„. + (Р,; -а. ) P„. =0(п>о4 P- ) .

Это и определяет возможность реализации в схеме табличного умноже-. ния только 0,25 части табл.1. Код табличного умножения представлен в табл.2 (для Р„. = 11). в десятич- в двоичном ном пред- представлеставлении нии

Величины 0 и Р = 11 не кодируются, так как умножение на эти величины дает ноль, и в этом случае операция будет. выполнена быстрее простым анализом операндов. При необходимости эти значения могут быть также включены в.табл.2.

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

Если,два числа A и В заданы по ,основанию Р. в коде табличного умно1 жения A = (Яо, а„. ), В (fp, ф1, то для того, чтобы получить произведение этих, чисел по модулю P,„. достаточно получить произведенйе а„. (>>q(mod Р„ ) в коде табличного ум40

55 бО

65 ножения и инвертировать его индекс у. в случае, если у отлично от л" где

У Pr

О, если 0 <а. — —

1, если — а-cp °;

P;+1

2 - > 1 ф если у ф ", ; если у = Я", Основная идея изобретения состоит в том, что в качестве коммутатора, определяющего результат операции модульного умно>кения, строится не единая таблица (табл.1), а п более мелких таблиц, реализующих ответы по каждому из и разрядов результата, где n - разрядность регистра (входных и выходного), необходимая для хранения цифры по рассматриваемому основанию Р„..

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

Устройство содержит первый и второй входные регистры 1, дешифраторы

2, первая 3 и вторая 4 группы элементов ИЛИ, первая 5 и вторая б группы ключей, группа коммутаторов 7, выходной регистр 8, первая 9, вторая

10 и третья 11 группы элементов И, первый 12, второй 13, третий 14, четвертый 15 и пятый 1б элементы ИЛИ, первый 17 и второй 18 элементы И, сумматор по модулю Р19.

Двоичные и-разрядные регистры 1 и

8 служат для фиксации соответственно значений операндов и результата операции модульного умножения. Коммутаторы 7 представляют таблицы, реализующие ответы по каждому из а разрядов результата операции. Конструктивно коммутаторы 7 представляют набор схем совпадения И. Количество элементов И в К-ом коммутаторе равно количеству единиц К-го разряда результата операции модульного умножения; эти элементы И объединяются общей выходной. шиной, подключенной к К-му разряду выходного регистра 8. На первый вход сумматора 19 через первую группу 9 элементов И поступает значение константы Р„. в двоичном коде; на второй вход через вторую группу 10 элементов И вЂ” значения операнда регистра 8, а с выхода сумматора 19 на инверсный вход выходного регистра 6 поступает инвентированное значение этого операнда, т.е. сумматор 19 инвертирует при наличии сигнала с выхода элемента ИЛИ

16) значения содержимого выходного регистра 8. Пусть А = (у,а) и

В (()В, pj) суть входные операнды в коде табличного умно>кения, тогда уп896620 равляющий сигнал с выхода элемента ИЛИ 16 присутствует тогда, когда

Щ, если ф » — "(сигнал с выхода элемента ИЛИ 16 отсутствует.Таким образом, элементы ИЛИ 13 и 16 и элементы И 18 служат для формирования управляющего сигнала при условии " Ф "р», Устройство работает следующим образом.

В начале работы все разряды выходного регистра 8 устанавливаются в нулевое состояние.

Пусть Щ» Рр . Входные операнды

A и В, представленные в двоичном коде, поступают во входные регистры 1.

Через соответствующие дешифраторы эти операнды в унитарном коде поступают на определенные соответствующие элементы ИЛИ первой 3 и второй 4 групп. Сигнал по управляющему входу открывает ключи групп 5 и 6, и операнды одновременно поступают на входы всех коммутаторов 7. В тех коммутаторах 7, где определены значащие ра.",ряды результата для данных операндов A и В (единицы в узлах таблиц), на выходной шине, подключенной к соответствующему разряду выходного регистра 8, появляется сигнал. Этот сигнал переводит соответствующий разряд выходного регистра 8 в единичное состояние (выхсдной сигнал К-го коммутатра 7 переводит в единичное состоянне Е-ый разряд выходного регистра 7). Одновременно сигналы с выходов дешифраторов 2 поступают на два из четырех элементов ИЛИ таким образом, что элементы И 17 и 18 закрыты, и выходной управляющий сигнал элемента ИЛИ 16 отсутствует (так как при ф» = ф" = 0 задействованы первый

12 и третий 14 элементы ИЛИ, а при ф » = $ p = 1 — второй 13 и четвертый

15 элементы ИЛИ).

16

Таким образом, в выходном регистре 8 содержится результат операции модульного умножения в двоичном ко" де. Это значение через открытые элементы И третьей группы 11 поступает на выход устройства.

Пусть Щ» -ф) .Как и в первом случае в выходной регистр 9 поступает из коммутаторов 7 операнд в двоичном коде. Но теперь на выходе элемента ИЛИ 16 присутствует управляющий сигнал (для ф,» = 1 и ф = 0 задействованы второй 13 и четвертый

15 элементы ИЛИ, открывающие второй . элемент И 18, а для ф <»= 0 и fp, 1 задействоваты первый 12 и третий 14 элементы ИЛИ, т.е. открыт первый элемент И 14). Выходной сигнал элемента ИЛИ 16 открывает элементы И .первой группы 9, элементы И второй группы 10 и элементы И третьей группы 11. При этом на входе сумматора

19 по модулю.P соответственно по30

55 бО

65 ступают значения константы P в двоичном коде и содержимое регистра 8.

С выхода сумматора 19 на второй вход регистра 8 поступает инвертированное по модулю .Р значение операнда, которое является результатом операции.

Таким образом, предлагаемое устройство позволяет перейти от реализации операции модульного умножения в однопозиционном коде посредством одного коммутатора (таблицы) к реализации этой операции с помощью п более мелких коммутаторов (таблиц), реализующих ответы по каждому из и разрядов результата, что позволяет значительно сократить объем оборудования.

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

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

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

10 ходам соответственно первого и второго элементов ИЛИ а вторые входы—

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

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

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

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

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

2. Авторское свидетелвство CCdP © по заявке Р 2675156/18-26, кл. G 06 F 7/39, 1978 (прототип).