Умножим первое уравнение на о и вычтем из него второе, умноженное на о. Тогда

(9.33)

S{o-a) +z{aa -оо) = 0.

Уравнение (9.33) может быть решено при достаточно разумных ограничениях. Основной результат содержится в теореме 9.34.

9.34. Теорема. Если среди корней порождающего многочлена негациклического кода над GF (р) содержатся элементы а, а*, а*, . . . . . ., a-, где 2t - 1<р, то этот код исправляет все ошибки, вес Ли которых t.

Замечания. Прежде чем доказывать эту теорему, приведем таблицу 9.1, в которой записаны параметры некоторых кодов, удовлетворяющих условиям теоремы. Большим t и сравнительно малым

Таблица 9.1

Значения параметров некоторых негацикличееких кодов, описываемых теоремой 9.34

Кратность исправляемых ошибок

61) 12 62 312

62 124

63 126

числам г проверочных позиций обычно соответствуют примитивные коды с блоковой длиной вида п = (р - 1)/2. Однако имеются также сравнительно хорошие непримитивные коды этого типа с другой блоковой длиной; эти коды в таблице отмечены единичкой.

Доказательство теоремы 9.34. Приводимое доказательство является конструктивным и задает эффективную процедуру декодирования.

Начнем с уравнения

5(aa-oa) = z(oo-oo). Так как о(0) = 1, то можно разделить обе части равенства на о:

Вводя производящую функцию

получим, что

S{U-i)zU,

Хотя с первого взгляда это уравнение может показаться громоздким, на самом деле оно решается тривиальным образом, поскольку каждый коэффициент и выражается через некоторые коэффициенты S и ранее определенные коэффициенты:

Uiz + U,z + U,z+ l±l-i + iUiZ + U,z+...rU., Ui= -Si,

-S, + UlS3 + 2UiUsSi

1) Непримитивный код; nfe (p"" - l)/2.

Дополнительные трудности возникают при определении коэффициента Up, так как при этом нужно выполнять деление на нуль поля GF (р). Однако, согласно предположению теоремы, 2t- 1 <j9 и при вычислении U, U, U„ . . ., Ut-x этого затруднения нет.

Так как U - нечетная функция от z, то можно ввести производящую функцию Т с помощью уравнения Т (z) = [1 + zC/ (z)]" - 1. Очевидно, что Г (0) = О и 1 + Г (z) = [1 + zC/ (z)]-i. Если коэффициенты Ui, 1/3, f/5, . . ., Ut-i известны, то это уравнение позволяет рекурсивным образом вычислить коэффициенты Т, Т, . . .

. . ., Tf Так как U = о/о и 1 + zC/ = (о + za)la, то, введя многочлены

co{z2) = o(z) и (t){z)=--a{z)- za{z), очевидно, получим

так что

(9.35)

[1 + Г (z)] Ф (z) = (о (z) mod z+i.

Мы теперь утверждаем, что если произошло не более t ошибок, то Ф и со удовлетворяют дополнительным условиям

ф(0) = со(0) = 1, degФ<, degco<

и являются взаимно простыми.

Последнее утверждение вытекает из того факта, что никакие два взаимных корня многочлена о (z) не дают в сумме нуля. Действительно, в этом случае а не может иметь делителей положительной четной степени и, следовательно, or и о, так же как Ф и со, взаимно просты.

Учитывая эти условия (9.35), можно решить уравнения (9.35) относительно Ф и со с помощью алгоритма 7.4:

ф=ф(", со = со(). Подытожим процедуру декодирования в виде алгоритма:

9.36. Алгоритм декодирования негациклических кодов, описанных теоремой 9.34.

1. Вычислить и mod z при помощи уравнения

U={m-i)dz.

2. Вычислить 1 + Г mod z+i при помощи уравнения

l+r(z2) = [l+zC/(z)r

3. Используя алгоритм 7.4, найти

Ф\ o)(0),t(0),y(0), Ф\ со(1), т(1), vi), Ф\ o)W как решения уравнений (1 + Т) ф() = со<) mod z+i.

4. Положить or (z) = со() (z); а (z) = [фС) (z) - ©С) {z)]lz; ;7 = а + а.

