Устройство для умножения элементов поля галуа gf(2 @ ) при образующем полиноме f(х)=х @ +х @ +х @ +х @ +1

Устройство для умножения элементов поля галуа gf(2 @ ) при образующем полиноме f(х)=х @ +х @ +х @ +х @ +1

Иллюстрации

Показать все

Реферат

 

Изобретение относится к специализированным устройствам вычислительной техники и может использоваться в декодирующих устройствах, работающих с полиномами над конечным полем ), образованным неприводимым полиномом F(x)-x8+x4+ + х +х +1, например в декодерах систем цифровых компакт-дисков. Цель изобретения - сокращение аппаратурных затрат за счет уменьшения количества многовходовых сумматоров путем объединения их в блок формирования результата и блок формирования частичных произведений, Устройство содержит первый 1 и второй 2 регистры, матрицу элементов И 3, блок 4 формирования частичных произведений и блок 5 формирования результата. 5 ил.

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

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

РЕСПУБЛИК (! 9) (1() (5!)5 G 06 F 7/49

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4751974/24 (22) 23.10.89 (46) 29,02.92.Бюл, t4 8

: (71) Научно-исследовательский институт бытовой радиоэлектронной аппаратуры (72) И.И.Ковалив и А,Ф.Теслюк (53) 681.325 (088.8) (56) Авторское свидетельство СССР

М 1013950, кл. G 06 F 7/52, 1981.

Bartee Th. С. Schneider D.I CompUtation

wIth Finite Г!еЫз —. Information and Control,, voI. 6, М 2, 1963, fig. 3, р. 85, (54) УСТРОЙСТВО ЛЛЯ УМНОЖЕНИЯ ЭЛЕ-.

МЕНТОВ ПОЛЯ ГАЛУА GF(2 ) ПРИ ОБРАЗУЮЩЕМ flOJINHOME F(x)=x"+õ +х"+х +1 (57) Изобретение относится к специализиИзобретение относится к специалиэи )ованным устройствам вычислительной техники и может использоваться в декодирующих устройствах, работающих с полиномами над конечным полем GF(2 ), образованным неприводимым полиномом

Р(х)=х+х +х+х+1, и с примитивным элементом, равным х, где х — фиктивная переменная, использующаяся для записи полиномов, например в декодерах системцифровых компакт-дисков.

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

Недостатком известного устройства является низкое быстродействие, если первый полином сомножителей больше полинома, рованным устройствам вычислительной техники и может использоваться в декодирующих устройствах, работающих с полиномами над конечным полем GF(2 ), образован- ным неприводимым полиномом F(x)=x +х +

+ х +х +1, например в декодерах систем

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

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

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

Известно устройство деление полиномов над конечными полями G F(2 ), содержащее два блока логарифмирования, блок вычитания и блок антилогарифмирования.

1716504

При замене блока вычитания блоком суммирования устройство деления преобразуется в устройство умножения двух полиномов над конечными полями GF(2 ).

Недостатком такого устройства является большая сложность и большие аппаратурные затраты при m >4.

Известно устройство для умножения элементов конечных полей GF(2 ), содержащее два m-разрядных регистра, m групп по

Al двухвходовых элементов И каждая, m mвходовых сумматоров по модулю два и m — 1 матричных преобразователей, каждый из которых состоит из двухвходовых сумматоров по модулю два, число которых равно числу ненулевых коэффициентов при степенях, умноженному на m — 1.

Недостатком известного устройства яв, ляется большие аппаратурные затраты, Так если поле GF(28) образовано неприводимым . полиномом F(x)=x +x +x +х +1, устройство содержит 157 элементарных функциональных элементов: 77 двухвходовых сумматоров по модулю два, 64 двухвходовых элемента И и 16 триггеров.

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

Цель изобретения — сокращение аппаратурных затрат.

С этой целью в устройство для умножения элементов поля Галуа GF(2 ) при образующем полиноме F(x)=x +х +х +х +1, содержащее два и-разрядных регистра (п=8), матрицу (n x п) элементов И, блок формирования частичных произведений, состоящий из тринадцати сумматоров по модулю два, и блок формирования результата, состоящий из пятнадцати сумматоров по модулю два, причем информационные входы первого и второго и-разрядных регистров соединены соответственно с входами первого и второго сомножителей устройства, первый вход i-го элемента И в каждом столбце матрицы (i 1, ..., 8. — номер строки матрицы), соединен с выходом i-ro разряда и-разрядного регистра второго операнда, 5

