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

ИЛИ и сумматор по моду.пю два, входы которого соединены с вькодами пятого и metToro элементов 1-ШИ, входы шестого элемента ИЛИ подключены к вторым выходам узлов табличного форьжрова1126950

ния разрядов результата, вьпшд сумматора по модулю два соединен с вторыми входами элементов И первой, второй и третьей групп.

УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ПО МО,ЩЛЮ, содержащее первый и второй входные регистры, первый и второй дешифраторы, первую и вторую группы элементов ИЛИ, первую и вторую группы ключей, первьш, второй, третий, четвертый и пятый элементы ИЛИ, первую, вторую и третью группы элементов И, сумматор по модулю Р, выходной регистр, группу узлов табличного формирования разрядов результата, причем первый и второй информационные входы устройства подключены к входам соответствующих входных регистров, выходы которых подключены к входам соответствующих дешифраторов, выходы первой и второй групп которых подключены к соответствуюmiiM входам элементов ИЛИ первой и второй групп соответственно, выхоЛД:, которых подключены соответственно к информационным входам ключей первой и второй групп, управляющие входы которых соединены с тактовым входом устройства, выходы первой и второй групп первого дешифратора подключены к входам первого и второго элементрв ИЛИ соответственно, выходы первой и второй групп второго дешифратора подключены к входам третьего и четвертого элементов 1ШИ соответственно, выходы первого и третьего элементов ИЛИ соединены с входами первого элемента И, выходы второго и четвертого элементов ИЛИ подключены к входам второго элемента И, выходы первого и второго элементов И соединены с входами пятого элемента 1-ШИ, входы первой группы узлов табличного формирования разрядов результата соединены с выходами ключей первой группы, входы i второй группы узлов табличного формирования разрядов результата соединены с выходами ключей второй группы, первые выходы узлов табличного формирования разрядов результата соединены с первькми входами соответствующих разрядов выходного регист я.л ра, первые входы элементов И первой группы соединены с входами задания г модуля устройства, а выходы элемена тов И первой группы соединены с первой группой входов сумматора по модулю Р, вторая группа входов которого соединена с выходами элементов И второй группы,первые входы которых соответственно соединены с выходами разрядов выходного регистра и первыми входами элементов И третьей группы, выходы которых соединены с выходами устройства, выходы cyNiMaToра по модулю Р подключены к вторым входам разрядов вькодного регистра, о. тли чающееся тем, что, с целью уменьшения оборудования, устройство содержит тестой элемент

Изобретение откосится к вычислительной технике и может быть использовано в системах и устройствах, фукционирующих в системе остаточных классов.

Известно устройство для множения по модулю., содержащее первый к второй входные регистры, первый и второй дешифраторы, коммутатор, ключи, сумматор по модулю дна5, элементы И и ИЛИ

Недостаток устройства - большое количество оборудования.

Известно также устройство для умножения по модулю,, содержащее входные и выходной регистры, два дешифртора, группы элементов ИЛИ, ключи, элементы И и ШШ, коммутатор сумматор по модулю Р 2j,

Недостаток устройства - большое кол1-1чество оборудования.

Наиболее близким к предлагаемому является устройс;во для умгюжения по модулю., содержащее подключеннрле информационным входам устройства первьй и второй входные регистры, первый и второй дешифраторы; первую и вторую группы элементов ИЛИ, первую и вторую группы ключевых элементов j группу узлов табличного формуфвания разрядов результата, выходной регистр, элементы И и ИЛИ, с /мматор по модулю Р (где Р - модуль, пс которому работает устройство), пзрвую вторую и третью группы элеме АТОв И

с СООТЕЕТСТВУЮГДНМИ СВЯЗЯ гН 33„

Недостаток устройства - большое количество оборудовамия„

Этот недостаток обусловлен тем, что при построении коммутаторов не учитывается цифровая структура таблицы модульного умножения,,

Цель изобретения - ут шньшение количесГна оборудования«

Поставленная цель достигается тем, что в устройство для умггожения

