Коды, исправляющие ошибки (1127158), страница 9
Текст из файла (страница 9)
×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè129 / 152Çàäà÷è ñ ðåøåíèÿìèÇàäà÷à ÒÊ-3Ðàññìîòðèì êîä Õýììèíãà ñèñòåìàòè÷åñêîãî êîäèðîâàíèÿñïîðîæäàþùèì ïîëèíîìîì α ∈ F2 [x]/ x3 + x + 1 .Òðåáóåòñÿ äåêîäèðîâàòü ïîëó÷åííûå ïîëèíîìû123w1 (x) = x6 + x2 + x,w2 (x) = x6 + x5 + x3 + x2 + x,w3 (x) = x6 + x3 + x2 + x.Ðåøåíèå Î÷åâèäíî, èìååì (7, 4, 3)-êîä Õýììèíãà, â êîòîðîìñîîáùåíèå åñòü êîýôôèöèåíòû ïåðåä ñòåïåíÿìè 3, . .
. , 6ôîðìàëüíîé ïåðåìåííîé x êîäîâîãî ïîëèíîìà.Äëÿ äåêîäèðîâàíèÿ íåîáõîäèìî âû÷èñëèòü ñèíäðîì s = w(α)ïðèíÿòîãî ñëîâà. Åñëè s = 0, òî ñ÷èòàåì, ÷òî îøèáîê ïðèïåðåäà÷å íå ïðîèçîøëî; èíà÷å íåîáõîäèìî íàéòè òàêîå k , ÷òîαk = s è ïåðåä âîññòàíîâëåíèåì ñîîáùåíèÿ èíâåðòèðîâàòü k -éðàçðÿä w(α) (÷òî, î÷åâèäíî, èìååò ñìûñë ïðè k ∈ {3, . . . , 6}).ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÇàäà÷è ñ ðåøåíèÿìèÇàäà÷à ÒÊ-3...
( α3 = α + 1)¶ w1 (x) = x6 + x2 + x ↔ [0110001]s = α6 + α2 + α = (α3 )2 + α2 + α == (α + 1)2 + α2 + α = α2 + 1 + α2 + α = α + 1 6= 0.Î÷åâèäíî, α + 1 = α3 , ò.å. k = 3, îøèáêà ïðîèçîøëà â 3-ìðàçðÿäå è vb(x) = w(x) + e(x) = x6 + x3 + x2 + x ↔ [0111001],u(x) ↔ [1001].· w2 (x) = x6 + x5 + x3 + x2 + x ↔ [0111011]s = α6 +α5 +α3 +α2 +α = (α+1)2 +(α+1)α2 +α+1+α2 +α == α2 + 1 + α3 + α2 + α2 + 1 = α3 + α2 = α2 + α + 1 6= 0.Î÷åâèäíî, α3 + α2 = (α + 1)α2 = α5 , ò.å. k = 5, îøèáêàïðîèçîøëà â 5-ì ðàçðÿäå è ñíîâà u(x) ↔ [1001].¸ w3 (x) = x6 + x3 + x2 + x ↔ [0111001].
Óáåæäàåìñÿ, ÷òî âýòîì ñëó÷àå s = 0, ò.å. îøèáîê íå ïðîèçîøëî è u(x) ↔ [1001]130 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè131 / 152Çàäà÷è ñ ðåøåíèÿìèÇàäà÷à ÒÊ-3... ( α3 = α + 1)Çàìåòå÷àíèå. Äåêîäèðîâàíèå ñèñòåìàòè÷åñêîãî êîäàÕýììèíãà ìîæíî îñóùåñòâèòü äåëåíèåì ïðèíÿòîãî ïîëèíîìàíà ïîðîæäàþùèé: îñòàòîê îò äåëåíèÿ åñòü ñèíäðîì s:w(x) = q(x) · g(x) + r(x),r(x) = s. íàøåì ñëó÷àå:1x6 + x2 + x = (x3 + x + 1)2 + x + 1;2x6 + x5 + x3 + x2 + x == (x3 + x2 + x + 1)(x3 + x + 1) + x2 + x + 1;3x6 + x3 + x2 + x = (x3 + x)(x3 + x + 1) + 0.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè132 / 152Çàäà÷è ñ ðåøåíèÿìèÇàäà÷à ÒÊ-4Äëÿ êîäà Á×Õ ñ íóëÿìè α, α2 , α3 è α4 , ãäå α ïðèìèòèâíûéýëåìåíò ïîëÿ F = F2 [x]/ x4 + x + 1 è ïðèíÿòîãî ñëîâàw(x) = x14 + x10 + x5 + x4 .íàéòè ïîëèíîì ëîêàòîðîâ îøèáîê σ(x).ÐåøåíèåÄëÿ óäîáñòâà âû÷èñëåíèé â ïîëå F ïîñòðîèì òàáëèöóñîîòâåòñòâèé ìåæäó ñòåïåííûì è ïîëèíîìèàëüíûìïðåäñòàâëåíèåì ýëåìåíòîâ ïîëÿ.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÇàäà÷è ñ ðåøåíèÿìèÇàäà÷à ÒÊ-4...α4 = α + 1α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 + 11133 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÇàäà÷è ñ ðåøåíèÿìèÇàäà÷à ÒÊ-4... α4 = α + 1, w(x) = x14 + x10 + x5 + x4Ñ ïîìîùüþ ýòîé òàáëèöû âû÷èñëèì ñèíäðîìû:s1 = w(α) = α14 + α10 + α5 + α4 == (α3 + 1) + (α2 + α + 1) + (α2 + α) + (α + 1) == α3 + α + 1 = α7 ,s2 = w(α2 ) = (w(α))2 = α14 ,s3 = w(α3 ) = α12 + 1 + 1 + α12 = 0,2s4 = w(α4 ) = w(α2 ) = α28 = α13 .Ñèíäðîìíûé ïîëèíîì s(x) = α13 x4 + α14 x2 + α7 x + 1.Ñèíäðîìîâ âñåãî ÷åòûðå, ñëåäîâàòåëüíî, r = 2.Ïîëèíîì ëîêàòîðîâ îøèáîê σ(x) ÿâëÿåòñÿ ðåøåíèåìóðàâíåíèÿx2r+1 a(x) + s(x)σ(x) = λ(x), deg λ(x) 6 r.134 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè135 / 152Çàäà÷è ñ ðåøåíèÿìèÇàäà÷à ÒÊ-4... x2r+1 a(x) + s(x)σ(x) = λ(x), deg λ(x) 6 2Ðåøàåì ñ ïîìîùüþ ðàñøèðåííîãî àëãîðèòìà Åâêëèäà:Øàã 0. r−2 (x) = x5 ,// Èíèöèàëèçàöèÿ134r−1 (x) = α x + α14 x2 + α7 x + 1,y−2 (x) = 0,y−1 (x) = 1.Øàã 1. r−2 (x) = r−1 (x)q0 (x) + r0 (x),// Äåëèì r−2 (x) íà r−1 (x) ñ îñòàòêîìq0 (x) = α2 x,r0 (x) = αx3 + α9 x2 + α2 x,y0 (x) = y−2 (x) − y−1 (x)q0 (x) = −q0 (x) = α2 x.Øàã 2.
r−1 (x) = r0 (x)q1 (x) + r1 (x),// Äåëèì r−1 (x) íà r0 (x) ñ îñòàòêîìq1 (x) = α12 x + α5 ,r1 (x) = α14 x2 + 1 deg r1 (x) = 2 6 r,y1 (x) = y−1 (x) − y0 (x)q1 (x) =ïîëèíîì ëîêàòîðîâ îøèáîê}|{z= 1 + α2 x(α12 x + α5 ) = α14 x2 + α7 x + 1 = σ(x).ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè136 / 152Çàäà÷è ñ ðåøåíèÿìèÇàäà÷à ÒÊ-5Ðàññìîòðèì êîä Á×Õ, íóëè êîòîðîãî îïðåäåëÿþòñÿ ñòåïåíÿìèα, ãäå α ïðèìèòèâíûé ýëåìåíò ïîëÿ F2 [x]/ x4 + x + 1 .Ïóñòü äëÿ íåêîòîðîãî ïðèíÿòîãî ñëîâà w(x) ïîëèíîìëîêàòîðîâ îøèáîê åñòü σ(x) = α2 x2 + α6 x + 1.Òðåáóåòñÿ îïðåäåëèòü ïîçèöèè îøèáîê â w(x).ÐåøåíèåÍàéä¼ì êîðíè ïîëèíîìà ëîêàòîðîâ îøèáîê ïîëíûì ïåðåáîðîì.Äëÿ âû÷èñëåíèé óäîáíî ïîëüçîâàòüñÿ òàáëèöåé ñîîòâåòñòâèéìåæäó ñòåïåííûì è ïîëèíîìèàëüíûì ïðåäñòàâëåíèåìýëåìåíòîâ ïîëÿ, âû÷èñëåííîé â ïðåäûäóùåé çàäà÷å ÒÊ-4.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÇàäà÷è ñ ðåøåíèÿìèÇàäà÷à ÒÊ-5...α4 = α + 1, α15 = 1σ(x) = α2 x2 + α6 x + 1σ(α) = α4 + α7 + 1 = α3 ,σ(α2 ) = α6 + α8 + 1 = α3 ,σ(α3 ) = α8 + α9 + 1 = α3 + α2 + α,σ(α4 ) = α10 + α10 + 1 = 1,σ(α5 ) = α12 + α11 + 1 = 0,σ(α6 ) = α14 + α12 + 1 = α2 + α + 1,σ(α7 ) = α16 + α13 + 1 = α3 + α2 + 1,σ(α8 ) = α18 + α14 + 1 = 0.Äàëüøå ìîæíî íå âû÷èñëÿòü: îáà êîðíÿ êâàäðàòíîãî ïîëèíîìàσ(x) íàéäåíû.137 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÇàäà÷è ñ ðåøåíèÿìèÇàäà÷à ÒÊ-5...α15 = 1Èòàê, ïîëèíîì ëîêàòîðîâ îøèáîêσ(x) = α2 x2 + α6 x + 1.èìååò êîðíè α5 è α8 .Îïðåäåëÿåì ïîçèöèè îøèáîê:−5 ≡15 10,−8 ≡15 7,(è ïîëèíîì îøèáîê åñòü e(x) = x10 + x7 ).138 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè139 / 152Çàäà÷è ñ ðåøåíèÿìèÇàäà÷à ÒÊ-6Ïîñòðîèòü Á×Õ-êîä äëèíû 15, èñïðàâëÿþùèé íå ìåíåå 2-õîøèáîê.ÐåøåíèåÈìååì q = 4, n = 24 − 1 = 15 è d = 2r + 1 = 5.Îáðàçóåì ïîëå F = F42 ∼= F2 [x]/(a(x)), âçÿâ â êà÷åñòâå a(x)íåïðèâîäèìûé ïîëèíîì 4-é ñòåïåíè x4 + x + 1 (ïðèâîäèìáîëåå ïîäðîáíîå ðåøåíèå ïðèìåðà 1, âàð.
4 ðàçäåëàÊîäèðîâàíèå Á×Õ-êîäàìè).Ïîëèíîì a(x) ïðèìèòèâåí, ò.å. ÿâëÿåòñÿ ì.ì. äëÿ α = x ãåíåðàòîðà ìóëüòèïëèêàòèâíîé ãðóïïû F ∗ .Íàõîäèì öèêëîòîìè÷åñêèå êëàññû äëÿ ýëåìåíòîâ α, α2 , α3 , α4ïîëÿ F , ó÷èòûâàÿ, ÷òî α4 = α + 1, α15 = 1, α16 = α, α24 = α3 :α, α2 , α4 , α8 è α3 , α6 , α9 , α12 ,òàê ÷òî äëÿ ïîðîæäàþùåãî ìíîãî÷ëåíà g(x) êîíñòðóèðóåìîãîÁ×Õ-êîäà áóäåì èìåòüg(x) = gα (x) · gα3 (x).ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÇàäà÷è ñ ðåøåíèÿìèÇàäà÷à ÒÊ-6... α4 = α + 1, α15 = 1ßñíî, ÷òî gα (x) = a(x) = x4 + x + 1.Âû÷èñëèì ýëåìåíòû öèêëîòîìè÷åñêîãî êëàññà, â êîòîðûéâõîäèò α3 :α6 = α4 α2 = (α + 1)α2 = α3 + α2 ,2α9 = α4 α = (α + 1)2 α = (α2 + 1)α = α3 + α,3α12 = α4 = (α + 1)3 = α3 + α2 + α + 1.Âû÷èñëèì ì.ì.
äëÿ öèêëîòîìè÷åñêîãî êëàññà ýëåìåíòà α3 :gα3 (x) = (x + α3 ) · (x + α6 ) · (x + α9 ) · (x + α12 ) =::::::::::::::= x2 + (α3 + α12 )x + α15 · x2 + (α6 + α9 )x + α15 =:::::::::::::::::::::::= x2 + (α2 + α + 1)x + 1 · x2 + (α2 + α)x + 1 == x4 + x3 + x2 + x + 1.140 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè141 / 152Çàäà÷è ñ ðåøåíèÿìèÇàäà÷à ÒÊ-6... α4 = α + 1, α15 = 1Òàêèì îáðàçîì,g(x) = gα (x)·gα3 (x) = x4 + x + 1 · x4 + x3 + x2 + x + 1 == x8 + x7 + x6 + x4 + 1,deg g(x) = m = 8, k = 15 − 8 = 7,è ïîëó÷åí ïîðîæäàþùèé ïîëèíîì äëÿ (15, 7, 5)-êîäà Á×Õ.Çàìå÷àíèå.
Ðàíåå áûëî óñòàíîâëåíî, ÷òî èìååòñÿ âñåãî 3íåïðèâîäèìûõ ìíîãî÷ëåíà 4-ãî ïîðÿäêà.Îäèí èç íèõ âûáðàí â êà÷åñòâå a(x) = gα (x) è ïîýòîìó ì.ì.äëÿ α3 ìîæåò áûòü îäèí èç äâóõ îñòàëüíûõ: x4 + x3 + 1 èëèx4 + x3 + x2 + x + 1.Óáåæäàåìñÿ, ÷òî ïîäñòàíîâêà x 7→ α3 îáðàùàåò ïåðâûé âα2 + 1, à âòîðîé â 0, è ïîýòîìó îí è åñòü gα3 (x).ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè142 / 152Çàäà÷è ñ ðåøåíèÿìèÇàäà÷à ÒÊ-7Ïîñòðîèòü 15-ðàçðÿäíûé Á×Õ-êîä äëÿ èñïðàâëåíèÿ íå ìåíåå 3îøèáîê.ÐåøåíèåÈìååì n = 15 = 24 − 1, r = 3, d = 7.Ïîðîæäàþùèé ìíîãî÷ëåí g(x) êîíñòðóèðóåìîãî êîäà äîëæåíèìåòü êîðíè α, α2 , α3 , α4 , α5 , α6 , ãäå α ïðèìèòèâíûéýëåìåíò ïîëÿ F = F42 .Ïðè ðàçáèåíèè F ∗ íà öèêëîòîìè÷åñêèå êëàññûâñåãäà áóäåòïðèñóòñòâîâàòü ÷åòûð¼õýëåìåíòíûé êëàññ α, α2 , α4 , α8 .Îñòàëüíûå ðàññìàòðèâàåìûå ñòåïåíè α áóäóò âõîäèòü âöèêëîòîìè÷åñêèå êëàññû 3 6α , α , . .
. è α5 , . . . .ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÇàäà÷è ñ ðåøåíèÿìèÇàäà÷à ÒÊ-7...Íåòðóäíî óñòàíîâèòü, ÷òî ýòî 4- è 2-ýëåìåíòíûå êëàññûñîîòâåòñòâåííî: 3 6 12 24α , α , α , α = α9 , ò.ê. 2 · 9 = 18 ≡15 3 è α18 = α3 ; 5 10 α ,α, ò.ê. 2 · 10 = 20 ≡15 = 5 è α20 = α5 .Ðàíåå áûëè íàéäåíû íåïðèâîäèìûå ìíîãî÷ëåíû ÷åòâ¼ðòîéñòåïåíè íàä F2 :¶ x4 + x + 1,¸ x4 + x3 + x2 + x + 1,· x4 + x3 + 1,Ïåðâûå äâà ìíîãî÷ëåíà ïðèìèòèâíûå (èõ êîðåíü α áóäåòãåíåðàòîðîì ìóëüòèïëèêàòèâíîé ãðóïïû ñîîòâåòñòâóþùåãîïîëÿ).143 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè144 / 152Çàäà÷è ñ ðåøåíèÿìèÇàäà÷à ÒÊ-7...Ñ äðóãîé ñòîðîíû, ìíîãî÷ëåí 3 íå ïðèìèòèâíûé, ò.ê. ïîðÿäîêåãî êîðíÿ α ðàâåí 5: ïðè óñëîâèè α4 = α3 + α2 + α + 1 èìååìα5 = αα4 = α(α3 + α2 + α + 1) = α4 + α3 + α2 + α ==α6 3+ α6 2+ α6 + 1+ α6 3+ α6 2+ α6 = 1.Ýòî îçíà÷àåò, â êà÷åñòâå ïîðîæäàþùåãî ïîëå ïîëèíîìà a(x)ìîãóò áûòü âûáðàí òîëüêî êàêîé-ëèáî èç ïåðâûõ äâóõìíîãî÷ëåíîâ.Ïîëîæèì a(x) = x4 + x3 + 1 (ìíîãî÷ëåí 2) è òîãäàgα (x) = a(x), α4 = α3 + 1, α15 = 1.Äàëåå, ñðàçó ÿñíî, ÷òî ì.ì. äëÿ ýëåìåíòà α5 (è α10 ) áóäåòíåïðèâîäèìûé ïîëèíîì 2-é ñòåïåíè (îí åäèíñòâåííûé):gα5 (x) = x2 + x + 1.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè145 / 152Çàäà÷è ñ ðåøåíèÿìèÇàäà÷à ÒÊ-7...
( α4 = α3 + 1, α15 = 1)Îñòàëîñü îïðåäåëèòü ì.ì. äëÿ α3 (è âñåãî åãî 4-ýëåìåíòíîãîöèêëîòîìè÷åñêîãî êëàññà) èì äîëæåí áûòü ëèáî ìíîãî÷ëåí1, ëèáî ìíîãî÷ëåí 3.Ïîäñòàíîâêà â ìíîãî÷ëåí 1 äà¼ò(x4 + x + 1)x=α3 = α12 + α3 + 1 = (α3 + 1)3 + α3 + 1 == (α3 + 1) (α3 + 1)2 + 1 = α4 (α6 + 6 1+ 6 1) = α10 6= 0.Ïîýòîìó (ìîæíî è íå ïðîâåðÿòü) ì.ì. ýëåìåíòà α3 áóäåòîñòàâøèéñÿ ìíîãî÷ëåí 3 èg(x) = gα (x) · gα3 (x) · gα5 (x) == (x4 + x3 + 1)(x4 + x3 + x2 + x + 1)(x2 + x + 1) == x10 + x8 + x5 + x4 + x2 + x + 1,m = 10, k = 5. ðåçóëüòàòå ïîñòðîåí Á×Õ (15, 5, 7)-êîä, óæå ïîëó÷åííûéðàíåå â ðàçäåëå Êîäèðîâàíèå Á×Õ-êîäàìè.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè146 / 152Çàäà÷è ñ ðåøåíèÿìèÇàäà÷à ÒÊ-8Ïîñòðîèòü 31-ðàçðÿäíûé Á×Õ-êîä äëÿ èñïðàâëåíèÿ íå ìåíåå 3îøèáîê.ÐåøåíèåÈìååì n = 31 = 25 − 1, r = 3, d = 7.Ïîðîæäàþùèé ìíîãî÷ëåí g(x) êîíñòðóèðóåìîãî êîäà äîëæåíèìåòü êîðíè α, α2 , α3 , α4 , α5 , α6 , ãäå α ïðèìèòèâíûéýëåìåíò ïîëÿ F = F52 .Ïðè ðàçáèåíèè F ∗ íà öèêëîòîìè÷åñêèåêëàññû âñåãäà áóäåòïðèñóòñòâîâàòü ïÿòèýëåìåíòíûé êëàññ α, α2 , α4 , α8 , α16 .Îñòàëüíûå ðàññìàòðèâàåìûå ñòåïåíè α áóäóò âõîäèòü âöèêëîòîìè÷åñêèå êëàññû 3 6α , α , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
