Устройство для умножения по модулю м=2 @ -1

 

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕС(1УБЛИК

„„80„„1383339 А1 (5))4 С 06 F 7/49

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

" «,, « «-».

F, l3I

: j«

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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4090600/24-24 (22) 15.07.86 (46) 23.03.88. Вюл. 11» ll .(71) Физико-механический институт им. Г.В«Карпенко (72) Л.В.Вариченко (53).681.325 (088.8) (56) Авторское свидетельство СССР

11» 1160398, кл. G 06 F 7/49, 1983.

Авторское свидетельство СССР 11» 1254471, кл. G 06 F 7/49, 1985. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ПО МОДУЛЮ М2"-1

{57) Изобретение относится к вычисли- тельной и информационно-измерительной технике и может быть использовано в устройствах для цифровой обработки сигналов, в частности, для цифровой обработки изображений, а также в устройствах кодирования,. принцип действия которых базируется на теории конечных колец и полей Галуа. Цель изобретения - повышение быстродействия. Устройство содержит группы входов I 2 прямого и инверсного значений одного операнда, группу входов 3 другого операица, коммутатор 4, блок

5 формирования частичных произведений, блок 6 суммирования частичных произведений, блок 7 коррекции, коммутатор 8, многовходовой одноразряд-. ный сумматор 9, группу элементов НЕ

10. выходы 11. 1 з.п. ф-лы, 10 ил.

1383339

Изобретение относится к вычислительной технике и информационно-измерительным системам и может быть использовано в устройствах для цифро5 вой обработки сигналов, в частности, для цифровой обработки изображений а также в устройствах кодирования, принцип действия которых базируется на теории конечных колец и полей Га-. 10 луа.

Цель изобретения - повышение быстродействия устройства.

На фиг.l приведена функциональная схема устройства для умножения по мо- 15 и дулю М-2 -1; на фиг.2 - функциональная схема многовходового (п-входового) одноразрядного сумматора, на фиг.3 - функциональная схема коммутатора; на фиг.4 и 5 — функциональная 20 схема блока формирования частичных произведений; на фиг.б — функциональная схема узла приоритета; на фиг.7— функциональная схема сдвигателя, на фиг.8 — схемы умножителей на степе- 25 ни двойки; на фиг.9 — функциональная схема блока суммирования частичных произведений; на фиг ° 10 — функциональная схема блока коррекции.

Устройство для умножения по модулю М=2 -1 (фиг.l) содержит группу входов 1,, 1,..., 1„ прямого значения операнда Ь,, Ь,,. ° ., Ь„, группу входов 2,, 2,..., 2„ инверсного значения операнда Ь,, b,..., Ь„, группу входов 3,3,..., 3 „ (прямого зна-. чения) второго операнда а,, а а„, коммутатор 4, блок 5 формирования частичных произведений, блок 6 суммирования частичных произведений, 40 блок 7 коррекции, коммутатор 8, многовходовой одноразрядный сумматор 9, группу элементов НЕ 10,, 10 ...,10„, выходы 11<, 11, ° ... Il Значения операндов могут быть выбраны из ре- 45 гистров (при этом прямые и инверсные выходы одного регистра могут быть соединены с входами 1,, ° .., 1„ и 2,, 2 ), и в регистр же может быть занесено значение результата с выходов 11„,..., ll Сумматор 9 своими входами 12 „ 12,..., 12„ соединен с входами 1,, 1,..., .1„, а выходом 13 старшего разряда — с управляющими вхоцами коммутаторов 4 и 8. Информационные входы коммутатора 4 соединены с входами I 1,..., 1„ и 2,, 2,..., 2„, а выходы 14,, 14

14„ - с первой группой входов блока 5, вторая группа входов которого соедииена с входами 3,, 3,..., 3„, а выходы 15,, 15,..., 15„(где k

= — — при п — четном k = — — — при

n — нечетном) подключены к входам блока 6, выходы 16(, 1бя,,...в 16л.кторого подключены к входам блока 7, в моды 17) 172, ° . 17„ которого соединены с входами элементов НЕ 10, 10,..., IO„ и первой группой информационных входов коммутатора 8, вторая группа входов которого подключена к выходам элементов НЕ 10<, IOä, ° ° ю 10 °

