Глава 9

Негациклические коды для метрики Ли

в этой главе мы построим класс кодов, исправляющих конфигурации ошибок достаточно малого веса в смысле метрики Ли. На протяжении всей главы предполагается, что входной алфавит канала состоит из элементов поля GF (р), где р - простое нечетное число. Хотя читателю может сначала показаться, что это сильное ограничение, оно является необходимым. В отличие от метрики Хэмминга метрика Ли связана со способом модуляции, приводящим к необ-: ходимости построения кодов над кольцами классов вычетов по модулю q, а не над структурами типа полей GF (q). Если объем входного : алфавита не является простым числом, то такое кольцо не будет полем и конструкции этой главы оказываются несостоятельными. Позже мы увидим (теорема 13.25), что для некоторых очень специальных случаев существуют другие конструкции, приводящие: к хорошим кодам над алфавитами составных порядков.

9.1. Локаторы ошибок и многочлен локаторов ошибок

Начнем с рассмотрения ошибок веса 1. Если блоковая длина рав- j на п, существует 2п конфигураций таких ошибок, так как в метрике, Ли вес 1 имеют одиночные ошибки вида ±1 в любой из п позиций. Присоединяя сюда нулевой вектор ошибок, получим 2п + 1различ-; ных векторов ошибок с весом Ли 1. Если мы хотим с помощью j линейного кода, содержащего г проверочных позиций, исправить j каждую из этих 2?г + 1 конфигураций ошибок, то каждой из них надо; сопоставить различные проверки и, следовательно, 2п i р или п{р - 1)/2.

Следуя основной идее Боуза - Чоудхури и Хоквингема построения кодов, перенумеруем каждую позицию кода ненулевыми элементами из некоторого расширения поля GF (р). Предыдущее неравенство наводит на мысль, что каждую позицию кода надо соотносить двум различным локаторам ошибок из GF {р). Учитывая определение метрики Ли и нашу задачу исправлять ошибки ±1 в каждой из! п - (р - 1)/2 позиций, свяжем с у-й позицией кода пару локаторов; ±а~1, где а - примитивный элемент поля GF (р). Так как а" = \ = -1, то пары, соответствующие двум различным позициям, не имеют общих локаторов.

В качестве простейшего нетривиального примера рассмотрим случай р = Ъ, 7- = 2 и п = (5 - 1)/2 = 12. Здесь 24 ненулевых элемента поля GF (25) могут быть записаны в виде соответствующих степеней а, где а - корень примитивного квадратного многочлена а; + х + 2. Каждый элемент из GF (25) может быть также записан в виде Ла + Ло, где и А GF (5). Соотношения между этими способами задания GF (25) выписаны в приложении В. Сопоставим ненулевые числа из GF (25) и 12 позиций кода следующим образом:

Позиции кода

Мы теперь утверждаем, что любой вектор ошибок с весом Ли, равным t, может быть определен с помощью локаторов t одиночных ошибок или с помощью задания многочлена о (z), взаимные корни которого представляют собой эти локаторы.

Рассмотрим, например, следующие векторы ошибок:

для всех нечетных ;

