Устройство для умножения элементов поля Галуа GF(2 @ ) при образующем полиноме F(х)=х @ +Х @ +х @ +х @ +1 Советский патент 1992 года по МПК G06F7/49 

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

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

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

соответствующего примитивному элементу поля, и зависимость времени выполнения операции умножения от значения коэффициентов первого полинома сомножителя.

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

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

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

О

ел о

4

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

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

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

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

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

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

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

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

С этой целью в устройство для умножения элементов поля Галуа GF(2 ) при обра- 45 зующем полиноме F(x)x8+x4+x3+x2+1, содержащее два п-разрядных регистра (), матрицу (n х п) элементов И, блок формирования частичных произведений, состоящий из тринадцати сумматоров по 50 модулю два, и блок формирования результата, состоящий из пятнадцати сумматоров по модулю два, причем информационные входы первого и второго п-разрядных регистров соединены соответственно с входами 55 первого и второго сомножителей устройст- . ва, первый вход 1-го элемента И в каждом

столбце матрицы (,1 - номер строки

матрицы), соединен с выходом i-fo разряда п-разрядногр регистра второго операнда,

второй вход i-ro элемента И в каждой строке матрицы соединен . j - номер столбца матрицы) соответственно с выходом К- го разряда п-разрядного регистра первого

операнда (), выходы (1,1)-го и (8,8}-го

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

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

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

Вычисление результата умножения элементов поля Галуа GFp8) при образующем полиноме Р(хУ х8+хА+х +х+1 реализуется на основе следующих соотношений.

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

So оь©#©Дг

Sl «1©/3g® 2 $2

5з 03©ySi@$

$4

S5 05©an©/ 3

5б Об©СГ10©/ 4

S7 07©ai3©/ 4(

где

fi «3©«12

/fc ai3©ai4

Д} «9©«10

$4 «n©ai2 /S5 aio®ai3

fk - О8®Щ 1 /9 «8®«14

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

So «b©/3i©/%

Sl «1©«9©/#7

$2 «2©Дг©$

$4 55 «5©«11©/ 4

Se «б©«ю©Дз S «7©«1з©/йз

где

/Si «8® «14

. $2 «12©«13

/Зз «м©«12

«9 ©«10

/% «8©«io / б «8©«9

«13 ©«14

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

So

Si «i©«9©/k

S2

5з «з©Дз©/ 7

84

.85 as ©an Se «бф«ю ®/8з

S7 «7©«11

(2м)

in

)

IK 15

20

25

где

«8® «14 /fc 059 фаю #3 «11 ©«12

/84 «12 Фатз

/fe «13 ©«14

/fe «8 ©«ю

Pi 08 © «9

Причем «i ЈAj BI-J(3), где«i-част-

j 0.

ные произведения сомножителей, АО, ..,, А

- разряды кода первого сомножителя, Во

В - разряды кода второго сомножителя.

Знак суммы определяет функцию ело-

жения по модулю два. Значения AsAi4,

Bs, ..., 814 равны нулю и в формировании результатов частных произведений участия не принимают.

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

15

Например: «15 Aj Bi5-j AoBig©AiBi4©

J 0

©А2В13© АзВ12© A4Bi0AsBio© АеВд © © АзВ7 @ АэВе © АюВб ©АцВ4с& ©Ai2B3©Ai3B2@Ai Bi©Ai5Bo. Представляя As, .. , , B8 В , получаем .

)

.,

10

15

20

25

30

35

т- 40

А

о- 45

i4,

ии ия

50

ссю.

4© 55

© 4с& яя 0. .

Анализ выражения (3) показывает, что для вычисления значений частных произведений «о, ,.., «14 потребуется 64 двухвходовых элемента И и 49 двухвходовых сумматоров по модулю два.

Для. вычисления значений , .... /3 согласно выражения (2) требуется 7 двухвходовых сумматоров по модулю два, а для вычисления синдромов So, ... S согласно выражению (1) требуется 16 двухвходовых сумматоров по модулю два.

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

