Устройство для умножения по модулю Советский патент 1982 года по МПК G06F7/72 

1

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

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

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

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

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

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

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

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

25 девятого, десятого, двенадцатого и тринадцатого элементов ИЛИ соединены с соответствующими входа ми выходного, регистра, выход которого является выходом устройства 21.

30

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

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

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

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

„ Р-1 +1

между числами 2 2

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

Таблица 1 Симметричность относительно левой диагонали определяется коммута тивностью операции умножения, симметричность относительно правой диагонали определяется тем, что .) 5 а p-Y ( PI) Симметричность относительно вер тикали и горизонтали определяется тем, что сумма сиглметричных чисел кратна Р,- , т.е. . р + а,- ( -/.) О (mod Р ) a-i - (P-j-a -) (niod p.) . Это и определяет возможность ре лизации в схеме табличного умножения только 0,25 части табл.1. Код табличного умножения представлен в табл.2 (для Р 11). Таблица Величины О и Р 11 не кодирую ся, так как умножениена эти велич ны дает ноль, и в этом случаеопер ция будет.выполнена быстрее просты анализом операндов. При необходимо ти эти значения могут быть также включены в табл.2. . Алгоритм получения результата о рации модульного умножения определ ется так следукяцим образом. Если,два числа А и В заданы по .основанию Р в коде табличного умн жения AI (Уа.), В (Jpfti то для того, чтобы получить произв дение этих чисел по модулю Р,достаточно получить произведение а. f)4(nod РО в коде табличного у ножения и инвертировать его индексу в случае, если-г- отлично от- где 1, если - PI ,f, если р, |-, если -jr tQ. Основная идея изобретения состоит в том, что в качестве коммутатора, определяющего результат операции модульного умножения, строится не единая таблица (табл.1), а п более мелких .таблиц, реализующих ответы по каждому из п разрядов результата, где п - разрядность регистра (входных и выходного), необходимая для хранения цифры по рассматриваемому основанию . На чертеже представлена блок-схема устройства для умножения по модулю. Устройство содержит первый и второй входные регистры 1, дешифраторы 2, первая 3 и вторая 4 группы элементов ИЛИ, первая 5 и вторая 6 группы ключей, группа коммутаторов 7, выходной регистр 8, первая 9, вторая 10 и третья 11 группы элементов И, первый 12, второй 13, третий 14, четвертый 15. и пятый 16 элементы ИЛИ, первый 17 и второй 18 элементы И, сумматор по модулю Р19. Двоичные п-разрядные регистры 1 и 8 служат для фиксации соответственно значений операндов и результата операции модульного умножения.Комму- . таторы 7 представляют таблицы, реализующие ответы по каждому из п разрядов результата операции. Конструктивно коммутаторы 7 представляют набор схем совпадения И. Количество элементов И в К-ом коммутаторе равно количеству единиц К-го разряда результата операции модульного умножения; эти элементы И объединяются общей выходной шиной, подключенной к К-му разряду выходного регистра 8. На первый вход сумматора 19 через первую группу 9 элементов И поступает значение константы в двоичном коде; на второй вход через вторую группу 10 элементов И - значения операнда регистра 8, а с выхода сумма- . тора 19 на инверсный вход выходного регистра 8 поступает инвентированное значение этого операнда, т.е. сумматор 19 инвертирует при наличии сигнала с.выхода элемента ИЛИ 16) значения содержимого выходного регистра 8. Пусть А (,а) и В (в , fi) суТь входные операнды в коде табличного умножения, тогда управляющий сигнал с выхода элеманта ИЛИ 16 присутствует тогда,когда fa ТР если а -Тр сигнал с вьлхода элемента ИЛИ 16 отсутствует.Таким образом, элементы ИЛИ 13 и 16 и элементы И 18 служат для формирования управляющего сигнала при условии 0 r|VУстройство работает следующим образом.

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

Пусть jy%. Входные операнды А и В, представленные в двоичном коде, поступают во входные регистры 1. Через соответствующие дешифраторы эти операнды в унитарном коде поступают на определенные соответствующие элементы ИЛИ первой 3 и второй 4 групп. Сигнал по управляющему входу открывает ключи групп 5 и 6, и операнды одновременно поступают на входы всех коммутаторов 7, в тех коммутаторах 7, где определены значащие раг.ряды результата для данных операндов А и В (единицы в узлах таблиц), на выходной шине, подключенной к соответствующему разряду выходного регистра 8, появляется сигнал. Этот сигнал переводит, соответствующий разряд выходного регистра 8 в единичное состояние (выходной сигнал К-го коммутатТра 7 переводит в единичное состояние Е-ый разряд выходного регистра 7). Одновременно сигналы с выходов дешифраторов 2 поступают на два из четырех элементов ИЛИ таким образом, что элементы И 17 и 18 закрыты, и выходной управляющий сигнал элемента ИЛИ 16 отсутствует (так как при а (Ь - О задействованы первый 12 и третий 14 элементы ИЛИ, а при 7fQ 1 - второй 13 и четвертый 15 элементы ИЛИ).

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

Пусть ipQ J(%-Как и в первом случае в выходной регистр 9 поступает из коммутаторов 7 операнд в двоичном коде. Но теперь на выходе элемента ИЛИ 16 присутствует управляющий сигнал (для -ЯГс 1 и -gTfi О задействованы второй 13 и четвертый 15 элементы ИЛИ, открывающие второй элемент И 18, а для а О и , 1 задействоваты первый 12 и третий 14 элементы ИЛИ, т.е. открыт первый элемент И 14). Выходной сигнал элемента ИЛИ 16 открывает элементы И первой группы 9, элементы И второй группы 10 и элементы И третьей группы 11. При этом на входе сумматора 19 по модулю.Р соответственно поступают значения константы Р в двоичном коде и содержимое регистра 8. С выхода сумматора 19 на второй вход регистра 8 поступает инвертированное по модулю .Р значение операнда, которое является результатом операции.

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

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

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

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

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

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

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

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

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

Источники информации,

принятые во внимание при экспертиэе

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

2.Авторское свидетелвство ccdp по заявке № 2675156/18-26,

кл. G Об F 7/39, 1978 (прототип).