13.9. ГРУППЫ АВТОМОРФИЗМОВ РИДА-МАЛЕРА КОДОВ

Пусть -двоичная обратимая -матрица, и пусть двоичная -последовательность. Преобразование

представляет собой подстановку на множестве -последовательностей, переводящую в

Преобразование можно трактовать так же как перестановку на булевых функциях:

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

второй способами, третий способами Кроме того, имеется способов выбора вектора Таким образом, порядок этой группы, которая называется полной аффинной группой и обозначается равен

Полезным приближением этой величины для больших является (Мы уже встречались с этой группой в другой форме в § 8.5.) Из (13.18) видно, что если многочлен степени то также является многочленом степени Следовательно, группа переставляет слова РМ кода порядка и

Подгруппа группы состоящая из всех преобразований вида

(т. е. преобразований, для которых называется полной линейной группой, обозначается через (см. § 8.5) и имеет порядок

Так как преобразование (13.21) фиксирует нулевую m-последовательность, то группа переставляет слова выколотого РМ кода

Заметим, что группа дважды транзитивна, а группа трижды транзитивна (упражнение (9)).

Теорема 23. Для 1;

Доказательство. Пусть векторы минимального веса в коде Пусть для . Далее плоскость размерности Если произвольная -мерная плоскость, то для некоторых Следовательно, множество

представляет собой пересечение двух -мерных плоскостей, и состоит из точек, так как я — подстановка. Таким обрааом, плоскость размерности Следовательно, переставляет образующие векторы кода так что весь код инвариантен относительно Пункт доказывается аналогичным образом.

Из упражнения (5) сразу вытекает, что

В оставшейся части параграфа мы докажем, что в (13.20) и (13.23) имеет место равенство.

Теорема 24. Для :

Доказательство, (i). Имеем:

Согласно упражнению (30) гл. Так как размерность кода равна то из (13.21) и замечания, следующего за теоремой 13 гл. 8, получаем, что Наконец согласно упражнению (29) гл.

(ii). Пусть Ясно, что является подгруппой группы фиксирующей координату 0. Так как транзитивна, то группа также транзитивна. Поскольку каждый смежный класс в группе по подгруппе переводит точку 0 в различные точки, то Следовательно, из (13.20) и (13.21) вытекает равенство Используя опять упражнение (28) гл. 8, получаем .

(iii). Из теоремы 23 и пунктов следует:

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