Матричное устройство для умножения чисел по модулю 2 @ -1 Советский патент 1986 года по МПК G06F7/49 

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

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

На фиг.1 приведена схема матричного устройства для умножения чисел по модулю 2 - 1; на фиг.2 - блок формирования частичных произведений; на фиг.З - блок суммирования частичных произведений; на фиг.4 - блок коррекции результатаj на фиг.З - группа линеек одноразрядных сумматоров; на фиг.6 - примеры построения блока суммирования частичных произведений для конкретных значений п.

Матричное устройство для умножения чисел по модулю (фиг.1) содержит блок 1 формирования частичных произведений, блок 2 суммирования частичных произведений, п-разрядный сумматор 3, блок .4 коррекции результата, группу (п-1) элементов И 5 и

Множимое А а

, +

. п

а h-, 2

|П-г

+ ...

а,

л-

и множитель

В b 210

+ а,-2 ,, + ... + 2 + Ъ поступают на входы блока 1 формирования

5 частичных произведений. Блок 1 обра- з ует попарные произведения а, Ь; (i 1, 2, ..., п; j 1, ... п). Произведения разрядов множимого на мпад- ший разряд множителя , образуют слово q, частичных произведений первой ступени, произведения разрядов множимого на второй разряд множителя обрузуют слово q частичных произведений второй ступени, ..., произведения разрядов множимого на старший (п-й) разряд множителя , образуют слова q частичных произведений п-й ступени, причем в k-м разряде слова q,- (k 1, .. . п) стоит произведение

20 Hjb. , где k (j - i + 1) Моа„((А) х X Modn - п при А кратном п, (А) Modn равно целому положительному остатку от деления А на п при А не кратном п). Другими словами, блок 1 формирует ци)5

25

клически сдвинутые по сравнению со случаем обычного множителя слова, так как умножение на число вида 2 равгруппу сумматоров 6 по модулю два. В п-разрядном сумматоре 3 р

Ч.

а,Ь,

а„Ь.

,.,

.

носильно циклическому сдвигу влево на 06 разрядов п-разрядной двоичной

- вход пе- 30 записи множимого (потому что 2 сов- реноса, р - выход переноса, А - входы падает с единицей по модулю 2 - 1). первого слагаемого, В - входы второго Таким образом, блок формирования ча- слагаемого, S - выходы суммы. стичных произведений образуе-т следуюБлок 1 формирования частичных-про- щие слова: изведений (фиг.2) состоит из двухвхо- с довых элементов И 7.

Блок 2 суммирования частичных произведений (фиг.З) состоит из группы линеек 8 одноразрядных сумматоров, q,, ... q - входные слова блока сум- Q мирования частичных произведений, U, V - его выходные слова.

Блок 4 коррекции результата (фиг.4) состоит из п-входового элемента И-НЕ 9 и группы элементов И Ш. j

Линейка длины п (фиг.З) состоит из одноразрядных сумматоров 11, h,, hy, hj - входы линейки, U - выходы слова суммы линейки, V - выходы слова переноса линейки, S - выход суммы од- ;0 поразрядного сумматора, р - выход переноса одноразрядного сумматора.

Матричное- устройство для умножения чисел по модулю 2 - 1 выполняет умножение двух п-разрядных двоичных чисел по модулю 2 - 1,

п - п-п

Блок 2 суммирования частичных произведений представляет собой древовидную структуру из группы линеек 8 одноразрядных сумматоров. Число с линеек одноразрядных сумматоров в первой группе линеек задается соотношением с

-§-, где

