Устройство для умножения в системе остаточных классов

 

«и922731

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

Социалистических республик

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву (51)М. Кл. (22)Заявлено 18.11.78 (21) 2675156/18-24 с присоединением заявки М (23) Приоритет

Опубликовано 23. 04 ° 82. Бктллетень М 15

Дата опубликования описания 23.04.82

G 06 F 7/52

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

СССР но делам изобретений и отнрытнй (53) УДК 681 ° 3 (088.8) (7Я) Автор изобретения

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

ОСТАТОЧНЫХ КЛАССОВ

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

Известны табличные устройства модульного умножения в системе остаточных классов (1 .

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

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

Цель изобретения - упрощение устройства.

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

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

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

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

Pj +1 где Р; — модуль таблицы. Это и определяет возможность реализации в схеме табличного умножения только

0,25 ч. таблицы.

2 3 4 5 6 7. 8 9 10

2 3 4 5 6 7 8 9 10

6 8 101 3 5 7 9

1 1

2 2

3 3 6 9 1 4 7 102 5 8

4 4 8 1 5 9 2 6 103 7

5 5 104 9 3 8 2 7 1 6

6 6 1 7 2 8 3 9 4 105

3 106 2 9 5 1 8 4

5 2 107 4 1 9 6 3

7 7

8 8

9 9 7 5 3 1 108 6 4 2

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

2731 4

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

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

Цифра!

20

25

Алгоритм получения результата операции определяется следующим соотношением: если два числа х и у заданы по основанию P в коде табличного умножения. х; = (g„, х;); у„ (f, у„), то для того, чтобы получить произведение этих чисел по модулю P, достаточно получить произИ ведение х1 y;/mod Р„) в коде табличного. умноженЙя и инвертировать его индекс г в случае, если у„ отлично от . где

Мр

P. -1

О, если 0.<х; <

Р„+1

1, если " (х ° < Р; -1.

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

На.чертеже изображена функциональная схема модульного умножения в системе остаточных классов по модулю П (P, =I I) .

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

Устройство содержит входные реги стры 1, дешифраторы 2, группы элементов ИЛИ 3, первый, второй, третий и четвертый элементы ИЛИ 4, сумматор 5 по модулю два, ключи 6, ком5 92273 мутатор 7, шестой, седьмой, восьмой,девятый и десятый элементы ИЛИ 8, выходной регистр 9, пятый и одиннадцатый элементы ИЛИ 10, первый,второй, третий и четвертый элементы И

11, двенадцатый и тринадцатый элемен- ты ИЛИ 12.

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

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

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

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

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

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

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

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

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

Этот сигнал представляет код индекса ("0" или "1").

Одновременно код результата модуль ного умножения поступает через элемент ИЛИ 8 на вход выходного регист55 ра 9 °

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

1 6

Необходимо отметить простоту реализации логических элементов И и ИЛИ и унификацию их для произвольного модуля.

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

7 922731 8 нулевому и единичному выходам сумма- входами выходного регистра, выход тора по модулю два, а выходы первого которого является выходом устройства и четвертого элементов И и соответ- Источники информации, ственно второго и третьего элемен- принятые во внимание при экспертизе тов И подключены к соответствующим s 1. Акушский И.Я., Юдицкий Д.И. входам двенадцатого и тринадцатого Машинная арифметика в остаточных элементов ИЛИ, выходы шестого,седь- классах. М., 1968, с. 331-334. мого, восьмого, девятого, десятого, 2. Авторское свидетельство СССР двенадцатого и тринадцатого элемен- 4 550636, кл. G 06 F 7/52, 1977 тов ИЛИ соединены с соответствующими 1О (прототип).

81/63 сное

ФМлиал ППП Патент, г.ужгород, ул.Проектная, ч операции