ло МОДУЛЮ; содержащее первьй и второй входные регистгьц первый и второй Д1;ешифраторы, первую и вторую группы элементов I-UIW,, первую и вто5 рую группы ключей5 первый, второй, третий, четвертый а пятый элеметгты -ШИ,, первую, и третью злемептов И, сумматор по модулю Р, выход1юй регистрJ группу узлов табO личного форкирования разрядов результата j причем первый к второй информационные входы устройства подключены к входам соответствуюгцих входных регистров, зыходь; которых под5 клгочеггы к вхо,цам соотнетстврогдих де-шифраторов, вькоды первой и зтоРОГ групп которых Г ОДКЛЮЧег Ы к СООТветстзукч.гим входам, элементен ИПИ первой и второй групп соответственно,

0 выходы которь х подключены соответственно к инфоркационнкП-1 входам ключей первой и второй групП; управляющие входы которых соединены с тактовь м входом устройства, выходы первой

5 и второй групп первого дешифратора подключень: к входам первого и второго элементов ШТЛ соответственно, выходы первой и второй групп второго дешифратора подк.гпочены к входам 0 третьего и четвертого элементов ИЛИ соответстве/пш,, вьжоды первого и третьего элвмектои ЯчИ соединеигл с входами первого элемента И, выходе. второго и четвертого элементов

ИЛИ подк.11ючены к входам второго элемента И, ;зькодь; и второго э.пементюв И соедияелгы с входами пятого элемента ШШ, ггхо.цы первой группы .узлов табличного формироиакия разряхюв осзультат.и соеднкены с гзыходам.и j

