Коды, исправляющие ошибки (1127158), страница 8

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 8)

. .. . . = α6 + α3 + 1 = α3 + α2 + α3 + 1 = α2 + 1 = α8 ,s4 = w(α4 ) = (w(α2 ))2 = α4 ,s5 = w(α5 ) = α70 + α55 + α40 + α30 + α20 + α15 + α10 + α5 + 1 == α10 + α10 + α10 + 1 + α5 + 1 + α10 + α5 + 1 = 1,s6 = w(α6 ) = (w(α3 ))2 = (α2 + 1)2 = α4 + 1 = α.Òàêèì îáðàçîì, ñèíäðîìíûé ïîëèíîì åñòüs(x) = αx6 + x5 + α4 x4 + α8 x3 + α2 x2 + αx + 1.112 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè113 / 152Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÄåêîäèðîâàíèå êîäîâ Á×ÕÊîäû Á×Õ: ïðèìåð äåêîäèðîâàíèÿ...2. Âûáèðàåì äåêîäåð íà áàçå ðàñøèðåííîãî àëãîðèòìàÅâêëèäà ðåøàåì óðàâíåíèå x7 a(x) + s(x)σ(x) = λ(x)(íàõîäèì σ(x) ïî a(x) è s(x) ):Øàã 0.r−2 (x) = x7 ,r−1 (x) = s(x) = αx6 + x5 + α4 x4 + α8 x3 ++α2 x2 + αx + 1,y−2 (x) = 0,y−1 (x) = 1.Øàã 1.r−2 (x) = r−1 (x)q0 (x) + r0 (x),q0 (x) = α14 x + α13 ,r0 (x) = α8 x5 + α12 x4 + α11 x3 + α13 ,y0 (x) = y−2 (x) + y−1 (x)q0 (x) = q0 (x) = α14 x + α13 .ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè114 / 152Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÄåêîäèðîâàíèå êîäîâ Á×ÕÊîäû Á×Õ: ïðèìåð äåêîäèðîâàíèÿ...Øàã 2.r−1 (x) = r0 (x)q1 (x) + r1 (x),q1 (x) = α8 x + α2 ,r1 (x) = α14 x4 + α3 x3 + α2 x2 + α11 x,y1 (x) = y−1 (x) + y0 (x)q1 (x) = α7 x2 + α11 x.Øàã 3.r0 (x) = r1 (x)q2 (x) + r2 (x),q2 (x) = α9 x,r2 (x) = α5 x + α13 ,y2 (x) = y0 (x) + y1 (x)q2 (x) = αx3 + α5 x2 + α14 x + α13 .Ýòî ïîñëåäíèé øàã àëãîðèòìà Åâêëèäà, ò.ê.

òåêóùèé îñòàòîêr2 (x) èìååò ñòåïåíü 1 6 r = 3.Òàêèì îáðàçîì, ïîëèíîì ëîêàòîðîâ îøèáîê íàéäåí:σ(x) = y2 (x) = αx3 + α5 x2 + α14 x + α13è ν = deg σ(x) = 3.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÊîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÄåêîäèðîâàíèå êîäîâ Á×ÕÊîäû Á×Õ: ïðèìåð äåêîäèðîâàíèÿ...3. Íàéä¼ì êîðíè σ(x) ïîëíûì ïåðåáîðîì (α4 = α + 1):σ(α) = α4 + α7 + 1 + α13 = α2 ,σ(α2 ) = α7 + α9 + α + α13 = α3 + α2 + α,σ(α3 ) = α10 + α11 + α2 + α13 = 0,σ(α4 ) = α13 + α13 + α3 + α13 = α2 + 1,σ(α5 ) = α + 1 + α4 + α13 = α13 ,σ(α6 ) = α4 + α2 + α5 + α13 = α3 + α2 ,σ(α7 ) = α7 + α4 + α6 + α13 = α3 + 1,σ(α8 ) = α10 + α6 + α7 + α13 = α3 + α2 + 1,σ(α9 ) = α13 + α8 + α8 + α13 = 0,σ(α10 ) = α + α10 + α9 + α13 = α,σ(α11 ) = α4 + α12 + α10 + α13 = α2 + α,σ(α12 ) = α7 + α14 + α11 + α13 = 1,σ(α13 ) = α10 + α + α12 + α13 = α2 + α + 1,σ(α14 ) = α13 + α3 + α13 + α13 = α2 + 1,σ(α15 ) = α + α5 + α14 + α13 = 0.115 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.

