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

(61) Дополнительное к авт. свив-ву(51)М. Кд,(22) Заявлено 09.02.81 (21) 3287 Я 7/18-2 ц с присоелинением заявки Рй 3250549/18-21 С ОЬ Р 7/49 Гасударственных каюнтвт СССРОпубликовано 28,02.83. Бюллетень ЛЪ 8 по делам нзвврствннй н втврытийДата опубликования описания 28,02 .83 В, А. Краснобаев иА. В; Фцолер(54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ПО МОДУЛН 20 Изобретение относится к вычислительной технике.Известно устройство для умножения в системе остаточных классов, содержащее входные регистры, дешифраторы, ключи, коммутатор, выходной регистр, а также сумматор по модулю два, группы элементов ИЛИ, элементы И и ИЛИ и соответствующие связи 1 1 1,Недостаток устройства - большой 1 о объем оборудования.Наиболее близким к предлагаемому по техническому решению являет-. ся устройство для умножения по моду. лю, содержащее первый и второй вход ные регистры, дешифраторы, две группы элементов ИЛИ, первую группу элементов И, две группы ключей, пять элементов ИЛИ, первый и второй элементы И, выходной регистр, первый и второй входные регистры, подключены выходами к входам соответствующих дешифраторов, выходы первой и 2ъвторой групп в юрах подключены к соответствующим в%одам :,элементов ИЛИ первой и второй групп , выходы которых подключены к соответству-. ющим входам ключей соответственно первой и второй групп , первые и вторые группы выходов первого и второго дешифраторов подключены со- . ответственно к входам первого и второго , третьего и четвертого элементов ИЛИ , а также п коммутаторов (иУ 1 оц 2 Р; Р - модуль), сумматор по модулю Р, две группы элементов И, причем соответствующие входы первой4 ( группы входов коммутаторов объеди нены и подключены к выходам соот" ветствующих ключей первой группы, со. ответствующие входы второй группы входов коммутаторов объединены и подключены к выходам соответствующих ключей второй группы, выходы коммутаторов подключены к соответствующим входам первой группы вы001086 4 Зр содержит сумматор по модулю два, шесНедостаток устройства - большой объем оборудования.Цель изобретения - уменьшение объема оборудования.Поставленная цель достигается тем, что в устройство для умножения по модулю, содержащее первый и второй входные регистры, дешифраторы, первую и вторую группы элементов ИЛИ, первую и вторую группы ключей, группу коммутаторов, выходной регистр, первую , вторую и третью группы элементов И, первый, второй- третий, четвертый и пятый элементы ИЛИ, первый и второй элементы И, сумматор по модулю Р, причем первый и второй входные регистры подключены выходами к входам соответствующих дешифраторов, выходы первой и второй групп которых подключены к соответствующим входам элементов ИЛИ пер вой и второй групп, выходы которых подключены к соответствующим информационным входам ключей соответственно первой и второй групп, управляющие входы которых объединены и являются управляющим входом нумножение" устройства, первые и вторые груп пы выходов первого и второго дешифра 35 40 45 Основная идея изобретения состоит 5 О в том, цто результат операции модульного умножения представляется в коде табличного умножения, Это позволяет сократить объем оборудованияза счет уменьшения количества коммутаторов ( уменьшения колицества схемсовпадения И таблиц коммутаторов )а также за счет исключения из устройства сумматора по модулю Р, так как 3 1 ходного регистра, вторая группа вХодов которого подключена к группе выходов сумматора по модулю Р 1 первая группа входов которого подключена соответственно к выходам ключей первой группы, информационные входы которых .являются входами ко;да константы Р, а управляющие входы объединены и подключены .к выходупятого элемента ИЛИ, входы которого подключены к выходам соответственно первого и второго элементов И, первые входы которых подключены к выходам соответственно первого и второго элементов ИЛИ, а вторые входы - к выходам соответственно третьего и чет 1 вертого элементов ИЛИ, первые входы соответствующих элементов И второй и третьей групп объединены и подключены К соответствующим входам выходного регистра, вторые входы элементов И второй и третьей групп объединены и подключены к выходу пятого элемента ИЛИ, вторая группа входов сумматора по модулю Р подключена к выходам соответствующих элементов И второй группы, группа выходов элементов И третьей группы является выходом устройства 2 . торов подключены соответственно к входам первого и второго, третьего ичетвертого элементов ИЛИ, одноименныевходы первой группы входов Моммутаторов объединены и подключены к выходам соответствующих ключей первой. группы, одноименные входы второй группы входов коммутаторов объединены и .подключены к выходам соответствующих ключей второй группы, первые выходы коммутаторов подключены к соответствующим входам выходного регистра,первые входы элементов И первой,второй и третьей групп объединеныи подключены к выходу пятого элемента ИЛИ, входы которого подключены к выходам соответственно первого и второго элементов И, вторыевходы элементов И первой группы явля -ются вхсдами кода константы Р, а выходы подключены к соответствующим входам первой группы сумматора по модулю Р, вторые входы элемен -тов И второй и третьей групп попарнообъединены и подключены к соответствующим выходам выходного регистра,выходы элементов И второй группы подключены к соответствующим входам второй группы сумматора по модулю Р. той элемент ИЛИ, третью группу элементов ИЛИ, выходы которых являются выходом устройства, первые входыподключены к соответствующим выходамсумматора по модулю Р, вторые входыподключены к,выходам соответствующих элементов И третьей группы, выходы первого, второго, третьего,ичетвертого элементов ИЛИ подключенык соответствующим входам сумматорапо модулю два, единичный и нулевойвыходы которого подключены к первымвходам соответственно первого и второго элементов И, вторые входы которых объединены и .подключенык выходу шестого, элемента ИЛИ, входы которого подключены к вторым выходамсоответствующих коммутаторов группы.2 1 1+ 1+ о Таблицаб 2 3 1 + 4 15 1 1 В узлах, обозначенных знаком (+), результат операции лежит в диапазоне 16РВ предлагаемом устройстве значения результата операции, лежащих в диапаэонеР, инвертируется по модулю , т.е. в изобретении реа-, 2 ф лиэуется табл. 3.1 1 "1 1 13 4 5 евц ее еГсли в прототипе необходимо и1 л-коммутаторов, где 2 (Р 2, то дляпредлагаемого устройства необходи-мо п коммутаторов, где 2 2(для Р=11: и Ч, о=3). Таким образом, в предлагаемом изобретении, например, для Р=11, количество коммутаторов .равно и =3. Таблицы этих коммутаторов реализуют ответы по каждому иэ и разрядов результата операции модульного умножения. Выпишем такую таблицу для первого (младшего) разряда результата, отметив те квадраты, в которых результат имеет единицу по младшему разряду, и оставив пустыми квадраты с нулевыми значениями младшего разряда результата (табл. 4). Построим аналогичным образом таблицы единичных значений для второго (табл. 5) и третьего старшего разрядов результата (табл. 6). 2 3 4 5 а 1 2 3 4 5 В квадратах табл. 4-6, отмеченных знаком (+), уквзаны те значения разрядов результата операции, который инвертируется по модулю Р,Устройство работает следующим образом.В начале работы все разряды регистра 8 устанавливаются в нулевое10010состояние, Входные операнды А и В, представленные в двоичном коде, посту пают в входные регистры 1. Через соответствующие дешифраторы,2 эти операнды в унитарном коде поступают на определенные соответствующие элементы ИЛИ групп 3 и 4., Управляющий сигнал открывает ключи 5 и 6 групп. Операнды А и В одновременно поступают на соответствующие входы всех коммутаторов 7; В тех коммутаторах 7, где определены значения , разряды ре зультата для данных операндов (единица в узлах таблиц),на первых выходных шинах, подключенных к соответст З вующему разряду регистра 8, присутствует сигналЭтот сигнал переводит соответствующий разряд выходного регистра 8 в единичное состояние. Одновременно сигналы с выходов дешиФ раторов 3 поступают нз два из четырех элементов ИЛИ 12-15.Пустьф = ф. Если сигнал второй выходной шины коммутаторов 7 отсутствует, что сигнал нулевой в.ходной 2 З шины сумматора 20 не проходит через закрытый элемент И 18. Операнд регистра 8 ( результат операции) че- . рез открытье элементы И 11, элементы ИЛИ 21 поступает на выход устройства. Если сигнал второй выходной шины коммутаторов 7 присутствует, то сигнал нуле.-ой выходной шины сумматора 20 через открытый элемент И 17, элементы ИЛИ 15 открывает эле-. менты И первой и второй грыппы 9 и 10 и закрывает элемент третьей группы 11. Операнд регистра 8 через открытые элементы И 10 второй группы поступает на второй вход сумматора 19, на первый вход которого через открытые элементы И 9 первой группы поступает значение модуля Р в двоичном ко. де Инвертированный по модулю Р, результат операции регистра 8 с выхода сумматора 19,-через элементы ИЛИ 21 поступает на выход устроиства.Пустьф. Если сигнал второй выходной шины коммутаторов 7 отсутствует, то сигнал единичного выходаИ сумматора 20 через открытый элемент И 17 через пятьй элемент ИЛИ 16 открывает элементы И .первой и второй групп 9 и 10 и закрывает элемент третьей группы 11. Такимобразом, инвертированное по модулю Р значение ,результата регистра 8 с выхода сумматора 19 через элементы ИЛИ 21 поступает на выход устройства. Если 86 10сигнал второй выходной шины коммутаторов 7 присутствует, то элемент И 17 закрыт, .Значение результата опе рации с выхода регистра 8 через открытые элементы И 11, элементы ИЛИ 21. поступает на выход 18 устройства,Таким образом, введение в состав предлагаемого устройства сумматора по модулю два элемента ИЛИ, группы элементов-ИЛИ и соответствующих связей приводит к уменьшению объема оборудования коммутаторов и устройств в целом.Формула . изобретенияУстройство для умножения по моду" лю, содержащее первый и второй входные регистры, дешифраторы, первую и вторую группы элементов ИЛИ, первую и вторую группы ключей, группу комму" таторов, выходной регистр, первую , вторую и третью группы элементов И, первый, второй, третий, четвертый и пятый элементы ИЛИ, первый и второй элементы И, сумматор по модулю Р, причем первый и второй входные. регистры подключены вьходами к входам соответствующих дешифраторов, выходы первой и второй групп которых подключены к соответствующим вхо" дам элементов ИЛИ первой и второйгрупп выходы которых подключены к соответствующим информационным входам ключей соответственно первой и второй групп, управляющие входы которых объединены и являются управляющим входом "Умножение" устройства, первые и вторые группы выходов первого и второго дешифраторов подключены соответственно к входам первого и вТорого, третьего и четвертого элементов ИЛИ, одноименные входы первой группы входов коммутаторов объединены и подключены к выходам соответ- ствующих ключей первой группы, одноименные входы второй группы входов коммутаторов объединены и подключены к выходам. соответствующих ключей второй группы, -первые выходы коммутаторов подключены к соответствующим входам выходного регистра, первые входы элементов И первой, второй, третьей групп объединены и подключе" ны к выходу пятого элемента ИЛИ, входы которого подключены к выходам соответственно первого и второго элементов И, вторые входы элементов И11 1001086 12первой группы являются входами кода тьей группы выходы первого, втоконстанты Р, а йыходы подключены к рого, третьего и четвертого элеменсоответствующим входам первой группы тов ИЛИ подключены к соответствую- сумматора по модулю Р, вторые входы щим входам сумматора по модулю два, элементов И второй и третьей групп З единичный и нулевой выходы которого попарно объединены и подключены к подключены к первым входам соответсоответствующим выходам выходного ре. ственно первого и второго элементов гистра, выходы элементов И второй И, вторые входы которых объединегруппы подключены к соответствующим ны и подключены к выходу шестого входам второй группы сумматора по О элемента ИЛИ, входы которого подмодулю Р,:о т л и ч а ю щ е е с я ключены к вторым выходам соответтем, что, с целью сокращения объема ствующих коммутаторов группы.оборудования, оно содержит сумматор Источники информации,по модулю два, шестой элемент ИЛИ, принятые во внимание при экспертизе третью группу элементов ИЛИ, выходы 1% 1. Авторское свидетельство СССР которых являются. выходом устройства, по заявке У 2675156/18-24,первые входы подключены к соответ- кл, С 06 Е 7/49, 1979ствующим выходам сумматора по модулю . 2. Авторское свидетельство СССР Р, вторые входы подключены к выхо- . по заявке Ю 2916541/18-24дам соответствующих элементов И тре кл. О 06 Р 7/72, 1980 (прототип),001086. ВНИИПИ Заказ 1396/ Тираж 704 Подписное лиал ППП "Патент", . Ужгород,ул.Проектная,