8.5. ГРУППЫ АВТОМОРФИЗМОВ КОДА

Пусть двоичный код длины Любая перестановка координат переводит в эквивалентный код, многие свойства которого совпадают со свойствами исходного кода (те же минимальный вес, весовой спектр и т. п.).

Определение. Множество перестановок координат, отображающих код «на себя» (переводящих кодовое слово в кодовое слово, возможно, отличное от исходного), называется группой автоморфизмов кода и обозначается через

Упражнение. (28). Показать, что действительно группа.

Подстановка символов переводит в (или, в более удобном обозначении, в Вектор переходит в вектор Если некоторая другая

подстановка, то произведение означает: сначала применим , а затем Таким образом, Например, если

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

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

(2). Группа автоморфизмов кода

состоит из следующих восьми подстановок:

Упражнения. (29). Если код линеен, то

(30). Если код линеен и получается из путем добавления проверочной позиции или путем добавления вектора из всех единиц, то В случае если блоковая длина нечетна, а все кодовые векторы имеют чётный вес, то

(31). Показать, что из включения не следует включение

(32). Пусть -код, порождающая матрица которого показана на рис. 8.4. Таким образом, первая строка содержит 1 в координатах вторая строка — в координатах и т.д.

Показать, что группа состоит только из тождественной подстановки.

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

Пусть линейный -код с порождающей матрицей содержит линейно независимых строк.

Лемма 12. Подстановка координат, задаваемая некоторой -матрицей А, принадлежит группе тогда и только

Рис. 8.4. -код с тривиальной группой автоморфизмов

да, когда для некоторой обратимой -матрицы К.

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

Пример. [7, 3, 4] симплексный код з задается порождающей матрицей

Подстановка (124) (365) переводит кодовые слова в кодовые слова. В самом деле,

Определение. Множество всех обратимых -матриц над полем называется полной линейной группой и обозначается через Если конечное поле то этот факт записывается в виде

Теорема 13. Порядок полной линейной группы равен

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

Согласно лемме 12 группа автоморфизмов двоичного линейного кода размерности изоморфна подгруппе группы

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

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

Доказать, что

Приведем теперь одно полезное свойство, описывающее весовой спектр.

Теорема 14. Предположим, что код длины все веса в котором четны и который обладает следующим свойством: какую бы из координат мы ни удалили, получающийся при этом выколотый код (см. § 1.9) имеет один и тот же весовой спектр. Если весовой спектр кода весовой спектр любого из таких выколотых кодов, то

Более того, минимальное расстояние этих выколотых кодов нечетно.

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

Отсюда следует и вторая формула, так как

Группа подстановок символов называется транзитивной, если для любой пары символов найдется подстановка такая, что Более общо называется -кратно транзитивной, если для различных символов различных символов найдется подстановка лей такая, что

Следствие 15. Предположим, что код инвариантен относительно транзитивной группы подстановок. Тогда: (i). Удаление любой из координат приводит к эквивалентным кодам Если все веса кода четны, то минимальный вес в коде нечетен.

Позже мы увидим, что многие расширенные циклические коды обладают транзитивными группами подстановок. Но будьте осторожны! Как видно из упражнения (35), теорема 14 применима не ко всем циклическим кодам.

Упражнения. (35). Пусть невырожденный [9, 3, 3] циклический код с порождающим многочленом Показать, что расширенный код не удовлетворяет условиям теоремы 14.

(36). Доказать, что если код длины фиксируется транзитивной группой подстановок, то где число кодовых слов веса

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

(38). (Камьон.) Предположим, что циклический код над -кратно транзитивной группой Доказать, что

Группа автоморфизмов циклического кода. Согласно определению группа автоморфизмов циклического кода содержит все циклические подстановки на множестве и все их степени.

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

Упражнения. (39). Найти группу автоморфизмов кода, представленного на рис. 5.1.

(40). Показать, что порождают группу порядка состоящую из подстановок вида для

Пример. На рис. 8.5 показано действие подстановки на слова симплексного кода з.

Рис. 8 5 Действие автоморфизма на слова симплексного кода

Эквивалентность циклических кодов. Будем сейчас рассматривать не как кольцо многочленов, а как групповую алгебру циклической группы порядка Отображения , где

— число, взаимно простое с образуют группу автоморфизмов группы G. (Автоморфизмом группы называется такое отображение о группы «на себя», которое сохраняет умножение в группе; Таким образом, элементы из 9 переставляют координаты кольца и переводят циклический код в циклический код.

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

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

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

(см. рис. 4.4).

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

Например, для циклотомические классы, содержащие числа, взаимно простые с имеют вид:

Выделенные жирным шрифтом числа задают степени 5 по модулю 63; следовательно, в данном случае фактор-группа является циклической порядка 6.

Действие на примитивных идемпотентах (или на циклотомических классах) описывается следующим образом:

Мы видим, что подстановка разбивает примитивные идемпотенты на классы. Идемпотенты первого класса порождают невырожденные циклические коды длины 63. Идемпотенты второго класса задают повторения циклических кодов длины 3, из третьего класса — повторения циклических кодов длины 21, из четвертого — длины 9 и из пятого — длины 7. Нетрудно сообразить, что порядок вещей всегда таков: любой невырожденный идемпотент длины может быть получен из применением подстановки ом.

Таким образом, невырожденные минимальные идеалы одной и той же блоковой длины эквивалентны.

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

эквивалентны.

Упражнение. (41). (а). Показать, что при подстановка отображает

Для подстановка отображает

При подстановка отображает

Группа автоморфизмов кода БЧХ. Пусть код длины Сопоставим координатам ненулевые элементы поля элементы Добавим общую проверку на четность, присвоив ей номер и сопоставив нуль поля

Определение. Аффинная группа. Пусть подстановка элементов поля вида

где

Величина задает циклический сдвиг на позиций, оставляющий на месте 0, т. е. оставляющий на месте координату

Например, при длине действие подстановки а в поле задаваемом таблицей на рис. 4.5, описывается следующей цепочкой переходов:

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

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

Теорема 16. Пусть примитивный код БЧХ длины с конструктивным расстоянием и пусть его расширение. Тогда группа автоморфизмов кода содержит аффинную группу поля

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

Пусть где Тогда так как Также для так как код БЧХ.

Пусть — локаторы единиц в кодовом слове, полученном после подстановки. Тогда

Следовательно, слово, полученное в результате подстановки, также лежит в

Следствие 17. Пусть циклический код в его расширение. Если группа транзитивна, то минимальное расстояние кода нечетно и код содержит также слова (четного) веса . В частности, это имеет место для двоичного примитивного кода БЧХ.

Доказательство. Согласно теореме 14 если число слов веса в коде то

Упражнение. (43). Видоизмените доказательство теоремы 16 так, чтобы получить следующее ее обобщение, принадлежащее Касами, Лину и Питерсону. Пусть положительное целое число

и обозначает множество положительных целых чисел, двоичное представление которых «покрывается» двоичным представлением числа Таким образом, если где или 1, то

Пусть циклический код длины для которого элемент 1 служит ненулем, и пусть расширение этого кода. Тогда код инвариантен относительно аффинной группы, если и только если а - является нулем кода для всех всякий раз, когда нуль кода

Теорема 18. Если двоичный циклический код инвариантен относительно -кратно транзитивной группы то кодовые слова любого фиксированного веса образуют схему, где

Доказательство. Пусть множество кодовых слов веса которые в координатах содержат единицу. Так как кратно транзитивна, то не зависит от частного выбора координат Следовательно, кодовые слова веса образуют схему. Согласно теореме 9 гл. 2 имеет место равенство

Следствие 19. Кодовые слова каждого веса в расширенном двоичном примитивном коде БЧХ образуют -схему (ср. с теоремой 15 гл. 2).

Упражнения. (44). Доказать, что при минимальное расстояние кода БЧХ длины исправляющего две ошибки, равно точно 5.

(45). Пусть а смежный класс кода и Доказать, что — также смежный класс кода

(46). (Камьон.) Каждой матрице из группы сопоставим вектор-столбец длины Показать, что параметры кода над GF(q) с порождающей -матрицей равны:

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

Пусть — код над GF(q) длины Предположим сначала, что простое число.

Определение. Группой автоморфизмов линейного кода называется группа состоящая из всех мономиальных -матриц А над таких, что для всех

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

Таким образом, группа состоит из мономиальных матриц

Упражнение. (47). Показать, что порядок группы автоморфизмов кода из гл. 1 равен 48.

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