19.6. ХОРОШИЕ САМОДУАЛЬНЫЕ КОДЫ СУЩЕСТВУЮТ

В этом разделе различными способами подсчитавается число самодуальных кодов и показывается, что некоторые из них удовлетворяют границе Варшамова-Гилберта. Для простоты рассматривается только двоичный случай (общий случай см. в работая Мэллоуса и др. [892], Плесс [1053, 1054], Плесс и Пирса [1061] и также Зе-Хяна [1457]).

Если то назовем код слабо самодуальным.

Теорема 18. (Мак-Вильямс и др. [887].) Пусть и предположим, что (двоичный) слабо самодуальный -код, причем Тогда число самодуальных -кодов, содержащих код равно

Доказательство. Обозначим через число слабо самодуальных -кодов, которые содержат код Найдем рекуррентную формулу для Слабо самодуальный -код Ж), содержащий может быть пополнен до слабо самодуального -кода, содержащего 92, присоединением любого вектора из кода не принадлежащего Представим как объединение смежных классов кода

где Всего имеется I различных пополнений кода 3), а именно где В каждом из этих пополнений имеется -подкодов содержащих так как таково число ненулевых векторов в ортогональных коду . Таким образом, для значений имеет место формула

Так как исходное значение то получаем (19.70).

Следствие 19. Полное число двоичных самодуальных кодов длины равно

Доказательство. В качестве кода в теореме 18 выберем код

Следствие 20. Пусть двоичный вектор четного веса, отличный от Число самодуальных кодов, содержащих вектор равно

Теорема 21. ([887].) Существуют длинные двоичные самодуальные коды, достигающие границы Варшамова-Гилберта.

Доказательство. Получается стандартным способом из следствий 19, 20 (см. теорему 31 гл. 17). 9

Соответствующее рассуждение показывает, что аналогичный результат имеет место для самодуальных кодов над GF(q) (см. [1061]). Самым трудным оказался случай четных самодуальных кодов, и за доказательством следующего результата читатель отсылается к работе [887].

Теорема 22. Пусть кратно 8. Предположим, что — двоичный слабо самодуальный -код, веса всех слов которого делятся на 4. Число -четных самодуальных кодов, содержащих код равно

Следствие 23. Полное число четных самодуальных кодов длины равно

Число таких кодов, содержащих фиксированный вектор отличный от веса равно

Теорема 24. (Томпсон [1320а]; см. также [887].) Существуют длинные четные самодуальные коды, достигающие границы Варшамова-Гилберта.

В следующих шести упражнениях через обозначен класс всех двоичных слабо самодуальных -кодов, а через — подкласс в состоящий из кодов, содержащих вектор где (см. [1063]).

Упражнения. (14). Пусть четное и Показать, что число кодов из содержащих равно

(15). Показать, что полное число кодов в равно

если четное, и равно нулю, если нечетное.

(16). Пусть Показать, что число кодов в содержащих код равно

(17). Показать, что полное число кодов в равно

(18). Пусть четное и Показать, что число кодов в содержащих код , равно

(19). Показать, что для четного полное число кодов в равно

(20). Показать, что сумма весовых функций всех самодуальных кодов длины (для четного равна

Та же сумма для четных самйдуальных кодов (если делится на 8) равна

(21). ([1053, 1054].) Пусть — слабо самодуальный -код над наибольший в том смысле, что не содержится ни в каком слабо самодуальном коде той же длины и большей мощности.

(a). Показать, что

(b). Показать, что число таких наибольших кодов равно

(c). Показать, таким образом, что сацодуальный код существует, если и только если кратно 4.

(22). ([1054].) Показать в общем случае, что самодуальный -код над GF(q) существует тогда и только тогда, когда выполняется одно из следующих условий: (i) оба числа являются четными; четное число; делится на 4.

(23). ([1054].) Показать, что если выполнены условия предыдущего упражнения, то число самодуальных кодов над GF(q) равно

где , если четное, и если нечетное.

Задача (нерешенная). (19.5). Сколько неизоморфных еамодуальных кодов длины существует? (Для небольших значений см. [1058, 1059, 1062, 1063, 892].)

ЗАМЕЧАНИЯ К ГЛ. 19

(см. скан)