Грани́ца Джо́нсона определяет предел мощности кода длины
и минимального расстояния
.
Формулировка
Пусть
—
-чный код длины
над полем
или, другими словами, подмножество
. Пусть
— минимальное расстояние кода
, то есть

где
— расстояние Хэмминга между кодовыми словами
и
.
Пусть
— множество всех
-чных кодов длины
и минимального расстояния
и пусть
обозначает подмножество всех равновесных кодов в
, иными словами, всех кодов, вес всех кодовых слов которых равен
.
Обозначим через
количество кодовых слов в
, а через
— максимальную мощность кода длины
и минимального расстояния
, то есть

Похожим образом определим
как максимальную мощность кода в
:

Теорема 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.
См. также