В математике из теории кодирования , то Плоткина, названная в честь Морриса Плоткина, предел (или связан) на максимально возможном числе кодовых слов в двоичных кодах заданной длиной п и заданный минимальное расстояние г .
Код считается "двоичным", если в кодовых словах используются символы из двоичного алфавита. . В частности, если все кодовые слова имеют фиксированную длину n , то двоичный код имеет длину n . Эквивалентно, в этом случае кодовые слова можно рассматривать как элементы векторного пространства. над конечным полем . Позволять быть минимальным расстоянием , т.е.
где это расстояние Хэмминга между а также . Выражение представляет максимальное количество возможных кодовых слов в двоичном коде длины и минимальное расстояние . Граница Плоткина накладывает ограничение на это выражение.
Теорема (оценка Плоткина):
i) Если даже и , тогда
ii) Если это странно и , тогда
iii) Если ровно, тогда
iv) Если странно, то
где обозначает функцию пола .
Позволять быть расстояние Хэмминга от а также , а также быть количеством элементов в (таким образом, равно ). Оценка доказывается ограничением величины двумя разными способами.
С одной стороны, есть выбор для и для каждого такого выбора есть выбор для . Поскольку по определению для всех а также (), следует, что
С другой стороны, пусть быть матрица, строки которой являются элементами . Позволять быть количеством нулей, содержащихся в -й столбец . Это означает, чтостолбец содержит единицы. Каждый выбор нуля и единицы в одном столбце дает точный вклад (так как ) к сумме и поэтому
Количество справа максимизируется тогда и только тогда, когда справедливо для всех (на этом этапе доказательства мы игнорируем тот факт, что целые числа), то
Комбинируя верхнюю и нижнюю оценки для что мы только что получили,
что с учетом того эквивалентно
С четно, отсюда следует, что
Это завершает доказательство оценки.