Устройство для модульного умножения

ОП ИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз. Советсни кСоциалистическихРеспублик и 968808(51)М. Кл. 606 Г 7/49 с присоединением заявки М Веударатеанеб комитет ССФР дв делам наебретений н втнрмтнй(54) УСТРОЙСТВО ДЛЯ МОДУЛЬНОГО УМНОЖЕНИЯ1Изобретение относится к вычислительной технике.Э По основному авт. св,922731 иэвестно устройство для умножения в систе.ме остаточных классов, содеркащее вход ные регистры, дешифраторы, ключи, коммутатор, выходной регистр, а также сумматор по модулю два, группы элементов ИЛИ, элементы И и ИЛИ, причем первый и второй входные регистры последова-, 1 О тельно через соответствующие первый и второй дешифраторы, первую и вторую группы элементов ИЛИ, первый и второй ключи подключены соответственно к первой и второй группам входов коммутатора, 15 первые и вторые группы входов первого и . второго дешифраторов подключены соответственно к входам первого, второго и третьего, четвертого элементов ИЛИ, выходы которых подключены к соответствующим входам сумматора по модулю два, управляющие входы ключей являются входами управления устройства, первая группа входов коммутатора подключена к входам пятого элемента ИЛИ и первым входам шестого, седьмого, восьмого, девятого и десятого элементов ИЛИ, к вторым входам которых подключена втораягруппа выиодов коммутатора и вход одиннадцатого элемента ИЛИ, выход которогоподключен к первым входам первого ивторого элементов И, выход пятого элемента ИЛИ подключен к первым входамтретьего и четвертого элементов И, вторые входы первого и третьего элементовИ и второго и четвертого элементов Иподключены соответственно к нулевому иединичному выходам сумматора по модулю два, а выходы первого и четвертогоэлементов И и соответственно второгои третьего элементов И подключены ксоответствующим входам двенадцатого итринадцатого элементов ИЛИ, выходы шес.того, седьмого, восьмого, девятого, десятого, двенадцатого и тринадцатого элементов ИЛИ соединены с соответствующимивходами выходного регистра, выход которого является выходом устройства 1,Недостатком известного является ограниченные функциональные возможности,заключающиеся в том, что в выходном регистре содеркится результат операции вкоде табличного умножения, Этот операндне может непосредственно участвоватьв следующей операции в цепи вычисленийЦВМ. 1 ЕЦель изобретения - расширение функциональных возможностей устройства засчет получения результата умножения вкоде "1" из "Р",Поставленная цель достигается тем, 15что устройство для модульного умножения дополнительно содержит группу из Рэлементов И (Р - модуль, по которомуработает устройство), выходы которых являются выходами устрОйства, первые вхо Оды 1 -ых элементов И группы (1 = 1,3, , .(Р - 1)/2 - 1) объединены и подключены к первому выходу выходного регистре, первые входы-ых элементовИ группы (= 24, 7 , (Р - 1)/2) у 5объединены.и подключены к второму выходу выходного регистра (1= 1, 3Р - 1;= 2, 4, ,. Р при Р - четном;=1,3 Р, =2, 4,Р при Р - нечетном), вторые входы 1-ыхи ) -ых элементов И группы попарнообъединены и подключены к соответствушим 1 -ым выходам выходного регистра, 35Р - четном).В данном устройстве используютсясвойства симметрии арифметической таблицы относительно диагонали, вертикал.и горизонтали, проходящих между вели рчинами (Р - 12 и (Р + 1)/2, гдеР - модуль таблицы. Это определяетвозможность реализации в схеме табличного умножения только 0,25 части таблицы (для Р = 11 приведена табл, 1). 45Операция модульного умножения выполняется в коде табличного умножения, представленного в табл. 2.. Алгоритм получения результата опера ции определяется следующим соотношением: если два числа Хи у заданы по основанию Р; в коде табличного умножения= ( ,у. ) Ч.= (7 у, 1 ) то для того, чтобы получить произведение 55 этих чисел по модулю Р достаточнополучить произведение ХУ (ДОВР) в коде табличного умножения и инвертировать его индекс у в случае, если х отлично фу, где:О,ЕСли ОХ (.Р)/2,Т= ,ЕСЛИ(Р+1)И-Хср.На чертеже представлена блох-схемаустройства,Устройство содержит входные регистры 1, дешифраторы 2, группы элементовИЛИ 3, первый, второй, третий и четвертый элементы ИЛИ 4 сумматор 5 по модулю два, ключи 6, коммутатор 7, шестой, седьмой, восьмой. девятый и десятый элемент ИЛИ 8, выходной регистр9, пятый и одиннадцатый элементы ИЛИ10, первый. второй, третий и четвертыйэлементы И 11, .двенадцатый и тринадцатый элементы ИЛИ 12, группу элементов И 13.Устройство работает следующим образом.Входы устройстве по кодовым цепямС исвязываются входными регистрами 1 с цифровой вычислительной машиной.С входных регистров 1 операнды чиселпоступают на свои дешифраторы 2. Дешифраторы служат для преобразования операндов машинного представления в унитарныйкод. Сигнал с выхода дешифратора 2 строк(столбцов) одновременно поступает на двухвходовые 3 и пятивходовые 4 элементы.ИДИ. Сигнел с выхода двухвходового элемента ИЛИ поступает на один из ключей6 строк (столбцов). Управляющий сигналот устройства управления одновременно поступает на ключи 6 (строк и столбцов), свыхода которых сигналы поступают не коммутатор 7 (матрицу ответов),Сигнал с выхода пятивходового элемента ИЛИ 4 поступает на единичный или нулевой входы сумматора по модулю два 5.С единичного или нулевого выхода сумматора 5 (в зависимости от результата модульного сложения) сигнал поступает на два элементе И 11.В зависимости от результата модульного умножения на один из вторых входов элементов И 11 поступает сигнал с выхода матрицы ответов через один из двух элементов ИЛИ 10. Выбор одного из двух элементов ИЛИ зависит от того, к какой группе (0-5 иди 6-10) относится результат модульного умножения, Сигнал с выхода элемента И 11 поступает на вход элемента ИЛИ 12, выход которого соединяется с входом выходного регистра 9. Этот сигнал представляет код индекса (."0" или 1 ). Одновременно код2 5 8 10 3 7 5. . 5 10 4 9 3 8 2 7 1 6 6 6 1 7 2 8 3 9 4 10 5 3 10 6 2 7 7 1 8 4 8 8 .5 2 10 7 4 1 9 6 3 7, 5 3 1 10 8 6 4 2 9 9 10 10 9 8 7 6 5 4 3 2 1 Таблица 2 2 4 7 3 0 5 968808 Ьрезультата модульного умножения посту- ичный код, пригодный для дальнейшей пает через элементы ИЛИ 8 на вход вы- обработки.ходного регистра 9, с выхода кото- Таким образом введение в состав устрого поступает на входы соответст- ройства группы элементов И позволяет вуюших элементов И группы . 13, гдерасширить функциональные возможности происхоцит преобразование унитарного устройства за счет получения результата кода результата с индексом в дво- в двоичном коде.7 ММ 08 81ф о р м у л а и з о б р е т е н и и ны и подключены ко второму выходу выходного регистра (1" = 1, 3, , Р;1Устройство для модульного умножения 1 = 2, 4, Р при Р - четном;= 1, поавт. св. %922731 отличаю 3, ., Р 3 -.2, 4, , Рпри Р-не" .ш е е с я тем, что, с целью расширения ф четном), вторые входы 4-ых и-ыхфункциональных возможностей за счет элементов И группы попарно объединены получения результата умножения в коде и подключены к соответствующим -,ым , 1 и Р, оно дополнительно содержит груп- выходам выходного регистра ( 1 = 3, 4, пу из Р элементов И (Р - модуль по ко- , , (Р)/2+2, при Р - нечетном; торому работает устройство), выходы ко- , с щ 3, 4, ., Р/2+2 при Р четном).,1 Р ьторых являются выходами устройства, Источники информации первые входы 4 -ых элементов И груп принятые во внимание при экспертизе пы объединены и подключены к первому, 1, Авторское свидетельство СССР по выходу выходного регистра, первые вхо- заявке Ж 2675156/18-24, ды-ых элементов И группы обьедине. кл, 606 Р 7/39, 1978 (прототип).