Многовходовой одноразрядный .сумматор 9 (фиг.2) построен на двоичных сумматорах 18.

Коммутатор 4 (фиг.3) содержит элементы И 19,, 19,,...; 19 „, 20,, 20

22 ° Коммутатор 8 строится аналогично.

Блок 5 формирования частичных про" изведений (фиг.4 и 5) содержит узлы

23,, 23, 23» ..., 23к приоритета, группы сумматоров 24 по модулю два, сдвигатели 25,, 25,..., 25„. Совокупности узлов 23 и сумматоров 24 onределяют управляющие коды, которые поступают на управляющие коды сдвигателей 25, на информационные входы ко-!

",îðûõ подается с входов 3,, 3

3„ код операнда а,, а,..., а„. Каж- . дый 8-й узел 23 (фиг.б), где В =

1, 2,..., k, имеет входы 26з„..., 26зк и выходы 27 „..., 27зк . Узел

23 содержит элементы HE 28,,..., 28к-, И 29, . ° . ° ь 29к °

Каждьп сдвигатель 25 (фиг. 7) содержит группы элементов И 30, умножители 31 на степени двойки и группу элементов ИЛИ 32.

Блок 6 суммирования частичных произведений (фиг.9) имеет k и-разрядных входов и содержит двоичные сумматоры 33 и узел 34 ускоренного переноса.

Блок 7 коррекции (фиг.10) содержит двоичные сумматоры 35, узел 36 ускоренного переноса и элемент И 37. В совокупности блоки б и 7 йредставляют собой сумматор k чисел по модулю M. . Произведением чисел а и Ъ по модулю И q = а Ь (mod М) называется остаток от деления обычного произведения

ahab на значение модуля M.

1383339

Принцип быстрого умножения заключается в следующем.

