ГЛАВА 7. КОДЫ БОУЗА-ЧОУДХУРИ-ХОКВИНГЕМА

Коды Боуза-Чоудхури-Хоквингема (БЧХ) представляют собой обширный класс кодов, способных исправлять несколько ошибок и занимающих заметное место в теории и практике кодирования. Интерес к кодам БЧХ определяется по меньшей мере следующими четырьмя обстоятельствами: 1) среди кодов БЧХ при небольших длинах существуют хорошие (но, как правило, не лучшие из известных) коды; 2) известны относительно простые и конструктивные методы их кодирования и декодирования (хотя если единственным критерием является простота, то предпочтение следует отдать другим кодам); 3) коды Рида-Соломона, являющиеся широко известным подклассом недвоичных кодов, обладают определенными оптимальными свойствами и прозрачной весовой структурой; 4) полное понимание кодов БЧХ, по всей видимости, является наилучшей отправной точкой для изучения многих других классов кодов.

В этой главе мы будем говорить о кодах БЧХ во временном представлении. Это будет отражать исторически первый подход к изучению кодов БЧХ. В гл. 8 мы изложим те же самые идеи при помощи частотной интерпретации полей Галуа.

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

7.1. ОПРЕДЕЛЕНИЕ КОДОВ БЧХ

Порождающий многочлен циклического кода можно представить в виде

где минимальные многочлены корней

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

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

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

Таким образом,

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

Для произвольного циклического кода с порождающим многочленом имеющим корни определим компоненты синдрома

Эти элементы поля отличны от синдромного многочлена но содержат эквивалентную информацию. Мы хотим подобрать так, чтобы по можно было найти ошибок. Вскоре мы докажем, что если а — примитивный элемент поля то таким множеством является

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

1) выберем примитивный многочлен степени и построим поле

2) найдем минимальные многочлены для

3) положим в

В следующем параграфе, подробно описав алгоритм декодирования, мы докажем, что такой циклический код может исправлять ошибок. Иногда построенные таким образом коды БЧХ могут исправлять более ошибок. Поэтому величина

называется конструктивным расстоянием кода. Истинное минимальное расстояние кода может быть больше, конструктивного.

В табд 7.1 задано представление поля как расширение поля построенное но примитивному многочлену в нее включены также минимальные многочлены для всех элементов из поля где примитивный элемент Заметим, что минимальные многочлены любой четной степени а всегда уже содержатся в одной из предыдущих строк таблицы. Это следствие теоремы 5.3.4, которая утверждает, что элементы для любых имеют одинаковые минимальные многочлены над полем GF (2). Данный факт немного поможет нам при вычислении

Порождающий многочлен для исправляющею две ошибки кода БЧХ длины 15 получается следующим образом

Таблица 7.1 (см. скан) Представления поля

Поскольку степень равна Отсюда мы получили порождающий многочлен -кода БЧХ, исправляющего 2 ошибки. Отметим, что коды БЧХ строятся по заданным Значение не известно, пока не найден

Тем же способом мы можем построить порождающий многочлен для другого примитивного кода БЧХ длины 15.

Пусть

Получился порождающий многочлен для -кода БЧХ, исправляющего три ошибки.

Пусть

Получился порождающий многочлен для -кода БЧХ. Это простой код с повторением, исправляющийсемь ошибок.

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

В табл. 7.2 приведено представление поля как расширение поля построенное по примитивному многочлену Эта таблица содержит также минимальные многочлены над для всех элементов из поля где а примитивный элемент.

Порождающий многочлен для исправляющего одиночные ошибки кода длины 15 находится следующим образом:

Получился порождающий многочлен для -кода БЧХ над исправляющего одиночные ошибки. Этим кодом последовательность II четверичных символов (что эквивалентно

Таблица 7.2 (см. скан) Представления поля

там) кодируется в последовательность 15 четверичных символов. Такой код не является кодом Хэмминга.

Таким же образом мы можем найти порождающие многочлены для других кодов БЧХ над длины 15.

Пусть

Получился порождающий многочлен для -кода БЧХ над исправляющего две ошибки.

Пусть

Это дает -код БЧХ над исправляющий три ошибки. Пусть

Это дает -код БЧХ над исправляющий четыре ошибки.

Пусть

Это дает -код БЧХ над исправляющий пять ошибок. Пусть :

Получается -код БЧХ над исправляющий шесть ошибок. Это простой код с повторением, который в действительности исправляет семь ошибок

Теперь мы дадим формальное определение кода БЧХ. Оно будет более общим, чем данное выше определение примитивного кода БЧХ, так как в качестве корней будут браться последовательных степеней произвольного элемента ноля (не обязательно примитивного элемента). Длина кода будет равна порядку элемента такому наименьшему для которого

Определение Пусть заданы и пусть любой элемент порядка Тогда для любого положительного целого числа и любого целого числа соответствующий код БЧХ является циклическим кодом длины с порождающим многочленом

где - минимальный многочлен элемента

Часто выбирают что, как правило, (но не всегда), приводит к многочлену с наименьшей степенью. Обычно требуется большая длина кода, и тогда выбирается элемент поля с наибольшим порядком, т. е. примитивный элемент.