55 второй вход l-ro элемента И в каждой строке матрицы соединен (j-1, ..., 8, J — номер столбца матрицы) соответственно с выходом Кm разряда и-разрядного регистра первого операнда (К=Я, „., 1), выходы(1,1)-ro и(8,8)-го элементов И матрицы соединены соответственно с первым и пятнадцатым входами блока формирования результата, выходы элементов И матрицы, кроме (1,1)-го и (8,8)го элементов И, соединены со входами соответствующих весов сумматоров по модулю два с первого по тринадцатый блока формирования частичных. произведений, выходы которых соединены соответственно . со входами со второго по четырнадцатый блока формирования результата, выходы с первого по восьмой которого соединены с выходами результата устройства, при этом в блоке формирования результата первые входы сумматоров по модулю два с первого по восьмой соединены соответственно с входами с первого по восьмой блока, девятый вход которого соединен с первыми входами девятого и десятого сумматоров по модулю два, десятый вход блока соединен с первыми входами одиннадцатого и двенадцатого и вторым входом второго сумматоров по модулю два, одиннадцатый вход блока соединен со вторыми входами седьмого и одиннадцатого и первым входом тринадцатого сумматоров по модулю два, двенадцатый вход блока соединен с первым входом четырнадцатого и вторыми входами шестнадцатого и двенадцатого сумматоров по модулю два, тринадцатый вход блока соединен со вторыми входами девятого и четырнадцатого сумматоров по модулю два, четырнадцатый вход блока соединен с первым входом пятнадцатого и вторыми входами восьмого и тринадцатого сумматоров по модулю два, пятнадцатый вход блока соединен со вторыми входами десятого и пятнадцатого сумматоров по модулю два, выход девятого сумматора по модулю два соединен со вторыми входами первого, третьего и четвертого сумматоров по модулю два, выход десятого сумматора по модулю два соединен со вторым входом пятого сумматора по модулю два, третий вход которого соединеН с третьим входом шестого и выходом одиннадцатого сумматоров по модулю два, выходы двенадцатого и тринадцатого сумматоров по модулю два соединены соответственно с третьими входами четвертого и третьего сумматоров по модулю два, вы-. ход четырнадцатого сумматора по модулю два соединен с третьими входами седьмого и BocbMoto сумматоров по модулю два, выход пятнадцатого сумматора по модулю два соединен с третьими входами Aepaor;

1716504 и второго сумматоров по модулю два, выходы сумматоров по модулю два с первого по восьмой соединены соответственно с выходами с первого по восьмой блока, или в блоке формирования результата первые входы сумматоров по модулю два с первого по восьмой соединены соответственно со входами с первого по восьмой блока, девятый вход которого соединен с первыми вхо-. дами сумматоров по модулю два с девятого

10 по одиннадцатый, десятый вход блока соединен с первым входом двенадцатого и вторыми входами второго и одиннадцатого сумматоров по модулю два, одиннадцатый вход блока соединен со вторыми входами седьмого, десятого и двенадцатого сумма15 торов по модулю два, двенадцатый вход блока соединен с первым входом тринадцатого и вторым входом шестого сумматоров по модулю два, тринадцатый вход блока со-. 20 единен с первым входом четырнадцатого и вторым входом тринадцатого сумматоров по модулю два, четырнадцатый вход блока соединен со вторыми входами восьмого и четырнадцатого и первым входом пятнадцатого сумматоров по модулю два, пятнадцатый вход блока соединен со вторыми входами девятаго и пятнадцатого сумматоров по модулю два. выход девятого сумматора по модулю два соединен со вторыми. 30 входами первого и пятого сумматоров по модулю два, выходы десятого и.одиннадцатого сумматоров по модулю два соединейы со вторыми входами третьего и четвертого

