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

(.5) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЧИСЕЛ ПО МОДУЛЮ

Изобретение относится к вычислител ной технике и может быть использовано в вычислительных устройствах, работаю щих в системе остаточных классов. По основному авт. св. № 922731 известно устройство для. умножения в сие теме остаточных классов, содержащее входные регистры, дешифраторы, ключи коммутатор, выходной регистр, а также сумматор по модулю два, группы эле ментов ИЛИ, элементы И и ИЛИ, причем первый и второй входные регистры последовательно через соответствующие первый и второй дешифраторы, первую и вторую группы элементов ИЛИ и первый и второй КЛЮЧИ подключены соответственно к первой и второй группам входов коммутатора, первые и вторые группы входов первого и второго дешифраторов подключены соответственно к входам первого, второго, третьего и четвертого элементов ИЛИ, выходы которых подключены к соответствующим входам сумматора по модулю два, управ ляющие входы ключей являются входами управления устройства, первая группа выходов коммутатора подключена к входам пятого элемента ИЛИ и первым входам шестого, седьмого, восьмого, девятого и дecяtoгo элементов ИЛИ, к вторым входам которых подключена вторая группа выходов коммутатора и входов одиннадцатого элемента ИЛИ, выход которого подключен к первым входам первого и второго элемента И, выход пятого элемента ИЛИ подключен к первым входам третьего и четвертого элементов И, вторые входы первого и третьего элементов И и второго и четвертого элементов И подключены соответственно к нулевому и единичному выходам сумматора по модулю два, а выходы первого и четвертого элементов И и соответственно второго и третьего элементов И подключены к соответствующим входам и двенадцатого и тринадцатого элементов ИЛИ, выходы шестого, седьмого, восьмого, девятого, десятого. 3 97 двенадцатого и тринадцатого элементов ИЛИ соединены с соответствующими входами выходного регистра, выход которого является выходом устройства Недостаток устройства - ограниченные функциональные возможности, связанные с обработкой только положитель ных чисел. Цель изобретения - расширение функ циональных возможностей. Поставленная цель достигается тем, что устройство содержит две группы элементов И, четвертую группу элементов ИЛИ, шифратор, сумматор по модулю Р (Р - модуль, по которому работает устройство), второй сумматор по модулю два, причем выходы знаковых I разрядов входных регистров подключены к входам второго сумматора по модулю два, выход которого, подключен к входу знакового разряда выходного регистра, информационные выходы выходного регистра подключены к соответствующим входам шифратора, выходы которого подключены к первым входам соответствующих элементов И первой и второй групп вторые входы которых соответственно объединены и подключены к первому и «второму индексным выходам выходного регистра, выходы элементов И первой груплы подключены к входам первой груп пы суммматора по модулю Р, входы второй группы которого объединены.и подключены к входу константы Р устройства , а выходы подключены к первым вхо- дам элементов ИЛИ четвертой группы, вторые входы которых подключены к выходам соответствующих элементов И второй группы, выходы элементов ИЛИ четвертой группы являются информационным выходом устройства, выход знакового разряда выходного регистра является знаковым выходом устройства. На чертеже представлена блок-схема устройства. Устройство содержит входные регист ры 1 , дешифраторы 2, первую и вторую группы элементов ИЛИ 3, первый, вто-. рой, третий и четвертый элементы ИЛИ k, первый сумматор 5 по модулю два, ключи 6, коммутатор 7 ,шестой, седьмой, восьмой, девятый и десятый эдементы . ИЛИ 8, выходной регистр 9, пятый и шестой элементы ИЛИ 10, первый, второй, -третий и четвертый элементы И 11 двенадцатый и тринадцатый элементы ИЛИ 12, шифратор 13, первую и вторую Сруппы элементов 1 и 15, суммматор 16.по модулю Р, второй сумматор 17 по . 4 модулю два, третью группу элементов ИЛИ 18, вход 19 константы Р устройства, выход 20 устройства, знаковый выход 21 устройства. В схеме модульного умножения используются свойства симметрии арифметической таблицы относительно диагонали, вертикали и горизонтали. Это определяет возможность реализации 0,25 части арифметической таблицы коммутатора (табл. Wl, для ). Таблица 1 Siini.:rr.L Если два числа X и Y заданы по основанию Р в виде табличного умножения х(гГх ib У(Т: .У,), то для того, чтобы получить произведение этих чисел по модулю .Р, достаточно получить произведение xy(mod Р) в коде табличного умножения и инвертировать его индекс в случа1е, если х отлично от , . где если П ; если Pi X Pi V у ч ч лп-«с ft л При реализации операции модульного умножения возможны два основных способа введения знака: -представление чисел в искусственной форме, т. е. А А+РЙ; -введение знака в явном виде, т.е. сопровождать число А признаком 51 д его знака sign А. Условимся, что, если , то0.д 0, а если , то51.д 1. В первом способе диапазон ЕО, Р-1) предстааимых чисел А уменьшается в два раза, так как числа, лежащие в интервале fO, 1), обозначают отрицательные числа А, а в интервале - + р-1) положительные. Это значительно сужает функциональные возможности устройства. Кроме этого, определение знакового признака йд д чисел, представленных в искусственной форме, вызывает необходимость значительных дополнительных аппаратурных затрат. Наиболее просто реализуется второй способ - введение знака числа А в явном виде. Во-первых, конструктивно просто реализовать признак ,, во-вторых, диапазон представимых ч сел за счет введения признака йд у личивается вдвое. И, наконец, при дении знака в явном виде для реали ции операции модульного умножения необходимости применять критерий п реполнения . . как в случае сложения. Для модульного умножения призн Лд 4А5Р зультата операции формир ся сумматором по модулю два (табл Т а б л и ц а 2 Таким образом, выходной операнд представляется в специальном коде табличного умножения (табл. З) IТ а б л и ц а Специальный к Специальный код табличного тйбличного умножения) |1множения

