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

 

, 981990

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

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

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

Соцнапнстнческик

Республик (61) Дополнительное к авт. свнд-ву (51)М. Кл. (22) Заявлено 10.02.81 (21) 3247220/18 24 с присоединением заявки М (л 06 Р 7/49

Гааударстееявьй кемятет

СССР (23) Приоритет (53) УД 681.325 (088.8) Опубликовано 15.12 82 Бюллетень ¹ 46 яе. девам язебретеякй и атерытий

Дата опубликования описания 17,02.83 (72) Авторы изобретения

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

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

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

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

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

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

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

ro и четвертого элементов И, вторые вхо ды первого и третьего элементов И и

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

ИЛИ подключены ко входам соответственно первого и второго элементов И, выходы которых подключены ко входам пятого элемента ИЛИ, вторые входы элементов И первой группы и элементов И второй группы объединены и подключены к выходу пятого элемента ИЛИ, а выходы " подключены соответственно к первым и вторым входам соответствующих элементов ИЛИ третьей группы, входы k-го элемента И третьей группы (4=1j ) подклн чены к 1 -му B 1 -му выходам сооТ ветственно первого и второго дешифраторов (1= 1,2,...-,Р-1; 1 = 1,2,..., Р 1), для которых (A> В„ ) A ° ° В, где (А и В - исходные числа, (° ) -искусственная форма произведения, Х -искусст»

l венная форма операнда Х}, выходы элементов И третьей группы подключены ко входам шестого элемента ИЛИ, выход ,которого подключен к первым входам элементов И четвертой и патой групп, выходы выходного регистра подключены к соответствующим входам дешифратора, выходы которого подключены ко вторым входам соответствующих элементов И четвертой группы и к входам первой группы сумматора по модулю Р, вторая группа входов которого подключена к выходам соответствующих элементов И пятой группы, вторые входы которых объединены и являютса входом константы Р устройства,. выходы элементов И пятой группь1 и сумматора по модулю

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

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

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

Алгоритм получения результата операции определяется соотношением, если два числа А и В заданы по модулю Р в коде табличного умножения А = (®„, Д ), В = (y>, p), то для того, чтобы. получить произведение этих чисел по модулк

Р, достаточно получить произведение

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

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

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

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

35 первой и второй групп первого и второго дешифраторов подключены соответственно к первым и вторым входам, элементов

ИЛИ первой и второй групп и ко входам

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

45 второй групп, вторые входы которых объедии4ны и являются управляюшим входом устройства, а выходы подключены соответственно к первой и второй группам входов коммутатора, выходы элементов ИЛИ третьей группы подключены к соответст

50 вуюшим входам выходного регистра, со.держит два элемента И, четыре группы элементов И, шифратор, шестой элемент

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

9Si990

Таблнца3

