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

 

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

СОЮЗ GOHETCHMX

СО!.Ц4АЛИСТИЧЕСНИХ

РЕСПУБЛИН

„„SU„„1126950

g g С 06 I 7/49

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

И АВТОРСИОММ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТНЕННЫЙ КОМИТЕТ СССР пО ЕЛА ИЗСБ =ТЕНИЙ W 0ТН ЦТИЙ (2i) 3610332/24-24 (22) 23.07,83 (46) 30,11.84. Бюл. ¹ 44 (72) В.А. Краснобаев и Л.Г. Трусей (53) 681.325(088.8) (56) 1. Авторское свидетельство СССР № 922731, кл; С 06 Г 7/49, 1981.

2. Авторское свидетельство СССР № 951296, кл. С 06 Г 7/49, 1981.

3. Ангорское свидетельство СССР № 896620, кл. С 06 Р 1980 (прототип). (4) (57) УСТРОЙСТВО ДЛЯ УМНО)КЕНИЯ ПО

ИОДЛПО, содержащее первый и второй входные регистры, первый и второй дешифраторы, первую и вторую группы элементов ИЛИ, первую и вторую группы кхпочей, первый, второй, третий, четвертый и пятый элементы ИЛИ, первую, вторую и третью группы элементов И, сумматор по модулю P выходной регистр, группу узлов табличного формирования разрядов результата, причем первый и второй информационные входы устройства подключены к входам соответствующих входных регистров, выходы которых подключены к входам соответствующих дешифраторов, выходы первой и второй групп которых подключены к соответствующим входам элементов ИЛИ первой и второй групп соответственно, выходы которых подключены соответственно к информационным входам ключей первой и второй групп, управляющие входы которых соединены с тактовым г входом устройства„ выходы первой и второй групп первого дешифратора подключены к входам первого и второго элементов ИЛИ соответственно, выходы первой и второй групп второго дешифратора подключены к входам третьего и четвертого элементов IUIH соответственно, выходы первого и третьего элементов ИЛИ соединены с входами первого элемента И, выходы второго и четвертого элементов

ИЛИ подключены к входам второго элемента И, выходы первого и второго элементов И соединены с входами пятого элемента ИЛИ, входы первой группы узлов табличногб формирования разрядов результата соединены с выходами ключей первой группы, входы второй группы узлов табличного формирования разрядов результата соединены с выхог.:Rми ключей второй группы, первые выходь| узлов табличного формирования разрядов результата соединены с первыми входами соответствующих разрядов выходного регистра, первые входы элементов И первой группы соединены с входами задания модуля устройства, а вььходы э".åìåíтов И первой группы соединены с первой группой входон сумматора по модулю Р, вторая группа входов которого соединена с выходами элементов

И второй группы, первые входы которых соответственно соединены с выходами разрядов выходного регистра и первыми входами элементов И третьей группы, выходы которых соединень! с выходами устройства, выходы сумматора по модулю Р подключены к вторым входам разрядов выходного регистра, о т л и ч а ю щ е е с я тем„ что, с целью уменьшения оборудования, устройство содержит шестой элемеит

) 2695Î

ИЛИ и сумматор по модулю д>за, входы которого соединены с вьгходами пятого и шестого элементов Ип"1„ входы шестого элемента ИЛИ подклк>че5(ы к P Topûì выходам узлов табличного формироваИзобретение относится к вычисли- тельной технике и может быть использовано в системах и устройствами-:, функ" ционирующих в системе остаточных классов. 5

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

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

