Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 136
Текст из файла (страница 136)
Боэн имеется г;-. ) ошибок, то в(х) =- ~~ о,х", г — -ч Гл. 9. Приложения конечных полей где а,, ..., а, — различные элементы из (О, 1, ..., л — 1). Эл менты пг:-- а'! ~ Г,, называются локаторал!и ошибки, а эл менты с; ~ 'г' — значениями ошибки. Таким образом, для си драма вектора о получаем формулу г 5; .= е (с!!) =- ~ сгт!!, Ь е.;1 <.' Ь вЂ” ' !( — 2. Учитывая правила вычисления н поле Г,, приходим к раве ствам 5е! = ( ~ с,х)',~ = ~ сот)гге .
= ~ с!!)!е === 5; . (9. х!=-! !=! ! — -! Нам надо найти неизвестные пары (!1„с,), ! -- 1, ..., г. Коор наты 5; синдрома 5 (т) можно считать известными, так как и можно определить по полученному вектору т. В бинарном сл чае каждая ошибка полностью характеризуется величиной т! так как в этом случае все с! могут принимать лишь значени равное !.
Следующим шагом декодирующего алгоритма является опр деление коэффициентов о!, задаваемых полнномиальным тожд ством г П(тп — х) =-- ~ ( — 1)гаг !х! == ог - о„,х г .,' ( — 1)'о„л . г=-! ~.=-о Таким образом, о„- 1, а и„..., о, — элементарные симмет ческие многочлены от т1„..., т1,. Подставляя Ч! вместо х, пол чаем ( — 1)' ог + ( — ! )' ' о, !вл + + ( — 1) о!х!' ' + ч)! == О, ! =--1, Умножая на с!х!!; и суммируя эти равенства по всем !' = 1, ..., получаем ( .1) о,5,. ) (--1) — ' ог,5т,! -!- ° ° ° + ( — 1)О15, — + 5у+ = 0 где ! =- Ь, Ь '- 1, ..., Ь + г — !.
9.48. Лемма. Система дравнени!1 Ксх),=5ь 1=Ь, Ь+1 ..., Ьн-г — 1, г==! относительно неизвестных с! разрешима, если Пг являются р личными элементами из Г ! 2. Циклические колы 6!3 ь Чг ЬЬ! !я! 1аг ь,! г — ! Чг' Ч,49. Лемма. Сиео1еиа урони«ниц ( - !'!'ог5,.' ( — 1!' 'о, !5;,1 р . 2 ( — 1)о251ч„,-)- 5,, =- О, )==Ь, Ь-! 1, ..., Ь-, «--1, о«он! 1титльно неизвестных ( — !)'о,, !' — 1, 2, ..., «, однозначно ооормиима тогда и !полька тогда, когда а полученная слове ил1ггтгг! « ои1ибон. У(онозатсльсгпво. Матрицу, соответствуюгцую этой системе урв11н пий, можно представить в виде '5ь 5ь 2 . 5ь;..! ' 5, 5, ... 5 1' 1 1'2 ' ' ' Ь'г И)«т — 5Ьег . 5Ьгкг-2 г г!' 1 1 ...
! 2!1 Ч2 Чг г — 1 г — 1 г — ! Ч! Ч1 . Ч. ел", 0 ... 0 0 с!Чье ... 0 0 О . с,т)ь 1~!аг!п1ца данной системы невырожденна тогда и только тогда, 1"ида матрицы 1«н 0 являются невырожденнымп. Матрица '!в'яется матрицей Вандермонда; оиа невырожденна то~да и т'!'н ко тогда, когда все Ч;, 1' =-- 1, ..., «, различны. Матрица !л иев!'Рождеппа тогда и только тогда, когда все Ч1 П с, ОтлНЧНы От О. ~~!н! ьтловия выполняются в том и только том случае, когда в по- 11У'инион некто!н.' имеется «ошибок. !) Внедем так называемый многочлгн локапюров о1иибки: г ь (х) =.. П (1 - — Ч1х) .=- ~л (--1)1о,х'. О 1 1.
О Д!гкааа~йиеЬС1наи. !!ястс!! ь Ч2 ! '1. 1г!; Че Определитель этой системы уравнений рав- .=- Ч202 . Ч, П (21, — Ч,) ~0, !", !'л, Нп Прнложепяп нпнепнмх полей где о; определены выше. Корни многочле>ш ь (х) равны ц!, ..., ц, Для того чгобы наяти зти корни, можно воспользоваться ир»ига рои '!е>ш. Для этого иам надо, во-нервых, узнать, является число ал ' локатором >янибки, т с. яв.>яется ли элемент а .—:. а->л-" ко!тем м>и>гочлена з (т).
Чтобы нр»верит! зто, ра смотрим сумму — о,а -! о>а> ( 1)'о,а". Если она равна - — 1, зо ал ' является .ижатором ошибки, та как в этом случае з (а) — О. В общем случае точно таким же разом проверяем элементы гхл -"' для т 1, 2,, и. В бннарн случае обнаружение местонахождения онн>бки равносильно иснравлениив Приведем теперь нолиостьн> алгоритм дскодир" ванин БЧХ-кодов. обозначая нри этом (- — !)'о; через г!. 9.90. Декодирование БЧХ-кодов.
!)реш!оложим, что в нер данном кодовом слове ч', закодированном с помощьк> ВЧХ-ко с конструктивным расстгшнием >1: 2! ° 1, нонна:н>сь ис б>и>ее; ошибок. Шаг Е Находим синдром полученного слова 5(т) =-- (5>„5ь„„...ь 5ь„л,)т. Пусть и 5; .. ~„'с,ц',, Ь:",:1: Ь, г! 2. ! Шаг 2. Находим максимальное число г.:.; 1, такое, что си,, стема уравнецнй 5>,„-,' 5,,„,т, ! -!-5,т„==-О, Ь.:::.!' ..'Ь -! г — 1, относительно пеизвсстных т; имеет невырожденну>о матриц, коэффициентов.
Тем самым получаем число появившихся ош бок. Построим миогочлен локаторов оишб>ки и 1 з(х) — П (1 — т),х) =- ~ т>х:. ! >=-о Коэффициенты т, выражаем через 5,. Шаг 3. Решаем уравнение з (х) =- О, подставляя в з ( \ вместо х степени элемента а. Тем самым находим локатор, ошибки т); (процедура Чена). Шаг 4 Г!одставляем ц; в первые г уравнении, образована на шаге 1, и определяем значения ошибки сь Г1осги чего из ура пения к> (х) о (х) — е (х) находим переданное слово и. 9.51. Замечание.
Заметим, что самым трудным >вагом это алгоритма являетгя шаг 2. Имеготся различные методы для е реа.пиза>ы>и. Одним нз иих яв;!ястся использование алгоритм й 2. Цикла >ескнс коды ° „кзсьэк>па--й(ессн из гл. 8 для определения нензвестнык коэф,пп>»сп>ов т; в линейном рекуррептном соотношении для 5>., ! >к52, Пример. Рассмг>грим БЧХ-код с конструктивным рас,, пнем с! -- 5, который может исправлять любую одиночную пля дв»йну>о ошибку. В этом случае положим (> -= 1, л =- 15, 2.
Если через тн> (х) обозначить минимальный многочлеп пад п>лем Г, элемента а', где примитивный элемен~ >х Е т>„ яв.»ются корнем многочлепа х' -!- х ! 1, то тон (х) == >п>н> (х) = тм> (х) =- п><к> (х) ==.. 1 -г х ..', х>, >поп (х) —.
ш>к> (х) =. т< "> (х) — - т>н> (х) == 1 + х -' хк >- хз + х>, Та>спм образом, порождающий многочлен рассматриваемого БЧХ- ко.ш имеет вид сс(х) =. щ<н(х) шы> (,) :-:>и:г код является линейным (15,7)-кодом с проверочным многоч,>сном 6 (х) — (х" — 1)>й> (х) --= 1 + х' О качестве базиса этого (15,7)-БЧХ-кода ответствующие многочленам у (х), х» (х), х'и (х), х>и (х), х>д (х), '!'аким образом, получаем порождающую 1 0 О О 1 О 1 1 1 О ->- х' + х' возьмем векторы, со- х%а (х), хк а (х) !!!юдпос>ожпм теперь, что полученное слово к имеет внд 100100110000100; 'ада соответствующий многочлен о (х) имеет вид о (х) :=- 1 я- хк > х" + х> + х>к. " с»»тветствии с шагом 1 декодирующего алгоритма найдем его ся>г ром, воспользовавшись при этом для упрощения вычисле- нии соотношениями (9.6): Я> =-' е (а) ---: о (сс) =-.
1, Я, — е (>х') ==-. о (>х') --. 1, 0 1 О О 0 1 0 0 1 О 0 0 0 0 0 1 0 0 0 О О О 1 0 0 0 0 0 0 1 О О О О О 0 О 1 1 1 1 0 1 1 0 1 0 1 0 0 1 0 0 0 0 ! 1 0 О 0 матрицу О 0 О 0 О 0 0 0 0 0 1 0 0 0 0 1 1 0 О О 1 1 1 0 0 О 1 1 1 0 О 1 1 1 6!6 Гл 9. 1!рне!оженил конечных полей 5к е (а') и (и') .—. а', 5 — е (а') . с (а4) —. 1, й!аксик!!!лш!ая невырождепная система линейных уравнений о' носительно неизвестных т, (шаг 21 имеет в этом случае вид 5т, -1 5те 5л, 5кт, ! 5ете 5,, или т, ! те и', а'т, 1- те -- !. Очевидно, что матрица этой системы иевырожденна.
Следов тельно, число встретившихся ошибок должно равняться 2, т. 2. Решая эту систему уравнений, получаем тч — 1, т, =- Иодставляя эп! значения в а (х) и считая, что тн =-. 1, получас что а (х) 1, х ' их'-'. — ! к — 1 !як как корни этого многочлена лежат в !! !е, то ч!! - сс, ч!а — а" и, следовательно, пн с!', не а'. Отсюда мы делаем в вод, что ошибки появились в 8-й и !О-й компонентах передапно слова. Исправив этп ошибки в полученном многочлене, получа ш (х) -- о (х) — е (х) — (! ! х' -' х' -; х' -, ,'х") — (х! , 'х') = — хк -.
хе ! хе ' хге. Соответствук)щее кодовое" слово— 100100100100100. Исходную ниформапию (до кодирования) можно получить с п' мощшо деления исправленного мпогочлена (т. е, переданно кодового многочлеин и (х)) иа многочлеп д (х). В результате пол чаем ьа (х),'д (.!) 1 лк , 'х', что соответствует передаваемому сообщению 100 1 100. Ч 3. Конечные геометрии Этот пара!раф посвящен применению теории конечных и лей в геометрии, В извеетнок! смысле тсоршо кодирование мож также рассматривать и как раздел геометрии, и как раздел к бипаторикп, так как в к изучаются вопросы упаковки шар в метрическом пространстве конечной мощности, как правиЛ в конечномерном векторном пространстве над полем 'ге.
Проективиая плоскость состоит из множества точек и множест, й 3. Конечные геометрии »рямых, которые связаны между собой отношением ипцидентно,,» Вго отношение позволяет для каждой точки и каждой пря„о>) устаиовигь, лежит данная точки на данной прямой нлн нет. ! >я г»гч> чгобы дать строгое определение, необходимо сформулн!»»н>гь несколько аксиом. 0.53. Определение.
77рг>екпгивная плоскость определяется как и» >жество элементов, называемых >почками, вместе с выделенными »«дмножсствамп этого множества, называемыми >грнлгыии, и т»» ьепием I, называемым птногиснисм и>гнггдсн>п>а>с>пи между т;жк >мп и прямыми и удовлетворяющим следующим условиям: ()) каждая пара различных прямых инцидентна единствен»ой точке (т. е. для каждой пары различных прямых существует ед»гктвенная точка, лежащая на обеих прямых и называемая их пгрсгт ь.нием); ()>'г каждая пара различных ~очек пнцидентна единственной зримой (т. е. для каждой пары различных точек существует един-ешшая прямая, содержащая обе эти точки, иначе — прямая, ,>»>х»лишая через эти точки); ый) существуют четыре точки, такие, 'гто никакие три нз них ,>»»»дептны одной и той же прямой (т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
