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

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

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

Íàéä¼ì ñèíäðîì ïðèíÿòîãî ñîîáùåíèÿ w: 1 0  1 1 1 0 0 010 = 0 = s .Hw = 1 0 0 1 1 0 × 0 1 0 1 0 1 101053 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÃðóïïîâûå (ëèíåéíûå) êîäûÄåêîäèðîâàíèå ëèíåéíûõ êîäîâÄåêîäèðîâàíèå ëèíåéíîãî êîäà: ïðèìåð...2. Íàõîäèì âñå ðåøåíèÿ ñèñòåìû He = s.2.à Íàõîäèì ÷àñòíîå ðåøåíèå eb ýòîé ñèñòåìû. Ïîñêîëüêó âñòîëáöàõ 2, 4, 6 ïðîâåðî÷íîé ìàòðèöû H ñòîèò åäèíè÷íàÿïîäìàòðèöà, âîçüì¼ì êîîðäèíàòû 1, 3 è 5 âåêòîðà ebíóëåâûìè: eb1 = eb3 = eb5 = 0 è òîãäàeb2 = s1 = 1, eb4 = s2 = 0, eb6 = s3 = 0, ò.å. eb = [0 1 0 0 0 0]T .2.à Âñå ðåøåíèÿ îäíîðîäíîé ñèñòåìû He = 0 óæå áûëèíàéäåíû ðàíüøå ïðè âû÷èñëåíèè êîäîâîãî ðàññòîÿíèÿ d:0 1 0 1 0 1 0 10 1 0 1 1 0 1 00 0 0 0 1 1 1 1.G × [ u1 . . .

u8 ] = 0 1 1 0 1 0 0 10 0 1 1 1 1 0 00 1 1 0 0 1 1 054 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè55 / 152Ãðóïïîâûå (ëèíåéíûå) êîäûÄåêîäèðîâàíèå ëèíåéíûõ êîäîâÄåêîäèðîâàíèå ëèíåéíîãî êîäà: ïðèìåð...Òàêèì îáðàçîì, âñå 8 ðåøåíèé ñèñòåìû He = sçàïèñûâàþòñÿ êàê ñóììà âåêòîðà eb = [0 1 0 0 0 0]T ñî âñåìèñòîëáöàìè ìàòðèöû G × [ u1 . .

. u8 ]:010000100101010111100010001110111011001001111.100Âûáèðàåì ñðåäè íèõ ðåøåíèå ñ íàèìåíüøèì âåñîì ýòîïåðâûé ñòîëáåö e = [0 1 0 0 0 0]T .Îòñþäàb = w +e = [1 0 0 0 1 0]T +[0 1 0 0 0 0]T = [1 1 0 0 1 0]T = vvè èñõîäíîå ñîîáùåíèå âîññòàíîâëåíî âåðíî.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè56 / 152Ãðóïïîâûå (ëèíåéíûå) êîäûÄåêîäèðîâàíèå ëèíåéíûõ êîäîâÃðóïïîâîå êîäû (n, k): ðåçþìåÒðåáîâàíèå ëèíåéíîñòè ïîçâîëÿåò ðåàëèçîâûâàòü áîëååýôôåêòèâíûå àëãîðèòìû êîäèðîâàíèÿ è äåêîäèðîâàíèÿ.Êîäèðîâàíèå îñóùåñòâëÿåòñÿ îñîáåííî ïðîñòî: äëÿ ýòîãî íàäîóìíîæèòü âåêòîð-ñîîáùåíèÿ íà ïîðîæäàþùóþ ìàòðèöó.Íî âîïðîñ ¾êàê íàéòè ïîäõîäÿùóþ ïîðîæäàþùóþ ìàòðèöó?¿îñòà¼òñÿ îòêðûòûì.Äåêîäèðîâàíèå òàêæå çíà÷èòåëüíî óïðîùàåòñÿ:îñóùåñòâëÿåòñÿ ñ ïîìîùüþ ëåãêî âû÷èñëÿåìûõ ñèíäðîìîâ;ýòàï 2 ïðè ñèñòåìàòè÷åñêîì êîäèðîâàíèè ýëåìåíòàðåí.Îäíàêî â îáùåì ñëó÷àå òðåáóåòñÿ ïåðåáðàòü 2k ðåøåíèéÑËÀÓ, ò.å.

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

