Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 134
Текст из файла (страница 134)
Тогда для любого многочле, Ь (х) произведение Ь (х) а (х) принадлежит С. Последнее озн чает, что С я вл я ется идеалом. й 2. Циклические коды бво Каждый идеал кольца сч !х!?(хн — 1) является главным, а чзсгности, любой ненулевой идеал С порождается нормированным миогочленом степени, меньшей чем и, и если обозначить этот ;,, огочлен через д(х), то д (х) делит х" — !.
с).Н?. Определение. Пусть С . (д (х)) — циклический код, '),я да мпогочлен а (х) называется аорождаюи(им мноаочлснол к. зо С, а миогочлен й (х) (хн — 1),'лс(х) называется нриагроч нам многочлгном кода С. 11) сю л'" — 1 . )с, (х) )о (х) „. 1 (х) — — разложение миогоь.шш х" — 1 па нормированные неприводпмыс многочлеиы над и л~гч Г,. В силу предположения о том, что ИОД (и, д) — 1. ил~у шем, что крзтныс сомножители в этом разложении отсутсшуют 1:слн мпогочлен (; (х) нсприводим нзд полем 7ч, то идеал (1, ';)) является л~аксимальнсям идеалом, а циклический код ро.кденный многочлеполи ?с (х), называется максимальным цикнсчсткилс кодом. Код, порожденный многочлепом (х" — 1)?)'с (х), ~ а ывзгтся асс|рита)имам Никличгским кодом.
Можно найти все шхличсские коды длины и над гч, разлагая многочлен х" — 1 множители указанным выше образом и выбирая в качестве » р окдакяцего многочлеиа любой из 2'" — 2 нетривиальных нопчировзшсых делителей многочлена х" — !. 1:слп сс (х) — проверочньсй миогочлен циклического кода С ~:— '.:,',,)х1;(хн — — 1), а ц(л) Е Гч !х!?(хн -- 11, то и (х) р С тогда ~ (шко тогда, когдз и (х) й (.г) = 0 (пюс( (хн — 1)).
Миогочлен н (г) ач а,х ! ..; ак,хл — ', соответствУюЩий псРеДавземой информации, кодируется кодом С в многочлен еа (х) =- а (х). д (х1, где р (х) — порождакяций миогочлен этого кода. Если ш: гсжлеп и (х), соответствующий принимаемой ннформаспги, ра Ше,шть на д (х), то получение ненулевого остатка означает нализпс' ошибки в принятом сообщении. Каноническую порождзкч' 'укл матрицу кода С можно получи~ь следующим образом. Пусть ')сц (й (х)) н -.. сг. Тогда супсествуьот единственным образом ирг,к,~яехсые мпогочлены а; (х) и с, (х), такие, что дед (сс (х)) < и -- Ф хс — а, (х) д (х) , 'с, (х) .
С ш"овательпо, лц -- сз (х) Явлаетса кодовым многочленом; кодонвлг ется и многочлен аз (х) - хл (хс — с, (х)), взятый по "нлулю х" — ! . Миогочлсны аз (х), 1 и — — Ф, ..., л — 1, лиигино независимы и образуют каноническую порождающую ма'1ш' у (?л ((), где ?л — - единичная матрица размера Ф:, А, матрица размера сг х (п — сг), сзя строка которой образоаа'ш коэах$исциентами миогочлена с„..
~ ~ ы (х). и Зк. Пример. Пусть и - ?, с) — 2. Тогда л ' †. 1 (л 1 !) (х" ! х !) (х' -с хч ' 1), Гл, 9. Приложении конечных полей 604 Многочлеп 9 (х) — х' + хе и ! порождает циклический (7,4)-кое с проверочным многочленом 6 (х) — х' ! хл 1 хл ' 1. Соответ,' ствующая каноническая порождающая матрица 6 и проверочна матрица И имеют внд 1 0 0 0 1 О 1 1 1 1 О 1 0 0' 0 1 0 0 1 1 1 — 0 0 1 0 1 1 О, 0 0 1 ! 1 О ! О 1 1 0 1 О 0 1/ Напомним полученный в гл. 8 результат о том, что если )' с Ко !х ! — многочлеи вида )'(х) =7в !-6ех р . -,'-),х", ~.~0, 7„= 1, то решениями линейного рекуррентного соотношения 1 ~~ )зае„— — О, ! -- О, 1, ~ .о являются чисто периодические последовательности с периодом' равным и.
Множество п-наборов, состоящих и~ первых и члено каждого такого решения и рассматриваемых как миогочлены п модулю х' — 1, образует идеал, порожденный в кольце Ге !х !/(хв — 1) многочленом а (х). Здесь д (х) — многочлен степени и— возвратный к многочлену (хе — 1),')' (х) '). Таким образом, леож использооить для получения кодовлех слов в циклических код линейные рекуррентные аютношения, причем этот процесс мож легко реализовать технически с помощью регистров сдвига. 9,39. Пример, Пусть ) (х) хл ~ х 1 1 — делитель мног' члена х' — 1 над полем $"е.
Соответствующее линейное рекуррен ное ссютношеиие имеет вид а;,в + аьм -'- а, =- О. Оно порожд циклический (7,3)-код, который, например, кодирует слово 111 в слово 1! 10010. Порождающим многочлепом в этом случае я ляется многочлен, возвратный к многочлену (х' -- 1)П (х), т. д (х) -- х' -' х' ! хе †; !. ! Циклические коды можно также описать путем задания кори всех кодовых многочленов„перейдя в соответствующее расш рение ноля Ке, Условие, что все кодовые многочлены делятся н порождающий многочлен д (х) циклического кода, означает прост ' что все кодовые многочлены должны принимать значение 0 н корнях мпогочлена а (х). Пусть и„..., сее — элементы фикснр ванного РасшиРениЯ полЯ Ке а Гй (х), ~' 1, ..., гь — мннпмал ' ный многочлеп элемента х; над полем Ге.
Пусть и ~ И таково, ч а"; -- 1 для всех ! -- 1, ..., з. Положим а (х) НОК (р, (х), . ') Ом. гл. 8, й 3. — Прим. перев. 4 2. Циклические коды , р, (х)). Тогда многочлен а (х) делит х" — 1. Если С ~ Ц— циклический код с порождающим многочленом д (х), то о (х) Р С гг!гда и только тогда, когда о (а,) =- О, ! = 1, ..., э. В качестве примера того, как связаны описания циклического кода с помощью порождающего мпогочлена и с помощью кодовых многочленов, докажем следующий результат. При этом используется понятие эквивалентности кодов, определяемое в упр. 9,1О, 9.40.
Теорема. Бинарный циклический код длины и = 2~ — 1, н рггждаюощий многоылен которого является минимальным много- елсном над полем !го для некоторого примитивного элемента т лл Г,„„эквивалентен бинарному (п, и — т)-коду Хэмминга.
Доказательство. Обозначим через а примитивный элемент полн ~Г, и пусть р (х) — (х — а) (х — ае)... (х — и'" ') — - минимальный многочлен элемента и над полем Го. Рассмотрим теперь циклический код С, порождеяный миогочленом р (х). Построим матрицу Н размера тх(2 — 1), 1-й столбец которой имеет вид (с,, с„..., с,)', где с! Р 7о и гл — 1 и! — '= й' соа', /=1, 2, ..., 2"' — 1. =о Ес.ш а -- (а„а,, ..., а„,) и а (х) = а, + а,х + + а„,х" — ' Е Е Го (х), то вектор Нат соответствует элементу а (а), выражен- ному в базисе (1, и,,, а — ').
Следовательно, равенство На' =- О выполняется только тогда, когда минимальный многочлен р (х) делит а (х). Таким образом, матрица Н является проверочной матрицей кода С. В силу того что столбцы матрицы Н представ- ляют собой перестановку двоичной записи чисел 1, 2, ..., 2~ — 1, все они различны. Теорема доказана, (1 О 41. Пример. Многочлен х" + х + 1 является примитивным многочленом над полем го, и, следовательно, его корнем будет примитивный элемент и Е Г'го. Если длЯ всех 15 элементов и! ~ Г(о, 1 = О, 1, ..., 14, воспользоваться векторной записью, выражая их в базисе !1, а, и', ао), и из полученных векторов, '!спользуя их как столбцы, образовать матрицу размера 4 х 15, то мы получим проверочную матрицу кода, эквивалентного (15, 11. ° )-коду Хэмминга, При этом сообщение вида (ао а! ", аго) кодируется в кодовый мцогочлен го(х) =а(х)(х'+х+ 1), где а (х) =- а, + а,х + + а!ох!о.
ПРедположим тепеРь, что многочлен о (х), соответствующий полученному сообщению, со- "ержит одну ошибку, т. е. что о (х) = ги (х) + х' — ', в то время Гл. З. Врилогкенвя конечных колея как передавалось сообщение, соответствующее многочлепу иг (х) Тогда синдром равняется иг (а) . а' — ' и' '. !)тсгггдгг получ ' тель заключает, что в принятом ссюбщепин на мес; г номером имеется ошибка. 9.42. Теорема. Пусть С а=. К'о (х 1,'(х" — )г нпк.гичсски' код с порождагои)илг многочленом у(х), и пуспгь а, корни .иногочлена у (х).
В этом случае многочлсн / Е ),г 1х)г!хк — — 1) является кодовым многочленом тогда и тольюг гп;да, когд' вектор (/о, )г, ..., ), г), образованньгй коэффициентами гггг~ ' г г.гена й лежигн в нуль-пространстве матрицы 2 о--г Н=— 1 аг аг ... аг (9. 1 а, л а„ь ... акг, Дггказательсгпво. Пусть ) (х) -- )гг -'. )гх и' -" )о гх" '; тогд ) (аг) = го + )гаг -Ь Ь )„ га' ' ††: О для всех 1 -. г:.-,: и — Фг а это значит, что (1, а„..., а )()о)г ., )к г) ==О, 1.,!сп — й, тогда и только тогда, когда Н ()о, )„..., ), г)' '- О.
Напомним (см. $ 1), что для исправления ошибки в получе, ном слове у необходимо определить синдром этого слова, В сл ' чае циклического кода синдром, который является вектор длины и — я, часто бывает возможно заменить другим более пр ' етым объектом. Например, пусть а — примитивный корень и степени из 1 в ноле ге, и пусть д (х) — порождающий мно член кода — является минимальным многочленом элемента над полем Кч.
В силу того что уделит многочлен 1' с Гч (х1/(х" .' — 1) тогда и только тогда, когда )' (а) =- О, матрицу Н из (9. можно заменить матрицей Н вида Н.== (!аа'...а" — '), Тогда в роли синдрома выступает вектор 8 (у) = Нут, прич 3 (у) — у (а), так как у =- (уо, у„..., у„,) можно рассматрива как многочлен у (х) с коэффициентами у,. Далее, будем обозн вать через гч передаваемое слово, через ч — принимаемое слов а через го (х) и и (х) — соответствующие многочлены. Предггол, жим, что енг (х) = х) — ', 1 ( ! ( и, — многочлен ошибок, с ' ответствующий единственной ошибке, и пусть и =- нг + еы Тогда о (а) = иг (а) + еыг (а) === еыг (а) = аг — '.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
