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

(54) УСТРОЙСТЮ ДЛЯ УМНОЖЕНИЯ ПО МОДУЛЮ

1

( Изобретение относится к вычислительной техники.

По основному авт.св. № 896620 известно устройство для умножения по модулю, содержащее первый и:второй входные регистры, дешифрато яа, две группы элементов ИЛИ, первую группу элементов И, две группы ключей,пер- вый, второй, третий, четвертый, пятый элементы ИЛИ, первый и второй элементы И, выходной регистр, пер%1й и вто рой входные регистры подключены выходами ко входам-соо -ветствукщих дешифраторов, выходы первой ..и второй групп которых подключены к соотвехствуквдим входам элементов ИЛИ первой и второй групп, выходы которых подключены к соответствующимвходам ключей соответственно первой и второй групп,первые и вторые группы выходов первого и второго дешифраторов подключены соответственно ко входам первого и второго, третьего и четвертого элементов ИЛИ, а также содержит п коммутаторов (п logg Р, Р - модуль) сумматор по модулю Р, две групгы элементов И, причем соответствующие входы первой группы входов коммутаторов объединены и подключены к выходам соответствующих

.ключей первой группы, соответствующие входы второй группы входов коммутаторов объединены и подключены к ,выходам соответствующих ключей второй группы, выходы коммутаторов подключены к соответствующим входам первой группы выходного регистра, .вторая группа входов которого подключена к группе выходов сумматора

10 по модулю Р, первая группа входов которого подключена соответственно к выходам ключей первой группы, информационные входы, которых являются входами кода константы Р, а управ15ляющие входы объединены и подключены к ВЁ1ХОДУ пятого элемента ИЛИ, входы которого подключены к,выходам соот,ветственно первого и второго элементов И, первые входы которых под20ключены к выходам соответственно первого и второго элементов ИЛИ, а вторые входы - к выходам соответственно третьего и четвертого элементов ИЛИ, входы соответствующих- элементов И второй и третьей групп объединены и подключены к соответствующим клходам выходного регистра, вторые входы элементов и второй и третьей групп объединены и подключены к выходу пятого элемента ИЛИ, вторая группа входов сумматора по модулю Р подключена к выходам соответствующих элементов И второй группы, группы вы ходов элементов И третьей группы является выходом устройства. В этом устройстве используются свойства сим метрии арифметической таблицы. При этом реализгщияоперации модульного умножения ocs цecтвляeтcя посредством п коммутаторов, реализукадих ответы по каждому из п разрядов результата 1. Недостатком прототипа является низкое быстродействие, что обусловлено необходимостью записи в выходной регистр и считывания результата операций сумматора по модулю Р. Цель изобретения - повышение быстродействия. Поставленная цель достигается тем что устройство для умножения по модулю содержит третью группу элементов ИЛИ причем выходы сумматора по модулю Р подключены к первым входам соответст вующих элементов ИЛИ третьей группы выходы которых являются выходами уст роства, выходы элементов И третьей группы подключены ко вторым входам соответствующих элементов ИЛИ третье группы. Как принято, в схеме модульного умножения используются свойства симметрии арифметической таблицы относительно левой и правой диагоналей, вертикали и горизонтали, проходящих между числами P-ij2 и (/2 , где Р модуль таблицы. Это и определяет воз можность реализации в схеме таблично го умножения только 0,25 части табли цы коммутатора. Операция модульного умножения выполняется в коде табличного,,умножения. Алгоритм получения результата операции модульного умножения определяется так: если два числа А и В заданы по основанию Р в кодетабличного умножения А tJf(,,a),E (У(},й то для того, чтобы получить прои.зведение этих чисел по модулю достаточно получить произведение а и (modP) в коде табличного умножения и инвертировать его индекс у в слу чае, если отлично от у я , где Г О, если О а f 1, если а л Р , если УО, И Ур у , если у Ур В прототипе в качестве коммутатор определяющего результат операции модульного умножения, используется не единая таблица, а п более мелких таб лиц, реализующих ответы по каждому из п разрйдов коммутатора, где п количество двоичных разрядов в записи операндов л и В, т.е. П . , Результат операции представляется двоичным кодом. Основная идея изобретения состоит в том, что быстродействие выполнения операции умножения повышается путем исключения операции записи в выходной регистр и считывания результата операции сумматора по модулю Р. На чертеже представлена блок-схема устройства. На схеме обозначено первый и второй входные регистры 1,дешифраторы 2, первая и вторая группы элементов ИЛИ 3 и 4, первая и вторая rpynn i ключей 5 и б, группа коммутаторов 7, выходной регистр 8, первая, вторая и третья группы элементов И 9-11, первый, второй, третий, четвертый и пятый элемены ИЛИ 12-16, первый и второй элементы И, 17 и 18, сумматор пи модулю Р 19, третья группа элементов ИЛИ 20. Двоичные п-разрядные регистры 1 и 8 служат ,5ля фиксгщии соответственно значений операндов и результата операции модульного умножения. Коммутаторы 7 представляют таблицы, реализующие ответы по каждому из п разрядов результата операции. Конструктивно коммутаторы 7 представляют набор схем И. Количество элементов И в К-ом комглутаторе равно количеству единиц К-го разряда результата операции модульного умножения. Эти элементы И объединяются общей выходной шиной, подключенной к К-у разряду регистра 8. Устройство работает следующим образом. Случай, когда Уо )р . Входные операнды А и В,представленные в двоичном коде, поступают в входные регистры 1. Через соответствугацие дешифраторы 2 эти операнды в унитарном коде поступают на соответствующие элементы первой и второй групп ИЛИ 3 и 4. Сигнал по управляющему входу открывает ключи групп 5 и 6, и операнды одновременно поступают на входы всех коммутаторов 7. В тех коммутаторах 7, где определены значения разрядов результата для данных операндов А и В (единицы в узлах таблиц), на входной шине (выходе коммутатора) , подключенной к соответствующему разряду выходного регистра 8, появляется сигнал. Этот сигнал переводит соответствующий разряд выходного регистра 8 в единичное состояние (выходной сигнал К-го KOi iMyтатора 7 переводит к единичное состояние, К-й разряд регистра 8). Одновременно сигналы с выходов дешифраторов 2 поступс1ют на два из четырех элементов ИЛИ 12-15 таким образом, .что эле менты И 1 и 18 закрыты, и выходной управляющий сигнал элемента ИЛИ 16 отсутствует (так как при Уд Jfj О, задействованы первый и третий элемен ты ИЛИ 12 и 14, а при jfo ifp 1 вто рой и четвертый элементы ИЛИ 13 и 15 Таким образом, в выходном регистр 8 содержится результат операции модульного умножения в двоичном коде. Это значение через открытые элементы И третьей группы 11 поступают на выход устройства. Случай, когда jfg у а. Как и в пе вом случае (а) в регистр 8 из коммутаторов 7 поступает операнд {результат операции) в двоичн( коде Но те перь на выходе элемента ИЛИ 16 присутствует управляющий сигигш (для ,Ур О задействованы второй и четвертый элементы ИЛИ 13 и 15, открыванхдие первый элемент И 17, а для jfo О и(ь 1 . задействованы первый и четвертый элементы ИЛИ 12 и 14, т.е. открыт второй элемент И 18). Выходной сигнал пятого элемента ИЛИ 16 открывает элементы И первой и второй групп 9 и 10 и закрывает элементы 11. При этом на первую группу входов сумматора по модулю Р 19, через элементы И первой группы 9 поступает константа Р в двоичном коде, а на вторую группу входов сумматора по модулю Р 19,через элементы И второй группы 10 поступает содержимое регистра -8..С выхода сумматора 19 через элементы ИЛИ третьей группы 20 на выход устройства поступает содержимое регистра 8. Это и будет являться результатом операции модульного умнсякения. Таким образом, в данном изобретении исключаются операции записи в выходной регистр и считывания результата. Это повышает быстродействие операции умножения по модулю. Формула изобретения Устройство для умножения по модулю по авт.св. 896620, отличающееся тем, что, с целью повышения быстродействия, оно содержит третью группу элементов ИЛИ,причем выходы сукматора по модулю Р подключены к первым входам соответствующих элементрв ИЛИ третьей группы, выходы которых являются выходами устройства, выходы элементов И третьей группы подключены к вторым входам соответствующих элементов ИЛИ третьей группы. Источники информации, тфниятые во внимание при экспертизе 1. Авторское свидетельство СССР 896620, кл. G 06 F 7/72, 1982 (прототип) .

r

I

12

Uu

JJd

16

r

.--- «I III.

f

«

I