Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 135
Текст из файла (страница 135)
Величина е'гг (а) называется локатором оигибки. В этом случ синдром 5 (ч) --: аг — ' однозначно определяет ошибку, так к его (а) чь еггг (а) при 1 < г, 1' ~~ и и 4 2. Циклические коды 1!режде чем переходить к циклическим кодам общего вида, ,досмотрим следукиций пример. у.43. Пример. Пусть элемент а е !)'1к -- корень многочлена 1 е Ге 1х!. Тогда минимальными многочлеками але,,ся;, и а и ое' пад нолем 1'к являются соответственно пби (х) х; ! и т<" (х) х' -; х' -'. хи .
х + 1. Оба много,лсни лбы (х) и ты> (х) суть делители многочлена х" -- 1. Те~срь чы можем определить бинарный циклический код С с ио)н,кджлцнм многочленом и =- гн<ипбм. Так как г( делит многоч. си / Е )к !х1((х1к — !) тогда и только тогда, когда )." (се) , (мк! — О, то матрицу Н в (9.3) можно заменить матрицей Н ки.ю 1 а ак ... аы! Н -(, !1ижс мы покажем (см. теорему 9.40 и пример 9.47), что минимашшое расстояние кода С не меньше 5; следовательно, код С может исправлять 2 ошибки. Код С является циклическим (!5,7)- ко.ом. Пусть и 5, -- ~~ н;и', и 5 ~~~ онхм ю'=Π— компоненты синдрома 5 (ч) — Нчт. Тогда т ~ С в том и только точ лучив, когда 5 (у) — Нт1 — О.
В свою очередь это соотио,ь нш: равносильно тому, что 5, — 5к =-- О. Если элементы паля )Ем иредстзвить в двоичной векторнон записи, т. е. вместо элемента а" чоместить соответствующий вектор-столбец, то указанная выше ми~рнии Н принимает вид '1 0 0 0 1 0 О 1 ! 0 1 0 1 1 1 )1)и ..„ !л эт~ и столбцы матрицы Н оиределялись следующим образом: червь, Рш и 4 координаты' 1-го столбца явлиются. коэффициентами таииги элемента ! в виде 1 †. 1 ак + 0 ск' + 0 сек + 0 ак, ионные 4 коордшшты 2-го столбца являкпся коэффициентами "'«' ни элемента о.
в виде ек =- 0 екк '- 1 о' ! О ак -(- 0 ак и 1!оследние 4 координаты 1-го столбца являются коэффи- 0 1 0 0 0 0 1 0 0 О О 1 ! 0 0 0 0 0 0 ! 0 0 1 0 0 ! 1 1 1 1 0 1 0 1 0 1 1 0 1 0 0 О 1 1 О 1 1 1 0 0 0 1 1 0 0 0 1 1 1 О О 1 0 1 1 0 1 1 ! 1 1 1 ! 0 О ! 1 ! 1 0 0 1 ! 1 1 ! О 0 0 1 0 0 0 ! 1 0 0 1 0 1 0 1 1 1 1, 608 Гл. сь Приложения конечных полей циеитами в записи элемента 1 в виде 1 = 1 а' --,- О и' И 0 а' ! 0 я", последние 4 координаты 2-го столбца являются коэфф циеитами в записи элемента и' в виде и' — 0 и' е 0 и' -!- 0 ах 1 ал н т. д.
Для вычисления используется соотношение и' и- 1 =О. Допустим, что полученный вектор и — (нч, ..., о„) содерис не более двух ошибок. Например, е (х) х" с хл.-, где 0 и,, аз: 14, а, 4= ае, Тогда 5, —. а' ч-и", 5 =-. и" -)-азпь ПУсть и,:: Ял, з)е — - и": — локаторы ошибок; значит, 5~ -- зн + Чл 5з == Ч| -' з)с поэтому з л з 5ч — ' 5~ -' 5)зи Ф 51ч~ а следовательно, 5~Ч~ "- (51 ' 5з51 ) з11 Если имеется 2 ошибки, го 1), 1 и и ' являются корнями многочлеи з(х) -- 1 5х; (5; 5з5~ ')х. (9, ' и,', а следов ' Если имеется только одна ошибка, то 5~ -- Чь 5з тельно, 5 ! 5з -- О, и тогда а (х) - 1 — 5зх Если ошибок нет, то 5, 5л -- О, и получено правильное код., вое слово хч.
Итак, в начале мы вычисляем синдром 5 (т) -= Оут для иол ченного вектора зз, затем найдем х (х) и, наконец, с помощью ко ней многочлеиа з (х) найдем ошибки. Если 5, Ф О, то многочле определенный формулой (9.5), имеет корень в поле Ксл. Есл, миогочлен, заданный формулой (9.4), ие имеет корней в поле Г' то мы получаем, что векгор ошибок е (х! имеет более двух не левых компонент и, следовательно, эти ошибки нельзя исирави с помощью данного (15,7)-кола. Пусть, например, полученное слово имсеч вил ч-=100 ! 11000000000. Тогда 5 (т) — сх ) задается формулами зБзХ 5, =-1 Гик, и' - а'== яе-- и'". 5л=-1; а' и'х ни" 1, ил 4 2. пиквик»гкио коды 609 б!)сс)((и)с)ен в (х) из (9.4) имеет вид 1 ! ((хь ! оь)х ! П, а ..
иг ! ак -",— (1 Ч- иг) (с(г —,— »хь)-! ! хг =- .- ! -г (иь + и') х .'- (1 + и -, 'и') .к'. б)екс);!»)ы проб и ошибок найдем, что корпи мпогочлена ь (х) рав- 7 — ! 7 )! )о(юшя а и и . Следовательно, )Б и, 0 .= аг, т. е.
пл а Таким образом, мы знаем, что ошибки должны нахо, „,и па местах, соответствующих х' и х'", т. е, в 9-й н 15-й компонентах вектора ч. Переданное кодовое слово должно, слеюват(льно, иметь вид кг -- 100!1!001000001, огь г(ь-) !) 1 оь и- ьлг(ь.(-л-г), а( -!)(ььи — г) Зкк )((гдовое слово нс декодируетси путем деления соответствующего ечу мпогочлепа на порождакяций многочлен д (х). В результате ьи! получаем многочлен ! -'- х' ! хь Е хь и остаток, равный О.
Таким образом, заключаем, что переданное сообщение имело ш и 10010! 1. П 9.44. Определение. Пусть () — целое неотрицательное число, .'. пусгь и Е Г,,„— примитивный корень и-й степени из 1, где т иляется мультипликативным порядком числа с) по модулю и. '1'огда кодом Боуэа — Чоудхури — Хоквинеема (или БЧ Х -кодом) агины и с, конструктивны.и расстояниел» И, 2:, д ...
и, над полем У, называется циклический код, определяемый корнями порождающего многочлена ,„ь,ь.! ь,и — г 1х,ш через т(') (х) обозначить минимальный многочлен элемента а' над полем !гч, то порождающий многочлен и (х) соответ. твующего БЧХ-кода имеет вид д(х) = НОК(т((о(х) т('!')(х), ..., т(ь "и "(х)). Бажны также и некоторые частные случаи общего определения ') 41. Так, если () =- 1, то соответствующий БЧХ-код называется 1)'!Х-кодом в узком смысге.
Если п —. д"' — 1, то соответствую(!(нй БЧХ-код называется примитивным. Если п =- с) — 1, то !"!Х-ьод длины п над полем Гя называется кодом Рида — Соло.м пи 9 4б Теорема. Минимальное расстояние БЧХ-кода с кон""руктивным расстоянием д не меньше, чем»(. Доказательство. БЧХ-код совпадает с нуль-пространством и1'ои(7очной матрицы 1 аь и(и — !)ь ! а'' ско! †!)(В-)!) 14 .=- ! л, 9. Прнложепня конечных полек о)о что любые (( — 1 столбцов этой матриць) линейно нц Если мы рассмотрим определитель для любых ((— столбцов матрицы 11', то получим Покажем, зависимы. различных я ' Ы (Ье1) 11 а ' Ьв а (Ьч П(, я Л-1 ы' (Ьэв) („, СЬ 1 а (ьеа — 2>( (ььн-2)в> (Ь(Л вЂ” 2)в' 1 ... а Н-1 ,(ЬЯ1 1 '' ЛВ Ь(в +В, -в;в,( ) я1 в (Л-г) в (Л вЂ” 2) яь (Л вЂ” 2) аь((в> (ьв""'~(л-1) П (я'1 — я'ь) эь О.
ВС(.В-:Л вЂ” В Следовательно, минимальное расстояние этого кода не меньш чем (( 0.46. Пример. Пусть >и(') (х) х( х ' 1 — - минимальны многочлен над полем Г, для примитивного элемента а р Кв Представим степени а', 0; 1' .. 14, в виде линейных комбин ций элементов 1, я, а', я' и получим, таким образом, проверо ную матрицу Н для кода, эквивалентного (15,11)-коду Хэмминг ! 0 0 0 1 0 0 1 1 0 1 0 1 1 1 0 1 0 0 1 ! 0 ! 0 1 1 1 1 0 0 — О 0 0 0 1 0 0 1 1 0 1 0 1 1 1 1 (1 а яя аз яь аь с(е яв аь сьь (хвь я)1 я)2 ям (ьы) Этот код можно также рассматривать как БЧХ-код в узк смысле над полем Кг с конструктивным расстоянием (в —: 3 (з метим, что элемент я' таки(е является корнем многочлена ьч('> (х):, Минимальное расстояние этого кода также равно 3, поэтому может исправлять одну о(пнбку.
Для того чтобы декодирова, полученный вектор ч Р Кг, нам надо найти синдром 3 (и) )Ь вЂ” О>вт. В данном случае для циклического (15,! 1)-кода этот си драм определяется разло>кением элемента о (а) в базисе (1, аг, аз), Чтобы получить его, разделим о(х) на и(1) (х). Пуст скажем, о (х) а (х) т(в> (х) * г (х), где ((ед (г (х)) < 4; тог о (я) — г (я), так что компоненты синдрома равняются коэфф, циентам многочлена г (х).
Например, пусть (в:-- О ! О ! 1 0 О О 1 0 ! 1 1 0 1, й 2. г(иклачесяае коды .„,гза г (х) —:- 1 ~ х и, следовательно, 5(о)==Нет=(! 1 0 0)т= ! ;'-о, )):г:ес, пам надо найти вектор ошибки е веса ш (е):,' 1, имеющий тот,гз самый синдром. Лля этого мы должны опредс:шть ), 0 =-: !4, такое, что оЯ вЂ” Нет. В нашем случае. ) — 4, т. е. в но,,1ую нпом векторе э глппбочной является пятая координата, и, ьп,пм образом, переданное слово имело вид тт — О!О!000010!1101.
й.47, Пример. Пусть д — 2, и — !5, д - 4. Тогда многочлен х' х ! является неприводимым над полем Га, а его корни о)шмптпвпые элементы полЯ Гм. Если м — один нз этик коРней, зо а'" также является корнем этого многочлена„а а' -- корень гюно;жлена х' + х' 4. х' '- х; !. Тогда БЧХ-код в узком смыс е с конструктивным расстоянием д — 4 может порождаться мн ноч ~епом р(.) (ач х-'.!)('4 ' хз',-х2-'-х .'1). Э- » м.югочлеп будет также порождающим для БЧХ-кода с коняг!Ч ктннпым расстоянием д — 5, так как о' также является корнем нно очлена х' + х Ч 1. Размерность это~о кода равна !5— — !гя(гг(х)) =-7. Этот кодужебыл детальноизученв примере 9 43.
г ! Б'1Х-коды важны ввиду того, что для любого положительного иггюго числа д можно построить БЧХ-код с минимальным расс", знаем, не меныпим чем д. Для того чтобы получить БЧХ- юж - ббльшим минимальным расстоянием, мы должны увеличить ег. длину и и, следовательно, степень гп расширения поля и 1д шлем Гю БЧХ-кодс конструктивным расстоянием д ~ 21 + ! бум'г псппавлять ! ошибок (и, разумеется, любое меньшее число шш бок).
но в то же время для того, чтобы получить код с таким ко..'овым расстоянием, мы должны использовать кодовые слояа большев длины. Опишем теперь пхаориам декодирования БЧХ-кодов. Обозначим через ю (х), о (х) и е (х) соответственно передаваемый кодовый м" ~о~лен, принимаемый многочлен и многочлен ошибок; тогда "(х) ю (х) ! е (х). Прежде всего нам надо найти синдром век"о)щ э 5 (т) =- Нчт == (5ь, 5ь,м, Бь,а э)т, гдг -~з == о(а1): —.- гв(сг )-' е(сг!) == в(сг!), Ь~(!.е'Ь од — 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
