Коды, исправляющие ошибки (1127158), страница 6
Текст из файла (страница 6)
×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè82 / 152Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÎïðåäåëåíèå è îñíîâíûå ñâîéñòâàÑâîéñòâà öèêëîòîìè÷åñêèõ êëàññîâ...Åñëè α ∈ FN2 è m ìîùíîñòü íåêîòîðîãî åãîöèêëîòîìè÷åñêîãî êëàññà íàä ïîäïîëåì Fn2 , òî ïîëèíîìmα (x) =m−1Yix + α2= xm−1 + λm−2 xm−2 + . . . + λ1 x + λ0i=0ÿâëÿåòñÿ ì.ì. α, à òàêæå äëÿ âñåõ ýëåìåíòîâ, âõîäÿùèõ âäàííûé öèêëîòîìè÷åñêèé êëàññ.Îòñþäà âûâîäèòñÿ ìåòîä ïîñòðîåíèÿ ì.ì. äëÿ äàííîãîýëåìåíòà ïîëÿ α:1îïðåäåëèòü ÷èñëî m ýëåìåíòîâ öèêëîòîìè÷åñêîãî êëàññàýëåìåíòà α;2íàéòè êîýôôèöèåíòû ïîëèíîìà mα (x) ïóòåìi2ïåðåìíîæåíèÿ ñêîáîê x + αäëÿ âñåõ i = 0, m − 1.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè83 / 152Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÎïðåäåëåíèå è îñíîâíûå ñâîéñòâàÑïåöèàëüíûå öèêëè÷åñêèå êîäûÅñëè äëèíà öèêëè÷åñêîãî êîäà n = 2q − 1, òî:1êîðíÿìè ìíîãî÷ëåíà xn + 1 ÿâëÿþòñÿ âñå íåíóëåâûåýëåìåíòû ïîëÿ Fq2 ;2ïîðîæäàþùèìè ìíîãî÷ëåíàìè öèêëè÷åñêîãî êîäà ìîãóòáûòü òîëüêî ïðîèçâåäåíèÿ ìèíèìàëüíûõ ìíîãî÷ëåíîâ äëÿíåêîòîðûõ ñîâîêóïíîñòåé ýëåìåíòîâ Fq2 .Òàêèå êîäû:1ÿâëÿþòñÿ ïîäìíîæåñòâîì öèêëè÷åñêèõ êîäîâ, èìåþùèìóêàçàííóþ óäîáíóþ ñâÿçü ìåæäó ïîðîæäàþùèìïîëèíîìîì è ýëåìåíòàìè èç Fq2 ;2óæå íå ìîãóò èìåòü ïðîèçâîëüíûå äëèíû (åñòü ñïîñîáîáîéòè ýòî îãðàíè÷åíèå èñïîëüçîâàíèå ò.í.
óêîðî÷åííûõêîäîâ Á×Õ, êîòîðûå ìû íå ðàññìàòðèâàåì).ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÊîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÎïðåäåëåíèå è îñíîâíûå ñâîéñòâàÁ×Õ-êîäû: îïðåäåëåíèå (ïðîñòåéøèé ñëó÷àé)Ïóñòü âûáðàíû ïàðàìåòðû: q , îïðåäåëÿþùèé äëèíó êîäàn = 2q − 1 è êîíñòðóêòèâíîå ðàññòîÿíèå d 6 n.Êîä Á×Õ åñòü öèêëè÷åñêèé (n, k)-êîä, â êîòîðîì ïîðîæäàþùèéìíîãî÷ëåí g(x) èìååò êîðíÿìè ýëåìåíòû α, α2 , α3 , .
. . , αd−1ïîëÿ F = Fq2 (íàçûâàåìûå íóëÿìè Á×Õ-êîäà) è ãäåα ãåíåðàòîð ìóëüòèïëèêàòèâíîé ãðóïïû F ∗ ,deg g(x) = m ÷èñëî ïðîâåðî÷íûõ áèò,k = n − m ÷èñëî èíôîðìàöèîííûõ áèò.Ïðè ýòîì:g(x) âûáèðàþò êàê ÍÎÊ ïîëèíîìîâ (÷àñòî ýòî ïðîñòî èõïðîèçâåäåíèå), ÿâëÿþùèõñÿ ìèíèìàëüíûìè ìíîãî÷ëåíàìèäëÿ âñåõ íóëåé êîäà, ïîïàâøèõ â äàííûé öèêëîòîìè÷åñêèéêëàññ;êîäîâîå ðàññòîÿíèå ïîñòðîåííîãî êîäà îêàçûâàåòñÿ íåìåíåå âûáðàííîãî êîíñòðóêòèâíîãî ðàññòîÿíèÿ d.84 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÊîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÎïðåäåëåíèå è îñíîâíûå ñâîéñòâàÁ×Õ-êîä: êîäîâîå ðàññòîÿíèå íå ìåíåå êîíñòðóêòèâíîãîÒåîðåìàÏóñòü Á×Õ-êîä äëèíîé n = 2q − 1 ñ êîíñòðóêòèâíûìðàññòîÿíèåì d çàäà¼òñÿ êîäèðóþùèì ìíîãî÷ëåíîìg(x) = HOK ( m1 (x), . . .
, md−1 (x) ),ãäå mi (x), i = 1, d − 1 ìèíèìàëüíûå ìíîãî÷ëåíû íóëåéα, α2 , . . . , αd−1 êîäà.Òîãäà êîäîâîå ðàññòîÿíèå äàííîãî Á×Õ-êîäà íå ìåíåå d.ÄîêàçàòåëüñòâîÏîêàæåì, ÷òî ìíîãî÷ëåí h(x) ñ êîðíÿìè α, α2 , . . . , αd−1èìååò íå ìåíåå d íåíóëåâûõ ýëåìåíòîâ.Ïðåäïîëîæèì ïðîòèâíîå. Òîãäà h(x) ìîæíî çàïèñàòü â âèäåh(x) = b1 xn1 + b2 xn2 + . . . + bd−1 xnd−1 .85 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè86 / 152Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÎïðåäåëåíèå è îñíîâíûå ñâîéñòâàÁ×Õ-êîä: êîäîâîå ðàññòîÿíèå íå ìåíåå êîíñòðóêòèâíîãî...Äîêàçàòåëüñòâî (ïðîäîëæåíèå)Ïîñêîëüêó α, α2 , . .
. , αd−1 êîðíè h(x), åãî êîýôôèöèåíòûb1 , . . . , bd−1 äîëæíû óäîâëåòâîðÿòü ëèíåéíîé ñèñòåìån1+ . . . + bd−1 αnd−1= 0 b1 α2n2n1d−1b1 α+ . . . + bd−1 α= 0..................(d−1)n(d−1)n1d−1b1 α+ . . . + bd−1 α= 0Ìàòðèöà A ñèñòåìû íåâûðîæäåíà, ò.ê. å¼ îïðåäåëèòåëüÂàíäåðìîíäà îòëè÷åí îò íóëÿ:Y|A| =( αni − αnj ) 6= 0, nj < ni < 2q .i>jÑëåäîâàòåëüíî, b1 = . . . = bd−1 = 0 ïðîòèâîðå÷èå.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè87 / 152Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÎïðåäåëåíèå è îñíîâíûå ñâîéñòâàÊîäû Á×Õ: ñèíäðîìûÏîñêîëüêó âñå êîäîâûå ñëîâà öèêëè÷åñêîãî êîäà C äåëÿòñÿ íàïîëèíîì g(x) ñ êîðíÿìè α, α2 , . . .
, αd−1 , òîv(x) ∈ C ⇔ v(αi ) = 0, i = 1, d − 1.ÎïðåäåëåíèåÑèíäðîìàìè ïðèíÿòîãî ïîëèíîìà w(x), çàêîäèðîâàííîãîÁ×Õ-êîäîì ñ íóëÿìè αi , i = 1, d − 1 è, âîçìîæíî, ñîäåðæàùåãîîøèáêè, íàçîâ¼ì çíà÷åíèÿ w(x) â íóëÿõ êîäà: si = w(αi ).ßñíî, ÷òî¾âñå ñèíäðîìû ðàâíû íóëþ¿ ⇔ w(x) êîäîâîå ñëîâî.Îïðåäåëåíèå ñèíäðîìà äëÿ Á×Õ-êîäà, î÷åâèäíî, åñòüïåðåôðàçèðîâêà â òåðìèíàõ íóëåé êîäà ïîëèíîìîâ ñèíäðîìàäëÿ öèêëè÷åñêîãî êîäà.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÊîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÊîäèðîâàíèå Á×Õ-êîäàìèÐàçäåëû12Áëîêîâîå êîäèðîâàíèå. Êîäû ÕýììèíãàÃðóïïîâûå (ëèíåéíûå) êîäûÎïðåäåëåíèå è ñâîéñòâàÊîäèðîâàíèå ëèíåéíûìè êîäàìèÄåêîäèðîâàíèå ëèíåéíûõ êîäîâ3Öèêëè÷åñêèå êîäûÎïðåäåëåíèå, îñíîâíûå ñâîéñòâà, ïðèìåðÊîäèðîâàíèå öèêëè÷åñêèìè êîäàìè è äåêîäèðîâàíèå4Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÎïðåäåëåíèå è îñíîâíûå ñâîéñòâàÊîäèðîâàíèå Á×Õ-êîäàìèÄåêîäèðîâàíèå êîäîâ Á×Õ5Çàäà÷è ñ ðåøåíèÿìè88 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè89 / 152Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÊîäèðîâàíèå Á×Õ-êîäàìèÏîñòðîåíèÿ êîäîâ Á×Õ äëÿ q = 3, n = 7, a(x) = x3 + x + 1Ïóñòü q = 3, ò.å.
ñòðîèì Á×Õ-êîäû äëÿ ïîëÿ F = F32 è n = 7. êà÷åñòâå ïîðîæäàþùåãî ïîëå F = F2 [x]/(a(x)) ìíîãî÷ëåíàâîçüì¼ì ïðèìèòèâíûé ìíîãî÷ëåí a(x) = x3 + x + 1.a(x) ì.ì. äëÿ ãåíåðàòîðà x = α ∈ F ∗ è F ∗ ðàçáèâàåòñÿ íàñëåäóþùèå öèêëîòîìè÷åñêèå êëàññû íàä F2 (áûëî ðàíåå): { 1 } , α, α2 , α4 , α3 , α6 , α5 .1. Êîä Á×Õ, èñïðàâëÿþùèé r = 1 îøèáêó (êîä Õýììèíãà).Òîãäà d − 1 = 2r = 2 è ýëåìåíòû α, α2 ïîïàäàþò â îäèíöèêëîòîìè÷åñêèé êëàññ.Ì.ì.
äëÿ âñåõ ýëåìåíòîâ ýòîãî êëàññà a(x), ïîýòîìóïîðîæäàþùèé ïîëèíîì g(x) = a(x), m = deg g(x) = 3 è âðåçóëüòàòå ïîëó÷àåì óæå èçâåñòíûé (7, 4, 3)-êîä.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè90 / 152Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÊîäèðîâàíèå Á×Õ-êîäàìèÏîñòðîåíèÿ êîäîâ Á×Õ äëÿ q = 3, n = 7, a(x) = x3 + x + 1...2. Êîä Á×Õ, èñïðàâëÿþùèé íå ìåíåå r = 2 îøèáîê.Ïîñêîëüêó d − 1 = 2r = 4, òî ïîðîæäàþùèé ïîëèíîì g(x)åñòü ìíîãî÷ëåí ìèíèìàëüíîé ñòåïåíè ñ êîðíÿìè α, α2 , α3 , α4èç ïîëÿ F .Äàííûåýëåìåíòû âõîäÿò â äâà öèêëîòîìè÷åñêèõ êëàññà:α, α2 , α4 è α3 , α6 , α5 , ïîðîæäàåìûõ α è α3ñîîòâåòñòâåííî, ñëåäîâàòåëüíî g(x) = gα (x) · gα3 (x),ãäå gα (x) è gα3 (x) ì.ì.
äëÿ α è α3 ñîîòâåòñòâåííî.Ì.ì. äëÿ α èçâåñòåí: gα (x) = a(x) = x3 + x + 1.Íàéäåì ì.ì. äëÿ α3 :gα3 (x) = x + α3 x + α5 x + α6 == x3 + α3 + α5 + α6 x2 + α8 + α9 + α11 x + α14 .ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè91 / 152Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÊîäèðîâàíèå Á×Õ-êîäàìèÏîñòðîåíèÿ êîäîâ Á×Õ äëÿ q = 3, n = 7, a(x) = x3 + x + 1...Âû÷èñëèì êîýôôèöèåíòû gα3 (x).Ïîñêîëüêó α ïðèìèòèâíûé ýëåìåíò ïîëÿòî α7 = 1, α3 = α + 1 èF2 [x]/ x3 + x + 1 ,α3 + α5 + α6 = α + 1 + (α + 1)2 + α2 (α + 1) == α + 1 + α2 + 1 + α3 + α2 = 1 ,α8 + α9 + α11 = α2 + α + α4 = α2 + α + α(α + 1) = 0 ,α14 = 1 .Òàêèì îáðàçîì, gα3 (x) = x3 + x2 + 1 èg(x) = gα (x) · gα3 (x) = (x3 + x + 1)(x3 + x2 + 1) == x6 + x5 + x4 + x3 + x2 + x + 1,deg g(x) = 6, k = 7−6 = 1. ðåçóëüòàòå ïîñòðîåí òðèâèàëüíûé (7, 1, 7)-êîä, ñîäåðæàùèéâñåãî äâà êîäîâûõ ñëîâà v 1 = [0000000], v 2 = [1111111] èèñïðàâëÿþùèé 3 îøèáêè.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè92 / 152Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÊîäèðîâàíèå Á×Õ-êîäàìèÏîñòðîåíèÿ êîäîâ Á×Õ äëÿ q = 4, n = 15, a(x) = x4 + x + 1Ìû âèäèì, ÷òî êîä ïîëó÷èëñÿ ïëîõîé: õîòÿ îí è èñïðàâëÿåòáîëüøå îøèáîê, ÷åì ïëàíèðîâàëîñü, åãî ñêîðîñòü ðàâíàR = 1/7, ò.å.
î÷åíü ìàëà.Ïîïûòàåìñÿ ïîñòðîèòü ëó÷øèé êîä äëÿ èñïðàâëåíèÿ äâóõîøèáîê, âçÿâ áîëüøóþ åãî äëèíó: q = 4, n = 2q − 1 = 15.3. Êîä Á×Õ, èñïðàâëÿþùèé r = 2 îøèáêè. êà÷åñòâå ïîðîæäàþùåãî ïîëå F = F2 [x]/(a(x)) ìíîãî÷ëåíàâîçüì¼ì ïðèìèòèâíûé ìíîãî÷ëåí a(x) = x4 + x + 1.Åñëè α ãåíåðàòîð â F ∗ , òî íóëÿìè êîäà áóäóò α, α2 , α3 , α4 ,ðàñïîëàãàþùèåñÿ â äâóõ öèêëîòîìè÷åñêèõ êëàññàõ:α, α2 , α4 , α8 è α3 , α6 , α12 , α9 .ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè93 / 152Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÊîäèðîâàíèå Á×Õ-êîäàìèÏîñòðîåíèÿ êîäîâ Á×Õ äëÿ q = 4, n = 15, a(x) = x4 + x + 1...Ìèíèìàëüíûå ìíîãî÷ëåíû äëÿ âñåõ ýëåìåíòîâ ýòèõ êëàññîâ:ïåðâîãî ( α ):âòîðîãî ( α3 ):gα (x) = a(x).gα3 (x) = (x − α3 )(x − α6 )(x − α9 )(x − α12 ) =...
= x4 + x3 + x2 + x + 1.Ïîðîæäàþùèé ïîëèíîì åñòüg(x) = gα (x) · gα3 (x) = x8 + x7 + x6 + x4 + 1. ðåçóëüòàòå k = 15 − 8 = 7 è, ìîæíî ïîêàçàòü, d = 5, ò.å.ïîëó÷åí Á×Õ (15, 7, 5)-êîä ñî ñêîðîñòüþ óæå R = 7/15 > 1/7.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè94 / 152Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÊîäèðîâàíèå Á×Õ-êîäàìèÏîñòðîåíèÿ êîäîâ Á×Õ äëÿ q = 4, n = 15, a(x) = x4 + x + 1... òîì æå ïîëå F ïîñòðîèì4.
Êîä Á×Õ, èñïðàâëÿþùèé r = 3 îøèáêè.Ïóñòü α ãåíåðàòîð F ∗ (ò.å. α15 = 1, α4 = α + 1).Íóëÿìè êîíñòðóèðóåìîãî Á×Õ-êîäà áóäóò α, α2 , . . . , α6 ,êîòîðûå ïîïàäàþò â öèêëîòîìè÷åñêèå êëàññû α, α2 , α4 , α8 , α3 , α6 , α9 , α12 , α5 , α10 .Ìèíèìàëüíûå ìíîãî÷ëåíû äëÿ ýëåìåíòîâ ýòèõ êëàññîâ ñóòügα (x) = x4 + x + 1, gα3 (x) = x4 + x3 + x2 + x + 1 ègα5 (x) = x2 + x + 1, à ïîðîæäàþùèé ïîëèíîì ïîëó÷åííîãî(15, 5, 7)-êîäà Á×Õ åñòü èõ ïðîèçâåäåíèå:g(x) = gα (x)·gα3 (x)·gα5 (x) = x10 + x8 + x5 + x4 + x2 + x + 1.Ýòîò êîä ïðè òîé æå äëèíå, ÷òî è ïðåäûäóùèé, èñïðàâëÿåòáîëüøå îøèáîê, íî èìååò ìåíüøóþ ñêîðîñòü.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè95 / 152Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÊîäèðîâàíèå Á×Õ-êîäàìèÊîäû Á×Õ: çàâèñèìîñòè ñêîðîñòè îò êîäîâîãî ðàññòîÿíèÿlength n = 255length n = 63110.90.90.80.80.7speed k/nspeed k/n0.70.60.50.40.60.50.40.30.30.20.20.10.100510152025distance dÃðàôèêè ñêîðîñòè3035020406080100120140distance dk/n êîäîâ Á×Õ â çàâèñèìîñòè îòd äëÿ äàííîé äëèíû êîäà n.êîäîâîãîðàññòîÿíèÿ¾Ñòóïåíüêè¿ íà ãðàôèêàõ ñîîòâåòñòâóþò ñèòóàöèè, êîãäàðåàëüíîå êîäîâîå ðàññòîÿíèå îêàçûâàåòñÿ áîëüøåêîíñòðóêòèâíîãî, çàäàâàåìîãî ïðè ïîñòðîåíèè êîäà.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