×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè59 / 152Öèêëè÷åñêèå êîäûÎïðåäåëåíèå, îñíîâíûå ñâîéñòâà, ïðèìåðÖèêëè÷åñêèå êîäû: îïðåäåëåíèåÎïðåäåëåíèåÊîä C íàçûâàåòñÿ öèêëè÷åñêèì (ñäâèãîâûì), åñëè îíèíâàðèàíòåí îòíîñèòåëüíî öèêëè÷åñêèõ ñäâèãîâ, ò.å. äëÿëþáîãî 0 6 s 6 n − 1 ñïðàâåäëèâî(α0 , . . . , αn−1 ) ∈ C ⇒ (αs , αs+1 , . .

. , αn−1 , α0 , . . . , αs−1 ) ∈ C .Ðàíåå ðàññìàòðèâàëîñü è áûëî ïîêàçàíî: êîëüöå Fp [x]/(xn − 1), ðàññìàòðèâàåìîì êàê âåêòîðíîåïðîñòðàíñòâî íàä ïîëåìn Fp , èìååòñÿ áàçèño1, x, . . . , xn−1 .Öèêëè÷åñêèé ñäâèã êîîðäèíàò â ýòîì áàçèñå ðàâíîñèëåíóìíîæåíèþ íà x.Òåîðåìà: Âåêòîðíîå ïîäïðîñòðàíñòâî I ⊆ Fp [x]/(xn − 1)ÿâëÿåòñÿ öèêëè÷åñêèì i I Fp [x]/(xn − 1).ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÖèêëè÷åñêèå êîäûÎïðåäåëåíèå, îñíîâíûå ñâîéñòâà, ïðèìåðÖèêëè÷åñêèå êîäû: èäåÿ ïîñòðîåíèÿÏîýòîìó ïîñòðîèòü äâîè÷íûé öèêëè÷åñêèé êîä ìîæíî òàê:1âûáèðàåì íåêîòîðûé äåëèòåëü g(x) áèíîìà xn − 1;ìíîãî÷ëåí g(x) íàçûâàþò ïîðîæäàþùèì.2â êîëüöåF2 [x]/(xn − 1) îáðàçóåì èäåàë (g(x)).Îêàçûâàåòñÿ, ïðè óäà÷íîì âûáîðå g(x) êîýôôèöèåíòûìíîãî÷ëåíîâ èç äàííîãî èäåàëà áóäóò äàâàòü õîðîøèé êîä ñìàëîé èçáûòî÷íîñòüþ m/n ïðè áîëüøîì d.Îäíàêî:åñòü òîëüêî íåñêîëüêî êîíñòðóêöèé öèêëè÷åñêèõ êîäîâñ õîðîøèìè ïàðàìåòðàìè;â îáùåì ñëó÷àå îïðåäåëåíèå êîäîâîãî ðàññòîÿíèÿöèêëè÷åñêîãî êîäà ÷ðåçâû÷àéíî ñëîæíî.Öèêëè÷åñêèé êîä àíãë.

CRC, Cyclic Redundancy Code.60 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè61 / 152Öèêëè÷åñêèå êîäûÎïðåäåëåíèå, îñíîâíûå ñâîéñòâà, ïðèìåðËèíåéíûå öèêëè÷åñêèå êîäûÈç âñåõ ëèíåéíûõ (n, k)-êîäîâ áóäåì äàëåå ðàññìàòðèâàòüöèêëè÷åñêèå.Óñòàíîâèì ñîîòâåòñòâèå âåêòîðà v êîîðäèíàòíîãîïðîñòðàíñòâà {0, 1}n è ïîëèíîìà v(x) ∈ F2 [x]:v = [ v0 , v1 , . . . , vn−1 ]T ↔ v(x) = v0 + v1 x + . . . + vn−1 xn−1 .Òîãäà ñâîéñòâî ãëàâíîãî èäåàëà ïåðåôîðìóëèðóåòñÿ:äëÿ êàæäîãî (n, k)-öèêëè÷åñêîãî êîäà íàéäåòñÿ ïîðîæäàþùèéïîëèíîì g(x) òàêîé, ÷òî1g(x) | (xn − 1);2ëþáîå êîäîâîå ñëîâî v(x) ïðåäñòàâëÿåòñÿ â âèäåv(x) = g(x)q(x), ãäå q(x) íåêîòîðûé ïîëèíîì.Ëþáîé äåëÿùèé xn − 1 ïîëèíîì ÿâëÿåòñÿ ïîðîæäàþùèì äëÿíåêîòîðîãî öèêëè÷åñêîãî êîäà äëèíû n.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.

