Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 9 июля 2014 года; проверки требуют 2 правки.
У этого термина существуют и другие значения, см. Плоткин.
Грани́ца Пло́ткина — в теории кодирования определяет предел мощности двоичного кодa длины и минимального расстояния . Названа в честь американского математика Морриса Плоткина (1907—2003).
Пусть — двоичный код длины или, другими словами, подмножество . Пусть — минимальное расстояние кода , то есть
где — расстояние Хэмминга между и . Выражение обозначает максимально возможное количество кодовых слов в двоичном коде длины и минимального расстояния . Граница Плоткина даёт верхний предел этого выражения.
Пусть — расстояние Хэмминга между и , а — мощность . Найдём предел величины двумя разными способами.
С одной стороны, всего есть разных возможностей для выбора , и для каждой из них есть возможностей для выбора . По определению для всех и , следовательно
С другой стороны, определим как матрицу размерности , строками которой будут элементы кода . Если — количество нулей в столбце матрицы , то столбец содержит единиц. Любые ноль и единица в одном и том же столбце добавляют ровно (так как ) к общей сумме , а значит
При чётном величина в правой части равенства достигает максимума при , что означает
Объединяя нижнюю и верхнюю границы выражения в одно неравенство, получим
что при условии равнозначно
Так как — чётное число, то
С другой стороны, если нечётное, то достигает максимума при , откуда следует, что
Объединяя нижнюю и верхнюю границы выражения в одно неравенство, получим
Снова докажем сперва следующее вспомогательное утверждение.
Лемма 2
Доказательство леммы
В заданном -коде разделим все кодовые слова на два класса, отнеся в один класс те слова, которые начинаются с нуля, а в другой — те, которые начинаются с единицы. Один из этих классов содержит по крайней мере половину кодовых слов, что влечёт
Из первой части доказательства и леммы 2 следует, что
Если существуют матрицы Адамара всех возможных порядков (что, однако, до сих пор ещё не доказано), то во всех частях теоремы выполняются равенства. Таким образом, граница Плоткина является точной в том смысле, что существуют коды, достигающие этой границы[1].