Глава 12. Нахождение числа информационных символов в БЧХ-кодах

12.1. Сведение задачи к перечислению некоторых чисел по модулю n

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

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

Предыдущие замечания справедливы для всех циклических кодов.

Любой -ичный БЧХ-код с блоковой длиной над может быть определен как циклический код, корнями порождающего многочлена которого являются и сопряженные с ними. Этот код исправляет по крайней мере ошибок (см. гл. 10) и минимальное расстояние Хэмминга такого кода равно по меньшей мере Поэтому d называется конструктивным расстоянием кода (или -границей).

Первым результатом о числе информационных символов в БЧХ-коде является следующая лемма:

12.11. Лемма. Пусть число информационных символов -ичного БЧХ-кода с блоковой длиной и конструктивным расстоянием Определим уравнениями

Тогда число таких чисел что для всех к.

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

Наоборот, -корень проверочного многочлена для БХЧ-кода тогда и только тогда, когда для всех к.

Лемма 12.11 позволяет определить число информационных позиций БЧХ-кода, не производя специальных вычислений в поле или его расширениях. Надо только вычислить некоторые типы классов вычетов Однако практически такое вычисление очень трудоемко, особенно, когда велики.

Для получения более обозримых результатов при больших эту лемму удобно переформулировать в следующем виде:

12.12. Лемма. Пусть число информационных символов в -ичном БЧХ-коде с блоковой длиной и конструктивным расстоянием Определим уравнениями

Тогда число таких чисел что для всех

Доказательство, для всех тогда и только тогда, когда для всех к. Положим