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

СОЮЗ СОВСОЗИАЛИРЕСПУБ х Р 7/49 Р "ъ НИ ь ов ИЛИ соответств вой и второй груп а подключены к вх четвертого элеме енно,и втор э выходы педешифратотретьегосоответст одамцтов 1 Трусеи ходы первого ецн етельство ССС/72, 1980 о в ого РУ одь едиупегист ЬтЫе Зюга ной модуля уст тов И перв первой гру модулю Р,рого соеди Яй Ю Д дов кото- лемецтов ГОСУДАРСТНЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОтНРЦТИй(прототип),(4) (57) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ПОМОДУЛ 10, содержащее первый и второйвходные регистры, первый и второйдешифраторы, первую и вторую группаэлементов ИЛИ первую и вторую группы ключей, первый, второй, третий,четвертый и пятый элементы ИЛИ, первую, вторую и третью группы элементов И, сумматор по модулю Р, выходной регистр, группу узлов табличногоФормирования разрядов результата,причем первый и второй информацион"цые входы устройства подключены квходам соответствующих входныхрегистров, выходы которых подключены к входам соответствующих дешцфраторов, выходы первой и второй группкоторых подключены к соответствующим входам элементов ИЛИ первой ивторой групп соответственно, выходы которых подключены соответственнок информационным входам ключейпервой и второй групп, управляющиевходы которых соединены с тактовымвходом устройства выходы первой ивторой групп первого дешифратораподключены к входам первого и второ" ЯО 112695 О третьего элементов ИЛИ соединеныс входами первого элемента И, выхды второго и четвертого элемецтоИЛИ подключены к входам второгоэлемента И, выходы первого и втоэлементов И соединены с входамитого элемента ИЛИ, входы первойпы узлов табличногб формированияразрядов результата соединены свыходами ключей первой группы, ввторой группы узлов табличного фмирования разрядов результата соиены с выхо.,ами ключей второй грпы, первые выходь узлов табличцоформирования разрядов результатасоединены с первыми входами соответствующих разрядов выходного рра, первые входы элементов И пер группы соединены с входами задания оиства, а выходы элемей группы соединены спой входон сумматора иторая группа вхоеца с выходами э И второй группы, первые входы которыхсоответственно соединены с выходамиразрядов выходного регистра и первыми входами элементов И третьейгруппы, выходы которых соедицець свыходами устройства, выходы сумматора по модулю Р подключены к вторымвходам разрядов выходного регистра,о. т л и ч а ю щ е е с я тем что,с целью уменьшения оборудования,устройство содержит вестой элемент2695 О ИЛИ и сумматор па модупю,цва, Входыкоторого соединены с вьгходами пятогои шестого элементов ИП."4 в)соды шестого элемента ИЛИ подклкчееы к вторымвыходам узлов табличного фармираваИзобретение относится к Вычисли-тельной технике и может быть использовано в системах и устройствах, функ ционирующих в системе астаточньхклассов. 5Известно устройство для умножения по модуло, содержащее первый ивторой входные регистры, первый ивторой дешифраторы, коммутатор.ключи, сумматор па модулю два зле - т 0менты И и ИЛИ 11Недостаток устройства - большоеколичество оборуцования.Известно также устройство дляумножения па модулю садержащ-е Вход т;ные и Выходной регистры, два дешифратора, группы элементов ИЛИ., 1 Г)тзочтт,элементы И и ИЛИ, коммутатор, сумматор по модулю Р т,21.Недостаток устройства - большое 2 рколичества ОбаруДОВапиЯ,Наиболее близким к предлагаемомуявляется устройс.Ва,цля умноженияпо модулю, содержащее подключенные кинформационным входам устройства 2 .)первый и Второй входные регистрь",первый и второй дешифраторы,. первуои вторую группы элементов ИЛИ первую и вторую группь ключевых элементов, груттпу узлов табл 1 тнт)та формирования разрядов результата, вьв:Одноирегистр, элементы И и ИЛИ, сумматорпо модуля Р ,где Р - модуль, и, которому работает устрайствГз), и -рвуювторую и третью группы элементов И,с соответстэутощми связями Недостаток устройства - большоеколичества оборудова 1 ия.Этот недостаток абусловззеп Тем,чта при па троении коммутаторов неучитызается цифровая структура табзИцы модулькОГО умножения:,Цель изобретения - уменьшениеколичества оборудования.Наставленная цель достигаетсятем, чта в устройство для умноженияния разрядов резугЬтата, выходсумматора по модулю два соединен с Вторьми входами элементов И первой, Втарсй и третьейгрупп. ч.;О модуло, содержащее первый и вта;)ОЙ )хадИте;)ег 11 стГьт, пГрвый и Вгарой дешифратары, первую и вторую Группы элементов ИЛИ первую и втору:о Групгы кзвю ей, первый, второй,т)е тип че Гвер гои 1 иыт .Ззтемс-.ттт ЛЛ 1 первуо Втору)о и трете к) Гр")ппы элементов И, сумата) Ио мадугпо Р, Выходной регистр, Группу узлов табличного ар.и)оваия разрядов результата, причем первый и Второй инфор- .1.)ционные зходы устр )."ства падключепьт к входам соответствующих вход- НЫХ РЕГИСтРаВ, Вт:ХОД.1 т:ОтОРЬГХ ПОД- к)ттоеты к Входам СООтетствутотих дешифра ) 01)ав Вьгха,) о певВОЙ и 3 та тО) ГРУПП КОТОРЫХ ПОДКЛЮЧЕНЫ К Сааткетствуоктим Вхацам, эзтететтаз ИтИ первой и второй групп соответственно,Вь.ходы катар,х подключен. саатветстВе 1:ИО к информационным Входам ключейпе 4)ВГ)й и Втат)ОЙ Гругг,. упргВтяощиевходы которых соединены с тактовымВХОДОМ СОаит Ва ВЫХОД ГЕВБО 1и второй групп первого дешифратора:)ОцключееЬт к входам первсга и второго элементов ИЛ:.". сас)тветственна выходы первой и второй Гт)упп втот)ОГОдешифратара гО)ключены 11 входа:третьего и .етвертаго элементов ИЛИ саОтветстве:1 О Вьтхвдь псрВОГО итреЬега злг меттавыИ саеД 111 Сетьс в)гад "и 1 перВОГО эл опте 1 т И вьеходы второго и четьергсго элементовИЛИ падтитючееты к входам Второго эле 1 е 1 тз И, Выхадь: п. рьага и второго3 тементав т 1 соединены с Вхо:дам)1 1 тята -ГО злсмета И)РттхГ)ды геввОЙ Г)уппьузла 3 гаГ)зичнаГО фо)ит)а)" 1 тин разря1126 3с первыми входами соответствующихразрядов выходного регистра, первыевходы элементов И первой группы соединены с входами задания модуля устройства, а выходы элементов И первойгруппы соединены с первой группойвходов сумматора по модулю Р, втораягруппа входов которого соединена свыходами элементов И второй группы,Рпервые входы которых соответственносоединены с выходами разрядов выходного регистра и первыми входами элементов И третьей группы, выходы которых соединены с выходами устройства, выходы сумматора по модулю Рподключены к вторым входам разрядоввыходного регистра, содержит шестойэлемент ИЛИ и сумматор по модулюдва, входы которого соединены с выходами пятого и шестого элементов ИЛИ,20входы шестого элемента ИЛИ подключены к вторым выходам узлов табличногоФормирования разрядов результата. вьг"ход сумматора по модулю два соединенс вторыми входами элементов И первой,25второй и третьей групп.Сущность изобретения заключаетсяв том, что узлам табличного формирования разрядов результата присвоенызначения модульного умножения с(,.; ЯеодР 1или Р- о 1 мод Р), для которых количестно единиц в записи двоичногочисла о; р; вод Р 1 или Р-.о; р; еодРминимально. Это позволяет существенно уменьшить количество оборудо. вания устройства для умножения по 35модулю засчет сокращения количества элементов И коммутаторов.На чертеже представлена структурная схема устройства для умножения по модулю,40Устройство содержит входы 1 и 2,входные регистры 3 и 4, дешцфраторы5 и 6, группы элементов ИЛИ 7 и 8,группы ключей 9 и 10, группу узлов11 табличного формирования разрядов 45результата, выходной регистр 12, тактовый вход 13, элементы ИЛИ 14 и 15,элементы И 16 и 17, элементы ИЛИ 18 -20, сумматор 21 по модулю два, эле"мент. ИЛИ 22; группы элементов И 5023 - 25, входы 26 задания модуля,сумматор 27 по мОДУЛ 10 Р, выхОДы 28Информационные входы 1 и 2 подключецы соответственно к входамвходных регистров 3 и 4, выходы 55которых через соответствующие дешифраторы 5 и 6, группы элементов ИЛИ7 и 8, группы кпочей 9 и 10 после 950 4 довдтельио подключеиы к первой и второй группам входов соответствующих узлов 11 (выходные шины дешифрдторов 5 и б объединены парами таким образом, что суддма значений, присвоенная каждой паре, равна модулю Р), выходы которых подключены к соответствующим входам выходного регистра 12. К управляющим входам групп к.тодей 9 и 10Р 1 подключен вход 13, Первая (1 - в , )2 и вторая ( Р" -Р 1) группы выходов дешифратора 5 подкл 1 очены к входам соответственно элементов ИЛИ 14 ц 15, выходы которых подключены к первым входам соответственно элементов И 16 и 17. Первая (1 - в1 ) ц вторая ( -- Р - 1 ) группы выхо- "Р+1дов дешифратора 6 падключеиы к входам се ответственно элементов ИЛИ 18 и 19, выходы которых подкхгюдеиы к вторым входам соответственно элементов И 1 и 16. Выходы злемецтс П 16и 17 подключены к входам элемента ИЛИ 20, выход которого подключенк входу сумматора 21 по модулю два,к другому входу которого подключенвыход элемеитд ИЛ 1 22, к входам которого подключены выходы узлов 11.Выход сумматора 21 ди дключец квходам злемснтов 1 23 - 25. К Другимвходам элемента И 23 подключенывходы 26. К другим входам элементовИ 24 и 25 подключены выходы регистра 12. Выходы элементов И 23 и 24подключець. соответствеицо к входамсумматора 2 ло модулю Р, выходыкоторого подключены к входам рсгцстра 12, Выходы элемеитд И 25 являются выходамдд 28 ус тродд с тза .Узлы 11 предстдвддиот тдблццы, реализующие ответы по каждому цз и= ддо,Р+1 двоичных разрядов результата Операции, Коиструкти.:ио узлы 11 представляют набор элементов И. Количество злеме тог И и 1 омузле 11 равно количеству едцицц 1-горазряда результата операции Р-сд;1.,(водР 1 цли с;,(о.оо Эти элементы И объединяются общей выходной шиной, подключенной к Ъ -му разряду выходного регистра 12, Одновременно, другой выход 1-го узла 11Объединяет элементы И, для которьдхприсвоено значение Р- сд,; 1 ь(оод Р,выходы узлов 11 падключсцы к входамэлемента ИЛИ 22,Устройство работает следующимобразом.3 1126950Входные операнды А и В А= фс,.;4В - (у Д,в двоичном коде поступаютпо входам 1 и 2 в соотыетс; вующие регистрь 1 3 и 4 и далее в дешифраторы 5 и 6, после которых операнды сС;и р Р;-1 еслг 1А 2Л, прп ,у : О,(т.е. Р - А, при . = 1,Рассмотрим пример конкретного выполнения огерации АВ(11 оР) для Р г 1,. В.этом случае количество узлов 11 равно п = 4. В изобретении реализуется 025 части полной таблицы АВ(гоос 1 Р), т.е. табл. 1, в которой знаком + отмечены те узлы таблицы, для которых количество единиц в записи числа М;(Ъ;( водР больше, чем для чиспа Р-д.; р,.(гиодР) (см. табл, 2). Табл. 3 реализуется при количестье узлов 11 равном и 4 Таблица 1 3 5 5 0 . Г а 10 под 11 010 10 0 О" 6 0110 в унитарном коде через соответствующие элементы ИЛИ 7 и 8 поступаотна соответствующую пару ключей 9 и10. Сигнал с входа 13 открывает соответствующую пару ключей 9 и 10,и операнды си Д одновременно поступают на входы всех л узлов 11, Втех узлах 11, где определены значащие разряды результата для данныхоперандов с; и ф,. (единицы в узлах ртаблицы) на выходе, подключенном .соответствующему разряду регистра 2,появляется сигнал, переводящий этотразряд регистра 12 в единичное состояние.При у,1 = уВ выходной сигнал элемента ИЛИ 20 отсутствует (нулевойсигнал на втором входе сумматора 21);Если на выходе элемента ИЛИ 22 отсутствует сигнал, то на выходе сумматора 21 также отсутствует сигнал(О + 0 = 0 мод) и элементы И 2325 закрыты В этом случае содержимоес; Дпос 1 Р ) регистра 1 2 являетсярезультатом операции АВщос Р),Если на выходе элемента ИЛИ 22 при -сутствует сигнал, то на выходе сумматора 21 также присутствует сигнал(О1 = 1 мое 2 ), который от; рываеэлементы И 23 - 25, В этом случаена одни входы сумматора 27 (по входам 26 через элементы И 23) поступа"ет значение модуля Р, а на другиевходы - содержимое:регистра 12, Свыхода сумматора 27 значение Р-о1, вод Р= 46( м 0 Р), которое являетсярезультатом операции умножения помодулю поступает на входы регист"ра 12.Прн е м в 1,"ходи.сигнал элементау,;ле,ИЛИ 20 присутствует,единичный сигнална первом входе -умматора 2), слина выходе элемента ИЛИ 22 отсутсс"вует сигнал, то на выходе суматор;=21 также отсутствует сигнзл+ 1 О г 4 5 2+ первогоего) раимеет видо узлалица траблицыа 11 (длразрядат вид т 0 1 1 Табл 7 Т лица 0 3 4 5 О 0 0 2 0 0= 5 ерв 5 0 0 кода делемен Таблица вого (млад операции) лица второ лицы 5; та имеет вид вертого уз (старшего) рации) име 7Т аблица 3 узла 11 (для нер ряда результататаблицы 4 (таб имеет вид табтьего узла.11таблица четя четвертого результата опеблицы 7Таблица 6 Знаком "+" отмечены те уз менты И) таблиц узлов 11 (см 4 - 7), которые объединяются ходами, подключенными к вход,элемента ИЛИ 22. П р и м е р 1. Пусть необ определить АВ( юона 11), для(уА= О), В = 6 (в.=11). В регистр 3 записывается операнд А0101, а в регист второй операнд В : 0110, С в.шифратора 5 операнд поступае пятый элемент ИЛИ 7 и черезИЛИ 14 на вход элемента И 16, С вухо.да дешифратора 6 па эанд поступаетна пятый (6 - 5 = Р) э;.:-мент ИЛИ 8 ичерез элемент ИЛИ 19 ча вход эле-мента И 16. Таким образом, элемент И 516 открыт и на выходе элемента ИЛИ20 (на входе сумматора 21) присутствует сигнал, Сигнал с входа 13одновременно открывает пятый ключ 9и .пятый ключ 10, и операнды с(; -" 5,, = 5 поступают на входы всех узлов11. Первый узел 11 (табл, 4) определяет значение ноль, второй узел 11(табл. 7) определяет значение единица. Таким образом, в регистре 12содержится "1000", На выхоце четвертого узла 11 присутствует сигнал 20(в узле Ы; = ;.= 5 табл. 7 едипицасо знаком " 4) который черезэлемент ИЛИ 22 поступает на второйвход сумматора 21. Иа выходе сумматора 21 Отсутствует сигнал 25(14 + = 0 (боб 2 и таким Образом,элементы И 23, 24, 25 закрыты, Вэтом случае содержимое "1000" регистра 12 является искомым результатом операции. 30Проверка 56 = 8 (вжд 11),ПОимер 2.А"-5 (у =О) В 4э( " с 0)ЦЕПЬ ПРОХОжДЕНээЯ ПЕРВОэО ОПЕРацда А.= 0101 описана в примере 1.Второй операнд В = 0100 с регистра 4через дешифратор 6 в унитарном кодепоступает ца четвергый элемент ИПИ 8через элемент ИЛИ 18 ца вход элемента И 17,В этом случае отсутсчвюетсигнал на выходе элемента ИЛИ 20(Отсутствует сигнал ца первом входе сумматора 21) 05 гцал с входа 13одновременнО Открывает пятый ключ9 и четвертый ключ 10,. и операндыь,; 55 Ь:, = 4 поступают на входы всехузлов 11, Первый узел 11 (табл, 4)ОПРЕДЕЛЯЕТ ЗнаЧЕНИЕ НОЛ 5 э, Втооойузел 1 1 (тдб) э/ эдинэг" э 1 тпепч 16 сУзел 1 1 (таб и э 67ноль 5 четвеРтыи э рТ аблица 8 Количество элементов И гР 911 40 1 рототип Данное,устроис, во Выигрыш в процентах на 30% ца 257 Преимущество предлагаемого устройСТВа,ПО СРаВНЕНИЮ С ПРОТОТИПОМэ заключается в уменьшении количества оборудования прп сохранении всех фУНКЦИОНаЛЬНЫХ И ТЕХНИЧЯСК 5 ээх ВОЗМОж настей устройства, что достигается сокращением элементов И в узлах (для модуля . - 11 сок 1 эащяется 1 эЕ элементов И (см табл. 8. 950 10узел 11 (табл, 7) - ноль. Такимобразом в регистре 12 содержится"0010". На выходе второго узла 11присутствует сигнал (в узле Ы; в " 5,; = 4 таблицы 5 единица со знаком"+), который через элемент ИЛИ 22постугает на второй вход сумматора 21. На выходе сумматора 21 присутствует сигнал (О + 1 = 1 (гпод 2.и таким образом, элементы И 23 - 25Открытыв В этом случае по вхоцам26 чсрез. элементы И 23 на вход сумма,тора 27 поступает значение модуляР = 1011, на другой вход сумматора 27с выхода регистра 12 (через элементы И 24) поступает значение "0010"С выхода сумматора 27 значениеР - 0010 .- 1001 поступает в регистр 12.Зтот операнд 1001 и определяет результат операции.Проверка 5 ф 4 (щоЮ 1) = 9,В табл, 3 в качестве примера приведены данные о количестве элементов И в узлах 11 для Р = 7 и Р = 11,