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

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

Формулировка[править | править код]

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

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

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

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

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

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

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

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

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

При ${\displaystyle d=2t+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}}}.}$

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

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

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

При ${\displaystyle d>2w}$

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

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

${\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 ,}$

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

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

Доказательство первой теоремы[править | править код]

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

${\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 .}$

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

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

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

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

${\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).}$

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

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

различных векторов на расстоянии ${\displaystyle t+1}$ от ${\displaystyle 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.

См. также[править | править код]

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