Коды, исправляющие ошибки (1127158), страница 7
Текст из файла (страница 7)
×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÊîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÄåêîäèðîâàíèå êîäîâ Á×ÕÐàçäåëû12Áëîêîâîå êîäèðîâàíèå. Êîäû ÕýììèíãàÃðóïïîâûå (ëèíåéíûå) êîäûÎïðåäåëåíèå è ñâîéñòâàÊîäèðîâàíèå ëèíåéíûìè êîäàìèÄåêîäèðîâàíèå ëèíåéíûõ êîäîâ3Öèêëè÷åñêèå êîäûÎïðåäåëåíèå, îñíîâíûå ñâîéñòâà, ïðèìåðÊîäèðîâàíèå öèêëè÷åñêèìè êîäàìè è äåêîäèðîâàíèå4Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÎïðåäåëåíèå è îñíîâíûå ñâîéñòâàÊîäèðîâàíèå Á×Õ-êîäàìèÄåêîäèðîâàíèå êîäîâ Á×Õ5Çàäà÷è ñ ðåøåíèÿìè96 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè97 / 152Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÄåêîäèðîâàíèå êîäîâ Á×ÕÄåêîäèðîâàíèå êîäà Õýììèíãà: êàê ýòî äåëàåòñÿÊîä Õýììèíãà ÿâëÿåòñÿ ïðîñòåéøèì êîäîì Á×Õ, ó êîòîðîãîr = 1, d = 3, è ïîýòîìó åãî íóëÿìè ÿâëÿþòñÿ α è α2 , ãäå α ïðèìèòèâíûé ýëåìåíò ïîëÿ Fn2 , n = 2q − 1.Äëÿ äåêîäèðîâàíèÿ ïðèíÿòîãî ñëîâà w(x) âû÷èñëÿåì ñèíäðîìs1 = w(α) (ñèíäðîì s2 = w(α2 ) íàì íå ïîòðåáóåòñÿ).Ïðès1 = 0 ïîëàãàåì vb(x) = w(x) è åñëè îøèáîê íåïðîèçîøëî, òî vb(x) = v(x).s1 6= 0 îïðåäåëÿåì çíà÷åíèå j ∈ {0, .
. . , n − 1}, äëÿêîòîðîãî αj = s1 , ïîëàãàåì vb(x) = w(x) + xj è åñëèïðîèçîøëà åäèíè÷íàÿ îøèáêà, òî å¼ ïîçèöèÿ j èvb(x) = w(x) (èíà÷å ïðîèçîøëî áîëüøåå êîëè÷åñòâîîøèáîê è vb(x) 6= v(x) ).ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè98 / 152Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÄåêîäèðîâàíèå êîäîâ Á×ÕÄåêîäèðîâàíèå êîäà Õýììèíãà: ïðèìåðÐàññìàòðèâàåì (7, 4)-êîä Õýììèíãà, ïîñòðîåííûé â ïðèìåðåäëÿ öèêëè÷åñêèõ êîäîâ (ïîðîæäàþùèé ïîëèíîì g(x) = x3 + x + 1), ãäå áûëî íàéäåíî ñèñòåìàòè÷åñêîåêîäèðîâàíèå âõîäíîãî ïîëèíîìà u(x) = x3 + x2 ↔ [0011]T :v(x) = x6 + x5 + x ↔ [0100011]T .Òåïåðü ìû ïîñòðîèëè ýòîò æå êîä ñ èñïîëüçîâàíèåì ïîëÿF = F2 [x]/ x3 + x + 1 , â êîòîðîì α3 = α + 1 è α7 = 1 äëÿïðèìèòèâíîãî ýëåìåíòà α ∈ F ∗ .Ïóñòü ïðè ïåðåäà÷å ñîîáùåíèÿ ïðîèçîøëà îøèáêà â ïîçèöèè 5,ò.å.
ïðèíÿòî ñëîâî [0100001]T ↔ w(x) = x6 + x è(íåèçâåñòíûé) ïîëèíîì îøèáîê e(x) = x5 .Äëÿ äåêîäèðîâàíèÿ w(x) íàéäåì ñèíäðîì2s1 = w(α) = α6 + α = α3 + α = (α + 1)2 + α == α2 + α + 1 6= 0.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè99 / 152Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÄåêîäèðîâàíèå êîäîâ Á×ÕÄåêîäèðîâàíèå êîäà Õýììèíãà: ïðèìåð... s1 = α2 + α + 1Íàéä¼ì αj äëÿ j = 0, . . .
, 6 , ò.å. âñå íåíóëåâûå ýëåìåíòû ïîëÿF2 [x]/ x3 + x + 1 :α0 = 1,α3 = α + 1,α1 = α,α4 = α(α + 1) = α2 + α,α2 = α2 ,α5 = α2 (α + 1) = α3 + α2 == α2 + α + 1 = s1 ,α6 = (α + 1)2 = α2 + 1 ìîæíî óæå íå âû÷èñëÿòüÎòñþäà ñëåäóåò, ÷òî îøèáêà ïðîèçîøëà â ïîçèöèè 5 è, òàêèìîáðàçîì, vb(x) = w(x) + x5 = x6 + x5 + x = v(x).Åñëè æå ïðîèçîøëî äâå îøèáêè, íàïðèìåð, â 5-é è 4-éïîçèöèÿõ, òî w(x) = x6 + x4 + x, s1 = 1, j = 0,vb(x) = x6 + x4 + x + 1 ↔ [1100101]T è áóäåò ðàñêîäèðîâàíîñîîáùåíèå [0101]T âìåñòî ïîñëàííîãî u(x) ↔ [0011]T .ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÊîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÄåêîäèðîâàíèå êîäîâ Á×ÕÊîäû Á×Õ: äåêîäèðîâàíèåÏóñòü ïðè ïåðåäà÷å ñîîáùåíèÿ, çàêîäèðîâàíîãî êîäîì Á×Õ âïîëå Fq2 = F[x]/(a(x)) ïðîèçîøëî ν îøèáîê.Òîãäà e(x) = xj1 + xj2 + · · · + xjν , ãäå ñòåïåíè j1 , . . . , jν ïîçèöèè îøèáîê, ν 6 r = [(d − 1)/2].Çàïèøåì ðàâåíñòâà si = w(αi ) = e(αi ), i = 1, 2r êàê ñèñòåìó:s1 = αj1 + αj2 + .
. . + αjν ,s2 = (αj1 )2 + (αj2 )2 + . . . + (αjν )2 ,...................................s2r = (αj1 )2r + . . . + (αjν )2r .Ëþáîå ðåøåíèå ( j1 , . . . , jν ) äàííîé ñèñòåìû äëÿ íåêîòîðîãîν 6 r áóäåò èñêîìûì (òàêîå ðåøåíèå âñåãäà ñóùåñòâóåò èåäèíñòâåííî, ò.ê. êîä ïî ïîñòðîåíèþ ñïîñîáåí èñïðàâëÿòü äî rîøèáîê).100 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè101 / 152Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÄåêîäèðîâàíèå êîäîâ Á×ÕÊîäû Á×Õ: äåêîäèðîâàíèå...Ââåäÿ îáîçíà÷åíèÿ βi = αji , i = 1, 2r (âåëè÷èíû βi íàçûâàþòëîêàòîðàìè îøèáîê), ïåðåïèøåì ñèñòåìó:s1 = β1 + β2 + .
. . + βν ,s2 = β12 + β22 + . . . + βν2 ,(1).......................s2r = β12r + β22r + . . . + βν2r .Ðàññìîòðèì ïîëèíîì ëîêàòîðîâ îøèáîêσ(x) =νY(1 + βi x) = 1 + σ1 x + σ2 x2 + · · · + σν xν ,i=1êîðíÿìè êîòîðîãî ÿâëÿþòñÿ âåëè÷èíû βi−1 = α−ji , i = 1, 2r.Äëÿ ïðîäâèíóòûõ: ýòî ïðîèçâîäÿùèé ïîëèíîì.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè102 / 152Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÄåêîäèðîâàíèå êîäîâ Á×ÕÊîäû Á×Õ: äåêîäèðîâàíèå...Ñâÿçü ìåæäó σk è βi îïðåäåëÿåò òåîðåìà Âèåòà:σ1 = β1 + β2 + . . .
+ βν ,σ2 = β1Xβ2 + β2 β3 + β1 β3 + . . . + βν−1 βν ,σ3 =βi1 βi2 βi3 ,i<i<i123.......................σν = β1 β2 . . . βν .(2)Ââåä¼ííûå ñèñòåìû çàäàþò âåëè÷èíû ñèíäðîìîâ èêîýôôèöèåíòîâ ïîëèíîìà ëîêàòîðîâ îøèáîê ñîîòâåòñòâåííîêàê çíà÷åíèÿ ñèììåòðè÷åñêèõ ïîëèíîìîâ:(1) ñóììû k -ûõ ñòåïåíåé βi , k = 1, 2r;(2) ýëåìåíòàðíûõ.Ñîîòíîøåíèÿ ìåæäó ýòèìè äâóìÿ òèïàìè ñèììåòðè÷åñêèõïîëèíîìîâ çàäàþòñÿ òîæäåñòâàìè Íüþòîíà-Æèðàðà.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè103 / 152Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÄåêîäèðîâàíèå êîäîâ Á×ÕÊîäû Á×Õ: äåêîäèðîâàíèå... äâîè÷íîé àðèôìåòèêå òîæäåñòâà Íüþòîíà-Æèðàðàçàïèñûâàþòñÿ êàês1 + σ1 = 0,s2 + σ1 s1 + 2σ2 = 0,s3 + σ1 s2 + σ2 s1 + 3σ3 = 0,.............................sν + σ1 sν−1 + .
. . + σν−1 s1 + νσν = 0,sν+1 + σ1 sν + . . . + σν−1 s2 + σν s1 = 0,sν+2 + σ1 sν+1 + . . . + σν−1 s3 + σν s2 = 0,.........................................s2r + σ1 s2r−1 + . . . + σν−1 s2r−ν+1 + σν s2r−ν= 0.Ïîñëåäíèå ðàâåíñòâà ÑËÀÓ äëÿ êëþ÷åâîãî óðàâíåíèÿÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÊîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÄåêîäèðîâàíèå êîäîâ Á×ÕÊîäû Á×Õ: äåêîäèðîâàíèå...Ïîñëåäíèå 2r − ν + 1 óðàâíåíèé äàííîé ñèñòåìû ÿâëÿþòñÿÑËÀÓ îòíîñèòåëüíî σ1 , . . . , σν .ż ðåøåíèå ïîçâîëÿåò íàéòè ïîëèíîì ëîêàòîðîâ îøèáîê σ(x).Äàëåå ïîëíûì ïåðåáîðîì ìîæíî îòûñêàòü âñå åãî êîðíè α−ji ,à ïî íèì ïîçèöèè îøèáîê ji , i = 1, 2r.Îñíîâíàÿ òðóäíîñòü â ðåøåíèè äàííîé ÑËÀÓ ñîñòîèò â òîì,÷òî çíà÷åíèå ν íåèçâåñòíî.Ðåøàòåëè ÑËÀÓ äëÿ êëþ÷åâîãî óðàâíåíèÿ íàçûâàþòñÿäåêîäåðàìè.Ðàññìîòðèì äâà íàèáîëåå ïðîñòûõ èç íèõ.104 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÊîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÄåêîäèðîâàíèå êîäîâ Á×ÕÊîäû Á×Õ: äåêîäèðîâàíèå...1. Äåêîäåð PGZ (Peterson-Gorenstein-Zierler) ñîñòîèò â ïîñëåäîâàòåëüíîì ðåøåíèè ðàññìàòðèâàåìîé ÑËÀÓäëÿ ν = r, r − 1, . . . äî òåõ ïîð, ïîêà ìàòðèöà î÷åðåäíîéÑËÀÓ íå îêàæåòñÿ íåâûðîæäåííîé (ïðè ïåðåõîäå îò r ê r − 1ïîëàãàåì σr = 0).2.
Äåêîäåð íà áàçå ðàñøèðåííîãî àëãîðèòìà ÅâêëèäàÄëÿ íàõîæäåíèÿ ïîëèíîìà ëîêàòîðîâ îøèáîê σ(x) è åãîêîðíåé ââåä¼ì âñïîìîãàòåëüíûé ñèíäðîìíûé ïîëèíîìs(x) = 1 + s1 x + s2 x2 + . . . + s2r x2r ,ãäå si = w(αi ), i = 1, . . . , 2r ñèíäðîìû.Äëÿ ïðîäâèíóòûõ: ýòî òîæå ïðîèçâîäÿùèé ïîëèíîì.105 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÊîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÄåêîäèðîâàíèå êîäîâ Á×ÕÊîäû Á×Õ: äåêîäèðîâàíèå...Ïåðåìíîæèì ïîëèíîìû ñèíäðîìíûé è ëîêàòîðîâ îøèáîê:λ(x) = s(x)σ(x) = 1 + λ1 x + λ2 x2 + .
. . + λ2r+ν x2r+ν .Çäåñü êîýôôèöèåíòû λj =jXsi σj−i îïðåäåëÿþòñÿi=0ñîîòíîøåíèåì äëÿ ïðîèçâåäåíèÿ ìíîãî÷ëåíîâ.Ïîñêîëüêó σ0 = 1, ÑËÀÓ ýêâèâàëåíòíà óñëîâèþλν+1 = λν+2 = . . . = λ2r = 0, ò.å.λ(x) = 1 + λ1 x + λ2 x2 + . . . + λν xν ++ λ2r+1 x2r+1 + .
. . + λ2r+ν x2r+ν .Ðàññìîòðèì îñòàòîê îò äåëåíèÿ λ(x) íà x2r+1 . ßñíî, ÷òîλ(x) ≡x2r+1 1 + λ1 x + · · · + λν xν .106 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè107 / 152Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÄåêîäèðîâàíèå êîäîâ Á×ÕÊîäû Á×Õ: äåêîäèðîâàíèå...Òàêèì îáðàçîì, íåêîòîðûé ìíîãî÷ëåí λ(x) è ïîëèíîìëîêàòîðîâ îøèáîê σ(x) óäîâëåòâîðÿþò êëþ÷åâîìó óðàâíåíèþs(x)σ(x) + x2r+1 a(x) = λ(x)(íàïîìèíàíèå: ðàáîòàåì â ïîëå(∗)Fq2 ∼= F2 [x]/(a(x)) ).Îòíîñèòåëüíî σ(x) äàííîå óðàâíåíèå ìîæåò áûòü ðåøåíî ñïîìîùüþ ðàñøèðåííîãî àëãîðèòìàÅâêëèäà äëÿ ïàðû2r+1ìíîãî÷ëåíîâ x, s(x) ñî ñâîéñòâàìè:óñëîâèå îñòàíîâêè ñòåïåíü î÷åðåäíîãî îñòàòêà 6 r;êîëè÷åñòâî ôàêòè÷åñêè ñîâåðøåííûõ îøèáîê ν = deg σ(x).Çàìå÷àíèå: íàèáîëåå ýôôåêòèâíûì äåêîäåðîì äëÿ (íåñëèøêîì äëèííûõ) êîäîâ Á×Õ ÿâëÿåòñÿ äåêîäåðÁåðëåêýìïà-Ìýññè.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè108 / 152Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÄåêîäèðîâàíèå êîäîâ Á×ÕÝ. Áåðëåêýìï è Ä. ÌýññèÝëâèí Ðàëüô Áåðëåêýìï(Elwyn Ralph Berlekamp, 1940) àìåðèêàíñêèé ìàòåìàòèê,âíåñøèé ñóùåñòâåííûé âêëàä â òåîðèèêîäèðîâàíèÿ è êîìáèíàòîðíûõ èãð (èãðà Ãî).Ïîìèìî ìàòåìàòèêè,çàíèìàëñÿ èíâåñòèöèîííûì ìåíåäæìåíòîì.Äæåéìñ Ëè Ìýññè(James Lee Massey, 19342013) âûäàþùèéñÿ àìåðèêàíñêèé ó÷åíûé,âíåñøèé çíà÷èòåëüíûé âêëàä âòåîðèþ èíôîðìàöèè è êðèïòîãðàôèþ. ÷àñòíîñòè, ðàçðàáîòàë (â ñîàâòîðñòâå)øèôðû SAFER è IDEA.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÊîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÄåêîäèðîâàíèå êîäîâ Á×ÕÊîäû Á×Õ: îáùàÿ ñõåìà äåêîäèðîâàíèÿÏóñòü ïðèíÿòî ñëîâî w(x) ñîîáùåíèå, çàêîäèðîâàííîå(n, k, d)-êîäîì Á×Õ è, âîçìîæíî, ñîäåðæàùåå îøèáêè, à α ãåíåðàòîð ìóëèòèïëèêàòèâíîé ãðóïïû ïîëÿ, ïîðîæä¼ííîãîêîäèðóþùèì ïîëèíîìîì.1Äëÿ ñëîâà w(x) íàéòè âñå ñèíäðîìû si = w(αi ), i = 1, d − 1.2Íàéòè ïîëèíîì ëîêàòîðîâ îøèáîê σ(x), èñïîëüçóÿ òîò èëèèíîé äåêîäåð.3Íàéòè âñå êîðíè σ(x) ïîëíûì ïåðåáîðîì âñåõ ýëåìåíòîâïîëÿ Fq2 (èõ 2q − 1 = n, ò.å.
àëãîðèòì ëèíåéíûé ïî n, ÷åãîè äîáèâàëèñü!); ïóñòü íàéäåííûå êîðíè ñóòü αk1 , . . . , αkν .4Íàéòè ïîçèöèè îøèáîê ji ≡n −ki , i = 1, ν .5Èñïðàâèòü îøèáêè, ïîëó÷èâ ñëîâîvb(x) = w(x) + xj1 + . . . + xjν .6Íàéòè âñå çíà÷åíèÿ vb(αi ), i = 1, d − 1; åñëè íå âñå îíèðàâíû íóëþ, òî âûäàòü îòêàç îò äåêîäèðîâàíèÿ.109 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÊîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÄåêîäèðîâàíèå êîäîâ Á×ÕÊîäû Á×Õ: ïðèìåð äåêîäèðîâàíèÿÏóñòü Á×Õ (15, 5, 7)-êîä (ò.å.
r = 3) ïîñòðîåí â ïîëåF42 ∼= F2 [x]/ x4 + x + 1 .Ïóñòü ïåðåäà¼òñÿ ñîîáùåíèå [01101]T ↔ u(x) = x4 + x2 + x.Ïðè ñèñòåìàòè÷åñêîì êîäèðîâàíèè (îïóñòèì ýòîò ýòàï) êîäîâîåñëîâî åñòüv(x) = x14 + x12 + x11 + x8 + x4 + x3 + x2 + x ↔↔ [011110001001101]T(óáåæäàåìñÿ, ÷òî áèòû ñîîáùåíèÿ íàõîäÿòñÿ â êðàéíå ïðàâûõïîçèöèÿõ êîäîâîãî ñëîâà).Ïóñòü îøèáêè ïðîèçîøëè â 0-é, 6-é è 12-é ïîçèöèÿõ, ò.å.ïðèíÿòîå ñëîâî w(x) = x14 + x11 + x8 + x6 + x4 + x3 + x2 + x + 1 ↔↔ [íàïèøèòå ñàìè! ]T .110 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè111 / 152Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÄåêîäèðîâàíèå êîäîâ Á×ÕÊîäû Á×Õ: ïðèìåð äåêîäèðîâàíèÿ...
F = F2 [x]/ x4 + x + 1Íåíóëåâûå ýëåìåíòû ïîëÿ F êàê ñòåïåíè ãåíåðàòîðà α:α1α2α3α4α5α6α7α8α9α10α11α12α13α14α15αα2α3α+1α2 + αα3 + α2α3 + α + 1α2 + 1α3 + αα2 + α + 1α3 + α2 + αα3 + α2 + α + 1α3 + α2 + 1α3 + 11ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÊîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÄåêîäèðîâàíèå êîäîâ Á×ÕÊîäû Á×Õ: ïðèìåð äåêîäèðîâàíèÿ... α4 = α + 11. Íàéä¼ì 2r = 6 ñèíäðîìîâ äëÿ ïðèíÿòîãî ñëîâà:s1 = w(α) == α3 + 1 + α3 + α2 + α + α2 + 1 + α3 + α2 + α + 1 + α3 ++ α2 + α + 1 = α,s2 = w(α2 ) = (w(α))2 = α2 ,s3 = w(α3 ) = α42 + α33 + α24 + α18 + α12 + α9 + α6 + α3 + 1 = .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
