Wykład 5, Informatyka Magisterskie SGGW, Teoria Informacji TI, Egzamin

//-->.pos {position:absolute; z-index: 0; left: 0px; top: 0px;}Teoria informacji, 11.04.2013∑D−nii=1np.M1D=2{0, 1}nM=3a) warunek koniecznyn1,n2, . . . ,nMn1n2{0,1,. . . ,D−1}···nMDnM- liczba wszystkich w˛ złów ko´ cowychennM−nii-ty wykluczaDcałkowita liczba wykluczonych w˛ złówe∑DnM−nii=1MMDnM⇒∑D−nii=1M1Mb) warunek wystarczajacy˛n1,n2, . . . ,nM∑D−nii=11⇒∑DnM−nii=1DnMn1(korze´ ) wykluczaDnM−n1w˛ złów ko´ cowych (li´ci)⇒DnM−n1DnMnensnM−n1+DnM−n2w˛ złów ko´ cowych⇒DnM−nin2wykluczaDenDnMPrzykład kodu natychmiastowego w którym wyst˛ puja wyrazy o jednakowej długo´cie ˛sx1x211x3100x4101TwierdzenieJe´li jednoznacznie deszyfrowalny kod ma słowa o długo´ciach n1,n2, . . . ,nM,to∑D−nissi=1M11´Zródło reprezentowane przez zmienna losowaX:{x1,x2, . . . ,xM}z prawdopodobie´ stwamip1,p2, . . . ,pM, tym elementom ze˛˛nzródła przypisane sa słowa kodoweW1,W2, . . . ,WMo długo´ciachn1,n2, . . . ,nM, alfabet kodowy{a1, . . . ,aD}.Zamierzamy skonstru-´˛sM´owa´ kod jednoznacznie deszyfrowalny, który minimalizuje srednia długo´c słowa kodowegon=∑pinic˛s´i=11. Ustalamy absolutnie dolne ograniczenie na warto´c oczekiwana (n)s´˛˙˙ c2. Znajdujemy jak blisko mozna si˛ zblizy´ do tego ograniczeniae3. Próbujemy znale´ c "najlepszy" kodz´Twierdzenie o bezszumnym kodowaniuM´Je´lin=∑pinijest srednia długo´cia słowa kodowego w kodzie jednoznacznie deszyfrowalnym dla zmiennej losowejX:s˛s ˛i=1{x1,x2, . . . ,xM}tonH(X)log2DMH(X)logD,˙gdzie "=" wyst˛ puje wtedy i tylko wtedy, gdypi=D−nidla kazdego i.eM=−∑pilog2Di=−∑pilogDpi2i=1i=1MM�½MlogD∑pini−∑pilogpi⇒ −∑pilogD−nii=1i=1i=1nilogD=logDni=−logD−niD−niMlogp−∑pilogpii=1Mqi=M∑Dj=1−nj⇒∑qi=1i=1MMMMZ lematu−∑pilogpii=1M−∑pilogqilub−∑pilogqii=1Mi=1M−∑pilogi=1D−niMj=1∑D−njznak "=" wtedy i tylko wtedy, gdyMD−niM∑Dj=1−nj=piH(X)−∑pilogD−ni+ (∑pi)log(∑D−nj)⇒H(X)i=1D−niMnlogD+log(∑D−nj)[H(X)j=1nlogD]znak "=" wtedy i tylko wte-i=1j=1dy, gdypi=∑Dj=1−njKod osiagajacy dolne ograniczenie okre´lone w twierdzeniu o bezszumnym kodowaniu nazywamy kodem absolutnie optymalnym˛ ˛sH(X)(dla któregon=logD)PrzykładXPsłowa kodowe/kod1x1p1=2110x2p2=41x3p3=81101111x4p4=8D=2⇒logD=1H(X)=n=74−ni⇒n=−logpipi=DilogDp−logDilogni1p−logDi+1logi=1, 2,. . . ,M∑D−nii=1MlogpiMnilogD⇒piMD−ni⇒∑D−nii=1MMMM∑pi=1i=1pb)−∑pilogDilogi=1∑pinii=1i=1logp∑pilogDi+∑pii=1Twierdzenie´Dla danej zmiennej losowej X z niepewno´cia H(X) isnieje kod natychmiastowy z baza D, którego srednia długo´c słowa kodo-s ˛˛s´H(X)H(X)wego n spełnialogDnlogD+1Kod spełniajacy ten warunek jest kodem optymalnym˛˙Mozemy podej´c dowolnie blisko dolnego ograniczenia, je´li zastosujemy kodowanie blokowe, tzn. zamiast kodowa´ kazdys´sc ˙˙symbolxiwe´ miemy ciagsniezaleznych obserwacjiXi przypiszemy słowo kodowe wynikłej grupiessymboli, tzn. konstruujemyz˛˙˙kod dla wektora losowegoY= (X1,X2, . . . ,Xs)gdzieXisa niezalezne i kazdeXima ten sam rozkład coX.Kodowanie blokowe˛´zmniejsza srednia długo´c słowa kodowego przypadajaca na warto´cx.˛s´˛ ˛s´2PrzykładX P słowo kodowe (ni=1)3x1 411x2 4Y= (X1,X2)P słowa kodowe9x1x1163x1x210163x2x1110161x2x2111163H(X)=2−4log 3≈0.811278n=1·1+1·3=144liter3319ndla bloku=16+16·2+16·3+16·3=27 na 2 kodowych=27 liter kodowych≈0.84375liter kodowych16warto´ci xs32 na 1 warto´c xs´na 1 warto´c xs´Kod dlaYH(Y))kodowychnH(YD+1literwarto´c YlogDlognas´H(Y) =H(X1,X2, . . . ,Xs) =H(X1) +· · ·+H(Xs) =sH(X)sH(X)H(X)1ns sH(X)+1 lubH(X) nsslogDlogDlogDlogD+sns´˛s´s- srednia liczba liter kodowych przypadajaca na warto´ c X3

zanotowane.pl

doc.pisz.pl

pdf.pisz.pl

kachorra.htw.pl