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

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

Иллюстрации

Показать все

Реферат

 

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

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

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

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

Республик (6() Дополнительное к авт. свил-ву ((922731 (22)Заивлено 17.02.81 (2() 3250557/18-24 с присоелинением заявки Ля 3259079/24 (23) Приоритет

Опубликовано 23 11.82. Бюллетень h"43

Дата опубликования описания 23 . 1 1 .82 (5! )М. Кл.

С 06 Г 7/49

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

СССР во делам изобретений и открытий (53) УДК 681. 325 (O88. 8) (72) Авторы изобретения

В. А. Краснобаев и А. В. Королев (7l ) Заявитель (547 УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЧИСЕЛ

ПО МОДУЛЮ

Изобретение относится к вычислителo ной технике и может быть использовано в вычислительных устройствах, работающих в системе остаточных классов.

По основному авт. св. (Г 922731 известно устройство для. умножения в сис-5 теме остаточных классов, содержащее входные регистры, дешифраторы, ключи, коммутатор, выходной регистр, а так— же сумматор по модулю два, группы элементов ИЛИ, элементы И и ИЛИ, причем первый и второй входныЕ регистры последовательно через соответствующие первый и второй дешиФраторы, первую и вторую группы элементов ИЛИ и первый и второй ключи подключены соот15 ветственно к первой и второй группам входов коммутатора, первые и вторые группы входов первого и второго дешифраторов подключены соответственно к входам первого, второго, третьего и четвертого элементов ИЛИ, выходы которых подключены к соответствующим входам сумматора по модулю два, управ2 ляющие входы ключей являются входами управления устройства, первая группа выходов коммутатора подключена к входам пятого элемента ИЛИ и первым входам шестого, седьмого, восьмого, девятого и десятого элементов ИЛИ, к вторым входам которых подключена вторая группа выходов коммутатора и входов одиннадцатого элемента ИЛИ, выход которого подключен к первым входам первого и второго элемента И, выход пятого элемента ИЛИ подключен к первым входам третьего и четвертого элементов И, вторые входы первого и третьего элементов И и второго и четвертого элементов И подключены соответственно к нулевому и единичному выходам сумматора по модулю два, а выходы первого и четвертого элементов И и соответственно второго и третьего элементов И подключены к соответствующим входам и двенадцатого и тринадцатого элементов ИЛИ, выходы шестого, седьмого, восьмого, девятого, десятого, 3 97644 двенадцатого и тринадцатого элементов ИЛИ соединены с соответствующими входами выходного регистра, выход которого является выходом устройства(1 ).

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

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

Поставленная цель достигается тем, что устройство содержит две группы элементов И, четвертую группу элементов ИЛИ, шифратор, сумматор по модулю Р (P - модуль, по которому работа; 1$ ет устройство), второй сумматор по модулю два, причем выходы знаковых разрядов входных регистров подключены к входам второго .сумматора по модулю два, выход которого подключен к входу р знакового разряда выходного регистра, информационные выходы выходного регистра подключены к соответствующим входам шифратора, выходы которого подключены к первым входам соответствую- 2у щих элементов И первой и второй групп, вторые входы которых соответственно объединены и подключены к первому и .второму индексным выходам выходного регистра, выходы элементов И первой группы подключены к входам первой группы суммматора по модулю Р, входы второй группы которого объединены. и под- . ключены к входу константы Р устройства, а выходы подключены к первым вхо дам элементов ИЛИ четвертой группы, вторые входы которых подключены к выходам соответствующих элементов И вто-. рой группы, выходы элементов ИЛ, четвертой группы являются информацйонным выходом устройства, выход знакового разряда выходного регистра является знаковым выходом устройства.

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

43

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

4, первый сумматор 5 по модулю два, ключи 6, коммутатор 7,шестой, седьмой,, восьмой, девятый и десятый эдементы

ИЛИ 8, выходной регистр 9, пятый и шестой элементы ИЛИ 10, первый, второй, третий и четвертый элементы И 11, двенадцатый и тринадцатый элементы

ИЛИ 12, шифратор 13, первую и вторую группы элементов 14 и 15, суммматор

16 по модулю Р, второй сумматор 17 по

0 ф модулю два, третью группу элементов

ИЛИ 18, вход 19 константы Р устройства, выход 20 устройства, знаковый выход 21 устройства.

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

0,25 части арифметической таблицы коммутатора (табл. М 1, для Р=11).

Т а б л и ц а 1 () у. 1 2 3 " 5

1 1 2 3 4

2 2 4 6 8 10

3 3 6 9 1 4

4 4 8 1 5 9

5 5 10 4 9 3

Если два числа Х и У заданы по основанию Р в виде табличного умножения х=($>,х„.), у=(f>,у. ), то для того, чтобы получить произведение этих чисел по модулю Р, достаточно получить произведение xy(mod Р) в коде табличного умножения и инвертировать его индекс в случае, если " отлично от

Ь Р1-4 0, если 0= ", Зх 1 если P4 4 cx

2 1

При реализации операции модульного умножения возможны два основных способа введения знака:

- представление чисел в искусственной форме, т. е. А =А+Р/2; — введение знака в явном виде, т.е.. сопровождать число А признаком

Я его знака sign А.

Условимся, что, если А Ъ О, то QА=

=О, а если А <О, то Q.А=1. В первом способе диапазон 1 О, P-1) представимых чисел А уменьшается в два раза, г так как числа, лежащие в интервале 0, — -1), обозначают отрицательные числа А, а в интервале 1 « +1), р-1)положительные. Это значительно сужает

Функциональные возможности устройства.

Кроме этого, определение знакового признака Я.А А чисел, представленных ! в искусственной форме, вызывает необходимость значительных дополнительных аппаратурных затрат.

Наиболее просто реализуется второй способ - введение знака числа А в явном виде. Во-первых, конструктивно

5 просто реализовать признак Q.A +. тджх во-вторых, диапазон представимых чисел за счет введения признака QA увеличивается вдвое. И, наконец, при введении знака в явном виде для реалиэа- 5 ции операции модульного умножения нет необходимости применять критерий переполнения.

-А+А А А " А+д 1

1+ 1 г- +A - 10 как в случае сложения.

Для модульного умножения признак

Q.ä„ ä ðå3óëüòàTà операции формируется сумматором по модулю два (табл. 2), 9764

Таблица 2

+A +A.+

0 0 0

0 1 . 1

1 0 1

1 1 0

25 д ) у д в

И 14 и 15 первой и второй групп. Если

50 =О, то операнд с выхода шифратора

9 через открытые элементы И 15 второй группы, элементы ИЛИ 18 поступает на выход 20 устройства. Если у =1, то операнд через открытые элементы И 15 второй группы поступает на первые вхоСпециальный код табличного, умножения

Специальный код табличного умножения

Число . Цифра

Р„)4 а„.

