е(х) s(x)

х R,x

Рис. 5.1. Таблица значений синдромов.

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

5.3. МИНИМАЛЬНЫЕ МНОГОЧЛЕНЫ И СОПРЯЖЕНИЯ

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

х«-1 =fAx)h{x)...fsix),

где s - число простых множителей. Произведение произвольного подмножества этих множителей дает порождающий многочлен g (х). Если все простые множители многочлена х" - 1 различны, то всего имеется 2 - 2 различных нетривиальных циклических кодов длины п (исключаются тривиальные случаи g (х) = I и g (х) --= х" - 1). Какие из них, если они вообще имеются, дают коды с большим минимальным расстоянием - вопрос, на который сразу ответить нельзя.

Предположим, что g (х) представляет собой порождающий многочлен. Он делит многочлен х"- 1, и, следовательно, g (х) = =IX/j (х), где произведение берется по некоторому подмножеству множества s простых многочленов. Порождаемый многочленом g (х) циклический код состоит из многочленов, которые делятся на каждый из этих ft (х). Многочлен g- (х) можно найти, найдя все его простые делители.

122 гл. Б. ЦИКЛИЧЕСКИЕЕКОДЫ

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

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

Определение 5.3.1. Для кода над GF (q) длина п вида п = ~ q" -1 называется примитивной. Циклический код примитивной длины над Gf (q) называется примитивным циклическим кодом.

Поле GF (q) является расширением поля GF (q). Согласно теореме об однозначном разложении, разложение

над полем GF (q) однозначно. Так как g (х) делит многочлен х?"-1 - 1, то он должен быть равен произведению некоторых из этих множителей. С другой стороны, каждый ненулевой элемент поля GF {q") является корнем многочлена xi"- - 1. Следовательно, в поле расширения GF (q") многочлен х- - 1 можно представить в виде

- 1 =П(-Р

где Ру - все ненулевые элементы поля GF {q). Отсюда следует, что каждый из многочленов /; (х) может быть разложен в произведение некоторых из этих линейных множителей и что каждый элемент р является корнем точно одного из fi{x). Этот многочлен fi{x) является минимальным многочленом элемента Р, и мы такжеобозначим его через fj{x). Он представляет собой многочлен наименьшей степени с коэффициентами из основного поля GF (q), для которого элемент р из расширения поля является корнем.

Теперь мы можем связать данное определение циклического кода с использованной в § 5.1 его трактовкой.

Теорема 5.3.2. Пусть элементы Р, Р из поля GF (9") являются корнями порождающего многочлена g {х) примитивного кода. Многочлен с (х) над GF (q) является кодовым тогда и только тогда, когда

=сф) = ... =сфг) = 0,

) Мы извиняемся за неопределенность в использовании/г (х) при 1= l,...,s для обозначения различных минимальных многочленов и fj (х) при / = 1, q - 1 для обозначения минимальных многочленов элементов Pj. Конкретный смысл всегда будет ясен из контекста.

где с (Р/) вычисляется в поле GF {q").

Доказательство. Если с (х) = а (х) g (х), то имеем с (р-) = = а ifij) g (Pj) = 0. Обратно, предположим, что с (Ру) = О, и запишем

cix) = Q (х) fj {X) + S (х),

где степень s (х) меньше степени fj (х), а fj (х) - минимальный многочлен элемента Ру. Но тогда из равенства

О = с (р) = Q (р) (р) + S (р,.) = S (р,.)

следует, что s (х) = 0. Следовательно, с {х) должен делиться на fj{x) для всех /= 1, г, а поэтому и на НОК [fi{x), /, (X), .... frix)] =gix). □

Чтобы проиллюстрировать эти идеи, выберем /г = 15. Можно найти все циклические коды длины 15, разложив х - I на простые многочлены-

х1« - 1 = (х + 1) {х + х + 1) (х* + X + 1) (х* -f

+ х 4- 1) (х* + хз + х + X + 1).

Справедливость такого разложения можно проверить перемножением, а простоту множителей - методом проб и ошибок. Всего имеется 2 = 32 подмножества множества этих простых множителей и, следовательно, 32 порождающих многочлена циклических кодов длины 15. Два из них {g (х) - х - 1 с k = О и g (х) = 1 с k - п) являются тривиальными, а 30 приводят к нетривиальным циклическим кодам. В качестве примера рассмотрим один из них, положив

g (х) = (х* + Х + 1) (X* + Х« + Х + X + 1) =

= х» +х* -f х +х -f 1.

Так как степень g (х) равна 8, топ - к = 8ик = 7,а так как вес многочлена g (х) равен 5, то минимальное расстояние не превосходит 5. В гл. 7 мы увидим, что минимальное расстояние равно 5. Следовательно, рассматриваемый код является (15, 7, 5)-кодом й позволяет исправлять две ошибки. Проверочные соотношения Могут быть записаны в виде

с (&) = О, с (ai) =0, л

Ае a и W - некоторые корни многочленов х* + х + I и х* + + х -f X* -f X -f 1 соответственно из расширения OF (16). В част-йос¥и, с (а) = О и с (й) = О, и, следовательно, это рассмотренный в §5.1 пример. (Многочлен g (х) имеет, конечно, и другие корни, но этих двух корней достаточно, чтобы определить g (х), и нет необходимости проверять остальные.)