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

(54) УС1ЮЙСТВО ДЛЯ УМНОЖЕНИЯ ПО МОДУЛЮ

Изобретение относится к вычислительной технике. Известно устройство для умножения в сис теме остаточных классов, содержащее входные и выходной регистры, дешифраторы, ключи, коммутатор и логические блоки поиска квадрата и квадрантов арифметической таблицы. В устройстве используются свойства симметри арифметической таблицы модульного умножения двух операндов 1. Недостатком этого устройства является сложность построения и большое количество логических элементов. Наиболее близким к данному изобретению техническим решением является устройство дл умножения в системе остаточных классов, содержащее входные регистры, дешифраторы, ключи, коммутатор, выходной регистр, а такж сумматор по модулю два, группы элементов ИЛИ, элементы И и ИЛИ, причем первый и второй входные регистры последовательно через соответствующие первый и второй дешифраторы, первую и вторую группы элементов ИЛИ и первый и второй ключи подключен соответственно к первой и второй группам входов коммутатора, первые и вторые группы входов первого и вторюго дешифраторов подключены соответственно к входам первого, второго, третьего, четвертого элементов ИЛИ, выходы которых подключены к соответствующим входам сумматора по модулю два, управляющие входы ключей являются входами управления устройства, первая группа входов коммутатора подключена к входам пятого элемента ИЛИ л первым входам шестого, седьмогб, восьмого, девятого н десятого элементов ИЛИ, к вторым входам которых подключена вторая группа выходов коммутатора и входы одиннадцатого элемента ИЛИ, выход которого подключен к первым входам первого и второго элементов И, выход пятого элемента ИЛИ подключен к первым входам третьего и четвертого элементов И, вторые входы первого и третьего элементов И и второго и четвертого элементов И подключены соответственно к нулевому и еданичному выходам сумматора по модулю два, а выходы первого и четвертого элементов И и соответственно второго н третьего элементов И подключены к соответствующим входам двенадцатого н тринадцатого элементов ИЛИ, выходы шестого, седьмого, восыиого, девятого, десятого, двенадцатого и тринадцатого элементов ИЛИ соединены с соответствующими входами выходног регистра, выход которого является выходом устройства {2. Недостатком устройства является узкая область применения. Это обусловлено тем, что в вь ходном регистре результат операции модульного умножения получается в коде табличного умножения, а это не позволяет кспользовать его непосредственно в цепи последующих операций ЦВМ. Цель изобретения - расширение области при менения за счет получения результата умножения в двоичном коде. Поставленная цель достигается тем, что устройство, содержащее первый и второй входные регистры, входы которых являются первыми информационными входами устройства, первый и второй дешифраторы, коммутатор, три группы элементов ИЛИ, пять элементов ИЛИ, три группы элементов И, выходной регистр, вы ходы которого являются выходом устройства, входы первого и второго дешифраторов подклю чены к выходам соответствующих регистров, а i-ый и (Р-О-ый выходы (i О, 1, 2,... Р-1) подключены соответственно к первому и второму входам j-oro элемента ИЛИ (j 1, 2,. . . (Р-1)/2) соответственно первой и второй групп первые группы к-х выходов (k 0, 1, 2, ... (Р-1)/2) соответственно первого и второго дешифраторов подключены к входам соответственно первого и второго элементов ИЛИ, вторые группы г-ых выходов (г(Р-Ц)/2, .. .. Р-1) соответственно первого и второго дешифр торов подключены к входам соответственно третьего и четвертого элементов ИЛИ, выходы элементов ИЛИ первой и второй групп подклю чены к первым входам соответствующих элементов И первой и второй групп, вторые входы которых объединены и являются управляющим входом устройства, а выходы подключены соот ветственно к первой и второй грутшам входов коммутатора, содержит первый и второй элемен ты И, четвертую и пятую группы элементов И, шифратор, сумматор, по модулю Р, причем, первые входы элементов И третьей группы объединены с первыми входами соответствующих элементов И, четвертой группы и подключены к соответствующим выходам шифратора входами подключенного к выходам коммутаторЧ; пзрвые входь элементов И пятой группы Ш1.ПЯТПТСЯ третьим информационным входом устройства, вторые входы элементов И третьей, четвертой и пятой групп объединены и подключены к выходу пятого элемента ИЛИ, первый 9 64 и второй входы которого подключены к выходам первого и второго элементов И соответственно, первые входы которых подключены к выходам первого и третьего элементов ИЛИ соответственно, а вторые вхоДы - к выходам третьего и четвертого элементов ИЛИ соответственно, вЬпсоды элементов И четвертой и пятой групп подключены соответственно к первой и второй группам входов сумматора по модулю Р, группа выходов которого подключена к первым входам элементов ИЛИ третьей группы, выходы элементов И третьей группы подключены соответственно к вторым входам элементов ИЛИ третьей группы, выходы которых подключены к соответствующим входам выходного регистра, выход которого является выходом устройства. В предложенном устройстве используются свойства симметрии арифметической таблицы относительно диагонали, вертикали и горизонтали, проходящих между величинами (Р-1)/2 и (Р+1)/2, где Р - модуль таблицы. Это и . определяет возможность реализации в схеме табличного умножения только 0,25 таблицы (табл. 1, для ). Операция модульного умножения выполняется в коде табличного умножения (табл. 2). Алгоритм получения результата операции определяется следующим соотношением: если заданы по модулю в коде табличкого умножения X .( J , х), 7 (Тд. у) то для того, чтобы получить произведение этих чисел по модулю Р, достаточно получить произведение х (mod Р) в коде табличного умножения и инвертировать его индекс У в случае, если Ту отлично от ЗЯ Де ТА TV индексы кода табличного умножения. Jo,если )/2, 5 (-i,ecAvi срн)/2 5 Х- Р На чертеже представлена блок-схема устройства. Блок схема включает первый и второй входные регистры 1 и 2, первый и второй дешифраторы 3 и 4, первую, вторую и третью группы элементов ИЛИ 5,6 и 7, первый, второй, третий, четвертый н пятый элементы ИЛИ,8-12, первую, вторую, третью, четвертзто и пятую гр)тшы элементов И 13-17, коммутатор 18, шифратор 19, сумматор по модулю Р 20, выходной регистр 21, первый и второй элементы И 22 и 23. Устройство работает следующим образом. Операнды в двоичном коде поступают на . входные регистры 1 и 2. С выходов регистров 1 и 2 операнды чисел поступают на свои дешифраторы 3 и 4. Сигналы с выходов деишфраторов 3 и 4 одновременно поступают

