С.И. Гуров, Д.А. Кропотов - Конспект лекций по курсу Прикладная алгебра (1127136), страница 15
Текст из файла (страница 15)
е . принято слово6[0100001]т н w(x) == х +х .Для декодированиянайдем синдром, учитыw(x)7вая, что аз == а+ 1 (и а == 1):62s == w(a) == а +а== (аз) +а== (а+ 1) +а==2а==Определим теперь значениеторого а 1 ==1,j2Е { О,+а+1=!= О. .. , 6 } , дляs:а+1,а(а+ 1 ) == о?+а,аз + а2== а2+ а+ 1s..ко3. 7.(IIIпоток) Коды, исправляrощие ошибки159Т.о. 5-я позиция ошибки определена верно 8 .Если же произошло две ошибки, например , в5и4-йпозициях, тоw(x) == х64+ х + х,6== х + х + х + 14v(x)s == 1, j == О ,~ [1 1 0 ,0 1 0 1J ти будет раскодировано сообщение [О 1 О 1]т вместо посланного [О О 1 1]т.Декодирование кодов ВЧХ в общем случае.
Рассмотрим(п, k,d)-код БЧХ длиныn == 2q-1при построениикоторого для определения порождаfощего полинома использовалось поле F == [F~ == !F[x]/(a(x)), dega(x) == qи а - некоторый примитивный элемент F , нуль кода .Пустьпри передачепроизошлоvТогдае( х)==.х.1где степени1.+ х.1 + · · · + xJv,,Jv -v ~ r ==l (d -1)/ 2J,позиции ошибок.равенствадлясиндромовe(ai), i == 1, 2, ... , 2r как системуw(ai).82.2j 1 , ...slсообщенияошибок .Запишемsiзакодированного+..+ . . . + aJv'+(+ ... + (aJv )2,aJIaJ2(aJI )2aJ2)2• • • • • • • • • • • • • • • • • • • • • • • • • • • •s 2rРешение== (aJI )2r + ...
+ (aJv )2r.(j 1,... ,Jv )данной системы для некоторого v ~ r определит искомые позиции ошибок 9 .8 Альтернативный метод декодирования кода Хэмминга см. на с.177.Такое решение всегда существует и единственно, т.к. код по построениюспособен исправлять до r ошибок.9160 IIIпоток: Глава3.В ведём обозначенияКоды, исправляrощие ошибкиf3i.== a}i , iэти1, ... , v;==величины называiот ло'Х;аmорами ошибо'Х;.П ерепишем систему :+ fЗ2 + · · · + f3v,+ rзi + . . .
+ rз~,fЗ1rзr• • • • • • • • • • • • • • • • • •Определим полином ЛО'Х;аmоров ошибо'Х;vа(х)==п (l+f3ix)==2l + a1x + a2 x + ·· · + avxv,i=1КОрНЯМИ КОТОрОГО ЯВЛЯIQТСЯ ВеЛИЧИНЫ {Зi- 1 ==a - ,ji,i== l , ... ,v.Связь междуakиf3iопределяет теорема Виета :fЗ1 + fЗ2 + · · · + f3v,fЗ1 fЗ2 + fЗ2fЗз + fЗ1 fЗз+ · ·· +f3v - 1f3v,~ fЗi1JJi2f3iз ,i1<i2 <iз• • • • • • • • • • • • • • • • • •Введённые системы задаiот величины синдромов икоэ ффициентов полином а локаторов ошибок соответственно как значениясимметриtttес'Х;их полиномов :(*) -суммы k-x степеней(**) - элементарных.локаторов ошибок;3. 7.(IIIпоток) Коды, исправляrощие ошибкиСоотношенияметрическихмеждуэтимиполиномовдвумязадаютсятипами161симтождествамиНъютона-Жирара, которые в двоичной арифметикезаписываются как+ 0'"1 О ,82 + 0'"1 81 +31:=:+3з0'"182+О,20'"2 ===0'"28 1+ЗО'"зО,• • • • • • • • • • • • • • • • • • • • • • •+0'"13v- 1+ ··· +O'"v - 131+VO'"v3v+l+O'"I3 v+ ··· +O'"v-132+O'"v3 13v+2+0'"1 81/+13v=== О ,=== О ,+ · · · + O'"v- 133 + O'"v32=== О ,• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •П оследние2r - vравенств данной системы являются СЛАУ относительно 0'"1 , .
. . , O'"v . В литературе покодам она получила название к;лючевого уравнения . Еёр ешение позволяет найти полином локатор ов ошибокО'"(х) .О сновная трудность в решении данной СЛАУ состоит в том, что значениеvнеизвестно . Её решателиназывают дек;одерами .ДекодерPGZ (Peterson-Gorenstein-Zierler)по следовательномv===r, r - 1, ...решенииключевогосостоит ву равн ения длядо тех пор, пока матрица очереднойСЛАУ не окажется невырожденной (при переходе откr - 1 полагаемO'"r=== О).r162 IIIпоток: ГлаваАлгоритм ВМА3.Коды, исправляrощие ошибки(B erlekamp-Messey)наиболее эффективен для не слишком длинных кодов БЧХ ; егоздесь не рассматриваем.Декодер на основе расширенного алгоритма Евклида-рассмотрен ниже.После нахождения а(х) полным перебором можно.отыскать все его корни a-Ji, а по нимбок( j1,.. .,jv-позиции оши-).Алгоритм декодирования ВЧХ-кодаРассмотрим(n, k, d)-код БЧХ , n == 2q - 1, исправляFоrций r == l (d - 1) /2 J ошибок и а - нуль кода примитивный элемент мулитипликативной группы поляtrg==!F 2[х]/ (а(х)) , порождённого полиномом а(х) ,deg а(х) == q.
Пусть принято слово w(x) , которое, возможно, не является кодовым,поскольку может содер жать ошибки.1. Для слова w ( х) найти все синдромы si == w ( ai) ,i == 1, ... ' d- 1.2.Найти полином локаторов ошибок а(х) , используя тот или иной декодер.3.Найти все корниа(х)полным перебором всехиенулевых элементов поляkl , ... , а k v .корни суть а10trg; пусть найденные4.Н айти позиции ошибок5.И справить ошибки , получив словоv( х) == w ( х)10 ихJi-n-ki, i == 1, ...
, v.+ xJl + ... + xJv.2q - 1 = n, т.е. этот этап алгоритма линеен по n3. 7.(IIIпоток) Коды, исправляrощие ошибки1636. Найти все значения v( ai), i == 1, ... , v и еслине все они равны нул1о, то выдать отказ от декодирования .Мы будем использовать деrк;одер на основе расширенного алгоритма Евrк;лида . Опишем его .Для нахождения полинома локаторов ошибок а(х),а затем и его корней, рассмотр и м вспомогательный синдромныu полино.мs(x)221 +s1x+s2x + .. . +s 2rx r,==где Si == w ( ai), i == 1, .
. . , 2r - синдромы и формальноs0== 1.Если перемножить полиномы-синдромный и локаторов ошибок, получим полином значении ошибоrк;:s(x) a(x)21 + AI X + А2Х + ... + A2r+vx r+v .2==Коэффициенты этого полинома определяi{)Т СЯ соотношением для произведения многочленов-.~Ai==Lsjai- j,i == 1, ... , 2r+ v.j=OЗамечаем, что значенияi == v + 1, ... , 2rAiпо данной формуле длясуть левые части равенств ключевогоуравнения, т.е. все они равны О .Таким образом, полином значений ошибок имеет нулевую << среднюю часть>> .
Обозначим первую часть -А(х) ,а из заключительной части вынесим за скобку x 2r + l:s(x)a(x)==2(1 + А 1Х + А2х + ... + AvXv ) +=Л(х)164 IIIпоток: Глава3.Коды, исправляrощие ошибкиЭто означает, чтоТаким образом , некоторый многочлен Л(х) степениv~rи полином локаторов ошибок О"(х) удовлетворяют соотношениiо В езуs(x)O"(x)+ x r+ a(x)21(напоминание: работаем в поле IF~== Л(х)rvIF 2 [х]/ (а(х))) .Это соотношение может быть решено относительноО" (х) помощыо расширенного алгоритма Евклида, приэтом :•условие остановкиного остатка ~-степень очередного полученr;• количество совершенных ошибок v == deg О" (х);• при решении не требуется знать сам м ногочленЛ(х).Пример3.13 (декодирования БЧХ-кода на основе расширенного алгоритма Евклида).Рассмотрим БЧХ (15, 5, 7)- код 15 == 2q- 1 == 24 - 1,исправляiощий до r == 3 ошибок . Пусть при построе15нии кода в качестве поля разложения бинома х - 14использовалось поле IF~ rv IF 2 [ х] / ( х + х + 1) и а нул ь кода.Пусть также передаётся сообщение[О 11 О 1 ]т+-742u(x) == х +х +х.3.
7.(IIIпоток) Коды, исправляrощие ошибки165При систематическом кодировании (опустим этотэтап) кодовое слово естьv(x )=== xl4+xl2+xll+xв+x4+xз+x2+x ~~ [О 1 1 1 1 О О О 1 О ,О 1 1 О 1] т .Пусть ошибки произошл и в О ,приня тое словоw(x) === х146и1 2- й позициях, т.е.-+х118642+ х + х + х + хз + х + х + 1 ~~ [1 1 1 1 1 О 1 О 1 О О 1 О О 1] т .Длядальнейш ихбитсяпредставлениеlr2 [х] /4(хвычислени йвенулевыхн ампон адо-элементов+ х + 1)полякак степеней его генератора(дублируем таблицу со с . 72):а1аа2а2азаз4аа5а+ 12а +аа6аз+ а2а7аз+ а+ 12а +1а8а9а10аз+ а2а +а+ 1allаз+ а2 +аа 12аз + а 2 + а + 1аз+ а2 + 1аз+ 11аlЗal4al5а166 IIIпоток : Глава3.1. П оскольку d - 1Коды, исправляrощие ошибки== 2r == 6,найдём все6синдромов для принятого слова:s1== w(a) ==2== (аз+ 1) +(аз+ а+а)+ (а + 1) +(аз+ а )+22+(а+ 1) +аз+ а +а+ 12== а,22s 2 == w ( а ) == (w (а)) == а ,== w(аз) == а42 + азз + а24 + al8 +al2 + ag+82з~2~~~8== а + 1 == а ,422== а4s4 == w( а ) == (w( а ) )'85 == w(a5) == а1о + а55 + а4О +аза+ а2о + al5++ alo + а5 + 1 ==== alO + alO + a lO+ 1 + а5 + 1 + alO + а5 + 1 == 1,22246sв == w(a ) == (w(аз)) == (а + 1 ) == а + 1 ==а.Таким образом, синдромный полином есть2.По декодеру на базе расширенного алгоритма Евклида необходимо по а(х) иs(x) решить соотношениеВезу7х а(х)относительно о- (х) .Реш аем:+s(x)o-(x)==Л(х)3.
7.(IIIпоток) Коды, исправляrощие ошибкиШаг О .// Инициализация7r-2 (х) == х ,+х +а+ ах+ 1,r_l (х) == s(x) == ах8+а ха-2(х)==a_l(x ) ==Шаг3+а2х26544х +О,1.1. // Делим с остатком r -2(х) на r _ 1 (х)r -2(х) == r - l(x)qo(x) + ro(x) ,qo(x) == а14х+аlз ,ro(x) == а8х5 + а12х4 + allxз +deg ro (х) == 5 > 3,ао(х) == а-2(х) + a_l (x) qo(x)== qo(x) == al4x + аlЗ .Шаг167аlЗ '2. // Делим с остатком r_ 1 (x) на r 0 (x)r_l(x) == ro(x)ql(x) + r1(x),28ql (х) == а х + а ,rl (х) == a l4x4 + азхз + а2х2 + a llx ,deg r 1 ( х) == 4 > 3,а1(х) == a_l(x) + ao(x) ql(x) ==== а7 х2 + allx .Шаг3. // Делим с остатком r 0 (x) на r 1 (x)ro (х) == r1 (х) Q2 (х) + r2 (х) ,9q2(x) == а х ,135r 2 (x) == а х + а ,deg r2(x) == 1 :( 3,а2(х) == ао (х) + a1(x) q2(x) ====а(х)==35214ах + а х + а х+а13.168 IIIпоток: Глава3.Коды, исправляrощие ошибкиЭто последний шаг алгоритма Евклида, т.
к . степеньостаткаr 2 ( х) не превосходит r == 3.Таки м образом, полином локаторов ошибок найден:а(х)и==а2 (х)==52141ахз+а х +а х+а з .v == deg а(х) == 3.3. Найдём корни а( х) полным перебором 11 , используя построеннуiо ранее таблицу степеней а :а (а)а (а )== а ,7912а + а +а+ а з == аз + а +а,а1о + all + а2 + а1з == О ,а1з + а 1з +аз+ а1з == а2 + 1,411а+ 1 + а + а з == а з,а4 + а2 + а5 + аlЗ == аз+ а2,7416а + а + а + а з == аз+ 1,a(as)alo+a6+a7 +alз==2а (а )а( аз)а (а4)а(а 5 )а (а6)79а (а )107а +а +1+а з112881а з+ а + а + а з1091аз+а2+ 1 ,О,а (а )а+ аa (all)а4а ( а12)== 1,alO +а+ а12 + аlЗ == а2 +а+ 1,а1з +аз+ а1з + а1з == а2 + 1 ,а + а5 + а14 + аlЗ == О.а(аlЗ)а( а14 )a(al5)114а7+ а + а з == а,+ а12 + а1о + а1з == а2+а14ясно , что корней всего З+ all +а1з+а,3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
