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

ОП ИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(22) Заявлено 17. 02.81 (21 3250548/18-24 Сфвз СфветскняСоциалистическихРеспублик цд 81991 ИЦМ.К т.з с присоединением заявки Йо С 06 Р 7/49 Государственный комитет СССР по делам изобретений и открытийДата опубликования описания 15.12,82(71) Заявител МНОЖЕНИЯ ПО МОДУЛ 4) УСТРОЙСТВОИзобретение относится к вычислительной технике.По основному авт.св. Р 896620 известно устройство для умножения по модулю, содержащее первый и: второй входные регистры, дешифраторы, две группы элементов ИЛИ, первую группу элементов И, две группы ключей,первый, второй, третий, четвертый, пятый элементы ИЛЙ, первый и второй элементы И, выходной регистр, первый и второй входные регистры подключены выходами ко входам. соответствующих дешифраторов, выходы первой:и второй групп которых подключены к.соответствующим входам элементов ИЛИ первой и второй групп, выходы которых подключены к соответствующимвходам ключей соответственно первой и второй. групп, первые н вторые группы выходов первого и второго дешиФраторов подключены соответственно ко входам первого и второго, третьего и четвертого элементов ИЛИ, а также содержит и коммутаторов (и1 од Р, Р - модуль) сумматор по модулю Р, две группы элементов И, причем соответствующие входы первой группы вхо дов коммутаторов объединены и подключены к выходам соответствукщих ключей первой группы, соответствующие входы второй группы входов коммутаторов объединены и. подключены к ,выходам соответствующих ключей второй группы, выходы коммутаторов подключены к соответствующим входам первой группы выходного регистра, ,вторая группа входов которого подключена к группе выходов сумматора по модулю Р, первая группа входов которого подключена соответственно к выходам ключей первой группы, ин" Формационные входы, которых являются входами кода константы Р, а управляющие входы объединены и подключены к выходу пятого элемента ИЛИ, входЫ которого подключены к выходам соответственно первого и второго элементов И, первые входы которых подключены к выходам соответственно первого и второго элементов ИЛИ, а вторые входы - к выходам соответственно третьего и четвертого элементов ИЛИ, первые входы соответствующих элемен тов И второй и третьей групп объединены и подключены к соответствующим выходам исходного регистра, вторые входы элементов И второй и третьей групп объединены и подключены к выхо-.30 дупятого элемента ИЛИ, вторая груп 981991па входов сумматора по модулю Р подключена к выходам соответствующих элементов И второй группы, группы выходов элементов И третьей группы является выходом устройства. В этом устройстве используются свойства сим метрии арифметической таблицы. Ири этом реализацияоперации модульного умножения осуществляется посредством и коммутаторов, реализующих ответы по каждому из и разрядов результа та 1 .Недостатком прототипа является низкое быстродействие, что обусловлено необходимостью записи в выходной регистр и считывания результата операций сумматора по модулю Р.Цель изобретения - повышение быстродействия.поставленная цель достигается тем, что устройство для умножения по модулю содержит третью группу элементов ИЛИ, причем выходы сумматора по модулю Р подключены к первым входам соответствующих элементов ИЛИ третьей группы, выходы которых являются выходами уст 25 роства, выходы элементов И третьей группы подключены ко вторым входам соответствующих элементов ИЛИ третьей группы.Как принято, в схеме модульного умножения используются свойства симметрии арифметической таблицы относительно левой и правой диагоналей, вертикали и горизонтали, проходящих между числами Р/Х и Р+1(2 , где Р модуль таблицы. Это и определяет воз-З 5 можность реализации в схеме табличного умножения только 0,25 части таблицы коммутатора, Операция модульного умножения выполняется в коде таблийного умножения. 40Алгоритм получения результата операции модульного умножения определяется так: если два числа А и В заданы по основанию Р в коде табличного умножения А =Уо,а), В = (фр,б) 145 то для того, чтобы получить произведение этих чисел по модулю достаточно получить произведение О й (аоЙР) в коде табличного умножения и инвертировать его индексв слу чае, если с отлично отр, где0, еслиМ Р+11, если - - с аР 5если оресли60В прототипе в качестве коммутатора, определяющего результат операции модульного умножения, используется не единая таблица, а и более мелких таблиц, реализующих ответы по каждому 65 из и разрядов коммутатора, где иколичество двоичных разрядов в записи операндов А и В, т.е. и1 одР.Результат операции представляетсядвоичным кодом.Основная идея изобретения состоитв том, что быстродействие выполнения операции умножения повышаетсяпутем исключения операции записи ввыходной-регистр и считывания результата операции сумматора по модулю Р.На чертеже представлена блок-схемаустройства.На схеме обозначено первый и второй входные регистры 1,дешифраторы 2,первая и вторая группы элементов ИЛИ3 и 4, первая и вторая группа ключей5 и 6, группа коммутаторов 7, выходной регистр 8, первая, вторая итретья группы элементов И 9-11, первый, второй, третий, четвертый и пятый элемены ИЛИ 12-16, первый и второй элементы И, 17 и 18, сумматор пОмодулю Р 19, третья группа элементовИЛИ 20.Двоичные и-разрядные регистры 1и 8 служат для Фиксации соответственно значений операндов и результатаоперации модульного умножения. Коммутаторы 7 представляют таблицы, реализующие ответы по каждому из и разрядов результата операции. Конструктивно коммутаторы 7 представляют наборсхем И, Количество элементов И в К-омкоммутаторе равно количеству единицК-го разряда результата операции модульного умножения. Эти элементы Иобъединяются общей выхоцной шиной,подключенной к К-у разряду регистра 8,Устройство работает следующим образом.Случай, когда с =. Входные операнды А и В,представленные в двоичном коде, поступают в входные регистры 1. Через соответствующие дешифраторы 2 эти операнды в унитарном коде поступают на соответствующие элементы первой и второй групп ИЛИ 3 и 4. Сигнал по управляющему входу открывает ключи групп 5 и 6, и операнды одновременно поступают на входы всех коммутаторов 7В тех коммутаторах 7, где определены значения разрядов результата для данных операндов А и В (единицы в узлах таблиц), на входной шине (выходе коммутатора), подключенной к соответствующему разрядувыходного регистра 8, появляется сигнал. Этот сигнал переводит соответствующий разряд выходного регистра 8 в единичное состояние выходной сигнал К-го коммутатора 7 переводит к единичное состояние К-й разряд регистра 8). Одновременно сигналы с выходов дешифраторов .2 поступают на два из четырех элементов ИЛИ 12-15 такиы образомчто элементы И 17 и 18 закрыты, и выходнойуправляющий сигнал элемента ИЛИ 16отсутствует так как при д = р = О,задействованы первый и третий элементы ИЛИ 12 и 14, а при с = = 1 вто 5рой к четвертый элементы ИЛИ 13 и 15).Таким образом, в выходном регистре8 содержится результат операции модульного умножения в двоичном коде.Это значение через открытые элементыИ третьей группы 11 поступают на вы ход устройства,Случай, когдаФ р. Как и в первом случае а) в регистр 8 из ковмутаторов 7 поступает операнд (результат операции) в двоичном коде. Но теперь на выходе элемента ИЛИ 16 присутствует управляющий сигнал (дляа=1,р = 0 задействованы второй ичетвертый элементы ИЛИ 13 и 15, открывающие первый элемент И 17, адля а = 0 и = 1 . задействованыпервый н четвертый элементы ИЛИ 12и 14, т.е. открыт второй элементИ 18). Выходной сигнал пятого элемента ИЛИ 16 открывает элементы Ипервой и второй групп 9 и 10 и закрывает элементы 11. Прк этом напервую группу входов сумматора помодулю Р 19, через элементы И пер- . щвой группы 9 поступает константа Рв двоичном коде, а на вторую группувходов сумматора по модулю Р 19,через элементы И второй группы 10 поступает ссщеранмое регистра 8 С выхода сумматора 19 через элементы ИЛИ третьей группы 20 на выход устройства поступает содержимое регкстра 8. Это и будет являться результатом операции модульного умножения.Таким образом, в данном изобретении исключаются операции записи в выходной регистр и считывания результата. Это повышает быстродействие операции умноаения по модулю.формула изобретенияУстройство для умножения по модулю по авт.св. 9 896620, о т л ич а ю щ е е с я тем, что, с целью повыаения быстродействия, оно содеракт третью группу. элементов ИЛИ,причем выходы суьиатора по модулю Р подключены к первым входам соответствукщкх элементрв ИЛИ третьей группы, выходы которых являются выходамн устройства, выходы элементов И третьей группы подключены к вторым входам соответствукщих элементов ИЛИ третьей группыеИсточники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССР 896620, кл. С 06 Р 7/72, 1982 (прототип).981991 ВНИИПИ Закаэ 9712/68 Тира алкал ППП "Патент", г. нгоро Подписи Проектная