14.2. 1-укорочение кода (выбрасывание проверочных символов)

Любой код можно 1-укоротить путем выбрасывания проверочных символов, причем минимальный вес -укороченного кода будет значительно меньше минимального веса исходного кода, если только не позаботиться о хорошем выборе оставляемых проверочных

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

Соломон и Стиффлер [1965] показали, что при достаточно малых скоростях хорошие линейные коды могут быть получены путем -укорочения регистровых кодов максимальной длины. Например, рассмотрим двоичный регистровый код максимальной длины с блоковой длиной 31 и порождающей матрицей

Нулевой вектор и 31 столбец этой матрицы образуют -мерное векторное пространство над Множество из трех столбцов, отмеченных буквой X, и нуль-вектор образуют в нем -мерное подпространство, а множество из семи столбцов, отмеченных буквой У, и нуль-вектор — -мерное подпространство этого пространства. Каждое слово исходного кода или не содержит ни одной единицы, или имеет две единицы в позициях, отмеченных буквой X, и не имеет ни одной, либо имеет четыре единицы в позициях, отмеченных буквой У. Вообще, любое кодовое слово регистрового кода максимальной длины с блоковой длиной не содержит ни одной единицы, либо имеет единиц в позициях, соответствующих ненулевым точкам -мерного подпространства. Следовательно, если выбросить из регистрового кода максимальной длины точки, соответствующие линейно независимым подпространствам размерностей где

то блоковая длина и минимальное расстояние изменяется в соответствии с формулами

Например, если выбросить из матрицы (14.21) позиции, отмеченные буквами то получим укороченный код с блоковой длиной ,

минимальным расстоянием 10 и порождающей матрицей

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

Процедура -укорочения, предложенная Соломоном и Стиффлером, позволяет построить многие оптимальные коды, но в силу ограничения (14.22) все эти коды обладают малой скоростью или малой блоковой длиной.