40 единен с третьими входами четвертого, седьмого и восьмого сумматоров по модулю два, выход четырнадцатого сумматора по модулю два соединен с третьими входами первого и третьего сумматоров по модулю два, выход пятнадцатого сумматора по мо- 45 дулю два соединен с третьим входом второго сумматора по модулю два, выходы сумматоров с первого по восьмой соединены с выходами с первого по восьмой блока. соответственно, или в блоке формирования 50 результата первые входы сумматоров по модулю два с первого по восьмой соединены. соответственно со входами с первого по восьмой блока, девятый вход которого соединен с первыми входами девятого, десято- 5 го и одиннадцатого сумматоров по модулю два, десятый вход блока соединен со вторыми входами второго и одиннадцатого сумматоров по модулю два, одиннадцатый вход блока соединен с первым входом двенадцасумматоров по модулю два соответственно, 35 выход двенадцатого сумматора по модулю два соединен с третьими входами пятого и шестого сумматоров по модулю два.. выход тринадцатого сумматора по модулю два сор1 = aaBa 1г

p2 = а139а14

j4 = адаа10 р4 =а11йа1г

j4 = а10®а13

ps = 46O+a»

p7 = авйа14 (2 ) того и вторыми входами седьмого и десятого сумматоров по модулю два, двенадцатый вход блока соединен с первым входом тринадцатого и вторыми входами шестого, восьмого и двенадцатого сумматоров по мо. дулю два, тринадцатый вход блока соединен со вторым входом тринадцатого и первым входом четырнадцатого сумматоров по модулю два, четырнадцатый вход блока соединен со вторым входом четырнадцатого и первым входом пятнадцатого сумматоров по модулю два, пятнадцатый вход блока соединен со вторыми. входами девятого и пятнадцатого сумматоров по модулю два, выход девятого сумматора по модулю два соединен со вторыми входами первого и пятого сумматоров по модулю два, выходы десятого и одиннадцатого сумматоров по модулю два соединены соответственно. со вторыми входами третьего и четвертого сумматоров по модулю два, выход двенадцатого сумматора по модулю два соединен с третьими входами пятого и шестого сумматоров по модулю два, выход тринадцатого сумматора по модулю два соединен с третьими входами четвертого и седьмого сумматоров по модулю два, выход четырнадцатого сумматора по модулю два соединен с третьими входами первого, третьего и восьмого сумматоров по модулю два, выход пятнадцатого сумматора по модулю два соединен с третьим входом второго сумматора по модулю два, выходы сумматоров по модулю два с. первого по восьмой соединены соответственно с выходами с первого по восьмой блока.