×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè62 / 152Öèêëè÷åñêèå êîäûÎïðåäåëåíèå, îñíîâíûå ñâîéñòâà, ïðèìåðÖèêëè÷åñêèå êîäû: ïðèìåð ïîñòðîåíèÿÏîñòðîèì öèêëè÷åñêèé êîä äëèíû n = 23.Äëÿ íàõîæäåíèÿ ïîðîæäàþùåãî ïîëèíîìà êîäà íàõîäèìðàçëîæåíèå áèíîìà x23 − 1 íà íåïðèâîäèìûå ìíîãî÷ëåíû.Îäèí êîðåíü íàõîäèòñÿ ñðàçó: ýòî x.Äàëåå èìååì ðàçëîæåíèå2221x23 + 1 = (x + 1)(x. . + x2 + x + 1}).| + x + . {zf (x)Ïåðåáîðîì íåïðèâîäèìûõ ïîëèíîìîâ ñòåïåíè äî 11, ïîëó÷àåì119765f (x) = (x| + x + x +{zx + x + x + 1})×f1 (x)11106542× (x| + x + x +{zx + x + x + 1})f2 (x)ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè63 / 152Öèêëè÷åñêèå êîäûÎïðåäåëåíèå, îñíîâíûå ñâîéñòâà, ïðèìåðÖèêëè÷åñêèå êîäû: ïðèìåð ïîñòðîåíèÿ...Ïîñêîëüêó ñòåïåíè ïîëèíîìîâ f1 (x) è f2 (x) ñîâïàäàþò, ëþáîéèç íèõ ìîæåò áûòü âûáðàí êàê ïîðîæäàþùèé äëÿ (23, 12)-êîäà.Ìîæíî ïîêàçàòü, ÷òî êîäîâîå ðàññòîÿíèå ïîëó÷åííîãî êîäàðàâíî 7.Íàïðèìåð, ïðè âûáîðå ïîðîæäàþùèì f2 (x) è(íåñèñòåìàòè÷åñêîì) êîäèðîâàíèè ñîîáùåíèÿ[110000000000] ↔ x + 1,ïîëó÷àåì êîäîâîå ñëîâî âåñà 7:11106542(x| + x + x +{zx + x + x + 1})(x + 1) =g(x)= x12 + x10 + x7 + x4 + x3 + x2 + x ↔ [011110010010100000000000].ßñíî, ÷òî ïîñòðîåí êîä Ãîëåÿ.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.

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

×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè65 / 152Öèêëè÷åñêèå êîäûÊîäèðîâàíèå öèêëè÷åñêèìè êîäàìè è äåêîäèðîâàíèåÖèêëè÷åñêèå êîäû: êîäèðîâàíèåÏóñòü çàäàí ïîðîæäàþùèé ïîëèíîì g(x) ñòåïåíè m(= ÷èñëó ïðîâåðî÷íûõ áèòîâ ó áóäóùåãî êîäà C ).Ðàññìîòðèìâîçìîæíûåìåòîäûïîñòðîåíèÿëèíåéíûõöèêëè÷åñêèõ (n, k)-êîäîâ (n = m + k ), êîäèðóþùèõñîîáùåíèåïîëèíîì u(x) ñòåïåíè k − 1: u(x) 7→ v(x).Ðåçóëüòàò êîäîâîå ñëîâîïîëèíîì v(x) ∈ C ñòåïåíè n − 1.Íåñèñòåìàòè÷åñêîå êîäèðîâàíèå îñóùåñòâëÿåòñÿ ïóò¼ìóìíîæåíèÿ êîäèðóåìîãî âåêòîðà íà ïîðîæäàþùèé ïîëèíîì:u(x) 7→ v(x) = g(x)u(x). ïîðîæäàþùåé ìàòðèöå Gn×k = [ g 0 .

. . g k−1 ] äàííîãî êîäàáàçèñíûå âåêòîðû g i ñîîòâåòñòâóþò ïîëèíîìàì xi g(x),i = 0, k − 1.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÖèêëè÷åñêèå êîäûÊîäèðîâàíèå öèêëè÷åñêèìè êîäàìè è äåêîäèðîâàíèåÖèêëè÷åñêèå êîäû: ñèñòåìàòè÷åñêîå êîäèðîâàíèå...Ñèñòåìàòè÷åñêîå êîäèðîâàíèå îñóùåñòâëÿåòñÿ ïóò¼ì¾äîïèñûâàíèÿ¿ ê êîäèðóåìîìó ñëîâó îñòàòêà r(x) îò äåëåíèÿxm u(x) íà g(x):xm u(x) = g(x)q(x) + r(x)è deg r(x) < m.Îòñþäàxm u(x) + r(x) = g(x)q(x) ∈ C ,ñèñòåìàòè÷åñêîå êîäèðîâàíèå ìîæåò áûòü çàäàíî êàêv(x) = xm u(x) + r(x), ãäå r(x) ≡g(x) xm u(x),è ïîëèíîì v(x) èìååò â k êðàéíèõ ïðàâûõ ïîçèöèÿõ (ò.å. ïðèñòàðøèõ ñòåïåíÿõ x) k êîýôôèöèåíòîâ ïîëèíîìà u(x). ïîðîæäàþùåé ìàòðèöå Gn×k = [ g 0 . .

. g k−1 ] äàííîãî êîäàáàçèñíûå âåêòîðû g i ñîîòâåòñòâóþò ïîëèíîìàìxm+i + ri (x), ãäå ri (x) ≡g(x) xm+i , i = 0, k − 1.66 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè67 / 152Öèêëè÷åñêèå êîäûÊîäèðîâàíèå öèêëè÷åñêèìè êîäàìè è äåêîäèðîâàíèåÖèêëè÷åñêèé êîä: ïðèìåð êîäèðîâàíèÿÏóñòü òðåáóåòñÿ ïîñòðîèòü öèêëè÷åñêèé êîä äëèíûn = 7.Ýòî îçíà÷àåò, ÷òî ðàáîòàåì â êîëüöå F2 [x]/ x7 − 1 .1.

Íàõîäèì ðàçëîæåíèå ïîëèíîìà x7 − 1 íà íåïðèâîäèìûåìíîæèòåëè.Òàê êàê 7 = 23 − 1, òî êîðíÿìè x7 − 1 ÿâëÿþòñÿ âñå íåíóëåâûåýëåìåíòû ïîëÿ F32 .Èçâåñòíî, ÷òî:êàæäûé ìíîãî÷ëåí f íàä êîíå÷íûì ïîëåì ñîäåðæèò âðàñøèðåíèè ýòîãî ïîëÿ âìåñòå ñ ëþáûì ñâîèì êîðíåì β2òàêæå ñîïðÿæ¼ííûå êîðíè âèäà β 2 , β 2 , . . .;åñëè f ïðèâîäèì, òî èìååòñÿ íåñêîëüêî ñåðèé òàêèõñîïðÿæ¼ííûõ êîðíåé.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÖèêëè÷åñêèå êîäûÊîäèðîâàíèå öèêëè÷åñêèìè êîäàìè è äåêîäèðîâàíèåÖèêëè÷åñêèé êîä: ïðèìåð êîäèðîâàíèÿ...Ïóñòü α ïðîèçâîëüíûé ïðèìèòèâíûé ýëåìåíò ïîëÿ F = F32 .Òîãäà ñ ó÷åòîì α7 = 1 íàõîäèì ðàçáèåíèå êîðíåé x7 − 1 (=âñåõ ýëåìåíòîâ F ∗ ) íà îðáèòû: α, α2 , α4 , α3 , α6 , α5 , { 1 }.Òàêèì îáðàçîì, ìíîãî÷ëåí x7 + 1 èìååò îäèí íåïðèâîäèìûéäåëèòåëü 1-é ñòåïåíè è äâà íåïðèâîäèìûõ äåëèòåëÿ 3-éñòåïåíè.  ðåçóëüòàòå ïîëó÷àåì ðàçëîæåíèåx7 − 1 = x7 + 1 = (x + 1)(x3 + x + 1)(x3 + x2 + 1).2.

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

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