(aO-2Xi = S;.

Читателя, знакомого с обобщением Горенстейна - Цирлера для БЧХ-кодов в метрике Хэмминга, необходимо предупредить о том, что в наших негациклических кодах для метрики Ли не используются значения ошибок. Величине ошибки в некоторой данной позиции соответствует кратность корня в многочлене локаторов ошибок. Таким образом, справедлива

9.11. Т е О р ем а. Каждый из различных векторов ошибок с весом Ли, равным t, соответствует одному из многочленов локатюров ошибок о (z) степени t.

При соответствующих ограничениях справедливо и обратное.

9.12. Теорема. Многочлен локаторов ошибок а (z) степени t соответствует вектору ошибок свесомЛи,равным1,есливсевзаимные корни многочлена а (z) - корни 2п-й степени из единицы, кратность всех взаимных корней а (z) не превосходит {р - 1)/2, и никакие два взаимных корня а (z) не равны в сумме нулю.

9.2. Коды, исправляющие две ошибки

Рассмотрим теперь код с блоковой длиной 12 над GF (5), исправляющий две ошибки в метрике Ли. Как показано в приложении В, ненулевые элементы поля GF (25) могут быть записаны через «тепени корня а многочлена х х -t- 2. Следуя эвристическим рассуждениям Боуза - Чоудхури - Хоквингема, в качестве первых двух строк проверочной матрицы выберем положительные локаторы позиций, а в качестве вторых двух строк - кубы первых двух строк:

"О 1 -1 1 -2-1 0 2 -2 -2 1 -2-1 0 -2 2 2 -1 2 0 1 -1 -1 -2 0-1 0-2 О 1 0 2 0 -1 0 -2 .1 2 2 -1 -1 -2 -2 1 1 2 2 -1. В качестве кодовых слов выбираются векторы, удовлетворяющие этим четыремпроверочным соотношениям. К переданному кодовому слову прибавляется шум. Используя первые два проверочных уравнения, декодер получает сумму локаторов ошибок, 5i = 2 i, а используя два нижних уравнения, он получает сумму кубов локаторов ошибок, 53 = 2 Xi- Если произошло не более двух ошибок, то

5j = Xi+Х2=/= О, за исключением Zi = Z2 = 0, 8з = Х1-{- XI,

3 v2 v v I у2

- 5j= -3X1X2,

35,

(9.21)

o(z) = l -5iz-

Таким образом, код позволяет исправлять две ошибки. Для декодирования необходимо из проверочных уравнений вычислить и 5з и затем выполнить необходимые для определения многочлена локаторов ошибок операции в поле GF (5). Если а - взаимный корень этого многочлена и О / < га, то в (; + 1)-й позиции полученного слова произошла ошибка+1. Если а-взаимный корень многочлена локаторов ошибок и га ]<2п, то в (y+l - га)-й позиции полученного слова произошла ошибка -1. Двойные ошибки в любой позиции кодового слова соответствуют взаимным корням многочлена локаторов ошибок кратности два. Для рассматриваемого кода, исправляющего двойные ошибки, квадратный многочлен локаторов ошибок

"1+ 35i имеет кратные корни тогда и только тогда, когда

5? = 4

1~ 35i

или 45з = 5?.

Это же условие вытекает из уравнений = 2Xi и 5з = 2Х\. Аналогично, легко увидеть, что в случае одной единичной ошибки {S\ - Ss)/3Si = О и ошибки отсутствуют только тогда, когда = 0.

У читателя может возникнуть вопрос, почему две нижние строки проверочной матрицы были построены в виде кубов двух первых строк, а не в виде их квадратов. Если вместо кубов взять квадраты, то нужные уравнения не получаются:

Xl -\- Х2 - Si, XI -\- XI = S2,

что можно привести к внешне более громоздкому (но более удобному для анализа) виду

Xi\Xi\+ XlXl 5,.

(9.22)

(9.23)

Здесь Xi = ±Xi в соответствии с тем, в каком интервале лежит loga Xi. между О и га - 1 или между га и 2га - 1. Осложнение возникает потому, что (-fZj) = (-Х;) Ф (-Xi). Аналогичная трудность возникает при включении в проверочную матрицу любой четной степени локаторов. Хотя такой выбор и не обязательно должен быть плохим, однако он всегда приводит к уравнениям типа (9.23), которых мы предпочитаем избегать.

Сделанный нами выбор матрицы обладает еще одним интересным математическим свойством, которое мы сейчас опишем. Так как столбцы первых двух строк этой матрицы представляют собой соответствующие степени а, то кодовый многочлен С (х) степени < 12

удовлетворяет этим проверочным соотношениям тогда и только тогда, когда С (а) = 0. Это возможно тогда и только тогда, когда многочлен С (х) кратен минимальному многочлену х + х + 2 элемента а. Аналогично, кодовый многочлен удовлетворяет последним двум проверочным соотношениям тогда и только тогда, когда С (а) = = О, что возможно тогда и только тогда, когда С (х) кратен минимальному многочлену х - 2 элемента а. Ясно, что многочлен С (х) степени <; 12 представляет кодовое слово тогда и только тогда, когда С (х) кратен произведению (х + х + 2) (ж - 2). Так как а - примитивный элемент поля GF (25), то а* = 1, но а** # 1 при О < А: < <; 24. Так как (а) = 1 и квадратные корни из единицы исчерпываются числами ±1, то очевидно, что а = -1. Аналогично заключаем, что (a)i = -1 для любого нечетного включая / = 3. Таким образом, и минимальный многочлен х -\- х -\- 2 элемента а, и минимальный многочлен х - 2 элемента должны быть делителями многочлена х + 1. Следовательно, если

С (х) = Со -Ь Сх + Сх + . . . + Сюх" + Ciix"

- кодовое слово, то С (х) кратен многочлену (а; + х + 2) (х - 2) и хС (х) - Сц (х + 1) = Сц + С„х + Сх" + . . . + Сох" + -f CioXi также кратен этому многочлену. По этой причине мы назовем этот код негациклическим.

9.3. Негациклические коды

9.31. Определение. Негациклическим кодом с блоковой длиной п над GF (р) (р - простое нечетное число, п ф О mod р) называется множество кратных порождающего многочлена g (х), делящего многочлен а;" + 1 над GF (р). Отношение (а;" + i)/g (х) называется проверочным многочленом h (х).

