Глава 6. Коды, схемы и совершенные коды

6.1. ВВЕДЕНИЕ

В этой главе мы продолжим изучение теоретико-множественных свойств кодов, начатое в гл. 5.

В § 6.2 мы определим четыре фундаментальных параметра связанных с любым линейным или нелинейным кодом

Параметр представляет собой минимальное расстояние между словами число различных ненулевых значений расстояния между его кодовыми словами. Параметры когда код 42 — линейный, являются аналогичными величинами для дуального кода Для нелинейного кода число по-прежнему называемое дуальным расстоянием, было определено в § 5.5, а параметр обозначает число индексов таких, что где, как обычно, преобразование Мак-Вильямс спектра расстояний кода Параметр называется внешним расстоянием кода, так как любой вектор из находится на расстоянии, не большем чем по крайней мере от одного кодового слова из (Теорема 21 из § 6.6. Однако число не обязательно является наименьшим числом с этим свойством, см. упражнение

Имеется довольно много интересных кодов, для которых либо В таком случае минимальное расстояние кода (или дуальное расстояние) заведомо не меньше, чем число неизвестных в спектре расстояний, и уравнения Мак-Вильямс могут быть разрешены. Отсюда следует, что такие коды удовлетворяют следующим трем замечательным свойствам, которые мы установим в § 6.3, 6.4, 6.7:

(a). Число кодовых слов, находящихся на расстоянии от кодового слова не зависит от выбора Образно говоря, совокупность кодовых слов выглядит одинаково с точки зрения любого кодового слова (теорема и следствие 5 из § 6.3.) Такой называется инвариантным относительно расстояния. Если код содержит нулевое кодовое слово, то спектры весов и расстояний совпадают. (Конечно, для линейных кодов свойство выполняется всегда.)

(b). Если обозначают значения весов, встречающихся в коде, то число кодовых слов веса является явно выписываемой функцией от и чисел (теоремы 2 и 4 из § 6.3 и теорема 7 из § 6.4).

(c). Кодовые слова любого веса образуют -схему, где не меньше, чем или (В действительности мы докажем более сильный результат, чем этот, — см. теорему 9 из § 6.4, следствие 14 из § 6.5 и теорему 24 из § 6.7.)

В § 6.5 мы покажем, что если кодовые слова любого веса линейном двоичном коде образуют -схемы, то этому же свойству удовлетворяют кодовые слова любого веса в дуальном коде (теорема 13).

В § 6.6 изучается весовой спектр кода, являющегося сдвигом некоторого линейного или нелинейного кода.

В § 6.8 приводятся два результата, относящихся к совершенным кодам: доказывается, что код совершенен, если и только если (теорема 27), и выписывается необходимое условие совершенности кода, принадлежащее Ллойду (теорема 28).

Все перечисленные до сих пор результаты относились к двоичным кодам. Только в § 6.9 мы обсудим, как эти результаты могут быть обобщены для случая произвольного поля GF(q). Мы рассмотрим только построение -схем из линейных кодов над GF(q) (теорема 29). В двоичном случае из теоремы 29 получается, по-видимому, более сильный результат, чем из следствия 14 (см. следствие 31).

Наконец, в § 6.10 будет доказана теорема Титвайнена-Ван Линта (теорема 33) о том, что единственными нетривиальными совершенными кодами над любым полем являются известные коды Хэмминга и Голея.