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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle A_{2}(2d,\;d)\leqslant 4d.}$

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

${\displaystyle A_{2}(2d+1,\;d)\leqslant 4d+4,}$

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

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

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

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

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

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

${\displaystyle \sum _{x,\;y\in C}d(x,\;y)=\sum _{i=1}^{n}2s_{i}(M-s_{i}).}$

При чётном ${\displaystyle M}$ величина в правой части равенства достигает максимума при ${\displaystyle s_{i}=M/2}$, что означает

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

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

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

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

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

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

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

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

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

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

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

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

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

Так как ${\displaystyle M}$ — целое число, то

${\displaystyle 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

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

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

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

${\displaystyle A_{2}(n,\;2r-1)\leqslant A_{2}(n+1,\;2r).}$

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

${\displaystyle A_{2}(n,\;2r-1)\geqslant A_{2}(n+1,\;2r).}$

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

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

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

Лемма 2

${\displaystyle A_{2}(n,\;d)\leqslant 2A_{2}(n-1,\;d).}$

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

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

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

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

${\displaystyle A_{2}(4r,\;2r)\leqslant 2A_{2}(4r-1,\;2r)\leqslant 8r.}$

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

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

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

${\displaystyle A_{2}(2d+1,\;d)=A_{2}(2d+2,\;d+1).}$

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

${\displaystyle A_{2}(2d+2,\;d+1)=A_{2}(2(d+1),\;d+1)\leqslant 4(d+1)=4d+4,}$

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

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

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

Примечания

1. ↑ Левенштейн В. И. Применение матриц Адамара к одной задаче кодирования. — Проблемы кибернетики. — 5:123-136 [2A], 1961.

Литература

• Плоткин М. Двоичные коды с заданным минимальным расстоянием. — Кибернетический сборник. — Москва, 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.

См. также

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

Эта страница в последний раз была отредактирована 1 февраля 2015 в 13:12.