Граница Плоткина (Ijguneg Hlkmtnug)

Перейти к навигации Перейти к поиску

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

Формулировка

[править | править код]

Пусть  — двоичный код длины или, другими словами, подмножество . Пусть  — минимальное расстояние кода , то есть

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

Теорема (граница Плоткина):

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

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

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

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

где оператор обозначает целую часть числа.

Доказательство первой части

[править | править код]

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

С одной стороны, всего есть разных возможностей для выбора , и для каждой из них есть возможностей для выбора . По определению для всех и , следовательно

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

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

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

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

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

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

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

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

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

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

Доказательство второй части

[править | править код]

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

Лемма 1

Доказательство леммы

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

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

Требуемый результат следует из первой части доказательства и леммы 1.

Доказательство третьей части

[править | править код]

Снова докажем сперва следующее вспомогательное утверждение.

Лемма 2

Доказательство леммы

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

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

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

Доказательство четвёртой части

[править | править код]

Из леммы 1 следует, что

Так как, и  — чётные числа, то можно воспользоваться результатом третьей части доказательства:

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

Коды, достигающие границы Плоткина

[править | править код]

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