5. Используя процедуру Ченя, вычислить многочлены о (а")

ii а (а") для j = п ~ i, . . ., 1, О, где а - примитивный корень 113 единицы 2п-й степени, соответствующие степени которого задают

локаторы позиций кода. Если о (а~) = - о (а-), то в (/ - 1)-й позиции кода произошла положительная ошибка; если а (а~) =

= + о (а"), то в (у - 1)-й позиции кода произошла отрицательная ошибка. В любом из этих случаев кратность ошибки может быть

определена с помощью производных от а и о. Если для i <к

Г d ", О

то кратность ошибки равна к. В этих уравнениях знаку минус соответствует положительная ошибка и наоборот.

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

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

. . ., d-a/dzt-K

С другой стороны, если число вычислительных регистров недостаточно, а время вычисления не ограничено, то процедуру Ченя

можно применять только к многочленам она. Подходящее программирование позволяет вычислять производные только тогда, когда они необходимы, не прерывая процедуру Ченя для а {а~) и о (ct~).

Хотя теорема 9.34 определяет достаточно мощный класс негацик-.гических кодов с практически приемлемым алгоритмом декодирования, естественным является желание освободиться от ограничения I {р - 1)/2, поскольку возможна ситуация, когда кратность ошибки больше, чем (р - 1)/2. Очевидное решение- использование кода, корни порождающего многочлена которого содержат другие подходящие нечетные степени элемента а. Если элементов а, а, . . ., а- цР оказалось недостаточно, то, возможно, помогут ;)лементы а, а*, а, . . ., а*", а+Р К сожалению, эта гипотеза также не проходит. Причины этого будут ясны из теоремы 11.65. Задачи

9.1. Показать, что шаги 1 и 2 алгоритма 9.36 могут быть совмещены и что функция Т (z) = V (г) может быть вычислена непосредственно по S (z) из

zV - zV=zV + S [(z2 1) F2 + 2zV + z].

9.2. Выписать степени числа 3 в GF (31). Полагая ЛГ<») (х) = х -3*, рас- смотрим негациклический код с блоковой длиной 15 над GF (31), порождаемый! многочленом g (х) = Af(i) (х) ЛГ<3) (х) М<> (х) AfO (х) = х* + 20х« + ISx" + + 28х + 28. Этот код исправляет все ошибки с весом Ли < 4. Предполагая, что j произошло не более четырех ошибок, декодировать полученную последователь-; ность R = (20, 20, И, 5, 16, 9, 14, 22, 19, 23, 5, 17, 1, 6, 15].

Ответы

Глава 10

Недвоичное обобщение Горенстейна-Цирлера БЧХ-кодов в случае метрики Хэмминга

10.1. Обобщенные БЧХ-коды и алгоритм их декодирования

Циклические коды над GF (q), где q - степень произвольного простого числа, определяются точно так же, как и циклические коды ]£ад GF (2). В качестве порождающего многочлена выбираются некоторые делители многочлена а:" - 1 над GF (q). Кодовые слова исчерпываются всеми кратными порождающего многочлена, степень которых меньше, чем п. Как и в двоичном случае, порождающий многочлен д-ичного БЧХ-кода, исправляющего t ошибок, с блоковой длиной п равен произведению различных минимальных многочленов элементов а, а, а, . . ., а, где а - примитивный корень п-й степени из единицы над GF (q) и а GF (q), где т -мультипликативный порядок числа q mod п. Поле GF (q) называется полем символов, а GF (q) - полем локаторов.

Такое обобщение БЧХ-кодов на недвоичный случай впервые было предложено Горенстейном и Цирлером [1961]. Частный случай п = q - i рассматривался ранее с другой точки зрения Ридом и Соломоном [1960].

Если кодер передает кодовое слово, символы которого совпадают с коэффициентами многочлена

С (х) = Со + Сх + Сх" + . . . + Ci е GF (q),

а в канале к нему добавляется вектор шума, заданный многочленом

Е {X) = Ео + Ех+ Е.х +... + En-iO-\ Ei g GF (q),

TO декодер получает слово

R{x) = C{x) + E(x).

Пусть a - примитивный корень п-й степени из единицы. Если а - корень многочлена С (х), то R (а") = Е (а"). Если вектор ошибок содержит ошибку в позиции с локатором = al, ошибку У2 в позиции с локатором Z2,= а2,... то Е (х) = YiX

и Е (а*) = 2 (И"-» = S YiXi - iSft. Здесь Xi называются лока-

торами ошибок. У, - значениями ошибок, а - взвешенной степенной симметрической функцией.