ключей первой группы, вхо.цы второй группы узлов табличного формирован1-;я разр.чдов результата оедип.укьг с выходами к.пючей второй групгты, аер, вые цылоды узлов таб.чичного (;.ормиро« тзапия разр.ядов ретультпта сог;и-1неньг с первыми входами соответствующих разрядов выходного регистра, первые входы элементов И первой группы соединёиы с входами задания модуля устройства, а выходы элементов И первой группы соединены с первой группой входов сумматора по модулю Р, вторая группа входов которого соедршена с выходами элементов И второй группы первые входы которых соответственно соединены с выходами разрядов выходного регистра и первыми входами элементов И третьей группы, выходы которых соединены с выходами устройстза, выходы сумматора по мoдvлю Р подключены к вторым входам разрядов выходного регистра, содержит шестой элемент ИЛИ и cyiviMaTop по модулю .два, входы которого соединены с выхо дами пятого и шестого элементов ИЛИ, входы шестого элемента ИЛИ подключены к вторым выходам узлов табличного формирования разрядов результата, вы ход сумматора по модулю два соединен с вторыми входами элементов И первой второй и третьей групп. Сущность изобретения заключается в том, что узлам табличного формирования разрядов результата присвоены значения модульного умножения ot.; /bj(,mo или P-oLj|j. mod Р) , для которых количество единиц в записи двоичного числа Pi (mod Р) или Р-Ы,-fi IwodPj мии№1ально. Это позволяет Существенно уменьшить количество оборудо. вания устройства для умножения по модулю засчет сокращения количества элементов И коммутаторов. На чертеже представлена структурная схема устройс ва для умножения по модулю. Устройство содержит входы 1 и 2, входные регистры 3 и А, дешифраторы 5 и 5.) группы элементов ИЛИ 7 и 8, группы ключей 9 и 10, группу узлов 11 табличного формирования разрядов результата, выходной регистр 12, так товый вход 13, элементы ИЛИ 14 и 15 элементы И 16 и 17, элементы ИЛИ 18 20, сумматор 21 по модулю два, элемент. ИЛИ 22J группы элементов И 23 - 25, входы 26 задания модуля, сумматор 27 по модулю Р, выходы 28. Информационные входы 1 и 2 подключены соответственно к входам входных регистров 3 и 4, выходы которых через соответствующие дешифраторы 5 и 6, группы элементов ИЛ 7 и 8, группы ктаочей 9 и 10 последовательно подключепь к первой и второй группам входов соответству ощих узлов 11 (выходнБ е шины дешифраторов 5 и 6 объединены парами таким образом, что суъо- а значений, присвоенная каждой паре, равна модулю Р) , вьосоды которых подключены к соответству1ощи1.{ входам выходно1о регистра 12. К управляющим входам групп к.шочей 9 и 10 подключен вход 13. Первая ( ) и вторая () группы выходов, дешифратора 5 подключены к входам соответственно элементов ШШ 14 и 15, выходы которых подключены к первым входам соответственно элементов И 16 и17. Первая (1 - -&|-L)-n вторая ( Р 1 ) группы выходов дешифратора 6 подклга-1 е 1Ы к входам соответственно злемеитов ИЛИ 18 и 19, выходы которь-х подключ;ены к вторым входам соответственно элементов И 17 и 16, Выходы элементов И 16 и 17 подключены к входам элемента ИЛИ 20, выход которого подключен к входу сумм.атора 21 по модулю два, к другому входу которого подключен выход элемента ИЛИ 22, к входам которого подключены выходы узлов 1, Выход с т-1матора 2 S пс.дключен к входам элементов И 23 - 25. К друп-м входам элемента И 23 подклдочены входы 26. К друг51м входам элементов И 24 и 25 подключены вькоды регистра 12. Выходы элементов И 23 и 24 подключены соответствешю к входам сумматора 27 по моду.п}о Р, выхо.ды которого подключены к входам рспЕстра 12. Выходы элемента И 25 являются выходами 28 устройстаа. Узлы 11 предстявлупот таблицы, реализ пощие ответы по каждому из (р-1)-И двоичных разрядов результата операции. Конструкти1 но Ззлы 1 1 представляют набор -элементон И. Количество элеме1 тоБ И D k-ом узле 11 равно количеству единиц разряда результата операции Р-с(..|-р. (modPl или (i;fi.j(irioci .Р. Эти элементы И объединяются общей имходной шиной, подключенной к V-му разряду выходного регистра 12, Одновременно, другой вькод К-го узль 11 объединяет элементы И, для которых присвоено значение Р- ее.; fb,-(mod Р), . выходы узлов 11 подключены к входам элемента ИГО- 22, Устройство работает следующим образом.

5 ,1126950

Входные операнда А и В, A-(./i B()) в двоичном коде поступгцот по входам 1 и 2 в сооткаГСлБующие реАЭ При : Oj (т.е. если 1 А4- „ Р - А,при -уд 1, (т.е. если - А i Р - 1) , в унитарном коде через соответствующие элементы РШ1-1 7 и 8 поступают на соответствующую пару ключей 9 и 10,.Сигнал с входа 13 открывает соответствующую пару ключей 9 и 19, и операнды d и /3 одновременно посту- - пают на вхо,цы всех f узлов 11. В тех узлах 11, где определены знача щие разряды результата для данных операндов d к /:, (единицы в узлах р таблицы) на выходе, подключенном к 20 соответствующему разряду регистра 12, появляется сигнал переводящий этот разряд регистра 12 в единичное состояние . При -j-д JQ ВЫХОДНОЙ сигнал элемента ИЛИ 20 отсутствует (нулевой сигнал на второмвходе сумматора 21) Если на выходе элемента ИЛИ 22 отсутствует сигнал, то на выходе сумматора 21 также отсутствует сигнал (О + О О inod.2) и элементы И 23 25 закрыты, В -этом случае содерж- мое (ii/ij ( mod Р ) регистра 12 является результатом операции АВ (modP), Если на выходе элемента ИЛИ 22 присутствует сигнал, то на выходе cyi4- матора 21 также присутствует сигнал (О -ь 1 1 ), который открывает элементы И 23 -- 25 В этом случае на одни входы су 1матора 27 (по lO дам 26 через элементы И 23) поступа ет значение модуля 1% а на другие входы - содержимое регистра 12 С выхода сум11ат6ра 27 значение ,р i, modP) - Л&(п101:ЗР), которое является -.З результатом операции умножения по модулю, поступает на входы регистра 12, При - у„ъъгходнок сигнал элемента ИЛИ 20 присутствует (единнчиий сигнал Su на первом входа су шатора 21), Если на выходе элемента HJEn 22 отсутс г™ вует сигнал 5 то на зьгходе cl h iaтop.i 21 также отсутствует сигнал (1 + 1 - О mocJ2 ) гд элементы И 23 55 25 закрыты а результат-операции пределяется содер/ки1-1ькм сугматора В( тос Р) « об; fij (люсг Р}.

гистры 3 и 4 и далее в дешифраторы 5 и 5, после которых операнды

,

Р - 1 вы Р уз ре цы ро та ни бо (C пр смотрим пример конкретного ения операции ABdnoc Р) для „ В - этом случае количество 11 равно п 4о 3 изобретении уется 0,25 части полной таблигоос Р), т.е. котоаком -f отмечены те узлы ы, для которых количество едизаписи числа ci; р,- ( modP) , чем для числа Р - о.,,-/5;( modp) абл. 2), Табл. 3 реализуется ичестве узлов 11 равном п- 4, Таблица 1 Таблица 2 1 ( (mod. iij (mod 11| ИЛИ 14 на вход элемента И 16, С вьто да дешифратор.а 5 операнд поступает на пятый (6- 5 Р) элемент ИЛИ 8 и через элемент ИЛИ 19 на вход элемента И 16. Таким образом, элемент И 16 открыт и на вььчо.де элемента 1ШИ 20 (на входе сумматора 21) присутствует сигнал. Сигнал с входа 13 одновременно открьшает пятый ключ 9 и-ПЯТЫЙ ключ 10, и операнды ci - 5, 1 - 5 поступают на входы всех узлов 11. Первый узел 11 (табл, 4) определяет значение ноль второй узел 11 (табл, 5) определяет значение ноль; третий узел 11 (табл„ 6) определяет значение ноль| четвертый узел 11 (табл..7) определяет значение единица;, Таким o5pa30Mj в регистре 12 содержи-тся 1000, На выходе четветзтого узла 11.присутствует сигнал (в узле 5 табл. 7 единица со знаком -s--), который через элемент ИЛИ 22 поступает на второй вход сумг атора 21 „ На выходе сумматора 21 отсутствует сигнал (1 + -.0 ( 2)), и таким образоМэ, элементы И 23j 245 25 закрыты, В этом случае содержиг гог 1000 рв гистра 12 является искомым результатом рперацр5и, Проверказ 5 6 8 (тойИ). П р и м е р 2, А- 5 ();, Б 0)„ Цепь гфохождения первого операнда А 0101 описана в примере 1, Второй операнд В- 0100 с регистра 4 через дешифратор 6 и унитарном коде поступает ма чет8ер Ъ1й элемент КШ через элемент МГП 13 на вход элемента И STOM случае отеутствует сигнал на выходе элемента ЯГШ 20 (отсутствует сигнал на первом входе сумматора 21). Сигнал с входа 13 одновременко открывает пятый ключ 9 к четвертый ключ 10, и операнды ci- 5, Р - 4 поступают на входы всех узлов 11« ISepBbrii узел 11 (табл 4) определяет зиаггение ноль;, второй узел 11 (таб.1ь 5) - -аднпидй,; третий узел Г (табл, б) - аоль четвертьй узел 11 (табл. 7) - ноль. Таким образом, в регистре 12 содержится 0010. На выходе второго узла 11 присутствует сигнал (в узле Ы; 5, |5; - 4 таблицы 5 единица со знаком )5 которьй через элемент ИЛИ 22 поступает на второй вход сумматора 21. На выходе сумматора 21 присутствует сигнал (О - 1 1 (mod2)),, и таким образом, элементы И 23 - 25 открыты. В этом случае по входам 26 через, элементы И 23 на вход сумма тора 27 поступает значение модуля Р 10-11, на другой вход -сут- матора 27 с выхода регистра 12 (через элементы И 24) поступает значение 0010 С выхода сумматора 27 значение - 0010 1001 поступает в регистр 12. Этот операнд 1001 и определяет результат операции. Проверка : 5 4 ( modi 1) - 9-. В табЛв 3 в качестве примера приведены данные о количестве элементов И в узлах 1t для Р 7 и Р Таблица Выигрыш в прок а 25% центах . на Преимутцество предлагаемого -устройства, по сравненгао с прототипом, заключается в уменьшении количества оборудования при сохрйнекии всех функционйльиьж и техни-qecKnx возможностей устр.ойства, что достигается сокращением элементов И в уилах 11. j сокращается 25% (.для модуля табл, 8)). элементов И