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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

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

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

Республик п>885999

Ф д (61) Дополнительное к авт. саид-ву (22) Заявлено 0211.79 (23) 2838013/18-24 с присоединением заявки ¹ (23) ПриоритетОпубликовано 301181 Бюллетень № 44, Дата опубликования описания 30.11.81 (51)М. Кл.з

G F 7/72

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

СССР по делам изобретений и открытий (53) УДХ 681.325 (088.8) (72) Автор изобретения

В.A.Êðàñíoáàåâ (71) Заявитель (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ И СЛОЖЕНИЯ

ЧИСЕЛ ПО МОДУЛЮ

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

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

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

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

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

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

885999

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

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

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

° соединены между собой и с выходом седьмого элемента ИЛИ, вторые входы третьего и четвертого элементов И первой группы соединены между собой и с. выходом восьмого элемента ИЛИ, содержит вторую, третью, четвертую и пятую группы элементов И, третью группу элементов ИЛИ, шесть элементов И, два элемента Й-НЕ, второй коммутатор, третью группу ключей, причем первая и вторая группы выхо дов первого коммутатора подключены соответственно к первым входам элементов И четвертой и пятой групп, выходы 1 -ых и (Р- j )-ых ключей первой и второй групп (=1,2,...,Р-1;

P - модуль) подключены ко входам соответствующих клюЧей третьей группы, выходы которых подключены ко входам второго коммутатора, первая и вторая группы - /2выходов которого псдключены к первым Р-4j2 входам соответственно седьмого и восьмого элементам ИЛИ, выходы 1 -ых и (Р-i)-ых элементов И четвертой группы подключены соответственно к первым .и вторым входам элементов ИЛИ третьей группы и ко вторым P-4/2 входам седьмого и восьмого элементов ИЛИ, выходы

1-ых и (Р- )-ых элементов И пятой группы подключены соответственно к третьим и четвертым входам элементов ИЛИ третьей группы и к третьим

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

M второй и .третьей групп и первый вход третьего элемента И объединены и подключены к выходу четвертого элемента

И; первый вход которого подключен к первому входу пятого элемента И ко

4р второму входу первого элемента И и является входом "Сложение" устройства,вторые входы четвертого элемента

И второй группы и первого элемента

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

И, второй вход которого объединен со вторыми входами элементов И четвертой группы и подключен к выходу пятого элемента И, второй вход которого подключен к нулевому выходу сумматора по модулю два, выходы первого второго, четвертого элементов И второй группы и выход третьего элемента И третьей группы подключены ко входам девятого элемента ИЛИ, вы55 ход которого подключен к первому входу первого элемента И-НЕ, выходы третьего элемента И второй группы и первого, второго, четвертого элементов И третьей группы подключены ко що входам десятого элемента ИЛИ, выход которого подключен к первому входу второго элемента И-НЕ, выходы первого и второго элементов И-НЕ подключены соответственно к ((Р+1)-му и (P+2)» д му входам выхоцного регистра, вторые

865999

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

1 Таблица 1 а1

4 ) 5 1 б

1 f 2 3

8 9

8 9

5,7

2 5

10 3

1 1

2 2

2 3 4 5 б

4 6 8 10 1

10 б б 9 1 4 7

3 3

4 4

5 5 б 6

7 . 7

8 8

9 9

10 10

9 2

8 1 5

10 4 9 3 6

1 7 2 8 3

3 10 б 2 9

5

8

5 2 10 7 4

7 5 3 1 10

9 8 7 б 5

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

4

2

1

1

1 б

8

10

Алгоритм получения результата операции модульного умножения определяется следующим образом. Если два числа А и В заданы по основанию Р . в коде табличного умножения A =(Я, ал); В =(Т, Рл ), то для того, чтобы получить произведение этих чисел по модулю Ъ1, достаточно получить произведение оцл (Ьл (мой p „ ) в коде табличного умножения и инвертировать его индекс 1" в случае, если ф отлично от у, где р, л 4

О, если О Ол g g

1, если — а g„- <Р.

Рл+ 4

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

Это определяется коммутативностью операции сложения.

В табл.3 показана реализация выполнения операции модульного сложения для Р =11 °.Таблица 2

1

3

5 бО

0 входы первого и второго элементов

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

Симметричность относительно левой диагонали опредсияюхся коммутативностью операции умножения, симметричность отсносительно правой диагонали определяется тем, что (Рч„)(РP ) ц (моЮ>

Симметричность относительно вертикали и горизонтали определяется тем, что сумма симметричных чисел кратна

Р„, т.е. с 1 ;+Ф; (К -14 =-О (О РА Ь„+(Р„. -a„) -)ь„= 0(вод Р„) 45

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

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

4 2 Э

885999

Таблица 3

1 . 2 3

2 3

2 3 4

4 5

5 б

7 8

8 9

1О

9 10

1О О о

1 2

9

10 о

7 8 9

1О О

2 3

3 4

5 б

3 4 5 б 7 4 5 6 7 8

5 б 7 8 9

6 7 8 9 10

8 9 10 О .1

9 10 О 1 2

10 О 1 2 3

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

Определены номера квадрантов ариф- 10 метической таблицы:

П (ц 1Ч

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

Устройство содержит входные регистры 1, дешифраторы 2, первая и третья группы элементов ИЛИ 3,4 и 5, первый, второй, третий, четвертый, пятый, шестой, седьмой, восьмой, де- 40 вятый и десятый элементы ИЛИ 6-15, первая, вторая и третья группы ключей 16, 17 и 18, первый и второй коычутаторы 19 и 20, первая, вторая, третья, четвертая и пятая гРуппы эле- 45 ментов И 21-25, сумматор 26 по модулю два, первый, второй, третий, четвертый, пятый и шестой элементы И

27-32, первый и второй элементы И-НЕ

33 и 34, выходной регистр 35. 50

Первый коммутатор 19 определяет результат модульного умножения табл.1 и операции модульного сложения для ц и »ф квадрантов табл.3 (т.е. для. .4"о О, Q =О, Я » =1, $g =1) . В зависи° ° ° ° сти от кода операции (умножения и и "сложения) первый коммутатор 19 определяет результат модульного умножения или сложения, т.е. первый коммутатор совмещает выполнение двух операций. 60

Первая и вторая группы выходов первого коммутатора 19 определяют результат модульного умножения, причем первая группа выходов определяет значения 1-: --. ф —, а вторая pj+<(2-. 65

-.Р -» . Третья и четвертая группы вы-. ходов первого коммутатора 19 определяют результат модульного сложения для И и IV квадрантов табл.3, причем третья группа .выходов определяет значение g-; p„ -qJ2, а чет.вертая Р1+»/2-.Р. -1.

Величины 0 и Р не кодируются, так как при умножении на эти величины результат равен нулю, и в этом случае операция выполняется быстрее простым аналйзом операндов, при сложении с этими величинами значение второго операнда не изменяется, он и определяет результат операции, при определении результата операции со второго коммутатора (I, II» квадранты) выходная шина, объединяющая элементы И, которым присвоен результат модульного сложения О и Р,;(правая диагональ табл.3), подключается непосредственно к выходу устройства. При необходимости значения О и Р могут быть также включены в табл.2.

Второй коммутатор 20 определяет результат модульного сложения для

I и Щ квадрантов (табл.3) . Первая группа выходов второго коммутатора определяет значения 4-: „. g/g, а вторая Р„.+4/й-:Р„--»

Первый 19 и второй 20 коммутаторы (матрицы ответов) представляют набор элементов И. Количество элементов И каждого коммутатора равно (Р„-1)Ч4. Элементы И, которым присвоен одинаковый результат операции, объединяются выходной шиной. В коммутаторах осуществляется операция в унитарном коде. Результат операции также представляется в унитарном коде. Количество выходных шин второго коммутатора 20 равно Р„ -1, он определяет Результат модульного

885999

20

35

50

55 бО

65 сложения для и III квадрайтов.

Первая группа выходов объединяет шины, которым присвоен результат модульного сложения g-;P - «/2, а вторая группа Р1+.!/2 P

Количество выходных шин первого коммутатора 19 равно 2 (Р -1), так как коммутатор 19 определяет резуль тат модульного умножения (первая и вторая группы выходов определяют, соответственно, значения :Pq-М и „. +!/g р„. q,для умножения} и. результат модульного сложения для,!! и IV квадрантов (третья и четвер ая группы выходов определяют, соответственно, значения

g + Р.; « /g и.Р„ +Ц2- Р1 g для сложения ).

Таким образом, каждому элементу

И коммутатора 19 присваивается два значения: результат модульного умножения и результат модульного сложения (для !! и «ч квадрантов).

Количество элементов первой и второй, и третьей групп элементов

ИЛИ 3, 4 и 5 равно P †4 /2 в каждой группе. Количество элементов И четвертой 24 и пятой 25 групп элементов И равно Р1 -1 в. каждой группе.

Выход элемента ИЛИ 14 определя= ет значение Я" =1, а выход элемента

ИЛИ 15 — 7 =--О.

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

Первый режим работы — определение результата модульного умножения.

На входные регистры 1 заносятся операнды и последовательно через дешифраторы 2, группы элементов ИЛИ

3 и 4 и,группы ключей 16 и 17 поступают на коммутатор 19. Ключи 16 открываются сигналом с управлякщего входа устройства. Одновременно присутствует сигнал "Умножение" устройства. Выходной сигнал коммутатора 19 через один из элементов И 25 пятой. группы поступает на один из шести входов определенного элемента

ИЛИ 5 третьей группы. С выхода этого элемента сигнал поступает на соответствующий вход выходного регистра 35. Элементы 12, 13, 21, 10, 11, 22, 23, 14, 15, 33 и 34 служат для опрецеления индекса g в записи результата модульной операции. Коммутатор 20 закрыт, так как отсутствует сигнал "Сложение" устройства.

Второй режим работы — определение результата операции модульного сложения для !! и Я квадрантов таблицы модульного сложения (т.е.@«=у =

-"0 и Я С«= р =1). В этом случае сиг" нал "Сложение" устройства присутствует. Коммутатор 20 закрыт, так как отсутствует сигнал с единичного выхода сумматора 26 по модулю два(+ф= 0(пч03 ) ), элемент И 27 закрыт. и, следовательно, ключи 18 третьей группы закрыты. Группа элементов И 25 пяток группы закрыта (отсутствие сигнала "Умножение" устройства). Выходной сигнал коммутатора 19 по третьей и четвертой группам выходов (по одной из шин этих групп ) через один из элементов И 24 четвертой группы, элемент ИЛИ 5 третьей группы поступает на выходной регистр 35.

Третий режим работы — определение результата операции модульного сложения для t u fff квадрантов таблицы модульного сложения ("..е. для

=Оу р =1 и Д =1у "р, =О) . Сигнал "Сложение" устройства присутствует, а сигнал "Умножение" устройства отсутствует. Коммутатор 20 открыт, а на выходных шинах коммутато1 ра 19 отсутствует выходной сигнал, так как элементы И 24 и 25 четвертой и пятой групп закрыты. .Ключи 18 третьей группы открыты (на выходе элемента И 27 присутствует сигнал) и коммутатор 20 определяет результат модульного сложения для и Ilf квадрантов.. Для =1, =0 значение индекса у в записи результата модульного сложения определяется с выходов элементов ИЛИ 14 и 15. Для О « =О, g>--1 значение определяется ийвертированием выходных сигналов элементов ИЛИ 14 и 15.

Таким образом, изобретение совмещает выполнение операций модульного умножения и сложения в коде табличного умножения (табл.2). При этом таблица реализующая операцию умножения, может быть конструктивно уменьшена в четыре раза, а таблица, реализующая операцию сложения — в два раза.

Если для реализации операции умножения и сложения без применения специального кода умножения необходимо 2 ° (Р -Ц элементов табл.1 и 3, то с применением кода (табл.2). †(Р -4) /2 элементов таблиц. При применении специального- кода умножения сокращается также количество элементов входных, выходных регистров и дешифраторов.

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

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

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

ИЛИ, шесть элементов И, два элемента И-НЕ, второй коммутатор, третью группу ключей, причем первая и вторая группы выходов первого коммутатора подключены соответственно к первым входам элементов И четвертой и пятой групп, выходы 1 -ых и (Р-j)-ых ключей первой и второй групп (=1, 2,...,Р-1; Р - модуль) подключены ко ,входам соответствующих ключей третьей группы, выходы которых подключены ко входам второго коммутатора, 40 первая и вторая группы Р-4(2 выходов которого подключены к первым (2 входам соответственно седьмого и восьмого элементов ИЛИ, выходы ; -ых и (Р- 1.)-ых элементов И 45 четвертой группы подключены соответственно к первым и вторым входам элементов ИЛИ третьей группы и ко вторым Р- 4 и входам седьмого и восьмого элементов ИЛИ, Выходы $ -ых и (Р- j)-ых элементов И пятой группы подключены соответственно к третьим и четвертым входам элементов ИЛИ третьей группы и к третьим Р-4)2.входа седьмого и восьмого элементов

ИЛ, (-2)-ые и (Р- )-ые выходы в рого коммутатора подключены соответственно к пятым и шестым входам соответствующих элементов ИЛИ третьей группы, выходы которых подключены к первым Р входам выходного регистра, первые входы элементов И второй и третьей группы объединены и подключены соответственно к выходам пятого и шесl того элементов ИЛИ, управляющие входы ключей третьей группы объединены и подключены к выходу первого элемента И, к первому входу второго элемента И, ко вторым входам первого и четвертого элементов И, соответственно, второй и третьей групп, вторые входы вторых элементов И второй и третьей, и пятой групп объединены и являются

"УмнЬжение" устройства, вторые входы третьих элементов И второй и третьей групп и первый вход третьего элемента И объединены и подключены к выходу четвертого элемента И, первый вход которого подключен к первому входу пятого элемента И, ко второму входу riepвого элемента И и является входом

"Сложение" устройства, вторые входы четвертого элемента И второй группы и первого элемента И третьей группы объединены и подключены к выходу-третьего элемента И, второй вход которого объединен со вторыми входами элементов И четвертой группы и подключен к выходу пятого элемента И, второй вход которого подключен к нулевому выходу сумматора по модулю два, выходы первого, второго, четвертого элементов И второй группы и выход третьего элемента И третьей группы подключены ко входам девятого элемента ИЛИ, выход которого подключен к первому входу первого элемента И-НЕ, выходы третьего элемента И второй группы и первого, второго, четвертого элементов И третьей группы подключены ко входам десятого элемента ИЛИ, выход которого подключен к первому входу второго элемента И-НЕ, выходы первого и второго элементов И-НЕ подключены соответственно к (Р+1) -му и

{ Р+2) -My входам выходного регистра, вторые входы первого и второго элементов И-НЕ объединены и подключены к выходу второго элемента И, первый вход шестого элемента И подключен к выходу четвертого элемента ИЛИ, вторые входы второго и шестого элементов И объединены и подключены к выходу второго элемента ИЛИ, выход шес того элемента И подключен ко второму входу четвертого элемента И.

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

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

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

2. Авторское свидетельство СССР по заявке В 2675156/18-24, кл. G 06 F 7/49, 1978 (прототип)885999

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

Техред З.фанта КорректорС.Щомак

Редактор И.Михеева

Подписное

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

Заказ 10544/70 Тираж 748

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

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