Грани́ца Джо́нсона определяет предел мощности кода длины
и минимального расстояния
.
Пусть
—
-чный код длины
над полем
или, другими словами, подмножество
. Пусть
— минимальное расстояние кода
, то есть
![{\displaystyle d=\min _{x,y\in C,\;x\neq y}{\mathsf {d}}(x,y)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1046523e6a64ac873bd5c5cb754a468545032d96)
где
— расстояние Хэмминга между кодовыми словами
и
.
Пусть
— множество всех
-чных кодов длины
и минимального расстояния
и пусть
обозначает подмножество всех равновесных кодов в
, иными словами, всех кодов, вес всех кодовых слов которых равен
.
Обозначим через
количество кодовых слов в
, а через
— максимальную мощность кода длины
и минимального расстояния
, то есть
![{\displaystyle A_{q}(n,d)=\max _{C\in C_{q}(n,d)}|C|.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e505cd59d8c6cd8a9bf6d0e15da80e0ac5a5d731)
Похожим образом определим
как максимальную мощность кода в
:
![{\displaystyle A_{q}(n,d,w)=\max _{C\in C_{q}(n,d,w)}|C|.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e8d3f4dbf158385f0d349a8604eb952beccd5ea4)
Теорема 1 (Граница Джонсона для
):
При
![{\displaystyle A_{q}(n,d)\leq {\frac {q^{n}}{\sum _{i=0}^{t}{n \choose i}(q-1)^{i}+{\frac {{n \choose t+1}-{d \choose t}A_{q}(n,d,d)}{A(n,d,t+1)}}(q-1)^{t+1}}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d1d9aa60e9a9330eaa48ed4345f5cf9c5da41557)
Примечание: для нахождения верхней границы на
для чётных значений
можно воспользоваться следующим равенством
![{\displaystyle A_{q}(n,2t)=A_{q}(n-1,2t-1).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2ca7d60528b84f2ffe23923ebce8e79de076e53e)
Теорема 2 (Граница Джонсона для
):
При
![{\displaystyle A_{q}(n,d,w)=1.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7798934790d16b76eec556babb577c7d6cdfe06e)
При
пускай
, а также
, тогда
![{\displaystyle A_{q}(n,d,w)\leq \lfloor {\frac {nq^{*}}{w}}\lfloor {\frac {(n-1)q^{*}}{w-1}}\lfloor \cdots \lfloor {\frac {(n-w+t)q^{*}}{t}}\rfloor \cdots \rfloor \rfloor ,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e331e7de2fdde4520a1465429e94e98056c9afdd)
где оператор
обозначает целую часть числа.
Примечание: подставляя границу теоремы 2 в теорему 1, мы получим верхнюю границу для
.
Пусть
— код длины
, мощности
с минимальным расстоянием
, содержащий нулевой вектор. Обозначим через
множество векторов, находящихся на расстоянии
от кода
, то есть
![{\displaystyle S_{i}=\left\lbrace u\in F^{n}:\forall v\in C\ d(u,v)\geq i\wedge \exists w\in C\ d(w,u)=i\right\rbrace .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/55eb5a461ec32fbacf4f730483d276e539d25f8e)
Таким образом,
. Тогда
, так как если бы нашёлся вектор, находящийся на расстоянии
или больше от кода
, то мы могли бы добавить его к
и получить код ещё большей мощности. Поскольку множества
не пересекаются, то отсюда следует граница сферической упаковки. Для получения же искомой границы оценим мощность
.
Выберем произвольное кодовое слово
и соответствующим сдвигом кода переведём его в начало координат. Кодовые слова веса
образуют равновесный код с минимальным расстоянием не менее
, и поэтому число кодовых слов веса
не превышает
.
Обозначим через
множество векторов
веса
. Любой вектор из
принадлежит либо
, либо
. Каждому кодовому слову
веса
соответствуют
векторов веса
, находящиеся от
на расстоянии
.
Все эти векторы различны и принадлежат множеству
. Следовательно,
![{\displaystyle |W_{t+1}\cap S_{t+1}|=|W_{t+1}|-|W_{t+1}\cap S_{t}|\geq {n \choose t+1}(q-1)^{t+1}-{d \choose t}(q-1)^{t+1}A_{q}(n,d,d).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/32b35f748fb6536ba1ac32d10b4c39230a29b4b0)
Вектор
из множества
находится на расстоянии
не более чем от
кодовых слов. Действительно, перенесём начало координат в точку
и подсчитаем, сколько кодовых слов может находиться от
на расстоянии
и иметь между собой расстояние Хэмминга
. Таковых по определению не должно быть больше
. Стало быть, векторы из множества
могут учитываться не более
раз, то есть каждому кодовому слову
соответствуют по крайней мере
![{\displaystyle {\frac {{n \choose t+1}-{d \choose t}A_{q}(n,d,d)}{A(n,d,t+1)}}(q-1)^{t+1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3efdd05a5470e13f4b845c3b798b71b47752505d)
различных векторов на расстоянии
от
.
- 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.