Русская Википедия:Граница Джонсона
Грани́ца Джо́нсона определяет предел мощности кода длины <math>n</math> и минимального расстояния <math>d</math>.
Формулировка
Пусть <math>C</math> — <math>q</math>-чный код длины <math>n</math> над полем <math>\mathbb{F} = \mathrm{GF}(q)</math> или, другими словами, подмножество <math>\mathbb{F}_q^n</math>. Пусть <math>d</math> — минимальное расстояние кода <math>C</math>, то есть
- <math>d = \min_{x,y \in C, \; x \neq y} \mathsf{d}(x,y)</math>
где <math>\mathsf{d}(x,y)</math> — расстояние Хэмминга между кодовыми словами <math>x</math> и <math>y</math>.
Пусть <math>C_q(n,d)</math> — множество всех <math>q</math>-чных кодов длины <math>n</math> и минимального расстояния <math>d</math> и пусть <math>C_q(n,d,w)</math> обозначает подмножество всех равновесных кодов в <math>C_q(n,d)</math>, иными словами, всех кодов, вес всех кодовых слов которых равен <math>w</math>.
Обозначим через <math>|C|</math> количество кодовых слов в <math>C</math>, а через <math>A_q(n,d)</math> — максимальную мощность кода длины <math>n</math> и минимального расстояния <math>d</math>, то есть
- <math> A_q(n,d) = \max_{C \in C_q(n,d)} |C|.</math>
Похожим образом определим <math>A_q(n,d,w)</math> как максимальную мощность кода в <math>C_q(n,d,w)</math>:
- <math> A_q(n,d,w) = \max_{C \in C_q(n,d,w)} |C|.</math>
Теорема 1 (Граница Джонсона для <math>A_q(n,d)</math>):
При <math>d=2t+1</math>
- <math> 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} }. </math>
Примечание: для нахождения верхней границы на <math> A_q(n,d)</math> для чётных значений <math>d=2t</math> можно воспользоваться следующим равенством
- <math> A_q(n,2t) = A_q(n-1,2t-1). </math>
Теорема 2 (Граница Джонсона для <math>A_q(n,d,w)</math>):
При <math>d > 2w</math>
- <math> A_q(n,d,w) = 1.</math>
При <math>d \leq 2w</math> пускай <math>t = \lceil \frac{d}{2}\rceil</math>, а также <math>q^* = q - 1</math>, тогда
- <math> 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, </math>
где оператор <math>\lfloor ~~ \rfloor</math> обозначает целую часть числа.
Примечание: подставляя границу теоремы 2 в теорему 1, мы получим верхнюю границу для <math>A_q(n,d)</math>.
Доказательство первой теоремы
Пусть <math>C</math> — код длины <math>n</math>, мощности <math>M = A_q(n, d)</math> с минимальным расстоянием <math>d = 2t + 1</math>, содержащий нулевой вектор. Обозначим через <math>S_i</math> множество векторов, находящихся на расстоянии <math>i</math> от кода <math>C</math>, то есть
- <math>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.</math>
Таким образом, <math>S_0 = C</math>. Тогда <math>S_0 \cup S_1 \cup \dots \cup S_{d - 1} = F^n</math>, так как если бы нашёлся вектор, находящийся на расстоянии <math>d</math> или больше от кода <math>C</math>, то мы могли бы добавить его к <math>C</math> и получить код ещё большей мощности. Поскольку множества <math>S_0, S_1, S_2, \dots, S_t</math> не пересекаются, то отсюда следует граница сферической упаковки. Для получения же искомой границы оценим мощность <math>S_{t + 1}</math>.
Выберем произвольное кодовое слово <math>P</math> и соответствующим сдвигом кода переведём его в начало координат. Кодовые слова веса <math>d = 2t + 1</math> образуют равновесный код с минимальным расстоянием не менее <math>2t + 1</math>, и поэтому число кодовых слов веса <math>d</math> не превышает <math>A_q(n, 2t + 1, 2t + 1) = A_q(n, d, d)</math>.
Обозначим через <math>W_{t + 1}</math> множество векторов <math>F^n</math> веса <math>t + 1</math>. Любой вектор из <math>W_{t + 1}</math> принадлежит либо <math>S_t</math>, либо <math>S_{t + 1}</math>. Каждому кодовому слову <math>Q</math> веса <math>d</math> соответствуют <math>{ d \choose t }</math> векторов веса <math>t + 1</math>, находящиеся от <math>Q</math> на расстоянии <math>t</math>.
Все эти векторы различны и принадлежат множеству <math>W_{t + 1} \cap S_t</math>. Следовательно,
- <math>|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).</math>
Вектор <math>R</math> из множества <math>W_{t + 1} \cap S_{t+1}</math> находится на расстоянии <math>t+1</math> не более чем от <math>A_q(n,d,t+1)</math> кодовых слов. Действительно, перенесём начало координат в точку <math>R</math> и подсчитаем, сколько кодовых слов может находиться от <math>R</math> на расстоянии <math>t + 1</math> и иметь между собой расстояние Хэмминга <math>d</math>. Таковых по определению не должно быть больше <math>A_q(n,d,t+1)</math>. Стало быть, векторы из множества <math>W_{t + 1} \cap S_{t+1}</math> могут учитываться не более <math>A_q(n,d,t+1)</math> раз, то есть каждому кодовому слову <math>P</math> соответствуют по крайней мере
- <math>\frac{{n \choose t+1} - {d \choose t} A_q(n,d,d)}{A(n,d,t+1)}(q - 1)^{t + 1}</math>
различных векторов на расстоянии <math>t+1</math> от <math>P</math>.
Литература
- 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.
См. также
