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

(54) УСТРОЙСТВО для УМНОЖЕНИЯ ПО МОДУЛЮ

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

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

Однако это устройство характеризуется сложностью построения и большим количеством логических элементов.

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

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

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

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

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

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

30 восьмого, девятого, десятого, двенадцатого и тринадцатого элементов ИЛИ соединены с соответствующими вхо дами выходного регистра, выход которого является выходом устройства 2 Недостатком устройства является ограниченные функциональные возможности. Это обусловлено тем/ что в вы ходном регистре содержится ойеранд (результат операции модульного умножения) в коде табличного умножения, а это не позволит использовать его непосредственно в цепи последующих операций ЦВМ. Цель изобретения - расширение функциональных возможностей с тем, чтобы в выходном регистре результат формировался не в коде табличного умножителя-, а в двоичном коде. Поставленная цель достигается тем, что устройство, содержащее первый и второй входные регистры, входы которых являются первым и вторым информационными входами устройства, первый и второй дешифраторы, коммутатор, три группы элементов ИЛИ,пять элементов ИЛИ, три группы элементов И, выходной регистр, выходы которого являются выходом устройства, входы первого и второго дешифраторов подключены к выходам соответствующих регистров, а (-ый и (Р-1-1)-ый выходы ( 1 О, 1, 2,...,Р-1; Р - модуль) подключены соответственно к первому и второму входам j-ro элемента ИЛИ J 1, 2,...(P-1)/2J соот ветственно первой и второй групп, первые группыЧ выходов 1 О, 1., 2,.. .,(Р-1)/2J соответственно первого и второго дешифраторов подключены к входам соответственно первого и второго элементов ИЛИ, вторые группы г выходов Сг (р+1)/2,...,Р-1 соотве ственно первого и второго дешифрато ров подключены к входам соответстве но третьего и четвертого элементов ИЛИ, выходы элементов ИЛИ первой и второй групп подключены к первым входам соответствующих элементов И первой и второй групп, вторые входы которых объединены и являются управляющим входом устройства, а выходы подключены соответственно к первой и второй группам входов коммутатора, выходы элементов ИЛИ третьей группы подключены к входам соответствующих разрядов выходного регистра, содержит первый и второй элементы И, элемент НЕ, четвертую группу элементов И, первые входы -х элементов И третьей и четвертой групп (i О, 1, 2,...,Р-1) попарно объединены и подключены к соответствующим i -м выходам коммутатора, вторые эле ёнтов И третьей группы объединены и подключены к выходу элемента НЕ, вторые входы элементов И четвертой группы и вход элемента НЕ объединены и подключены к выходу пятого элемента ИЛИ, первый и второй входы которого подключены к выходам соответственно первого и второго элементов И, первый и второй входы которых подключены соответственно к выходам первого, второго, третьего и четвертого элементов ИЛИ, выходы i-х элементов И третьей и четвертой групп подключены соответственно к первым и вторым входам i-X элементов ИЛИ третьей группы. В предлагаемом устройстве используются свойства симметрии арифметической таблицы относительно диагонали, вертикали и горизонтали, проходящих между величинами где Р - модуль таблицы. Это и определяет возможность реализации в схеме табличного умножения только 0,25. ё табл. 1 приведен пример реализации в схеме табличного умножения (Р 11). Таблица 1

Операция модульного умножения выполняется в коде табличного умноже ния и приведена в табл. 2.

Таблица 2

Алгоритм получения ревультата операции определяется следующим соотношением. Если два числа X и V заданы по модулю Р в коде табличного умножения X (3х гх-,- ), V (.Гу,У) , то, для того, чтобы получить Произведение этих чисел по модулю Р, достаточно получить произведение xy(modp) в коде табличного умножения и инвертировать его индекс у в случае, .если tx отлично от т , где

если О X й(Р-1)/1, если (Р+1)/2.х Р.

На чертеже представлена структурная схема устройства.

Устройство содержит первый и второй входные регистры 1 и 2, первый и второй дешифраторы 3 и 4, первую, , вторую, и третью группы элементов ИЛИ

Продолжение табл. 1

5, б и 7 ; первый, второй, третий, четвертый и пятый элементы ИЛИ 8, 9,

5 10, 11 и 12, первую, вторую, третью и четвертую группы элементов И 13, 14, 15 и 16, элементы НЕ 17, коммутатор 18, выходной регистр 19, первый и второй элементы И 20 и 21.

0

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

Операнды в двоичном коде поступают на,входные регистры 1 и 2, с выходов которых поступают на свои дешиф5раторы 3 и 4, переводящие их двоичные коды в коды 1 из Р. Сигналы с выходов дешифраторов 3 и 4 одновременно поступают на элементы ИЛИ первой и второй групп 5 и 6-и элементы ИЛИ

0 В, 9, 10 и 11. Сигналы с выходов элементов ИЛИ первой и второй групп 5 и 6 через элементы И первой и второй групп 13 и 14 поступают на входы коммутатора 18.

5

Управляющий сигнал от устройства управления ЦВМ открывает по вторым даходам элементы И первой и второй групп 13 и 14. - Если fv. - Ту элементы И 20 и 21 закрыты (сигналы

0 одновременно присутствуют «а выходах первого и третьего или второго и четвертого элементов ИЛИ 8, 9, 10 и 11) и выходной сигнал пятого элемента ИЛИ 12 отсутствует, элементы И груп- . пы 16 закрыты, а группы 15:открыты.

5 Сигнал с выхода коммутатора 18 через элементы И группы 15 и элементы ИЛИ группы 7 поступает на входы выходного регистра 19. Если Ух Э i то на выходе пятого элемента ИЛИ.12 присут0ствует сигнал (сигналы одновременно присутствуют на выходах первого и четвертого или второго и третьего элементов ИЛИ 8,9, 10 и 11) открыт один из двух элементов И 14 или 15.

5 Сигнал с выхода эл&}лент:а ИЛИ 12 через элемент НЕ 17 открывает элементы И группы 15 и закрывает - 16. Сигнал с выхода коммутатора 18 через элементы И группы 16, через элементы ИЛИ груп0пы 7 поступает на вход выходного регистра 19.

