Граница Джонсона

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

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

Пусть $C$ — $q$ -чный код длины $n$ над полем $\mathbb {F} =\mathrm {GF} (q)$ или, другими словами, подмножество $\mathbb {F} _{q}^{n}$ . Пусть $d$ — минимальное расстояние кода $C$ , то есть

d=\min _{x,y\in C,\;x\neq y}{\mathsf {d}}(x,y)

где ${\mathsf {d}}(x,y)$ — расстояние Хэмминга между кодовыми словами $x$ и $y$ .

Пусть $C_{q}(n,d)$ — множество всех $q$ -чных кодов длины $n$ и минимального расстояния $d$ и пусть $C_{q}(n,d,w)$ обозначает подмножество всех равновесных кодов в $C_{q}(n,d)$ , иными словами, всех кодов, вес всех кодовых слов которых равен $w$ .

Обозначим через $|C|$ количество кодовых слов в $C$ , а через $A_{q}(n,d)$ — максимальную мощность кода длины $n$ и минимального расстояния $d$ , то есть

A_{q}(n,d)=\max _{C\in C_{q}(n,d)}|C|.

Похожим образом определим $A_{q}(n,d,w)$ как максимальную мощность кода в $C_{q}(n,d,w)$ :

A_{q}(n,d,w)=\max _{C\in C_{q}(n,d,w)}|C|.

Теорема 1 (Граница Джонсона для $A_{q}(n,d)$ ):

При $d=2t+1$

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}}}.

Примечание: для нахождения верхней границы на $A_{q}(n,d)$ для чётных значений $d=2t$ можно воспользоваться следующим равенством

A_{q}(n,2t)=A_{q}(n-1,2t-1).

Теорема 2 (Граница Джонсона для $A_{q}(n,d,w)$ ):

При $d>2w$

A_{q}(n,d,w)=1.

При $d\leq 2w$ пускай $t=\lceil {\frac {d}{2}}\rceil$ , а также $q^{*}=q-1$ , тогда

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 ,

где оператор $\lfloor ~~\rfloor$ обозначает целую часть числа.

Примечание: подставляя границу теоремы 2 в теорему 1, мы получим верхнюю границу для $A_{q}(n,d)$ .

Доказательство первой теоремы

Пусть $C$ — код длины $n$ , мощности $M=A_{q}(n,d)$ с минимальным расстоянием $d=2t+1$ , содержащий нулевой вектор. Обозначим через $S_{i}$ множество векторов, находящихся на расстоянии $i$ от кода $C$ , то есть

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 .

Таким образом, $S_{0}=C$ . Тогда $S_{0}\cup S_{1}\cup \dots \cup S_{d-1}=F^{n}$ , так как если бы нашёлся вектор, находящийся на расстоянии $d$ или больше от кода $C$ , то мы могли бы добавить его к $C$ и получить код ещё большей мощности. Поскольку множества $S_{0},S_{1},S_{2},\dots ,S_{t}$ не пересекаются, то отсюда следует граница сферической упаковки. Для получения же искомой границы оценим мощность $S_{t+1}$ .

Выберем произвольное кодовое слово $P$ и соответствующим сдвигом кода переведём его в начало координат. Кодовые слова веса $d=2t+1$ образуют равновесный код с минимальным расстоянием не менее $2t+1$ , и поэтому число кодовых слов веса $d$ не превышает $A_{q}(n,2t+1,2t+1)=A_{q}(n,d,d)$ .

Обозначим через $W_{t+1}$ множество векторов $F^{n}$ веса $t+1$ . Любой вектор из $W_{t+1}$ принадлежит либо $S_{t}$ , либо $S_{t+1}$ . Каждому кодовому слову $Q$ веса $d$ соответствуют ${d \choose t}$ векторов веса $t+1$ , находящиеся от $Q$ на расстоянии $t$ .

Все эти векторы различны и принадлежат множеству $W_{t+1}\cap S_{t}$ . Следовательно,

|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).

Вектор $R$ из множества $W_{t+1}\cap S_{t+1}$ находится на расстоянии $t+1$ не более чем от $A_{q}(n,d,t+1)$ кодовых слов. Действительно, перенесём начало координат в точку $R$ и подсчитаем, сколько кодовых слов может находиться от $R$ на расстоянии $t+1$ и иметь между собой расстояние Хэмминга $d$ . Таковых по определению не должно быть больше $A_{q}(n,d,t+1)$ . Стало быть, векторы из множества $W_{t+1}\cap S_{t+1}$ могут учитываться не более $A_{q}(n,d,t+1)$ раз, то есть каждому кодовому слову $P$ соответствуют по крайней мере

{\frac {{n \choose t+1}-{d \choose t}A_{q}(n,d,d)}{A(n,d,t+1)}}(q-1)^{t+1}

различных векторов на расстоянии $t+1$ от $P$ .

Литература

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.

См. также