×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè116 / 152Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÄåêîäèðîâàíèå êîäîâ Á×ÕÊîäû Á×Õ: ïðèìåð äåêîäèðîâàíèÿ...4. Ïî íàéäåííûì êîðíÿì α3 , α9 , α15 âû÷èñëÿåì ïîçèöèèîøèáîê:j1 = −3 ≡15 12,j2 = −9 ≡15 6,j3 = −15 ≡15 0.5. Èìååì: ïîëèíîì îøèáîê e(x) = x12 + x6 + 1 îïðåäåë¼íïðàâèëüíî, vb(x) = w(x) + e(x) == x14 + x12 + x11 + x8 + x4 + x3 + x2 + x.è êîäîâîå ñëîâî âîññòàíîâëåíî.6. Ïðîâåðêà vb(α) = vb(α2 ) = . . . = vb(α6 ) = 0 ãîâîðèò îò òîì,÷òî âîññòàíîâëåíèå âåðíîå (èëè æå ïðîèçîøëî r 3 îøèáîê,íî ýòî êðàéíå ìàëîâåðîÿòíî).ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÊîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÄåêîäèðîâàíèå êîäîâ Á×ÕÁ×Õ (n, k, d)-êîäû: èñòîðè÷åñêèå ñâåäåíèÿÏåðâûì ïðàêòè÷åñêè ðåàëèçîâàííûì Á×Õ-êîäîì áûë(127, 92, 11)-êîä. ñèñòåìàõ ïåðåäà÷è äàííûõ øèðîêî èñïîëüçóåòñÿ äâîè÷íûé(255, 231, 7)-êîä, ïîñòðîåííûé ñ ïîìîùüþ ïðèìèòèâíîãîýëåìåíòà α ∈ F82 255-ãî ïîðÿäêà:ñòåïåíü ïîðîæäàþùåãî ìíîãî÷ëåíà g(x) 24;êîðíè g(x) α, α2 , α3 , α4 , α5 è α6 .â îáùåì ÷èñëå ñëîâ äëèíû 255 äîëÿ êîäîâûõ 12−24 ≈ 16·106 (ïðè ââîäå ñëó÷àéíûõ ñëîâ òîëüêî ïðèìåðíîîäíî èç øåñòíàäöàòè ìèëëèîíîâ îêàçàëîñü áû êîäîâûì). òå÷åíèè ìíîãèõ ëåò íå áûëî ñëó÷àÿ, ÷òîáû îøèáêà ïåðåäà÷èïðîøëà íåçàìå÷åííîé.Äëÿ âûáîðà ìèíèìàëüíûõ ìíîãî÷ëåíîâ ïðè ïîñòðîåíèèÁ×Õ-êîäîâ ñîñòàâëåíû ñïåöèàëüíûå òàáëèöû.117 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.

