13.3. АФФИННЫЕ ПЕРЕСТАНОВКИ ДЛЯ ЦИКЛИЧЕСКИХ КОДОВ    

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

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

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

элемент 0 в будем обозначать как Перенумеруем следующим образом компоненты вектора с») из элементами компонента нумеруется локатором а компоненты при локаторами а.

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

Аффинная перестановка — это перестановка, которая переводит компоненту с локатором X в компоненту с локатором где любые фиксированные элементы из и Множество всех аффинных перестановок образует группу относительно композиции, так как: 1) если локатор X переходит в локатор и локатор У переходит в локатор то X переходит в и 2) перестановка обратна перестановке Группа аффинных перестановок дважды транзитивна, так как при заданных парах система уравнений

решается относительно единственным образом.

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

Доказательство. Пусть а — примитивный элемент, используемый для задания локаторов. Перестановка аффинна. Но она представляет собой циклический сдвиг всех локаторов, кроме Следовательно, код является циклическим.

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

Определение 13.3.2. Пусть целое число в -ичном разложении:

Отличное от целое число к в -ичном разложении:

называется -ичным потомком числа если

Выяснить, является ли данное целое -ичным потомком целого может оказаться затруднительным. В случае когда равно простому числу для нахождения простого эквивалентного условия, записанного через сочетания будет использоваться приведенная ниже теорема (напомним, что при принято считать

Теорема 13.3.3 (теорема Лукаса). Пусть простое число, и пусть

и

— p-ичные разложения двух произвольных целых чисел Тогда справедливо следующее соотношение:

Кроме того, равно нулю по модулю тогда и только тогда, когда не является -ичным потомком числа

Доказательство. Второе утверждение следует из первого, так как при всех не равпо нулю по модулю тогда и только тогда, когда является -ичным потомком Необходимо доказать лишь первое утверждение теоремы.

Доказательство состоит в разложении многочлена двумя различными способами и последующем приравнивании коэффициентов при одинаковых степенях х. Используя теорему 4.6.10, можно записать следующее тождество над

Тогда для произвольного имеем

Используя биномиальное разложение обеих частей этого равенства, перепишем его в следующем виде:

где каждое не больше и поэтому меньше Далее приравняем коэффициенты при х и получим

где суммирование ведется по всем -совокупностям в которых каждая компонента меньше

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

Это завершает доказательство теоремы.

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

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

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

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

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

Кодовый многочлен удовлетворяет соотношению а добавленный символ равен сто Пусть Тогда

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

Переставленное слово с является кодовым, если выполняется соотношение остающееся, очевидно, справедливым и после перестановки, и если, кроме того,

при всех для которых является корнем Рассмотрим такое

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

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

для всех и всех для которых является корнем Как и ранее, имеем

Пусть — число ичных потомков перенумеруем их числами при Запишем сумму по ним в виде

Пусть теперь произвольны. Полагая равным 1, а а поочередно равным первым К последовательным степеням а, получаем

Эта матрица — матрица Вандермопда. Она обратима, так как все ее столбцы различны. Поэтому при Следовательно, корень всех являющихся потомками j в -ичном представлении. Это завершает доказательство теоремы.