Матричное множительное устройство

 

МАТРИЧНОЕ МНОЖИТЕЛЬНОЕ УСТРОЙСТВО, содержащее блок формирования частичных произведений, выполненнь в виде матрицы п х п элементов И (П - разрядность множимого и множителя) и блок суммирования частичных произведений, выполненный в виде древовидной матрицы г xU П разрядных сумматоров (t logjh колич ,ество ярусов в матрице. О « - количество П -разрядных сумматоров в I -М ярусе матрицы, где I 1, .../i), причем первые входы элементов И -и строки матрицы соединеш г с входом i -го разряда множителя устройства (j 1, ..., п ), м-й разряд множимого которого соединен с вторыми входами

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

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

РЕСПУБЛИК (l9) (3Ц (si)4 G 06 Р 7/49

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

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

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

3 г0, ))а„ая (21) 3688164/24-24 (22) 09.01.84 (46) 30.07.85. Бюл. Иъ 28 (72) Л.В.Вариченко, В.Б.Попович, Ю.А.Томны и А.А.Яковлев (53) 681 ° 325(088.8) (56) 1. Карцев И.А. Арифметика цифровых машин. М., "Наука", 1969, с. 438.

2. Авторское свидетельство СССР

У 600554, кл. С 06 F 7/52, 1978.

3. Патент США Р 403?093, кл. G 06 E 7/52, опублик. 1977.

4. Авторское свидетельство СССР

tt 900281, кл. 6 06 F 7/52, 1979.

5. Рабинер Л.P. Гоулд Б. Теория и применение цифровой обработки сигналов. M., "Мир", 1978, с. 574-575, рис. 8,32,8.33 (прототип). (54)(5?) МАТРИЧНОЕ МНОЖИТЕЛЬНОЕ

