9.2. ИСТИННОЕ МИНИМАЛЬНОЕ РАССТОЯНИЕ КОДА БЧХ

Первые три теоремы устанавливают, что при известных условиях истинное минимальное расстояние кода БЧХ равно его конструктивному расстоянию Последняя теорема описывает верхнюю границу истинного минимального расстояния для произ вольного кода БЧХ Первые два результата являются очень простыми

Теорема 2 (Фарр) Минимальное расстояние двоичного кода БЧХ длины с конструктивным расстоянием равно если

или

Доказательство По следствию 17 гл 8 минимальное расстояние нечетно Предположим, что Размерность кода больше или равна так что согласно границе сферической упаковки

Но это противоречит (9 3) Условие выводится из путем непосредственных вычислений, которые мы опускаем

Пример Пусть Тогда легко проверить, что

Таким образом, коды длины действительно имеют минимальное расстояние как показано на рис. 9.1

Теорема 3 (Питерсон) Если то минимальное расстояние двоичного (не обязательно примитивного) кода БЧХ "V длины и конструктивным расстоянием а равно точно а.

Рис. 9.1. (см. скан) Таблица кодов нижняя граница для

Доказательство. Пусть а — примитивный корень степени из единицы, так что для Так как то элементы не являющиеся корнями многочлена являются корнями многочлена Последний многочлен и является словом веса а в коде

Пример. Минимальное расстояние кода блоковой длины 255 и конструктивным расстоянием 51 равно в точности 51.

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

Лемма 4. Пусть — некоторый многочлен над Многочлен является многочленом локаторов некоторого слова а, состоящего из нулей и единиц и принадлежащего коду БЧХ над GF(q) с конструктивным расстоянием в том и только в том случае, когда выполняются условия

Корни многочлена являются различными корнями степени из единицы.

(ii). Если степень простого числа то коэффициенты справны нулю для всех лежащих в интервале и не делящихся на

Доказательство. Если многочлен локаторов вектора а, удовлетворяющего условиям леммы, то для —1.

Тогда результат вытекает из упражнения (53) гл. 8. С другой стороны, предположим, что выполнены условия (i) и (ii), и пусть элементы, обратные корням многочлена Тогда вектор а, содержащий единицы на позициях с этими локаторами, удовлетворяет равенствам для всех —1 (опять согласно упражнению следовательно, принадлежит коду БЧХ.

Мы используем эту лемму для доказательства теоремы.

Теорема 5. Минимальное расстояние кода БЧХ длины и конструктивным расстоянием над полем равно

Доказательство. Мы укажем кодовое слово веса Пусть -мерное подпространство поля По лемме 21 гл. 4

— линеаризованный многочлен над Рассмотрим вектор а, локаторами которого являются все ненулевые элементы (5 из причем координаты на позициях с этими локаторами равны 1. Многочлен локаторов такого вектора а равен:

где если не равно для Согласно лемме 9.4 вектор а принадлежит коду БЧХ с конструктивным расстоянием и его минимальный вес равен

Пример. Пусть т. е. рассмотрим код БЧХ с длиной и конструктивным расстоянием 3. Этот код является [7, 4, 3]-кодом Хэмминга. Как видно из доказательства теоремы, этот код содержит векторы инцидентности всех линий проективной плоскости над (см. рис. 2.12 и уравнение (24) гл. 2), и, следовательно, его истинное минимальное расстояние равно 3.

Теорема 6. Истинное минимальное расстояние кода БЧХ над GF(q) с конструктивным расстоянием не превосходит

Доказательство. Определим условием Так как коды БЧХ вложены друг в друга, то содержит код с конструктивным расстоянием и согласно предыдущей теореме истинное минимальное расстояние этого кода равно Следовательно,

Хотя известно большое число результатов типа теорем 2, 3, 5 данной главы (см. замечания в конце главы), однако следующая задача остается нерешенной до сих пор.

Задача (нерешенная). (9.1). Найти необходимые и достаточные условия, которым должны удовлетворять и конструктивное расстояние для того, чтобы минимальное расстояние кода было равно 6.

Задача нахождения точного значения для в случае, когда представляется еще более тяжелой.