А.Б. Угольников - Лекции по дискретной математике (1083729), страница 5
Текст из файла (страница 5)
ßñíî, ÷òî |Vi | = 2n−λ(vi ) .  ñèëó ïðåäûäóùåãîñìîòðèì ìíîæåñòâîóòâåðæäåíèÿBn ⊆m[Vi ,i=1îòêóäà2n 6mX2n−λ(vi ) ,i=1Vi ∩ Vj = ∅,ïðè÷¼ì ðàâåíñòâî âîçìîæíî ëèøü â ñëó÷àåïðèi 6= j ,ò.å. åñëè êîä ïðåôèêñíûé. Âñèëó íåðàâåíñòâà Êðàôòà-Ìàêìèëëàíà2n >mX2n−λ(vi ) .i=1Ïîýòîìón2 =mX2n−λ(vi ) ,i=1è êîä ïðåôèêñíûé.Îáðàòíî, ïóñòü êîäV ïðåôèêñíûé êîä, óäîâëåòâîðÿþùèé (1).  ñèëó ïðåôèêñíîñòè îí ðàç-β , òàêîåi 6= j. Ïîýòîìóm m m[ G X 2n−λ(vi ) Vi = Vi = äåëèìûé, è íóæíî ïîêàçàòü òîëüêî ïîëíîòó. Âîçüì¼ìïðåôèêñíûé, òîVi ∩ Vj = ∅,ïðèi=1i=1Åñëèβíå ïðåäñòàâëÿåòñÿ â âèäåβ = vi γ ,i=1òîm[|B | > Vi ,ni=125÷òîn = λ(β) > λmax .Ò.ê.
êîäò.å.mX2n >2n−λ(vi )i=1 ïðîòèâîðå÷èå ñ (1). Ò.î. êîäVóäîâëåòâîðÿåò óñëîâèþ ïðåäûäóùåãî óòâåðæäåíèÿ. Òåîðåìà äîêà-çàíà.Ñëåäñòâèå. Ïóñòü V = {v1 , ..., vm } ïðåôèêñíûé êîä, òîãäà ñóùåñòâóåò ïðåôèêñíûé è ïîëíûé êîä V 0 òàêîé, ÷òî âûïîëíåíî íåðàâåíñòâî λ(vi0 ) 6 λ(vi ).Äîêàçàòåëüñòâî. Ïóñòü li = λ(vi ). Ïî íåðàâåíñòâó Êðàôòà-ÌàêìèëëàíàmX2−li 6 1.i=1ÅñëèmX2−li = 1,i=1òî ïî êðèòåðèþ ïîëíîòû ïîëó÷àåì, ÷òîV ïîëíûé.
Ðàçáåð¼ì ñëó÷àémX2−li < 1.i=1 ýòîì ñëó÷àå ñïðàâåäëèâîmX2−li + 2−λmax 6 1.i=1Ïóñòü lj= λmax .Òîãäà1−mX2−li > 2−lj + 2−lj = 2−(lj −1) .i=1i6=jÏîëîæèìli0 =li ,i 6= jlj − 1, i = j0Äëÿ ÷èñåë li âûïîëíÿåòñÿmX02−li 6 1.(2)i=1Çíà÷èò, ïî óòâåðæäåíèþ èç ïðåäûäóùåé ëåêöèè ñóùåñòâóåò ïðåôèêñíûé êîä0äëèíàìè êîäîâûõ ñëîâ li , òàêèõ ÷òîmPi=1li0<mPli .0V 0 = {v10 , ..., vm}ñÅñëè â (2) ïî ïðåæíåìó ñòðîãîå íåðàâåíñòâî,i=1mPli0 ïîëó÷èì, ÷òî ðàíî èëèi=1ïîçäíî â íåðàâåíñòâå Êðàôòà-Ìàêìèëëàíà äîñòèãíåòñÿ ðàâåíñòâî.
Ñëåäñòâèå äîêàçàíî.òî ïðèìåíèì îïèñàííóþ ïðîöåäóðó ê íåìó, è ò.ä. Âåäÿ èíäóêöèþ ïîÏóñòüA = {a1 , ..., am }, P = {p1 , ..., pm } ðàñïðåäåëåíèå âåðîÿòíîñòåé ïîÿâëåíèÿ áóêâ â òåêñòå:mXpi = 1.i=1Ïîñòàâèì çàäà÷ó: äëÿ çàäàííîãîPïîñòðîèòü ðàçäåëèìûé êîäVîïòèìàëüíûé â ñìûñëå ìàòåìà-òè÷åñêîãî îæèäàíèÿ äëèíû êîäèðóþùåãî ñëîâà. Ôîðìàëüíî: ââåä¼ìLV (P ) =mXi=126pi λ(vi )èL(P ) =ÅñëèLV (P ) = L(P ),òîãäàVíàçûâàåòñÿinfV −ðàçä.LV (P ).îïòèìàëüíûì.Ðàññìîòðèì ñâîéñòâà îïòèìàëüíûõ êîäîâ:1) Îïòèìàëüíûé êîä ñóùåñòâóåò. Äåéñòâèåòëüíî, äëÿ ëþáîãîMñóùåñòâóåò ëèøü êîíå÷íîå ÷èñëî ðàçëè÷íûõ êîäîâLV (P ) äîñòèãàåòñÿ îáÿçàòåëüíî íà êàêîìV îïòèìàëüíûé êîä, òî ñóùåñòâóåò V 0 V,V LV (P ) > 1, êðîìå òîãî äëÿ ëþáîãîLV (P ) < M. Ïîýòîìó íèæíÿÿV.òàêèõ ÷òîãðàíü ïîëèáî êîäå2) Åñëèîïòèìàëüíûé è ïðè ýòîì ïðåôèêñíûé êîä ïîñëåäñòâèþ èç êðèòåðèÿ ïîëíîòû.3) Äëÿ îïòèìàëüíîãî êîäàV = {v1 , ..., vm }ñïðàâåäëèâîpi > pj ⇒ λ(vi ) 6 λ(vj )vi è vj ïîëó÷èì êîä ñ ìåíüøèì LV (P ).V îïòèìàëüíûé ïðåôèêñíûé êîä, òî ñóùåñòâóþò vi è vj , òàêèå ÷òî λ(vi ) = λ(vj ) = λmax∗è vi = v0, vj = v1, äëÿ íåêîòîðîãî v ∈ B .Òåîðåìà (Ðåäóêöèè).
Ïóñòü V = {v1 , . . . , vm }, m > 2, îïòèìàëüíûé ïðåôèêñíûé êîä ïðè ðàñïðåäåëåíèè P = {p1 , . . . , pm }, p1 > p2 > . . . > pm . Ïóñòü ÷èñëà q0 , q1 òàêîâû, ÷òî â ïðîòèâíîì ñëó÷àå, ïîìåíÿâ ìåñòàìè4) Åñëèq 0 + q 1 = piäëÿ íåêîòîðîãî 1 6 i 6 m, èpm > q 0 > q 1 .Òîãäà W = {v1 , ..., vi−1 , vi+1 , ..., vm , vi 0, vi 1} îïòèìàëüíûé ïðåôèêñíûé êîä äëÿP 0 = {p1 , ..., pi−1 , pi+1 , ..., pm , q0 , q1 }.c Äîêàçàòåëüñòâî. LW (P 0 ) = LV (P ) − pi λ(vi ) + q0 λ(vi 0) + q1 λ(vi 1) = LV (P ) + pi .
Ïóñòü W0cîïòèìàëüíûé êîä ïðè ðàñïðåäåëåíèè P . Òîãäà ñîãëàñíî ñâîéñòâàì 3) è 4) îïòèìàëüíûõ êîäîâ Wèìååò ñëåäóþùóþ ñòðóêòóðó:c = {w1 , w2 , ..., wi−1 , wi+1 , ..., wm , w0, w1}.WÐàññìîòðèì êîäVb = {w1 , w2 , ..., wi−1 , w, wi+1 , ..., wm }.ßñíî, ÷òî0LWb + pi .c (P ) = LVÍî, â ñèëó îïòèìàëüíîñòèV,LV 6 LVb .ÎòêóäàLW 6 LWc.×òî è òðåáîâàëîñü äîêàçàòü.Àëãîðèòì Õàôôìàíà ïîñòðîåíèå îïòèìàëüíîãî êîäà.Ïóñòü òðåáóåòñÿ ïîñòðîèòü îïòèìàëüíûé êîä äëÿ çàäàííîãî óïîðÿäî÷åííîãî ðàñïðåäåëåíèÿ... > pm ,m = 2 ïåðåõîäèì ê ïóíêòó 4;p0 = pm−1 + pm ;03)Îòñîðòèðóåì íàáîð p1 , ..., pm−2 , p ;4)Äëÿ äâóõ ÷èñåë p̂1 , p̂2 ñòðîèì êîäîâûå1)Åñëè2)Ïîëîæèìñëîâà 0 è 1;27p1 >5)Ðàñêðó÷èâàåì íàáîð âåðîÿòíîñòåé â îáðàòíóþ ñòîðîíó, ïðèïèñûâàÿ ê êîäîâûì ñëîâàì 0 è1.Ïðèìåð.(0)p1(0)p2(0)p3(0)p4(0)p5(0)p6(0)p7(0)p8========(1)0, 20, 20, 150, 150, 10, 10, 050, 05(4)p1(4)p1(4)p2(4)p3(4)p4p5(1)p1(1)p2(1)p3(1)p4(1)p5(1)p6(1)p7(3)========(0)(0)p7 + p8 :0, 20, 20, 150, 150, 10, 10, 1(2)p1(2)p1(2)p2(2)p3(2)p4(2)p5(2)p6=======(1)(1)p6 + p6 :0, 20, 20, 20, 150, 150, 1(3)p1(3)p1(3)p2(3)p3(3)p4(3)p5======(2)(2)p5 + p6 :0, 250, 20, 20, 20, 15(3)= p4 + p5 := 0, 35= 0, 25= 0, 2= 0, 2(5)(4)(4)= p3 + p4 := 0, 4= 0, 35= 0, 25p1(5)p1(5)p2(5)p3(6)p1(6)p1(6)p2(5)(5)= p2 + p3 := 0, 6= 0, 4Äåëàåì îáðàòíûé õîä:(6)v1(6)v2= 0= 1(5)v1(5)v2(5)v3(4)= 1= 00= 01(1)v1(1)v2(1)v3(1)v4(1)v5(1)v6(1)v7v1(4)v2(4)v3(4)v4======== 00= 01= 10= 11(0)11000001010011100101v1(0)v2(0)v3(0)v4(0)v5(0)v6(0)v7(0)v8 çàêëþ÷åíèå ïðèâåä¼ì îäíî î÷åâèäíîå(3)v1(3)v2(3)v3(3)v4(3)v5= 01= 10= 11= 000= 001(2)v1(2)v2(2)v3(2)v4(2)v5(2)v6= 10= 11= 000= 001= 010= 011= 11= 000= 001= 010= 100= 101= 0110= 0111Óòâåðæäåíèå.
Åñëè V îïòèìàëüíûé ïðåôèêñíûé êîä, òîãäà V ïîëíûé. Äîêàçàòåëüñòâî. Ïî ñëåäñòâèþ èç êðèòåðèÿ ïîëíîòû.28Ëåêöèÿ 8(22.10.03)Êîäû, èñïðàâëÿþùèå îøèáêèÏîñòàíîâêà çàäà÷è.Èìååòñÿ êàíàë ñâÿçè, ïî êîòîðîìó íåîáõîäèìî ïåðåäàâàòü ñîîáùåíèÿ äâîè÷íûå êîäû (îáùàÿ òåîðèÿ íå ñèëüíî èçìåíèòñÿ, åñëè â êà÷åñòâå àëôàâèòà ñîîáùåíèé âçÿòüáîëåå øèðîêèé àëôàâèò, ÷åì äâîè÷íûé). Êàíàë ñâÿçè èñêàæàåò ñîîáùåíèÿ ñëåäóþùèìè ñïîñîáàìè:1. Îøèáêè òèïà çàìåùåíèÿ: íåêîòîðûå áèòû ñîîáùåíèÿ çàìåíÿþòñÿ íà ïðîòèâîïîëîæíûå.2.
Íåêîòîðûå áèòû ñîîáùåíèÿ ìîãóò òåðÿþòñÿ ïðè ïåðåäà÷å.3.  ñîîáùåíèè ìîãóò ïîÿâëÿòüñÿ íîâûå áèòû.Ââåä¼ì íåêîòîðûå îáîçíà÷åíèÿ. Ïóñòüäëèíûnnn, |B | = 2.BnB n = {α = (α1 , ..., αn ), αi ∈ {0, 1}} ïðîñòðàíñòâî ñëîâîáëàäàåò ñòðóêòóðîé ëèíåéíîãî ïðîñòðàíñòâà íàä ïîëåìçàäà¼òñÿ ñëåäóþùèì îáðàçîì:kαk =nPαi .Ââåä¼ì âBnìåòðèêóρ(α, β) =i=1nPZ2 .Íîðìà âBn|αi − βi | = kα + βk,i=1ãäå ðàçíîñòü áåð¼òñÿ ïî ìîäóëþ 2.Snt (α) ìíîæåñòâî ñëîâ, â êîòîðîå ìîæåò ïåðåéòè α ïðè óñëîâèè âîçíèêíîâåíèÿnt12Níå áîëåå ÷åì t îøèáîê. Ïóñòü B ⊇ Vn = {α , α , ..., α } êîä äëÿ ñëîâ äëèíû n, óñòîé÷èâûé ê íåtitjáîëåå ÷åì t îøèáêàì, ò.å. Sn (α ) ∩ Sn (α ) = ∅, ïðè i 6= j.Îáîçíà÷èì ÷åðåçÄàëåå ìû áóäåì èçó÷àòü òîëüêî êàíàëû ñ âîçìîæíîñòüþ ïîÿâëåíèÿ îøèáîê òîëüêî òèïà çàìå-t.ùåíèÿ, ïðè òîì â êîëè÷åñòâå íå áîëåå, ÷åì= Øtn (α) = {β ∈ B n kα − βk 6 t}tiØn (α )∩tjØn (α )=∅Snt (α) =öåíòðîì â α ðàäèóñà t. ýòîì ñëó÷àåBn øàð âñßñíî, ÷òî óñëîâèåðàâíîñèëüíî ñëåäóþùåìóρ(αi , αj ) > 2t + 1.Ýëåìåíòàðíûå îöåíêè.äàííîãî ðîâíî âiÄëÿ ëþáîãîðàçðÿäàõ.
Ïîýòîìó äëÿ06i6nëþáîãî α|Øtn (α)| =ñóùåñòâóåò ðîâíîtX(1)Cniñëîâ, îòëè÷àþùèõñÿ îòCnii=0Òðèâèàëüíûå îöåíêè ÷èñëà ñî÷åòàíèé äàþò n tt6 Cni 6ntt!Îòêóäàc1 (t)nt 6 |Øtn (α)| 6 c2 (t)nt(2)Èç óñëîâèÿ êîëè÷åñòâà âñåõ ñëîâ è ïóñòîòû ïåðåñå÷åíèÿ øàðîâ äëÿ êîäîâûõ ñëîâ ïîëó÷àåìNX|Øtn (αi )| = N |Øtn (α)| 6 2ni=1Îòêóäà, ó÷èòûâàÿ îöåíêó (2), ïîëó÷àåìN62nc2 (t)ntlog2 N 6 n − t log2 n + c3 (t)(3)(4)Îöåíêà (3) íîñèò íàçâàíèå ãðàíèöà ñôåðè÷åñêîé óïàêîâêè èëè ãðàíèöà Õåììèíãà.Ïîêàæåì, ÷òî èìåÿ â ðàñïîðÿæåíèè íåêîòîðûåñòàòî÷íî áîëüøîé êîäVnt .tn è t, âñåãäà ìîæíî ïîñòðîèòü íåêîòîðûé äîi) ∩ Øtn (αj ) = ∅ ïåðåïèøåì â ýêâèâàëåíòíîìÄëÿ ýòîãî óñëîâèå Øn (αâèäå:αj ∈/ Ø2tn (αi )29Äàëåå ïîñòóïàåì ñëåäóþùèì îáðàçîì: âûáèðàåì ïðîèçâîëüíîåα1 ∈ B nα2âûáèðàåì èç óñëîâèÿα3 èç óñëîâèÿα2 ∈/ Ø2tn (α1 )2tα3 ∈/ Ø2tn (α1 ) ∪ Øn (α2 )è ò.ä. Óñëîâèå íà âûáîðαi+1çàïèøåòñÿ ñëåäóþùèì îáðàçîì:αi+1 ∈/i[2tØn(αi )k=1ßñíî, ÷òî î÷åðåäíîåαN +1íå óäàñòñÿ âûáðàòü, òîëüêî êîãäàN[2tØn(αi ) = B ni=1Äëÿ ïîñòðîåííîãî êîäà ñïðàâåäëèâà îöåíêàNXn|Ø2tn (αi )| > 2i=1ò.å.nN |Ø2tn (α)| > 2Ó÷èòûâàÿ îöåíêó (2) ïîëó÷àåì:2nn2tlog2 N > n − 2t log2 n + c1 2t(5)N > c1 (2t)(6)Ò.î.
çàêëþ÷àåì, ÷òî íåëüçÿ ïîñòðîèòü êîä, íå óäîâëåòâîðÿþùèé îöåíêå (3) è çàâåäîìî ìîæíî,óäîâëåòâîðÿþùèé îöåíêå (5).Êîäûäàííîãîek (m)nNSttinnØn (α ) = B , ò.å. åñëè 2 = N |Øn (α)|.i=1Õýììèíãà. Êîäû Õýììèíãà êîäû èñïðàâëÿþùèå 1 îøèáêó òèïà çàìåùåíèÿ. Äëÿk−1íàéä¼ì òàêîå k, ÷òî 26 n 6 2k . Äëÿ êàæäîãî öåëîãî ÷èñëà 0 6 m < 2k ïîëîæèìÊîä íàçûâàþò ñîâåðøåííûì, åñëè äâîè÷íàÿ çàïèñü ÷èñëàmñ èñïîëüçîâàíèåìkðàçðÿäîâ.Ïðèìåð. e3 (1) = 001, e3 (2) = 010, e3 (3) = 011.Îïðåäåëèì îáðàòíóþ îïåðàöèþ:N (γ) = N (γ1 ...γk ) =kPγi 2k−i ,ò.å.N ek (m) = m.Òåïåðüi=1îïðåäåëèì ëèíåéíîå îòîáðàæåíèåH : Bn → BkH(α) = H(α1 ...αn ) = α1 ek (1) + ...
+ αn ek (n).ÏóñòüV ÿäðî ýòîãî îòîáðàæåíèÿ, ò.å.V = {α ∈ B n | H(α) = 0...0}. Vè íàçûâàåòñÿ êîäîìÕýììèíãà. Èçó÷èì åãî ñâîéñòâà:1.|V | = 2n−k :iαt ñòðîêà ñ åäèíèöåé íà t-îì ìåñòå èkíóëÿìè íà îñòàëüíûõ, îáðàçóåò áàçèñ ïðîñòðàíñòâà B . Ïîýòîìó îòîáðàæåíèå H ñþðúåêòèâíî, ñëåäîâàòåëüíî ðàçìåðíîñòü ÿäðà n − k . Êðîìå òîãî, ñèñòåìà óðàâíåíèé H(α) = 0...0ðàçðåøèìà îòíîñèòåëüíî ïåðâûõ k ýëåìåíòîâ, ÷òî äà¼ò íàì ïðàâî íàçâàòü ïåðâûå k ðàçðÿäîâêîäà ïðîâåðî÷íûìè, à îñòàëüíûå èíôîðìàöèîííûìè, ò.å. ïîäïðîñòðàíñòâî â V , íàòÿíóòîån−kíà ïîñëåäíèå n − k êîîðäèíàò, åñòü B.ìíîæåñòâî{H(α2 ) i = 0, ..., k − 1},30ãäåV2.åñòü êîä, èñïðàâëÿþùèé îäíó îøèáêó òèïà çàìåùåíèÿ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
