3.8    Циклические коды

Линейный (гг, &)-код С над полем ¥ч называется циклическим, если для любого вектора (ао,а\,..., ап-\) Є С вектор

{0"п-\і а0і а1і ■ ■ ■ і Оп^г) £ С. 125

Отождествим пространство ¥™ с фактор-кольцом ¥д[х]/(хп — 1) относи­тельно изоморфизма (ао, аь ..., ап-1) ~^ ао + + • • • + ап-\хп~1. Смеж­ный класс а £ Рд[х]/(х" — 1) часто будем записывать без черты.

Утверждение 1. Линейный код С является циклическим тогда и только тогда, когда С-идеал в ¥д[х]/(хп — 1).

ДОКАЗАТЕЛЬСТВО. Действительно, если С - идеал и (<7(). а\..... ап-\) £ С, то х • (ао + а\х + • • • + ап-\хп~г) = ап^\ ■ 1 + ао ■ х + ■ ■ ■ + ап^2 • хп^1 £ С, т.е.   (ап_1, ао,..., ап-2) принадлежат С. Обратно, если С - циклический код, то для любого элемента Ь £ С элементы хЬ,..., хп~1Ъ принадлежат С. Следовательно, для любого элемента

_ п—1

у = ро ■ 1 Н-----\-рп-\хп~1 £ ¥д[х]/(хп - 1), у ■ Ъ = ]Г р,;хг - Ъ £С.

$=0

Если С - идеал в Рд[х]/(х" — 1), то он является гомоморфным образом некоторого идеала Р в Рд[х], содержащего идеал (хп — 1).

Утверждение 2. Идеал Р является главным, т.е. Р = (д(х)), где д(х) - некоторый делитель (хп — 1) и старший коэффициент д(х) равен единице.

ДОКАЗАТЕЛЬСТВО. Пусть д(х) - ненулевой многочлен минимальной степени из идеала Р. Тогда можно считать, что старший коэффициент д(х) равен единице, и если (р(х) £ Р, то по лемме о делении с остатком (р = д ■ -Ф + г. где г = 0, либо о1едд > о1едг. Так как г = <р — дф £ Р, то, ввиду минимальности о!ед(д),г = 0 и Р = (д(х)). Так как (хп — 1) £ Р, то д(х) делит (;/;" — 1).

Ясно, что С = (д(х)). Многочлен д(х) называется порождающим много­членом кода С, а многочлен Н(х) = (хп — 1)/д(х) называется проверочным многочленом кода С.

Пусть д(х) = до + д\х + • • • + 1 • хп^к и Н(х) = Но + Н\х + • • • + Н^хк. Тогда ЯоНо = —1, *£2 Яг^т-г = 0.1 < т < г/ — 1. //./,. = 1. Далее, из включений

д. ~х~д...., хк^1д £ С и неравенства доф 0 следует, что следующую матрицу

/

в =

9о 9і О до 9п-к 0

9п-к

0

о

о \

о

\ 0   0   ...     0      д0    ... дп_к )

ранга к, где дп_& = 1, можно взять в качестве порождающей для кода С (т.е. векторы д, хд,..., хк^1д действительно образуют базис идеала С). Матрица

0    Нк   Н^\ ■ ■

н

/о о

о о

Нк і Ло О

Ы Ы Но \ Н\ Но О

О

является провероч-

/

НОИ.

Как уже отмечалось, порождающих матриц для линейного кода много, т.к. они соответствуют базисам этого кода. Укажем некоторый канониче­ский алгоритм выбора порождающей матрицы циклического кода С с по­рождающим многочленом д(х) степени (п — к) и с проверочным многочле­ном Н(х) = (хп — 1)/д(х)

Замечание 1. Пусть у(х) £ Гд[х]/(хп — 1). Тогда у(х) £ С -Ф4> у ■ Н = 0. Замечание 2. Предположим, что нам необходимо передать информа­цию ((Ц). о\..... (ц--\). Рассмотрим элемент

а(х) = Щ) + а\х + • • • + аи-\хк 1 в Гд[х]/(хп — 1).

Закодируем его многочленом гп(х) = а(х)д(х) в ¥д[х]/(хп — 1), где д(х) -порождащий многочлен кода С. Пусть у(х) - принятый для декодирования многочлен. Если остаток у(х) от деления на д(х) не равен нулю, то при передаче произошла ошибка.

Рассмотрим алгоритм Евклида (деления с остатком):

хп^к = ап^к(х)д(х) + •/•„_*.хп к+1 = ап^к+1(х) ■ д(х) + г„_*+ь

хп 1 = ап-1(х)д(х) + г„_ь

где о1едг^ < п — к^<п— 1.

В силу замечания 1, (х3 — т^) £ С. Следовательно, многочлены д^[х) = хк(х-' — /'.;) € С. ] = гг — к, п — к + 1,. .., п — 1. Если многочлены 5^- линейно зависимые, то при некоторых     £ ¥д (не все А^- равны нулю ^2 А;ч/;- = 0. Откуда следует, что

х (Хп^1ап^1 + Хп^2ап^2 Н-----1- Хп-кОп-к) • д(х) = 0.

Так как х не делит к и (1сд(Хи-\ои-\ + • • • + Хп^кап^к) < к — 1, то //(:/;) не делит    (^ Л;с/;). Следовательно, Лг- = 0,г<гг — 1. Пусть

Я и—к = х (х Тп^к) = Ж (   Тп^к$    Тп—к\Х     • • •     '" / ^ —    — л- — I -' * ~Ь х ),

дп-1 = хк(хп 1 - г„_1) = жй(-гте^ю - г„_цж-----гте^1те^1Жте й 1 + хп 1

Соответствующая порождающая матрица равна

^ 1   0    0     ...    0     -Гп_*,0       -Г„_*д     . . .      -Г„_*,„_*_1 \

,, т        0 1   0   ...   0 — гп-к+1,о — Гп-к+1,1 •••   — гп-к+1,п-к-1 \1кЩ =

\ 0 0   0   ...   1    -г„_ю     -г„_1д    ...    -г„_1,„_*_1 )

Будем считать в дальнейшем, что (п. д) = 1. Если     — 1 = /|/2... /, разложение на неприводимые многочлены в ^[ж], то, так как (:/;" — 1)' = пх"^1 и (п. д) = 1, (;/;" — 1) не имеет кратных корней.

В силу 3.3 каждый идеал (/»•) является максимальным, а соответствую­щий код называется максимальным циклическим кодом. Код, порожден­ный (хп — 1)//г, называется неприводимым циклическим кодом.

Замечание 3. Так как каждый делитель (;/;" — 1) имеет вид /,"' ... /;);". где £/ = 0,1, то число нетривиальных делителей (ф 1,— 1) равно (2т — 2), т.е. циклических кодов длины п не более (2т — 2).

Замечание 4. Пусть п|.....п.,. элементы алгебраического замыкания поля ¥д и р\ (;/;).. ... р.н{х) - (соответственно) их минимальные многочлены над ¥д. Пусть п - минимальное натуральное число с условием, что о',' = «2 = • • • = си" = 1. Тогда д(х)= Н.О.К. [р\.р->. ■ ■ ■ ■ /->.-,-] делит (;/;" — 1). Пусть С С.¥™ - циклический код с порождающим многочленом д(х). Тогда /(х) £ С в том и только в том случае, если /(о |) = • • • = /(п.,.) = 0.

Утверждение 3. Пусть а - примитивный элемент поля />« и р(х) = (х — а)(х — а2)... (ж — а2"1 1) - его минимальный многочлен над полем И>. Тогда бинарный циклический код С длины п = 2т — 1 с порождающим многочленом р(х) эквивалентен бинарному (2т — 1, 2т — т — 1)-коду Хэм-минга.

ДОКАЗАТЕЛЬСТВО. Так как {1, а,..., а"1"1} - базис />« над Ь'->.

то имеют место равенства

а

а

1 • 1 0-1

0 • а

1 • а 0 • а 0 • а т—1

т—1

а

а1

т—1

0-1 0 • а

<*>0,т+1 - 1    +   0>1,т+1 ' а

и'т—1,т+1 ' 5

2та^2

—   ао,2™^2 ' 1   +   И-1.2'"-2 ' ОС

Рассмотрим соответствующую матрицу

/ 1 0 ...   0    ао,т+1    • • •    ао,2™^2 \

0   1...    0     а1,т+1      • • • 0>1,2т-2

я

\ о о

1 0>т.—

т—1,т+1

а,

1—1,2"*—2 /

«•//»-1.2"'-2 • ОС т—1

Покажем, что Н - проверочная матрица для кода С. Пусть а = (Ь0,6Ь ..., Ь„_і) и а(ж) = 60 + Ь\ Н-----1- Ь„_іжп_1

соответствующий

многочлен. Имеем /1 о О 1

И-а

т

О О а0,т+1 а1,т+1

О>0,2т-2 0>1,2т-2

Ьі

\0 0 ...   1 ат-і,т+і

/    6о     + ао,т+1&т     +   • • •

&1    + а>і,т+іЬт    +  • • •

\ Ьт^\   -\- 0>тп—\,т+\Отп   ~Ь   • • •

И

~Ь   &т—1,п^п—1 /

а(а) = (Ь0 + аот+1&т Н-----1- аоп&п-О • 1 + (&1 + а1ТО+1&т Н-----Ь

+Д1те6те^1) • сН-----1-

Ясно, ЧТО тогда и только тогда, когда а(а) = 0. Последнее усло-

вие равносильно делимости р(х)\а(х), так как р(х) - неприводимый мно­гочлен. Итак, мы доказали, что Н - проверочная матрица для линейного (п, п — т)-кода С.

Для доказательства того, что С - ход Хэмминга, осталось доказать, что множество столбцов Н исчерпывает множество чисел

1,2,

в двоичной системе исчисления. Для этого достаточно заметить, что ника­кие два (ненулевых!) столбца не совпадают. В противном случае ак = 1, где к < 2т — 2, что противоречит примитивности а (а - циклический по­рождающий ГруППЫ Р2*т = Р2т \ {0}).

Утверждение 4. Пусть С - циклический код в ¥д[х]/(хп — 1) с поро­ждающим многочленом д(х), корни которого равны а\,.... о„_д.. Много­член /(х) = 6о + Ь\х + • • • + 6п_іжп_1 Є С тогда и только тогда, когда

ДОКАЗАТЕЛЬСТВО. Многочлен /(;/;) Є С тогда и только тогда, ко­гда f(cti) = О, і < п — к. На матричном языке эти условия равносильны

/ ь0 \

равенству Я = о.

Предположим, что мы имеем циклический код с порождающим много-

членом д{х): который, в свою очередь, является минимальным многочле­ном для а Є і^га, ап = 1, над полем і^. Согласно предыдущему для испра­вления ошибки в полученном слове у необходимо вычислить синдром этого слова. Укажем один из алгоритмов такого вычисления. Элемент а являет­ся корнем <р(х) Є Рд[х]/(хп — 1) тогда и только тогда, когда д(х)\ір(х). Сле­довательно, синдромом вектора у = (уо, у\,..., уп-і) можно считать вектор

Б(у) = (1аа2 ... ип^1) ■ ут = у (а) = Уо + у\а + • • • + уп-\ап~1. Если при передаче слова гп получено слово у и совершено не более одной ошибки, то у = ш + е, где е = 0. .г*7'-1 (в бинарном коде). Следовательно, синдром Б (у) = Б(е) = 0. о7'-1. Этот синдром еще называют локатором ошибок. Если Б (у) = си-7'-1, то ошибка произошла в ^'-ой координате (ибо аг ф а3 при г ф 3, г < п - 1, з < п - 1).