Число Цифра

$g Q„.

0 1 1

1 0 0

0 1

2 0 0

3 0

4 0 0

0 1

0 1

Таким образом, выходной операнд представляется в специальном коде табличного умножения (табл. 3).

1 Таблица 3

40 6 сумматора 17. С выходов дешифраторов

2 операнды, в унитарном коде, через элементы ИЛИ 3, ключи 6 поступают на соответствующие входы коммутатора 7.

Коммутатор 7 определяет результат операции xy(mod P), который через элементы ИЛИ8 поступает на соответствующий вход регистра 9, и одновремен" но поступает на пятый или шестой элемент ИЛИ 4, и далее через первый сумматор 5 по модулю два и определенный элемент И 11, элемент ИЛИ 12 на нулевой или единичный входы регистра 9, определяя индекс ", результата операции. Сигнал нулевого, "Х = <„ ) или единичного (g> f. ф„ ) выхода сумматора

5 поступает на второй вход соответствующего элемента И 11. Сумматор 17 формирует, в соответствии с табл.2, признак Й. 1, который поступает на знаковый разряд регистра 9. Таким образом, в выходном регистре 9 содержится результат операции модульного умножения в специальном коде табличного умножения хУ=(91 3 q x„y„(mod P, )) °

Операнды регистра 9:,çíà÷åíèÿ от 1 о пост пают на вхо ы элемента ды сумматора 16, à на вторые входы сумматора 14 поступает значение константы P в двоичном коде. С выхода сумматора 16 инвертированный по модулю P операнд, через элементы ИЛИ 18 поступает на выход 20 устройства.

5 0 0

6 1 0

1 0

8 1 0

9 1 0

10 1 0

0 1

7 1 1

1 1 3

1 1 2

-10 1 1

50

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

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

Таким образом, предложенное устрой ство обрабатывает по модулю как положительные, так и отрицательные числа и выдает результат в двоичном коде, что делает его совместимым со всеми. трактами современных ЦВМ.

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

Устройство для умножения чисел по модулю по авт. св. 1" 922731, о т л ич а ю щ е е с я тем, что, с целью расширения функциональных воэможнос" тей путем перемножения как положительных, так и отрицательных чисел, а также получения результата в двоичном

7 9764 коде, устройство содержит две группы элементов И, четвертую группу элементов ИЛИ, шифратор, сумматор по модулю P (P -модуль, по которому работает устройство), второй сумматор по модулю два, причем выходы знаковых разрядов входных регистров подключены к входам второго сумматора по модулю два, выход которого подключен к входу знакового разряда выходного регистра, 10 информационные выходы выходного регистра подключены к соответствующим входам шифратора, выходы которого подключены к первым входам соответствующих элементов И первой и второй 3 групп, вторые входы которых соответственно объединены и подключены к первому И второму индексным выходам выходного регистра, выходы элементов И пер40 8 вой группы подключены к входам первой группы сумматора по модулю Р, входы второй группы которого объединены и подключены к bxoAy константы Р устройства, а выходы подключены к первым входам элементов ИЛИ четвертой группы, вторые входы которых подключены к выходам соответствующих элементов И второй группы, выходы элементов ИЛИ четвертой группы являются информационным выходом устройства, выход знакового разряда выходного регистра является знаковым выходом устройства.

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

1. Авторское свидетельство СССР и 922731, кл. G 06 F 7/49, 1978 (прототип).