Научная литература
booksshare.net -> Добавить материал -> Физика -> Лидл Р. -> "Конечные поля. Том 1" -> 251

Конечные поля. Том 1 - Лидл Р.

Лидл Р., Нидеррайтер Г. Конечные поля. Том 1 — М.: Мир, 1988. — 430 c.
ISBN 5-03-000065-8
Скачать (прямая ссылка): konechniepolya1988.djvu
Предыдущая << 1 .. 245 246 247 248 249 250 < 251 > 252 253 254 255 256 257 .. 371 >> Следующая

ап_2) ? С, то для любого многочлена о (х) ?
f
многочлен х*а (х) также принадлежит С, а. следовательно, х2о (х) ? С, х^а
(х) б О и т.д. Тогда для любого многочле Ь (х) п р он з в еде мне Ь (х) •
а (х) п р и н а дл ежит С, Поел ед и ее озн чает, что С является идеалом.
•15-е:
§ 2, Циклические коды
Х ...... лр!|;:г-~ .IA..MA.X-"Ч" П " 'I ' ' '
г 11' 1 VC iii 3i г~|'||'| |'0' iWiH fiMH ¦iiihiiii ~'1I~I'i'' '
i 4 h|hihhi цчц^1 1ГГИППГП
Л I ^¦ 1 1
аждый идеал кольца Fq \x\j(xn - 1) является главным; частности, любой
ненулевой идеал С порождается нормированным многочленом степени, меньшей
чем п, и если обозначить этот многочлен через g (х), то g (х) делнт х* -
1.
9.37. Определение. Пусть С -- (g (х)) - циклический код. То да многочлен
g (х) называется порождающим, многочленом кода С, а многочлен h (х)
(хп - 1 )ig (х) называется проверочным лтогочленом кода С.
Пусть хп - 1 /1 (х) /3 (х) ... /т (х) - разложение много-
члена хп - I из нормированные неприводимые многочлены над полем Тп. В
силу предположения о том, что НОД (я, q) - 1, подучаем, что кратные
сомножители, в этом разложении отсутствуют, Еслн многочлен /у (х)
неприводим над полем Fif то идеал {Т (л)) является максимальным идеалом,
а циклический код. порожденный многочленом /у (х), называется
максимальным циническим. кодом.. Код, порожденный многочленом (хп - 1 )/П
(х), сзывается неприводимым циклическим кодом.. Можно найти все
циклические коды длины п над Fq, разлагая многочлен Xя - 1 г-н множители
указанным выше образом и выбирая в качестве порождающего многочлена любой
из Тп ¦- 2 нетривиальных нормированных делителей многочлена хп - I.
Если h (х) проверочный многочлен циклического кода С то то Е,:; [x!/(xfl
-- 1), ад (х) ? F4 [xl/(xn - 1), то v (x) ? С тогда и только тогда, когда
v (х) h (х) х 0 (mod (хп - Г)). Многочлен ч (х) - ап I asл ¦+- ... -|
ak.^xk^-lt соответствующий передавае-
м о й 51 и фо рмацим, к од п р у етс я к од ом С в многочлен w (х) ~ а
(х) -
¦g (х), где g (х) - порождающий многочлен этого кода, Если
многочлен v (х), соответствующий принимаемой информации, р а аде;) и т ь
на g (х), то пол у че и и е иен у левого остатка о з н а ч а е т надитне
ошибки в принятом сообщении, Каноническую порождающую матрицу кода С
можно получить следующим образом. Пусть 4 ТО (g (т)} п.. - k. Тогда
существуют единственным образом
) оделяемые многочлены а, (х) и щ (х), такие, что deg (/у (ТО) <
и
xi - aj(x)g(x) f rj(x).
-ДЩдовательно, TO - /у (х) является кодовым многочленом; кодовым является
и многочлен gj (,v) xk (xi - щ (x)), взятый по
то>дулю хп - Е Многочлены gs (х), / • п -- ТО п 1, ли-
тойко независимы и образуют каноническую порождающую ма-Щ1 нцу (4 /?),
где Ih - единичная матрица размера к X А,
d к матрица размера к X (п - А), i-я строка которой образо-
тогл коэффициентами многочлена гп к 5(х).
Пример. Пусть /г- 7t q --- 2. Тогда X7 I - (х 4- I) {Xs У ж 4- 1) (X3 у
Xя +¦ I).
ОЩ
X?
604
Г л. 9, Приложения конечных полей
*" ii I I iimtti'i'iwnt'^tir~i~i~i~i'~i'i~i'i 'патго lYTTirrrmwvitrrrwm m
*i i u i ~rr~
MWVTV*AHbV Ч Г--1~ ~I~I I 'if Jb fcV 11
Многочлен g (x) Xs + x2 1 порождает циклический (7,4)-кеш
с проверочным многочленом h (х) ¦= х4 -\- х3
X
,2
1. Соответ!
ствующая каноническая порождающая матрица 0 и и ровер очна!
€ =
а я имеют вид 4
1 0 0 0 1 0 К
0 1 0 0 1 1 1
0 0 1 0 1 1 0
0 0 0 1 0 1 1,
Я
1
1
0
0
1
\
1 о о-
О 1 о
О О 1 /
Напомним полученный в гл. 8 результат о том, что если f t
б ?ч Н З -• многочлен вида
f {X) = fo + flX +
fkXk, /o#0, fk ^ 1,
"\4k
то решениями линейного рекуррентного соотношения
к
И fjauj = о, / • о, 1,
A J •*
/=л)
являются чисто периодические последовательности с периодом| равным я.
Множество н-наборов, состоящих из первых п члепо! каждого такого решения
и рассматриваемых как многочлены ш модулю хп- 1, образует идеал,
порожденный в кольце {р^ U'.3/(Ml - 1) многочленом g(x). Здесь g (х) -
многочлен степени п - возвратный к многочлену (хп - 1)//' (х) 1). Таким
образом, можщ использовать для получения кодовых слов в циклических кодЩ
линейные рекуррентные соотношения, причем этот процесс можш легко
реализовать технически с помощью регистров сдвига.
9,39, Пример, Пусть / (х)
л:
X
:C;ti
делитель миогщ
члена х7 - 1 над нолем FV Соответствующее линейное рекурретш
ное соотношение имеет вид ai+3 -f ai+1 + at -= 0. Оно порождав
циклический (7,3}-код, который, например, кодирует слово 11| в слово
1110010. Порождающим многочленом в этом случае яЦ ляетея многочлен,
возвратный к многочлену (,г 1}// (х), т. ||
g (х) хЛ ~f х3 -f Xs + 1. га
v <
Циклические коды можно также описать путем задания корне! всех кодовых
многочленов, перейдя в соответствующее раеШ11| ренне поля ?ч. Условие,
что все кодовые многочлены делятся Н§ порождающий многочлен g (х)
циклического кода, означает npocTfijjj что все кодовые многочлены должны
принимать значение 0 щ корнях многочлена g (т). Пусть "1( as - элементы
Предыдущая << 1 .. 245 246 247 248 249 250 < 251 > 252 253 254 255 256 257 .. 371 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed