Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
фиксирв) ванного расширения поля а р{ (х), i 1, s, - минималь! ный
многочлен элемента щ над полем Fq, Пусть п б М таково, Щ
1 для всех l 1, s. Положим g (х) ~ НОК (pi (т)
• A 11 . : Ы%'1Щ
I
} См, гл, 8* § 3, - Прим. перев,
§ 2. Циклические коды
605
ps (х)). Тогда многочлен g (х) делит хп - J. Если С е ;FJ - циклический
код с порождающим многочленом g (х), то v (х) ? С
тогда и только тогда, когда v (аЦ = 0, i - 1 s. В качестве
примера того, как связаны описания циклического кода с помощью
порождающего многочлена и с помощью кодовых многочленов, докажем
следующий результат. При этом используется понятие эквивалентности кодов,
определяемое в упр. 9.10.
9.40. Теорема. Бинарный циклический код длины п - 2т - I, порождающий
многочлен которого является минимальным многочленом над полем Fa для
некоторого примитивного элемента ноля F т> эквивалентен бинарному (п, п -
т)-коду Хэмминга.
Доказательство. Обозначим через а примитивный элемент
поля L, и пусть &
р (х) ----- (х - а) (х а2) . . . (х - а2'"-1)
- минимальный многочлен элемента а над полем Fa. Рассмотрим теперь
циклический код С, порожденный многочленом р (х). Построим матрицу И
размера тХ(2т ~ 1), /-й столбец которой имеет вид (с0, сх, Ст^}7, где d G
F2 и
т-1
а/_1 = ? с1а*> j ~ Ь 2, . .., 2т - 1.
(=0
Если а = (а0, %, an_L) и а (х) - а0 -f ахх 4..........4~ €
G Fa Ex], то вектор #ат соответствует элементу а (а), выраженному в
базнсе {1, а, ..., ат~1}. Следовательно, равенство Яат =:= 0 выполняется
только тогда, когда минимальный многочлен р (х) делит а (х). Таким
образом, матрица Н является проверочной матрицей кода С. В силу того что
столбцы матрицы Н представляют собой перестановку двоичной записи чисел
1, 2, 2т - 1, все они различны. Теорема доказана. ?
9.41. Пример. Многочлен х4 4- х 4 1 является примитивным многочленом над
полем Fa, и, следовательно, его корнем будет примитивный элемент а ? Fie.
Если для всех 15 элементов af ? ? Ffe, / = 0, 1, 14,
воспользоваться векторной записью,
выражая их в базисе jl, ot, а2, а3|, и из полученных векторов, используя
их как столбцы, образовать матрицу размера 4x15* т° мы получим
проверочную матрицу кода, эквивалентного (15, И)-коду Хэмминга. При этом
сообщение вида (а0, alt ап) иодируется в кодовый многочлен
w (х) - а (х) (х4 4~ х + 1),
ГДС- а (х) = + ахх + - - ¦+ al0xi0. Предположим теперь, что
Многочлен v (х), соответствующий полученному сообщению, со-^еРжит одну
ошибку, т. е. что v (х) = w (х) + хе~{, в то время
fS. л
bub
Гл, 9, Приложения конечных полей
А >**ЧЫН KptW-WsJ-'iYi I { fill** ff iJAl •
H ,IWi
Ш
ft*-..
:, $¦? ¦яШ
как передавалось сообщение, соответствующее многочлену w (xjj
Тогда синдром равняется w (а) + ае ! = оТОТО Отсюда иолу
тель заключает, что в примятом сообщении на место с номером ; имеется
ошибка. н
9.42. Т ео рема. /7 усть С то [ру 1x1 / (хп - ]) ци к
л и чсскщ
код с порождающим многочленом g (х), и пусть а,, . корни многочлена g
(х). В этом случае многочлен f ? ipT 1т !/(х"
- !) является кодовым многочленом тогда и только тогда, когдё
вектор (/0, /а, 4-i)* образованный коз
лежит в нуль-пространстве матрицы
иен там и м ногочлена
. a
1
а
2
Щ
м > i
п-1
>•ijl
я
(9.
1
2
(Xn~k
Доказательство. Пусть / (х)
/ ("г) - /о + Да* то - -а это значит, что
fl - 1 Ctfi-k
Jty3S
+ ь
/,
о
[\х ь * ' О для всех
flr i *
•:ф
ТОГД!
т
<Г
п
1*
•<%й
(с
а
Д 1) i/o * fu ¦
i)T = 0. 1
,Т
? < П 0.
А,
? * - , - ? j?
тогда и только тогда, когда Н (/", Д, /фф)
. Напомним (см, § I), что для исправления ошибки в получе^! ном слове у
необходимо определить синдром этого слова. В слр чае циклического кода
синдром, который является векторе*; длины п - А, часто бывает возможно
заменить другим более up стым объектом. Например, пусть а - примитивный
корень т степени из 1 в поле fqfn, и пусть g (х) - порождающий миог
член кода - является минимальным многочленом элемента иад полем Fr/. В
силу того что уделит многочлен [ ?Fq [х1/(хп - 1) тогда и только тогда,
когда / (а) - 0, матрицу 7/ из (9 можно заменить матрицей /7 вида ш
И - (1 а а2 ... ап~ф),
Тогда в роли синдрома выступает вектор 5 (у) Иут, прич S (у) ^ у (а), так
как у ^ (у0, уи упД можно рассматривав как многочлен у (х) с
коэффициентами yh Далее, будем обоз" чать через w передаваемое слово,
через v - принимаемое слов а через w (х) и v (х) - соответствующие
многочлены. Пред пол жим, что ей> (х) -- xE~s, ] j Д п, - многочлен
ошибок, сЩ ответствующий единственной ошибке, и пусть v ~ w Ф Тогда
v (а) = w (а) ф ед) (а) .• еб) (а) ^ а/-3.
Величина е(1) (а) называется локатором ошибки. В этом случ$ синдром S (v)
-¦= Ф~1 однозначно определяет ошибку, так е<0 (а) Ф (а) при 1 < i, j < п
и i Фф ф
то
ж
§ 2. Циклические коды
807
IKM"M Wi*h4%lfcfcWTItfUM*Г ЛГИ ¦ Ml УМ* t >1 ТВ Г
¦ чем переходить к циклическим кодам общего вида, рассмотрим следующий
пример.
г
Пример, Пусть элемент а f f16 корень многочлена iff., ix), Тогда
минимальными многочленами эле-
