д(20

3 =

В поле характеристики р

ft=0 m=0

Это тождество приводит к следующему утверждению: 10.56. Теорема

im,4P-l

m=0 m=0

В частном случае С/ = 1, F = FiZ и р = 2. Отсюда получаем, что

д(20 у [] [(0(20)2+ Fa(2M20]2 ,

(а(20)2 4.Fa(20T(20 = 1 + {о\У + (0*)2 z* + ... ...+Fiz[Tp>z + (Tf>+TlM>)z2+...],

так что (10.57)

А< = Fiz + [FfT<i" + Vi {а?*Г] z + ... .

10.6. Примеры

Сначала мы продолжим рассмотрение примера 7.68, в которо» исследовался двоичный БЧХ-код с исправлением 3 ошибок и кодовое длиной 31, когда поле задается многочленами от а степени <5, гдв а* + + 1 = 0. Степенные симметрические функции от локаторов ошибок имели вид = 11101 = а", S3 = 10000 = а* и S = = 00010 = аЧ Согласно алгоритму 7.4, находим, что а(*) = aV+i + О -z + ai*z 4- 1 и = ah + az + aV. Тогда 1 + S = 1 + + a"z + a2«z2 + a*z3 + az* + ah + a«z« + . . . . Используя формулу

Si для i<6,

is\%oaSl%+aS[% для J>6, .3=1

получим, что

1 + 5(в) = 1 + a"z + aV -f + aV + +

-f a«z« -f az + a"z« + az -f ah<> + . . . .

Из условий цикличности и сопряженности вытекает, что Sq = = S31+Q = = SI = Ф а" = 5(). Значит, многочлен а(*) недопустим; он не имеет в GF (2*) трех различных корней, так как Af) = Sg - iS(6) = а* - а" = 1 0. Уместно сделать следующие коррективы.

Если предположить, что произошло не более четырех ошибок, то общее решение о = С/о(*) + FtC) примет вид о = о) + FiZt(*). (Заметим, что для двоичного кода U имеет четную, а F - нечетную степень, и если deg U 2 или deg F 2, то о должен иметь степень >4.) Согласно уравнению 10.57,

Af)=F?TP4F,(of"). Для рассматриваемого примера это дает

1 = F,W* + Fia28,

(10.61) (Fio-y + Fia-* = а-\

Решения этого квадратного уравнения имеют вид Fitt-* = ач или а" + 1 = а", Fi = а" или аз.

Если Fi = а", то о = 1 + a"z -f az + az + aOz*.

Если Fi = аз, то 0 = 1 -f a"z + az -f ah + a-z*.

Один из методов проверки этих возможных многочленов локаторов ошибок на допустимость - это установить, делят или не делят они многочлен z* - z. Это можно осуществить очень быстро. По модулю 0 (z) = Z* -Ь az + az + az -f a"

z* = ai*z3 -I- ah + az + ao, 25 „162З „2622 a"z + «3, ze = дзз j „822 „162 + a z2 = (z*)2 = a28z« 4- a"z* + az + a" = = a-3z3 -L ai5z2 + аЗг + aS z2* = a-6z« J- a-iz* + ah + a = = агз + a23z2 -l az +

225 „2426 „1524 J „822 „25 =

Следовательно, многочлен а (z) = 1 + a*z + a*z + az + аЩ должен иметь в GF (2) четыре различных корня. С помощью процеду! ры Ченя находим, что

а = (1 + ah) (1 + ah) (1 + ah) (1 + a"z).

Второй возможный многочлен локаторов ошибок также имеет четы корня в GF (25):

1 + a"z + a"z2 + azs + aV =

= (1 + a"z) (1 + ah) (1 + ah) (1 + azf

Итак, оказалось, что любая попытка исправить 4 ошибки с nfl мощью двоичного БЧХ-кода с исправлением 3 ошибок и блоково длиной 31 приводит к двузначности результата, так как каждь смежный класс, имеюнщй вес 4, содержит 2 лидера. Это свойств является следствием того, что рассматриваемый код получаетс выбрасыванием одного символа из кода Рида - Маллера. Ко;: такого типа изучаются в разд. 15.3.

В качестве второго примера рассмотрим двоичный БЧХ-кс с блоковой длиной 31 и исправлением 5 опшбок. Предполож! что Si = а\ S3 = a S = а, S = а\ Так как Sg = SI = а,

1 + 5 (z) = 1 + a*z +, a"z2 -f ah -f aV +

-f ai»z* + ah« + ah -f ah + a"z» + a-izi» + . . . .

Согласно алгоритму 7.64,

am (z) = 1 -f ah + a"z + aV -j- aV + ah\ t(i«) (z) = ah + a"z2 + aV -f aV + a"z».

С помощью обычных вычислений находим, что

Sm (z) =

Здесь

51° = a" Ф {S[y = (a)* = ao.

Многочлен локаторов ошибок (z) недопустим, и уместно внес! коррективы.

Если произошло не более шести ошибок, то, согласно уравне нию (10.57),

Полагая Sg = 5*1, получим квадратное уравнение относительно

(10.62)

1,10

-f Fia" + Via = (а -f F}*, + Fia" + FJa + F* = 0.

Как будет показано в разд. 11.1, это уравнение имеет в GF (2) два решения: либо Vi = а*, либо F = а*.

Если Fi = то о (z) = 1 + ah + ah + aV -f a"z* +

+ aV + и 1 -f 5 (z) =

+ az + az* -f az + az* + az. Так как в этом случае = а, SI = а* =5 5з = а, то мы должны отвергнуть гипотезу Fa = «2*.

Полагая Fj = а*, получим, что о (z) = 1 -f az -f az + aV + + aV -f az + az*. Процедура Ченя показывает, что этот многочлен допустим и имеет место разложение

а (z) = (1 -f z) (1 -f az) (1 -\- ah) (1 + ah) (1 + a*z) (1 + ah).

В общем случае если предположить, что произошло t + и ошибок, то, используя разложение в ряд для производящей функции А(), можно получить систему уравнений относительно и неизвестных коэффициентов многочленов U ж V. Эта система может не иметь решения (что случится, когда полученное слово лежит в смежном классе, все слова которого имеют вес >Z + и), может иметь несколько допустимых решений или единственное решение.

К сожалению, эти системы нелинейных уравнений бывают очень сложными, и ;ало что известно об условиях существования решений, условиях их единственности и правилах отыскания решений (решения), если они существуют. Если предположить, что произошла только t -\- I ошибка, то локатор этой дополнительной ошибки может быть найден с помощью решения единственного алгебраического уравнения с одной неизвестной Fi. Однако если произошло более чем Z + 1 ошибок, то ситуация очень быстро усложняется.

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

Задача

10.1. Рассмотрим БХЧ-код с исправлением двух ошибок над GF (4). Пред-полошим, - что l + S = l + 0z4-ai*22 j a23-f-0z*+. . . . Показать, что a(z) = l + + a2z4-a*z2 и что Xi = a, Ха, Yi = l, 2 = 1-

Глава 11

Линеаризированные многочлены и аффинные многочлены

11.1. Как найти их корни

Мы видели, что часто возникает ситуация, когда декодеру необ- ходимо знать корни многочлена / (z) над GF (р"), лежащие в этом! поле. Общим методом решения этой задачи является процедура Ченя, описанная в разд. 5.4. Для больших значений числа она требует значительного числа операций.

Однако существует специальный класс многочленов, корни кото-1 рых могут быть найдены значительно проще. Эти многочлены впервые I исследовались Оре [1933, 1934], который назвал их р-многочленами,\ но мы в силу причин, которые станут ясными из теоремы 11.12,] будем называть их линеаризированными многочленами.

11.11. Определение. Многочлен L (z) над GF (р™) называется линеаризированным, если L {z)= 2 LiZP.

Если Zfe g GF (p) и a", a, . . ., «""- - стандартный базис ноля] GF (р"), то отсюда получим важное утверждение.

11.12. Теорема. Пусть L (z)-линеаризированный многочлен] и Z = 2Zfta где е GP (р), тогда L (z) = ZL (а").

Используя для элементов L (а"), L (а), . . ., L (а"") стандарт-

ные выражения, получаем, что L (at) = 2 Xt, jo}, Х%, j б GF (р).

Следовательно, коэффициенты разложения многочлена L (z) по стандартному базису могут быть получены путем умножения вектор-строки Z = [Zo, Zj, . . ., Zm-i\ на [т X пг)-матрицу над GF (р):

[Zq, Zj, . . . , Zm-i\

0,0 Xo,i Xo,2 ••• Xo,m-l 1,0 1,1 1,2 ••• 1. m-l

Xm-l,0........m-l,n-l

Рассмотрим, например, многочлен

L (z) = z* -j- az + ai«2

над GF (2), где a - корень примитивного неприводимого двоичного многочлена + + I. Используя приведенные в приложении А таблицы логарифмов и антилогарифмов, получаем, что

L (1) = 1 + а + = а + «2 + а*,

L (а) = а* + а" + а" = + а\

L {а") = а» + а" + а» = а + a

L (а) = + + = а + a

L (а*) = а" + + = 1 + а\

так что X - двоичная, (5 X 5)-матрица вида

0 110 1 0 0 110 0 110 0 0 10 10 Ll О О О IJ

Если, например, необходимо найти корни многочлена (10.62) Z* + az -f + а",

то это эквивалентно уравнению

L (z) = а" = 1 + а\ что равносильно системе линейных двоичных уравнений

ГО 1 1 О П

[07 li 2) 3,

0 0 110 0 110 0 0 10 10

Ll о о о 1

= [1 0 0 0 1].

Эта система может быть решена с помощью методов, описанных в разд. 2.5. Ее решения - это Z = [О О О О 1] и Z = [О 1 1 1 1]. Следовательно, а* и а + + + а* = а* - корни многочлена (10.62) в GF (2); другие два корня лежат в GF (2").

Многочлен (10.62) получается путем вычитания из линеаризированного многочлена константы. Многочлены такого вида мы будем называть аффинными.

11.13. Определение. Многочлен А (z) над GF (р™) называется аффинным, если Л (z) = L (z) - и, где L (z) - линеаризированный многочлен, а м g GF (р").

Как было видно из примера, корни произвольного аффинного многочлена над GF (р"), лежащие в поле GF (р"), могут быть найдены