6.8. СОВЕРШЕННЫЕ КОДЫ

В этом разделе мы докажем, что -код является совершенным, если и только если Закончим этот раздел важным необходимым условием существования совершенного кода (теоремой Ллойда).

Теорема 25. Для любого кода выполняется неравенство

Доказательство. Допустим, что код содержит нулевое слово. Вначале предположим, что нечетное, и пусть вектор веса Если то по теореме 21 найдется кодовое слово с, находящееся на расстоянии меньшем, чем от вектора Но тогда что приводит к противоречию. Те же самые рассуждения проходят и для случая четного

Лемма 26. Если нечетное), то

Доказательство. Пусть вектор веса Для кода полученного сдвигом, получаем, что

Тогда в силу для Если вектор имеет вес то

и снова из (6.18) получаем, что

Теорема -код является совершенным, если и только если

Доказательство. Предположим, что Тогда по теореме 21 для любого вектора из найдется кодовое слово, находящееся от него на расстоянии не более чем Это соответствует тому, что шары радиуса с центрами в кодовых точках заполняют все множество и поэтому код является совершенным. Наоборот, предположим, что совершенный код, так что выполняется соотношение (5.26).

Применяя теперь лемму 19 к многочлену получаем, что аннулирующий многочлен кода должен делить многочлен Следовательно,

Но по теореме

Таким образом, аннулирующий многочлен совершенного кода имеет вид

Этот многочлен называется многочленом Ллойда и обозначается через Согласно упражнению 42 гл. Отсюда получаем, что верна следующая теорема.

Теорема 28. (Ллойд). Если существует двоичный совершенный -код, то многочлен имеет целых корней удовлетворяющих условию

Пример. Для [7, 4, 3]-кода Хэмминга