Лекции по прикладной алгебре. v1.0 (1127110), страница 9
Текст из файла (страница 9)
âåðõíÿÿ îöåíêà âòåîðåìå Õýììèíãà äîñòèãàåòñÿ.Ïîñòðîèì êîä, à ïîòîì îïðåäåëèì åãî êîäîâîå ðàññòîÿíèå.Ðàññìîòðèì òàáëèöó:2m −(m+1)100. . . 000010. . . 000001. . . 000...000. . . 100000. . . 010000. . . 0011100. . . 0001010. . . 0001001. . . 000...1111.
. . 1011111. . . 1101111. . . 111||{z}2m −(m+1){zm}Ñëåâà åäèíè÷íàÿ ìàòðèöà ïîðÿäêà 2m − (m + 1), ñïðàâà âñåáèíàðíûå íàáîðû äëèíû m, ñîäåðæàùèå íå ìåíåå äâóõ åäèíèö.Ïðèêëàäíàÿ àëãåáðà123 / 225Êîäû, èñïðàâëÿþùèå îøèáêèÎñíîâíàÿ çàäà÷à òåîðèè êîäèðîâàíèÿÑëó÷àé n = 2m − 1, r = 1: êîä ÕýììèíãàÏðîñóììèðóåì âñåâîçìîæíûå ñîâîêóïíîñòè ñòðîê ýòîémòàáëèöû, ïîëó÷èâ âñåãî 22 −(m+1) íàáîðîâ. Çàìåòèì, ÷òîm22m −(m+1)2n22 −1=.=2mn+1Ëåãêî âèäåòü, ÷òî åñëè ñóììèðóåìäâå ñòðîêè â ëåâîé ÷àñòè áóäåò äâå åäèíèöû, à â ïðàâîé õîòÿ áû îäíà;íå ìåíåå òð¼õ ñòðîê â ëåâîé ÷àñòè áóäåò íå ìåíåå òðåõ åäèíèö;e >3ò.å. âñåãäà ρ(eα, β)è øàðû ðàäèóñà 1 ñ öåíòðàìè â ýòèõ íàáîðàõ íå ïåðåñåêàþòñÿ.Ïðèêëàäíàÿ àëãåáðà124 / 225Êîäû, èñïðàâëÿþùèå îøèáêèÎñíîâíàÿ çàäà÷à òåîðèè êîäèðîâàíèÿÑëó÷àé n = 2m − 1, r = 1: êîä Õýììèíãà äëèíû 7 (m = 3)ÏðèìåðÑîñòàâèì òàáëèöó äëÿ êîäà Õýììèíãà äëèíû 7:1000010000100001110110110111Ñêëàäûâàÿ ïî mod 2 ïðîèçâîëüíûå ñîâîêóïíîñòè ñòðîê,ïîëó÷àåì 16 ðàçëè÷íûõ áèíàðíûõ ñëîâ.
Èìè ìîæíîçàêîäèðîâàòü 16 ñîîáùåíèé íàïðèìåð, 10 öèôð|ðàçäåëèòåëü|=| + | − | × | ÷.Ïðè ïåðåäà÷å ñîîáùåíèé ñ ïîìîùüþ êîäà Õýììèíãàìîæíî èñïðàâèòü îäíó îøèáêó.Ïðèêëàäíàÿ àëãåáðà125 / 225Êîäû, èñïðàâëÿþùèå îøèáêèÎñíîâíàÿ çàäà÷à òåîðèè êîäèðîâàíèÿÑëó÷àé n = 23, r = 3 ýòîì ñëó÷àå âåðõíÿÿ ãðàíèöà ÷èñëà âëîæåííûõ øàðîâðàäèóñà 3 â êóá 23-ìåðíûé åäèíè÷íûé êóá2231 + 23 +23·222+23·22·216=223223= 11 = 212 = 409620482äîñòèãàåòñÿ èìååì ïëîòíóþ óïàêîâêó, êàê è â ðàíååðàññìîòðåííûõ ñëó÷àÿõ.Äðóãèõ ïàð n è r, óäîâëåòâîðÿþùèõ óñëîâèþ2n öåëîånnn++ ...
+01ríåèçâåñòíî.Ïðèêëàäíàÿ àëãåáðàÊîäû, èñïðàâëÿþùèå îøèáêèÖèêëè÷åñêèå êîäûÐàçäåë I1Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà - IÏîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÏîñòðîåíèå ïîëåé ÃàëóàËèíåéíàÿ àëãåáðà íàä êîíå÷íûì ïîëåìÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåì2Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà - IIÑóùåñòâîâàíèå è åäèíñòâåííîñòü ïîëÿ Ãàëóà èç pnýëåìåíòîâÖèêëè÷åñêèå ïîäïðîñòðàíñòâàÇàäà÷è3Êîäû, èñïðàâëÿþùèå îøèáêèÎñíîâíàÿ çàäà÷à òåîðèè êîäèðîâàíèÿÖèêëè÷åñêèå êîäû126 / 225Ïðèêëàäíàÿ àëãåáðàÊîäû, èñïðàâëÿþùèå îøèáêèÖèêëè÷åñêèå êîäûÐàçäåë IIÊîäû Á×Õ4Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÄåéñòâèå ãðóïïû íà ìíîæåñòâåÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿêîìáèíàòîðíûõ çàäà÷5×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÎïåðàöèè íàä ÷.ó.
ìíîæåñòâàìèËèíåàðèçàöèÿ6Àëãåáðàè÷åñêèå ðåø¼òêèÐåø¼òêè127 / 225Ïðèêëàäíàÿ àëãåáðà128 / 225Êîäû, èñïðàâëÿþùèå îøèáêèÖèêëè÷åñêèå êîäûÖèêëè÷åñêèå êîäû: îïðåäåëåíèåÎïðåäåëåíèåÊîä C íàçûâàåòñÿ öèêëè÷åñêèì, åñëè îí èíâàðèàíòåíîòíîñèòåëüíî öèêëè÷åñêèõ ñäâèãîâ: èç òîãî, ÷òî íàáîð(α0 , . . . , αn−1 )∈C , ñëåäóåò, ÷òî è âñÿêèé íàáîð(αs , αs+1 , . . . , αn−1 , α0 , . . . , αs−1 ) ∈ C .Ðàíåå ðàññìàòðèâàëèñü áûëî ïîêàçàíî: êîëüöå Fp /(xn − 1), ðàññìàòðèâàåìîì êàêâåêòîðíîå ïðîñòðàíñòâî íàä ïîëåì Fp , åñòü áàçèñ{ 1, x, .
. . , xn−1 }. Öèêëè÷åñêèé ñäâèã êîîðäèíàò â ýòîì áàçèñåðàâíîñèëåí óìíîæåíèþ íà x.Òåîðåìà: Ïîäïðîñòðàíñòâî I ⊆ Fp /(xn − 1) ÿâëÿåòñÿöèêëè÷åñêèì i I èäåàë â Fp /(xn − 1).Ïðèêëàäíàÿ àëãåáðàÊîäû, èñïðàâëÿþùèå îøèáêèÖèêëè÷åñêèå êîäûÖèêëè÷åñêèå êîäû: ïîñòðîåíèåÏîýòîìó ïîñòðîèòü öèêëè÷åñêèé êîä ìîæíî òàê:ðàññìîòðèì ìíîãî÷ëåí xn − 1 è âûáåðåì íåêîòîðûé åãîäåëèòåëü ϕ(x);â êîëüöå F2 [x]/(xn − 1) îáðàçóåì èäåàë (ϕ(x)).Îêàçûâàåòñÿ, ïðè óäà÷íîì âûáîðå ϕ(x) êîýôôèöèåíòûìíîãî÷ëåíîâ, ïðèíàäëåæàùèõ ýòîìó èäåàëó, áóäóò äàâàòüõîðîøèé êîä.Åñòü òîëüêî íåñêîëüêî êîíñòðóêöèé öèêëè÷åñêèõ êîäîâ ñõîðîøèìè ïàðàìåòðàìè.Âîïðîñ î êîäîâîì ðàññòîÿíèè ïðîèçâîëüíîãî öèêëè÷åñêîãîêîäà ÷ðåçâû÷àéíî òðóäåí.129 / 225Ïðèêëàäíàÿ àëãåáðà130 / 225Êîäû, èñïðàâëÿþùèå îøèáêèÖèêëè÷åñêèå êîäûÖèêëè÷åñêèå êîäû: ïðèìåð ïîñòðîåíèÿÏðèìåðÏóñòü n = 7.
Ðàçëîæåíèå íà íåïðèâîäèìûå ìíîæèòåëè:x7 − 1 = (1 + x)(1 + x2 + x3 )(1 + x + x3 ).Ïðèêëàäíàÿ àëãåáðà130 / 225Êîäû, èñïðàâëÿþùèå îøèáêèÖèêëè÷åñêèå êîäûÖèêëè÷åñêèå êîäû: ïðèìåð ïîñòðîåíèÿÏðèìåðÏóñòü n = 7. Ðàçëîæåíèå íà íåïðèâîäèìûå ìíîæèòåëè:x7 − 1 = (1 + x)(1 + x2 + x3 )(1 + x + x3 ). êà÷åñòâå ϕ âîçüìåì ïîñëåäíèé ìíîæèòåëü, deg ϕ = 3.
Óìíîæàÿåãî íà ñòåïåíè x (öèêëè÷åñêè ñäâèãàÿ 3 ðàçà) ïîëó÷èì áàçèñ âïîäïðîñòðàíñòâå, êîòîðîå ÿâëÿåòñÿ êîäîì:(1101000) ↔ ϕ(0110100) ↔ ϕ · x(0011010) ↔ ϕ · x2(0001101) ↔ ϕ · x3Ìîæíî ïðîâåðèòü, ÷òî êîäîâîå ðàññòîÿíèå äëÿ ýòîãî êîäà ðàâíî 3.Ïðèêëàäíàÿ àëãåáðàÊîäû, èñïðàâëÿþùèå îøèáêèÊîäû Á×ÕÐàçäåë I1Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà - IÏîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÏîñòðîåíèå ïîëåé ÃàëóàËèíåéíàÿ àëãåáðà íàä êîíå÷íûì ïîëåìÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåì2Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà - IIÑóùåñòâîâàíèå è åäèíñòâåííîñòü ïîëÿ Ãàëóà èç pnýëåìåíòîâÖèêëè÷åñêèå ïîäïðîñòðàíñòâàÇàäà÷è3Êîäû, èñïðàâëÿþùèå îøèáêèÎñíîâíàÿ çàäà÷à òåîðèè êîäèðîâàíèÿÖèêëè÷åñêèå êîäû131 / 225Ïðèêëàäíàÿ àëãåáðàÊîäû, èñïðàâëÿþùèå îøèáêèÊîäû Á×ÕÐàçäåë IIÊîäû Á×Õ4Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÄåéñòâèå ãðóïïû íà ìíîæåñòâåÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿêîìáèíàòîðíûõ çàäà÷5×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÎïåðàöèè íàä ÷.ó.
ìíîæåñòâàìèËèíåàðèçàöèÿ6Àëãåáðàè÷åñêèå ðåø¼òêèÐåø¼òêè132 / 225Ïðèêëàäíàÿ àëãåáðàÊîäû, èñïðàâëÿþùèå îøèáêèÊîäû Á×ÕÊîäû Á×Õ êîäû äëèíû n = 2k − 1Ðàññìîòðèì êîäû äëèíû n = 2k − 1.Ðàññìàòðèâàåìûé äàëåå ñïîñîá ïîñòðîåíèÿ ¾õîðîøåãî¿ êîäà,èñïðàâëÿþùåãî ¾ìíîãî¿ îøèáîê ïðåäëîæèëè Ðàäæ ×àíäðàÁîóç è Äâàéäæåíäðà Êàìàð Ðåé-×îóäõóðè â 1959 ã. èíåçàâèñèìî Àëåêñèñ Õîêâèíãåì â 1960 ã.Ïîýòîìó êîäû, êîòîðûå ìû ðàññìîòðèì, íàçûâàþòñÿ êîäàìèÁîóçà-×îóäõóðè-Õîêâèíãåìà èëè Á×Õ-êîäàìè (BCH,Bose-Chaudhuri-Hocquenghem) ýòî êëàññ öèêëè÷åñêèõ êîäîâ,èñïðàâëÿþùèõ êðàòíûå (2 è áîëåå) îøèáêè.Òåîðåòè÷åñêè êîäû Á×Õ ìîãóò èñïðàâëÿòü ïðîèçâîëüíîåêîëè÷åñòâî îøèáîê, íî ïðè ýòîì ñóùåñòâåííî óâåëè÷èâàåòñÿäëèíà êîäîâîãî ñëîâà (÷òî ïðèâîäèò ê óìåíüøåíèþ ñêîðîñòèïåðåäà÷è äàííûõ è óñëîæíåíèþ ïðèåìî-ïåðåäàþùåéàïïàðàòóðû).Êîäû Õýììèíãà ÷àñòíûé ñëó÷àé Á×Õ-êîäîâ.133 / 225Ïðèêëàäíàÿ àëãåáðà134 / 225Êîäû, èñïðàâëÿþùèå îøèáêèÊîäû Á×ÕÓòî÷íåíèå îïèñàííîé âûøå ñõåìû ïðè n = 2k − 1 êîíêðåòèçèðóþùåé âûáîð èäåàëà.1234Ñòðîèì ïîëå Fn2 = F2 /(f ), f íåïðèâîäèìûé ìíîãî÷ëåí.Ýëåìåíòû Fn∗2 îáðàçóþò öèêëè÷åñêóþ ãðóïïó ïî óìíîæåíèþ.Âûáåðåì ïîðîæäàþùèé ýëåìåíò α ∈ Fn∗2 è ðàññìîòðèì åãîñòåïåíèα, α2 , .
. . , α2r ,ãäå r ÷èñëî îøèáîê, êîòîðûå íóæíî óìåòü èñïðàâëÿòü. ðàçëîæåíèè ìíîãî÷ëåíà xn −1 âûáåðåì òàêèå íåïðèâîäèìûåìíîãî÷ëåíû, ÷òîáû êàæäàÿ èç óêàçàííûõ ñòåïåíåé áûëà êîðíåìîäíîãî èç íèõ.ϕ åñòü ðåçóëüòàò ïåðåìíîæåíèÿ ýòèõ ìíîãî÷ëåíîâ.Êîäû êîýôôèöèåíòû ìíîãî÷ëåíîâ èç èäåàëà (ϕ).Îêàçûâàåòñÿ (äàëåå áóäåò äîêàçàíî), ÷òî ýòî ãàðàíòèðóåòèñïðàâëåíèå r îøèáîê.Ïðèêëàäíàÿ àëãåáðà135 / 225Êîäû, èñïðàâëÿþùèå îøèáêèÊîäû Á×ÕÏîñòðîåíèå êîäà Á×Õ, èñïðàâëÿþùåãî 3 îøèáêèÏðèìåð (k = 4, ìíîãî÷ëåí äëÿ ðàçëîæåíèÿ: x15 − 1)Ïóñòü íóæåí êîä, èñïðàâëÿþùèé r = 3 îøèáêè. Çíà÷èò, íóæíîíàéòè ìíîãî÷ëåíû, êîðíÿìè êîòîðûõ ÿâëÿþòñÿ ïåðâûå 2r = 6ñòåïåíåé ïîðîæäàþùåãî ýëåìåíòà α.123åñëè ìíîãî÷ëåí èìååò êîðåíüαα3α5òî îí èìååò êîðíèα2 , α4 , α86α , α12 , α9 (= α24 )α10Ïî òð¼ì íàáîðàì êîðíåé ïîñòðîèì òðè ìíîãî÷ëåíà, äâà 4-éñòåïåíè è îäèí 2-é. Ïåðåìíîæèâ èõ, ïîëó÷èì ìíîãî÷ëåí 10-éñòåïåíè.Èäåàë ïî ìîäóëþ ýòîãî ìíîãî÷ëåíà áóäåò 5-ìåðíûìïðîñòðàíñòâîì.Ïðèêëàäíàÿ àëãåáðà136 / 225Êîäû, èñïðàâëÿþùèå îøèáêèÊîäû Á×ÕÑêîëüêî ýëåìåíòîâ ñîäåðæèò èäåàë (ϕ)?ϕ = ïðîèçâåäåíèå íåêîòîðûõ íåïðèâîäèìûõ ìíîãî÷ëåíîâäåëèòåëåé xn − 1.Êàæäûé äåëèòåëü èìååò, êàê ìèíèìóì, 2 êîðíÿ èç ñîâîêóïíîñòè{ α, .
. . , α2r }, ò.å. èõ òðåáóåòñÿ íå áîëåå r øòóê.sÅñëè äåëèòåëü èìååò êîðíÿìè s ýëåìåíòîâ { αm , α2m , . . . , α2 m },òî 2s 6 n = 2k − 1, ò.å. ñòåïåíü êàæäîãî äåëèòåëÿ íå áîëååk = log2 (n + 1).deg ϕ 6 rk = r log2 (n + 1).Èäåàë, ïîðîæäåííûé ϕ, èìååò ðàçìåðíîñòü n − deg ϕ.2n|(ϕ)| 6 2n−r log2 (n+1) = (n+1)r.ßñíî, ÷òî ýòà îöåíêà äàëåêà îò òî÷íîñòè.Ïðèêëàäíàÿ àëãåáðà136 / 225Êîäû, èñïðàâëÿþùèå îøèáêèÊîäû Á×ÕÑêîëüêî ýëåìåíòîâ ñîäåðæèò èäåàë (ϕ)?ϕ = ïðîèçâåäåíèå íåêîòîðûõ íåïðèâîäèìûõ ìíîãî÷ëåíîâäåëèòåëåé xn − 1.Êàæäûé äåëèòåëü èìååò, êàê ìèíèìóì, 2 êîðíÿ èç ñîâîêóïíîñòè{ α, . . .
, α2r }, ò.å. èõ òðåáóåòñÿ íå áîëåå r øòóê.sÅñëè äåëèòåëü èìååò êîðíÿìè s ýëåìåíòîâ { αm , α2m , . . . , α2 m },òî 2s 6 n = 2k − 1, ò.å. ñòåïåíü êàæäîãî äåëèòåëÿ íå áîëååk = log2 (n + 1).deg ϕ 6 rk = r log2 (n + 1).Èäåàë, ïîðîæäåííûé ϕ, èìååò ðàçìåðíîñòü n − deg ϕ.2n|(ϕ)| 6 2n−r log2 (n+1) = (n+1)r.ßñíî, ÷òî ýòà îöåíêà äàëåêà îò òî÷íîñòè.Ïðèêëàäíàÿ àëãåáðàÊîäû, èñïðàâëÿþùèå îøèáêèÊîäû Á×ÕÎöåíêà êîäîâîãî ðàññòîÿíèÿÏîêàæåì, ÷òî ðàññòîÿíèå ìåæäó òî÷êàìè êîäà íå ìåíüøå, ÷åì2r + 1 (÷òî íàì è òðåáóåòñÿ!).137 / 225Ïðèêëàäíàÿ àëãåáðàÊîäû, èñïðàâëÿþùèå îøèáêèÊîäû Á×ÕÎöåíêà êîäîâîãî ðàññòîÿíèÿÏîêàæåì, ÷òî ðàññòîÿíèå ìåæäó òî÷êàìè êîäà íå ìåíüøå, ÷åì2r + 1 (÷òî íàì è òðåáóåòñÿ!).Âñå ìíîãî÷ëåíû, âõîäÿùèå â íàø êîä â èäåàë (ϕ) , êðàòíûϕ ⇒ êàæäûé êîäîâûé ìíîãî÷ëåí èìååò êîðíè α, α2 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
