19.5. НЕСУЩЕСТВОВАНИЕ НЕКОТОРЫХ ОЧЕНЬ ХОРОШИХ КОДОВ

В этом разделе теорема используется для получения верхней границы (теорема 13) для минимального расстояния четных самодуальных кодов. Затем будет показано (следствие 16), что эта верхняя граница достижима лишь при небольших значениях Используемый при этом метод обобщает приведенное в § 19.2 вычисление весовой функции [48, 24, 12] КВ-кода. Аналогичные результаты справедливы и для других типов самодуальных кодов, описываемых теоремой 1.

Пусть обозначает четный самодуальный код, имеющий весовую функцию Согласно теореме является многочленом и который может быть записан как

где или 2. Предположим, что коэффициентов а, в выражении (19.52) выбраны так, что

т. е. выбраны так, что в многочлене равно нулю максимально возможное число старших коэффициентов. Ниже будет показано, что это условие однозначно определяет Многочлен задаваемый формулой (19.53), представляет собой весовую функцию четного самодуального кода с наибольшим минимальным весом, которого мы надеемся достичь, и называется экстремальной весовой функцией.

Если существует код с весовой функцией то он имеет минимальное расстояние пока коэффициент в

(19.53) случайно не окажется нулем, в этом случае

Но этого не происходит.

Теорема 13. (Мэллоус и Слоэн [893].) Число кодовых слов минимального ненулевого веса в экстремальной весовой функции определяется следующими выражениями:

и это число никогда не равно нулю. Следовательно, минимальное расстояние четного самодуального кода длины равно самое большее

Доказательство. Мы дадим здесь элементарное доказательство для случая другие случаи аналогичны. Ниже будет дано второе доказательство, которое применимо ко всем случаям одновременно.

Согласно теореме 9 гл. 6 кодовые слова веса образуют -схему. Но нам проще вычислить параметр соответствующей -схемы. Из равенства (6.9) получаем, что

где

Следующие тождества легко проверяются:

Следовательно,

и поэтому

Таким образом, число кодовых слов веса определяется вы ражением (19.54).

Известные коды, которые достигают границы, установленной в теореме 13, приведены на рис. 19.2. Что касается дважды циркулянтных кодов, имеющихся в этой таблице, см. рис. 16.7.

Экстремальные весовые функции для (и, в частности, весовые функции всех кодов, представленных на рис. 19.2) приведены в работе [893]. Они были получены с помощью теоремы 15.

Рис. 19.2. Четные самодуальные коды с

Фейт [426] построил [96, 48, 16] четный самодуальный код, используя конструкцию типа описанную в гл. 18. Все четные самодуальные коды длины приведены Плесс [1058] и Плесс и Слоэном [1062, 1063]. Первая невыясненная точка на рис. 19.2 соответствует значению

Задача (нерешенная). (19.3). ([1227].) Существует ли [72, 36, 16] четный самодуальный код?

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

Но если Очень велико, то экстремальная весовая функция содержит отрицательный коэффициент, и граница, описываемая теоремой 13, не может быть достигнута. Как показывает следующее упражнение, это может быть доказано методом, использованным для доказательства теоремы 13.

Упражнение. (13). Предположим, что — четный самодуальный код длины весовая функция которого совпадает с экстремальной весовой функцией Кодовые слова каждого веса образуют -схему (а). Показать, что параметр Для -схемы, образованной кодовыми словами веса равен

(b). Вывести отсюда, что для достаточно больших

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

Теорема 14. (Борман-Лагранж.) (См. Уиттекер и Ватсон [1414, с. 186], Голдстейн [520], Гуд [533], Сэк [1137-1139].) Пусть функции, аналитические в окрестности точки причем При условии, что уравнение определяет однозначно в некоторой окрестности нуля, функция при достаточно малых может быть следующим образом разложена в ряд по степеням

(Штрих обозначает дифференцирование.)

Чтобы применить эту теорему к экстремальной весовой функции, заменим вначале в выражении на 1, а на х. Тогда превращается в превращается в Для простоты предположим, что кратно 24 и поэтому два других случая доказываются аналогично. Приравнивая (19.52) и (19.53), получаем, что

Разделив на имеем

где

для малых х.

Используя теорему 14, разложим теперь степеням с

Получим, что

где

для Сравнивая (19.59) и (19.60), убеждаемся, что

и поэтому

Таким образом, мы доказали следующую теорему. Теорема 15. ([893].) Экстремальная весовая функция четного самодуального кода длины определяется выражением (19.58), где коэффициенты задаются в явном виде равенствами (19.61) и (19.62). Кроме того, приравнивая коэффициенты при в (19.63), получаем, что

и

Теперь из (19.61) непосредственно следует, что и это дает другое доказательство верхней границы теоремы 13. Но следующий коэффициент становится отрицательным.

Следствие 16. (Мэллоус и др. [891].) для всех достаточно больших

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

Приведенное доказательство показывает, что коэффициент впервые становится отрицательным, когда значение

близко к 3720. Действительно, при вычисления на ЭВМ показали, что

для значений

Подобные же рассуждения могут быть использованы, чтобы показать, что следствие 16 справедливо также и для случаев Другой способ доказательства того, что отношение ограничено, приведен в работе [891]. Он использует метод перевала для разложения в ряд выражения внутри квадратных скобок в (19 61).

Итак, мы рассмотрели только коды типа (ii) из теоремы 1. Соответствующие результаты имеют место и для кодов других типов, причем доказательства аналогичны.

Теорема 17. Минимальное расстояние самодуального кода над веса всех слов которого кратны равно самое большее где

Но для всех достаточно больших не существует кодов, достигающих этих оценок

Заметим, что при из границы Мак-Элиса и др. (теорема 37 гл 17) для двоичных кодов со скоростью 1/2 получаем, что а из границы Элайеса (теорема 34 гл 17) для кодов со скоростью 1/2 получаем, что (для кодов над (для кодов над Таким образом, выражения (19 67) и (19 68) являются более сильными оценками, в то время как (19 66) и (19 69) хуже указанных оценок.

Оценка (19 66) достигается самодуальными кодами длины 2, 4, 6, 8, 12, 14, 22, 24 и не достигается для других значений (см. доказательство в [893, 1058, 1062, 1063] и Уорда (Н. N. Ward) [1389]). Кроме того, для и, возможно, для других значений ([893, 1389]) существуют формально самодуальные коды, удовлетворяющие (19 66).

Граница (19 68) достигается для значений (код Голея), 24, 36, 48 и 60 (KB и симметричные коды Плесс), 16 и 40 (код с порождающей матрицей где матрица Адамара, частное сообщение Уорда) и, возможно, для других значении (см [892]) Гораздо меньше известно о кодах, достигающих границы (19 69) (см. [1478]).

Задача (нерешенная). (19.4). Чему равно наибольшее для которого существуют коды, достигающие границ, приведенных в теореме 17?

В работе [891] доказан также следующий более сильный результат. Для любого фиксированного числа существует такое, что все самодуальные коды длины, большей чем имеют минимальное расстояние, меньшее чем где определяется теоремой 17.