Граница Плоткина

Грани́ца Пло́ткина — в теории кодирования определяет предел мощности двоичного кодa длины $n$ и минимального расстояния $d$. Названа в честь американского математика Морриса Плоткина (1907—2003).

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

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

$d=\min_{\begin{smallmatrix}x,\;y\in C,\\x\neq y\end{smallmatrix}}d(x,\;y),$

где $d(x,\;y)$ — расстояние Хэмминга между $x$ и $y$. Выражение $A_2(n,\;d)$ обозначает максимально возможное количество кодовых слов в двоичном коде длины $n$ и минимального расстояния $d$. Граница Плоткина даёт верхний предел этого выражения.

Теорема (граница Плоткина):

1. Если $d$ — чётное число $2d>n$, то

$A_2(n,\;d)\leqslant 2\left\lfloor\frac{d}{2d-n}\right\rfloor.$

2. Если $d$ — нечётное число и $2d+1>n$, то

$A_2(n,\;d)\leqslant 2\left\lfloor\frac{d+1}{2d+1-n}\right\rfloor.$

3. Если $d$ — чётное число, то

$A_2(2d,\;d)\leqslant 4d.$

4. Если $d$ — нечётное число, то

$A_2(2d+1,\;d)\leqslant 4d+4,$

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

Доказательство первой части

Пусть $d(x,\;y)$ — расстояние Хэмминга между $x$ и $y$, а $M$ — мощность $C$. Найдём предел величины $\sum_{x,\;y\in C}d(x,\;y)$ двумя разными способами.

С одной стороны, всего есть $M$ разных возможностей для выбора $x$, и для каждой из них есть $M-1$ возможностей для выбора $y$. По определению $d(x,\;y)\geqslant d$ для всех $x$ и $y$, следовательно

$\sum_{x,\;y\in C}d(x,\;y)\geqslant M(M-1)d.$

С другой стороны, определим $A$ как матрицу размерности $M\times n$, строками которой будут элементы кода $C$. Если $s_i$ — количество нулей в столбце $i$ матрицы $A$, то столбец $i$ содержит $M-s_i$ единиц. Любые ноль и единица в одном и том же столбце добавляют ровно $2$ (так как $d(x,\;y)=d(y,\;x)$) к общей сумме $\sum_{x,\;y\in C}d(x,\;y)$, а значит

$\sum_{x,\;y\in C}d(x,\;y)=\sum_{i=1}^n 2s_i(M-s_i).$

При чётном $M$ величина в правой части равенства достигает максимума при $s_i=M/2$, что означает

$\sum_{x,\;y\in C}d(x,\;y)\leqslant\frac{1}{2}nM^2.$

Объединяя нижнюю и верхнюю границы выражения $\sum_{x,\;y\in C}d(x,\;y)$ в одно неравенство, получим

$M(M-1)d\leqslant\frac{1}{2}nM^2,$

что при условии $2d>n$ равнозначно

$M\leqslant\frac{2d}{2d-n}.$

Так как $M$ — чётное число, то

$M\leqslant 2\left\lfloor\frac{d}{2d-n}\right\rfloor.$

С другой стороны, если $M$ нечётное, то $\sum_{i=1}^n 2s_i(M-s_i)$ достигает максимума при $s_i=\frac{M\pm1}{2}$, откуда следует, что

$\sum_{x,\;y\in C}d(x,\;y)\leqslant\frac{1}{2}n(M^2-1).$

Объединяя нижнюю и верхнюю границы выражения $\sum_{x,\;y\in C}d(x,\;y)$ в одно неравенство, получим

$M(M-1)d\leqslant\frac{1}{2}n(M^2-1),$

что при условии $2d>n$ равнозначно

$M\leqslant\frac{2d}{2d-n}-1.$

Так как $M$ — целое число, то

$M\leqslant\left\lfloor\frac{2d}{2d-n}-1\right\rfloor=\left\lfloor\frac{2d}{2d-n}\right\rfloor-1\leqslant 2\left\lfloor\frac{d}{2d-n}\right\rfloor,$

что и завершает доказательство первой части.

Доказательство второй части

Для получения необходимого неравенства нам необходимо доказать следующую лемму.

Лемма 1

$A(n,\;2r-1)= A(n+1,\;2r).$

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

Пусть $C$ будет $(n,\;M,\;2r-1)$-кодом. Добавляя к $C$ проверку на чётность, получаем $(n+1,\;M,\;2r)$-код, откуда следует, что

$A_2(n,\;2r-1)\leqslant A_2(n+1,\;2r).$

В обратную сторону выкидывание одной координаты в заданном $(n+1,\;M,\;2r)$-коде приводит к $(n,\;M,\;d\geqslant 2r-1)$-коду, так что

$A_2(n,\;2r-1)\geqslant A_2(n+1,\;2r).$

Требуемый результат следует из первой части доказательства и леммы 1.

Доказательство третьей части

Снова докажем сперва следующее вспомогательное утверждение.

Лемма 2

$A_2(n,\;d)\leqslant 2A_2(n-1,\;d).$

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

В заданном $(n,\;M,\;d)$-коде разделим все кодовые слова на два класса, отнеся в один класс те слова, которые начинаются с нуля, а в другой — те, которые начинаются с единицы. Один из этих классов содержит по крайней мере половину кодовых слов, что влечёт

$A_2(n-1,\;d)\geqslant\frac{A_2(n,\;d)}{2}.$

Из первой части доказательства и леммы 2 следует, что

$A_2(4r,\;2r)\leqslant 2A_2(4r-1,\;2r)\leqslant 8r.$

Искомый результат получаем, подставляя $d=2r$.

Доказательство четвёртой части

Из леммы 1 следует, что

$A_2(2d+1,\;d)=A_2(2d+2,\;d+1).$

Так как, $2d+2$ и $d+1$ — чётные числа, то можно воспользоваться результатом третьей части доказательства:

$A_2(2d+2,\;d+1)=A_2(2(d+1),\;d+1)\leqslant 4(d+1)=4d+4,$

что завершает доказательство всей теоремы.

Коды, достигающие границы Плоткина

Если существуют матрицы Адамара всех возможных порядков (что, однако, до сих пор ещё не доказано), то во всех частях теоремы выполняются равенства. Таким образом, граница Плоткина является точной в том смысле, что существуют коды, достигающие этой границы.

Литература

• Плоткин М. Двоичные коды с заданным минимальным расстоянием. — Кибернетический сборник. — Москва, 7:60-73 [2], 1963.
• F. J. MacWilliams and N. J. A. Sloane. The Theory of Error-Correcting Codes. — Amsterdam, Netherlands, North-Holland, § 2.2, 1977.

См. также

• Граница Синглтона
• Граница Хэмминга
• Неравенство Гильберта — Варшамова
• Граница Джонсона
• Неравенство Адамара