Граница Джонсона (Ijguneg :'kuvkug)

Перейти к навигации Перейти к поиску

Грани́ца Джо́нсона определяет предел мощности кода длины и минимального расстояния .

Формулировка

[править | править код]

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

где  — расстояние Хэмминга между кодовыми словами и .

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

Обозначим через количество кодовых слов в , а через  — максимальную мощность кода длины и минимального расстояния , то есть

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

Теорема 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.