16.5. ГРУППА АВТОМОРФИЗМОВ КВ-КОДОВ

В данном параграфе доказывается, что расширенный КВ-код 9? инвариантен относительно мощной группы подстановок

Определение группы Пусть простое число вида Совокупность всех подстановок на множестве вида

где образует группу, которая называется проективной специальной линейной группой (иногда она называется дробно-линейной группой).

Необходимые нам свойства группы описываются следующей теоремой.

Теорема Группа порождается тремя подстановками:

где примитивный элемент поля

(b). Группа состоит из подстановок вида:

где

(c). Если то образующие подстановки связаны соотношениями:

Группа дважды транзитивна.

Доказательство, Типичный элемент группы

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

Основной результат для двоичного случая дается следующей теоремой.

Теорема 10. (Глизон и Прэндж.) Если то расширенный квадратично-вычетный код инвариантен относительно группы

Доказательство. Так как порождающий идемпотент кода инвариантен относительно подстановки V, а подстановка 5 представляет собой циклический сдвиг, то код следовательно, код инвариантны относительно Согласно теоремы 9 остается доказать инвариантность относительно подстановки Мы рассмотрим только случай и покажем, что каждая строка порождающей матрицы (16.28), т. е. матрицы

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

(i). Первая строка матрицы скажем, равна

Тогда

(ii). Пусть строка матрицы равна:

Мы покажем, что Для этого в отдельности для каждого члена равенства проанализируем координаты, содержащие символ 1. Вектор содержит символ 1 в координатах — для что включает в себя (если вычетов и невычетов (по теореме Перрона 24), Вектор

содержит символ 1 в координатах что чает в себя вычетов и невычетов. Следовательно, сумма содержит символ 1 в координате и символ 0 в координате (невычет). Если то для некоторого и символы 1 в сумме взаимно уничтожаются. Таким образом, координаты, соответствующие в сумме невычетам, всегда содержат символ 0. С другой стороны, если то для всех и координаты, соответствующие в сумме вычетам, содержат символ 0. Таким образом,

Аналогично, если то

Согласно теореме 18 гл. 8 слова каждого фиксированного веса кода образуют -схему. В некоторых случаях имеет место более сильное утверждение (см. конец § 16.8).

Следствие 11. Все коды 2, получаемые из 2 удалением одной координаты, эквивалентны между собой независимо от того, какая из координат вычеркивается.

Доказательство. Это вытекает из следствия 15 гл. 8, так как группа транзитивна.

Группа автоморфизмов недвоичных КВ-кодов. Если то, (как было определено в § 8.5) группа состоит из всех мономиальных матриц, относительно которых код инвариантен.

В силу линейности код инвариантен относительно скалярных матриц

где Этими матрицами удобно пренебречь и рассматривать в качестве группы автоморфизмов группу Очевидно, что

Теорема 12. (Глизон и Прэндж.) Если то группа содержит группу, изоморфную группе и порождаемую элементами где представляет собой следующее мономиальное обобщение подстановки Т: элемент, стоящий первоначально в координате , умножается на элемент, стоящий первоначально в координате 0, умножается на элемент, первоначально стоящий в координате умножается на где было определено в предыдущем параграфе, и знак плюс берется для а знак минус — для

Доказательство. Аналогично доказательству теоремы 10. Из теорем 10 и 12 следует только тот факт, что группа содержит Известны три случая, когда на самом деле больше группы а именно при код равен -коду Хэмминга и согласно теореме 24 гл. 13 . Два других случая получаются при ; в этих случаях код равен расширенному коду Голея, а его группа автоморфизмов равна группе Матье (см. гл. 20).

Но представляется очень вероятным, что для остальных значений группа равна группе Это предположение выполняется во многих случаях; например, имеет место следующий результат.

Теорема 13. (Ассмус и Мэттсон.) Если простое число и то, за исключением указанных трех случаев, группа равна (изоморфна) группе Доказательство опускается.

Упражнения. (2). Доказать, что коды имеют одно и то же минимальное расстояние, а минимальное расстояние кода на 1 меньше.

(3). Доказать, что подстановка (16.29) принадлежит группе тогда и только тогда, когда число является квадратичным вычетом по модулю

(4). Доказать, что образующая V в (16.30) является избыточной: группа порождается подстановками

(5). Доказать, что если то соотношения, задаваемые теоремы 9, определяют абстрактную группу порядка изоморфную, естественно, группе

Задача (нерешенная). (16.3). Доказать, что утверждение теоремы 13 справедливо для всех