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

(5) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ по МОДУЛЮ

Изобретение относится к вычислите льной технике. Известно устройство для умножения в системе остаточных классов, со держащее входные регистры, дешифрато ры, ключи, коммутатор, выходной регистр, а также сумматор по модулю дв группы элементов ИЛИ, элементы И и ИЛИ и соответствующие связи 1 J. Недостаток устройства - большой объем оборудования. Наиболее близким к предлагаемому по техническому решению является устройство для умножения по модулю, содержащее первый и второй входные регистры, дешифраторы, две группы элементов ИЛИ, первую группу элементов И, две группы ключей, пять элементов ИЛИ, первый и второй элементы И, выходной регистр, первый и второй входные регистры, подключены выходами к входам соответствующих дешифраторов, выходы первой и второй групп к твеых подключены к i соответствукмцим ,®лёментов ИЛИ первой и второй групп, выходы которых подключены к соответствующим входам ключей соответственно первой и второй групп, первые и вторые группы выходов первого и второго дешифраторов подключены соответственно к входам первого и второго, третьего и четвертого элементов ИЛИ, а такжеп коммутаторов ( Р - модуль), сумматор по модулю Р, две группы элементов И, причем соответствующие входы первой группы входов коммутаторрв объединены и подключены к выходам соответствующих ключей первой группы, соответствующие входы второй группы входов коммутаторов объединены и подключены к выходам соответствующих ключей второй группы, выходы коммутаторов подключены к соответствующим входам первой группы выходного регистра, вторая группа входов которого подключена к группе выходов сумматора по модулю Pj первая группа входов которого подключена соответственно к выходам ключей первой группы, информационны входы которых являются входами ко.да константы Р, а управляющие входы объединены и подключены .к выходу пятого элемента ИЛИ входы которого подключены к выходам соответственно первого и второго элементов И, перв входы которых подключены к выходам соответственно первого и второго эл ментов ИЛИ, а вторые входы - к выходам соответственно третьего и чет вертого элементов ИЛИ, первые входы соответствующих элементов И второй и третьей групп объединены и подклю чены k соответствующим входам выход ного регистра, вторые входы элементов И второй и третьей групп объединены и подключены к выходу пятого элемента ИЛИ, вторая группа входов сумматора по модулю Р подключена к выходам соответствующих элементов И второй группь, группа выходов элементов И третьей группы является выходом устройства 2. Недостаток устройства - большой объем оборудования. Цель изобретения-- уменьшение объема оборудования. Поставленная цель достигается ния по модулю, содержащее первый и второй входные регистры, дешифраторы, первую и вторую группы элементов Или, первую и вторую группы клю чей, труппу коммутаторов, выходной регистр, первую , вторую и третью группы элементов И, первый, второйт.ретий, четвертый и пятый элементы ИЛИ, первый и второй элементы И, сумматор по модулю Р, причем первый и второй входные регистры подкл/ючены выходами к входам соответствующих дешифраторов, выходы первой и второй групп которых подключены к соответствующим входам элементов ИЛИ пер вой и второй групп, выходы которых подключены к соответствующим информационным входам ключей соответствен но первой и второй групп, управляющие входы которых объединены и являются управляющим входом Умножение устройства, первые и вторые гру пы выходов первого и второго дешифра 864 торов подключены соответственно к входам первого и второго, третьего и четвертого элементов ИЛИ, одноименные входы первой группы входов Коммутато-ров объединены и подключены к выходам соответствующих ключей первой. группы, одноименные входы второй группы входов коммутаторов объединены и подключены к выходам соответствующих ключей второй группы, первые выходы коммутаторов подключены к соответствующим входам выходного регистра, первые входы элементов И первой, второй и третьей групп объединены и подключены к выходу пятого элемента ИЛИ, входы которого подключены к выходам соответственно первого и второго элементов И, вторые входы элементов И первой группы являются входами кода константы Р, а выходы подключены к соответствующим входам первой группы сумматора по модулю Р, вторые входы элементов И второй и третьей групп попарно объединены и подключены к соответствующим выходам выходного регистра, выходы элементов И второй группы подключены к соответствующим входам второй группы сумматора по модулю Р. содержит сумматор по модулю два, шестой элемент ИЛИ., третью группу элементов ИЛИ, выходы которых являются выходом устройства, первые входы подключены к соответствующим выходам сумматора по модулю Р. вторые входы подключены к, выходам соответствую щих элементов. И третьей группы, выходы первого, второго, третьего,и четвертого элементов ИЛИ подключены к соответстгзующим входам сумматора по модулю два, единичный и нулевой выходы которого подключены к первым входам соответственно первого и второго элементов И, вторые входы которых объединены и .подключенык выходу шестого,элемента ИЛИ, входы которого подключены к вторым выходам соответствующих коммутаторов группы. Основная идея изобретения состоит в том, что результат операции модульного умножения представляется -в кое табличного умножения. Это позвояет сократить объем оборудования за счет уменьшения количества коммутаторов (уменьшения количества схем совпадения И таблиц коммутаторов) , а также за счет исключения из устройства сумматора по модулю Р, так как

инвертирование по модулю Р результат операции, представленного в коде табличного умножения, осуществляется путём инвертирования индекса результата ГНа чертеже представлена блок-схема устройства,

