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

 

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

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

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

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

Республик (»)96880S (6! ) Дополнительное к авт. саид-ву. g 922731 (22)Заявлено 08.12.80 (2I ) 3213286/18-24 (53)N. Кл.

G06 F 7/49 с присоединением заявки М

3Ьеударетаанай квинтет

CCCP ав делам наееретений н втнритнй (23) Приоритет—

Опубликовано 23.10.82 Бюллетень М39 (53) УДК 681.325 (088.8) /

Дата опубликования описания 01.11-82

А. В. Королев и В. А. Краснобаев. (73) Авторы изобретения (71) Заявитель (54) УСТРОЙСТВО ДЛЯ МОДУЛЬНОГО

УМНОЖЕНИЯ

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

По основному авт. св. № 922731 иэJ вестно устройство для умножения в систе. ме остаточных классов, содеркашее вход--ные регистры, дешифраторы, ключи, коммутатор, выходной регистр, а также сумматор по модулю два, группы элементов

ИЛИ, элементы И и ИЛИ, причем первый и второй входные регистры последова-, 10 тельно через соответствуюшне первый и второй дешифраторы, первую и вторую группы элементов ИЛИ, первый и второй ключи подключены соответственно к первой и второй группам входов коммутатора, 15 .- первые и вторые группы входов первого и . второго дешифраторов подключены соответственно к входам первого, второго и третьего, четвертого элементов ИЛИ, выходы которых подключены к соответствуюшим входам сумматора по модулю два, управляющие входы ключей являются входами управления устройства, первая группа входов коммутатора подключена к входам пятого элемента ИЛИ и первым входам шестого, седьмого, восьмого, девятого и десятого элементов ИЛИ, к вто» рым входам которых подключена вторая группа выходов коммутатора и вход одиннадцатого элемента ИЛИ, выход которого подключен к первым входам первого и второго элементов И, выход пятого элемента ИЛИ подключен к первым входам третьего и четвертого элементов И, вторые входы первого и третьего элементов

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

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

968808 рого является выходом устройства 1).

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

UBN. 1Е

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

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

И группы (j = 2„4, 7 ..., (Р - 1)/2) д объединены.и подключены к второму выходу выходного регистра (1 = 1, 3, P - 1; ) = 2, 4, ...,. P npu P — четном;

