чают локаторы ненулевых компонент кодового слова при аффинной перестановке, т. е. Xl = aXi + b.

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

Кодовый многочлен удовлетворяет соотношению с (х) = = g (х) d (х), а добавленный символ равен Соо = -(c„ i + • • + +Со). Пусть Cj = с (а) = Ij"=oac,-. Тогда

С,- = S Cta = Т ViM = О

1=0 1=0

при всех /, для которых а является корнем g{x). Заметим, что в локаторе а" может быть ненулевой символ. Но а°° есть представление нулевого элемента; поэтому соответствующий Xi является нулем. Даже в тех случаях, когда слагаемое КХ при равном нулю Х[ не входит в определение Cj, можно считать его входящим, так J<aK оно равно нулю.

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

Ci = Т YiXi = О 1=1

при всех /, для которых а является корнем g{x). Рассмотрим такое /:

с;-= 2 № + Ь)/=

/ =1 k=0 k=0

По TeopeMeJ3.3.3 равно нулю по модулю р,"если k не является ;о-ичным потомком /; для тех же k, которые являются р-ич-ными потомками /, по предположению Ch равно нулю. Следовательно, в каждом слагаемом суммы или ( ) равно нулю, или Ch равно нулю. Поэтому С] равно нулю и переставленное кодовое слово снова является кодовым словом.

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

Ci TYiiaXi [-Ьу = 0 1=1

Эта матрица - матрица Вандермонда. Она обратима, так как все ее столбцы различны. Поэтому Ck = О при 1 = 1, К-

Следовательно, а* -• корень g (х) при всех ki, являющихся потомками / в р-ичном представлении. Это завершает доказательство теоремы. □

13.4. ЦИКЛИЧЕСКИЕ КОДЫ,

ОСНОВАННЫЕ НА ПЕРЕСТАНОВКАХ

Теперь опишем метод построения некоторых допускающих одно-шаговое мажоритарное декодирование кодов, основанный на группе аффинных перестановок (см. § 13.3). Этот метод может применяться для нахождения циклических кодов над GF (q) длины п при условии, что л - составное число, а именно что л = = L- J. Кроме того, необходимо предположить, что L не сравнимо с нулем по модулю р, где р - характеристика GF (q). Это условие всегда удовлетворяется для тех п, которые являются примитивной длиной или ее делителем.

Выберем длину кода л примитивной и составной; п = q - 1 и л = L. /. Тогда

X" - 1 = {xJy- - 1 =

= {х - 1) {х (-) + Х- <-2) +

+ x-f 1).

для всех ая b и всех /, для которых а является корнем g (х). Как и ранее, имеем

с;-= t (i)fc-vc. = o.

Пусть К - число /о-ичных потомков /; перенумеруем их числами ki при / = 1, К- Запишем сумму по ним в виде

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

Обозначим второй член этого разложения через а {х), так что

я« - 1 = {х - 1) а (х).

Ненулевые элементы GF {q") являются корнями или х - 1, или а (х). Если а - примитивный элемент GF {q), то а- = 1 и а--", а-) ojL 1 являются / корнями х- -

-1. Поэтому при каждом /, не кратном L, а является корнем а (х).

Определим многочлен й (х), такой, что взаимный ему многочлен является проверочным многочленом рассматриваемого кода. При всех /, которые не кратны L и q-ичнъш потомок которых не кратен L, а является корнем й (х). Так как каждый корень й (х) является корнем а (х), многочлен а (х) кратен й (х).

Пусть h (х) »- многочлен, взаимный к Н (х), и пусть g (х) определяется соотношением

g (Х) h(x) =X-\.

Мы получили два циклических кода, являющихся дуальными. Пусть W - циклический код с порождающим многочленом g (х), а W-- - циклиЧеский код с порождающим многочленом Я (х). По определению й (х) и по теореме 13.3.4 W-- - циклический код, обладающий свойством дважды транзитивной инвариантности. Поэтому можно расширить W-- до кода W--, который является инвариантным относительно группы аффинных перестановок.

Составим / проверочных равенств для циклического кода W, согласующихся в одной координате. Так как код циклический, он мажоритарно декодируем и его минимальное расстояние не меньше / -f 1. Найдем указанные проверочные равенства для кода ё, оперируя с дуальным кодом W--.

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

а (х) = х (-1) + х (-2) Н-----h-x-f-l

тогда и только тогда, когда / не кратно L. Следовательно, а {х) кратно й (х) и является кодовым словом дуального кода. Поэтому все элементы множества многочленов

{а(х), ха(х), ха(х), .... x~ а (х)]

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

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