При введении в указанной связи с ос тальными элементами схемы в предлагаемое УСТРОЙСТВО.ДЛЯ умножения элементов поля Галуа GF(2S) при образующем полиноме F(x)x +x +х3+х2+1 указанные блоки проявляют новые свойства, приводящие к упрощению устройства,

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

Устройство для умножения элементов поля Галуа GF(2 при образующем полиноме F(x)x+x4+x3+x2+1 содержит первый 1 и второй 2 регистры, группы 3.1, .... 3.8 элементов И 3, блок 4 формирования частных произведений, блок 5 формирования результата, входы 6 и 7 устройства являются входами первого и второго сомножителей, выход 8 устройства, причем входы первого 1 и второго 2 регистров подключены соответственно к входам 6 и 7 устройства, первые входы элементов И 3 каждой группы 3.1, ...., З.Зрбъединены и подключены к соответ- ствун щим выходам первого 1 регистра, каждый выход второго 2 регистра подключен к соответствующим по порядку объединенным вторым входам группы 3.1,.... 3.8 элементов И 3, входы блока 4 формирования частных произведений согласно нумерации подключены к выходам соответствующих элементов И 3 таким образом, что номер состоит из двух цифр, первая из которых указывает номер выхода первого регистра, а вторая цифра - номер выхода второго регистра, входящих в коньюнкцию, выходы блока 4 формирования частных произведений соединены с соответствующими входами блока 5 формирования результата.

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

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

Блок 5 формирования результата содержит пятнадцать сумматоров 37-51 по модулю два, пятнадцать входов 52-66 блока 5 и восемь выходов 67-74 блока 5, причем входы блока 5 с первого 52 по восьмой 59 подключены соответственно к первым входам сумматоров с восьмого 44 по пятнадцатый 5,1, девятый вход 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, десятый $1 вход которого совместно со вторыми входами третьего 39 и девятого 45 сумматоров соединен с первым входом шестого 42 сумматора, выход которого подключен к третьему входу одиннадцатого 47 сумматора, выход

пятого 41 сумматора соединен с третьим входом десятого 46 сумматора, второй вход тринадцатого 49 сумматора совместно со вторыми входами четвертого 40 и шестого

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

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

0 десятого сумматора 46 соединен с выходом второго сумматора 38, первый вход.которо- t го совместно со вторым входом третьего сумматора 39 подключен к тринадцатому входу 64 блока 5, пятнадцатый вход 66 кото5 рого совместно со вторым входом первого сумматора 37 соединен со вторым входом седьмого сумматора 43, выход которого подключен к третьему входу девятого суммато-. . ра 45, второй вход которого совместно с

0 первым входом четвертого сумматора .40 и вторым входом шестого сумматора 42 соединен с десятым входом 61 блока 5, четырнадцатый вход 65 которого совместно со вторым входом второго сумматора 38 и пер5 вым входом седьмого сумматора 43 подключен ко второму входу пятнадцатого сумматора 51, третий вход которого совместно со вторым входом одиннадцатого сумматора .47 и третьим входом четырнадцатого

0 сумматора 50 соединен с выходом третьего сумматора 39, первый вход которого совместно со вторым входом тринадцатого сумматора 49 подключен к двенадцатому входу 63 блока 5, одиннадцатый вход 62 которого со5 вместно со вторыми входами пятого 41 и четырнадцатого.50 сумматоров соединен со вторым входом четвертого сумматора 40, выход которого совместно с третьим входом тринадцатого сумматора; 49 подключен к

0 третьему входу двенадцатого сумматора 48, выходы пятого 41 и шестого 42 сумматоров соответственно подключены к третьим входам десятого 46 и одиннадцатого 47 сумматоров, выходы сумматоров с восьмого 44 по

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

совместно с первыми входами шестого 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, первый вход которого совместно со вторым входом четырнадцатого сумматора 50 и одиннадцатым входом 62 блока 5 подключен ко второму входу шестого сумматора 42, выход которого соединен с третьим входом десятого сумматора 46, второй вход четвертого сумматора 40 совместно с первым входом пятого сумматора 41 под- ключей к четырнадцатому входу 65 блока 5, выходы которого с первого 67 по восьмой 74 соответственно соединены с выходами сумматоров с восьмого 44 по пятнадцатый 51.

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

Коды первого и второго сомножителей через входы 6 и 7 устройства соответственно записываются в первый 1 и второй 2 регистры, с выходов которых поступают со- ответственно на первые и вторые входы групп 3.1, ..., 3.8 элементов И 3. образуя множество коньюнкций (Aj BI-J), результаты вычисления которых с выходов элементов И 3 поступают в блок 4 формирования частот- ных произведений согласно выражению(3) и далее в блок 5 формирования разрядов кода результата So,..., S, вычисление которых осуществляется согласно выражениям (1)и(2).

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

Формула изо б р е те н и я Устройство для умножения элементов поля Галуа GF(2®) при образующем полино- м е F(x)x8+x4+x3+x +1, соде ржа щее д ва п- разрядных регистра (), матрицу (n x п) элементов И, блок формирования частичных произведений, состоящий из тринадцати сумматоров по модулю два, и блок формирования результата, состоящий из пятнадцати сумматоров по модулю два, причем информационные входы первого и второго п-раз- рядных регистров соединены, соответственно с входами первого и второго сомножителей устройства, первый вход 1-го элемента И в каждом столбце матрицы (. ... 8, I,- номер строки матрицы) соединен с выходом 1-го разряда n-разрядного регистра второго операнда, второй вход j-ro элемента И в каждой строке матрицы соединен (, .... 8, j - номер столбца матрицы) соответственно с выходом К-го разряда п-разрядного

регистра первого операнда (), о т л

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

четырнадцатого и вторыми входами шестого и двенадцатого сумматоров по модулю два, тринадцатый вход блока соединен с вторыми входами девятого и четырнадцатого сумматоров по 5 модулю два, четырнадцатый вход блока соединен с первым входом пятнадцатого и вторыми входами восьмого и тринадцатого сумматоров по модулю два, пят- 10 надцатый вход блока соединен с вторыми входами десятого и пятнадцатого сумматоров по модулю два, выход девятого сумматора . по модулю два среди- 15 нен с вторыми входами первого, третьего и четвертого сумматоров по модулю два, выход десятого сумматора по модулю два сое динен с вторым входом пятого сумматора по модулю два, третий вход которого соединен, 20 с третьим входом шестого и выходом одинг- надцатого сумматоров по модулю два, выхо- ды двенадцатого и тринадцатого сумматоров по модулю два соединены соответственно с третьими входами четвертого и третьего Сум- 25 маторов по модулю два. выход четырнадцатого сумматора по модулю два соединен с третьими входами седьмого и восьмого сумматоров по модулю два, выход пятнадцатого сумматора по модулю два соединен с третьи- 30 ми входами первого и второго сумматоров по модулю два, выходы сумматоров по модулю два с первого по восьмой соединены соответственно с выходами с первого по восьмой блока или в блоке формирования 35 результата первые входы сумматоров по мЪ- дулю два с первого по восьмой соединены соответственно С входами с первого по восьмой блока, девятый вход которого соединен с первыми входами сумматоров по 40 модулю два с девятого по одиннадцатый, десятый вход блока соединен с первым входом двенадцатого и вторыми входами второго и одиннадцатого сумматоров по модулю два, одиннадцатый вход блока сое- 45 динен с вторыми входами седьмого, десятого и двенадцатого сумматоров по модулю -два, двенадцатый вход блока соединён ;с первым входом тринадцатого и вторым входом шестого сумматоров по модулю два, три- 50 надцатый вход блока соединен с первым входом четырнадцатого и вторым входом тринадцатого сумматоров по модулю два, четырнадцатый вход блоха соединен с вторыми входами восьмого и четырнадцатого и 55 первым входом пятнадцатого сумматоров по модулю два/пятнадцатый вход блока соединен с вторыми входами девятого и пятнадцатого сумматоров по модулю, два, выход девятого сумматора по модулю два

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

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

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

7 1

I

Фиг.1

ФиаЗ