Устройство работает следующим образом.

По входным шинам во входные регистры 1 поступают операнды чисел в двоичном коде, а также признаки Лдоперан- дов. С регистров 1 операнды поступают на свои дешифраторы 2, а сигналы, соответствующие признакам51д - на входь

SO

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

Устройство для умножения чисел по модулю по авт. св. f 922731, отличающееся тем, что, с целью расширения функциональных возможностей путем перемножения как положительных, так и отрицательных чисел, а также получения .результата в двоичном сумматора 17. С выходов дешифраторов 2 операнды, в унитарном коде, через элементы ИЛИ 3 ключи 6 поступают на соответствующие входы коммутатора 7Коммутатор 7 определяет результат операции xy(mod Р), который через элементы ИЛИ8 поступает на соответствующий вход регистра 9, и одновременно поступает на пятый или шестой элемент ИЛИ k, и далее через первый сумматор 5 по модулю два и определенный элемент И 11, элемент ИЛИ 12 на нулевой или единичный входы регистра 9, определяя индекс JVv результата операции. Сигнал нулевого (-JT Ту ) или единичного (jy 3)) выхода сумматора 5 поступает на второй вход соответствующего элемента И 11. Сумматор 17 формирует, в соответствии с табл.2, признак ST. х , который поступает на знаковый разряд регистра Э. Таким образом, в выходном регистре 9 содержится результат операции модульного умножения в специальном коде табличного умножения ху(51,, ,4, , X, у (mod PC )). Операнды регистра 9;,значения от 1 до -) поступают на входы элементов И 1 4 и 15 первой и второй групп. Если , то операнд с выхода шифратора 9 через открытые элементы И 15 второй группы, элементы ИЛИ 18 поступает на выход 20 устройства. Если , то операнд через открытые элементы И 15 второй группы поступает на первые входы сумматора 16, а на вторые входы сумматора Т4 поступает значение константы Р в двоичном коде. С выхода сумматора 16 инвертированный по модулю Р операнд, через элементы ИЛИ 18 поступает на выход 20 устройства. Таким образом, предложенное устройство обрабатывает по модулю как положительные, так и отрицательные числа и выдает результат в двоичном коде, что делает его совместимым со всеми, трактами современных ЦВМ. коде, устройство содержит две группы элементов И, четвертую группу элементов ИЛИ, шифратор, сумматор по модулю Р (Р -модуль, по которому работает устройство), второй сумматор по модулю два, причем выходы знаковых разрядов входных регистров подключены к входам второго сумматора по модулю два, выход которого подключен к входу знакового разряда .выходного регистра, информационные выходы выходного регистра подключены к соответствующим входам шифратора, выходы которого подключены к первым входам соответствующих элементов И первой и второй групп, вторые входы которых соответственно объединены и подключены к первому и второму индексным выходам ного регистра, выходы элементов И первой группы подключены к входам первой группы сумматора по модулю Р, входы второй группы которого объединены и подключены к йходу константы Р устройства, а выходы подключены к первым входам элементов ИЛИ четвертой группы, вторые входы которых подключены к выходам соответствующих элементов И второй группы, выходы элементов ИЛИ четвёртой группы являются информационным выходом устройства, выход знакового разряда выходного регистра является знаковым выходом устройства. Источники информации, принятые во внимание при экспертизе 1. Авторское свидетельство СССР № 922731, кл. G Об F , 1978 (прототип).

J/A

11

(

Я

W y ) i

Ш Ш Ш Щ