信息论编码例题

平均互信息的物理意义I(X;Y)=工迟p(xy )I(x ;y )=工迟p(xy )log : j ji j 2 p(x)i=1 j=1i12 p(x / y )ij(1) Y对X的平均互信息i j i缶一工迟p(孕严gii=1 j=1i=1 j=1二工迟p(xy )logi j 2i=1 j=1=H (X) H (X / Y)其中条件熵：H(X/Y)=工迟p(xy )log p(x /y )i j 2 i ji=1 j=1*Y对X的平均互信息是对Y一无所知的情况下，X的先验不定度与收到Y后关于X的后验不定度之差，即收到Y前、后 关于X的不确定度减少的量。H(X/Y)表示收到随机变量Y后，对随机变量X仍然存在的不确定度，这是Y关于X的后验 不定度，通常称它为信道疑义度或损失熵(代表了在信道中损失的信息)(2)X 对 Y 的平均互信息*X对Y的平均互信息是Y的先验不定度与发出X后关于Y的后验不定度之差，即发X前、后关于Y的不确定度减少的量。H(Y/X) 表 示 发出随机变 量 X 后，对随 机变量Y仍然 存在的平均 不确定度，常 被称为噪声 熵。(3) Y 对 X 的 平均互信息I(Y;X)=瓦艺 p(xy )I(y ;x )=瓦区 p(xy )log Wi j j ii j 2 p ( y )i=1 j=1i=1 j=1j=艺艺 p(x y )log 1XX p(x y )log 1D儿电p(y )儿电p(y / x )i 1 j 1i i 1 j 1j iH(Y)H(Y /X)其中条件熵：H(Y /X) Xn Xmp(x y )log p(y /x) ci j2j ii 1 j 1I(X;Y)=工迟p(xy )I(x ;y )=工迟p(xy )log222 p(x )p(y ) ij12 p( y )j例 2.1.5将已知信源XP(X)0.52 0.5接到下图所示的信道上，求在该信道上传输的平均互信息量 I(X;Y)、i j i j i ji=1 j=1i=1 j=1二艺迟 p(xy )logp(xy )logi j 2 p ( x )i ji=1 j=1ii=1 j=1-瓦迟 p(x y )log1i j2 p(x y )i 1 j 1i j=H (X) + H (Y) - H (XY)其中联合熵：H(XY) 工迟 p(x y )log p(x y )i j 2 i ji 1 j 1* 信道两端随机变量 X，Y 之间的平均互信息量等于通信前、后整个系统不确定度减少的量。联合熵表示输入随机变量 X ， 经信道传输到达信宿，输出随机变量Y,即收发双方通信后，整个系统仍然存在的不确定度。如果在通信前，我们把X,Y看成是两个独立的随机变量，那么通信前，整个系统的先验不定度即X和Y的联合熵等于H(X)+H(Y)；通信后，我们把 信道两端同时出现X和Y看成是由信道的传递统计特性联系起来的具有一定统计关联关系的两个随机变量，这时整个系 统的后验不定度由H(XY)描述。疑义度H(X/Y)、噪声熵H(Y/X)和联合熵H(XY)。x解：由P (兀儿)=P ( xi ) P ( / J)求出各联合概率：p(x y ) = p(x)p(y /x) = 0.5x0.98=0.49p(x y ) = p(x)p(y / x) = 0.5 x 0.02=0.01p(x y ) = p(x )p(y /x ) = 0.5 x 0.20=0.102 121 2p(x y ) = p(x )p(y /x ) = 0.5x0.80= 0.402 222 2P(y )二 Hp(x y ),(2)由j /j得到Y集各消息概率：i=1p(y )=工P(x y ) = p(x y ) + p(x y ) = 0.49+0.10 = 0.591i 11 12 1i=ip(y)=1- p(y)=1-0.59=0.41213)由 p(x / y ) = ijp( x y )i jp( y )j得到 X 的各后验概率：p(x / y ) =11p( x y ) 0.491 1 =p(y)0.591= 0.831p(x / y ) =1- p(x / y ) = 0.1692 1 1 1同样可推出p(x / y )=0.024,p(x /y )=0.9761 2 2 2H(X)二工p(x)logp(x) = -0.5log 0.5+0.5log 0.5 = 1(比特/符号4)i 2 i22i=1H(Y)= 一工p(y )log p(y ) = -0.59log 0.59+0.41log 0.41i 2 i22i=1=0.98( 比特 / 符号 )H (XY)二戏p (x y )log p (x y ) c i j2i ji=1 j =1= -0.49log 0.49+ 0.01log 0.01+0.10log 0.10+0.40log 0.402222= 1.43(比特/ 符号)(5)平均互信息I(X;Y) = H(X)+H(Y)-H(XY) =1+0.98-1.43=0.55(比特/符号)(6)疑义度H (X / Y) = - 2 p (x y )log p (x / y ) ci j2i ji=1 j =1= -0.49log 0.831+ 0.01log 0.024+ 0.10log 0.169+ 0.40log 0.9762 2 2 2= 0 . 45 (比特 / 符号)H ( Y / X) = 2 p (x y )log p (y / x ) ci j2j ii =1 j =1=0.49log 0.98 + O.Ollog 0.02 + O.lOlog 0.20 + 0.40log 0.802 2 2 2= 0.43(比特 / 符号) 平均互信息的性质-非负性x 和y先前考虑两个具体消息 ij 之间的互信息量体消息出发，而是从随机变量X和Y的整体角度出发, I (X ; Y)=另习 p (x y )log ij i=1 j=1I(x ; y )i j 时，可能出现负值。而平均互信息量不是从两个具 并在平均意义上观察问题，所以平均互信息量不会出现负值。p ( x y ) i j2 p (x ) p (y ) ij p(x ) p(y )i=1 j=1p (x y )logi 1 j 2 p (x y ) ijp(x ) p(y )ijp (x y )ijp (x ) p (y ) p (x y ij i=1 j=1SnSmp( x y )ij1 logi=1 j=1=S SiLi=1j=1=S p (x )SiL i=1j=1=0即I (X ; Y) 0)logP (x y ) logij当且仅当X和Y相互独立时，等号成立。 凸函数性I (X ; Y)=艺习i=1 j=1=刀习p(x y ) logijp ( y / x )j ip(y )jp(x )p(y / x )logciji2p(y / x )j ii=1 j=1工 p (x ) p (y / x )ij ii=1p0(儿 / xi)丫 p (x ) p (y / x )3 i 0 j i. =1=另另ap1 (I + (1 -&) P 2 (xi ) P 0( 丁 j / A，) lOg2 i=1 j=1叮 yj / xi)=工另ap1(xi)+(1 -a)p2(xi)p0(yj/xi)log2.=1 j =1丫ap (x ) + (1 -a)p (x )p (y /x )1 i2 i 0 j ii=1丫 ap (x ) + (1-a)p (x )p (y / x )1 i2 i 0 j ip0(yj /xi)p(y /X )(i=12 ，n; j 二 1，2,，m分布 j i的函数。I(X;Y) = f p(x )若固定信道，调整信源：iI(X;Y) = fp(y / x )若固定信源，调整信道：jip(x)(1)平均互信息是输入信源概率分布i 的上凸函数x ,x ，x p (x)所谓上凸函 数，是指同 一信源集合 12 n , 对应两个不 同的概率分布 1 i 和p (x )(i = 12 ,n)0x 一工 p(x )log p(x )根据熵的极值性i 2 ii 2 i 有i=1i=1区乞j=1区工j=1p (x )p (y /x )1 i 0 j ij i=lp (x )p (y /x )2 i 0 j ij i=llog dp (y ) + (1 u) P (y )、区 P (y )log p (y )21 j2 j1 j21 jj=1log up (y ) + (1 d)p (y )、区p (y )log p (y )21 j2 j2 j22 jj=1代入上式有Ip (x )op (y )log p (y ) (1 a正p (y )log p (y ) +3 i1 j21 j2 j22 jj=1j=1为另ap (x ) + (1 a)p (x )p (y / x )log p (y / x )1 i2 i 0 j i20 j ii=1 j=1= aX2 p (x )p (y /x )log1 i 0 j ii=1 j=1p (y /x )0 j i +2p (y )1jp (y / x )0 j i2(1 a 正艺 p (x ) p (y / x )log2 i 0 j ii=1 j=1=aIp (x ) + (1 a)Ip (x )1 i2 ip(x) p (x) p (x )当 3 i = 1 i =2 i 时，等号成立，一般情况下Ip (x ) aIp (x ) + (1 a)Ip3 i1 ip(y /x )(2)平均互信息是信道转移概率j i 的下凸函数p(x )p(y /x )p (y / x )i ， 通过调整信道 j i 而得；即有两个不同的信道特性 1 j i 和1 p (y /x)对 1 j i2(xi)固定信源p (y /x)o2 j i将信道两端的输入和输出即X和Y联系起来，如果用小于1的正数p (y /x)和 2 j i 进 行 线 性 组 合p (y /x) =op (y /x)+(1-a)p (y /x)3 j i1 j i2 j i 。所谓下凸函数即得到信道特性I p (y / x) = I op (y / x) + (1 -a) p (y / x)3 j i 1 j i 2 j iaIp (y /x ) + (1 -a)Ip (y /x )1 j i 2 j ip = p (u ) nP = P(v / u ) u凸）函数。证法二：互信息I(U;V)是 ii的上凸( 凸)函数；是 jij i的下凸(证明：为了证明方便，我们将互信息改写为：I (U; V) = H (V) - H (V / U)=-i jiijppPi jiPjiji=一工工p P log丄i jiij= I(p ,P )i ji=Po ji ，PP当条件概率 ji 不变时， jiI(p , P ) = I (p , Po ) = I(p ) 这时， i jii jiip0=0 p+ (1 -0 ) p p0 p p设： iii，即 i为 i 与 i内插值，0 9 1其中，这时有q0 =工 p0 Po =工0 p + (1 -0) p ”Po =0 q + (1 -0 )q ” ji jiii jijjiiI( p )p所以要证明i 是 i 的上凸函数，只需证：(按上凸函数定义)01(p) + (1 -0)I(p) I0p + (1 -0)piiii ，即：01 (p) + (1 -0) I (p) -1 0 p + (1 -0) p0 p + (1 -0) P = p0 i i i i i i i=0EEijpPo log i jiPj +(i-0)H q ；i jPo pPo log i ji q ”j-ZZijPo0p + (1 -0 )pPo log ii ji q0j=eZZijPoq0 pPo l0g j i jq Poj jiji - j + (1 -0 )ZZijPoq0 pPo log ji j i ji q” Po j jiE fE /0 log Z (Z p Po )+ (1 -0 )log Z (Z p Po ).i i ji qj=0 log Z q0 + (1 -0)log Z q9jj=0 logl + (1 -0)log1 = 0ijiq0j ji q ”jJensen 不等式上凸性得证。p = p o 再证下凸性，这时，可认为 i i 为不变值，I(p ,P ) = I(po,P ) = I(P )I 则ijiijijiP0 =0P + (1 -0)P0 0 1同理，可设： jijiji而q0 = Z poP0 = Z po0 P + (1 -0) P ji jii jijiii=0 q + (1 -0) qjj要证下凸性，只需证I0P + (1 -0)P 01(P) + (1 -0)I(P )jijijiji ，即I0P + (1 -0)P -01(P ) + (1 -0)I(P)jijiji-H 0 p + (1 -0 )P po log jjiji iq0i jj-0X _j -(i-0)ni ji qi jji j0H poP log ji j + (1 -0 )H poPTog _j i ji q0 P i jj jiP0jiPpoP log _ji jiq ”jP0 q ji ji q0 P i jj jiEfJensen 不 等式E I (X ; Y) I (X ; Z) I (X ; W ) 证明：信道I信道i(WBI (X ; Z) I (X ; Y)假设y条件下x与z独立II信道III证明：对式I (x ; yz ) = log P(xi / j)i j k21 (xi;儿1 zk)=logP (x )iP(x / y z )i j kX YZZ求数学期望得到 与 之间的平均互信息量和I (X; YZ ) = E I (x ; y z )i j k已知条件下，2 P (x / z )ikXY和 之间的条件平均互信息量p(xi/yjzk)其中j=1P(xiyjzk)=P (x )inmL=mp (x y z )logi j k2i=1 j=1 k=1n=Y p(x )log p(x ) - H(X / YZ) i 2 ii=1= H(X ) - H (X /YZ ) (1)P(x / y z )i j kp(x / z )iknmLI(X;Y/Z)=EI(x;y /z )=zzzP(xi yj zk )log2i j ki=1 j=1 k=1二-工迟艺p(xy z)log p(x /z ) +HEEp(xy z )log p(x /y z )i j ki=i j=i k=12 i ki=1 j=1 k=1=-xzz m L p(x y z )log p(x / z ) 一 H(X / YZ)i j k2i ki=1 j=1 k =1= H (X / Z) 一 H (X /YZ )(2)mE p (X y z ) = p (x z )其中 i j k i k 。 j=1式( 1)减去( 2)得到I (X; Z) = I (X; YZ) I (X; Y / Z)同理可得I(X;Y) = I(X;YZ) 一 I(X;Z/Y)Y X zI(X;Z /Y)因为已假设在 条件下 与 相互独立，故有=0，由式(4)得I(X;Y) = I(X;YZ)(5)代入式(3)I(X;Z) = I(X;Y) 一 I(X;Y/Z)I(X;Y/Z)考虑到 为非负量，则有I (X; Z) I (X; Y)同理可得I(X;Z) I(Y;Z)结论：两级串联信道输入与输出消息之间的平均互信息量既不会超过第 I 级信道输入与输出之间的平均互信息量，也不 会超过第 II 级信道输入与输出之间的平均互信息量。数据处理定理说明-当对信号、数据或消息进行多级处理时，每处 理一次，就有可能损失一部分信息，也就是说数据处理会把信号、数据或消息变成更有用的形式，但是决不会创造出新 的信息。此即信息不增原理。如果我们想通过Y尽可能多地获得关于X的消息，也就是想增加互信息量，必须付出代价。 思考？至此，我们已讨论了熵H(U)、H(V),条件熵H(U/V)、H(V/U),联合熵H(U,V)以及互信息I(U;V),它们之间可以用 下列形象、直观图形表示：J(U)AH( 作业二习题5.证明平稳信源有H(X3 1 XiX2)H(X2 1 Xi),并说明等式成立的条件。(pp71 2.16)H(XX X ) H(X ) + H(X ) + H(X )习题6.证明12 N12N (pp71 2.17)习题7.设有一个信源，它产生0、1序列的消息。它在任意时间而且不论以前发生过什么符号，均按P(0)=0.4,P(l)=0.6 的概率发出信号。(1) 试问这个信源是否平稳的？H(X2),H(X |X X )limH (X)(2) 试计算31 2及N卞N 。H(X 4)X 4(3) 试计算 丿并写出信源中可能有的所有符号。(pp71 2.18)X习题8. 一阶马尔可夫信源的状态图如下图所示，信源的符号集为0, 1，2o (pp71 2.23)(1) 求平稳后信源的概率分布。(2) 求信源的熵H如(3) 求当P = 0和P二1时信源的熵，并说明其理由。