×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè118 / 152Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÄåêîäèðîâàíèå êîäîâ Á×ÕÁ×Õ (n, k, d)-êîäû: ðåçþìåÁ×Õ-êîäû ÿâëÿþòñÿ ïîäêëàññîì öèêëè÷åñêèõ.Ñàìîå öåííîå ñâîéñòâî âîçìîæíîñòü ïîñòðîåíèÿ êîäà ñçàäàííûì êîäîâûì ðàññòîÿíèåì d.Êîäèðîâàíèå îñóùåñòâëÿåòñÿ ñ ïîìîùüþ ïîðîæäàþùåãîïîëèíîìà, èìåþùåãî êîðíÿìè ñòåïåíè íåêîòîðîãîïðèìèòèâíîãî ýëåìåíòà ïîëÿ.Äåêîäèðîâàíèå ìîæåò áûòü ïðîâåäåíî ñ ïîìîùüþýôôåêòèâíûõ àëãîðèòìîâ (Áåðëåêýìïà-Ìýññè,Ïèòåðñîíà-Ãîðåíñòåéíà-Öèðëåðà, Åâêëèäîâ àëãîðèòì, ...).Ñðåäè êîäîâ Á×Õ ïðè íåáîëüøèõ äëèíàõ ñóùåñòâóþòõîðîøèå (íî, êàê ïðàâèëî, íå ëó÷øèå èç èçâåñòíûõ) êîäû.Ñ ðîñòîì n ïðè ôèêñèðîâàííîì çíà÷åíèè ñêîðîñòè êîäà, êñîæàëåíèþ, d/n → 0, è ïîýòîìó ïðè áîëüøèõ äëèíàõïðèõîäèòñÿ èñïîëüçîâàòü äðóãèå êîäû.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÊîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÄåêîäèðîâàíèå êîäîâ Á×ÕÊîäû ÐèäàÑîëîìîíà: îáùèå ñâåäåíèÿØèðîêî èñïîëüçóåìûì ÷àñòíûì ñëó÷àåì êîäîâ Á×Õ ÿâëÿþòñÿêîäû Ðèäà-Ñîëîìîíà (ReedSolomon codes), êîòîðûåïîçâîëÿþò èñïðàâëÿòü ïàêåòû îøèáîê.Ïàêåò îøèáîê (error burst) ãðóïïà áèòîâ, â êîòîðîé äâàïîñëåäîâàòåëüíûõ îøèáî÷íûõ áèòà âñåãäà ðàçäåëåíûïðàâèëüíûìè áèòàìè, ÷èñëî êîòîðûõ ìåíåå óñòàíîâëåííîãî.Êîäû ÐèäàÑîëîìîíà:íåáèíàðíûå (â ÷àñòíîñòè, î÷åíü ðàñïðîñòðàíåíû êîäû,ðàáîòàþùèå ñ áàéòàìè);÷àñòî èñïîëüçóþòñÿ â óñòðîéñòâàõöèôðîâîé çàïèñè çâóêà, â òîì ÷èñëåíà êîìïàêò-äèñêè.119 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.

×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè120 / 152Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÄåêîäèðîâàíèå êîäîâ Á×ÕÏðèìåð íåãðóïïîâîãî áëîêîâîãî êîäàÏóñòü ïî äâîè÷íîìó ñèììåòðè÷íîìó êàíàëó ñ øóìîì òðåáóåòñÿïåðåäàâàòü t = 4 áèòîâûõ ñîîáùåíèÿ S1 , S2 , S3 , S4 äëèíû 2.Áëîêîâûé ðàçäåëèìûé íåãðóïïîâîé êîä C , èñïðàâëÿþùèé 1îøèáêó çàäà¼òñÿ òàáëèöåéS00011011C00110011011001111000¾Çàçîð¿: 25 − 4 · (1 + 5) = 8 ñëîâ;ãðàíèöà Ïëîòêèíà äîñòèãàåòñÿ(ïðîâåðüòå)Êîäîâîå ðàññòîÿíèå ïîñòðîåííîãî êîäà C ðàâíî 3 è ïîñòðîåíñèñòåìàòè÷åñêèé (5, 2, 3)-êîä, ñîäåðæàùèé èñõîäíîå ñîîáùåíèå(äëèíû 2) â ïåðâûõ äâóõ ïîçèöèÿõ.Äëÿ ñðàâíåíèÿ: (7, 4, 3)-êîä Õýììèíãà êîäèðóåò 16ñîîáùåíèé äëèíû 4.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè121 / 152Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÄåêîäèðîâàíèå êîäîâ Á×ÕÏðèìåíåíèå ïîìåõîóñòîé÷èâîãî êîäèðîâàíèÿ IÄàëåêî íå âñåãäà îò êîäà òðåáóåòñÿ êîððåêöèÿ îøèáîê.Ìíîãèå ñîâðåìåííûå êàíàëû ñâÿçè îáëàäàþò õîðîøèìèõàðàêòåðèñòèêàìè, è ïðèíèìàþùåé ñòîðîíå ÷àñòîäîñòàòî÷íî ëèøü ïðîâåðèòü, óñïåøíî ëè ïðîøëà ïåðåäà÷à,à êîíêðåòíûå ïîçèöèè íåâåðíûõ ñèìâîëîâ å¼ íåèíòåðåñóþò. ýòèõ ñëó÷àÿõ ïðèìåíÿþòñÿ êîäû ñïåöèàëüíîïðåäíàçíà÷åííûå äëÿ îáíàðóæåíèÿ îøèáîê, à íå äëÿ èõèñïðàâëåíèÿ.Êîäû èñïîëüçóþòñÿ äëÿ ïîëó÷åíèÿ íàäåæíîé ñâÿçè, êîãäàìîùíîñòü ïðèíèìàåìîãî ñèãíàëà áëèçêà ê ìîùíîñòèòåïëîâûõ øóìîâ. âîåííûõ ïðèëîæåíèÿõ äëÿ çàùèòû ïðîòèâ íàìåðåííîîðãàíèçîâàííîé ïðîòèâíèêîì èíòåðôåðåíöèè.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.

