ГЛАВА 7

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

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

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

Мы сначала определим исправляющие t ошибок коды БЧХ над GF (q) длины q"" - 1, задавая порождающий многочлен g (х). Коды такой длины называют примитивными кодами БЧХ. Мы докажем, что эти коды исправляют t ошибок, построив в явном виде алгоритм декодирования. Затем мы обобщим наши рассуждения на случай кодов БЧХ, длина которых является делителем q - I.

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

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

g (х) = НОК [fi (х), h (х), .... fr (х)1 где fi{x), /г () - минимальные многочлены корней g (х).

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

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

у (х) = с (х) + е (х).

Мы можем вычислить значение этого многочлена на элементах из GF (q); в частности, нас будут интересовать значения многочлена в точках, являющихся корнями g (х), скажем в точках 7i, Уг- Тогда поскольку с (yj) = О для любых yj, являющихся корнями g (х), то

* V {yj) = с iyj) + е [yj) = е (yj). Таким образом,

v{yi)= £ еу), /= 1, . . ., г,

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

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

5j = V (yj), j = 1, г.

Эти элементы поля отличны от синдромного многочлена s (х), но содержат эквивалентную информацию. Мы хотим подобрать У1, Уг так, чтобы по 5i, 5 можно было найти t ошибок. Вскоре мы докажем, что если а - примитивный элемент поля GF (q"), то таким множеством является

а, «2, а, а\.

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

1) выберем примитивный многочлен степени т и построим поле GF {q");

2) найдем минимальные многочлены fj{x) для af, /= 1, 3) положим g (х) = ЯОК Ih {X), W I.

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

d = 2t + \

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

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

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

g {X) = НОК [h W, к {X), и W, f4 ix) ] -

= НОК [х + х + 1, X* -\-х -\-\, X* + -fx=*+x2-fx-fl, х*+х+1] =

Таблица 7.1

Представления поля GF (2)