Коды, исправляющие ошибки (1127158), страница 2
Текст из файла (страница 2)
+012røàðû ðàäèóñà r ñ öåíòðàìè â âûáðàííûõ òî÷êàõ íåïåðåñåêàþòñÿ.17 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÁëîêîâîå êîäèðîâàíèå. Êîäû ÕýììèíãàÈëëþñòðàöèÿ ê òåîðåìå Õýììèíãà18 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÁëîêîâîå êîäèðîâàíèå. Êîäû ÕýììèíãàÃðàíèöà ÂàðøàìîâàÃèëüáåðòàÇàìå÷àíèå: îöåíêà íèæíåé ãðàíèöû êîëè÷åñòâà t êîäîâûõñëîâ, èñïðàâëÿþùèõ r îøèáîê â ïîëå GE(pn ) pn 6 t.nnn012r(p − 1) +(p − 1) + . . .
+(p − 1)012rÐîì Ðóáåíîâè÷ Âàðøàìîâ (19271999) ÷ë.-êîðð. ÀÍ ÀðìÑÑÐ, îñíîâîïîëîæíèêàëãåáðàè÷åñêîé òåîðèè êîäèðîâàíèÿ.Ýäãàð Ãèëüáåðò (Edgar Nelson Gilbert,19232013) àìåðèêàíñêèé ìàòåìàòèê,ñïåöèàëèñò â îáëàñòè òåîðèè êîäèðîâàíèÿ.19 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè20 / 152Áëîêîâîå êîäèðîâàíèå. Êîäû ÕýììèíãàÊîä Õýììèíãà n = 2m − 1, r = 1: ïîñòðîåíèån2Ïîêàæåì, ÷òî â ñëó÷àå n = 2m − 1 ïîëó÷èì t = 1+n, ò.å. âåðõíÿÿîöåíêà â òåîðåìå Õýììèíãà äîñòèãàåòñÿ.Ïîñòðîèì êîä, à ïîòîì îïðåäåëèì åãî êîäîâîå ðàññòîÿíèå.Ðàññìîòðèì òàáëèöó: 100 . .
. 0001100 . . . 000010...0001010. . . 000001...0001001. . . 000m......k = 2 −(m+1)000...1001111. . . 101000...0101111. . . 110000 . . . 0011111 . . . 111|{z}k = 2m −(m+1)|{zm}Ñëåâà åäèíè÷íàÿ ìàòðèöà ïîðÿäêà 2m − (m + 1), ñïðàâà âñåáèíàðíûå íàáîðû äëèíû m, ñîäåðæàùèå íå ìåíåå äâóõ åäèíèö.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè21 / 152Áëîêîâîå êîäèðîâàíèå. Êîäû ÕýììèíãàÊîä Õýììèíãà n = 2m − 1, r = 1: êîäîâîå ðàññòîÿíèåÏðîñóììèðóåì âñåâîçìîæíûå ñîâîêóïíîñòè ñòðîê ýòîémòàáëèöû, ïîëó÷èâ âñåãî 2k = 22 −(m+1) ðàçëè÷íûõíàáîðîâêîäîâûõ ñëîâ. Íî22m −(m+1)m=22 −12m=2nn+1= max t.Íàéä¼ì êîäîâîå ðàññòîÿíèå ïîñòðîåííîãî êîäà:â êàæäîé ñòðîêå òàáëèöû íå ìåíåå 3 åäèíèö;åñëè ñëîæèòüäâå ñòðîêè â ëåâîé ÷àñòè áóäåò 2 åäèíèöû, à âïðàâîé õîòÿ áû 1,íå ìåíåå òð¼õ ñòðîê â ëåâîé ÷àñòè áóäåò íå ìåíåå 3åäèíèö.Ò.å.
âñåãäà ρ αe, βe > 3 ⇒ øàðû åäèíè÷íîãî ðàäèóñà ñöåíòðàìè â ïîëó÷åííûõ íàáîðàõ íå ïåðåñåêàþòñÿ.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè22 / 152Áëîêîâîå êîäèðîâàíèå. Êîäû ÕýììèíãàÊîä Õýììèíãà äëèíû 7Ïðèìåð ( m = 3, n = 23 − 1 = 7, k = 7 − 3 = 4)Äëÿ äàííîãî ïàðàìåòðà mÕýììèíãà:1 00 10 00 0= 3 ñîñòàâèì òàáëèöó êîäà00100001110110110111Ñêëàäûâàÿ ïî mod 2 âñå ñîâîêóïíîñòè ïðèâåä¼ííûõ 4 ñòðîê(âêëþ÷àÿ ïóñòóþ), ïîëó÷àåì 24 = 16 ðàçëè÷íûõ áèíàðíûõñëîâ äëèíû 7, êîòîðûìè ìîæíî çàêîäèðîâàòü 16 ñîîáùåíèé.Ýòè êîäîâûå ñëîâà ðàñïîëàãàþòñÿ â 0-ì, 3-ì, 4-ì è 7-ì ñëîÿõåäèíè÷íîãî êóáà B 7 .ßâëÿåòñÿ ëè êîäîì Õåììèíãà òðèâèàëüíûé (3, 1)-êîä?ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè23 / 152Áëîêîâîå êîäèðîâàíèå.
Êîäû ÕýììèíãàÊîä Ãîëåÿ (23, 12, 7)-êîä äàííîì ñëó÷àå âåðõíÿÿ ãðàíèöà ÷èñëà âëîæåííûõ øàðîâðàäèóñà 3 â 23-ìåðíûé åäèíè÷íûé êóát =2231 + 23 +23·221·2+23·22·211·2·3=223223= 11 = 212 = 409620482òàêæå äîñòèãàåòñÿ, ò.å. èìååì ïëîòíóþ óïàêîâêó, êàê è â êîäàõÕýììèíãà (ñîâïàäåíèå ëîãàðèôìà t = 212 è ÷èñëàèíôîðìàöèîííûõ áèò k = 12 ñëó÷àéíî).Äðóãèõ ïàð (n, r), óäîâëåòâîðÿþùèõ óñëîâèþ2n nnn++ ...
+01ríåèçâåñòíî. öåëîåÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè24 / 152Áëîêîâîå êîäèðîâàíèå. Êîäû ÕýììèíãàÌ. ÃîëåéÌàðñåëü Ãîëåé(Marcel J. E. Golay, 19021989) øâåéöàðñêèé ìàòåìàòèê è ôèçèê,ðàáîòàâøèé â ÑØÀ è çàíèìàâøèéñÿïðîáëåìàìè ãàçîâîé õðîìàòîãðàôèèè îïòè÷åñêîé ñïåêòðîñêîïèè. ñâîåé åäèíñòâåííîé ðàáîòå ïî òåîðèèèíôîðìàöèè (1949) ïðåäëîæèëñîâåðøåííûé äâîè÷íûé êîä, èñïðàâëÿþùèé òðè îøèáêè. õîäå êîñìè÷åñêîé ïðîãðàììûÂîÿäæåð (1979-81) äëÿ ïåðåäà÷èöâåòíûõ èçîáðàæåíèé Þïèòåðà è Ñàòóðíàèñïîëüçîâàëñÿ êîä Ãîëåÿ.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè25 / 152Áëîêîâîå êîäèðîâàíèå. Êîäû ÕýììèíãàÃðàíèöà ÏëîòêèíàÏóñòü t(n, d) ìàêñèìàëüíî âîçìîæíîå êîëè÷åñòâî êîäîâûõñëîâ ñðåäè âñåõ äâîè÷íûõ êîäîâ äëèíû n ñ êîäîâûìðàññòîÿíèåì d.Ãðàíèöà Ïëîòêèíà äà¼ò âåðõíèé ïðåäåë t(n, d).ÒåîðåìàÅñëè d 12÷¼òíî è 2d > n, òîdt(n, d) 6 2;2d − níå÷¼òíî è 2d + 1 > n, òîd+1t(n, d) 6 2.2d + 1 − nÑóùåñòâóþò êîäû, äëÿ êîòîðûõ ãðàíèöà Ïëîòêèíà äîñòèãàåòñÿ.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÃðóïïîâûå (ëèíåéíûå) êîäûÐàçäåëû I1Áëîêîâîå êîäèðîâàíèå. Êîäû Õýììèíãà2Ãðóïïîâûå (ëèíåéíûå) êîäûÎïðåäåëåíèå è ñâîéñòâàÊîäèðîâàíèå ëèíåéíûìè êîäàìèÄåêîäèðîâàíèå ëèíåéíûõ êîäîâ3Öèêëè÷åñêèå êîäûÎïðåäåëåíèå, îñíîâíûå ñâîéñòâà, ïðèìåðÊîäèðîâàíèå öèêëè÷åñêèìè êîäàìè è äåêîäèðîâàíèå4Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÎïðåäåëåíèå è îñíîâíûå ñâîéñòâàÊîäèðîâàíèå Á×Õ-êîäàìèÄåêîäèðîâàíèå êîäîâ Á×Õ5Çàäà÷è ñ ðåøåíèÿìè26 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÃðóïïîâûå (ëèíåéíûå) êîäûÎïðåäåëåíèå è ñâîéñòâàÐàçäåëû12Áëîêîâîå êîäèðîâàíèå. Êîäû ÕýììèíãàÃðóïïîâûå (ëèíåéíûå) êîäûÎïðåäåëåíèå è ñâîéñòâàÊîäèðîâàíèå ëèíåéíûìè êîäàìèÄåêîäèðîâàíèå ëèíåéíûõ êîäîâ3Öèêëè÷åñêèå êîäûÎïðåäåëåíèå, îñíîâíûå ñâîéñòâà, ïðèìåðÊîäèðîâàíèå öèêëè÷åñêèìè êîäàìè è äåêîäèðîâàíèå4Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÎïðåäåëåíèå è îñíîâíûå ñâîéñòâàÊîäèðîâàíèå Á×Õ-êîäàìèÄåêîäèðîâàíèå êîäîâ Á×Õ5Çàäà÷è ñ ðåøåíèÿìè27 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÃðóïïîâûå (ëèíåéíûå) êîäûÎïðåäåëåíèå è ñâîéñòâàÃðóïïîâûå êîäû: îïðåäåëåíèåÁîëüøàÿ ÷àñòü òåîðèè áëîêîâîãî êîäèðîâàíèÿ ïîñòðîåíà íàëèíåéíûõ êîäàõ, ïîçâîëÿþùèõ ðåàëèçîâûâàòü ýôôåêòèâíûåàëãîðèòìû êîäèðîâàíèÿ/äåêîäèðîâàíèÿ.
 äâîè÷íîì ñëó÷àå èõíàçûâàþò ãðóïïîâûìè, ò.ê. îíè îáðàçóþò ãðóïïó îòíîñèòåëüíî ⊕.Óòâåðæäåíèå 1Óñòîé÷èâàÿ ñîâîêóïíîñòü êîäîâûõ ñëîâ C = αe , ..., αetîáðàçóåò ãðóïïó ïî ñëîæåíèþ îòíîñèòåëüíî îïåðàöèè ⊕.ÄîêàçàòåëüñòâîÓñòîé÷èâîñòü (ïðåäïîëàãàåòñÿ): äëÿ ëþáûõ êîäîâûõ ñëîâαei , αej ∈ C âûïîëíÿåòñÿ αei ⊕ αej = αek ∈ C ;Àññîöèàòèâíîñòü: ñâîéñòâî îïåðàöèè ⊕ ;defÑóùåñòâîâàíèå 0: αe⊕αe = ( 0, . . . , 0 ) = e0 ∈ C;Ïðîòèâîïîëîæíûå ýëåìåíòû: −eα = αe ñì. âûøå.28 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè29 / 152Ãðóïïîâûå (ëèíåéíûå) êîäûÎïðåäåëåíèå è ñâîéñòâàÑâîéñòâî êîäîâîãî ðàññòîÿíèÿ ãðóïïîâîãî êîäàÒåîðåìàÊîäîâîå ðàññòîÿíèå d ãðóïïîâîãî êîäà C ðàâíîd = min ρ αe, βe = min keγ k,αe6=βeγe6=e0ãäå αe, βe è γe êîäîâûå ñëîâà èç C .ÄîêàçàòåëüñòâîÄëÿ ïðîèçâîëüíûõ êîäîâûõ ñëîâeè βe âñåãäà ñóùåñòâóåò èõ αñóììà êîäîâîå ñëîâî γ : ρ αe, βe = αe ⊕ βe = keγ k,ïðè÷åì γe 6= e0 ïðè αe 6= βe.Îòñþäà ïîëó÷àåì îöåíêó min ρ αe, βe > min keγ k, êîòîðàÿαe6=βeäîñòèãàåòñÿ, íàïðèìåð, ïðè βe = e0.γe6=e0ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè30 / 152Ãðóïïîâûå (ëèíåéíûå) êîäûÎïðåäåëåíèå è ñâîéñòâàÕàðàêòåðèñòèêè êîäà Õýììèíãà:ãðóïïîâîé ( 2m − 1, 2m − 1 − m, 3 )-êîä (èñïðàâëÿåò îäíóîøèáêó);ñîâåðøåííûé êîä: îñóùåñòâëÿåò ïëîòíóþ óïàêîâêó 2nmmêóá B 2 −1 ðàçáèâàåòñÿ íà t == 22 −(m+1) øàðîân+1ðàäèóñà r = 1 ñ öåíòðàìè â êîäîâûõ ñëîâàõ.mèçáûòî÷íîñòü m;2 −1Èñòîðè÷åñêàÿ ñïðàâêà. Ïåðâîé ÝÂÌ, â êîòîðîéèñïîëüçîâàëñÿ êîä Õýììèíãà, áûëà IBM 7030, ïîñòðîåííàÿ â1960 ã.