О, если 0 С g (— —.1;

Р

1, еслй — +1 (Q.(.p, Пусть Р = 2 К(К вЂ” натуральное число). Обозначаем P = . Оперируем 10 с числами, лежащими в диапазоне О 4 А Р. Принимаем в качестве нуля число

Р, и представляем числа в виде А =

Р+А.

В принятом представлении (искусственная форма) будем иметь дело с по ложительными числами. Однако числа в интервале 0, Р ) отображают отрицательные числа, а в интервале (Р,Р-1)положительные. Это показано (для P = 6) 20

В табло le

Та бли ца 4

Таблица 1

Матрица коммутатора, реализующего опе-З> рапию модульного умножения, представлена в табл. 2 (P = 6) °

Таблица 2

Известно, что (А В) = А В или А В + Р

В табл. 6 указаны такие пары чисел для .4з P 6 (Р = 3). 1 \ Таблниа6,Величины О, P и Р можно не кодировать (табл. 2), T&K как умножение на эти B&».

:личины дает ноль, н в этом случае.опе рация будет выполнена быстрее простым . °

М .анапизом операндов А и В. В этом случае табл. ¹ 1 и 2 преобразуются и при..

" нимают вид (табл. ¹ 3 и 4).

:id р (таад Р) в коде табличного умноже= ния и инвертировать его индекс . в случае, если ф,„отлично от ">, где

В данной схеме модульного умножения

:также используются свойства симметрии

:арифметической таблипы, и при этом

2S используется вышеприведенный алгоритм модульного умножения. В качестве таб .:лицы коммутаторов, реализующего операцию модульного умножения, используем

Н квацранттабл-. 4. Числовые значения, 30 йрисваиваемые схемам совпадения И

Э .и размещение входных шин коммутатора

:представляются табл. 5.

Таблица5

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

981990 8 тов И в четвертой группе равно количе"-ству двоичных разрядов .в записи числа P.

Сумматор 27 осуществляет суммирование по модулю Р операнда выходного регистра 25 и значения Р представленных двоичным кодом.

Количество возможных различных пар чисел определяется как 5 = С р +

+(Р - 2).

В частном случае нашего примера 5 =

=С + 4 = 16, где С„„= (W-1) ... п-K - 1) - число размещений из rn элементов.

Для четырех пар чисел (см. табл. 6) нет необходимости корректировать результат операции, так как по значениям опе

t рандов А и В из табл. 5 определяется !

А В = AB. Для остальных операндог (двадцати) А В + Р = А В.

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

Блок-схема устройства содержит первый и второй входные регистры 1 и 2, первый и второй дешифраторы 3 и 4, первая, вторая, третья и четвертая груп35 пы элементов ИЛИ 5 — 8, первая и. вторая группы ключей 9 и 10, коммутатор 11, первая, вторая, четвертая и пятая группы элементов И

12 — 16,второй, третий, четвертый, пя-.

40 тый и шестой элементы ИЛИ

17 — 22 q первый и второй элементы

И 23 и 24, выходной регистр 25, шифратор 26, сумматор 27 по модулю Р, вход 28 константы Р, выход 29 устройства, управляющий вход 30 устройства, информационные входы 31 и 32 устройства е

Коммутатор 11 представляет матрицу ответов, состоящую из элементов И. Элв- менты И, которым присвоен одинаковый результат операции, объединяются обшей выходной шиной. Количество элементов

И в первой группе равно количеству пар операндов, для которых (А В) = А В H (для P = 6 в первой группе четыре элемента И, табл. 6). Количество элементов

И третьей группы и количество элеменУстройство работает следующим образом.

По входным шинам 31 и 32 операнды в двоичном коде поступают на входные регистры 1 и 2, с которых операн.= ды чисел поступают на свои дешифрато-. ры 3 и 4. Операнды с выходов дешифраторов 3 в унитарном коде, поступают на соответствующие элементы 5 первой и 6 второй группы ИЛИ и на соответствуюшие элементы ИЛИ 17 - 20.Сигнал шины 30 открывает- ключи 9 и.10 и операнды одновременно поступают на соответствующие входы коммутатора 11, Если ) =, то элементы И 23 и.24 закрыты и выходной сигнал -с пятого элемента ИЛИ 21 отсутствует. Элементы И 13 второй группы, à 12 первой группы открыты. Выходной сигнал результата операции с выхода коммутатора 11 через элемент И 12 первой группы, через элемент ИЛИ 7 третьей группы поступает на соответствующий вход регист ра 25. Если " фу, то выходной сигнал коммутатора через открытый элемент И

13 второй группы, элемент ИЛИ 7 третьей группы поступает на соответствуюший вход регистра 25. С выхода шифратора

26 операнд в двоичном коде поступает на вторые входы элементов И 15 четвертой группы и на вторые входы сумматора 27. Если для данных А и В

f (А В) = А В, то на выходе шестого элемента ИЛИ 22 присутствует сигнал.

Этот сигнал закрывает элементы И 16 пятой группы и открывает элементы И