Известно также устройство для умножения по 7!Одулю„содержа(цее !>ход - 1;ные и выходной регистры, два дешифратора, группы элементов ИЛИ., ключи, элементь> И и ИЛИ, коммутатор, сумматор по модулю Р L2„".

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

Наиболее близким к предлагаемому является устройс:.во,цля умножения по модулю, содержащее подключенные к информационным входам устройства 25 первый и второй входные регистрь, первый и втоРой дешифраторы,. первуц и вторую группы элементов ИЛИ„ первую и вторую группь> ключевых элементов, группу узлов таблп- Iopo формиро- -;;, вания разрядов результата, вьп:Однои регистр, элементы И и ИЛИ, суммато". по модулк> Р (где Р -. модуль, и. Которому работает усTpoéñTHO), п=-рвую,, вторую и третью гру>апы элеме:IOH И, >

С COGTHBTOTHУЮЩ>1МЯ СВЯЗ57МИ (, > „, Недостаток устройства — бо>7! 1(10е количество оборудо>зан>зя.

Этот недостаток Обусло!3>зеп Тем, что при по(троении коммутаторов не > ) учитызается цифровая структура табЛИЦЫ MO5j, >i IFH HO 1 0 УМНОЖЕНИЯ,, Цель изобретения — уменьшение количества оборудования.

Поставленная цель достигается

>:> тем, что в устройство для умножения ния разрядов резуг(ьтата, выход сумматора по модулю два соединен с вторьц>и >зходами элементов И первой, вторсй и третьей групп.,-,О модулю. содержа>цее пеовый и ВтОРОЙ ЬХОДНЫЕ РЕГПСтрь(, ППРВЫ- И BTO рой дешифраторы, -..ýpHóþ и вторую гнуrl.(7FI элементов 1ЛИ, первую и НТору:о групг(ы к(7ю >ей, первый, второй, (ре Гип > че Гвер Гь и .I и f (bIA .3>Тем(-.ьте

1>Л((,, первую, вторую и третью Гр".ппы

И, O -. I F H T 0 р 1> с> M o 57 y!7! 0 P выходной регистР, Группу узлов табличного (1>ор(.1!рова Ия разрядов результа:; —., причем первый и второй информационные >зходы устр > ">ства подклю-.:Е.(ь(К ВХОДа"I СООТНеТС-.ВУЮЦИХ ВХОДных реpè(тров, .зыход!. ..Оторь>х подКЛ.ВЧЕПЫ К ВХОДаМ 000 r>e! . ТВУЮСЦИХ ,1(ешифраторов., выходы первой и зто(>ОГ гpупп кОтОРых подкз>к>че>>ь> >(соотнет-,таус: .Им входам. элеме! тов !ГД перrr (>Ь И БТ ОРОЙ I РУ17П СООТБЕТСТВЕННО выходы которцх подключен .l соответстве>:но к и (формационным вхоцам ключей первой и второй групп,. управляющие входы которь>х соединены с тактовым входом устройства, выходы первой и второй групп первого дешифратора

:>Одклю(ень: к входам первсго и второго элементов ИЛ:.". сос>тветственно„ выходы первой и 1зторой Г(зупп вто>зоГÎ деш.>фра TopG -1(1!< (>Рчс пь> !(входа> I третьего и -(етвертого эз-.еме тов И>>И

СООтВЕТСтнв.ri(0, ВЫХЗДЫ ПЕРВОГО И третьего Fi. I ме((тoн . 1(И(с.oåäII!I(.!! i! вхоц;,,(1 первогр эз>е>5р(>тg,I вы— ходы >зторо-: о и четьер (сг", элементов

ИЛИ по„-.,ключе,II 1(входам в-.орого эле:",eI« = И, вьгхo;i!,: перь=l О и второго

:>> ементо>з 71 соединены с входам>! 17ято

Го элсмепта ИЛИ, !>ходы первой групп(ы у 3 л о 73 Г а б 5(ич ЧОГО ф О р. 1и р 0 " а 1 1 1 51 р и 3 р яg o!3 вез "> л! i,= " - 1 (r(3>rl(7 or!>i! (. >ыхопа("(и кз!ю:1 ей,>СРвой (póïïû.;<ходы то РОЙ

-.руппы (алов -.абличного, :07>»;(po!3HF

rpF>.Hрпдо1з результата .Ое,"и(!епы

>зыходами ключей второй 1 >зу(п>ы, первые H iûoräû узлов таб:1ич>(ог(> (;,.ормироВ ПИЯ РаЗРЯДОВ РЕ;->.П;Т»; rr -(i(ПИНЕНЫ

1126

3 с первыми входами соответствующих разрядов выходного регистра, первые входы элементов И первой группы сое динены с входами задания модуля устройства, а выходы элементов И первой группы соединены с первой группой входов сумматора по модулю Р, вторая группа входов которого соединена с выходами элементов И второй группы, Р первые входы которых соответственно соединены с выходами разрядов выходного регистра и первыми входами элементов И третьей группы, выходы которых соединены с выходами устройства, выходы сумматора по модулю P подключены к вторым входам разрядов выходного регистра, содержит шестой элемент ИЛИ и сумматор по модулю два, входы которого соединены с выходами пятого и шестого элементов ИЛИ, 20 входы шестого элемента ИЛИ подключены к вторым выходам узлов табличного формирования разрядов результата. вьг" ход сумматора по модулю два соединен с вторыми входами элементов И первой, 25 второй и третьей групп.

Сущность изобретения заключается в том, что узлам табличного формирования разрядов результата присвоены значения модульного умножения с .; 3;(modPl или Р- Ж мод Р), для которых колиt честно единиц в записи двоичного числа о -; ; (то«1 Р1 или P i р; (вод Р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, группы элементов И 50

23 — 25, входы 26 задания модуля, сумматор 2/ по модулю Р, выходы 28.

Информационные входы 1 и 2 подключены соответственно к входам входных регистров 3 и 4, выходы 55 которых через соответствующие дешифраторы 5 и 6, группы элементов KIH

7 и 8, группы к почей 9 и 10 после950 4 довательио подключеиы к первой и второй группам входов соответст-. вующих узлов 11 (выходные шины дешифраторов 5 и б объединены парами таким образом, что сумма значений, присвоенная каждой паре, равна модулю P), выходы когорых подключены к соответствующим входам выходного регистра 12. К управляющим входам групп к>гочей 9 и 10

Р1 подключен вход 13, Первая (1 - —, )

2 и вторая (Р " -Р*1) группы выходов дешифратора 5 подкл1очены к входам соответственно элементов ИЛИ 14 и

15, выходы которых подключены к первым входам соответственно элементов

И 16 и 17. Первая (1 — — ") и вторая (—. — Р— 1 ) группы выхо-

I+1 дов дешифрагора 6 падключеиы к входам се ответственно =-.ëåìåíòîâ ИЛИ 18 и 19, вь>ходы которых подкхгючеиы к вторым входам соответственно элементов И 17 и 16. Выходы с«лемеито» П 16 и 17 подключены к входам элемента

ИЛИ 20, выход которого подключен к входу сумматора 21 по модулю два, к другому входу которого подключен выход элемеита ИЛ«1 22, к входам которого подключены выходы узлов 11.

Выход сумматора 21 п<.»дключеи к входам 3>teNc.н гов ««23 — 25 ° K другим входам элемента И 23 подключены входы 26. К другим входам элементов

И 24 и 25 подключены выходы регистра 12. Выходы элементов И 23 и 24 подключень. соответственно к входам сумматора 27 ло модулю Р, выхоцы которого подключены к входам рсгистра 12, Выходы элемента И 25 являются выходами 28 устройства.

Узлы 11 представя«иот таблицы, реализ чощие ответы по каждому из

tt= (В@ (P-1!+1 двоичиых разрядов результата операции. Каиструктииио узлы 11 представляют набор элементов

И. Количество элемеитог> И в k-ом узле 11 равно количеству единиц 1<-ro разряда результата операции Р— d.; p. (modP1 или 8;p;(od P)i. Эти элементы И объединяются общей выходной шиной, подключенной к Ъ -му разряду выходного регистра 12. Одновременно, другой выход k-го узла 11 объединяет элементы И, для которых присвоено значение Р- сс; ь„(tt 03 PJ, . выходы узлов 11 падключсны к входам элемента ИЛИ 22.

Устройство работает следующим образом.

3 1126950

Входные операнды А и В„ А=(!)> -. { {

В (у ) ;) в двоичном коде поступа2от по входам 1 и 2 в соотыетс:, вующие реР-.-1

1 с А<--- ---2

2 т.е. если

«{рп

Р- A,ïðè у =1., Таблица 1

4 б lO -:-, 4

Таблица 2

{ ОС 1{

) 0 )010

С iiO

1001

1000

6 01 l O

0 lO! в унитарном коде через соответствующие элементы ИЛИ 7 и 8 поступа{от на соответствующую пару ключей 9 и

10. Сигнал с входа 13 открывает соответствующую пару ключей 9 и 10, ) I и операнды с )и Д одновременно пасту- - пают на входы всех {! узлов 11. В тех узлах 11, где определены 3íà÷àщие разряды результата для данных операндов с ; и {,. (единицы в узлах р таблицы) на выходе, подключенно"i --:: соответствующему разряду регистра l2, появляется сигнал, переводящий этот разряд регистра 12 в единичное состояние.

При у = уВ выходной сигнал элемента ИЛИ 20 отсутствует (нулевой сигнал на втором входе сумматора 21);

Если на выходе элемента ИЛИ 22 отсутствует сигнал то на вь{ходе сум матора 21 также отсутствует tигнал М (О + О = O tttod2) и элементы И 23

25 закрыты. В этом случае содержимое

t2{; р; ({22ос) Р j регистра 12 является результатом операции АВ (мd{2) °

Если на выходе элемента ИЛИ 22 пр:-; — 3 сутствует сигнал, то на выходе сумматора 21l также присутствует сигl{227 (О * 1 = 1 Noct2 ), который от;рывает элементы И 23 - 25. В этом случае на одни входы сумматора 27 (по «!хо- {О дам 26 через элементы И 23) поступает значение модуля Р, а на другие входы — содержимое:регистра 12, C выхода сумиатора 27 значение Р-а,; „.

{ tqod P ) =- 46(mc dР), которое является {5 результатом операции умножения по модул{о поступ сет !{а входы регист ра 12.

При г ф р i,«хоцной сигнал э«{ем". нто

Г

ИЛИ 20 присутствует, едицич{{ай сигна2{ -2{2 на первом входе умматора 2i), сли

HB ньГходе элемента ИЛИ - 2 о l ñ"/T{." i-вует сигнал, то на выходе сум.{аторе

21 также отсутствует сигнзл (1 + ) = O tt>{2d2 ) л элементы И 23 5:.

25 закрыты„ а результат операции пределяется содержимым сум{атGра

В(mad Р) Ж Г ({2{о ) гистрь! 3 и 4 и далее в деши{12раторы

5 и 6, после которых операнды

К;и р

Р+ 1 (т е. если =-- — А < P — 1), Рассмотрим при21ер конкретного выполнения огерации АВ({во{ P) для

Р г 1,. В.этом случае количество узлов 11 равно n = 4. В изобретении реализуется 0„25 части полной таблицы AB(mod Р), т.е. табл. 1, в которой знаком + " отмечены те узлы таблицы, для которых количество единиц в записи числа М;)Ъ;(vnodP) больше, чем для чиспа Р-d.; р,.(tnadP) (см. табл. 2). Табл. 3 реализуется при количестье узпов l1 равном и- 4.

t2.: ° )5 ({чо 2 I1! P-d., )5 (mod 4, 1126950

Т аблица 3 з 6 ю

4 О О .О О 1+

4 5

1 .2 8+ 4 5

2 4 6 8 1 10

8+ 6 2+ 1 4

4 8 1 5 2+

Т аблица 6

1 2 3 4

5 1+ 4 2+ 8+

Таблица r åðâîãî узла 11 (для иер- 20 вого (младшего) разряда результата операции) имеет вид таблицы 4 (таблица второго узла 11 имеет вид таб-. лицы 5; таблица третьего узла.11 имеет вид таблицы 6; таблица чет- 25 вертого узла 11 (для четвертого (старшего) разряда результата операции) имеет вид таблицы 7.

Таблица 7

Т а блица 4

2 3 4 5

) 35

О 1 . О

О О

f 2

1+ 3

О 40 4

О О О

О

5 1+

О 0 О О

О 1

1 . О О О

Знаком " " отмечены те узлы (элементы И) таблиц узлов 11 (см. табл.

4 — 7), которые объединяются выходами, подключенными к входам

50,элемента ИЛИ 22.

Пример 1. Пусть необходимо определить АВ(mod f1), для A = 5 (gA= О), В = 6 ()в-=11).

В регистр 3 записывается гервый

55 операнд А 0101, а в регистр 4— второй операнд В = 0110. С выхода де- .шифратора 5 операнд поступает на пятый элемент ИЛИ 7 и через элемент

Т аблица 5

2 О . О О О

1 О 1 О 0 О

2 1 О 1 О О

3 . 0 1 1+ 0 0

5 О О О 1+. 0

1 О О О 1

2 О 1 1 О О.

3 О 1 О О

4 1 О О - 1 О

5 1 О 1 О 0

О 0 1+ О О

1+ 0 О О О

1 0 0 О

ИЛИ 14 на вход элемента И 16. С выхо" да дешифратора 6 ;;. анд поступает на пятый (6 - 5 = Р) =.:емент ИЛИ 8 и через элемент ИЛИ 19 на вход эле- мента И 16. Таким образом, элемент И 5

16 открыт и на выходе элемента ИЛИ

20 (на входе сумматора 21) присутствует сигнал. Сигнал - входа 13 одновременно открывает пятый ключ 9 и.пятый ключ 10, и операнды с ; -" 5, P, = 5 поступают на входы всех узлов 11. Первый узел 11 (табл. 4) опреде-.. ляет значение ноль, второй узел 11 (табл. 5) определяет значение ноль," третий узел 1 1 (табл. 6) определяет 5 значение ноль; четвертый узел 11 (табл. 7) определяет значение единица. Таким образом, в регистре 12 содержится "1000", На выхоце четвертого узла 11 присутствует сигнал 20 (в узле Ы; = p; = 5 табл. 7 едипица . со знаком " +")„ который через элемент ИЛИ 22 поступает на второй вход сумматора 21. Иа выходе сумматора 21 отсутствует сигнал 25 (1 + = 0 (в1об 2)), и таким образом, элементы И 23, 24, 25 закрыты. В этом случае содержимое "1000" регистра 12 является искомьь1 резуль1атом операции.

Проверка:: 5 ° 6 = 8 (,жд11) .

Пвимер2.А -5 (у =О) В= 4. (" e 0) ЦЕПЬ ПРОХожДЕНэээЯ ПЕРЦОэ О, ПЕРаида A OiOI описана в примере 1, Второй oII -Ранд 0100 "- pe- истра через дешифратор 6 в унитарном коде пос7упает на четвертый элемент ИЛИ 8 через эле?унт И1К! 1 8 па Б7ъод эле" мента И 1 Я >óoù случае Отсутсч в- v. т

СИГНаП Н.э ЗЬ1ХОдв ЭЛЕ1 -эи7 а КДI 20 (отсутствует сигнал на первом вхо.де сумматора ." ",). Сигнал с входа 13 одновременно открывает пятый ключ

9 vi четвеРТ1э1й ключ 10,. и ОпеРанпы

5 > p ; = 4 io< тупают на вхОды всех узлов 11. Первый узел 11 (табл. 4)

ОПРЕДЕЛЯЕТ ЗнаЧЕНИЕ 11ОЛ7э, В-1ОООй

1 1 (1 аб11 >) .«IIIп 11да э тпеп 11и узел I I (таба. 6) -:,1ольэ„-Iетвертьо:,.-р

Т аблица 8

Количество элементов. И г

P О11 O) 1рототип

Данное устройство

Выигрыш в процентах на 30% на 257

Преимущество предлагаемого устройства,по сравнению с Iipo707 HIIoli; эакл10чается в уменьшении coJIH÷Ðства оборудования пр11 сох17анении всеx фУНКЦИОНаЛЬНЫХ H ТЕХНИэ1ЕСКГХ ВОЗМОжностей ycòpolioòíà, что достигается сокращением элеме iT013 И в y-.IBx

, pl1I 1э1оду. 1я - 1 I сок1> .эця(- тся э эЕ элементов и (см,, табл. 8)).

950 IO узел 11 (табл, 7) — ноль. Таким образом„ в регистре 12 содержится "0010". На выходе втoðîãî узла 11 присутствует сигнал (â узле Ы; †" 5, P; = 4 таблицы 5 единица со знаком

"+ ), который через элемент ИЛИ 22 постугает на второй вход сумматора 21 На выходе сумматора 21 присутствует сигнал (О + 1 = i (rnod2)). и таким образом, элементы И 23 — 25

Открыты. В этОм случае по вхоцам

26 через. элементы И 23 на вход сумма,тора 27 поступает значение модуля

Р = 10.11, на другой вход сумматора 27 с выхода регистра 12 (через элементы И 24) поступает значение "0010"

С выхода сумматора 27 значение

Р— 0010 =. 1001 поступает в регистр 12.

Зтот операнд 100 I и определяет результат операц:;-;и. Проверка, 5 ° 4 (117ос1111) = 9.

3 табл, 3 в качестве примера приведены данные О количестве элементов И в узлах 11 для Р = 7 и Р = 11.

BMQKH Заказ 8693/37 Тираж 698 Подписное

Фжлиал HHG "Патент, г.Ужгород, ул.Проектная, 4