Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
тогда весовую функцию кода С1 можно представить в виде
А'(х,у)= ? f(v).
v-Cci
600
Гл. 9. Приложений конечных полей
' '*5
€
Пусть gf - отображение, заданное выше (ем. определение 9.ЗОЙ Дли v f Fa
положим
см
1, если v Ф О,
\ 0, если v = 0.
Тогда для u ~ (щ, tin) ? fj получаем
2 X (v • ц) ха:( vv)
f F
fl
?
s
* H € ¦>
Та
X (uivi 4
< * *
¦f ПДУ7()
inn-'
* -И т; I / 1
n hp
IH I) i K1-
2]
Ь-i v
!]
lr
V
С !
ntM
n
)
'Xib
%
V
'!•
- П У] xlv ]yj
i~ t v о [P q
В случае когда ик - 0, справедливо равенство % (иуо) - % (0)
:: П а следовательно, соответствующий сомножитель в последней)
произведении равен (р ~~ 1) х тг у. Прн щ ф 0 соответствукяци; сом н ож
ите л ь р а в н я етс и
У \ X 2 X Ь) = У - *•
"fF
5< "V
/:v?
-.1
sV
• I?
С Л1 (х, у)
Таким образом,
gf (U) = (у - *)"•¦' "> *)¦"- w
Из леммы 9.31 следует, что
с| 2 /Т)= 2 Ы") = а(у х,у + (я-')*)
v 6 С1 11 € ^
И наконец, |С| - qk по условию теоремы. Тем самым георема§ доказана.
9,33. Следствие. В весовых функциях А (х, у) и А1 (х,
положим х -•= г, у = 1. Полученные при этом многочлены обозна\ ним через
A {г) и Л1 (г) соответственно. Тогда тождество Маф Вильямс можно записать
в виде
\ - 2
Л1 (г) ~ р '" (1 -\ (р - 1) г)'1 А
И- <* -1)г
9,34. Пример, Пусть Сш - бинарный код Хэмминга длины* п. = 2т - 1 и
размерности п - т над р8. Порождающей матрйу!
цен его дуального кода Ст является проверочная матрица Щ
§ 2. Циклические коды 601
I '¦¦М №*"МММШ1ШМДМ1ШИ"Щ1ЮТ1ИМ-1йШЯ||||М.ЯЦЦЦ^№"чи ^ iW ?Л 11 № IM ИЧ.
MiO
лрА^Ф>* * '
к01л Cm. Эта матрица состоит из всех возможных ненулевых
столбцов длины т над нолем Fa- Код С~т состоит из нулевого вектора и 2т -
1 векторов веса 2т~К Таким образом, весовая функ-
д,
ц]Iя кода Ст равняется
у" И2Ш Вл^-у-1-1.
По теореме 9,32 весовая функция кода Ст определяется формулой А {X* у) ^
[(f/ -j- х)п ti \ у - ...j.. дг) ^^ ¦*'¦ j *
п
Пусть А (г) ~ A (zt 1), т. е. А (г) - ? Л цб Тогда нетрудно
ТОО
проверить, что А (г) удовлетворяет дифференциальному уравнению
(1 г2) -Л)- j (I _ пг) А (г) = (1 + г)"
с и а ч а д ь н ы м у с л ов нем А (0) ~ А 0 - 1, Эт о э к в н в а л е и
т н о с о от -
ношен ию
А|Г-(tm)" (ti - i 2) Л • _<>,, i - 2. 3, . .. . j tp
I - - l >
о начальными условиями A0 1, Л, 0, П
§ 2. Циклические коды
Циклические коды -это особая разновидность линенных кодов, они отличаются
достаточно хорошо изученной математической структурой н удивительно
просты в реализации,
9.35, Определение. Линейный (л, Ар-код С над полем Fq называется
циклическим, если из того, что вектор (а0, ах. а"_1) принадлежит С,
следует, что его циклический сдвиг ("п-и ао" ¦¦¦ ап_"2) принадлежит С.
С настоящего момента мы будем предполагать, что НОД (л, Я) ~ 1. Обозначим
через {.О - 1) идеал кольца Fq [xl, порожденный многочленом хп 1 ? fд
[х]. Тогда все элементы факторкольца fq \x\j(xn - 1) можно представлять
многочленами степени, меиьшей чем п. Очевидно, что это фактор кольцо
изоморфно
как векторное пространство над полем Fq, а изоморфизм
¦шеет вид
(а0, аг. . , ., йпД ¦*-+ aQ -j- ахх ф - • * -у йп_ххп~ Е
3 силу существования указанного изоморфизма мы будем представлять
элементы §ф |х1/(хп - 1) или в виде многочленов ете-
Пгм,ы меньшей чем я, которые рассматриваются по модулю ; или в виде
векторов или слов над полем Fq. Умножение
602
Гл. 9, Приложения конечных полей
!н.*д|И Hrt i i . rJiiHHji. i
•> !
\ *4
№
• i-iAy
I мы определяем обычным образом
ч
Ы, то gjg,, f означаеЙ
Ж
многочленов по модулю хп -
ем и /е F, Ь \Цхя 1), ft, & е F,,
что ftgs s f (mod (х'1 - 1)).
Циклический (и, Л)-код С можно получить путем умноженцЦ каждого
сообщения, содержащего к информационных символа (н которое мы
отождествляем е многочленом степени, меньше! чем к), иа фиксированный
многочлен g (х) степени п - к, г g (х) является делителем хп- L
.Многочлены g (х), xg (х), .$
матрица кода С имеет вид
gn-k.
I 0 еп гч
G =
gf) gi * Т- 1
0 gf) gt
1 0 0 0
gn + giX j-л s^_
0
словам
0 0
gn-k 0
go gi
г р *
0
о
" * 9
§п~к
•I
'¦§?
I .1,
.U
П-к
У Очевидно, что строки шщ трнцы G линейно независимы, и, таким образом,
ранг матрицы равен к ¦ размерности кода С. Если
Л (х) ^ (хп -- \)/g(х) - }ц | Ну (х)
Н~ 1цхк,
то матрица
И
0
о
V * гг
к
&-г
h b *
0 hh
0 hh hh-1
л r T 1 *. 0
h
V *
*• ч>
ft
0
.55
Ой
является проверочной матрицей кода С. Код с порождающё§ матрицей Я, т. е.
код, дуальный к коду С, также является цикл ческим кодом.
Так как мы отождествляем векторы (а1Ъ а1У .an-i) над п| лем и многочлены
аь 4- алх 4- ... I йл_гхп-] иад тем же лем, то код С можно рассматривать
как подмножество факта кольца Fq [х}({хп 1).
9.36. Теорема. Линейный код С является циклическим тог и только тогда,
когда он будет идеалом кольца F,7 \х]1{хп ¦- I
Доказательство. Если С является идеалом н (aQ, аг, ав-Л б С, то и
i
х*(й0 1" ОДА* 4 - ' * ' "ir йп-л4'ь'~'1) 7:-":v ^0i an- 2) €
J
Обратно, если нз того, что (й0, tft, an_i) ? С, следует, что (йд"х, я;,,
