У этого термина существуют и другие значения, см.
Плоткин.
Грани́ца Пло́ткина — в теории кодирования определяет предел мощности двоичного кодa длины
и минимального расстояния
. Названа в честь американского математика Морриса Плоткина (1907—2003).
Пусть
— двоичный код длины
или, другими словами, подмножество
. Пусть
— минимальное расстояние кода
, то есть

где
— расстояние Хэмминга между
и
. Выражение
обозначает максимально возможное количество кодовых слов в двоичном коде длины
и минимального расстояния
. Граница Плоткина даёт верхний предел этого выражения.
Теорема (граница Плоткина):
1. Если
— чётное число
, то

2. Если
— нечётное число и
, то

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

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

где оператор
обозначает целую часть числа.
Пусть
— расстояние Хэмминга между
и
, а
— мощность
. Найдём предел величины
двумя разными способами.
С одной стороны, всего есть
разных возможностей для выбора
, и для каждой из них есть
возможностей для выбора
. По определению
для всех
и
, следовательно

С другой стороны, определим
как матрицу размерности
, строками которой будут элементы кода
. Если
— количество нулей в столбце
матрицы
, то столбец
содержит
единиц. Любые ноль и единица в одном и том же столбце добавляют ровно
(так как
) к общей сумме
, а значит

При чётном
величина в правой части равенства достигает максимума при
, что означает

Объединяя нижнюю и верхнюю границы выражения
в одно неравенство, получим

что при условии
равнозначно

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

С другой стороны, если
нечётное, то
достигает максимума при
, откуда следует, что

Объединяя нижнюю и верхнюю границы выражения
в одно неравенство, получим

что при условии
равнозначно

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

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

Доказательство леммы
Пусть
будет
-кодом. Добавляя к
проверку на чётность, получаем
-код, откуда следует, что

В обратную сторону выкидывание одной координаты в заданном
-коде приводит к
-коду, так что

Требуемый результат следует из первой части доказательства и леммы 1.
Снова докажем сперва следующее вспомогательное утверждение.
Лемма 2

Доказательство леммы
В заданном
-коде разделим все кодовые слова на два класса, отнеся в один класс те слова, которые начинаются с нуля, а в другой — те, которые начинаются с единицы. Один из этих классов содержит по крайней мере половину кодовых слов, что влечёт

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

Искомый результат получаем, подставляя
.
Из леммы 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.