элемент О в GF (q) будем обозначать как а°°. Перенумеруем следующим образом компоненты вектора (c„ i, с, Со, Сос) из "ё элементами GF (q"): компонента со нумеруется локатором а~, а компоненты Ci при О < г < - 1 - локаторами а.

Группа перестановок называется транзитивной, если для любой пары локаторов (X, Y) в кодовом слове существует перестановка в группе, меняющая их местами; при этом возможно также изменение порядка других локаторов. Группа перестановок называется дважды транзитивной, если для любых двух пар локаторов ((Xi, Yi), (Xg, Kg)), где ХфХ, YlФY2, существует такая перестановка в группе, которая меняет местами локаторы как в первой, так и во второй паре. При этом также возможно изменение порядка других локаторов.

Аффинная перестановка - это перестановка, которая переводит компоненту с локатором X в компоненту с локатором аХ + + 6, где с и 6 - любые фиксированные элементы из GF (<?") и аф 0. Множество всех аффинных перестановок образует группу относительно композиции, так как: 1) если локатор X переходит в локатор Y = аХ + 6 и локатор Y переходит в локатор Z = = aY + Ь, то X переходит в Z = ааХ + аЬ + Ь и 2) перестановка а-Х - а~Ь обратна перестановке аХ + Ь. Группа аффинных перестановок дважды транзитивна, так как при заданных парах (Xi, Yi) и (Х, Kg) система уравнений

Yi = аХг + Ь, Y2==aX2 + b

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

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

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

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

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

/ = /о + /.7 + + /т-1Г. О <u<q.

[), будет

условия, записанного через сочетания

приведенная ниже теорема (напомним, что при т п принято j = 0).

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

i = /о -г /]Р Н-----г jmxP

k = ko k,p . . . + k,„ ,pn-l

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

(1)=п(;;)(п.<х1р).

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

Доказательство. Второе утверждение следует из первого, так как при всех i не равно нулю по модулю р тогда и только

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

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

(1 -f х)р = 1 -\-ХР\ Тогда для произвольного / имеем (1 -1- х)/ == (1 -L x)o+/iP+/,P=+-+;,„ iP"-

= (1 -1- x)h (I -\..xP)h (1 -i-хру. ... (1 -\-хР"-У"-К

Отличное от / целое число k в -ичном разложении: !А: = А + А:,9 + М+•• f m-i?-"-. 0ki<q, называется q-тным потомком числа /, если ki < ji, / = О, . .., m - I.

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

использоваться

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

L*m-i

m-1 , . . , ,=0 \ "m.-i /

"m-lP

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

(;.)=S(t)(i:)-(.r:)<-"°-rt.

где суммирование ведется по всем т-совокупностям (o.i. •• •-I m-i). в которых каждая компонента меньше р и

k==ko -f + kp- + + km.,p"-.

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

(i)=(i:)(i.)-(t:)<"°)-

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

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

Те рема 13.3.4. Пусть а - примитивный элемент поля GF (cj) характеристики р, пусть ё - циклический код длины 9" -• 1, порождаемый многочленом g (х), у которого а° не является корнем, и пусть ё - расширенный код, получаемый из него добавлением символа проверки на четность. Расширенный код инвариантен относительно группы аффинных перестановок тогда и только тогда, когда из того, что а* - корень g (х), а k - ненулевой р-ичный потомок k, следует, что а" также является корнем g (х).

Доказательство. Пусть X = аХ + b означает аффинную перестановку. Пусть Xi, Xg, Xv - локаторы ненулевых компонент кодового слова с, и пусть значения этих компонент обозначены через Yi, Кг, К. Пусть, далее, Хь Хг, Xv озна-