13.3. Границы d <= n+1-k

Как было показано в разд. 1.2, каждый линейный код с длиной и размерностью к может быть задан с помощью проверочной матрицы с столбцами и к линейно независимыми строками. Если к этой матрице дописать k-1 дополнительных строк, представляющих собой -мерные единичные векторы, то получится проверочная матрица некоторого подкода исходного кода. Этот линейный подкод ненулевой размерности состоит из тех кодовых слов, у которых в соответствующих k-1 позициях расположены нули. Так как ненулевые координаты в словах этого подкода расположены только в позициях, то для кодового расстояния выполняется неравенство

Это неравенство сохраняется также и для исходного кода.

Рассмотрим теперь коды, для которых

Такие коды мы будем называть кодами с достижимым максималъ расстоянием. Коды этого класса обладают и другими свойствами. Для любых заданных d позиций такой код должен содержать кодовых слов веса все ненулевые символы которых расположены в заданных d позициях. Размерность подкода, состоящего из этих слов, равна 1; размерность объемлющего подкода, состоящего из кодовых слов, содержащих в произвольных заданных позициях нули равна

Любой код, удовлетворяющий условию (13.32), имеет точно одно слово веса содержащее символ 1 в произвольно заданной позиции, и ненулевые символы точно в других позициях; он содержит точно кодовых слов веса имеющих символ 1 в произвольно заданной позиции и ненулевые символы в каждой из наперед заданных позиций. Если бы какая-либо пара из этих к кодовых слов имела бы один и тот же ненулевой символ в одной и той же из фиксированных позиций, то разность этих слов дала бы кодовое слово веса Следовательно, к Таким образом,

Используя аналогичные рассуждения для дуального кода -1), Синглтон [1964] показал, что

Из соотношения (13.33) следует, что уравнение (13.32) не выполняется ни для одного двоичного кода, за исключением случаев (двоичный код с повторением) и (код с одной проверкой на четность). Однако для больших алфавитов известны нетривиальные коды, для которых выполняется равенство . Один из классов таких кодов дает теорема 13 35.

13.35. Теорема. Расстояние, блоковая длина и число информационных позиций любого кода Рида — Соломона (БЧХ-кода с связаны соотношением

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

Другие классы кодов с достижимым максимальным расстоянием были предложены Синглтоном [1964]. В разд. 16.5 будет показано, что для этих кодов удается полностью определить их весовую структуру.