Wykład 8, Informatyka Magisterskie SGGW, Teoria Informacji TI, Egzamin
[ Pobierz całość w formacie PDF ]
//-->Teoria informacji, 09.05.2013Informacja wzajemnaI(X;Y) =H(Y)−H(Y|X)=H(X)−H(X|Y) =H(X)+H(Y)−H(X,Y)Przepustowo´c kanału [bit/s]s´C=maxI(X;Y)p(x)Bezszumny kanał binarnyP(Y|X)X\Y 0 11 010 1P(Y,X)X\Y 0 1121121 1P(X)= (2,2)1P(Y) = [1(1 +0),1(0 +1)]= (2,1)222p(yj) =∑p(yj|Xi)p(xi)iH(Y|X)=P(X=0)H(Y|X=0)+P(X=1)H(Y|X=1)=1(−1log 1−0 log 0)+1(−0log 0−1 log 1)=0 bitów22H(Y) =1log 2+1log 2=122I(X;Y) =1−=1Zaszumiony kanał z nienakładajacymi si˛ na siebie sygnałami wyj´ciowymi˛esP(Y|X)X\Y 1 2 3 4110 02210 01 233P(Y,X)X\Y 1 2 3 4110 04410 01 163P(Y) = (1,1,1,1)4 4 6 3P(X)= (1,1)⇒H(X)=1log 2+1log 2=12 2221H(Y) =1log 4+1log 4+1log 6+1log 3=1+1log 2+1log 3+3log 3=1+1+1log 3=7+1log 344636662621H(X,Y) =1log 4+1log 4+6log 6+1log 3=H(Y)443I(X;Y) =H(X)+H(Y)−H(X,Y) =H(X)=1 [bit/s]Zaszumiona maszyna do pisania11 11Z:P(X)= (27,27, . . . ,27)P(Y|X)B...X\Y A11A0. . . 033111B333...–130. . . 013–P(Y,X)X\YAB...130. . . 0B18118113A181181...0. . . 0181–1810. . . 0111–0. . . 08181811 11P(Y) = (27,27, . . . ,27)11H(Y) = (27log27)·27=3 log 311H(Y|X)=27·27(1log 3+3log 3+1log 3)=log 333I(X;Y) =3 log 3−log 3=2 log 3=log 9 [bit/s]C=maxI(X;Y) =max(H(Y )−H(Y|X))=2 log 3p(x)p(x)Binarny kanał symetrycznyP(X)= (1,1)2 2P(Y|X)X\Y11-pp1p1-pP(Y,X)2X\Y1112(1−p)2p1112p2(1−p)1 1P(Y) = (2,2)H(Y) =1log 2+1log 2=12211H(Y|X)=−2[(1−p)log(1−p)+plogp]−2[plogp+ (1−p)log(1−p)]=−plogp−(1−p)log(1−p)=H(p)[H2(p)]de fI(X;Y) =1−H(p)=CBinarny kanał zamazujacy˛Z:P(X)= (1−Π, Π)P(Y|X)X\Ye11−α α1α1−αP(X,Y)X\Ye1(1−Π)(1−α)(1−Π)α1αΠ(1−α)ΠP(Y) = [(1−Π)(1−α), α,(1−α)Π]H(Y) =−(1 −Π)(1−α)log[(1−Π)(1−α)]−αlogα−Π(1−α)log[Π(1−α)]= (1−α)[−(1−Π)log(1−Π)−ΠlogΠ]+[−(1−α)log(1−α)−αlogα]=H(α)+ (1−α)H(Π)H(Y|X)= (1−Π)[(1−α)log(1−α)+αlogα]−Π[αlogα+ (1−α)log(1−α)]=H(α)C=maxI(X;Y) =maxH(Y)−H(α)=max(1−α)H(Π)+H(α)−H(α)=1−αp(x)ΠΠ˙˙˙Poniewazαbitów ginie w kanale, mozemy odtworzy´ co najwyzej 1−αbitówcKanał "Z"Z:P(X)= (1−p, p)P(Y|X)X\Y 0111f 1-fP(X,Y)3X\Y11-p1pf p(1-f)P(Y) = [1−p(1−f),p(1−f)]H(Y) =H2[p(1−f)]H(q)=−qlogq−(1−q)log(1−q)H(Y|X)=−(1 −p)·1 log 1−p[ flogf+ (1−f)log(1−f)] =pH2(f)I(X;Y) =H2[p(1−f)]−pH2(f)∂I(X;Y)=maxI(X;Y):p∂pff=0H2(f)C=maxI(X;Y) =log[1+ (1−f)f1−f]≈1−p24
[ Pobierz całość w formacie PDF ]