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

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

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

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

$d=\underset{x,y\in C,x\ne y}{\min }𝖽(x,y)$

где $𝖽(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)=\underset{C\in C_q(n,d)}{\max }|C|.$

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

$A_q(n,d,w)=\underset{C\in C_q(n,d,w)}{\max }|C|.$

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

При $d=2t+1$

$A_q(n,d)\le \frac{q^n}{\sum _{i=0}^t(\genfrac{}{}{0ex}{}{n}{i})(q-1{)}^i+\frac{(\genfrac{}{}{0ex}{}{n}{t+1})-(\genfrac{}{}{0ex}{}{d}{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\le 2w$ пускай $t=\lceil \frac{d}{2}\rceil$, а также $q^{*}=q-1$, тогда

$A_q(n,d,w)\le \lfloor \frac{n{q}^{*}}{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=\{u\in F^n:\mathrm{\forall }v\in Cd(u,v)\ge i\wedge \mathrm{\exists }w\in Cd(w,u)=i\}.$

Таким образом, $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$ соответствуют $(\genfrac{}{}{0ex}{}{d}{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|\ge (\genfrac{}{}{0ex}{}{n}{t+1})(q-1{)}^{t+1}-(\genfrac{}{}{0ex}{}{d}{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{(\genfrac{}{}{0ex}{}{n}{t+1})-(\genfrac{}{}{0ex}{}{d}{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.

См. также

• Граница Синглтона
• Граница Хэмминга
• Граница Плоткина
• Граница Варшамова — Гилберта