обозначает целую часть числа. На первые - третьи входы всех линеек первой группы линеек блока 2 суммирования частичных произведений поступают 3с( слов с блока 1 формирования частичных произведений (по три слова на каждую ли- 55 нейку). Каждая линейка 8-состоит из п одноразрядных сумматоров 11. В ней происходит поразрядное сложение трех п-разрядных слов h,, h, hj и обраУстройство работает следующим образом.

-

яМножимое А а

2

, +

. п

а h-, 2

|П-г

+ ...

а,

л-

и множитель

В b 210

+ а,-2 ,, + ... + 2 + Ъ поступают на входы блока 1 формирования

5 частичных произведений. Блок 1 обра- з ует попарные произведения а, Ь; (i 1, 2, ..., п; j 1, ... п). Произведения разрядов множимого на мпад- ший разряд множителя , образуют слово q, частичных произведений первой ступени, произведения разрядов множимого на второй разряд множителя обрузуют слово q частичных произведений второй ступени, ..., произведения разрядов множимого на старший (п-й) разряд множителя , образуют слова q частичных произведений п-й ступени, причем в k-м разряде слова q,- (k 1, .. . п) стоит произведение

20 Hjb. , где k (j - i + 1) Моа„((А) х X Modn - п при А кратном п, (А) Modn равно целому положительному остатку от деления А на п при А не кратном п). Другими словами, блок 1 формирует ци)5

25

клически сдвинутые по сравнению со случаем обычного множителя слова, так как умножение на число вида 2 равЧ.

а,Ь,

а„Ь.

,.,

.

п - п-п

Блок 2 суммирования частичных произведений представляет собой древовидную структуру из группы линеек 8 одноразрядных сумматоров. Число с линеек одноразрядных сумматоров в первой группе линеек задается соотношением с

-§-, где

обознача