Так как а;" + 1 = (а;" - 1)/(х" - 1), то корни многочлена а;" + 1 совпадают с теми корнями многочлена х" - 1, которые не являются корнями многочлена - 1. Если а - примитивный корень многочлена х" - 1, то его нечетные степени суть корни многочлена а;" + 1, а четные степени - корни многочлена х" - 1.

Отметим повторно, что корни многочлена х" + 1 являются нечетными степенями примитивного корня из единицы 2и-й степени. Следовательно, как порождающий многочлен, так и проверочный многочлен негациклического кодасблоковойдлинойгемогутбыть удобно описаны указанием их корней, являющихся нечетными степенями одного примитивного корня из единицы 2п-ш степени. Для кода, исправляющего двойные ошибки, с блоковой длиной 12 над GF (5), описанного в предыдущем разделе, корни порождающего многочлена суть а и а*, а сопряженные к ним над GF (5) - это и (а) = а".. Осталь-

ные восемь нечетных степеней а, а*, а, а, а, а", а и а* являются корнями проверочного многочлена.

Этот способ описания негациклических кодов обладает тем преимуществом, что сразу задает уравнения для определения локаторов ошибок. Если - корень порождающего многочлена, то, вычисляя значение полученного многочлена R (х) = С (х) + Е (х) при X = а\ декодер сразу получает сумму j-x степеней локаторов ошибок, R (а) = О + Е (а) =XI = Sj. Зная эти Sj, декодер должен

далее определить взаимные корни многочлена локаторов ошибок о (z), задающие локаторы ошибок. Соотношения между величинами Sj и о (z) описываются тождествами Ньютона, к рассмотрению которых мы и переходим. Пусть о (z) = Ц (1 - Zz), где - не обязательно различны. Тогда

o{z)-XiU{-Xjz),

i ]фг

za (z) XI Xiz

a(z)

i fe=l

= 2 (X)z=.Suz = S{z). k=i i ft=i

Отсюда вытекает и тождество Ньютона для производящей функции:

(9.32)

5o + zo=0.

В случае негациклических кодов все коэффициенты при четных степенях z в производящей функции S первоначально не известны. Поэтому удобно исключить эти члены с помощью разбиения тождества Ньютона на две части.

0 = 1+02Z2 + 04Z*+ ... ,

а = OjiZ + Osz + . .. , S-=S2Z + Sz*+ ... ,

S = SiZ + S3Z+ .... Тождество Ньютона можно теперь записать в виде уравнения

{S + S){a + 6) + z{a+a).0, которое распадается на два уравнения

Sa + Sa + zo = 0

Sa + Sa + za = 0.