рассмотрим величины и,. = gr-thi , в силу равенства h {х) X

X §• (х) = X" - 1 равные нулю при О < г < п. Но тогда

Un-l Ч-п-2

Un-г «п-з

Uh-l

= 0,

и, следовательно, так определенная матрица Н действительно является пр(;)верочной матрицей. Теперь видно, что дуальный код для циклического кода с порождающим многочленом g (х) также является циклическим, так как Н представляет собой его порождающую матрицу и имеет вид порождающей матрицы циклического кода. Порождающий многочлен дуального кода равен взаимному к h (х) многочлену Н (х) = xh (х"). Иногда при рассмотрении циклических кодов дуальным называют код, порожденный многочленом h (х), но если быть точным, то в этом случае можно говорить только о коде, эквивалентном дуальному коду.

Можно также просто получить порождающую матрицу в систематическом виде. Воспользуемся алгоритмом деления и выпишем для каждой информационной позиции i = 1, k многочлен

X- = Qiix)gix)-\-St{x), i-l.

n-k-l Si{x)= Ц SjiX.

Тогда многочлен x"- - Sj (х) является кодовым словом, так как

X-~ Si{x) = Qtix)g{x).

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

- So,k • -sn-k-l).k 1 О ... О

--0, к-1

S(n-ft-I), ft-I О 1

- «0,1 • • • - S(/i-ft-i).i О О ... 1 В этой систематической порождающей матрице индексы координат информационных символов пробегают числа от п - k до п - 1. Чтобы выписать такую порождающую матрицу, необ-

5.б. коды хэлшинга как циклические коды 131

ходимо только вычислить все остатки Sj (х) от деления x на g (х). Используя описанные в § 3.2 методы, теперь можно выписать и проверочную матрицу кода. Она равна

1 О . . О So,ft ... So.i

О 1 ... О Si, ft ... Si, г

С о ... 1 S(„ ft i), k

S{n-k-l), 1

5.5. КОДЫ ХЭММИНГА КАК ЦИКЛИЧЕСКИЕ КОДЫ

Порождающий многочлен (7,4)-кода Хэмминга, использованного в начале главы, равен g (х) = х + х + 1. Корнем этого многочлена является примитивный элемент а поля GF (8), и, следовательно, все кодовые слова удовлетворяют равенству с (а) = 0. Аналогично, чтобы получить код Хэмминга с примитивной длиной п = 2" - 1, выберем g (х) так, чтобы примитивный элемент а поля GF (2*") был его корнем, а именно положим g (х) равным минимальному многочлену р (х) элемента а, используемому для построения поля GF {2"). Тогда так как с (х) = а (х) g (х), то с (а) - О для каждого кодового слова. Это эквивалентно равенству сН = О, где

Н = К ai . . . а"-].

Для больших алфавитов также существуют коды Хэмминга. В § 3.4 мы видели, что для каждого т существует код Хэмминга над полем GF (д) с п = {д"" - \)l(ci - I) и k = {q" - 1)/{д-1) - - т. В данном параграфе мы покажем, что многие из этих кодов (хотя и не все) являются циклическими, выписав их порождающие многочлены.

Пусть ос - примитивный элемент поля GF (д"), и пусть р = = а*-. Тогда p(?"-)/(7-i) =1, и, следовательно, Р является корнем многочлена хч-"- - 1. Таким образом, минимальный многочлен элемента Р является делителем многочлена («"-ОА?-!) - 1 и может быть выбран в качестве порождающего многочлена циклического кода длины п = {д" - 1)/{д - 1). Проверочная матрица равна Н= [р" р ... р"-].

Для 9 = 2 и р = а легко доказать, что этот код исправляет одну ошибку, указав простую процедуру исправления одной ошибки. Принятое слово записывается многочленом степени п - 1 в виде

• vix) = a{x)g (х) + е (х),

где многочлен е (х) содержит не более одного ненулевого коэффициента, так что е (х) = О или е (х) = х. Целое число i маркирует позицию, в которой произошла ошибка. Для маркировки ошибочных позиций мы будем также использовать поле GF (2"). Элемент поля а соответствует компоненте с номером i. Так как = О, то и (а) -Ф, и все степени а от О до 2" - 2 различны. Таким образом, по величине а сразу определяется позиция ошибки, за исключением случая v (а) == О, соответствующего отсутствию ошибки. Следовательно, рассматриваемый код является исправляющим одиночную ошибку кодом над GF (2) с п = = 2" - 1 Vl k = п - m; на самом деле это код Хэмминга над GF (2).

Мы доказали для случая <? = 2 формулируемую ниже теорему. Общий случай этого утверждения более сложен, так как для произвольного элемента у из GF (q) все величины вида у должны быть различны. Докажем формально теорему для произвольного q.

Теорема 5.5.1. Минимальное расстояние кода с проверочной матрицей Н = [р« ... р"- ], где р = а-?- и п = (q - l)/(q - - 1), равно по меньшей мере 3 тогда и только тогда, когда п и q - 1 взаимно просты, что возможно тогда и только тогда, когда т и q - 1 взаимно просты.

Доказательство. Предположим, что два столбца матрицы Н линейно зависимы: р = -ур, где элемент у принадлежит GF (q). Тогда элемент р" принадлежит полю GF (q) и, следовательно, является корнем уравнения x-~ - 1 = 0. Но ненулевые элементы поля GF (q) можно представить через примитивный элемент а поля GF {q) в виде первых q - 1 степеней элемента «(«"-ОЧ?-!), так как все такие степени различны и

((а(7"-)/(?-1)))-1=: 1.

Тогда для некоторого k, меньшего q - 1, имеем Р-/ = (а(«"-1)/(?-1))* = anft.

Далее, так как р == а"-, то

(q - 1) (• - /) = nk.

Так как i - / меньше, чем п, то это уравнение разрешимо относительно i - /тогда и только тогда, когда п ч q - 1 не являются взаимно простыми; таким образом, Н содержит два линейно зависимых столбца тогда и только тогда, когда п и q-1 не являются взаимно простыми.

Покажем теперь, что п п q - 1 взаимно просты тогда и только тогда, когда т и q - 1 также взаимно просты. Но