19.4. ОБОБЩЕНИЯ ТЕОРЕМЫ ГЛИСОНА

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

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

содержит некоторое кодовое слово веса Соответствующим умножением столбцов на —1 мы можем привести код к виду, когда он содержит кодовое слово

Цель этого раздела состоит в описании полной весовой функции кода посредством следующей теоремы.

Теорема 12. Если — полная весовая функция троичного самодуального кода, содержащего вектор 1, то

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

и

Заметим, что

(Индекс многочлена обозначает его степень.)

Доказательство. Доказательство состоит из двух этапов, описанных в § 19.2.

Этап Предположим, что типичное кодовое слово не содержит а нулей, единиц и с двоек. Так как 93 самодуальный код, содержащий вектор то

(вес Хэмминга делится на 3);

Следовательно, функция инвариантна относительно преобразований

Кроме того, вектор — и содержит а нулей, с единиц, двоек, а вектор содержит с нулей, а единиц, двоек. Следовательно, инвариантна относительно преобразований

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

Наконец согласно равенству инвариантна также относительно преобразования

Эти шесть матриц порождают группу порядка 2592, состоящую из 1944 матриц вида

и из 648 матриц вида

где или 3 и любая -матрица перестановок.

Таким образом, этап I завершен; из свойств кода вытекает, что его весовая функция Ж(х, инвариантна относительно группы

Этап II. Этот этап представляет собой доказательство того факта, что кольцо инвариантов группы равно

Вначале, так как у нас имеется список всех матриц группы необходимы непосредственные вычисления вручную для получения ряда Молина в виде (19.9). Как всегда, все сложности пропадают, и окончательное выражение имеет вид

Это выражение подсказывает нам степени многочленов хорошего полиномиального базиса, который мы должны искать.

Далее группа порождается матрицами и всеми матрицами перестановок Ясно, что инварианты должны быть симметрическими функциями от х, степень которых кратна 3. Поэтому рассмотрим алгебраически независимые симметрические функции и определим, какие функции от них являются инвариантами относительно преобразований Например, функция инвариантна относительно но преобразование переводит ее в Запишем это следующим образом:

Следовательно, инвариант. Далее

поэтому другим инвариантом является многочлен

Затем

и поэтому инвариант. Наконец

приводит к инварианту

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

Замечание. Без предположения о том, что код содержит вектор из всех единиц, теорема (принадлежащая Мак-Элису (R. J. Мс Eliece)) становится значительно более сложной ([883, § 4.7], Мэллоус и др. [892]) (см. также упражнение (5)).

Применения теоремы 12. Для троичного кода Голея (выражение Для [24, 12, 9] симметричного кода Плесс из гл. 16

С помощью теоремы 12 были также получены полные весовые функции для симметричных кодов Плесс длины 36, 48 и 60 (см. Мэллоус и др. [892]).

Другие обобщения. Следующие упражнения содержат дальнейшие теоремы подобного типа. Здесь не приводятся некоторые результаты для весовой функции Ли самодуального кода над (Мак-Вильямс и др. [883, § 5.3.2], Мэллоус и Слоэн [894]), для различных разделенных весовых функций — (см. Мэллоус и Слоэн [895]), для бивесовой функции и совместной весовой функции (§ 5.6) двоичных самодуальных кодов [883, § 4.9, 5.4.1]. Значительно меньше известно о полной весовой функции и весовой функции Ли самодуального кода над GF(q) (см. [883, § 5.3.1, 5.3.2] и приведенную выше теорему 6.

Весовые функции Хэмминга кодов типов теоремы 1 описываются теоремой Зс и упражнением (3). Два других типа кодов описываются следующим образом.

Упражнения. (5). (Глисон [486], Берлекэмп и др. [129], Фейт [425], [883].) Весовая функция Хэмминга самодуального

кода над представляет собой многочлен от (выражение (19.5)) и

[Указание. Группа, порожденная матрицами

имеет порядок 48 и ряд Молина Весовая функция Хэмминга самодуального кода над веса всех слов которого делятся на 2, представляет собой многочлен от [Указание. Соответствующая группа имеет порядок 12.] Весовая функция Хэмминга -кода, рассмотренного в примере равна Приведенный на с. 503 гл. -код имеет весовую функцию Хэмминга -код над веса всех слов которого четны, формально самодуален. Если же он самодуален, то у него имеется двоичная порождающая матрица.

(7). Весовая функция Ли для Пусть самодуальный код над с весовой функцией Ли

где число нулей в векторе число элементов число элементов ±2 (см. с. 146 гл. 5). Тогда 3(х, является многочленом от где

[Указание. Группа имеет порядок 120, см. [883, § 5.3.2] и Клейн [768, с. Следующие примеры иллюстрируют этот результат:

(8). (Фейт [424], Мэллоус и Слоэн [895].) Предположим, что нечетное число и что 9? — двоичный который содержится в коде, дуальном веса всех слов которого делятся на 4. Примерами таких кодов являются уменьшенные -код Хэмминга и -код Голея с весовыми функциями

Тогда должно иметь вид Если то весовая функция кода представляет собой элемент из

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

где

является весовой функцией -кода найденного Плесс [1058]. Вывести отсюда, что весовые функции [31, 15, 8] и [47, 23, 12] КВ-кодов равны соответственно

Соответствующие теоремы для двоичных самодуальных кодов с весами, кратными 2, и для троичных самодуальных кодов см. в работах Мэллоуса и др. [892, 895].

(9). Разделенные весовые функции. Предположим, что - четный самодуальный -код, содержащий кодовые слова и и обладаюзий тем свойством, что число кодовых слов с равно числу слов с (Здесь обозначают веса левой и правой половин слова, см. с. 151 гл. 5.) Такой код «уравновешен» относительно своей середины, и деление его на две половины вполне естественно. Тогда разделенная весовая функция (х, у, X, Y) кода (см. с. 151 гл. 5) представляет собой многочлен от где

(10). Примеры разделенных весовых функций. Будем использовать обозначение для определенных коэффициентов при записи и вместо выражения

будем писать следующую строку таблицы:

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

Рис. 19.1. Разделенные весовые функции четных самодуальных кодов

(11). Предположим, что Я — проективная плоскость порядка где (см. с. 68 гл. 2). Пусть обозначает -матрицу инцидентности где если прямая проходит через точку, и в противном случае. Пусть обозначает двоичный код, порожденный строками матрицы А, и пусть код получен из добавлением общей проверки на четность.

(i). Показать, что если то -код Хэмминга.

(ii). Показать, что в общем случае представляет собой

(iii). Отсюда вывести, что не существует проективной плоскости порядка 6. [Указание. Следует из теоремы так как ]. Заметим, что результаты упражнения (8) применимы к весовой функции кода Весовая функция гипотетической проективной плоскости порядка 10 обсуждалась Ассмусом и др. [43, 48], Мак-Вильямс и др. [888] и Мэллоусом и Слоэном [895].

Задача (нерешенная). (19.2). Пусть двоичный код, веса всех слов которого делятся на 4 и параметры которого равны для четного для нечетного причем Охарактеризовать бивесовую функцию кода