Вычисление результата умножения элементов поля Галуа GF(2 при образующем полнноие Е(х х +x +x +x +1 реализуется не

8 основе следующих соотношений.

Первый вариант

$ ьв %®,%

$1= а10+/ЬЩ

$г= жВР1О+/Ъ

$3= а3®/1@(4

$4= а4®фЗО+ 87

$в= аЪО+а1 1&фз

$6= аб®а1 ОО+ф4

$7 а79а13Юф4 (1 i где

1716504

Второй вариант

So-- ао9)91®Д

S 1; — a1 O+ ag O+p7

S2= агЮР29Р5

$з= @9рз®Р6

$4= а4®ф1®Р4

$5= а59а»9р4

S6= а69а10©ф3

S7= а7®а139/Ъ

10 где р1 =а69а14

Д =а1гяа13

jb =а11О+а12 р4 =а99а10

Ps = авО+а10

Р6 =аеаа9

p7 = а13Юа14 (2ii) 15

Третий вариант

So= аоО+/49ф4

S1= a19ag9pg

S2= a29p4@p6

$3= аз®фЗО+ф7

S4= а4®р19р2

S5= a5Ва11 Ур2

S6= а6 Ва10 ЮфЗ

$7= а7 9а11 6Р4 где

i-I1 = Цв @а14

Д =а99а10

p3 = а11фа12 р4 =а12 Жа13

p5 = a13O+a14

Р6 = as ga10

P7 =as ®ag (2 ) Причем а = Р Bi- (3), где а - черт- 40

1=0 ные произведения сомножителей, Ao, .„, А7 — разряды кода первого сомножителя, Bo, ..., В7 — разряды кода второго сомножителя, Знак суммы определяет функцию сло- 45 жения по модулю два. Значения As, ..., А14, Bs, ..., В14 равны нулю и в формировании результатов частных произведений участия не принимают.

Таким образом, для формирования частных произведений i=-0, ..., 14. Для i>14 частные произведения будут равны нулю.

Например: a15= ), Ai В15-1=А0В1ЖА1В149 55

j =о

О+А28130+ АЗВ12® А4В116А5В10 O+ А6В9 0+

Q+A7Bs 9 А6В7 Я AgB6 0+ А10В5 О+А11ВЮ

ЯА12В39А13В29 A14B19А15В0. Представляя

As, ..., А15=0, Bs, ..., B15=0, получаем а15=0.

Анализ выражения (3) показывает, что для вычисления значений частных произведений а0, „., а14 потребуется 64 двухвходовых элемента И и 49 двухвходовых сумматоров по модулю два.Для. вычисления значений ф1, ..., ф7 согласно выражения (2) требуется 7 двухвходовых сумматоров по модулю два, а для. вычисления. синдромов So..., S7 согласно выражению (1) требуется 16 двухвходовых сумматоров по модулю два.

Таким образом, для вычисления разрядов кода результата So, ..., S7 общее кОличество элементов И равно 64, а двухвходовых сумматоров по модулю два — 72.

При введенйи в указанной связи с остальными элементами схемы в предлагаемое устройство.для умножения элементов поля Галуа GF(2 ) при образующем полиноме F(x)=x +х +х +х +1 указанные блоки про4 3. 2 являют новые свойства, приводящие к упрощению устройства.

На фиг. 1 представлена структурная схема устройства для i множения элементов ROля Галуа GF(2 ) при порождающем полиноме F(x)=x +x +x +х +1; на фиг. 2— функциональная схема формирования частных произведений; на фиг. 3 — функциональная схема блока формирования результата; на фиг. 4 и 5 — альтернативные решения . блока формирования результата, Устройство для умножения элементов поля Галуа GF(2 ) при образующем полиноме F(x)=x +x +х +х +1 содержит первый 1 и второй 2 регистры, группы 3.1, ..., 3.8 элементов И 3, блок 4 формирования частных произведений, блок 5 формирования результата, входы 6 и 7 устройства являются входами первого и второго сомножителей, выход 8 устройства, причем входы первого

1 и второго 2 регистров подключены.соответственно к входам 6 и 7 устройства, первые входы элементов И 3 каждой:группы 3,1, ..., 3.8;объединены и подключены к соответствующим выходам первого 1 регистра, каждый выход второго 2 регистра подключен к соответствующим flo порядку обьединенным вторым входам группы ЗЛ, ..., 3.8 элементов И 3, входы блока 4 формирования частных произведений согласно нумерации подключены к выходам соответствующих элементов И 3 таким образом, что номер состоит из двух цифр, первая из которых указывает номер выхода первого регистра, а вторая цифра — номер выхода второго регистра, входящих в коньюнкцию, выходы блока 4 формирования частных произведений соединены с соответствующими входами блока 5 формирования результата, 1716504

25

35

50 выходы которого подключены к выходу 8 устройства.

-Блок 4 формирования частных произведений содержит тринадцать сумматоров 921 по модулю дм, входы с номерами от 0,0 до 7;7 пятнадцать выходов 22 — 36, причем входы блока 4 с номерами 0,0 и 7,7 подклЮчены соответственно к первому 22 и пятнадцатому 36 выходам блока 4, входы сумматоров 9-21 по модулю два соединены со входами блока 4 таким образом, что сумма цифр номера блока 4 соответствует номеру сумматора 9-21, к которому данный вход блока 4 подключен, выходы 6умматоров с первого 9 по тринадцатый 21.coединены соответственно со второго 2Я по четырнадцатый 35 выходами блока 4.

Блок 5 формирования результата содержит пятнадцать сумматоров 37 — 51 по модулю два, пятнадцать входов 52 — 66 блока 5 и восемь выходов 67-74 блока 5, причем входы блока 5 с первого 52 по восьмой 59 подключены соответственно к первым входам

- сумматоров с восьмого 44 nо пятнадцатый

51, девятый вход 60 блока 5 совместно с первым входом седьмого сумматора 43 соединен с первым входом первого сумматора

37, выход которого совместно со вторыми входами десятого 46 и одиннадцатого 47 сумматоров подключены ко второму входу восьмого 44 сумматора, третий вход котарого совместно с третьим входом девятого сумматора 45 соединен с выходом второго сумматора 38, первый вход которого совместно.с первым входом пятого 41 и вторым входом пятнадцатого 51 сумматоров подключен к четырнадцатому 65 входу блока 5; тринадцатый 64 вход которого совместно со вторым входом первого 37 сумматора соединен с первым входом четвертого 40 сумматора, выход которого совместно с третьим входом пятнадцатого 51 сумматора подключен к третьему входу четырнадцатого 50 сумматора, второй вход которого со" вместно с одиннадцатым 62 входом блока 5 и вторым входом пятого 41 сумматора соединен с первым входом третьего 39 сумма° .тора, выход которого совместно с третьим входом тринадцатого 49 сумматора подключен к третьему входу двенадцатого 48 сумматора, второй вход которого соединен .с выходом седьмого 43 сумматора, второй вход которого совместно со вторым входом второго 38 сумматора подключен к пятнадцатому 66 входу блока 5, десятый 61 вход 5 которого совместно со вторыми входами третьего 39 и девятого 45 сумматоров.соединен с первым входом шестого 42 сумматора, выход которого подключен к третьему входу одиннадцатого 47 сумматОра, выход пятого 41 сумматора соединен с третьим входом десятого 46 сумматора, второй вход тринадцатого 49 сумматора совместно со вторыми входами четвертого 40 и шестого

42 сумматоров подключен к двенадцатому

63 входу блока 5, выходы которого с первого

67 по восьмой 74 соединены соответственно с выходами сумматоров, с восьмого 44 по пятнадцатый 51 или входы блока 5 с первого

52 по восьмой 59 подключены соответственно к первым входам сумматоров с восьмого

44 по пятнадцатый 51, девятый вход 60 блока 5 совместно с первыми входами пятого 41 и шестого 42 сумматоров соединен с первым входом первого сумматора 37, выход которого совместно со вторым входом двенадцатого сумматора 48 подключен ко второму входу восьмого сумматора 44, третий вход которого совместно со вторым входом десятого сумматора 46 соединен с выходом второго сумматора 38, первый вход. которого совместно со вторым входом третьего сумматора 39 подключен к тринадцатому входу 64 блока 5, пятнадцатый вход 66 которого совместно со вторым входом первого сумматора 37 соединен со вторым входом седьмого сумматора 43, выход которого подключен к третьему входу девятого суммато-. ра 45, второй вход которого совместно с первым входом четвертого сумматора.40 и вторым входом шестого сумматора 42 соединен с десятым входом 61 блока 5, четырнадцатый вход 65 которого совместно со вторым входом второго сумматора 38 и первым входом седьмого сумматора 43 подключен ко второму входу пятнадцатого сумматора 51, третий вход которого совместно со вторым входом одиннадцатого сумматора 47 и третьим входом четырнадцатого сумматора 50 соединен с выходом третьего сумматора 39, первый вход которого совместно со вторым входом тринадцатого сумматора 49 подключен к двенадцатому входу 63 блока 5, одиннадцатый вход 62 которого совместно со вторыми входами пятого 41 и четырнадцатого 50 сумматоров соединен со вторым входом четвертого сумматора 40, выход которого совместно с третьим входом тринадцатого сумматора 49 подключен к третьему входу двенадцатого сумматора 48, выходы пятого 41.и шестого 42 сумматоров соответственно подключены к третьим входам десятого 46 и одиннадцатого 47 сумматоров, выходы сумматоров с восьмого 44 по пятнадцатый 51 соответственно соединены с выходами блока 5 с первого 67 по восьмой

74 или входы блока 5 с первого 52 по восьмой 59 подключены. соответственно к первым входам сумматоров с восьмого 44 по пятнадцатый 51, девятый вход 60 блока 5

1716504

10

20 матора 50 и одиннадцатым входом 62 блока 35

50 совместно с первыми входами шестого 42 и седьмого 43 сумматоров соединен с первым входом первого сумматора 37, выход которого совместно со вторым входом двенадцатого сумматора 48 подключен ко второму входу восьмого сумматора 44, третий вход которого совместно со вторым входом десятого сумматора 46 и третьим входом пятнадцатого сумматора 51 соединен с выходом четвертого сумматора 40, первый вход которого совместно с третьим входом третьего сумматора 39 подключен к тринадцатому входу 64 блока 5, пятнадцатый вход 66 которого совместно со вторым входом первого сумматора 37 соединен со вторым входом пятого сумматора 41, выход которого подключен к третьему входу девятого сумматора 45, второй вход которого совместно с десятым входом 61 блока 5 соединен со вторым входом седьмого. сумматора 43, выход .которого подключен к третьему входу одиннадцатого сумматора 47, второй вход которого совместно. с третьим входом четырнадцатого сумматора 50 соединен с выходом третьего сумматора 39, первый вход которого совместно с двенадцатым входом 63 блока 5.и вторыми входами второго 38 и пятнадцатого 51 сумматоров подключен ко второму входу тринадцатого сумматора 49, третий вход которого совместно с третьим входом двенадцатого сумматора 48 соединен с выходом второго сумматора 38, первый вход которого совместно со вторым входом четырнадцатого сум5 подключен ко второму входу шестого сумматора 42, выход которого соединен с третьим входом десятого сумматора 46, второй вход четвертого сумматора 40 совместно с первым входом пятого сумматора 41 подключен к четырнадцатому входу 65 блока 5, выходы которого с первого 67 по восьмой 74 соответственно соединены с выходами сумматоров с восьмого 44 по пятнадцатый 51.

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

Коды первого и второго сомножителей через входы 6 и 7 устройства соответственно записываются в первый 1 и второй 2 регистры, с выходов которых поступают соответственно на первые и вторые входы групп 3.1, ..., 3,8 элементов И 3. образуя множество коньюнкций (А Bi- ), результаты вычисления которых с выходов элементов И

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

Аппаратные затраты на реализацию устройства составляют 152 элементарных функциональных элемента (16 триггеров, 64 двухвходовых элемента И и 72 двухвходовых сумматора по модулю два), в то время как для реализации известного устройства—

222 элемента (16 триггеров, 64 двухвходовых элемента И, 141 двухвходовый сумматор).

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

Устройство для умножения элементов поля Галуа GF(2 ) при образующем полиноме F(x)=x +х +х+х +1, содержащее два и8 4 3 разрядных регистра (n=8), матрицу (и х и)

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

5 ... 8, 1 — номер строки матрицы) соединен с выходом 1-ro разряда и-разрядного регистра второго операнда, второй вход)-го элемента