ет целую часть числа. На первые - третьи входы всех линеек первой группы линеек блока 2 суммирования частичных произведений поступают 3с( слов с блока 1 формирования частичных произведений (по три слова на каждую ли- нейку). Каждая линейка 8-состоит из п одноразрядных сумматоров 11. В ней происходит поразрядное сложение трех п-разрядных слов h,, h, hj и образуется два п-разрядных результирующих слова и и V. Слово U состоит из значений на выходах суммы одноразрядных сумматоров, причем j-й разряд слова (J 1, 2, ..., п) совпадает со значением на выходе суммы j-ro сумматора..Слово V состоит из значений на выходах переноса одноразрядных сумматоров, причем j-й разряд этого слова (J 2, ..., п) совпадает с значением на выходе переноса (j-1)- го сумматора, а первый разряд - с значением на выходе переноса п-го сумматора, (так как 2 совпадает с единицей по модулю 2 - 1). На выхо- дах линеек первой группы в результате сложения формируется 2с( слов. Кроме того, имеем п - 3с, входных слов , блока 2 суммирования частичных произведений, которые не поступили на вхо-20 ние неоднозначности представления ну- ды линеек первой группы, общее число слов после прохождения первой группы линеек древовидной структуры равно

ля в устройстве, возникающее из-за равенства слов р... 00 и 1. .. 1 1

п-разрядов п-разрядов по модулю 2 -1.

т. е. на

2с +п-3с, п-с,. Число с линеек во второй группе линеек задаетс

Гп - с, выражением с„ |г-(

входы линеек второй группы поступают Зс слов из числа п - с слов. На выходах линеек второй группы после сложения образуется 2с слов. Общее число слов после прохождения второй группы линеек равно 2с + п - с

- Зс п - с.

Число С- линеек

в третьей группе задается соотношени

ем ( -сг I I J,

т. е. на

входы линеек третьей группы поступаю 3cj -слов из чисйа п - с, с слов. На выходах линеек третьей группы после сложения образуется 2сз слов. Общее число слов пос ле прохождения третьей группы линеек равно 2сj+ п п-с, -с, -с.

- с, - Сг - Зс

Число линеек в четвертой группе

линеек задается выражением с

fn - с, - с,- с-., 1.1iU т. д.

Число k групп линеек выбирается таким образом, чтобы после прохождения k группы образовалось два слова, которые являются выходными словами и и V блока 2. ,

Результирующие слова U и V складываются с помощью п-разрядного сумматора 3.

Если перенос при сложении не возникает, то на выходах всех элементов И 5 - нулевые значения. На выходы сумматоров 6 по модулю два пропускается код с выходов блока 4 коррекции результата. В случае, когда хотя бы один из разрядов суммы на выходах сумматора 3 отличен от единицы, на выходе элемента 9 И-НЕ логическая единица, и полученная сумма проходит на выходы элементов И 10 и далее на .выходы устройства.

В случае равенства всех разрядов суммы на выходах сумматора 3 единице на выходе элемента И-НЕ 9 - логический нуль, и на выходах блока 4 все нули, которые проходят на выходы устройства.

Таким образом, происходит устране0 ние неоднозначности представления ну-

5

0

5

0

5

ля в устройстве, возникающее из-за равенства слов р... 00 и 1. .. 1 1

п-разрядов п-разрядов по модулю 2 -1.

Если возникает перенос при сложении :результирующих слов U и V, то его необходимо прибавить в младший разряд полученной суммы. Заметим, что, так как каждое из слагаемых, поступающих на сумматор 3, не превьппа- ет 2 -1, то полученная сумма с учетом переноса не больше 2 + + (2 - 2), а сумма без учета переноса не больше . Это означает, что хотя бы один разряд сум-,, мы отличен от единицы, и она проходит. на выходы блока 4 коррекции результата. Элемент S;(i 1, ,.., п - 1) формирует перенос из i-ro в (1+1)-й разряд при добавлении единицы к полу- ч.енной на выходах сумматора 3 суммы. Перенос из i-ro в (1+1)-й разряд равен единице, если разряды S,... S,-., суммы равны единице. Сумматоры 6 по модулю два прибавляют образованные переносы к соответствующим разрядам ол5 енной суммы.

На выходах устройства получаем произведение А В по модулю 2-1.

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

1. Матричное устройство для умно- кения чисел по модулю 2-1, содержа- цее блок формирования частичных про- наведений, выполненный в виде матрицы п х п элементов И (п - разрядность множимого и множителя), блок :суммирования частичных произведений.

51

п-разрядный сумматор, блок коррекции результата, причем первые входы элементов И i-й строки матрицы (i 1, 2... п) соединены с входом i-ro разряда множителя устройства, вторые входы (i, j)-x элементов И (j-номер столбца матрицы, j 1, 2... п) соединены с k-M разрядом входа множимого устройства, где k (j - i + 1) Modn ((A) Mod n n при A кратном n, (A) Modn равно положительному остатку от деления A/n при А не кратном п), выходы элементов И i-й строки матрицы соединены с информационными входами J-X разрядов i-ro слова блока суммирования частичных произведений, выходы разрядов первого и второго результирующих слов которого соединены с информационными входами первого и второго слагаемых п-разрядного сумма- тора, вход переноса которого соединен .с щиной логического нуля, группа выходов суммы которого соединена с группой входов блока коррекции результата, отличающееся тем, что, с целью повышения быстродействия устройства, в него введена группа из (п-1) элементов И, р-й (р 1, 2... п-1) элемент И имеет (р+1) входов и группа п сумматоров по модулю два, причем q-и (q 1, 2... р) вход р- го элемента И группы соединен с q-м выходом суммы п-разрядного сумматора выход переноса которого соединен, .с (р+1)ми входами элементов И группы и первым входом первого сумматора по модулю два группы, выходы элементов И группы соединены с первыми входами сумматоров по модулю два группы с второго по п-й соответственно, вторые входы которых соединены соответственно с выходами блока коррекции резуль

43

тата, выходы сзгмматоров по модулю два являются выходами устройства.

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

55

3. Устройство по П.1, о т л и ч а- ю щ е е с я тем, что блок суммирова

5 0

6

ния частичных произведений состоит из групп линеек длиной п одноразрядных тpeixoдoвьrx сумматоров, причем число линеек с„ в т-й группе линеек 5 задается соотношением

т-(

I .IIc; 1 1

m

(m 2 - k),

где

П. k целая часть числа;

число групп линеек, числ

линеек в первой группе

Г и 1 линеек равно с, |

г-й вход (г 1, 2, 3) j-ro. (j 1, 2... n) трехвходового одноразрядного сумматора В-й линейки (t номер линейки) первой группы линееК соединен с входом j-ro разряда i-ro частичного произведения (где i 3(Е-1)+г) блока суммирования частичных произведений, первый вход jro (j 1, ... n) сумматора F-й линейки (F - нечетное) т-й группы линеек соединен с выходом суммы

3 г -

-Jro сумматора

-и линейки

(т-1)-й группы линеек, второй вход первого сумматора t-й линейки (В - нечетное) т-й группы линеек соединен с выходом переноса п-го сумматора

-и линейки (т-1)-й группы

3 - 1

2

линеек, второй вход р-го сумматора (р-2.., п) i-й линейки ( - нечетное) тй группы линеек соединен с выходом переноса (р-1)-го сумматора

зе - 1 „ ,

2 линейки (т-1)-й

группы линеек, третий вход j-ro сумматора {-и (Е - нечет- , ное) линейк т-й группы линеек соединен с выходом суммы j-ro

3 - 1 .

группы линеек, первый вход р-го сумма-, тора 1-й линейки (Е - четное) т-й группы линеек соединен с выходом песумматора

-и линейки (т-1)-й.

реноса (j-l)-ro сумматора

2

-и

линейки (т-1)-й группы линеек, .. первый вход первого сумматора Е-й линейки (F - четное) и т-й группы линеек соединен с выходом переноса пГо сумматора

-и линейки

2

2

(т-1)-й группы линеек, второй вход j-ro сумматора F-й линейки (Е - четное) т-й группы линеек соединен с - выходом суммы j-ro сумматора

3

-::-- -и линейки (т-1)-й группы линеек, третий вход р-го сумматора линейки (F - четное) т-й группы линеек соединен с выходом переноса

3 (j-l)-ro сумматора -т- -и линейки

(т-1)-й группы линеек, третий вход первого сумматора Н-й ( - четное) линейки т-й группы линеек соединен с выходом переноса п-го суму атора

31

-и линейки {ш-1)-й группы линеБлоисуммир. произв.

п-разр. суммат. блок кор.

Блок рормир. произв.

54А718

ек, свободные входы сумматоров последней линейки т-группы линеек соединены с выходами суммы или переноса сумматоров линеек группы линеек пре- 5 дьщущих k (т-1)-й группе линеек, либо

с входами разрядов соответствующих слов (из оставшихся (п - Зс)) блока суммирования частичных произведений, выход суммы j-ro сумматора линейки

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

20 блока суммирования частичных произведении,

Фаз, 1

}i° 0nbf ... ogbf a,bi fi 0n-i a ... effdg Offbg 5 „./ , а„.зЬу ... апЬз

«

}n-0lt n°n n...

9U8. 9 --

9 VI-HE

10,

и

Юг И

iOn И

PU8.

Фив. 5

Изобретение относится к области вычислительной и технической кибернетики и может быть использовано в устройствах для цифровой обработки сигналов (в частности изображений), а также в системах кодирования, принцип действия которых базируется на теории полей Галуа. Целью изобретения является повышение быстродействия устройства. Поставленная цель достигается тем, что блок суммирования частичных произведений вьшолнен в виде древовидной группы линеек, блок коррекции результата содержит п-входовой элемент И-НЕ и группу п элементов И, введены группа элементов И и группа сумматоров по модулю два. Введение группы элементов И и группы сумматоров по модулю два и новых связей, а также новое вьшолнение блока суммирования частичных произведений и блока коррекции результата позволило повысить быстродействие устройства. 2 3. п. ф-лы, 6 ил. с SS (Л

пЧ

л 15

(Риз. 6

Редактор Н.Слободяник

Составитель Н.Маркелова,

Техред Л.Сердюкова Корректор Л.Патай

Заказ 4721/52Тираж 671Подписное

ВНИЙПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб,, д. 4/5

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