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

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

ФормулировкаПравить

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

$d=\underset{x,y\in <!--\; \in \; -->C,x\ne <!--\; \ne \; -->y}{min}\mathsf{d}(x,y)$$d = \min_{x,y \in C, \; x \neq y} \mathsf{d}(x,y)$ 

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

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

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

$A_q(n,d)=\underset{C\in <!--\; \in \; -->C_q(n,d)}{max}|C|.$$A_q(n,d) = \max_{C \in C_q(n,d)} |C|.$ 

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

$A_q(n,d,w)=\underset{C\in <!--\; \in \; -->C_q(n,d,w)}{max}|C|.$$A_q(n,d,w) = \max_{C \in C_q(n,d,w)} |C|.$ 

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

При $d=2t+1$$d=2t+1$ 

$A_q(n,d)\le <!--\; \le \; -->\frac{q^n}{\underset{i=0}{\overset{t}{\sum <!--\; \sum \; -->}}(\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) \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)$$A_q(n,d)$  для чётных значений $d=2t$$d=2t$  можно воспользоваться следующим равенством

$A_q(n,2t)=A_q(n-<!--\; -\; -->1,2t-<!--\; -\; -->1).$$A_q(n,2t) = A_q(n-1,2t-1).$ 

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

При $d>2w$$d > 2w$ 

$A_q(n,d,w)=1.$$A_q(n,d,w) = 1.$ 

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

$A_q(n,d,w)\le <!--\; \le \; -->\lfloor <!--\; \lfloor \; -->\frac{n{q}^{\ast <!--\; \ast \; -->}}{w}\lfloor <!--\; \lfloor \; -->\frac{(n-<!--\; -\; -->1)q^{\ast <!--\; \ast \; -->}}{w-<!--\; -\; -->1}\lfloor <!--\; \lfloor \; -->\cdots <!--\; \cdots \; -->\lfloor <!--\; \lfloor \; -->\frac{(n-<!--\; -\; -->w+t)q^{\ast <!--\; \ast \; -->}}{t}\rfloor <!--\; \rfloor \; -->\cdots <!--\; \cdots \; -->\rfloor <!--\; \rfloor \; -->\rfloor <!--\; \rfloor \; -->,$$A_q(n,d,w) \leq \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 <!--\; \lfloor \; -->\rfloor <!--\; \rfloor \; -->$$\lfloor ~~ \rfloor$  обозначает целую часть числа.

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

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

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

$S_i=\left\{u\in <!--\; \in \; -->F^n:\mathrm{\forall <!--\; \forall \; -->}v\in <!--\; \in \; -->Cd(u,v)\ge <!--\; \ge \; -->i\wedge <!--\; \wedge \; -->\mathrm{\exists <!--\; \exists \; -->}w\in <!--\; \in \; -->Cd(w,u)=i\right\}.$$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 = C$ . Тогда $S_0\cup <!--\; \cup \; -->S_1\cup <!--\; \cup \; -->\cdots <!--\; \cdots \; -->\cup <!--\; \cup \; -->S_{d-<!--\; -\; -->1}=F^n$$S_0 \cup S_1 \cup \dots \cup S_{d - 1} = F^n$ , так как если бы нашёлся вектор, находящийся на расстоянии $d$$d$  или больше от кода $C$$C$ , то мы могли бы добавить его к $C$$C$  и получить код ещё большей мощности. Поскольку множества $S_0,S_1,S_2,\dots <!--\; \dots \; -->,S_t$$S_0, S_1, S_2, \dots, S_t$  не пересекаются, то отсюда следует граница сферической упаковки. Для получения же искомой границы оценим мощность $S_{t+1}$$S_{t + 1}$ .

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

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

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

$|W_{t+1}\cap <!--\; \cap \; -->S_{t+1}|=|W_{t+1}|-<!--\; -\; -->|W_{t+1}\cap <!--\; \cap \; -->S_t|\ge <!--\; \ge \; -->(\genfrac{}{}{0ex}{}{n}{t+1})(q-<!--\; -\; -->1{)}^{t+1}-<!--\; -\; -->(\genfrac{}{}{0ex}{}{d}{t})(q-<!--\; -\; -->1{)}^{t+1}{A}_q(n,d,d).$$|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$$R$  из множества $W_{t+1}\cap <!--\; \cap \; -->S_{t+1}$$W_{t + 1} \cap S_{t+1}$  находится на расстоянии $t+1$$t+1$  не более чем от $A_q(n,d,t+1)$$A_q(n,d,t+1)$  кодовых слов. Действительно, перенесём начало координат в точку $R$$R$  и подсчитаем, сколько кодовых слов может находиться от $R$$R$  на расстоянии $t+1$$t + 1$  и иметь между собой расстояние Хэмминга $d$$d$ . Таковых по определению не должно быть больше $A_q(n,d,t+1)$$A_q(n,d,t+1)$ . Стало быть, векторы из множества $W_{t+1}\cap <!--\; \cap \; -->S_{t+1}$$W_{t + 1} \cap S_{t+1}$  могут учитываться не более $A_q(n,d,t+1)$$A_q(n,d,t+1)$  раз, то есть каждому кодовому слову $P$$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}$$\frac{{n \choose t+1} - {d \choose t} A_q(n,d,d)}{A(n,d,t+1)}(q - 1)^{t + 1}$ 

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

См. такжеПравить

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