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

ОП ИСАИ ИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСоциалистическихРеспублик(23) Приоритет С 06 Г 7/49 Государственный комитет СССР но делам изобретений и открытийОпубликовано 1509.82. Бюллетень Мо 34 Дата опубликования описания 150982 аявитель 4) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ПО МОДУ Изобретение относится к вычислительной технике.Известно устройство для умножения в системе остаточных классов, содержащее входные и выходной регистрыдешифраторы, ключи, коммутатор и логические блоки поиска квадрата и квадрантов арифметической таблицы. В устройстве исйользуются свойства симметрии арифметической таблицы модульного умножения двух операндов 13.Однако это устройство характеризу" ется сложностью построения и большим количеством логических элементов.Наиболее близким к предлагаемому является устройство для умножения в системе остаточных классов, содержащее входные регистры, дешифраторы, ключи, коммутатор, выходной регистр, а также сумматор по модулю два, группы элементов ИЛИ, элементы И и ИЛИ, причем первый и второй входные регистры последовательно через соответ ствующие первый и второй дешифраторы, первую и вторую группы элементов ИЛИ и первый и второй ключи подключены соответственно к первой и второй группам входов коммутатора, первые и вторые группы входов первого и второго дешифраторов подключены соответственно ко входам первого, второго, третьего, четвертого элементов ИЛИ, выхОды которых подключены к соответствующим входам сумматора по модулю два, управляющие входы ключей являются входами управления устройства, первая группа входов коммутатора подключена ко входам пятого элемента ИЛИ и пЕрвым входам шестого, седЬмого, восьмого, девятого и десятого элементов ИЛЙ, ко вторым входам которых подключена вторая группа выходов коммутатора и входы одиннадцатого элемента ИЛИ, выход которого подключен к первым входам первого и второ" го элементов И, выход пятого элемента ИЛИ подключен к первым входам третьего и четвертого элементов И, 20 вторые входы первого и третьего элементов И и второго и четвертого элементов И подключены соответственно к нулевому и единичному выходам сумматора по модулю два, а выходы первого 5 и четвертого элементов И и соответственно второго и третьего элементов . И подключены к соответствующим входам двенадцатого и тринадцатого элементов ИЛИ, выходы шестого, седьмого, 0 восьмого, девятого, десятого, две) 1 ( ( ( ( 1 ) ) ) У 1 2 3 4 5 б 7 8 9 10 1 2 2 4 3 б 4 8 5 10 б 7 8 9 10 1 3 5 7 10 2 7 9 5 8 2 б 10 3 7 8 2 7 1 б 3 9 4 10 5 9 5 1 8 4 10 надцатого и тринадцатого элементовИЛИ соединены с соответствующими входами выходного регистра, выход которого является выходом устройства (2.Недостатком устройства являетсяограниченные функциональные возможности. Это обусловлено тем, что в выходном регистре содержится ойеранд(результат операции модульного умножения) в коде табличного умножения,а это не позволит использовать его 9непосредственно в цепи последующихопераЦий ЦВМ,Цель изобретения - расширениефункциональных возможностей с тем,чтобы в выходном регистре результатформировался не в коде табличногоумножителя, а в двоичном коде.Поставленная цель достигаетсятем, что устройство, содержащее первый и второй входные регистры, входыкоторых являются первым и вторым информационными входами устройства,первый и второй дешифраторы, коммутатор, три группы элементов ИЛИ,пятьэлементов ИЛИ, три группы элементовИ, выходной регистр, выходы которого 25являются выходом устройства, входыпервого и второго дешифраторов подключены к выходам соответствующихрегистров, а 1 -ый и (Р-)-ый выходы (= О, 1, 2Р; Р - модуль) подключены соответственно кпервому и второму входам 3 -го элемента ИЛИ= 1, 2,(Р)/2 соответственно первой и второй групп,первые группы выходов (Х = О, 1., 352(Р)/2 соответственно первогои второго дешифраторов подключены квходам соответственно первого и второго элементов ИЛИ, вторые группы гвыходов (г: (Р+1)/2 Р-Ц соответ- щственно первого и второго дешифраторов подключены к входам соответственно третьего и четвертого элементовИЛИ, выходы элементов ИЛИ первой ивторой групп подключены к первымвходам соответствующих элементов И первой и второй групп, вторые входы которых объединены и являются управляющим входом устройства, а выходы подключены соответственно к первой и второй группам входов коммутатора, выходы элементов ИЛИ третьей группы подключены к входам соответствующих разрядов выходного регистра, содержит первый и второй элементы И, элемент НЕ, четвертую группу элементов И, первые входы-х элементов И третьей и четвертой групп (О, 1, 2Р) попарно объединены и подключены к соответствующим-м выходам коммутатора, вторые вхо" ды элементов И третьей группы объединены и подключены к выходу элемента НЕ, вторые входы элементов И четвертой группы и вход элемента НЕ объединены и подключены к выходу пятого элемента ИЛИ, первый и второй входы которого подключены к выходам соответатвенйо первого и второго элементов И, первый и второй входы которых подключены соответственно к выходам первого, второго, третьего и четвертого элементов ИЛИ, выходы-х элементов И третьей и четвертой групп подключены соответственно к первым и вторым входам -х элементов ИЛИ третьей группы.В предлагаемом устройстве используются свойства симметрии арифметической таблицы относителано диагонали, вертикали и горизонтали, проходящих между величинами где Р - модуль таблицы.Это и определяет возможность реализации в схеме табличного умножения только 0,25,Ь табл. 1 приведен пример реализации в схеме табличного умножения (Р = 11).Таблица 1ЦиФра Индекс Цифра 10 Операция модульного умножения выполняется в коде табличного умноже" ния и приведена в табл. 2. АлгЬритм получения рееультата операции определяется следующим соотношением. Если два,числа Х и 1 заданы по модулю Р в коде табличного Умножения х =(5,х.; ), У =(3 ,у;), то, для того, чтобы получить Произведение этих чисел по модулю Р, достаточно получить произведение ху(тодР) в коде табличного умножения и инвертировать его индекс у в случаеесли Ь отлично от 7, где О, если 0 ( х с(Р)/1,1, если (Р+1)/1 ( Х (Р. На чертеже представлена структурная схема устройства.Устройство содержит первый и второй входные регистры 1 и 2, первый и второй дешифраторы 3 и 4, первую, вторую, и третью группы элементов ИЛИ 5, б и 7, первый, второй, третий, четвертый и пятый элементы ИЛИ 8, 9,10, 11 и 12, первую, вторую, третьюи четвертую группы элементов И 13, 14,15 и 16, элементы НЕ 17, коммутатор18, выходной регистр 19, первый ивторой элементы И 20 и 21.Устройство работает следующим образом.Операнды в двоичном коде поступают на,входные регистры 1 и 2, с выходов которых поступают на свои дешифраторы 3 и 4, переводящие их двоичные коды в коды 1 иэ Р. Сигналы с выходов дешифраторов 3 и 4 одновременно поступают на элементы ИЛИ первойи второй групп 5 и б.и элементы ИЛИ ЗО 8, 9, 10 и 11. Сигналы с выходов элементов ИЛИ первой и второй групп 5и б через элементы И первойи второйгрупп 13 и 14 поступают на входы коммутатора 18.35 Управляющий сигнал от устройствауправления ЦВМ открывает по вторым1 входам элементы И первой и второйгрупп 13 и 14. - Если= у, тоэлементы И 20 и 21 закрыты (сигналы 49 одновременно присутствуют на выходахпервого и третьего или второго и четвертого элементов ИЛИ 8, 9, 10 и 11)и выходной сигнал пятого элементаИЛИ 12 отсутствует, элементы И груп пы 16 закрыты, а группы 15 открыты.Сигнал с выхода коммутатора 18 черезэлементы И группы 15 и элементы ИЛИгруппы 7 поступает на входы выходного регистра 19. Если4 у , то на 5 О выходе пятого элемента ИЛИ.12 присутствует сигнал (сигналы одновременноприсутствуют на выходах первого ичетвертого или второго и третьегоэлементов ИЛИ 8, 9, 10 и 11) открытодин из двух элементов И 14 или 15.Сигнал с выхода эле)ента ИЛИ 12 черезэлемент НЕ 17 открывает элементы Игруппы 15 и закрывает - 16. Сигнал свыхода коммутатора 18 через элементыИ группы 16, через элементы ИЛИ груп пы 7 поступает на вход выходного регистра 19.Таким образом, введение в устройство двух элементов И, элемента НЕ,группы элементов И и соответствующих 65 связей позволяет получить результатмодульного умножения в двоичном коде. формула изобретения5Устройство для умноженияпо модулю, содержащее первый и второй входные регистры, входы которых являются первым и вторым информационными входами устройства, первый и второй де шифраторы, коммутатор, три группы элементов ИЛИ, пять элементов ИЛИ, три группы элементов И, выходной регистр, выходы которого являются выходом устройства, входы первого и второго дешифраторов подключены к выходам соответствующих регистров, а т -й и (Р-1)-й выходы ( 1 = О, 1, 2Р; Р - модуль) подключены соответственно к первому и второму входам 1-го элемента ИЛИ 3 = О, 1, 2 (Р)/23 соответственно первой и второй групп, первые группы Ф выходов Г= О, 1, 2(Р)/21 соответственно первого и второго дешифраторов подключены к входам соответственно первого и второго элементов ИЛИ, вторые группы г выходов(Р+1)/2Рсоответственно первого и второго дешифраторов подключены к входам соответственно ЗО третьего и четвертого элементов ИЛИ, выходы элементов ИЛИ первой и второй групп подключены к первым входам соответствующих элементов И первой и второй групп, вторые входы которых 35 объединены и являются управляющим входом устройства,а выходы подключены соответственно к первой и второй.группам входов коммутатора, выходыэлементов ИЛИ третьей группы подключены к входам соответствующих разрядов выходного регистра, о т л ич а ю щ е е с я тем, что, с цельюрасширения области применения засчет получения результата умноженияв двоичном коде, оно содержит первыйи второй элементы И, элемент НЕ, четвертую группу элементов И, первые"входы 1 -х элементов И.третьей и четвертой групп ( 1 = О, 1, 2Р)попарно объединены и подключены ксоответствующим 1 -м выходам коммутатора, еторые входы элементов Итретьей группы объединены и подключены к выходу элемента НЕ, вторыевходы элементов И четвертой группыи вход элемента НЕ объединены и подключены к выходу пятого элемента ИЛИ,первый и второй входы которого подключены к выходам соответственно первого и второго элементов И, первый ивторой входы которых подключены соответственно .к выходам первого, второго, третьего и четвертого элементов.ИЛЙ, выходы 1 -х элементов И третьейи четвертой групп подключены соответственно к первым и вторым входам 1-хэлементов ИЛИ третьей группы. Источники информации,принятые во внимание при экспертизе 1. Авторское свидетельство СССР 9 550636, кл. 6 06 Г 7/52, 1977. 2. Авторское свидетельство СССР по заявке У 2675156/18-24,кл. О 06 Г 7/39, 1979,/65 . Тираж 731ВНИИПИ Государственного комитетапо делам изобретений и открыти 113035, Москва, Ж, Раушская н дписн филиал ППП "Патент", г. Ужгород, ул. Проектная,Составитель В.ЕвстигнеевРедактор Н, Киштулинец Техред.М.Коштура Корректор Г.Ога