И в каждой строке матрицы. соединен (I--1,,... 8, j — номер столбца матрицы) соответст0 венно с выходом К-го разряда и-разрядного регистра первого операнда (К=8, ..., 1), о т л» и ч а ю щ е е с.я тем, что, с целью сокращения аппаратурных затрат, выходы (1,1)- и (8,8)-го элементов И матрицы соединены соответственно с первым и пятнадцатым входами блока формирования результата, выходы элементов И матрицы, кроме (1,1)- и (8,8)-го элементов И, соединены с входами соответствующих весов сумматоров по модулю два с первого по тринадцатый блока формирования частичных произведений, выходы которых соединены соответственно с входами с второго по четырнадцатый блока формирования результата, с первого по восьмой. выходы которого соединены с выходами результата устройства, при этом в блоке формирования результата первые входу сумматоров по модулю два с первого по восьмой соединены соответственно с входами с первого по восьмой блока. девятый вход которого соединен с первыми входами девятого и десятого сумматоров по модулю два, десятый вход блока соединен с первыми входами одиннадцатого и двенадцатого и вторым входом второго сумматоров по модулю два, одиннадцатый вход блока соединен с вторым входом седьмого и одиннадцатого и первым входом тринадцатого сумматоров по модулю два, двенадцатый вход блока соединен с первым входом

1716504

10

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

1716504

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

1716504

1716504

1716504

Составитель И.Ковалив

Техред М. Моргентал

Корректор Л. Бескид

Редактор Н.Горват

Производ «нно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101

Заказ 613 Тираж Подписное

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

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