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

(54) УСТРОЙСТВО ДЛЯ МОДУЛЬНОГО 1 Изобретение относится к вычислительной технике. I По основному авт. св. № 922731 известно устройство для умножения в системе остаточных классов, содержащее входные регистры, дешифраторы, ключи, коммутатор, выходной регистр, а также сумматор по модулю два, группы элементов ИЛИ, элементы И и ИЛИ, причем первый и второй входные регистры последовательно через соответствующие первый и второй дешифраторы, первую и вторую гру пь1 элементов ИЛИ, первый и второй ключи подключены соответственно к первой и второй группам входов коммутатора, первые и вторые группы входов первого и второго дешифраторов подключены соответственно к входам первого, второго и третьего, четверюго элементов ИЛИ, выходы которых подключены к соответствующим входам сумматора по модулю два, управляющие входы ключей являются входами управления устройства, первая групУМНОЖЕНИЯпа входов коммутатора подключена к входам пятого элемента ИЛИ и первым входам шестого, седьмого, восьмого, девятого и десятого элементов ИЛИ, к вторым входам которых подключена вторая группа выходов коммутатора и вход оди/ннадцатого элемента ИЛИ, выход которого подключен к первым входам первого и еторого элементов И, выход пятого элемента ИЛИ подключен к первым входам третьего и четвертого элементов И, вто- , рые входы первого и третьего элементов И и второго и четвертого элементов И подключены соответственно к нулевому и единичному выходам сумматора по модулю два, а выходы первого и четвертого элементов И и соответственно второго и третьего элементов И подключены к соответствующим входам двенадцатого и тринадцатого элементов ИЛИ, выходы шестого, седьмого, восьмого, девятого, десятогО( двенадцатого и тринадцатого элементов ИЛИ соединены с соответствующими входами выходного регистре, выход кото рого является выходом устройства Ц. Недостатком известного является огр ниченные функциональные возможности, заключающиеся в том, что в выходном р гистре содержится результат операции в коде табличного умножения, Этот операн не может непосредственно участвовать в следующей операции в цепи вычислений ЦВМ. Цель изобретения - расширение функциональных возможностей устройства за счет получения результата умножения в коде из Р. Поставленная цель достигается тем, что устройство для модульного умножения дополнительно содержит группу из Р элементов И (Р - модуль, по которому работает устройство), выходы которых я ляются выходами устройства, первые BXO ды i -ых элементов И группы (i 1, 3, ..,, (Р - 1)/2 - 1) объединены и под ключены к первому выходу выходного ре гистра, первые входы j -ых элементов И группы ( j ±„ 4, 7 ... , (Р - 1)/2) объединены и подключены к второму выходу выходного регистра ( i 1, 3, ..., Р - 1; j 2, 4 Р при Р - четном; -i 1, 3 Р, J 2, 4, ..., Р 7 1 при Р - нечетном), вторью входы 1-ых и j -ых элементов И группы попарно объединены и подключены к соответствущим -ым выходам выходного регистра { е 3, 4 (Р - 1)/2 + 2, при Р нечетном} Р 3, 4, ..., Р/2 + 2 при Р „ четном). В данном устройстве используются свойства симметрии арифметической таблицы относительно диагонали, вертикал, и горизонтали, проходящих между величинами (Р - и (Р + 1)/2, где .Р- - модуль таблицы. Это определяет возможность реализации в схеме табличного умножения только 0,25 части таблицы (для Р 11 приведена табл. 1). Операция модульного умножения выполняется в коде табличного умножения, представленного в табл. 2. Алгоритм получения результата операции определяется следующим соотношением: если два числа .у и у заданы по основанию Pi в коде табличного умножения у ( Тх . Xi ( Tv), ), то для того, чтобы получить произведение этих чисел по модулю 1 достаточно получить произведение (wiOdP) в коде табличного умножения и инвертировать его индекс fy в случае, если -ух отлично от-у , где: (о,если о$х ср-1)/2, ri. Тг 1-1. если (р-и). На чертеже представлена блок-схема устройства. Устройство содержит входные регистры 1, дешифраторы 2, группы элементов ИЛИ 3, первый, второй, третий и четвертый элементы ИЛИ 4, сумматор 5 по модулю два, ключи 6, коммутатор 7, щес- той, седьмой, восьмой, девятый и десятый элемент ИЛИ 8, выходной регистр 9, пятый и одиннадцатый элементы ИЛИ 10, первый, второй, третий и четвертый элементы И 11, двенадцатый и тринадцатый элементы ИЛИ 12, группу элементов И 13. Устройство работает следующим образом. ., Входы устройства по кодовым цепям )t и 9 связываются входными регистрами 1 с цифровой вычислительной машиной. С входных регистров 1 операнды чисел поступают на свои дешифраторы 2. Дешифраторы служат для преобразования операндов машинного представления в унитарный код. Сигнал с выхода дешифратора 2 строк столбцов) одновременно поступает на двухвходовые 3 и пятивходовые 4 элементы. ИЛИ. Сигнал с выхода двухвходового элемента ИЛИ поступает на один из ключей 6 строк (столбцов). Управляющий сигнал от устройства управления одновременно поступает на ключи 6 (строк и столбцов), с выхода которых сигналы поступают на коммутатор 7 (матрицу ответов). Сигнал с выхода пятивходового элемента ИЛИ 4 поступает на единичный или нулевой входы сумматора по модулю два 5. С единичного или нулевого выхода сумматора 5 (в зависимости от результата модульного сложения) сигнал поступает на два элемента И 11. В зависимости от результата модульного умножения на один из вторых входов элементов И 11 поступает сигнал с выхода матрицы ответов через один из двух элементов ИЛИ 10. Выбор одного из двух элементов ИЛИ зависит от того, к какой группе (0-5 или 6-1О) относится результат модульного умножения. Сигнал с выхода элемента И 11 поступает на вход элемента ИЛИ 12, выход которого соединяется с входом выходного регистра 9. Этот сигнал представляет код индекса ( или ), Одновременно код

5 Se88086

результата модульного умножения посту-ичный код, пригодный для дальнейшей

пает через элементы ИЛИ 8 на вход вы-обработки.

ходного регистра 9, с выхода кото-Таким образом введение в состав устрого поступает на вкоды соответст-ройства группы элементов И позволяет

вуюших элементов И группы 13, где5 расширить функциональные возможности

происходит преобразование унитарногоустройства за счет получения результата

кода результата с индексом в дво-в двоичном коде.

Таблица 1

Цифра

Код табличного умножения Формула вэобретеняя Устройство для модульного умножения по авт. св. № 922731 отличаюш в ее я тем, что, с целью расширения (жальных возможностей за счет получения результатаумножения в копе 1 и Р , оно дополнительно содержит гру пу из Р элементов И (Р - модуль по которому работает устройство), выходы которых являются выходами устрс ства, первые входы { 4ах. элементов И груп i пы объединены и подключены к первому . выходу выходного регистра, первые входы i -ых элементов И группы обьедине« ны и подключены ко второму выходу выходного регистра (i 1, 3, ..., Р- 1; Ч 2, 4, ..., Р при Р - четном; , 3, ,.., Р} 2, 4, ..., Р-1 при Р - нечетном) вторые входы Л-ыл и -ых элементов И группы попарно объединены и подключены к соответствующим тым выходам вЪ1ходного регистра { ( 3, 4, ..., (Р-1)/2 + 2, при Р - нечетном; 3, 4, ..., Р/2 + 2 Р - четном). Источники информации принятые во .внимание про. экспертизе 1, Авторское свидетельство по заявке № 2675156/18-24, кл. G06 F 7/39, 1978 (прототип).