Граница Джонсона
Грани́ца Джо́нсона определяет предел мощности кода длины и минимального расстояния .
Формулировка
Пусть — -чный код длины над полем или, другими словами, подмножество . Пусть — минимальное расстояние кода , то есть
где — расстояние Хэмминга между кодовыми словами и .
Пусть — множество всех -чных кодов длины и минимального расстояния и пусть обозначает подмножество всех равновесных кодов в , иными словами, всех кодов, вес всех кодовых слов которых равен .
Обозначим через количество кодовых слов в , а через — максимальную мощность кода длины и минимального расстояния , то есть
Похожим образом определим как максимальную мощность кода в :
Теорема 1 (Граница Джонсона для ):
При
Примечание: для нахождения верхней границы на для чётных значений можно воспользоваться следующим равенством
Теорема 2 (Граница Джонсона для ):
При
При пускай , а также , тогда
где оператор обозначает целую часть числа.
Примечание: подставляя границу теоремы 2 в теорему 1, мы получим верхнюю границу для .
Доказательство первой теоремы
Пусть — код длины , мощности с минимальным расстоянием , содержащий нулевой вектор. Обозначим через множество векторов, находящихся на расстоянии от кода , то есть
Таким образом, . Тогда , так как если бы нашёлся вектор, находящийся на расстоянии или больше от кода , то мы могли бы добавить его к и получить код ещё большей мощности. Поскольку множества не пересекаются, то отсюда следует граница сферической упаковки. Для получения же искомой границы оценим мощность .
Выберем произвольное кодовое слово и соответствующим сдвигом кода переведём его в начало координат. Кодовые слова веса образуют равновесный код с минимальным расстоянием не менее , и поэтому число кодовых слов веса не превышает .
Обозначим через множество векторов веса . Любой вектор из принадлежит либо , либо . Каждому кодовому слову веса соответствуют векторов веса , находящиеся от на расстоянии .
Все эти векторы различны и принадлежат множеству . Следовательно,
Вектор из множества находится на расстоянии не более чем от кодовых слов. Действительно, перенесём начало координат в точку и подсчитаем, сколько кодовых слов может находиться от на расстоянии и иметь между собой расстояние Хэмминга . Таковых по определению не должно быть больше . Стало быть, векторы из множества могут учитываться не более раз, то есть каждому кодовому слову соответствуют по крайней мере
различных векторов на расстоянии от .
Литература
- S. Johnson, A new upper bound for error correcting codes, IRE Transactions on Information Theory, 203–207, April 1962.
- F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Amsterdam, Netherlands, North-Holland, § 17.2, § 17.3, 1977.
- W. C. Huffman, V. Pless, Fundamentals of Error-Correcting Codes, Cambridge University Press, 2003.