×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè122 / 152Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÄåêîäèðîâàíèå êîäîâ Á×ÕÏðèìåíåíèå ïîìåõîóñòîé÷èâîãî êîäèðîâàíèÿ IIÏåðåäà÷à äàííûõ â âû÷èñëèòåëüíûõ ñèñòåìàõ îáû÷íî÷óâñòâèòåëüíà äàæå ê î÷åíü ìàëîé äîëå îøèáîê. Çäåñüïîìåõîçàùèù¼ííûå êîäû èñïîëüçóþòñÿ äëÿçàùèòû äàííûõ âî âíóòðåííèõ è âíåøíèõ ÇÓ (ëåíòû,äèñêè...),çàùèòû äàííûõ íåïðàâèëüíîãî ôóíêöèîíèðîâàíèÿ èëèøóìîâ â öèôðîâûõ ëîãè÷åñêèõ öåïÿõ,ñæàòèÿ (ïëîòíîé óïàêîâêè) äàííûõ.Òåîðèÿ êîäèðîâàíèÿ ïðèìåíÿåòñÿ òàêæå äëÿ ïîëó÷åíèÿóñòîé÷èâûõ ïðèçíàêîâ èç áèîìåòðè÷åñêèõ õàðàêòåðèñòèê(ñåò÷àòêà ãëàçà, îòïå÷àòêè ïàëüöåâ, ...).Âñÿ ìàòåìàòèêà äåëèòñÿ íà òðè ðàçäåëà: íåáåñíàÿ ìåõàíèêà,ãèäðîäèíàìèêà è òåîðèÿ êîäèðîâàíèÿ.Â.

È. ÀðíîëüäÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÇàäà÷è ñ ðåøåíèÿìèÐàçäåëû I1Áëîêîâîå êîäèðîâàíèå. Êîäû Õýììèíãà2Ãðóïïîâûå (ëèíåéíûå) êîäûÎïðåäåëåíèå è ñâîéñòâàÊîäèðîâàíèå ëèíåéíûìè êîäàìèÄåêîäèðîâàíèå ëèíåéíûõ êîäîâ3Öèêëè÷åñêèå êîäûÎïðåäåëåíèå, îñíîâíûå ñâîéñòâà, ïðèìåðÊîäèðîâàíèå öèêëè÷åñêèìè êîäàìè è äåêîäèðîâàíèå4Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÎïðåäåëåíèå è îñíîâíûå ñâîéñòâàÊîäèðîâàíèå Á×Õ-êîäàìèÄåêîäèðîâàíèå êîäîâ Á×Õ5Çàäà÷è ñ ðåøåíèÿìè123 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.

×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè124 / 152Çàäà÷è ñ ðåøåíèÿìèÇàäà÷à ÒÊ-1Äëÿ ëèíåéíîãî êîäà, çàäàííîãî ñâîåé ïðîâåðî÷íîé ìàòðèöåé0 0 1 0 1 1 1H =  0 1 0 1 1 1 0 1 0 1 1 1 0 0òðåáóåòñÿ1ïîñòðîèòü ïîðîæäàþùóþ ìàòðèöó G êîäà äëÿñèñòåìàòè÷åñêîãî êîäèðîâàíèÿ, ïðè êîòîðîì áèòûèñõîäíîãî ñîîáùåíèÿ ïåðåõîäÿò â ïîñëåäíèå áèòû êîäîâîãîñëîâà;2íàéòè òàêîå êîäèðîâàíèå äëÿ ñîîáùåíèéu1 = [1101]T , u2 = [1001]T .ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè125 / 152Çàäà÷è ñ ðåøåíèÿìèÇàäà÷à ÒÊ-1 (I4 è I3 åäèíè÷íûå ìàòðèöû ïîðÿäêà 4 è 3)...ÐåøåíèåÏðîâåðî÷íàÿ ìàòðèöà H èìååò ðàçìåðíîñòü 3 × 7,ñëåäîâàòåëüíî êîä ïðè äëèíå n = 7 ñîäåðæèò m = 3ïðîâåðî÷íûõ è k = 7 − 3 = 4 èíôîðìàöèîííûõ áèò.Ïîðîæäàþùàÿ ìàòðèöà êîäà G, îáåñïå÷èâàþùàÿ òðåáóåìîåPñèñòåìàòè÷åñêîå êîäèðîâàíèå, äîëæíà èìåòü âèä.I4Ìàòðèöó P ìîæíî ïîëó÷èòü, åñëè ïðèâåñòè ïðîâåðî÷íóþìàòðèöó H ê âèäó I3 P , ïðåîáðàçóÿ ñòðîêè:0 0 1 0 1 1 11 0 1 1 1 0 0(1)↔(3)(1)+(3) 7→(1)0 1 0 1 1 1 0 −−−−−→ 0 1 0 1 1 1 0 −−−−−−−−→1 0 1 1 1 0 00 0 1 0 1 1 11 0 0 1 0 1 1→− 0 1 0 1 1 1 00 0 1 0 1 1 1ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.

