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

Иллюстрации

Устройство для умножения по модулю (патент 896620)
Устройство для умножения по модулю (патент 896620)
Устройство для умножения по модулю (патент 896620)
Устройство для умножения по модулю (патент 896620)
Показать все

Реферат

 

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

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

Республнк

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

<>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 (прототип).