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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социалистических

Республик (1) 959068 (61) Дополнительное к авт. свид-ву (22) Заявлено 11Л280 (21) 3215579/18-24

Р М g> з с присоединением заявки 8 (23) Приоритет

G F 7/49

Государственный комитет

СССР но делам изобретений и открытий

ДЗ) УДК 681. 325 (088. 8) Опубликовано 1509.82. Бюллетень Мо 34

Дата опубликования описания 150982 аявитель (54) уСТРойСтВО для уМНОжяяия По МодЛП0

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

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

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

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

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

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

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

P-1 Р+1 и—

2 2

) 1 f 1 3 1 ) У

1 2 3 4 5 6 7 8 9 10

1 2

2 4

3 б

4 8

5 10 б 7 8 9 10

1 3 5

7 10 2

7 9

5 8

2 б 10 3 7

8 2 7 1 б

3 9 4 10 5

9 5 1 8 4

10 надцатого и тринадцатого элементов

ИЛИ соединены с соответствующими входами выходного регистра, выход которого является выходом устройства (2).

Недостатком устройства является ограниченные функциональные возмож- 5 ности. Это обусловлено тем, что в выходном регистре содержится ойеранд (результат операции модульного умножения) в коде табличного умножения, а это не позволит использовать его непосредственно в цепи последующих операЦий ЦВМ.

Цель изобретения — расширение функциональных возможностей с тем, чтобы в выходном регистре результат формировался не в коде табличного умножителя-, а в двоичном коде.

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

И, выходной регистр, выходы которого являются выходом устройства, входы первого и второго дешифраторов подключены к выходам соответствующих регистров, а 3 --ый и (Р-1- )-ый выходы (= О, 1, 2,...,Р-1; Р— мо- 30 дуль) подключены соответственно к первому и второму входам -го элемента ИЛИ (j = 1, 2,...(Р-1)/2) соответственно первой и второй групп, первые группы » выходов t» = О, 1, 2,...,(Р-1)/2) соответственно первого и второго дешифраторов подключены к входам соответственно первого и второго элементов ИЛИ, вторые группы r выходов (г= (Р+1)/2,...,P-1)соответ- щ ственно первого и второго дешифраторов подключены к входам соответственно третьего и четвертого элементов

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

И третьей и четвертой групп (a

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

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

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

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

Ь табл. 1 приведен пример реализации в схеме табличного умножения (P = 11).

Таблица 1

959068

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

1 9 б

8 6 4

4 3 2

7 4

1 10

6 5

5 3

8 7

10

Таблица 2

Код табличного умножения

Цифра

Индекс Цифра

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

Алгоритм получения рееультата операции определяется следующим соотношением. Если два.числа X u Y заданы по модулю Р в коде табличного Умножения Х (> х- ), Y =(g> y;) то для того, чтобы получить Произведение этих чисел по модулю Р, достаточно получить произведение ху(тодР) в коде табличного умножения и инвертировать его индекс у в случае,,если отлично от, где

О, если 0 (х «с(Р-1Ц 1, 1, если (Р 1)/1(Х (РНа чертеже представлена структурная схема устройства.

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

5, б и 7; первый, второй, третий, четвертый и пятый элементы ИЛИ 8, 9, 10, 11 и 12, первую, вторую, третью и четвертую группы элементов И 13, 14, 15 и 16, элементы HE 17, коммутатор

18, выходной регистр 19, первый и второй элементы И 20 и 21.

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

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

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

35 Управляющий сигнал от устройства управления ЦВМ открывает по вторым

)входам элементы И первой и второй групп 13 и 14. - Если g = г, то элементы И 20 и 21 закрыты (сигналы ф} одновременно присутствуют йа выходах первого и третьего или второго и четвертого элементов ИЛИ 8, 9, 10 и 11) и выходной сигнал пятого элемента

ИЛИ 12 отсутствует, элементы И груп4 пы 16 закрыты, а группы 15 открыты.

Сигнал с выхода коммутатора 18 через элементы И группы 15 и элементы ИЛИ группы 7 поступает на входы выходного регистра 19. Если $x 4 у, то на

О выходе пятого элемента ИЛИ.12 присутствует сигнал (сигналы одновременно присутствуют на выходах первого и четвертого или второго и третьего элементов ИЛИ 8, 9, 10 и 11) открыт один из двух элементов И 14 или 15.

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

И группы 16, через элементы ИЛИ груп ® пы 7 поступает на вход выходного регистра 19.

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

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

959068 модульного умножения в двоичном коде.

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

Устройство для умножения по модулю, содержащее первый и второй входные регистры, входы которых являются первым и вторым информационными входами устройства, первый и второй дешифракоры, коммутатор, три группы элементов ИЛИ, пять элементов ИЛИ, три группы элементов И, выходной регистр, выходы которого являются выходом устройства, входы первого и ВТорого дешифраторов подключены к выходам соответствующих регистров, а т -й и (Р-1-i)-й выходы (= О, 1, 2,..., Р-1; Р— модуль) подключены соответственно к первому и второму входам

4 у-го элемента ИЛИ (j = О, 1, 2,..., (Р-1)/2) соответственно первой и второй групп, первые группы Ф выходов

E > = О, 1, 2,...,(Р-1)/21 соответственно первого и второго дешифраторов подключены к входам соответственно первого и второго элементов ИЛИ, вторые группы г выходов (Р+1)/2,...,P-1) соответственно первого и второго дешифраторов подключены к входам соответственно третьего и четвертого элементов ИЛИ, выходы элементов ИЛИ первой и второй групп подключены к первым входам соответствующих элементов И первой и второй групп, вторые входы которых 35 объединены и являются управляющим входом устройства,а выходы подключены соответственно к первой и второй. группам входов коммутатора, выходы элементов ИЛИ третьей группы подключены к входам соответствующих разрядов выходного регистра, о т л и ч а ю щ е е с я тем, что, с целью расширения области применения за счет получения результата умножения в двоичном коде, оно содержит первый и второй элементы И, элемент НЕ, четвертую группу элементов И, первые

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

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

1. Авторское свидетельство СССР

9 550636, кл. G 06 F 7/52, 1977.

2. Авторское свидетельство СССР по заявке Ф 2675156/18-24, кл. 6 06 F 7/39, 1979.

959068

Заказ 7017/65 . Тираж 731

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Подписное, Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4

Составитель В.Евстигнеев

Редактор Н. Киштулинец Техред.М.Коштура Корректор Г.Огар