УСТРОЙСТВО, содержащее блок формирования частичных произведений, выполненный в виде матрицы и х и элементов И (tl - разрядность множимого и множителя) и блок суммирования частичньи произведений, выполненный в виде древовидной матрицы 4 х(1 разрядных сумматоров (t 1og, и количество ярусов в матрице, 0"

2 — количество tl -разряднйх сумматоров в (-м ярусе матрицы, где 1 = 1, ... 1 ), причем первые входы элементов И 1 -й строки матрицы соединены с входом 1 -ro разряда множителя устройства (-1 1, ..., n ), IA-й разряд множимого которого соединен с вторыми входами (1, tn )-х элементов И блока формирования частичных произведений (М =-1, ...,Il ), а в блоке суммирования частичных произведений выходы суммы (2 k * 1)-го и-разрядного сумматора.г -ro яруса матрицу (1, ..., < 1, 4=1,...

) соединены с входами перво(.1 - го слагаемого k -ro 11 -разрядного сумматора (t + 1)-ro яруса матрицы, входы второго слагаемого которого соединены с выходами суммы 2k-ro

tt-разрядного сумматора г -ro яруса. матрицы, входы переносов И -разрядных сумматоров первых ярусов матрицы соединены с шиной нулевого потенциала, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей эа счет обеспечения умножения A -разрядных двоичных чи \ сел по модулю 2 - 1, в него введены первый и второй tl -разрядные сумматоры, блок коррекции переносов, выполненный в виде древовидной матрицы .p x Y сумматоров (p 1 - 2 — количество ярусов в матрице, 2 — количество сумматоров

1 в р-м ярусе матрицы), поичем Р -й ярус сумматоров матрицы состоит иэ

Р -разрядных сумматоров и блок коррекции результата, содержащий 11 -входовый элемент И и 11 -разрядный сумматор, причем -й вход первого слагаемого -го 1 -разрядного сумматора первого яруса матрицы блока суммирования частичных произведений ((, = 1, ..., tl/2 для и четного, Р

1, ..., tl + 1 для h нечетного) соединен с выходом (1, rn )-го элемента И блока формирования частнчных произведений (y " 26 " ь

Э ° (j - !n + 1)Мойя, причем j — Ф +

0450

117 . + 1 " А, где А Nod n = и при кратном и, А Nodp и + А при АсО,AHоd„=A при и О), выход (j,Ф )-го элемента

И которого (Ф= 2Р, j -, (j — X +

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

П-разрядного сумматора 1 -го яруса матрицы которого соединен с входом переноса -ro h -разрядного сумматора (t + 1)-го яруса матрицы блока суммирования частичных произведений выходы переноса 2k-х П -разрядных сумматоров первого и второго ярусов матрицы которого соединены с соответствующими входами одноразрядных сумматоров первого яруса матрицы блоЮ ка коррекции переносов, входы переноса p -разрядных сумматоров -го

1 яруса матрицы которого (Р =, 3, 2) соединены с соответствующими выходами переноса 21-х и --раз-! рядных сумматоров Г -го яруса матрицы блока суммирования частичных произведений (Г = 3, ..., — 1), выходы суммы и выход переноса t; -го яруса матрицы которого соединены соответственно с входами первого слагаемого и входом переноса первого и h -разрядного сумматора, первые

2 выходы второго слагаемого и (1 — 1)-й вход второго слагаемого которого соединены соответственно с выходами суммы и переноса (1 — 2)разрядного сумматора (4 — - 2)-го яруса матрицы блока коррекции переносов, выходы суммы (2Z - 1)-го Р -разряд-! ного сумматора р--го яруса матрицы которого соединены с входами первоI го слагаемого X -ro (p + 1)-разрядб ного сумматора (p + 1)-го яруса матрицы, блока коррекции переносов (Х= 1, 2, ..., 2 ), входы второго слагаемого которого соедиI иены с выходами суммы 2.Z -го $ -раз1 рядного сумматора р -го яруса матрицы блока коррекции переносов, выходы суммы и выход переноса первого n -разрядного сумматора соединены соответственно с входами первого слагаемого и входом переноса второго П -разрядного сумматора, выходы суммы которого соединены с входа:m П -входового элемента И и входами первого слагаемого и -разрядного сумматора блока коррекции результата, выход И -входового элемента И соединен с входом переноса П -разрядного сумматора блока коррекции результата, выходы суммы которого соединены с выходами результата устройства, входы второго слагаемого разрядного сумматора блока коррекции результата, g --e входы второго слагаемого первого — разрядного сумматора (q =4 ..., П } и входы второго слагаемого второго и — разрядного сумматора соединены с шиной нулевого потенциала.

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

Известен матричный умножитель, содержащий матрицу элементов И и параллельные сумматоры (1) .

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

Однако низкое быстродействие, а также невозможность выполнения операции умножения чисел по модулю, отличному от 2", снижает функциональные воэможности известных устройств °

Известно устройство для умножения в поле Галуа, содержащее и — 1 модульных блоков умножения (3 .

Недостаток этого устройства заключается в отсутствии воэможности

1170450 производить умножение в полях, число соединены с входами первого слагаемо" элементов которых отлично от степе- го k --oro h -разрядного сумматора ни двойки, а также невозможности (I + 1)-го яруса матрицы, входы втоего использования в качестве обычного рого слагаемого которого соединены умножителя чисел. 5 с выходами суммы 2k ro и -разрядного

Известно устройство для умножения сумматора г -ro яруса матрицы, входы произвольных элементов полей Галуа переносов и -разрядных сумматоров пер"

GF(p"), состоящее иэ и модульных вых ярусов матрицы соединены с шиной блоков умножения, и блоков формиро- нулевого потенциала, введены первый вания частичных произведений и п 1О и второй и --разрядные сумматоры, блок блоков суммирования (4) . коррекции переносов, выполненный в

Недостатком известного устройства виде древовидной матрицы х 4 является то, что оно базируется на сумматоров (P = 1, ..., — 2 заданном устройстве умножения по мо- количество ярусов в матрице, Vp дулю простого числа 2 — количество сумматоров в

Наиболее близким по технической f-м ярусе матрицы), причем р -й сущности к изобретению является мат- ярус сумматоров матрицы состоит из ричный умножитель с древовидной -разрядных сумматоров, и блок корструктурой, содержащий схему форми- рекции результата, содержащий и -вхорования частичных произведений, . 2О довой элемент И и й- -разрядный сумпредставляющую собой матрицу из Е х П матор, причем j -й вхоД первого элементов И, схему формирования ре- слагаемого 5 -ro 11 -разрядного сумэультата, представляющую собой дере-. матора перчого яруса матрицы блока во сумматоров $5J суммирования частичных произведеДанное устройство характеризуют 2 ний (6 1, ..., й/2 для 11 четного, низкие функциональные возможности, .3 = 1, ..., и + 1 для и нечетного

I связанные с невозможностью умножения 2 по модулю, отличному от степени соединен с выходом (j, e )-го эледвойки. мента И блока формирования частичЦель изобретения - расширение 30 ных произведений (N = 28 - 1, функциональных возможностей за счет (1 — 1п + 1)Иода, причем j — е + обеспечения умножения по модулю М + 1 А, где Д Иод П Р при Д крат2 - 1. ном и, А Иосип и +,Д при Д с0, Поставленная цель достигается тем,;" Nod n A при А > О), выход (j, м ) -го что в матричное множительное устрой- З5 . элемента И которого (ю 28

J в ство, содержащее блок формирования (J - tn + Wdn) соединен с -м частичных произведений, выполненный,входом второго слагаемого 3 --ro !

)" в виде матрицы и х Tl элементов И разрядного сумматора первого яруса (n - разрядность множимого и множи- - матрицы блока суммирования частицтеля), и блок суммирования частичных 40 ных произведений, выход переноса .произведений, выполненный в виде (2 k 1)-ro q -разрядного сумматора древовидной матрицы т, 0 й-разряд" 7 ""го яруса матрицы которого соединых сумматоров (4 1од п - коли; нен с входом переноса k -ro П -pasчество ярусов в матрице, Ц, 2 - рядного сумматора (+ 1)-го яруса количество и-разрядных сумматоров 4$ матрицы блока суммирования частичв -м ярусе матрицы, где 1 1, ... ° ных произведений, выходы переноса

l), причем первые входы элементов И 2"-х Ь -разрядных сумматоров перво1-ой строки матрицы соединены с вхо- го и второго ярусов матрицы котородом -го разряда множителя устрой- го соединены с соответствующими вхоства (= 1, ...) n ), rn --й разряд S0 дами одноразрядных сумматоров первомножимого которого соединен с вто- го яруса матрицы блока коррекции рыми входами (,щ )-х элементов И переносов, входы переноса р «разряд блока формирования частичных произ- ных сумматоров p -ro яруса матриведений (rn = 1, ..., n ), а в блоке цы которого (p 2, ..., - 2) суммирования частичных произведений я соединены с соответствующими выходавыходы суммы (2 k — 1)-ro n -разрядно- ми переноса 2k-х и -разрядных суммаго сумматора г -ro яруса матрицы, торов t --го яруса матрицы блока сум(t 1, ..., 4 - 1, k 1, ...,2 ), мирования частичных произведений

1170450 (3, ..., 4 — -1),,выходы суммы и выход перекоса 4 --го яруса матрицы которого соединены соответственно с входами первого слагаемого и входом 5 переноса первого и --разрядного сумматора, первые 1 — 2 входы второго слагаемого и (4 — 1}-й вход второго слагаемого которого соединены соответственно с выходами суммы и переноса (1 - 2)-разрядного сумматора (1 - 2}-ro яруса матрицы блока коррекции переносов, выходы суммы (27,1)-ro р -разрядного сумматора

t -го яруса матрицы которого соединены с входами первого слагаемого

2-го ((+ 1)-разрядного сумматора (Р + 1)-го яруса матрицы блока крррекции переносов (х. = 1, ..., 2 ), Ч,. р входы второго слагаемого которого соединены с выходами суммы 21-го

1 1

-разрядного сумматора $ --го яруса матрицы блока коррекции переносов, выходы суммы и выход переноса перво25 го и -разрядного сумматора соединены соответственно с входами первого слагаемого и входом переноса второго и-разрядного сумматора, выходы суммы которого соединены с входами Ь -входового элемента И и входами первого слагаемого и -разрядного сумматора блока коррекции результата, выход й-входового элемента И соединен с входом переноса и -разрядного сумматора блока коррекции результата, 35 выходы суммы которого соединены с выходами результата устройства, входы второго слагаемого VI--разрядного сумматора блока коррекции результата, q -е входы второго слагаемого пер- 40 вого и -разрядного сумматора (Q = Y, ..., n ) и входы второго слагаемого второго и -разрядного сумматора соединены с шиной нулевого потенциала.

На фиг. 1 представлена структур- 45 ная схема матричного множительного устройства, на фиг. 2 — блок формиро" вания частичных произведений; на фиг. 3 — блок суммирования частичных произведений, на фиг. 4 — блок кор- 50 рекции переносов, на фиг. 5 — блок коррекции результата.

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

2 суммирования частичных произведений, блок 3 коррекции переносов, первый 4 и второй 5 и -разрядные сумматоры, блок 6 коррекции результата.

Блок 1 формирования частичных произведений (фиг. 2) содержит матрицу пх и элементов И 7.

Блок 2 суммирования частичных произведений (фиг. 3) содержит древовидную матрицу k x ) e-разрядных сумматоров 8.

Блок 3 коррекции переносов (фиг ° 4) содержит древовидную матрицу р х -разрядных сумматоров 9.

Блок б коррекции результата (фиг. 5) содержит и -входовый эле мент И 10 и о -разрядный сумматор 11.

Матричное множительное устройство работает следующим образом.

На входы матричного множительного устройства поступают и -разрядное множимое A = 0 ... а, а, и и -разрядный множитель В = Ь„ ... Ъ b< °

Блок 1 формирования частичных произведений образует попарные произведения ф„, ь (1, 2,..., б

2, . ° °, и ) °

Произведения разрядов множимого на младший разряд множителя Qщ, Ф 1у образуют слово частичных произведений первой ступени f произведения разрядов множимого на второй разряд множителя y b, образуют слово частичных произведений второй ступени,, ..., произведения разрядов множимого на и -й (старший) разряд множителя б Ъ „ образуют слово частичных произведений и -й ступени

Слово f сдвинуто относительно слова 11 на один разряд влево, слово f сдвинуто относительно слова на два разряда влево, ..., слово сдвинуто относительно слова f>

Ц на и — 1 разрядов влево.

Выходы элементов И блока 1 формирования частичных произведений соединены с входами слагаемых сумматоров первого яруса матрицы блока 2 суммирования частичных произведений, и

Так как 2 = 1 по рассматриваемому модулю M = 2" — 1, то умножение на

t1l степень двойки 2 равносильно циклическому сдвигу влево на m разрядов и-разрядной двоичной записи множимого, т. е. линейный сдвиг слов заменяется циклическим.

Слово, полученное в результате циклического сдвига слова частичных

450

7 1170 произведений 1-й ступени на 1 разрядов влево, обозначается через

@ (1 - 1, 2, ...,!! ).

Например, 3 2 =On 2 ау,., Ь 2, о„.,1,, ...,а, Ъ,,ц „1»,. Блок 2 суммирования частичных произведений осуществляет сложение слов g . Слова о поступают на входы первого и р 1 10 второго слагаемых сумматоров 81ц.

Если и 2, то на оставшиеся входы слагаемых сумматоров 8 первого яруса матрицы подаются значения сигналов, соответствующие логическому "0" °

Такие же сигналы подаются и на входы переносов всех сумматоров первого яруса дерева.

Результаты попарного сложения слов,, ..., о (без участия пер а ° ° р реносов) поступают на входы слагаемых сумматоров второго яруса. Результаты попарного сложения укаэанных результатов (беэ учета переносов) поступают на входы слагаемых сумматоров третьего яруса и т. д.

Так как 2 = 1 по рассматриваемоп о му модулю N - =2 — 1, то переносы из и -го в (< + 1)-й разряд имеют вес, равный единице. Поэтому выходы переносов (2 4 — 1)-х сумматоров 8 30 г-го (= 1, 2, ..., 1 - 1) яруса (k = 1, 2, ..., 2 " ) соединены с входом переноса 1 -ro сумматора 8 (у. + 1)-го яруса матрицы. Остальные переносы сумматоров 8 поступают в блок 3 коррекции переносов.

Блок 3 коррекции переносов образует корректирующие слова путем сложения поступающих переносов. Переносы из сумматоров 8 первого и 40 второго ярусов матрицы блока 2 с четными номерами передаются на одноразрядные сумматоры 9 первого яруса матрицы блока 3 коррекции переносов, причем на один сумматор поступают три переноса. Полученные в результате сложения двухразрядные слова передаются на входы слагаемых сумматоров второго яруса матрицы блока 3 коррекции переносов. На входы переносов сумматоров 9 второго яруса матрицы блока 3 коррекции переносов поступают переносы из третьего яруса матрицы блока 2. Полученные в результате попарного сложения двухраз- у рядных слов трехразрядные слова поступают на входы слагаемых сумматоров 9 третьего яруса матрицы блока.3 коррекции переносов. На входы переносов сумматоров 9 третьего яруса матрицы блока 3 коррекции переносов передаются переносы из четвертого яруса матрицы блока 2 и т. д. На выходах сумматора 9 последнего яруса блока 2 коррекции переносов образуется (1 — 1)-разрядное слово коррекции, состоящее иэ (1 — 2)-разрядного слова суммы 5 " и переноса р обозначающего (t — 1)-й разряд слова.

На выходах сумматора 8 последнего яруса матрицы блока 2 получается h разрядное слово суммы g<) и перенос имеющий вес, равный единице.

g<)

Результат сложения слова б корректирующего слова и переноса ., полу 1) чается на выходе первого П -раэрядного сумматора 4.

Если в результате сложения образуется перенос, то его необходимо прибавить к младшему разряду полученного слова сумм. Эту функцию выполняет сумматор 5. В результате получается произведение АВ по модуl1 лю М 2 — 1, представленное и -разрядным двоичным числом.

Матричное множительное устройство имеет два представления нуля:

00...,.0 н 11.... 1, тяк как слоС разрядов Л разрядов во 11...1 сравнима с нулем яо маЛ разрядов дулю М = 2 — 1.

Ь

Поэтому окончательный результат должен корректироваться, для чего служит блок 6 коррекции результата.

Результат умножения поступает на !

1-входовой элемент И 10 и одновременно на 0 -разрядный сумматор 11.

При равенстве всех разрядов единице на выходе элемента И 1О появляется единица, которая поступает на входы переноса сумматора 11.

В результате на выходах сумматора 11 устанавливаются нулевые значения, т. е. нуль получает единственное представление.

При использовании матричного множительного устройства для обычного умножения значения сомножителей должны быть такими, чтобы A Bc 2" -1, где A и  — положительные двоичные числа. В этом случае результат уми ножения по модулю 2 — 1 не отличается от результата обычного умножения.

Таким образом, введенные связи позволяют расширить функциональные

И 70450

Фиг. r

° ° °

° ° °

01gr

Опт

use аггг @<8

° ° ° ° ° ° ° ° ° ° ° ° ° °

° ° °

0п п возмоаности матричного множительного устройства: мошно осуществлять обычное умножение и умножение по модулюИ2"-1 °

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

Кроме того, устройство мотет применяться в системах кодирования, принцип действия которых базируется на теории полей Галуа.! (7О450

1170450

Sy

Составитель Е.Захаренко

Редактор М.Келемеш Техред О.Ващишина Корректор В.Гирняк

Заказ 4705/46 Тиран 710 Подписное

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

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

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