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

Союз Советских Социалистических РеспубликОПИСАНИЕ ИЗОБРЕТЕНИЯ нн 896620 К АВТОИЖОМУ СВИДЕТЕЛЬСТВУ(5)М, (т,з 6 06 Г 7/72 Государственный комитет СССР но делам изобретений и открытий(54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ПО МОДУЛЮ входы ключей являются входами управления устройства, первая группавыходов коммутатора подключена ковходам пятого элемента ИЛИ и первымвходам шестого, седьмого, восьмогон девятого элементов ИЛИ, ко вторымвходам которых подключены втораягруппа выходов коммутатора и входыодиннадцатого элемента ИЛИ, выход которого подключен к первым входам первого и второго элементов И,выходпятого элемента ИЛИ подключен к первым входам третьего и четвертого элементов И, вторые входы первого и третьего элементов И и второго и четвертого элементов И подключены соответственно к нулевому и единичному выходам сумматора по модулю два, а выходы первого и четвертого элементов И и соответственно второго и третьего элементов И подключены к соответствующим входам двенадцатого и тринадцатого элементов ИЛИ,выходы шестого, седьмого, восьмого, девятого, десятого, двенадцатого и тринадцатого элементов ИЛИ соединены с соответствующими входа ми выходного, регистра, выход которого является выходом устройства 2 . Изобретение относится к вычислительной технике.Известно табличное устройство для модульного умножения в системе остаточных классов, содержащее дешифраторы, вентили, ключи, матрицу, элементы ИЛИ, логические схемы1,Недостатком устройства является большой объем оборудования.Наиболее близким к предлагаемому является устройство для умножения в системе остаточных классов, содер" жащее входные регистры, дешифраторы, ключи, коммутатор, выходной регистр, а также сумматор по модулю два,груп пы элементов ИЛИ, элементы И и ИЛИ, причем первый и второй входные регистры последовательно через соответствующие первый и второй дешифра" торы, первую и вторую группы элемен тов ИЛИ и первый и второй ключи подключены соответственно к первой и второй группам входов коммутатора, первые и вторые группы выходов первого и второго дешифраторов .подключены соответственно ко входам первого, второго, третьего и четвертого элементов ИЛИ, выходы которых подключены к соответствующим входам сумматора по модулю два, управляющие 30896620 4 5 б 7 8 9 10 7 8 8 10 1 3 1 4 10 3 б 4 б 10 3 5 9 5 5 2 8 1 8 7 7 7 4 1 1 10 8 9 9Ф10 10 9 7 Недостатком данного устройстваявляется сравнительно большая конструктивная сложность реализацииоперации модульного умножения (большое количество логических элементов,сложность связей между ними и сложность узлов коммутаторов), Это обус"ловлено тем, что для реализации операции модульного умножения примененкоммутатор (матрица ответов), в котором результат операции определяется унитарным кодом.Цель изобретения - уменьшениеобъема оборудования,Поставленная цель достигается тем,что устройство для умножения по модулю, содержащее первый и второй входные регистры, дешифраторы, две группы элементов ИЛИ, первую группу элементов И, две группы ключей, первый,второй, третий, четвертый и пятыйэлементы ИЛИ, первый и второй элементы И, выходной регистр, первый ивторой входные регистры подключенывыходами ко входам соответствующихдешифраторов, выходы первой и второйгрупп которых подключены к соответствующим входам элементов ИЛИ первой и второй групп, выходы которыхподключены к соответствующим входам ключей соответственно первой ивторой групп, первые и вторые группывыходов первого и в орого дешифраторов подключены соответственно ковходам первого и второго, третьегои четвертого элементов ИЛИ, оно содержит и коммутаторов (и Ъ 1 оа Р,где Р - модуль), сумматор по модулюР, две группы элементов И,причемсоответствующие входы первой группывходов коммутаторов объединены иподключены к выходам соответствующихключей первой группы, соответствующиевходы второй группы входов коммутаторов объединены и подключены к выходам соответствующих ключей второйгруппы, выходы коммутаторов подключены к соответствующим входам первойгруппы выходного регистра, вторая .группа входов которого подключенак группе выходов сумматора по модулюР, первая группа входов которогоподключена соответственно к выходамключей первой группы, информационныевходы которых являются входами кода константы Р, а управляющие входыобъединены и подключены к выходупятого элемента ИЛИ, входы которогоподключены к выходам соответственнопервого и второго элементов И, пер вые входы которых подключены к выходам соответственно первого и второгоэлементов ИЛИ, а вторые входы . - квыходам соответственно третьего ичетвертого элементов ИЛИ, первые 2 О входы соответствующих элементов Ивторой и третьей групп объединеныи подключены к соответствующим выходам выходного регистра, вторые входыэлементов И второй и третьей группобъединены и подключены к выходу пятого элемента ИЛИ, вторая группавходов сумматора по модулю Р подключена к выходам соответствующих элементов И второй группы, группа выходов элементов И третьей группы является выходом устройства.Как принято, в схеме модульногоумножения используются свойства симметрии арифметической таблицы относительно левой и правой диагоналей, ЗЗ вертикали и горизонтали, проходящихРл -1 Р+1между числами иВ табл.1 показана реализация выполнения операции модульного умноже ния для Р = 11, где Р - 1-ый модульвыбранной СОК.Таблица 189 бб 20 О 15 20 Таблица 2 ЦиФра Символ Код 25 30 35 0001 001 0010 010 011 . 0011 100 0100 0101 101 1 01 0110 100 0111 011 1000 010 1001 1010 001 10 Симметричность относительно левой диагонали определяется коммутативностью операции умножения, симметричность относительно правой диагонали определяется тем, что(Р -а)(Р,;-Ь 1) =ар(вод Р ),Симметричность относительно вертикали и горизонтали определяется тем, что сумма симметричных чисел кратна Р;, т.е.4 1 1(р -в) =-0(- Р )а 5+ (Р-а ) р =О(жМ р.),Это и определяет возможность реализации в схеме табличного умноже-. ния только 0,25 части табл.1. Код табличного умножения представлен в табл.2 (для Р = 11). в десятич- в двоичном ном пред- представлеставлении нии Величины 0 и Р = 11 не кодируются, так как умножениена эти величины дает ноль, и в этом случае опера" ция будет. выполнена быстрее простым анализом операндов. При необходимос" ти эти значения могут быть также включены в табл.2. Алгоритм получения результата операции модульного умножения определяется так следующим образом.Если,два числа А и В заданы по ,основанию Р в коде табличного умножения А 1 = (ЯОа 1)В 1 " (3 р ф 1 то для того, чтобы получить произведение этих . чисел по модулю Р, достаточно получить произведенйе а. ( 1(вод Р) в коде табличного ум 40 45 50 55 бО 65 ножения и инвертировать его индекс у в случае, если у отлично от лг где О, если 0 а1, если -а РР +12 ф если у ф ",; если у: ",Основная идея изобретения состоит в том, что в качестве коммутатора, определяющего результат операции модульного умнокения, строитсяне единая таблица (табл.1), а пболее мелких таблиц, реализующих ответы по каждому из и разрядов результата, где и - разрядность регистра (входных и выходного), необходимая для хранения цифры порассматриваемому основанию Р . На чертеже представлена блок-схема устройства для умножения по модулю.Устройство содержит первый и второй входные регистры 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 на инверсный вход выходного регистра 8 поступает инвентированное значение этого операнда, т.е. сумматор 19 инвертирует при наличии сигнала с выхода элемента ИЛИ 1 б) значения содержимого выходного регистра 8. Пусть А = (у,а) и В)Вф суть входные операнды в коде табличного умножения, тогда уп 896620равляющий сигнал с выхода элемента ИЛИ 16 присутствует тогда, когда3 О 436, если о =я сигнал с выхода элемента ИЛИ 16 отсутствует.Таким образом, элементы ИЛИ 13 и 16и элементы И 18 служат для формирования управляющего сигнала при условии д Фр,Устройство работает следующимобразом.В начале работы все разряды выход"ного регистра 8 устанавливаются внулевое состояние.Пусть Щ Я. Входные операндыА и В, представленные в двоичном коде, поступают во входные регистры 1.Через соответствующие дешифраторыэти операнды в унитарном коде поступают на определенные соответствующие элементы ИЛИ первой 3 и второй 4групп. Сигнал по управляющему входуоткрывает ключи групп 5 и б, и операнды одновременно поступают на входы всех коммутаторов 7. В тех коммутаторах 7, где определены значащиера,",ряды результата для данных операндов А и В (единицы в узлах таблиц),на выходной шине, подключенной к соответствующему разряду выходного регистра 8, появляется сигнал. Этотсигнал переводит соответствующий разряд выходного регистра 8 в единичное состояние (выхсдной сигнал К-гокоммутатора 7 переводит в единичноесостояние Е-ый разряд выходного регистра 7). Одновременно сигналы свыходов дешифраторов 2 поступают надва из четырех элементов ИЛИ такимобразом, что элементы И 17 и 18 закрыты, и выходной управляющий сигналэлемента ИЛИ 16 отсутствует (так какпри ф = " = О задействованы первый12 и третий 14 элементы ИЛИ, а при3 = ф = 1 - второй 13 и четвертый15 элементы ИЛИ). Таким образом, в выходном регистре 8 содержится результат операции модульного умножения в двоичном ко" де. Это значение через открытые элементы И третьей группы 11 поступает на выход устройства.Пусть Щ -ф).Как и в первом случае в выходной регистр 9 поступает из коммутаторов 7 операнд в двоичном коде, Но теперь на выходе элемента ИЛИ 16 присутствует управляющий сигнал (для щ = 1 и ф = 0 задействованы второй 13 и четвертый 15 элементы ИЛИ, открывающие второй элемент И 18, а для = 0 и "р, 1 задействоваты первый 12 и третий 14 элементы ИЛИ, т.е. открыт первый элемент И 14), Выходной сигнал элемента ИЛИ 16 открывает элементы И .первой группы 9, элементы И второй группы 10 и элементы И третьей группы 11. При этом на входе сумматора 19 по модулю.Р соответственно по 5 16 15Устройство для умножения по модулю, содержащее первый и второй входные регистры, дешифраторы, две группы элементов ИЛИ, первую группу элементов И, две группы ключей, первый, второй, третий, четвертый и пятый элементы ИЛИ, первый и второй элементы И, выходной регистр, первый и второй входные регистры подключены выходами ко входам соответствующих дешифраторов, выходы первой и второй групп которых подключены к соответствующим входам элементов ИЛИ первои и второй групп, выходы которых подключены к, соответствующим входам ключей соответственно первой и второй групп, первые и вторые группы выходов первого и второго дешифраторов подключены соответственно ко входам первого и второго, третьего и четвертого элементов ИЛИ, о т л ич а ю щ е е с я тем, что, с целью уменьшения объема оборудования, оно содержит и коммутаторов (и )г 1 о 9 Р, Р - модуль) сумматор по модулю Р, две группы элементов И, прием соответствующие входы первой группы входов коммутаторов объединены и подключены к выходам соответствующих ключей первой группы, соответствующие входы второй группы входов коммутаторов объединены и подключены к выходам соответствующих ключей второй группы, выходы коммутаторов подключены к соответствующим входам первой группы выходного регистра, вторая группа входов которого подключена к группе выходов сумматора по модулю Р, первая группа входов которого подключена соответственно к выходам ключей первой гРуппы, информационные входы .которых являются входами кода константы Р, а управляющие входы объединены и подключены к выходу пятого элемента ИЛИ, входы которого подключены к выходам соответственно первого и второго элементов И, первые входы которых подключены к вы 20 25 30 35 40 45 50 55 б 0 65 ступают значения константы Р в двоичном коде и содержимое регистра 8. С выхода сумматора 19 на второй вход регистра 8 поступает инвертированное по модулю .Р значение операнда, которое является результатом операции,Таким образом, предлагаемое устройство позволяет перейти от реализации операции модульного умножения в однопозиционном коде посредством одного коммутатора (таблицы) к реализации этой операции с помощью п более мелких коммутаторов (таблиц), реализующих ответы по каждому из и разрядов результата, что позволяет значительно сократить объем обору- дования Формула изобретенияходам соответственно первого и второго элементов ИЛИ а вторые входы -Ук выходам соответственно третьего и четвертого элементов ИЛИ, первые входы соответствующих элементов И второй и третьей групп объединены и подключены к соответствуюцим выходам выходного регистра, вторые входы элементов И второй и третьей групп объединены и подключены к выходу пятого элемента ИЛИ, вторая группа входов сумматора по модулю Р подключена к выходам соответствующих элементов И второй группы, группа выходов элементов И третьей группы является выходом устройства. э Источники информации,принятые во внимание при экспертизе 1. Авторское свидетельство СССР Р 550636, кл. 6 06 Г 7/52, 1977. 2. Авторское свидетелвство СССРпо заявке Р 2675156/18-26,кл. 6 06 Г 7/39, 1978 (прототип).