на элементы ИЛИ первой и второй группы 5 и 6 и .элементы ИЛИ 8-11, Сигналы с выходов элементов ИЛИ первой и второй группы S н 6 через элементы И первой и второй групп 13 и 14 поступают на входы коммутатора 18. Управляющий сигнал от устройства управления ЦВМ открывает по вторым входам элементы И первой н второй группы. ЕслИУ Эу, тогда элементы И 22 и 23 закрыты (сигналы одновременно присутствуют на выходных ишнах первого и третьего или второго и четвертого элементов ИЛИ 8-11) и таким образом, выходной сигнал элемента ИЛИ 12 отсутствует, элементы И четвертой и пятой групп 16 и 17 закрыты, а третьей группы 15 открьгты. Сигнал определяющий результат шеращш модульного умножения, по одной из выходных шин коммутатора 18 поступает на вход ишфратора 19. С выхода шифратора 19 результат операции модульного умножения (в дв жчиом коде) через открытые элементы И третьей групшы 15, группу элемеитов ИЛИ 7 поступает на вход выходного регистра 21. Если Т% тогда

10001

20010

открыт один tt3 элементов И 22 или 23 (сигналы одновременно присутствуют на выходных ишнах первого и четвертого или второго я третьего элементов И 8-11, и на выходе элемента ИЛИ 12 присутствует сигнал. Этот сигнал открьшает элементы И пятой группы 17, четвертой группы 16 и закрывает элементы И первой группы 15. Таким обраэом7с выхода шифратора 19 на вторую группу входов сумматора 20 поступает результат операции (в двоичном коде) мЪдульиого умножения, § на вторую группу входов сумматора 20 по третьему входу поступает «шсло Р в двоичном коде. Результат операции модульного сложеш1я (т.е. инвертированное по модулю Р значение результата операщш модульного умножения) через третыо группу элементов ИЛИ 7 поступает . на вход регистра 21.

Таким образом, введение в устройство даух элементов И, двух групп элементов И, ошфратора, сумматора по модулю Р и соответствующих связей позволяет получить результат модульного умнажАгтя в двоичном коде. IТаблица 1

001

О О 010 Ф о р tA у п я изобретения Устройство для умножения по модулю, содержащее первый и второй входные регистры входы которых являются первым и вторым информационными входами устройства, первый и второй дешифраторы, коммутатор, три группы элементов ИЛИ, пять элементов ИЛИ, три группы элементов И, выходной регистр, выходы которого являются выходом устройства, входы первого и второго дешифраторов подключены к выходам соответствующих входных регистров, а i-й и (р-1)-й выходы (i О, 1, . . ., р-1; р - модуль) подключены соответственно к первому и второму входам j-ro эле мента ИЛИ (J 1, 2, ... (р-1)/2) соответственно первой и второй групп, первые группы к-х выходов (k О, 1, 2 ... (р-1)/2) соответ ственно первого и второго дешифраторов подключены ко входам соответственно первого и второго элементов ИЛИ, вторые группы г-х выходов {г (р+1)/2),. . . р-1) соответствен но первого и второго дешифраторов по;оключены ко входам соответственно третьего и четвертого элементов ИЛИ, выходы элементов ИЛИ первой и второй групп подключены к первым входам соответствующих элементов И лервой и второй групп, вторые входы которых объединены и являются управляющим входом устройства, а выходы - подключены соответственно к первой и второй группам