(÷åðåç 10 ëåò ïîñëå ïîÿâëåíèÿ êîäà Õýììèíãà).Äî ýòîãî â âû÷èñëèòåëüíûõ ìàøèíàõ èñïîëüçîâàëñÿ ëèøüïðîñòåéøèé ñïîñîá ïîâûøåíèÿ íàäåæíîñòè ïðîâåðêà íà÷åòíîñòü.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè31 / 152Ãðóïïîâûå (ëèíåéíûå) êîäûÎïðåäåëåíèå è ñâîéñòâàËèíåéíûå êîäû: îïðåäåëåíèå{0, 1}n n-ìåðíîå êîîðäèíàòíîå âåêòîðíîå ïðîñòðàíñòâî íàäêîíå÷íûì ïîëåì F2 = {0, 1}.ÎïðåäåëåíèåÁëîêîâûé (n, k)-êîä C íàçûâàåòñÿ ëèíåéíûì, åñëè îí îáðàçóåòâåêòîðíîå ïîäïðîñòðàíñòâî ðàçìåðíîñòè k êîîðäèíàòíîãîïðîñòðàíñòâà {0, 1}n (äâîè÷íûé ñëó÷àé).Ýòî îçíà÷àåò, ÷òî â ëèíåéíîì êîäå C 12ñóììà ëþáûõ êîäîâûõ ñëîâ êîäîâîå ñëîâî;êîäîâîå ðàññòîÿíèå d = min keγ k;γe∈C3ñóùåñòâóåò áàçèñ èç k âåêòîðîâ { g 0 , g 1 , .
. . , g k−1 } è ëþáîéâåêòîð v ∈ C ìîæåò áûòü ïðåäñòàâëåí êàêk−1Xv =ui g i , ui ∈ {0, 1}.i=0ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè32 / 152Ãðóïïîâûå (ëèíåéíûå) êîäûÎïðåäåëåíèå è ñâîéñòâàËèíåéíûé êîä: ìàòðè÷íîå ïðåäñòàâëåíèåv =k−1Xui g i = Gu , ãäå Gn×k = [ g 0 g 1 . . . g k−1 ] i=0 ïîðîæäàþùàÿ ìàòðèöà êîäà.Ïðèìåð ( (7, 4)-êîä Õýììèíãà)Ðàíåå áûëà ïîëó÷åíà òàáëèöà, ñëîæåíèåì ïðîèçâîëüíûõ ñòðîêêîòîðîé ïîëó÷àþòñÿ âñå 24 = 16 êîäîâûõ ñëîâ. Ïîðîæäàþùàÿìàòðèöà ïîëó÷àåòñÿ òðàíñïîíèðîâàíèåì ýòîé òàáëèöû:1 0 0 00 1 0 00 0 1 0 ïðè êîäèðîâàíèè ýòîé ìàòðèöåéèñõîäíûå ñîîáùåíèÿ ïîìåùàþòñÿG7×4 = 0 0 0 1â ïåðâûå 4 áèòà êîäîâîãî ñëîâà1 1 0 11 0 1 10 1 1 1ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
