Коды, исправляющие ошибки (1127158), страница 5
Текст из файла (страница 5)
Âûáèðàåì ïîðîæäàþùèé ïîëèíîì g(x).Ìîæíî âûáðàòü ëþáîé äåëèòåëü x7 + 1 ⇒ âûáåðåìg(x) = x3 + x + 1, òîãäà deg g(x) = 3 = m, k = n − m = 4è ïîñòðîåí öèêëè÷åñêèé (7, 4)-êîä.Åãî êîäîâîå ðàññòîÿíèå íàäî âûÿñíÿòü...68 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè69 / 152Öèêëè÷åñêèå êîäûÊîäèðîâàíèå öèêëè÷åñêèìè êîäàìè è äåêîäèðîâàíèåÖèêëè÷åñêèé êîä: ïðèìåð êîäèðîâàíèÿ g(x) = x3 + x + 1...3. Ïðîâåä¼ì êîäèðîâàíèå ïîëèíîìà u(x) = x3 + x2 èëè ââåêòîðíîì ïðåäñòàâëåíèè u = [0011]T (k = 4).3.1. Íåñèñòåìàòè÷åñêîå êîäèðîâàíèå:v(x) = u(x)g(x) = (x3 + x2 )(x3 + x + 1) = x6 + x5 + x4 + x2èëè â âåêòîðíîì ïðåäñòàâëåíèè v = [0010111]T (n = 7).3.2. Ñèñòåìàòè÷åñêîå êîäèðîâàíèå.
Íàõîäèì îñòàòîê r(x) îòäåëåíèÿ ìíîãî÷ëåíà x3 u(x) íà g(x):x3 (x3 + x2 ) = x6 + x5 = (x3 + x2 + x)(x3 + x2 + 1) + x,ïîýòîìó v(x) = x3 u(x) + r(x) = x6 + x5 + xèëè â âåêòîðíîì ïðåäñòàâëåíèè v = [0100011]T (n = 7), ò.å.áèòû âõîäíîãî ñîîáùåíèÿ u âîñïðîèçâîäÿòñÿ â êðàéíèõïðàâûõ áèòàõ êîäîâîãî ñëîâà v .ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÖèêëè÷åñêèå êîäûÊîäèðîâàíèå öèêëè÷åñêèìè êîäàìè è äåêîäèðîâàíèåÖèêëè÷åñêèå êîäû: äåêîäèðîâàíèåÎïðåäåëåíèåÑèíäðîìîì ïðèíÿòîãî ïîëèíîìà w(x), çàêîäèðîâàííîãîöèêëè÷åñêèì (n, k)-êîäîì ñ ïîðîæäàþùèì ïîëèíîìîì g(x)(è, âîçìîæíî, ñîäåðæàùèì îøèáêè), íàçîâ¼ì îñòàòîê s(x) îòäåëåíèÿ w(x) íà g(x): s(x) ≡g(x) w(x).Îïðåäåëåíèå ñèíäðîìà äëÿ öèêëè÷åñêîãî êîäà, î÷åâèäíî, åñòüïåðåôðàçèðîâêà â òåðìèíàõ ïîëèíîìîâ ñèíäðîìà äëÿãðóïïîâûõ êîäîâ.Ñâîéñòâà ñèíäðîìà w(x):s(x) ≡ 0 ⇔ w(x) êîäîâîå ñëîâî;0 6 deg s(x) < m = n − k ;s(x) ≡g(x) (v(x) + e(x)) ≡g(x) e(x).70 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè71 / 152Öèêëè÷åñêèå êîäûÊîäèðîâàíèå öèêëè÷åñêèìè êîäàìè è äåêîäèðîâàíèåÖèêëè÷åñêèå êîäû: äåêîäèðîâàíèå...Äåêîäèðîâàíèå öèêëè÷åñêîãî êîäà ïðîõîäèò ïî îáùåé ñõåìåäåêîäèðîâàíèÿ ëèíåéíîãî êîäà:1âû÷èñëÿåòñÿ ñèíäðîì s(x) ïðèíÿòîãî ñëîâà w(x);2èùóòñÿ ðåøåíèÿ ñèñòåìû e(x) = s(x) + g(x)u(x) äëÿ âñåõ2k âîçìîæíûõ ïîëèíîìîâ u(x) ñòåïåíè k − 1(ýêñïîíåíöèàëüíàÿ ñëîæíîñòü ïî k );3îïðåäåëÿåòñÿ ïîëèíîì îøèáîê êàê ðåøåíèå ñìèíèìàëüíûì ÷èñëîì íåíóëåâûõ ñëàãàåìûõ;4âîññòàíàâëèâàåòñÿ ïåðåäàííîå ñîîáùåíèåu(x) = w(x) + e(x).Ïðèìåðû äåêîäèðîâàíèÿ öèêëè÷åñêèõ êîäîâ (ñ îäíîé îøèáêîé)áóäóò äàíû ïðè ðàññìîòðåíèè Á×Õ-êîäîâ.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÖèêëè÷åñêèå êîäûÊîäèðîâàíèå öèêëè÷åñêèìè êîäàìè è äåêîäèðîâàíèåÖèêëè÷åñêèå ãðóïïîâîå êîäû (n, k): ðåçþìåËèíåéíû êîäû îáùåãî âèäà ìîãóò èìåòü ïðîèçâîëüíûåïàðàìåòðû äëèíû n è ÷èñëà èíôîðìàöèîííûõ áèò k .Ëèíåéíûå öèêëè÷åñêèå êîäû òàêæå ìîãóò èìåòüïðîèçâîëüíóþ äëèíó n, íî ïàðàìåòðû m è,ñëåäîâàòåëüíî, k = n − m (÷èñëî èíôîðìàöèîííûõ áèò)óæå íå ïðîèçâîëüíû: ïîëèíîì g(x) ñòåïåíè m äîëæåíäåëèòü áèíîì xn − 1.Öèêëè÷åñêèé êîä áóäåò ãðóïïîâûì, òîëüêî åñëè îíïðèíàäëåæèò èäåàëó (g(x)) , deg g(x) = m êîëüöàìíîãî÷ëåíîâ F2 [x]: â í¼ì öèêëè÷åñêèå ñäâèãè êîäîâîãîñëîâà ïîëó÷àþòñÿ óìíîæåíèåì íà x, x2 , . . ., ÷òî èîáåñïå÷èâàåòñÿ ðàâåíñòâîì xn = 1.72 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè73 / 152Öèêëè÷åñêèå êîäûÊîäèðîâàíèå öèêëè÷åñêèìè êîäàìè è äåêîäèðîâàíèåÖèêëè÷åñêèå ãðóïïîâîå êîäû (n, k): ðåçþìå...Êîäèðîâàíèå ïðîèçâîäèòñÿ óìíîæåíèåì ñîîáùåíèÿ íàïîëèíîì g(x).
Îäíàêî âûáîð g(x), ïîðîæäàþùåãî êîä ñáîëüøèì êîäîâûì ðàññòîÿíèåì d ñëîæíàÿ çàäà÷à(îöåíêà ñâåðõó: d 6 m + 1 ÷èñëî ìîíîìîâ â g(x)).Äåêîäèðîâàíèå îñóùåñòâëÿåòñÿ ñ ïîìîùüþ âû÷èñëÿåìîãîñèíäðîìà ïðèíÿòîãî ïîëèíîìà, â ðåçóëüòàòå:âìåñòî ìàòðè÷íûõ óìíîæåíèé è ðåøåíèÿ ÑËÀÓ (êàê âëèíåéíûõ êîäàõ îáùåãî âèäà) èñïîëüçóþòñÿ îïåðàöèèóìíîæåíèÿ è äåëåíèÿ (ñ îñòàòêîì) ïîëèíîìîâ, ëåãêîðåàëèçóåìûå íà ðåãèñòðàõ ñäâèãà ñ îáðàòíûìè ñâÿçÿìè;îäíàêî îáùèé àëãîðèòì äåêîäèðîâàíèÿ ïî-ïðåæíåìó èìååòýêñïîíåíöèàëüíóþ ñëîæíîñòü ïîk.Ñóùåñòâóþò è àëüòåðíàòèâíûå ìåòîäû äåêîäèðîâàíèÿöèêëè÷åñêèõ êîäîâ îáùåãî âèäà (äåêîäåðû Ìåããèòà,Êàñàìè-Ðóäîëüôà, ìàæîðèòàðíûé, ...) òîæå ïëîõèå.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÊîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÐàçäåëû I1Áëîêîâîå êîäèðîâàíèå. Êîäû Õýììèíãà2Ãðóïïîâûå (ëèíåéíûå) êîäûÎïðåäåëåíèå è ñâîéñòâàÊîäèðîâàíèå ëèíåéíûìè êîäàìèÄåêîäèðîâàíèå ëèíåéíûõ êîäîâ3Öèêëè÷åñêèå êîäûÎïðåäåëåíèå, îñíîâíûå ñâîéñòâà, ïðèìåðÊîäèðîâàíèå öèêëè÷åñêèìè êîäàìè è äåêîäèðîâàíèå4Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÎïðåäåëåíèå è îñíîâíûå ñâîéñòâàÊîäèðîâàíèå Á×Õ-êîäàìèÄåêîäèðîâàíèå êîäîâ Á×Õ5Çàäà÷è ñ ðåøåíèÿìè74 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÊîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÎïðåäåëåíèå è îñíîâíûå ñâîéñòâàÐàçäåëû12Áëîêîâîå êîäèðîâàíèå. Êîäû ÕýììèíãàÃðóïïîâûå (ëèíåéíûå) êîäûÎïðåäåëåíèå è ñâîéñòâàÊîäèðîâàíèå ëèíåéíûìè êîäàìèÄåêîäèðîâàíèå ëèíåéíûõ êîäîâ3Öèêëè÷åñêèå êîäûÎïðåäåëåíèå, îñíîâíûå ñâîéñòâà, ïðèìåðÊîäèðîâàíèå öèêëè÷åñêèìè êîäàìè è äåêîäèðîâàíèå4Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÎïðåäåëåíèå è îñíîâíûå ñâîéñòâàÊîäèðîâàíèå Á×Õ-êîäàìèÄåêîäèðîâàíèå êîäîâ Á×Õ5Çàäà÷è ñ ðåøåíèÿìè75 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè76 / 152Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÎïðåäåëåíèå è îñíîâíûå ñâîéñòâàÁ×Õ-êîäû: ïåðâûå ñâåäåíèÿÊîäû Áîóçà-×îóäõóðè-Õîêâèíãåìà (Á×Õ, BCH) ïîäêëàññöèêëè÷åñêèõ êîäîâ, èñïðàâëÿþùèõ íå ìåíåå çàðàíåå çàäàííîãî÷èñëà îøèáîê.Ïðåäëîæåíû Ð.×.
Áîóçîì è Ä.Ê. Ðåé-×îóäõóðè â 1960 ã.íåçàâèñèìî îò îïóáëèêîâàííîé íà ãîä ðàíåå ðàáîòûÀ. Õîêâèíãåìà.Òåîðåòè÷åñêè êîäû Á×Õ ìîãóò èñïðàâëÿòü ïðîèçâîëüíîåêîëè÷åñòâî îøèáîê, íî ïðè ýòîì ñóùåñòâåííî óâåëè÷èâàåòñÿäëèíà êîäîâîãî ñëîâà n, ÷òî ïðèâîäèò ê óìåíüøåíèþ ñêîðîñòèïåðåäà÷è äàííûõ è óñëîæíåíèþ ïðè¼ìíî-ïåðåäàþùåéàïïàðàòóðû.Êîäû Õýììèíãà ÷àñòíûé ñëó÷àé Á×Õ-êîäîâ.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÊîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÎïðåäåëåíèå è îñíîâíûå ñâîéñòâàÐ.×. Áîóç è Ä.Ê. Ðåé-×îóäõóðèÐàäæ ×àíäðà Áîóç (Áîøó)(Raj Chandra Bose, 19011987) èíäèéñêèé ìàòåìàòèê, ðàáîòàâøèé â ÑØÀ.Èçâåñòåí ðàáîòîé (â ñîàâòîðñòâå),îïðîâåðãàþùåé ãèïîòåçó Ë.
Ýéëåðàî íåñóùåñòâîâàíèè ëàòèíñêèõ êâàäðàòîâñïåöèàëüíîãî âèäà.Äâàéäæåíäðà Êàìàð Ðåé-×îóäõóðè(Dwijendra Kumar Ray-Chaudhuri, 1933) èíäèéñêèé ìàòåìàòèê, ðàáîòàþùèé â ÑØÀ.Îáëàäàòåëü ìåäàëè Ýéëåðà, ïðèñóæäàåìîéÈíñòèòóòîì êîìáèíàòîðèêè è ïðèëîæåíèé(Institute of Combinatorics and its Applications,Êàíàäà) çà âêëàä â ðàçâèòèå êîìáèíàòîðèêè.77 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè78 / 152Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÎïðåäåëåíèå è îñíîâíûå ñâîéñòâàÀ. ÕîêâèíãåìÀëåêñèñ Õîêâèíãåì(Alexis Hocquenghem, 1908?1990) ôðàíöóçñêèé ìàòåìàòèê. åãî ðàáîòå 1959 ã. ñîäåðæèòñÿ ïåðâîåîïèñàíèå ëèíåéíûõ öèêëè÷åñêèõ êîäîâ,èñïðàâëÿþùèõ êðàòíûå îøèáêè.Hocquenghem ÿâëÿåòñÿ ãàëèöèíèçèðîâàííîé ôîðìîéãåðìàíñêîé èëè ôëàìàíäñêîé ôàìèëèè.Ïðàâèëüíîå å¼ ÷òåíèå Îêåíãåì.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÊîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÎïðåäåëåíèå è îñíîâíûå ñâîéñòâàÑâîéñòâà ìèíèìàëüíûõ ìíîãî÷ëåíîâ mβ (x) ïîëÿ FnpÂñïîìèíàåì:1∀ β ∈ Fnp ∃! mβ (x) è deg mβ (x) 6 n;2Åñëè3.f (β) = 0 ⇒ f (x) ..
mβ (x);4Ìèíèìàëüíûé ìíîãî÷ëåí íåïðèâîäèì.5Ìèíèìàëüíûé ìíîãî÷ëåí ãåíåðàòîðà ìóëüòèïëèêàòèâíîéãðóïïû ïîëÿ (ïðèìèòèâíîãî ýëåìåíòà) íàçûâàåòñÿïðèìèòèâíûì ìíîãî÷ëåíîì.Fnp = Fp [x]/(a(x)), òî a−1n a(x) ì.ì. äëÿ x;Åñëè β êîðåíü íåïðèâîäèìîãî ìíîãî÷ëåíà ϕ(x) ∈ Fp [x]ñòåïåíè n, òîno2n−1β, β p , β p , . . . , β p âñå n ðàçëè÷íûõ (ñîïðÿæ¼ííûõ) êîðíåé ϕ(x).79 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè80 / 152Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÎïðåäåëåíèå è îñíîâíûå ñâîéñòâàÖèêëîòîìè÷åñêèé ñîïðÿæ¼ííûé êëàññ ýëåìåíòà ïîëÿÎïðåäåëåíèå (äëÿ ñëó÷àÿ p = 2)Ïóñòü n | N .Öèêëîòîìè÷åñêèì êëàññîì (èëè êëàññîì ñîïðÿæ¼ííîñòè) íàäïîëåì Fn2 ýëåìåíòà α ∈ FN2 íàçûâàåòñÿ ìíîæåñòâî âñåõNðàçëè÷íûõ ýëåìåíòîâ F2 , ÿâëÿþùèõñÿ 2n -ìè ñòåïåíÿìè α.Ñâîéñòâà öèêëîòîìè÷åñêèõ êëàññîâÖèêëîòîìè÷åñêèå êëàññû ñîïðÿæ¼ííîñòè ðàçëè÷íûõýëåìåíòîâ ëèáî ñîâïàäàþò, ëèáî íå ïåðåñåêàþòñÿ.Ò.å.
ñîâîêóïíîñòü âñåõ öèêëîòîìè÷åñêèõ êëàññîâ ïîëÿ FN2îáðàçóåò åãî ðàçáèåíèå åãî ìóëüòèïëèêàòèâíîé ãðóïïû.non2n(k−1)nÖèêëîòîìè÷åñêèé êëàññ α, α2 , α2 , . . . , α2íàäïîëåì Fn2 ïðèìèòèâíîãî ýëåìåíòà α ïîëÿðîâíî k ýëåìåíòîâ.Fkn2 ñîäåðæèòÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè81 / 152Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÎïðåäåëåíèå è îñíîâíûå ñâîéñòâàÑâîéñòâà öèêëîòîìè÷åñêèõ êëàññîâ...Ïðèìåðû.Ðàññìîòðèì ðàçëîæåíèÿ ìóëüòèïëèêàòèâíûõ ãðóïï ïîëåéíà öèêëîòîìè÷åñêèå êëàññû íàä Fn2 .123Fkn2n = 1, k = 3 è α ïðèìèòèâíûé ýëåìåíò F32 = F .Òîãäà α7 = 1 è ðàçëîæåíèå F ∗ íàä F2 åñòü{ 1 }, { α, α2 , α4 }, { α3 , α6 , α12 = α5 }.n = 2, k = 2 è α ïðèìèòèâíûé ýëåìåíò F42 = F .Òîãäà α15 = 1 è ðàçëîæåíèå F ∗ íàä F22 åñòü{ 1 }, { α, α4 }, { α2 , α8 }, { α3 , α12 }, { α5 }, { α10 },{ α6 , α9 }, { α7 , α13 }, { α11 , α14 }.n = 1, k = 4 è α ïðèìèòèâíûé ýëåìåíò F42 = F .Òîãäà α15 = 1 è ðàçëîæåíèå F ∗ íàä F2 åñòü{ 1 }, { α, α2 , α4 , α8 }, { α3 , α6 , α12 , α24 = α9 },{ α5 , α10 }, { α7 , α14 , α28 = α13 , α26 = α11 }.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