- Устройство содержит первый и второй входные регистры 1, дешифраторы 2, первую и вторую группы элементов ИЛИ 3 и i, первую и вторую группы ключей 5 и 6, группу .коммутаторов 7, выходной регистр 8, первую,вторую и третью группы элементов И 9-11, первый, второй, третий, четвертый и пятьгй элементы ИЛИ 12-f6, первый и второй элементы И 17. и 18, сумматор 19 по модулю Р, сумматор 20 по модулю два, шестой элемент ИЛИ 21, третью группу элементов ИЛИ 22, Алгоритм-получения -результата операции модульного умножения определяется так: если два числа А и В заданы по основанию Р в коде таблич ного умножения А (Гс,, а), В (gTg , ). то для того, чтобы получить произвед ние этих чисел по Модулю Р, достато но получить произведение а fb (mod Р в коде табличного- умножения и инвертировать его индекс в случае, если /Уо отлично ,где: Г. |« если , , если

Двоичные входные регистры 1 служат фиксации входных операндов, пред |Ставленных двоичным кодом.

Дешифраторы 2 преобразуют двоичный код в унитарный. Количество выходных шин дешифратора 2 равно pl.

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

В табл. 1 показана реализация выполнения операции модульного умножения для , где Р- модуль таблицы.

Таблица 1 а Те о -/v если 3t Т если Та ГгаОсновная идея изобретения состоит в том, что узлам коммутаторов присваиваются значения в диапазоне 1--- -. Это позволяет сократить объем оборудования за с.чет уменьшения количества коммутаторов (уменьшения количества схем совпадения И таблиц коммутаторов) В качестве примера рассмотрим метод построения таблиц коммутаторов для . В прототипе реализуется . 0,25 части таблицы 1 (см. табл.2).

Таблица2 состояние. Входные операнды А и В, представленные в двоичном коде, пост пают в входные регистры 1. Через соответствующие дешифраторы. 2 эти операнды в унитарном коде поступают на определенные соответствующие элементы ИЛИ групп 3 и «. Управляющий сигнал открывает ключи 5 и 6 групп. Операнды А и В одновременно поступают на соответствующие входы всех ком мутаторов 7.. В тех коммутаторах 7, где определены значения , разряды ре зультата для данных операндов (едини ца в узлах таблиц),на первых выходных шинах, подключенных к соответствующему разряду регистра 8, присутствует сигнал. Этот сигнал переводит COOTветст ауИНДИИ разряд выходного регистра 8 в единичное состояние. Одновременно сигналы с выходов дешифраторов 3 поступают на два из четыре элементов ИЛИ 12-15. Пусть 7fg. Если сигнал второй выходной шины коммутаторов 7 отсутствует, что сигнал нулевой в- ходной шины сумматора 20 не проходит через закрытый элемент И 18. Операнд регистра 8 (результат операц4 и через открытые элементы И 11, элементы ИЛИ 21 поступает на выход устройства. Если сигнал второй выходной шины коммутаторов 7 присутствует, то сигнал нулевой выходной шины сумматора 20 через открытый элемент И 17, элементы ИЛИ 15 открывает элементы И первой и второй грыппы 9 и 1 и закрывает элемент третьей группы 11. Операнд регистра 8 через открыты элементы И 10 второй группы поступает на второй вход сумматора 19, на первый вход которого через.открытые элементы И 9 первой группы посту пает значение модуля Р в двоичном ко де.. Инвертированный по модулю Р, результат операции регистра 8 с выхода сумматора 19,-чер,ез элементы ИЛИ 21 поступает на ьыход устройства. Пусть , Если сигнал второй Быходной тины коммутаторов 7 отсутствует, то сигнал единичного выхода сумматора 20 через открытый элемент И 17, через пятый элемент ИЛИ 1б открывает элементы И первой и второй групп 9 и 10 и закрывает элемент третьей группы 11. Таким образом, инверт ированное по модулю Р значение результата регистра 8 с выхода сумматора 19 через элементы ИЛИ 21 поступает на выход устройства. Если сигнал второй выходной шины коммутаторов 7 присутствует, то элемент И 17 закрыт. .Значение результата опе рации с выхода регистра 8 через открытые элементы ИИ, элем,енты ИЛИ 21. поступает на выход 18 устройства. Таким образом, введение в состав предлагаемого устройства сумматора по модулю два элемента ИЛИ, группы элементов ИЛИ и соответствующих связей приводит к уменьшению объема оборудования коммутаторов и устройств в целом. Формула изобретения Устройство для умножения по модуглю, содержащее первый и второй входные регистры, дешифраторы, первую и вторую группы элементов ИЛИ, первую и вторую группы ключей, группу коммутаторов, выходной регистр, первую , вторую и третью группы элементов И, первый, второй, третий, четвертый и пятый элементы ИЛИ, первый и второй элементы И, сумматор по модулю Р, причем первый и второй входные регистры подключены выходами к входам соответствующих дешифраторов, выходы первой и второй групп кото рых подключены к соответствующим входам элементов ИЛИ первой и второй групп I выходы которых подключены к соответствующим информационным входам ключей соответственно первой и второй групп, управляющие входы которых объединены и являются управляющим входом Умножение устройства, первые и вторые группы выходов первого и второго дешифраторов подключены соответственно к входам первого и второго, третьего и четвертого элементов ИЛИ, одноименные входы первой группы входов коммутаторов объединены и подключены к выходам соответствуощих ключей первой группы, одноименные входы второй группы входоё коммутаторов объединены и подключены к выходам соответствующих ключей второй группы, первые выходы коммутаторов подключены к соответствующим входам выходного регистра, первые входы элементов И первой, второй, третьей групп объединены и подключе-. ны к выходу пятого элемента ИЛИ, входы которого подключены к выходам соответственно первого и второго элементов И, вторые входы элементов И

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

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

кл. G Об F , 1979.

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

LZJ