все коэффициенты которого (после раскрытия скобок) будут элементами поля GF (4). Для того чтобы указать эти элементы из поля GF (4), надо, однако, выделить элементы подполя GF (4) среди элементов поля GF (256). В поле GF (256) подполе GF (4) состоит из элементов {О, 1, а, а"}, так как элементы а" и а}° являются единственными элементами поля GF (256) порядка 3.

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

Теорема 5.3.7. Пусть GF (q) - конечное поле. Если п и q взаимно просты, то многочлен х" - 1 делит многочлен х"- - 1 при некотором т и многочлен х" -1 имеет п различных корней в расширении GF (q") поля GF (q).

Доказательство. Необходимо доказать только, что п делит q" - 1 при некотором т, так как в этом случае можно воспользоваться общим разложением

(х - 1) = (х - 1) (х-- -f х-2 + х-з 1)

чтобы показать, что при q" - 1 = nb для некоторого b имеет место равенство

ХП""-! - 1 = (х") ~ 1 =

= (Х" - 1) (Х" -f X" ("-2) -- . . . + Х« + 1).

Таким образом, х" - 1 делит х*"- - 1 и, следовательно, имеет п различных корней в GF {q"), так как х"*"- - 1 имеет qm - I различных корней в этом поле.

Чтобы доказать, что п делит q" - 1 для некоторого т, воспользуемся алгоритмом деления и выпишем п + 1 следующих равенств:

q = Qi« +

q"- = Qzn + «2. q = Qan + Ss,

Все остатки расположены между О и п - 1. Так как их всего R + 1. то по меньшей мере два из них равны между собой, скажем Sj и Sj при 1, меньшем /. Тогда

qi - 9 = Qjti -f Sj - Qiti - Si.

q{q--l) = {Qj~Qi)n.

Так как q и n взаимно просты, то п должно делить qi-~ - 1. Полагая т= j-i, завершаем доказательство. □

Используя эту теорему, любой циклический код в случае взаимно простых п и q можно описать в соответствующем расширении поля. Порождающий многочлен g (х) циклического кода длины п делит многочлен -1, который делит х""--1, так что g (х) делит также х"*"- - 1. Мы всегда будем пользоваться наименьшим т, для которого это выполняется. Пусть а - примитивный элемент поля GF {q"), пусть q" - 1 = nb, и пусть Р = а". Тогда все корни многочлена х" - 1 (а поэтому и многочлена g (х)) исчерпываются степенями элемента р. Простые делители многочлена х" - 1 имеют своими корнями только такие элементы.

Подводя итоги, скажем, что если мы используем р а*" вместо а и ограничиваем множество корней порождающего многочлена только степенями р, то мы получаем циклический код длины п = (q" -- \)lb.

5.4. МАТРИЧНОЕ ОПИСАНИЕ ЦИКЛИЧЕСКИХ КОДОВ

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

Имеется много способов формирования этих матриц. Прежде всего проверочную матрицу можно формировать в расширении поля так, как это было сделано в § 5.1. Если нулями g {х) являются элементы Vj GF (q") при /=!,...,/-, то

"Ё«У/ = 0, j=l,

что б матричном виде можно переписать как

- о 1-

Yi Yi

Y2 Y2

Y? yl

Уг-

Заменим теперь эту {г X п)-матрицу над GF (д"") на (гт X п)-ма-трицу над GF (д), заменяя каждый элемент Р вектор ом-столбцом коэффициентов многочлена, представляющего Р над GF (д). Это дает проверочную матрицу над GF (д), но некоторые строки этой матрицы могут быть линейно зависимыми и, следовательно, являются излишними. Удалим наименьшее число строк, необходимое для построения матрицы с линейно независимыми строками. Это приведет к проверочной матрице кода.

Хотя описанная процедура проясняет связь между корнями порождающего многочлена и проверочной матрицей кода, она слишком сложна для использования. По порождающему многочлену можно построить необходимые матрицы, даже не переходя в расширение поля. Одним из способов сделать это является построение порождающей матрицы непосредственно по порождающему многочлену. Так как кодовые слова записываются в виде с (х) = i (х) g (х), то в матричной форме имеем

О ... О

gn-h gn-k-1 gn-k-2.

gn-h-1 gn-h-2 gn-k-S

g2 gl go

gi go 0 go 0 0

0 0

проверочная матрица соответственно равна

0 0 О ... hk i hk

Q К hi .. . /гь 1 Ль О 0 0

Jio Ы h . . . hn О О ... О 0.

где h {х) -- проверочный многочлен циклического кода. Для проверки равенства

GHt = 0