Коды, исправляющие ошибки (1127158)
Текст из файла
ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè×àñòüIIÊîäû, èñïðàâëÿþùèå îøèáêè1 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÁëîêîâîå êîäèðîâàíèå. Êîäû ÕýììèíãàÐàçäåëû I1Áëîêîâîå êîäèðîâàíèå. Êîäû Õýììèíãà2Ãðóïïîâûå (ëèíåéíûå) êîäûÎïðåäåëåíèå è ñâîéñòâàÊîäèðîâàíèå ëèíåéíûìè êîäàìèÄåêîäèðîâàíèå ëèíåéíûõ êîäîâ3Öèêëè÷åñêèå êîäûÎïðåäåëåíèå, îñíîâíûå ñâîéñòâà, ïðèìåðÊîäèðîâàíèå öèêëè÷åñêèìè êîäàìè è äåêîäèðîâàíèå4Êîäû Áîóçà-×îóäõóðè-ÕîêâèíãåìàÎïðåäåëåíèå è îñíîâíûå ñâîéñòâàÊîäèðîâàíèå Á×Õ-êîäàìèÄåêîäèðîâàíèå êîäîâ Á×Õ5Çàäà÷è ñ ðåøåíèÿìè2 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè3 / 152Áëîêîâîå êîäèðîâàíèå. Êîäû ÕýììèíãàÇàäà÷à ïîìåõîóñòîé÷èâîãî êîäèðîâàíèÿ: ïîäõîäû ê ðåøåíèþÏî êàíàëó ñ øóìîì ïðîõîäèò ïîòîê áèòîâîé èíôîðìàöèè.Ìîäåëü ïîòîêà: ñëó÷àéíûé íåêîððåëèðîâàííûé.Ìîäåëü øóìà: íåêîòîðûå áèòû ñëó÷àéíî è íåçàâèñèìîìîãóò îêàçàòüñÿ èíâåðòèðîâàííûìè (äâîè÷íûéñèììåòðè÷íûé êàíàë, íåò äîáàâëåíèé/ñòèðàíèé áèòîâ).Çàäà÷à: îáåñïå÷èòü àâòîìàòè÷åñêîå èñïðàâëåíèå îøèáîê.Ïîäõîä ê ðåøåíèþ (îäèí èç âîçìîæíûõ!):1âõîäíîé ïîòîê èíôîðìàöèè ðàçáèòü íà ñîîáùåíèÿ íåïåðåñåêàþùèåñÿ áëîêè ôèêñèðîâàííîé äëèíû k ;2êàæäûé áëîê êîäèðîâàòü à) íåçàâèñèìî îò äðóãèõ áëîêîâîå êîäèðîâàíèå;á) â çàâèñèìîñòè îò ïðåäûäóùèõ ñâ¼ðòî÷íîåêîäèðîâàíèå (òóðáî-êîäû è äð.).ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè4 / 152Áëîêîâîå êîäèðîâàíèå. Êîäû ÕýììèíãàÇàäà÷è áëîêîâîãî êîäèðîâàíèÿÄàëåå ðàññìàòðèâàåòñÿ èñêëþ÷èòåëüíî áëîêîâîå êîäèðîâàíèå:åñòü íàáîð âñåõ ñîîáùåíèé S1 , . . . , St , äëèíû k êàæäîå(t = 2k ), êîòîðûå íóæíî ïåðåäàòü ïî êàíàëó ñâÿçè ñ øóìîì;äëÿ îáåñïå÷åíèÿ ïîìåõîçàùèø¼ííîñòè âìåñòî ýòèõ ñîîáùåíèéïåðåäàþò êîäîâûå ñëîâà áëîêè äëèíû n > k êàæäîå.Çàäà÷à (îñíîâíàÿ): ïîñòðîèòü êîä ìèíèìàëüíîé äëèíû n,ïîçâîëÿþùèé âîññòàíîâèòü ñîîáùåíèå, ñîäåðæàùåå íå áîëåår îøèáîê.Çàäà÷à (âñïîìîãàòåëüíàÿ): çàäàíûn äëèíà êîäà (îáû÷íî çàâèñèò îò ïàðàìåòðà(îâ) m, q, . . .);r ìàêñèìàëüíîå êîëè÷åñòâî èñïðàâèìûõ îøèáîê.Òðåáóåòñÿ ïîñòðîèòü êîä ñ ìàêñèìàëüíûì ÷èñëîì t êîäîâûõ ñëîâ(= ñîîáùåíèé, êîòîðûå ìîæíî ïåðåäàòü).ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÁëîêîâîå êîäèðîâàíèå.
Êîäû ÕýììèíãàÍåêîòîðûå ïîíÿòèÿ, ñâÿçàííûå ñ áóëåâûì êóáîìÐåøàåì âñïîìîãàòåëüíóþ çàäà÷ó îíà ïðîùå.Íàïîìèíàíèå èç äèñêðåòíîé ìàòåìàòèêè Íîðìà γe = ÷èñëî åäèíè÷íûõ êîîðäèíàò â γe ∈ Bn.Ìåòðèêà (âñïîìèíàåì, ÷òî ýòî òàêîå) íà ìíîæåñòâåáèíàðíûõ íàáîðîâ õýììèíãîâî ðàññòîÿíèå ( ⊕ ñóììàïî mod 2):ρ αe, βe = αe ⊕ βe .Øàð Õýììèíãà ñ öåíòðîì â αe è ðàäèóñîì r noSr (eα) = βe ∈ B n | ρ αe, βe 6 r .5 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè6 / 152Áëîêîâîå êîäèðîâàíèå. Êîäû ÕýììèíãàÐ.Ó.
ÕýììèíãÐè÷àðä Óýñëè Õýììèíã(Richard Wesley Hamming, 19151998) àìåðèêàíñêèé ìàòåìàòèê, ðàáîòûêîòîðîãî â ñôåðå òåîðèè èíôîðìàöèèîêàçàëè ñóùåñòâåííîå âëèÿíèå íàêîìïüþòåðíûå íàóêè è òåëåêîììóíèêàöèè. 1950 ã. îïóáëèêîâàë ñïîñîá ïîñòðîåíèÿêîäà, èñïðàâëÿþùåãî îäíó îøèáêóè íàçâàííûé âïîñëåäñòâèè åãî èìåíåì.Èíñòèòóò èíæåíåðîâ ïî ýëåêòðîòåõíèêå è ýëåêòðîíèêå (IEEE,Institute of Electrical and Electronics Engineers) ó÷ðåäèë ìåäàëü,êîòîðîé íàãðàæäàþòñÿ ó÷åíûå, âíåñøèå çíà÷èòåëüíûé âêëàä âòåîðèþ èíôîðìàöèè ìåäàëü Ðè÷àðäà Õýììèíãà.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè7 / 152Áëîêîâîå êîäèðîâàíèå. Êîäû ÕýììèíãàÊîäîâîå ðàññòîÿíèå IÎïðåäåëåíèåÌèíèìàëüíîå ðàññòîÿíèå ìåæäó ñëîâàìè êîäà íàçûâàåòñÿêîäîâûì ðàññòîÿíèåì (ñèìâîëè÷åñêè îáû÷íî d).ÓòâåðæäåíèåÌíîæåñòâî C îáðàçóåò êîä ñ èñïðàâëåíèåì íå ìåíåå re = ∅ äëÿ âñåõ αîøèáîê, åñëè Sr (eα) ∩ Sr (β)e, βe ∈ C òàêèõ, ÷òîeαe 6= β .ÄîêàçàòåëüñòâîÅñëè ïðè ïåðåäà÷å ñîîáùåíèÿ αe ñäåëàíî íå áîëåå r îøèáîê,òî íàáîð îñòàíåòñÿ â øàðå Sr (eα).Åñëè øàðû íå ïåðåñåêàþòñÿ, òî èñêîìîå êîäîâîå ñëîâî α áëèæàéøåå ê ïîëó÷åííîìó íàáîðó.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè8 / 152Áëîêîâîå êîäèðîâàíèå. Êîäû ÕýììèíãàÊîäîâîå ðàññòîÿíèå IIÑëåäñòâèåÓ êîäà, èñïðàâëÿþùåãî r îøèáîê, êîäîâîå ðàññòîÿíèå äîëæíîáûòü íå ìåíåå 2r + 1.Îïðåäåëåíèå êîäîâîãî ðàññòîÿíèÿ d ïðîèçâîëüíîãî êîäà ñëîæíàÿ çàäà÷à.Ïîýòîìó ïðè ïîìåõîóñòîé÷èâîì êîäèðîâàíèè íà ïåðâûé ïëàíâûõîäèò ïðîáëåìà ïîñòðîåíèÿ êîäîâ ñ çàäàííûì êîäîâûìðàññòîÿíèåì.Îíà ðåøàåòñÿ ïðè èñïîëüçîâàíèè, íàïðèìåð, ò.í. Á×Õ-êîäîâ,êîòîðûå áóäóò ðàññìîòðåíû äàëåå.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè9 / 152Áëîêîâîå êîäèðîâàíèå.
Êîäû ÕýììèíãàÁëîêîâîå êîäèðîâàíèå è äåêîäèðîâàíèå: îïðåäåëåíèÿ èòðèâèàëüíûé ïðèìåðÁëîêîâîåêîäèðîâàíèåïðåîáðàçîâàíèå ñîîáùåíèé äëèíûäëèíû n > k .kâçàèìíî-îäíîçíà÷íîåâ êîäîâûå ñëîâàÄåêîäèðîâàíèå îïðåäåëåíèå ñîîáùåíèÿ ïî êîäîâîìó ñëîâó.Ïðèìåð (òðèâèàëüíûé êîä k = 1, n = 3, d = 3)Èíôîðìàöèÿ ðàçáèâàåòñÿ íà áëîêè äëèíû k = 1, ò.å.ïåðåäàþòñÿ t = 2 ñîîáùåíèÿ: S0 = 0 è S1 = 1.Êîäèðîâàíèå0 7→ 0001 7→ 111èñïðàâëÿåò îäíó îøèáêó!Îäíàêî òàêîå êîäèðîâàíèå (âûáîð k = 1) êðàéíåíåýôôåêòèâíî: äëèíà ñîîáùåíèÿ óòðàèâàåòñÿ.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè10 / 152Áëîêîâîå êîäèðîâàíèå.
Êîäû ÕýììèíãàÁëîêîâîå êîäèðîâàíèå: îáîçíà÷åíèÿ è îïðåäåëåíèÿÁóäåì îáîçíà÷àòü êàæäîå ñîîáùåíèå âåêòîðîì-ñòîëáöîì(ïîëóæèðíûé øðèôò) u ∈ {0, 1}k :u1u = ··· u1 , . . . , uk èíôîðìàöèîííûå áèòûukÎïðåäåëåíèåv êîäîâîå ñëîâî äëèíû n = k + m, ñîäåðæàùåå ïîìèìîk èíôîðìàöèîííûõ åù¼ è m ïðîâåðî÷íûõ áèò(ðàçäåëèìîå áëîêîâîå êîäèðîâàíèå).Ìíîæåñòâî {v 1 , . . .
, v 2k } âñåõ 2k êîäîâûõ ñëîâ äëèíûn (n, k)-êîä (ñ êîäîâûì ðàññòîÿíèåì (n, k, d)-êîä).R = k/n ñêîðîñòü, m/n = 1 − R èçáûòî÷íîñòü êîäà.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè11 / 152Áëîêîâîå êîäèðîâàíèå. Êîäû ÕýììèíãàÁëîêîâûé (n, k) êîä: êîäèðîâàíèå è îøèáêè ïåðåäà÷èÁëîêîâîå êîäèðîâàíèå íå âûçûâàåò ïðèíöèïèàëüíûõòðóäíîñòåé: îòîáðàæåíèå S → C âñåãäà ìîæåò áûòüîñóùåñòâëåíî ñ èñïîëüçîâàíèåì òàáëèöû ðàçìåðà 2k ×n.Îäíàêî òàêîå ¾òàáëè÷íîå¿ êîäèðîâàíèå âåñüìà íåýôôåêòèâíî:n ìîæåò äîñòèãàòü äåñÿòêîâ è ñîòåí òûñÿ÷.Ïðè ïåðåäà÷å ïî êàíàëó ñ øóìîì êîäîâîå ñëîâî vïðåâðàùàåòñÿ â ïðèíÿòîå ñëîâî w òîé æå äëèíû n:v → w = v + e.Çäåñü e ∈ âåêòîð îøèáîê:1, åñëè â i-îì áèòå ïðîèçîøëà îøèáêà.ei =0, åñëè îøèáêè íåò.d−1îøèáîê.(n, k, d)-êîä ìîæåò èñïðàâèòü íå ìåíåå2{0, 1}nÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÁëîêîâîå êîäèðîâàíèå. Êîäû ÕýììèíãàÁëîêîâûé (n, k) êîä: äåêîäèðîâàíèåÄåêîäèðîâàíèå êîäîâ îáû÷íî çíà÷èòåëüíî ñëîæíååêîäèðîâàíèÿ (èçâåñòíû ò.í.
¾ýêñïàíäåðíûå¿ êîäû ñ ëèíåéíûìäåêîäèðîâàíèåì, äëÿ êîòîðûõ íåèçâåñòíû ñóáêâàäðàòè÷íûåàëãîðèòìû êîäèðîâàíèÿ, íî ýòî èñêëþ÷åíèå...).Äåêîäèðîâàíèå (n, k, d)-êîäà îñíîâàíî íà:ðàçáèåíèè åäèíè÷íîãî êóáà B n íà k îáëàñòåé,ñîäåðæàùèõ øàðû ðàäèóñà r = [ (d − 1)/2 ] ñ öåíòðàìè âêîäîâûõ ñëîâàõ;ïðåäïîëîæåíèè, ÷òî ïðè ïåðåäà÷å ïðîèçîøëî íå áîëåå rîøèáîê.12 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÁëîêîâîå êîäèðîâàíèå. Êîäû ÕýììèíãàÁëîêîâûé (n, k) êîä: äâà ýòàïà äåêîäèðîâàíèÿ1-é ýòàï: Âîññòàíîâëåíèå ïåðåäàííîãî êîäîâîãî ñëîâà vbêàê áëèæàéøåãî ê w â ìåòðèêå Õýììèíãà íàõîæäåíèå öåíòðà ñîîòâåòñòâóþùåãî øàðà.Äëÿ ýòîãî íàäî, âîîáùå ãîâîðÿ, ïåðåáðàòü âñå 2kñòðîê â 2k ×n-òàáëèöå êîäîâûõ ñëîâ.Åñëè ðàññòîÿíèå äî áëèæàéøåãî öåíòðà øàðà(êîäîâîãî ñëîâà) ïðåâûøàåò âåëè÷èíór = [ (d − 1)/2 ], òî ïðè ïåðåäà÷å ïðîèçîøëîáîëüøå îøèáîê, ÷åì ìîæåò èñïðàâèòü êîä èàëãîðèòì äåêîäèðîâàíèÿ äîëæåí âûäàòü îòêàç.b2-é ýòàï: Âîññòàíîâëåíèå ïî vb èñõîäíîãî ñîîáùåíèÿ uïóò¼ì óäàëåíèÿ ïðîâåðî÷íûõ áèò. îáùåì ñëó÷àå ýòî ïîòðåáóåò èñïîëüçîâàíèÿòàáëèöû ðàçìåðà 2k ×k .13 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè14 / 152Áëîêîâîå êîäèðîâàíèå. Êîäû ÕýììèíãàÁëîêîâîå êîäèðîâàíèå: îáùàÿ ñõåìà è ñëîæíîñòüuêîäèðîâàíèåèçáûòî÷íîñòüw vîøèáêà+ew wäåêîä.-1w vbáëèæ. êîä. ñëîâîäåêîä.-2w ubóäàëåíèå èçáûò.Èç ïðèâåä¼ííûõ îöåíîê ñëåäóåò:èñïîëüçîâàíèå áëîêîâîãî (n, k)-êîäà îáùåãî âèäà âîçìîæíîëèøü ïðè íåáîëüøèõ çíà÷åíèÿõ n è k .Îäíàêî, ïðèíÿâ ðÿä äîïîëíèòåëüíûõ îãðàíè÷åíèé íàìíîæåñòâî êîäîâûõ ñëîâ, ìîæíî ïåðåéòè îò ýêñïîíåíöèàëüíûõ(2k ) òðåáîâàíèé ïî ïàìÿòè äëÿ õðàíåíèÿ êîäà è ïî ñëîæíîñòèàëãîðèòìîâ êîäèðîâàíèÿ/äåêîäèðîâàíèÿ ê ëèíåéíûì ïî n è k .Ýòè îãðàíè÷åíèÿ ïðèâîäÿò ê èñïîëüçîâàíèþ áëîêîâûõ êîäîâñïåöèàëüíîãî âèäà: ãðóïïîâûõ, à èç ãðóïïîâûõ öèêëè÷åñêèõ.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêè15 / 152Áëîêîâîå êîäèðîâàíèå.
Êîäû ÕýììèíãàÏëîòíàÿ óïàêîâêà øàðîâ â áóëåâ êóá×òîáû ïîñòðîèòü êîä ìàêñèìàëüíîãî ðàçìåðà, èñïðàâëÿþùèér îøèáîê, íóæíî âëîæèòü â åäèíè÷íûé êóá B n ìàêñèìàëüíîâîçìîæíîå ÷èñëî íåïåðåñåêàþùèõñÿ øàðîâ ðàäèóñà r çàäà÷àïëîòíîé óïàêîâêè.Âîïðîñ: Ïðè êàêèõ n è r â êóá B n ìîæíî óëîæèòüíåïåðåñåêàþùèåñÿ øàðû ðàäèóñà r ¾ïëîòíî¿,¾áåç çàçîðîâ¿?Îòâåò: Òàêîå óäà¼òñÿ â ñëó÷àÿõ:1n = 2m − 1, r = 1 êîäû Õýììèíãà è2n = 23, r = 3 êîä Ãîëåÿ ýòî ñîâåðøåííûå èëè ýêñòðåìàëüíûå êîäû.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÁëîêîâîå êîäèðîâàíèå. Êîäû ÕýììèíãàÊîëè÷åñòâî êîäîâûõ ñëîâÒåîðåìà (Õýììèíãà)Ïðè 2r < n ìàêñèìàëüíîå ÷èñëî t êîäîâûõ ñëîâ íàõîäèòñÿ âïðåäåëàõ2n2n 6 t 6 .nnnnnn++ ...
+++ ... +012r01rÄîêàçàòåëüñòâît åñòü ìàêñèìàëüíîå ÷èñëî íåïåðåñåêàþùèõñÿ øàðîâ ðàäèóñàr, ïîìåùàþùèõñÿ â êóáå B n .Âåðõíÿÿ îöåíêà (ãðàíèöà Õýììèíãà) øàð ðàäèóñà rñîäåðæèò òî÷êè: ñàì öåíòð + âñå òî÷êè ñ îäíîé, äâóìÿ, ..., rèçìåíåííûìè êîîðäèíàòàìè, ò.å. âñåãî n0 + n1 + n2 + nrøòóê è øàðû íå ïåðåñåêàþòñÿ.16 / 152ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü II: Êîäû, èñïðàâëÿþùèå îøèáêèÁëîêîâîå êîäèðîâàíèå.
Êîäû ÕýììèíãàÏðîäîëæåíèå äîêàçàòåëüñòâàÄëÿ îöåíêè ñíèçó ïîñòðîèì íåãðóïïîâîé êîä:123áåðåì ïðîèçâîëüíóþ òî÷êó B n è ñòðîèì âîêðóã íå¼ øàððàäèóñà 2r;áåðåì ïðîèçâîëüíóþ òî÷êó âíå ïîñòðîåííîãî øàðà èñòðîèì âîêðóã íå¼ øàð ðàäèóñà 2r;è ò.ä., êàæäàÿ íîâàÿ òî÷êà âûáèðàåòñÿ âíå ïîñòðîåííûõøàðîâ.  ðåçóëüòàòå:øàðû,âîçìîæíî,ïåðåñåêàþòñÿ,íî êàæäûé øàð çàíèìàåònnn++...+òî÷åê⇒øàðîâíå ìåíåå012r2n ;nnn++ ...
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