Для М = 2 — 1 справедливо равенство: -а = а, т.е. отрицательное число 5 в кольце Z> (множество целых чисел (»"

О, 1, 2,..., M-I с рассматриваемыми на нем операциями сложения и умножения по модулю М), представленное в двоичной системе счисления, получает- 1ð ся в.результате инверсии соответствующего ему положительного числа. Отрицательные числа оказываются закодированными целыми числами, большими

М., Например, для 2,» = Z7 можно записать соответствие . 00, 1 1,2 2

3 3 4-3, 5 -2, 6-1. В двоичной системе счисления эти числа можно представить трехразрядными двоич- 20 ными числами: -001 = 11 0 =. 6; -010 =

101 = 5; -011 = 100 = 4, значит ум" ножение можно проводить по следующему выражению. а.Ъ (mod.М) = (а.b) (mod M) . (1) 35

Результат умножения по модулю М = и

2 - 1 имеет число разрядов, равное числу разрядов каждого из сомножителей. 30

Очевидно, что инверсия одного из сомножителей согласно (1) целесообразна лишь в том сЛучае, если этот сомножитель (в выражении (1) число

Ъ) имеет больше половины единиц в значащих разрядах. Управление работой коммутатора 4 осуществляется с помощью п-входового одноразрядного сумматора 9, на котором формируется сумма разрядов множителя. Если число 40 единиц в разрядах множителя больше

n/2, значение ш"го разряда на выхои г де сумматора 9 (т = )1о9 — -, тае скобки 1(обозначают округление до ближайшего большего целого числа) равно единице. Значения младших разрядов .не используются. Значение разряда сумматора 9 является управляющим сигналом для коммутатора 4. С выходов коммутатора 4 прямое или ин50 версное значение множителя подается на входы блока 5, на другие входы которого подается множимое с входов 3,, 3,..., 3„. Блок 5 формирует k слов частичных произведений, которые подаются на выходы 15,, 15,..., 15„ (каждый выход и-разрядный). Слова частичных произведений суммируются с помощью блока 6 и корректируются блоком 7, на выходах 17», 17

17 которого формируются разряды слова суммы частичных произведений. С этих выходов прямое значение слова суммы частичных произведений поступает на первые входы коммутатора 8.

Кроме того, слово суммы частичных произведений инвертируется с помощью элементов НЕ 10,, 10,..., 10 „ и подается на вторые входы коммутатора 8.

Управляется последний с помощью того же управляющего сигнала, что и комму" татор 4. Таким образом, если производится инверсия множителя с помощью коммутатора 4, осуществляется инверсия результата умножения с помощью коммутатора 8, как того требует выражение (1). С выходов коммутатора 8 и значение произведения по модулюМ=2 подается навыходы 11 устройства.

П р и и е р. При работе блока 5 пусть необходимо умножить два числа а = 1101011 (п = 7 и М = 2 — 1) и Ь = 0011011.

Умножение проводится согласно (1).

Значит слово а подается на входы 3,, 3,2,..., 3„, инверсное слово b =

1100100 подается на выходы 14,, 14,..., 14 „. Первые (младшие) k разрядов поступают на входы узла 23».

Задачей узла 23 является выбор едиS ницы, которая встречается впервые в слове, поступающем на входы этого узла. На входы 26„, 26,,..., 26„, (k = (7 + 1)/2 = 4) узла 23, подается слово 0010. На выходах 27„,...,. 27»,» имеют 0010 (в этом слове только одна единица, поэтому входное значение совпадает с выходным). Это слово яв-. ляется управляющим для сдвигателя

25, . На первые входы сумматоров 24«24, по модулю два подается слово.

010, а на вторые входы сумматоров

24«-24, — слово 010 с выходов 27» 27»4 узла 23». На вход 26 узла 23 подается эначенйе пятого разряда,т.е. нуль. Значит на сумматорах 24„ -24» суммируются по модулю два слова 010 и 010, что в результате дает слово

000. В результате на входах и выходах узла 23 имеют нулевое слово 0000, которое также является управляющим для сдвигателя 25. На первые входы сумматоров 24, -24, по модулю два подается слово 000 с выходов сумматоров

24,z и 24„ .первые два разряда и третий разряд с выхода 14 . На вторые

5 13833 входы сумматоров 24, -24 3 подается слово 000 с выходов 27 -27 узла 23 .

На вход 26 4 узла 23 подается значение шестого разряда, т,е. единица.

Значит на сумматорах 24, -24 3 суммируются по модулю два слова 000 и 000, что в результате дает слово 000. В результате на входах узла 233 находится слово 0001 и на выходе точно такое же слово 0001, которое является управляющим для сдвигателя 253.

На первые входы сумматоров 24, -24 3 по модулю два подается слово 001 с выходов сумматоров 24 и 24 3 первые два разряда и третий (k+2)-й разряд с выхода 14 . На вторые входы сумматоров 243, -24 3 подается 001 с выходов 273 2734 узла 233. На вход 2644 этого узла подается значение послед44 1 него, т.е. седьмого разряда, равное единице. На сумматорах 243, -243 суммируются по модулю два слова 001 и

001, что в результате дает слово 000..

В результате на входах узла 234 нахо-25 дится слово 000) и на выходе точно такое же слово 0001, которое является управляющим для сдвигателя 254.

Схема узла 23 осуществляет функцию выбора первой единицы в кодовом слове, которое поступает на входы 26,, 2632,, 26 „ . Умножители 31 на-степени двойки осуществляют умножение множимого на степень двойки по модулю М, что является обычным циклическим сдвигом и эти умножители представляют собой простую перекоммутацию проводов. На фиг.8 приведена такая перекоммутация для случая И = з — 2 -1. Умножитель 31 на степень

Si 40 двойки осуществляет умножение множимого на 2, умножитель 31в — на 2, умножитель 31 „ - на 2 ", причем умножение проводится по модулю

M. В результате происходит циклический сдвиг множимого с помощью управляющего слова, поступающего на входы элементов ИЛИ 32;,, 32 " 32;„.