15 четвертой группы. Операнд с выхода шифратора 26 через открытые злемен гы

И 15 четвертой группы, через четвертук группу элементов ИЛИ 8 поступает на выход 29 устройства. Если для данной пары операндов (А В) = А В + Р, то сигнал с шестого элемента ИЛИ 22 отсутствует. Операнд с выхода шифратора

26 поступает на один.из входов суммвтора 27, на другой вход которого через открытые элементы И 16 пятой группы по шине 28 поступает значение Р в двоичном коде. С выхода сумматора 27 опьf ранд (А В + P)maRP в двоичном коде, через четвертую группу элементов ИЛИ

8 поступает на выход 29 устройства.

$ ю !

9 98

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

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

Устройство для умножения чисел по модулю, содержащее первый и второй входные регистры, первый и второй дешифраторы, группу элементов И, первую, вторую и третью группы элементов ИЛИ, первую и вторую группу ключей, коммутатор, пять элементов ИЛИ, первый и второй элементы И, выхс.>,ной регистр, . причем входы первого и второго входных регистров являются информационными входами устройства, а выходы подключены ко входам соответственно первого и второго дешифраторов, выходы первой и второй групп первого и второго дешифраторов подключены соответственно к первым и вторым входам элементов ИЛИ первой и второй групп и ко входам сосл -. ветственно первого, второго, третьего и четвертого элементов ИЛИ, выходы элементов ИЛИ первой и второй групп подключены к первым входам соответствующих ключей соответственно первой и второй групп, вторые входы которых объединены и являются управляющим входам устройства, а выходы подключены соответственно к первой и второй группам входов коммутатора, выходы элементов ИЛИ третьей группы подключены к соответствующим входам выходного регистра, о т л и ч а ю ш е е с я тем, что, с целью расширения функцио- нальных возможностей путем перемножения как положительных так и отрицательных чисел, устройство содержит два элемента И, четыре группы элементов И, шифратор, шестой элемент ИЛИ, четвертую группу элементов ИЛИ, сумматор по модулю P (P -модуль, по которому ра1990 10 ботает устройство), первые входы элементов И первой группы объединены с первыми входами соответствующих элементов И второй группы и подключены к соответствующим выходам группы коммутатора, выходы первого и четвертого, второго и третьего элементов ИЛИ под» ключены по входам соответственно пер» вого и второго элементов И, выходы которых подключены ко. входам пятого элемента ИЛИ, вторые входы элементов

И первой группы и элементов И второй группы объединены и подключены к выходу пятого элемента ИЛИ, а выходы подключены соответственно к первым и вторым входам соответствующих эле ментов ИЛИ третьей группы, входы к-ro элемента И третьей группы (3(=1..j ) подключены к 1 -му и -му выходам со» ответственно первого и второго дешифраторов (1 = 1,2,...,Р-1; 1= 1,2,..., P-1), для которых (А "В ) = А.-В-, (где А и Висходные числа, (° ) - йскусственная форI ма произведения, Х. -искусственная форма операнда Х), выходы элементов третьей группы подключены ко входам шестого элемента ИЛИ, выход которого подключен к первым входам элементов И четвертой и пятой групп, выходы выходного регистра подключены к соответствук шим входам шифратора, выходы которого под» ключены ко вторым входам соответствуюших элементов И четвертой группы и к входам первой группы сумматора по мо-. дулю Р, вторая группа входов которого подключена к выходам соответствующих элементов И пятой группы, вторые входы которых объединены и являются вхо-, дом константы Р устройства, выходы элементов И .патой группы и сумматора по модулю P подключены соответственно ко входам соответствующих элементов

ИЛИ четвертой группы, выходы которых являются выходом устройства.

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

1. Авторское свидетельство СССР . М. 550636, кл. G.06 F 7/52, 1977.

2. Авторское свицетельство СССР по, заявке 142675156, кл.G 06 F 7/49, 1 8. 1 1.78 (прототип) .