Продопжение табл. 2 ВХОДОВ коммутатора, отличающееся тем, что, с целью расширения области применения за счет получения результата умножения в двоичном коде, оно содержит первый и второй элементы И, четвертую и пятую группы элементов И, шифратор, сумматор по модулю р, причем первые входы элементов И третьей группы объединены с первыми входами соогвегствующих элементов И четвертой групг;ьг ;: подключены к соответствующим выходам шифратора, входами подключенного к выходам коммутатора, первые входы элементов И пятой группы являются третьим информационным входом устройства, вторые входы элементов И третьей, четвертой и пятой групп объединены и подключены к выходу пятого элемента ИЛИ, первый и второй входы которого подключены к выходам первого и второго элементов И соответственно, первые входы которых подключены к выходам первого и третьего элементов ИЛИ соответственно, а вторые входы - к выходам третьего и четвертого элементов ИЛИ соответственно, выходы элементов И четвертой и пятой групп .подключены соответственно к первой и второй группам входов сумматора по модулю р, группа выходов которого подключена к первым входам элементов ИЛИ третьей группы, выходы элементов И третьей группы подключены соответственно ко вторым входам элементов ИЛИ третьей , выходы которые подключены к соответствующим 9 входам выходаого регистра, выход которого является выходом устройства. Источники информации, принятые во внимание при экспертизе 95129610 1. Авторское свидетельство СССР N 550636, кл. G 06 F 7/52, 1977. 2. Авторское свидетельство СССР по заявке № 2675156/18-24, кл. G 06 F 7/39, 1979 j (прототип).

JA

1

ШМ.

П

Jf

LpJ Г7

у

.г W

го

Г7

язн

/я:

О

-5