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