Матричное множительное устройство Советский патент 1985 года по МПК G06F7/49 

+ 1 А, где А Mod п « при кратном П,А Modh П+А при ,AModn A при А 7 0), выход (1,1 )-го элемента И которого (1П 2, (i 1)Modh) соединен с ) -м входом

J

второго слагаемого т-- -го п -разрядного сумматора первого яруса матрицы блока суммирования частичных произведений, выход переноса (21 - 1)-г И-разрядного сумматора -го яруса матрицы которого соединен с входом переноса -го h -разрядного сумматора (р + 1)-го яруса-матрицы блока суммирования частичных произведений выходы переноса 2k-х h -разрядных сумматоров первого и второго ярусов матрицы которого соединены с соответствукяцими входами одноразрядных сумматоров первого яруса матрицы блока коррекции переносов, входы переноса р -разрядных сумматоров р -го яруса матрицы которого ( р 2, 3, i.,, t - 2) соединены с соответствующими выходами переноса 2k-X п -разрядных сумматоров г -го яруса матрицы блока суммирования частичных произведений (р 3, ..., i -1), выходы суммы и выход переноса i -го яруса матрицы которого соединены соответственно с входами первого слагаемого и входом переноса первого и h -разрядного сумматора, первые t - 2 выходы второго слагаемого и (i - 1)-й вход второго слагаемого которого соединены соответственно с выходами суммы и переноса (i- 2)разрядного сумматора (-t - 2)-го яруса матрицы блока коррекции переносов выходы суммы (22 - 1)-го р -разрядного сумматора р-го яруса матрицы которого соединены с входами первого слагаемого Т, -го (р + 1)-разрядного сумматора ( Р + 1)-го яруса матрицы,блока коррекции переносов (г 1, 2, ..., ), входы второго слагаемого которого соединены с выходами суммы 2 -го р -разрядного сумматора р -го яруса матрицы блока коррекции переносов, выходы суммы и выход переноса первого и -разрядного сумматора соединены соответственно с входами первого слагаемого и входом переноса второго Г1 -разрядного сумматора, выходы суммы которого соединены с входа:№( п -входового элемента И и входами первого слагаемого р -разрядного сумматора блока коррекции результата, выход h -входового элемента И соединен с входом переноса п -разрядного сумматора блока коррекции результата, выходы суммы которого соединены с выходами результата устройства, входы второго слагаемого п разрядного сумматора блока коррекции результата, CJ -е входы второго слагаемого первого h разрядного сумматора (J , ... , П ) и входы второго слагаемого второго П - разрядного сумматора соединены с шиной нулевого потенциала.

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

1

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

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

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

сдвига,регистр задержки, регистры слов первого и второго сомножителя, две матрицы умножения, сумматоры и блок управления .2J. Однако низкое быстродействие, а также невозможность вьшолнения операции умножения чисел по модулю, отличному от 2, снижает функциональные возможности известных устройств. Известно устройство дпя умножения в поле Галуа, содержащее П - 1 модульных блоков умножения C3J .

Недостаток этого устройства заключается в отсутствии возможности производить умножение в полях, числ элементов которых отлично от степени двойки, а также невозможности его использования в качестве обычно умножителя чисел. Известно устройство для умножени .произвольных элементов полей Галуа GF{p), состоящее из п модульных блоков умножения, и блоков формирования частичных произведений и п блоков суммирования 4. Недостатком известного устройств является то, что оно базируется на заданном устройстве умножения по мо дулю простого числа р . Наиболее близким по технической сущности к изобретению является мат ричный умножитель с древовидной структурой, содержащий схему формирования частичных произведений, представляющую собой матрицу из fh х элементов И, схему -формирования результата, представляющую собой дере во сумматоров И. Данное устройство характеризуют низкие функциональные возможности, связанные с невозможностью умножени по модулю, отличному от степени двойки. Цель изобретения - расширение функциональных возможностей за счет обеспечения умножения по модулю М 2 - 1. Поставленная цель достигается те что в матричное множительное устрой ство, содержащее блок формирования частичньк произведений, выполненный в виде матрицы п х П элементов И (П - разрядность множимого и множителя), и блок суммирования частичных произведений, выполненный в виде древовидной матрицы {, i и-разрядных сумматоров (t logj п количество ярусов в матрице, (i( количество и-разр-ядных сумматоров в i-M ярусе матрицы, где i 1, ... i), причем первые входы элементов И j-ой строки матрицы соединены с входом j -го разряда множителя устройства ( 1п ),т-й разряд множимого которого соединен с вторыми входами (f,m)-х элементов И блока формирования частичных произведений (ип 1, ...,и), а в блоке суммирования частичных произведений выходы суммы (2k- 1)-го п -разрядн го сумматора h -го яруса матрицьг (Г 1i - 1, .k 1Г соединены с входами первого слагаемого k -ого п -разрядного сумматора (п + 1)-го яруса матрицы, входы второго слагаемого которого соединены с выходами суммы 2k-го ti -разрядного сумматора г -го яруса матрицы, входы переносов п -разрядных сумматоров первых ярусов матриць соединены с шиной нулевого потенциала, введены первый и второй п-разрядные сумматоры, блок Коррекции переносов, вьтолненный в i виде древовидной матрицы р х i сумматоров (,...,i-2 количество ярусов в матрице, Vn ° 2 Р - количество сумматоров в Р-м ярусе матрицы), причем р -и ярус сумматоров матрицы состоит из р-разрядных сумматоров, и блок коррекции результата, содержащий п -входовой элемент И и ft--разрядный сумматор, причем j-й вход первого слагаемого 6 -го п -разрядного сумматора перчого яруса матрицы блока суммирования частичных произведений ( Е 1Г)/2 для Г) четного, .8 1, ..., п + 1 для п нечетного соединен с выходом (|, m )-го элемента И блока формирования частичных произведений (,je ( j - W 1)Modh, причем - rn. 1 А, где А Mod И « П при А кратном rt , А Modn и +Л при А О, lAModn A ), выход (j,)-ro элемента И круторого (/ 26, j (j-m l)iWbdn) соединен с j -м входом второго слагаемого И -го п разрядного сумматора первого яруса матрицы блока суммирования частичных произведений, выход переноса (2k « 1)-го о -разрядного сумматора р-го яруса матрицы которого соединен с входом переноса k -го Р -разрядного сумматора ( Р + 1)-го яруса матрицы блока суммирования частичных .произведений, выходы переноса 2k-X о -разрядных сумматоров первого и второго ярусов матрицы которого соединены с соответствуюощми входами одноразрядных сумматоров первого яруса матрицы блока коррекции переносов, входы переноса р -разряд ных .сумматоров р-го яруса матрицы которого Ср 2, ..., i - 2) соединены с соответствуклдими выходами переноса 2k-х п -разрядных сумматоров р-го яруса матрицы блока суммирования частичных произведений

(г ° 3, , t - 1), выходы суммы и выход перекоса i -го яруса матрицы которого соединены соответственно с входами первого слагаемого и входом переноса первого п -разрядного сумматора, первые -1-2 входы второго слагаемого и (i - 1)-й вход второго слагаемого которого соединены соответственно с выходами суммы и переноса (i - 2)-разрядного сумматора ( 4. - 2)-го яруса матрицы блока коррекции переносов, выходы суммы (2 . 1)-го р -разрядного сумматора р -го яруса матрицы которого соединены с входами первого слагаемого 2-го (р+ 1)-разрядного сумматора ( р + 1)-го яруса матрицы блока к рврекции переносов (z - 1, ..., 2 ) входы второго слагаемого которого соединены с выходами суммы р -разрядного сумматора р -го яруса матрищ; блока коррекции переносов, выходы суммы и выход переноса первого п -разрядного сумматора соединены соответственно с входами первого слагаемого и входом переноса второго h-разрядного сумматора, выходы суммы которого соединены с входами Ь, -входового элемента И и входами первого слагаемого Я-разрядного сумматора блока коррекции результата, выход -входового элемента И соединен с входом переноса и-разрядного сумматора блока коррекции результата, выходы суммы которого соединены с выходами результата устройства, входы второго слагаемого И-разрядного сумматора блока коррекции результата, Q е входы второго слагаемого первого к -разрядного сумматора ( Т , ..., и ) и входы второго слагаемого второго п -разрядного сумматора соединены с шиной нулевого потенциала.

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

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

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

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

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

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

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

На входы матричного множительного устройства поступают п -разрядное множимое .,,a20(i и п -разрядный множитель В Ь ... Ь 2 Ь. Блок 1 формирования частичных произведений образует попарные произведения л„, ь; (j 1, 2,,.., п , m 1,

lis 4

2, .,,, п ).

Произведения разрядов множимого на младший разряд множителя

образуют слово частичных произведений первой ступени ) , произведения разрядов множимого на второй разряд множителя Си b 2 образуют слово частичных произведений второй ступени ij, ,.,, произведения разрядов множимого на п-и (старший) разряд множителя С(Ь„ образуют слово частичных гфоизведений п-и ступени 1 , Слово i 2 сдвинуто относительно

слова 1) на один разряд влево, слово { 3 сдвинуто относительно слова i на два разряда влево, ,.,, слово i сдвинуто относительно слова f ( на h - 1 разрядов влево.

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

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

Слово, полученное в результате циклического сдвига слова частичных 7 произведений 4-и ступени на 4 разрядов влево, обозначается через gj( i 1, 2, ...,п ). Например, i nb.j,Q. Ь j, ... Ojb,,a,bj, тогда % а„., Ъ, а„.Ь,, ...,а, b,j,qn Ь-. Блок 2 суммирования частичных произведений осуществляет сложение слов g . Сло ва о поступают на входы первого и &1о второго слагаемых сумматоров о,ц. Если п 2, то на оставшиеся входы слагаемых сумматоров 8 первого ярус матрицы подаются значения сигналов, соответствующие логическому О. Такие же сигналы подаются и на вход переносов всех сумматоров первого яруса дерева. Результаты попарного сложения слов р , (без участия переносов) поступают на входы слагаемых сумматоров второго яруса. Результаты попарного сложения указанных результатов (без учета переносов) поступают на входы слагаемых сумматоров третьего яруса и т. д. Так как 2 1 по рассматриваемо му модулю М 2 - 1, то переносы из п -го в (rt + 1)-й разряд имеют вес, ра.вный единице. Поэтому выходы переносов (2k - 1)-х сумматоров 8 г-го ( 1, 2, ..., i - 1) яруса ( k 1, 2, ..., ) соединены с входом переноса k -го сумматора 8 (г + 1)-го яруса матрицы. Остальные переносы сумматоров 8 поступают в блок 3 коррекции переносов. Блок 3 коррекции переносов образует корректирующие слова путем сложения поступающих переносов. Перенс сы из сумматоров 8 первого и второго ярусов матрицы блока 2 с четными номерами передаются на одно разрядные сумматоры 9 первого яруса матрицы блока 3 коррекции переносов причем на один сумматор поступают три переноса. Полученные в результа те сложения двухразрядные слова передаются на входы слагаемых суммато ров второго яруса матрицы блока 3 коррекции переносов. На входы переносов сумматоров 9 второго яруса ма рицы блока 3 коррекции переносов поступают переносы из третьего ярус матрицы блока 2. Полученные в результате попарного сложения двухраз рядных слов трехразрядные слова пос тупают на входы слагаемых сумматоров 9 третьего яруса матрицы блока 508 3 коррекции переносов. На входы переносов сумматоров 9 третьего яруса матрицы блока 3 коррекции переносов, передаются переносы из четвертого яруса матрицы блока 2 и т. д. На выходах сумматора 9 последнего яруса блока 2 коррекции переносов образуется (t- 1)-разрядное слово коррекции, состоящее из (i - 2)-разрядного слова суммы 5 и переноса р , обозначающего (i - 1)-й разряд слова. На выходах сумматора 8 последнего яруса матрицы блока 2 получается h разрядное слово суммы и перенос р ., имеющий вес, равный единице. Результат сложения слова , корректирующего слова и переноса jr ; , получается на выходе первого П -разрядного сумматора 4. Если в результате сложения образуется перенос, то его необходимо прибавить к младшему разряду полученного слова сумм. Эту функцию выполняет сумматор 5. В результате получается произведение А В по модулю М 2 - 1, представленное п -разрядным двоичным числом. Матричное множительное устройство имеет два представления нуля: 00.....0 и 11....1, так как слоГ разрядов П разрядов во 11... 1 сравнимо с нулем по моУ) разрядов дулю М 2 - 1. Поэтому окончательньи результат должен корректироваться, для чего служит блок 6 коррекции результата. Результат умножения поступает на П-входовой элемент И 10 и одновременно на п -разрядный сумматор 11. При равенстве всех разрядов единице на выходе элемента И 10 появляется единица, которая поступает на входы переноса сумматора 11. В результате на выходах сумматора 11 устанавливаются нулевые значения, т. е. нуль получает единственное представление. При использовании матричного множительного устройства для обычного умножения значения сомножителей должны быть такими, чтобы А- -1, где А и В - положительные двоичные числа. В зтом случае результат умножения по модулю 2 - 1 не отличается от результата обычного умножения. Таким образом, введенные связи позволяют расширить функциональные

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

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

фиг.2

зовать алгоритмы, определенные над конечным кольцом, а также классические алгоритмы.

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

an6j

9,

д

S

FL ;ш

.1

Я,

у Га ITJ SZE

5 1

-7,/

пЬигЗ

Щ-2 JR

dn-s

- iZf,Slti

-;

|,i/2

VrC

iLi

-.4

2 ;

«; 2 Я/7УС

rr;

5

ft

лТ/

(t)

i«w

et-7,P

Ib;,/t-r;

(ti)ttpyc

«r7 ярус

1риг.З 2 Ярус Г ярус фи.4/ (t-2)flpyc (t3)pyc

Si

10

5/1

n раз 4

c

1

C ол

Фиг. 5