17.5. ГРАНИЦА ГРАЙСМЕРА

Для линейного -кода граница Синглтона (17.45) утверждает, что Граница Грайсмера, задаваемая выражением (17.52), увеличивает правую часть этого неравенства. Лучше всего привести эту границу, используя величину минимально возможную длину двоичного линейного кода размерности с минимальным расстоянием

Теорема 23.

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

где матрица имеет ранг в противном случае мы бы обратили в нуль первую строку матрицы и минимальное расстояние кода было бы меньше чем

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

и, складывая эти неравенства, получаем, что или . Следовательно,

Теорема 24. (Граница Грайсмера [562]; см. также работу Соломона и Стиффлера [1257].)

Доказательство. Многократно применяя теорему 23, находим, что

Примеры. (1). Найдем число т. е. самый короткий код размерности 5, исправляющий три ошибки. Согласно теореме 24

В действительности существует -код БЧХ, и поэтому

(2). Если то из теоремы 24 вытекает, что

На самом деле симплексный (см. гл. 1) показывает, что эта граница достигается.