=1,3,...,P, j=2,4,...,P-1 при P — нечетном), вторые входы 1-ых и 1 -ых элементов И группы попарно объединены и подключены к соатветствушим -ым выходам выходного регистра (8 = 3, 4, ..., (P — 1)/2 + 2, при Pнечетном; (= 3, 4, ..., P/2 + 2 при, 3$

P - четном).

В данном устройстве используются свойства симметрии арифметической таблицы относительно диагонали, вертикал. и горизонтали, проходящих между вели- 4п чинами (P — 1 2 и (P + 1)/2, где

P. — модуль таблицы. Это определяет I возможность реализации в схеме таблич ного умножения только 0,25 части таблицы (для P = 11 приведена табл. 1). 4

Операция модульного умножения выполняется в коде табличного умножения, представленного в табл. 2. . Алгоритм получения р зультата опер - 50 ции определяется следующим соотношением: если два числа y, è у заданы по основанию Р; в коде табличного умножения }(= (Z» у.„-} Ч= (X V ),то для того, чтобы получить произведение этих чисел по модулю Р достаточно получить произведение»У (wORP} в коде табличного умножения и инвертировать

его индекс у в случае, если х отлично фч, где:

О,ЕСЛИ О Х (Р-1)/2, У» 4,Осли (Р+ )!1 Х р.

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

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

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

9, пятый и одиннадцатый элементы ИЛИ

10, первый. второй, третий и четвертый элементы И 11, .двенадцатый и тринадцатый элементы ИЛИ 12, группу элементов И 13.

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

Входы устройстве по кодовым цепям С и связываются входными регистрами 1 с цифровой вычислительной машиной.

С входных регистров 1 операнды чисел поступают на свои дешифраторы 2. Дешифраторы служат для преобразования операндов машинного представления в унитарный код. Сигнал с выхода дешифратора 2 строк (столбцов) одновременно поступает на двухвходовые 3 и пятивходовые 4 элементы.

ИДИ. Сигнел с выхода двухвходового элемента ИЛИ поступает на один из ключей

6 строк (столбцов). Управляющий сигнал от устройства управления одновременно поступает на ключи 6 (строк и столбцов), с выхода которых сигналы поступают не коммутатор 7 (матрицу ответов).

Сигнал с выхода пятивходового элемента ИЛИ 4 поступает на единичный или нулевой входы сумматора по модулю два 5.

С единичного или нулевого выхода сумматора 5 (в зависимости от результата модульного сложения) сигнал поступает на два элементе И 11.

В зависимости от результата модульного умножения на один из вторых входов элементов И 11 поступает сигнал с выхода матрицы ответов через один из двух элементов ИЛИ 10. Выбор одного из двух элементов ИЛИ зависит от того, к какой группе (0-5 или 6-10) относится результат модульного умножения, Сигнал с выхода элемента И 11 поступает на вход элемента ИЛИ 12, выход которого соединяется с входом выходного регистра 9. Этот сигнал представляет код индекса ("0" или 1 ). Одновременно код

Таблица 1.

1 1 2 3 4 5 6 7 8 9 10

2 2 4 6 8 10 1 3 5 7 9

3 3 6 9 1 4

4 4 8 1 5 9

7 10

2 6

2 5 8

10 3 7

5... 5 10 4 9 3 8 2 7 1 6

6 6 1 7 2 8 3 9 4 10 5

3 10

6 2

9 5

7 7

1 8 4

8 8 .5 2 10 7 4 1 9 6 3

7; 5 3 1 10 8 6 4 2

9 9

10 10 9 8 7 6 5 4 3 2 1

Таблица 2

1

0

5 968808 6 результата модульного умножения посту- ичный код, пригодный для дальнейшей пает через элементы ИЛИ 8 на вход вы обработки. ходного регистра 9, с выхода кото- Таким образом введение в состав устрого поступает на входы соответст- ройства группы элементов И позволяет вующих элементов И группы . 13, ae расширить функциональные возможности происходит преобразование унитарного устройства за счет получения результата кода результата с индексом в дво- в двоичном коде.

7 088808 8

Ф о р м у л а и з о б р е т е н и и ны и подключены ко второму выходу выходного регистра (1 = 1, 3, ..., P- 1;

1 1

Устройство для модульного умножения . = 2, 4..., P при Р - четном; = 1, по авт. св. % 922731 отличаю» 3, ..., P; .) 2, 4, ..., P-1 прн P - не .щ е е с я тем, что, с целью расширения > ччееттнноомм)), вторые входы .4-ых и -ых

I функциональных возможностей за счет элементов И группы попарно объединены получения результата умножения в коде и подключены к соответствуюшим р-,ûì

1 и Р, оно дополнительно содержит груп- выходам выходного регистра (1 = 3, 4, пу из P элементов И (P - модуль по ко-, ..., (P-1)/2+2, при P - нечетном; торому работает устройство), выходы ко-, . с 3, 4, ..., Р/2+2 при P четном).

:1Ф ь торых являются выходами устройства, Источники информации первые входы 4 -ых элементов И груп принятые во внимание при экспертизе пы объединены и подключены к первому . 1. Авторское свидетельство СССР по выходу выходного регистра, первые вхо- заявке l4 2675156/18-24, ды j -ых элементов И группы объедине кл. GO6 t- 7/39, 1978 (прототип).

968808 . Рслулиюж елюрацам

ВНИИПИ Заказ 8176/77 Тираж 731 Подписное

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