Глава 9. Коды БЧХ

9.1. ВВЕДЕНИЕ

Коды БЧХ представляют большой практический интерес с точки зрения исправления ошибок, особенно когда ожидаемое число ошибок мало по сравнению с блоковой длиной. Впервые мы встретились с этими кода в гл. 3, где коды БЧХ, исправляющие две ошибки, были построены как обобщение кодов Хэмминга. Лучше, однако, рассматривать коды БЧХ как циклические коды, что и было сделано в § 7.6 при общем определении кода БЧХ, исправляющего ошибок. Естественно, что основная часть теории циклических кодов, развитой в гл. 7 и 8, приложима к кодам БЧХ.

Например, коды БЧХ легко кодируются любым из методов, описанных в § 7.8. Декодирование будет рассматриваться ниже в § 96.

Напомним, что в гл. 7 код БЧХ над полем GF(q) длины и конструктивным расстоянием был определен как наибольший максимально возможный циклический код, нулями которого являются где примитивный корень степени из единицы; неотрицательное целое число, мультипликативный порядок по модулю (см. § 7.5).

Важнейшие частные случаи задаются условиями: (соответствующие коды называются кодами БЧХ в узком смысле) и (так называемые примитивные коды БЧХ). В тех случаях, когда не оговорено противное, под кодами БЧХ понимаются примитивные коды БЧХ в узком смысле. Другим важным подклассом кодов БЧХ являются коды с (т. е. с ). Этот подкласс известен как коды Рида — Соломона, и следующая глава посвящена описанию специфических свойств этих кодов.

В § 7.7 получены границы для размерности и минимального расстояния произвольного кода БЧХ.

Теорема Код БЧХ над GF(q) длины с конструктивным расстоянием имеет размерность и минимальное расстояние

(b). Двоичный код БЧХ блоковой длины и конструктивным расстоянием имеет размерность и минимальное расстояние

Возникает естественный вопрос, сколь близки эти границы к истинным значениям этот вопрос рассматривается в § 9.2 и 9.3. Ответ, грубо говоря, означает, что они достаточно близки. Однако в общем случае точная формула для не найдена до сих пор.

§ 9.4 содержит таблицу двоичных кодов БЧХ длин не более 255. В этом диапазоне (а на самом деле для длин, достигающих нескольких тысяч) коды БЧХ принадлежат к лучшим известным кодам (см. приложение А). Однако, как показано в § 9.5, если зафиксировать скорость и устремить длину к бесконечности, то их характеристики ухудшаются.

Декодированию кодов БЧХ посвящена обширная литература, предложены весьма эффективные алгоритмы их декодирования. § 9.6 содержит простое введение в описание алгоритма декодирования и его этапов.

Последний шаг алгоритма состоит в определении корней многочлена локаторов ошибок. Как мы увидим в § 9.7, в случае, когда этот многочлен является квадратным над полем характеристики 2, его корни находятся просто. Результаты § 9.7 используются также в § 9.8 для доказательства квазисовершенности двоичных кодов БЧХ, исправляющих две ошибки.

Использование глубоких результатов теории чисел позволяет показать в § 9.9, что если конструктивное расстояние кода БЧХ не превосходит примерно то все значения весов кода расположены около Можно заметить, что весовой спектр для многих кодов хорошо аппроксимируется функцией плотности нормального закона распределения. В § 9.10 дается частичное объяснение этого феномена.

В последнем параграфе главы описывается интересное семейство кодов не БЧХ, исправляющих три ошибки.

Обозначения. Обычно в этой главе обозначает (примитивный в узком смысле) код БЧХ над GF(q) с конструктивным расстоянием Как и выше -примитивный корень степени из единицы, где мультипликативный порядок по модулю (см. § 7.5).

Пусть — вектор над GF(q) веса и

Если ненулевые координаты вектора а, то назовем величины локаторами вектора , а многочлен

— многочленом локаторов Пусть далее и определим степенные суммы вида

(см также § 8.6) В частности, если вектор а принадлежит коду то для всех