×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè126 / 152Çàäà÷è ñ ðåøåíèÿìèÇàäà÷à ÒÊ-1...Òåïåðü ìîæíî ïîñòðîèòü òðåáóåìóþ ïîðîæäàþùóþ ìàòðèöó èîñóùåñòâèòü êîäèðîâàíèå äëÿ u1 = [1101]T , u2 = [1001]T :110G=1000011010011100101010,001000[v 1 , v 2 ] = G × [u1 , u2 ] = 11010111.001Íåòðóäíî âèäåòü, ÷òî áûë çàäàí (7, 4, 3)-êîä Õýììèíãà,ïîìåùàþùèé èíôîðìàöèîííûå áèòû â ïîñëåäíèå 4, àïðîâåðî÷íûå â ïåðâûå 3 ïîçèöèè êîäà.Çàìåòèì, ÷òî òðàäèöèîííî ïðîâåðî÷íûå áèòû ðàñïîëàãàþòñÿ â1, 2, 4, 8, .

. . ïîçèöèÿõ êîäîâîãî ñëîâà.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè127 / 152Çàäà÷è ñ ðåøåíèÿìèÇàäà÷à ÒÊ-2Öèêëè÷åñêèé (9, 3)-êîä çàäàí ñâîèì ïîðîæäàþùèì ïîëèíîìîìg(x) = x6 + x3 + 1.Òðåáóåòñÿ îïðåäåëèòü ìèíèìàëüíîå ðàññòîÿíèå êîäà d, à òàêæåîñóùåñòâèòü ñèñòåìàòè÷åñêîå êîäèðîâàíèå ïîëèíîìàu(x) = x2 + x ↔ [011]T .ÐåøåíèåÄëÿ îïðåäåëåíèÿ ìèíèìàëüíîãî êîäîâîãî ðàññòîÿíèÿ d íàéä¼ìâñå êîäîâûå ñëîâà:v(x) = g(x)(ax2 + bx + c) = (x6 + x3 + 1)(ax2 + bx + c) == ax8 + bx7 + cx6 + ax5 + bx4 + cx3 + ax2 + bx + c,a, b, c ∈ F2 .ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÇàäà÷è ñ ðåøåíèÿìèÇàäà÷à ÒÊ-2...g(x) = x6 + x3 + 1, u(x) = x2 + x âåêòîðíîì âèäå âñå êîäîâûå ñëîâà ïðåäñòàâëÿþòñÿ êàê[ a, b, c, a, b, c, a, b, c ].Î÷åâèäíî, ÷òî ìèíèìàëüíûé õýììèíãîâ âåñ íåíóëåâîãîêîäîâîãî ñëîâà ðàâåí 3 è, ñëåäîâàòåëüíî, d = 3.Ïðîâîäèì ñèñòåìàòè÷åñêîå êîäèðîâàíèå ñîîáùåíèÿ u(x):v(x) = x6 u(x) + r(x) =r(x) ≡g(x) x6 u(x) ≡x6 +x3 +1 x8 + x7 = x5 + x4 + x2 + x,= x8 + x7 + x5 + x4 + x2 + x ↔ [011011011]Tè óáåæäàåìñÿ, ÷òî áèòû ñîîáùåíèÿ íàõîäÿòñÿ â êðàéíèõïðàâûõ ïîçèöèÿõ êîäîâîãî ñëîâà.128 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.

Характеристики

Список файлов учебной работы