Если в управляющем слове j-é разрядравен единице, работает линейка элемен- . тов И 30,„, 30 „,..., 30, умножитель 31 „ нн степень двойки который

iij-< осуществляет умножения на 2 . Резул:ьтат умножения подается на выходы сдвигателя 25„через элементы ИЛИ 32.

На выходах остальных умножителей на степени двойки (умножители 31,, 31,..., 31 „ ) — сигналы, соответствующие значению логического нуля.

39

Блок 6 реализует операцию суммы по модулю M kn-разрядных слов частичных произведений. Блок 7 коррекции устраняет неоднозначность представления нуля 0 = 2-1 (mod И = 2" — 1). В двоичной системе счисления нуль может представляться нулевым кодовым словом 000...0, а также словом

111... 1 = 2" —, 1. Блок 7 коррекции преобразует единичное слово в нулевое.

Формула изобретения

1. Устройство для умножения по модулю М = 2 — 1, содержащее блок формирования частичных произведений, блок суммирования частичных произведений и блок коррекции, причем группа входов одного из операндов устройства соединена с одной из групп входов блока формирования частичных произведений, выходы которого соединены с входами блока суммирования частичных произведений, выходы которого соединены с входами блока коррекции, отличающееся тем, что, с целью повьш)ения быстродействия, в него введены два коммутатора, многовходовой одноразрядный сумматор и группа элементов НЕ, причем другая группа входов блока формирования частичных произведений соединена с выходами первого коммутатора, первая и вторая группы информационных входов которого соединены соответственно с группой входов прямого значения и группой входов инверсного значения другого операнда устройства, вь ходы блока коррекции соединены с первой группой информационных входов второго коммутатора и входами соответс1вующих элементов НЕ группы, выходы которых соединены с второй группой информационных входов второго коммутатора, выходы которого являются выходами устройства, а управляющий вход соединен с управляющим входом первого коммутатора и выходом старшего разряда многовходового одноразрядного сумматора, входы которого соединены с первой группой входов информационных входов первого коммутатора.

2, Устройство по п.1, о т л и ч а ю щ е е с я тем, что блок формирования частичных произведений содержит k узлов приоритета, (k-1) групп сумматоров по модулю два и k

1383339

121

12

12

12

127

128 !

12л-8 !

2л-7

12л-6

° °

4 .

12h 5

f2h-Ф

12h.-g

12л 2

1гл.1

1 .

ФИ8. 2 и сдвигателей (k = — — при n - четном

%

n+1

k — — при n — нечетном; n - раз2

5 рядность операндов), причем входы первого узла приоритета соединены с входами первой группы блока с первого по k-й, входы i-ro узла приоритета (i 2,..., k) соединены с выходами сумматоров по модулю два (i-1)-й . группы и (k+i-1)-м входом первой группы блока, первый вход j-ro сумматора по модулю два (i-1)-й группы (j . 1 ° ° ° k 1) соединен с ()+1) M 15 выходом (i-1)-.го узла приоритета, второй вход j-ro сумматора по модулю два второй группы соединен с (j+1)-м входом первой группы блока, второй вход х-го сумматора по модулю два

1-й группы (r = 1,..., k-2, 1 2, . ° ., k-1) соединен с выходом (r+1)-го сумматора по модулю два (1-l)-й группы, выходы узлов приоритета соединены с управляющими входами соответствующих сдвигателей, информационные входы которых соединены с входами второй группы блока, а выходы - с выходами блока.

1383339

l383339

26

2

151п

15А

Фиг. Х

1 383339

$1

3п

lSs

1 г

Х

4 о

2

Я

1 г

1

3

f

15е

g бд

15су

О is>

f 15и

15,»

6уу

151

2

3 1$

Ф а2" 1383339

1383339 фиг. 10

Составитель В.Березкин

Текред Л.Олейник Корректор О. Кравцова

Редактор Н.Рогулич

-Заказ 1297/47 Тираж 704 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4