Таким образом, введение в устройство двух элементов И, элемента НЕ, группы элементов И и соответствующих

5 связей позволяет получить результат

модульного умножения в двоичном коде. Формула изобретения

Устройство для умножения о модулю, содержащее первый и второй входные регистры, входы которых являются первым и вторым информационными входами устройства, первый и второй дешифраторы, коммутатор, три группы элементов ИЛИ, пять элементов ИЛИ, три группы элементов И, выходной регистр, выходы которого являются выходом устройства, входы первого и второго дешифраторов подключены к выходам соответствующих регистров, а t-и и {Р-1-1)-й выходы ( i О, 1, 2,..., Р-1; Р - модуль) подключены соответственно к первому и второму входам j-ro элемента ИЛИ , 1, 2,.,., (Р-l)/2j соответственно первой и второй групп, первые группы выходов 0, 1, 2, .. . ,(Р-1)/2Т соответственно первого и второго дешифраторюв подключены к входам соответственно первого и второго элементов ИЛИ, вторые группы г выходов f ( )/2,.. . ,Р-1 соответственно первого и второго дешифраторов подключены к входам соответственно третьего и четвертого элементов ИЛИ, выходы элементов ИЛИ первой и второй групп подключены к первым входам соответствующих элементов И первой и второй групп, вторые входы которых объединены и являются управляющим входом устройства,а выходы подключены соответственно к первой и второй. группам входов коммутатора, выходы элементов ИЛИ третьей группы подключены к входам соответствующих разрядов выходного регистра, о т л и чающееся тем, что, с целью расширения области применения за счет получения результата умножения в двоичном коде, оно содержит первый и второй элементы И, элемент НЕ, чет0 .вертую группу элементов И, первые

«входы i -X элементов И третьей и четвертой групп ( О, 1, 2,.,.,Р-1) попарно объединены и подключены к соответствующим i -м выходам коммутатора, «вторые входы элементов И

третьей группы объединены и подключены к выходу элемента НЕ, вторые входы элементов И четвертой группы и вход элемента НЕ объединены и подключены к выходу пятого элемента ИЛИ, первый и второй входы которого подключены тс выходам соответственно первого и второго элементов И, первый и второй входы которых подключены соот ветствейно .к выходам первого,второго, третьего и четвертого элементов ИЛИ, выходы i-X элементов И третьей и четвертой групп подключены соответственно к первым и вторым входам 1-х элементов ИЛИ третьей группы,

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

1. Авторское свидетельство СССР 550636, кл. G 06 F 7/52, 1977, 5 2, Авторское свидетельство СССР по заявке 2675156/18-24, кл, G 06 F 7/39, 1979.