14.2. 1-укорочение кода (выбрасывание проверочных символов)
Любой код можно 1-укоротить путем выбрасывания проверочных символов, причем минимальный вес
-укороченного кода будет значительно меньше минимального веса исходного кода, если только не позаботиться о хорошем выборе оставляемых проверочных
символов. В общем случае вес каждого слова исходного кода уменьшается на вес выбрасываемых символов. Следовательно,
-укорочение линейного кода с минимальным весом d на
позиций приводит к
-укороченному коду с минимальным весом
Минимальный вес
-укороченного кода больше
тогда и только тогда, когда в исходном коде ни одно из слов веса d не содержит единиц во всех выбрасываемых позициях.
Соломон и Стиффлер [1965] показали, что при достаточно малых скоростях хорошие линейные коды могут быть получены путем
-укорочения регистровых кодов максимальной длины. Например, рассмотрим двоичный регистровый код максимальной длины с блоковой длиной 31 и порождающей матрицей
Нулевой вектор и 31 столбец этой матрицы образуют
-мерное векторное пространство над
Множество из трех столбцов, отмеченных буквой X, и нуль-вектор образуют в нем
-мерное подпространство, а множество из семи столбцов, отмеченных буквой У, и нуль-вектор —
-мерное подпространство этого пространства. Каждое слово исходного кода или не содержит ни одной единицы, или имеет две единицы в позициях, отмеченных буквой X, и не имеет ни одной, либо имеет четыре единицы в позициях, отмеченных буквой У. Вообще, любое кодовое слово регистрового кода максимальной длины с блоковой длиной
не содержит ни одной единицы, либо имеет
единиц в
позициях, соответствующих ненулевым точкам
-мерного подпространства. Следовательно, если выбросить из регистрового кода максимальной длины точки, соответствующие линейно независимым подпространствам размерностей
где
то блоковая длина и минимальное расстояние изменяется в соответствии с формулами
Например, если выбросить из матрицы (14.21) позиции, отмеченные буквами
то получим укороченный код с блоковой длиной
,
минимальным расстоянием 10 и порождающей матрицей
Используя границу Грисмера, Соломон и Стиффлер показали, что каждый линейный код, полученный выбрасыванием подпространств различных размерностей из регистрового кода максимальной длины, является оптимальным в том смысле, что никакой линейный код с тем же числом кодовых слов и тем же минимальным расстоянием не может иметь меньшую блоковую длину.
Процедура
-укорочения, предложенная Соломоном и Стиффлером, позволяет построить многие оптимальные коды, но в силу ограничения (14.22) все эти коды обладают малой скоростью или малой блоковой длиной.