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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Грани́ца Пло́ткина — в теории кодирования определяет предел мощности двоичного код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.

Заметим, что величина z^*Mz всегда веществена, потому что M — это Эрмитова матрица.

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,

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

Коды, достигающие границы Плоткина[править | править вики-текст]

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

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