Устройство для умножения чисел по модулю Советский патент 1982 года по МПК G06F7/49 

(54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЧИСЕЛ ПО МОДУЛЮ

Изобретение относится к вычислительной технике. Известно устройство для модульного умножения в системе остаточных классов содержащее дешифраторы, вентили, ключи операционную матрицу, группы элементов ИЛИ, ферритовые линейки, блок хранения арифметических таблиц, логические схемы и соответствующие связи fl 3 Недостаток устройства - ограниченные функциональные возможности, заключающиеся в том, что модульное умножение выполняется только в области положифель ных чисел. Наиболее близким к изобретению техническим решением является устройство для умножения в системе остаточных классов, содержащее входные регистры, дешифраторы, ключи, коммутатор, выходной регистр, а также сумматор по модулю два, группы элементов ИЛИ, элементы И и ИЛИ, причем первый и второй входные регистры последовательно через соответствующие первый и второй раторы, первую и вторую группы элементов ИЛИ и первый и второй ключи псдклк чены соответственно к первой и второй группам входов коммутатора, первые и вторые групцы входов первого и второго дешифраторов подключены соответственно ко входам первого, второго и третьего, четвертого элементов ИЛИ, выходы которых подключены к соответствующим входам сумматора по модулю два, управляющие входы ключей являются входами управления устройства, первая группа входов коммутатора подключена ко входам пятого элемента ИЛИ и первым входам щестого, седьмого, восьмого, девятого и десятого элементов ИЛИ, ко вторым входам которых подключена вторая группа выходов коммутатора и входу одиннадпг того элемента ИЛИ, выход которого подключен к первым входам первого и второго элементов И, выход пятого элемента ИЛИ подключен к первым входам третье го и четвертого элементов И, вторые вхо-v ды первого и третьего элементов И и второго и четвертого элементов И подключены соответственно к нулевому и единичному выходам сумматора по модулю два, а выход первого и четвертого элементов И и соответственно второго и третьего элементов И подключены к соответствующим входам двенадцатого и тринадцатого элементов ИЛИ, выходы шестого, седьмого, восьмого, девятого, десятого, двенадцатого, тринадцатого элементов ИЛИ соединены с соответствук шими входами выходного регистра, выход которого 5голяется выходом устройства 2 Недостаток этого устройства также ограниченные функциональные возможноети, заключающиеся в том, что модульное умножение выполняется только в области положительных чисел. Цель изобретения - расширение функциональных возможностей устройства путем перемножения как положительных, так и отрицательных чисёй. Поставленная цель достигается тем, что устройство для умножения чисел по модулю, содержащее первый и второй входные регистры, первый и второй дешифратрры, группу элемёйтов И, первую, вторую и третью группы элементов ИЛИ, первую и вторую группу Ключей, коммута :. . элементы И, выходи ей регистр, причем входы первого и второго входных регистров являются информационными, входами устройства, а выходы подключены соответственно ко входам соответственно первого и второго дещифраторов, выходы первой и второй групп первого и второго де11Ш(|фаторов подключены соответственно к первым н вторым входам .элементов ИЛИ первой и второй групп и ко входам соответственно первого, второго, третьего и четвертого элементов ИЛИ, выходы ИЛИ первой и второй групп подключены к входам соответствующих ключей соответственно первой и второй групп, входы которых объ динены в являются управляющим входом устройства, а выходы подключены соотве ственно к первой и второй группам входо коммутатора, выходы элементов ИЛИ третьей группы подключены к соответствующим входам выходного регистра, содержит два элемента И, четыре группы элементов И, шифратор, щестой элемент ИЛИ, четвертую группу элементов ИЛИ, сумматор по модулю Р (Р-модуль, по которому работает устройство), первые входы элементов И первой группы объединены с первыми входами соответствую их элементов И второй группы и подлючены к соответствующим входам групы коммутатора, выходы первого и чет ертого, второго и третьего элементов ЛИ подключены ко входам соответствено первого и второго элементов И, выхоы которых подключены ко входам пятоо элемента ИЛИ, вторые входы элеменов И первой группы и элементов И втс рой группы объединены и подключены к ыходу пятого элемента ИЛИ, а |выходь1 ; одключены соответственно к первым и вторым входам соответствующих элеменов ИЛИ третьей группы, входы k-ro эле- ента И третьей группы (i. ij ) подклюьены к i -му и j -му выходам соответственно первого и второго дещифраторов ( i 1,2,...,Р-1} j 1,2,..., Р-1), для которых (А В) А В(- , где (А и В - исходные числа, ( )-искусственная форма произведения, Х-искусственная форма операнда X), выходы элементов И третьей группы подключены ко входам шестого элемента ИЛИ, выход .которого подключен к первым входам элементов И четвертой и пятой групп, выходы выходного регистра подключены к соответствующим входам дещифратора, выходы которого подключены ко вторым вход соотТегствуюшюсэлементов и четвертой группы и к входам первой группы сумматора по модулю Р, вторая группа входов которого подключена к выходам соответствующих элементов И пятой группы, вторые входы которых объединены и явл5потся входом константы Р устройства,, выходы элементов И пятой группы и сумматсфа по модулю Р подключены соответственно ко входам соответствующих элемент ов ИЛИ четверотой гругшы, выходы которых являются выходом устройства. В схэме модульного умножеяпя прототипа используется свойство симметрии арифметической таблицы коммутатора относительно диагоналей, вертикали и горизонтали, проходящих между величинами - - 1 и -у +1. Это и определяет возможность реализации в схеме таблнчногч умножения только 0,25 части таблицы. Алгоритм получения результата операции определяется соотнощением, если два числа А и В заданы по модулю Р в коде табличного умнозкения А - (д 3 }, В то для того, чтобы получить произведение этих чисел по модулк Р, достаточно получить произведение

ct ft (mo P) в JCOfle табличного умножения и инвертировать его индекс в случае, если Jf отлично от ,, гйе

0,если у,-1;

То|-Р

1,если est.Cp.

Пусть Р - 2 К(К - над-уральное число). Обогжачаем Р -. Оперируем с числами, лежацдалот в диапазоне О 4 . Принимаем в качестве нуля число Р , и представляем числа в виде А А. В принятом представлении (искусст-ветшая форма) будем иметь депо с по ложнтепьными числами. Однако числа в интервале СО. РЗ отображают отрицательные числа, а в интервале fPfP-lj попожительные. Это показано (для Р 6) в табл. 1. .Т а б л и ц а 1

Матрица коммутатора, реали юшегр рпе- рацию модульного умножения, представлена в табл, 2 (Р 6).

Т а б л и и а 2

, Величины О, Р и Рможно не кодировать (табл. 2), так как умножение на эти в&-.: личины дает ноль, и в этом случае, oneрация будет вьшопнена быстрее простым анализом операндов А и В. В этом случае табл. № 1 и 2 преобразуются и пр.. нймают вид (табл. № 3 и |4).

ТаблицаЗ

10

Т а б л и ц а 4

Известно, что Р (А В) АВШШ АВ+Р В табл. 6 указаны такие пары чисел для :Р 6 (Р 3).

Таблицаб

55 В данной схеме модульного умножения также используются свойства симметрии ари(метической табпицы, и при этом ; используется вышеприведенный алгоритм модульно1ч умножения. В качестве та&.лицы коммутаторов, реализующего опера вдю модульного укшожения, используем К квадрант табд 4. Чиспош 1е значения, присваиваемые схемам совпадения И, : и размещение входных шин кетлмутатора щэедставляются табл. 5. ТаблицаЗ в Продолжение табл. Количество возможных различных пар чисел определяется как S С р . о 4(Р- 2). В частном случае нашего примера 5 гС +4-16, где С т(Ул-1)-... К - 1) - число размещений из m элеме тов. Для четырех пар чисел (см. табл. 6) нет необходимости корректировать резуль тат операции, так как по значениям операндов А и в из табл. 5 определяется А-В АВ. Для остальных операндов (двадцати) Ав+ Р А-В. На чертеже представлена блок-схема устройства. Блок-схема устройства содержит пер вый и второй входные регистры 1 и 2, первый и второй дешифраторы 3 и 4, первая, вторая, третья и четвертая груп пы элементов ИЛИ 5-8, первая и вторая группы ключей 9 и 10, коммутатор 11, первая, вторая, четвертая и пятая группы элементов И 12 .- 16,второй, третий, четвертый, пя- тый и шестой элементы ИЛИ . 17 - 22 , первый и второй элементы И 23 и 24, выходной регистр 25, шифратор 26, сумматор 27 по модулю Р, вход 28 константы Р выход 29 устройства, управляющий вход 30 устройства, информационные входы 31 и 32 устройства. Коммутатор 1-1 представляет матриц ответов, состоящую из элементов И. Эл менты И, которым присвоен одинаковый результат операции, объединяются общей выходной шиной. Кь;шчество элементов И в первой группе равно количеству пар операндов, для которых (А В) А В (для Р 6 в первой группе четыре эле мента И, табл. 6). Количество элемент . И третьей группы и количество элемен- ов и в четвертой группе равно количе тву двоичных разрядов .в записи числа Р. Сумматор 27 осуществляет суммирование по модулк Р операнда выходного регистра 25 и значения Р представленных двоичным кодом. Устройство работает следующим обра зом. По входным щинам 31 и 32 операнды в двоичном коде поступают на входные регистры 1 и 2, с которых операнды чисел поступают на свои дешифраторы 3 и 4. Операнл.ъ1 с выходов дешифраторов 3 в унитарном коде, поступают на соответствующие элементы 5 первой и 6 второй группы ИЛИ и на соответствующие элементы ИЛИ 17 - 20. Сигнал шины ЗО открывает-ключи 9 и. 10 и операнды одновременно поступают на соответствующие входы коммутатора 11. Если Уд 3, то элементы И 23 и. 24 закрыты и выходной сигнал с пятого элемента ИЛИ 21 отсутствует. Элементы И13 второй группы, а 12 первой группы открыты. Выходной сигнал результата операции с выхода коммутатора 11 через элемент И 12 первой группы че. рез элемент ИЛИ 7 третьей группы поо тупает на соответствующий вход регист ра 25. Еслид- itgp, то выходной сигнал KOMMji-TaTopa через от1фытый элемент И 13 второй группы,элемент ИЛИ 7 третьей группы поступает на соответствующий вход регистра 25. С выхода шифратора 26 операнд в двоичном коде поступает на вторые входы элементов И 15 четвертой группы и на вторые входы сумматора 27. Если для данных Аи В (А В) А -В, то на выходе шестого элемента ИЛИ 22 присутствует сигнаЛо Этот сигнал закрывает элементы И 16 пятой группы и открывает элементы И 15 четвертой группы. Операнд с выхода шифратора 26 через открытые элементы И 15 четвертой группы, через четвертую группу элементов ИЛИ 8 поступает на выход 29 устройства. Если для данной пары операндов (А В) Ав+ Р то сигнал с шестого элемента ИЛИ 22 отсутствует. Операнд с выхода шифратора: 26 поступает на один .из входов сумматора 27, на другой вход которого через открытые элементы И 16 пятой группы по шине 28 поступает значение Рв двоичном коде. С выхода сумматора 27 операнд (АВ+ Р )тоЗР в двоичном коде, через четвертую группу элементов ИЛИ 8 поступает на выход 29 устройства. Таким образом, введение в состав устройства двух элементов И, двух груп элементов И, шифратора, шестого элеме№ та ИЛИ, группы элементов ИЛИ, сумматора по модулю Р, двух групп вентилей и соответствующих связей расширяет функхщональные возможности устройства, т.е. позволяет выполнить умножение по модулю в положительном и отрицательном числовом диапазоне. Формула изобретения Устройство для умножения чисел по модулю, содержащее первый, и второй, входные регистры, первый и второй ившифраторы, группу элементов И, первую вторую и третью группы элементов ИЛИ первую и вторую группу ключей, коммутатор, пять элементов ИЛИ, первый и второй элементы И, выходной регистр, причем входы первого и второго входных регистров являются информационными входамн устройства, а выходы подкпю- чены ко входам соответственно первого и второго дешифраторов, выходы первой и второй групп первого и второго дешиф раторов подключены соответственно к первым и вторым входам элементов ИЛИ первой и второй групп и ко входам соот% ветственно первого, второго, третьего и четвертого элементов ИЛИ, выходы элементов ИЛИ первой и второй групп подключены к первым входам соответствующих ключей соответственно первой и второй групп, вторые входы которых объединены и являются управл5пошим входам устройства, а выходы подключины соответственно к первой и второй группам входов коммутатора, выходы элементов ИЛИ третьей группы подключены к соответствуюшим входам выходного регистра, отличающееся тем, что, с целью расширения функцио- нальных возможностей путем перемножу ния как положительных так и отрицатель ных чисел, устройство содержит два эле мента И, четыре группы элементов И, шифратор, шестой элемент ИЛИ, четвертую группу элементов ИЛИ, сумматор по модулю Р (Р -модуль, по которому ра- 9010 ботает устройство), первые входы элементов И первой группы объединены с первыми входами соответствующих элементов И второй группы и подключены к соответствуюшим выходам группы коммутатора, выходы первого и четвертого, второго и третьего элементов ИЛИ подключ ень1 по входам соответственно первого и второго эпеметггов И, выходы которых подключены ко входам пятого элемента ИЛИ, вторые входы элементов И первой группы и элементов И второй группы объединены и подключены к выходу пятого элемента ИЛИ, а выходы подключены соответственно к первым и вторым входам соответствующих эл ментов ИЛИ третьей группы, входы 1с-го элемента И третьей группы (}(ri-j) подключены к 1 -му и J-му выходам соответственно первого и второго дешифра торов ( 1 1,2,...,Р-1; j 1,2Р-1), для которых() Aj.By, (где А и Вг «тг тлг /л . Q .1 ; Л . L3I тчп f Л гг d исходиые числа, ()- искусственная форма произведения, X -искусственная форма операнда X), выходы элементов третьей группы подключены ко входам шестого элемента ИЛИ, выход которого подключен к первым входам элементов И чет вертой и пятой групп, выходы выходного регистра подключены к соответствуюшим входам шифратора, выходы которого подключены ко вторым входам соответствующих элементов И четверт группы и к входам первой группы сумматора по мо-. дулю Р, вторая группа входов которого подключена к выходам соответствуюших элементов И П51той группы, вторые входы которых объединены и являются вхо- . дом константы Р устройства, выходы элементов И -пятой группы и сумматора по модулю Р подключены соответственно ко входам соответствуюших элементов ИЛИ четвертой группы, выходы которых явлшотся выходом устройства. Источники инфсфмашга, принятые во внимание при экспертизе 1.ABTOpcjcoe свидет1ельство СССР N 55О636,кл. G.O6 F 7/52, 1977. 2.Авторское свицетельство СССР по заявке №2675156, кл.С Об F 7/49, 18.11.78 (прототип).