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

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

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

Начнем с рассмотрения ошибок веса 1. Если блоковая длина равна существует конфигураций таких ошибок, так как в метрике Ли вес 1 имеют одиночные ошибки вида ±1 в любой из позиций. Присоединяя сюда нулевой вектор ошибок, получим различных векторов ошибок с весом Ли 1. Если мы хотим с помощью линейного кода, содержащего проверочных позиций, исправить каждую из этих конфигураций ошибок, то каждой из них надо сопоставить различные проверки и, следовательно, или

Следуя основной идее Боуза — Чоудхури и Хоквингема построения кодов, перенумеруем каждую позицию кода ненулевыми элементами из некоторого расширения поля Предыдущее неравенство наводит на мысль, что каждую позицию кода надо соотносить двум различным локаторам ошибок из Учитывая определение метрики Ли и нашу задачу исправлять ошибки ±1 в каждой из позиций, свяжем с позицией кода пару локаторов где а — примитивный элемент поля Так как то пары, соответствующие двум различным позициям, не имеют общих локаторов.

В качестве простейшего нетривиального примера рассмотрим случай Здесь 24 ненулевых элемента поля могут быть записаны в виде соответствующих степеней а, где а — корень примитивного квадратного многочлена Каждый элемент может быть также записан в виде где Соотношения между этими способами задания выписаны в приложении В. Сопоставим ненулевые числа из и 12 позиций кода следующим образом:

Позиции кода

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

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

Решающее свойство локаторов состоит в том, что для всех нечетных

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

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

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

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