信息论与编码第二章课后习题答案.pdf 15页

'第二章课后习题【2.1】设有12枚同值硬币，其中有一枚为假币。只知道假币的重量与真币的重量不同，但不知究竟是重还是轻。现用比较天平左右两边轻重的方法来测量。为了在天平上称出哪一枚是假币，试问至少必须称多少次？解：从信息论的角度看，1“12枚硬币中，某一枚为假币”该事件发生的概率为P=；121“假币的重量比真的轻，或重”该事件发生的概率为P=；2为确定哪一枚是假币，即要消除上述两事件的联合不确定性，由于二者是独立的，因此有I=log12+log2=log24比特1而用天平称时，有三种可能性：重、轻、相等，三者是等概率的，均为P=，因此天3平每一次消除的不确定性为I=log3比特因此，必须称的次数为I1log24=»2.9次Ilog32因此，至少需称3次。【延伸】如何测量？分3堆，每堆4枚，经过3次测量能否测出哪一枚为假币。【2.2】同时扔一对均匀的骰子，当得知“两骰子面朝上点数之和为2”或“面朝上点数之和为8”或“两骰子面朝上点数是3和4”时，试问这三种情况分别获得多少信息量？解：“两骰子总点数之和为2”有一种可能，即两骰子的点数各为1，由于二者是独立的，111因此该种情况发生的概率为P=´=，该事件的信息量为：6636 I=log36»5.17比特“两骰子总点数之和为8”共有如下可能：2和6、3和5、4和4、5和3、6和2，概115率为P=´´5=，因此该事件的信息量为：663636I=log»2.85比特5111“两骰子面朝上点数是3和4”的可能性有两种：3和4、4和3，概率为P=´´2=，6618因此该事件的信息量为：I=log18»4.17比特【2.3】如果你在不知道今天是星期几的情况下问你的朋友“明天星期几？”则答案中含有多少信息量？如果你在已知今天是星期四的情况下提出同样的问题，则答案中你能获得多少信息量（假设已知星期一至星期日的顺序）？解：如果不知今天星期几时问的话，答案可能有七种可能性，每一种都是等概率的，均为1P=，因此此时从答案中获得的信息量为7I=log7=2.807比特而当已知今天星期几时问同样的问题，其可能性只有一种，即发生的概率为1，此时获得的信息量为0比特。【2.4】居住某地区的女孩中有25%是大学生，在女大学生中有75%是身高1.6米以上的，而女孩中身高1.6米以上的占总数一半。假如我们得知“身高1.6米以上的某女孩是大学生”的消息，问获得多少信息量？解：设A表示女孩是大学生，P(A)=0.25；B表示女孩身高1.6米以上，P(B|A)=0.75，P(B)=0.5“身高1.6米以上的某女孩是大学生”的发生概率为 P(AB)P(A)P(B|A)0.25´0.75P(A|B)====0.375P(B)P(B)0.5已知该事件所能获得的信息量为1I=log»1.415比特0.375éXùéa1=0a2=1a3=2a4=3ù【2.5】设离散无记忆信源êú=êú，其发出的消息为ëP(x)ûë3/81/41/41/8û（202120130213001203210110321010021032011223210），求（1）此消息的自信息是多少？（2）在此消息中平均每个符号携带的信息量是多少？解：信源是无记忆的，因此，发出的各消息之间是互相独立的，此时发出的消息的自信息即为各消息的自信息之和。根据已知条件，发出各消息所包含的信息量分别为：8I(a=0)=log=1.415比特03I(a=1)=log4=2比特1I(a=2)=log4=2比特2I(a=3)=log8=3比特3在发出的消息中，共有14个“0”符号，13个“1”符号，12个“2”符号，6个“3”符号，则得到消息的自信息为：I=14´1.415+13´2+12´2+6´3»87.81比特45个符号共携带87.81比特的信息量，平均每个符号携带的信息量为87.81I==1.95比特/符号45注意：消息中平均每个符号携带的信息量有别于离散平均无记忆信源平均每个符号携带的信息量，后者是信息熵，可计算得H(X)=-åP(x)logP(x)=1.91比特/符号 【2.6】如有6行8列的棋型方格，若有二个质点A和B，分别以等概率落入任一方格内，且它们的坐标分别为（XA,YA）和（XB,YB），但A和B不能落入同一方格内。（1）若仅有质点A，求A落入任一个格的平均自信息量是多少？（2）若已知A已落入，求B落入的平均自信息量。（3）若A、B是可分辨的，求A、B同都落入的平均自信息量。解：（1）求质点A落入任一格的平均自信息量，即求信息熵，首先得出质点A落入任一格的概率空间为：éXùéa1a2a3La48ùêú=ê1111úëPûêLúë48484848û平均自信息量为H(A)=log48=5.58比特/符号（2）已知质点A已落入，求B落入的平均自信息量，即求H(B|A)。1A已落入，B落入的格可能有47个，条件概率P(b|a)均为。平均自信息量为ji474847H(B|A)=-ååP(ai)P(bj|ai)logP(bj|ai)=log47=5.55比特/符号i=1j=1（3）质点A和B同时落入的平均自信息量为H(AB)=H(A)+H(B|A)=11.13比特/符号【2.7】从大量统计资料知道，男性中红绿色盲的发病率为7%，女性发病率为0.5%，如果你问一位男同志：“你是否是红绿色盲？”，他的回答可能是“是”，也可能是“否”，问这两个回答中各含有多少信息量？平均每个回答中含有多少信息量？如果你问一位女同志，则答案中含有的平均自信息量是多少？解： 男同志红绿色盲的概率空间为：éXùéa1a2ùêú=êúëPûë0.070.93û问男同志回答“是”所获昨的信息量为：1I=log»3.836比特/符号0.07问男同志回答“否”所获得的信息量为：1I=log»0.105比特/符号0.93男同志平均每个回答中含有的信息量为H(X)=-åP(x)logP(x)=0.366比特/符号同样，女同志红绿色盲的概率空间为éYùéb1b2ùêú=êúëPûë0.0050.995û问女同志回答“是”所获昨的信息量为：1I=log»7.64比特/符号0.005问女同志回答“否”所获昨的信息量为：1-3I=log»7.23´10比特/符号0.995女同志平均每个回答中含有的信息量为H(Y)=-åP(x)logP(x)=0.045比特/符号éXùéa1a2a3a4a5a6ù【2.8】设信源êú=êú，求此信源的熵，并解释为什ëP(x)ûë0.20.190.180.170.160.17û么H(X)>log6，不满足信源熵的极值性。解：H(X)=-åP(x)logP(x)=2.65>log6原因是给定的信源空间不满足概率空间的完备集这一特性，因此不满足极值条件。 【2.9】设离散无记忆信源S其符号集A={a,a,...,a}，知其相应的概率分别为12q(P,P,...,P)。设另一离散无记忆信源S¢，其符号集为S信源符号集的两倍，12qA¢={a,i=1,2,...,2q}，并且各符号的概率分布满足iP¢=(1-e)Pi=1,2,...,qiiP¢=ePi=q+1,q+2,...,2qii试写出信源S¢的信息熵与信源S的信息熵的关系。解：H(S¢)=-åP(x)logP(x)=-(1-e)Plog(1-e)P-ePlogePåiiåii=-(1-e)åPilog(1-e)-(1-e)åPilogPi-eåPiloge-eåPilogPi=-(1-e)log(1-e)-eloge+H(S)=H(S)+H(e,1-e)【2.10】设有一概率空间，其概率分布为{p,p,...,p}，并有p>p。若取p¢=p-e，12q1211p¢=p+e，其中0<2e£p-p，而其他概率值不变。试证明由此所得新的概率空间的2212熵是增加的，并用熵的物理意义加以解释。解：设新的信源为X¢，新信源的熵为：H(X¢)=-plogp=-(p-e)log(p-e)-(p+e)log(p+e)-L-plogpåii1122qq原信源的熵H(X)=-plogp=-plogp-plogp-L-plogpåii1122qq因此有，H(X)-H(X¢)=(p-e)log(p-e)+(p+e)log(p+e)-plogp-plogp11221122æp1-p2ù令f(x)=(p-x)log(p-x)+(p+x)log(p+x)，xÎç0,，则1122çúè2ûp+x2f¢(x)=log£0p-x1 即函数f(x)为减函数，因此有f(0)³f(e)，即(p-e)log(p-e)+(p+e)log(p+e)£plogp+plogp11221122因此H(X)£H(X¢)成立。【解释】当信源符号的概率趋向等概率分布时，不确定性增加，即信息熵是增加的。Lm【2.11】试证明：若åpi=1，åqj=pL，则i=1j=1qqq12mH(p,p,K,p,q,q,K,q)=H(p,p,K,p,p)+pH(,,K,)12L-112m12L-1LLpppLLL并说明等式的物理意义。解：H(p,p,K,p,q,q,K,q)12L-112m=-plogp-plogp-K-plogp-qlogq-qlogq-K-qlogq1122L-1L-11122mm=-plogp-plogp-K-plogp-plogp+plogp1122L-1L-1LLLL-qlogq-qlogq-K-qlogq1122mm=-plogp-plogp-K-plogp-plogp+(q+q+q+L+q)logp1122L-1L-1LL123mL-qlogq-qlogq-K-qlogq1122mm=-plogp-plogp-K-plogp-plogp1122L-1L-1LLqqq12m-qlog-qlog-K-qlog12mpppLLL=-plogp-plogp-K-plogp-plogp1122L-1L-1LLqqqqqq1122mm+p(-log-log-K-log)LppppppLLLLLLq1q2qm=H(p,p,K,p,p)+pH(,,K,)12L-1LLmpppLLL【意义】将原信源中某一信源符号进行分割，而分割后的符号概率之和等于被分割的原符号的概率，则新信源的信息熵增加，熵所增加的一项就是由于分割而产生的不确定性量。5【2.12】（1）为了使电视图像获得良好的清晰度和规定的适当的对比度，需要用5×10个 像素和10个不同亮度电平，求传递此图像所需的信息率（比特/秒）。并设每秒要传送30帧图像，所有像素是独立变化的，且所有亮度电平等概率出现。（2）设某彩电系统，除了满足对于黑白电视系统的上述要求外，还必须有30个不同的色彩度，试证明传输这彩色系统的信息率要比黑白系统的信息率约大2.5倍。解：每个像素的电平取自10个不同的电平，每一个像素形成的概率空间为：éXùéa1a2La10ùêú=ê111úëPûêLúë101010û这样，平均每个像素携带的信息量为：H(X)=log10=3.32比特/像素现在所有的像素点之间独立变化的，因此，每帧图像含有的信息量为：N56H(X)=NH(X)=5´10´log10=1.66´10比特/帧按每秒传输30帧计算，每秒需要传输的比特数，即信息传输率为：N730´H(X)=4.98´10比特/秒除满足黑白电视系统的要求外，还需30个不同的色彩度，不妨设每个色彩度等概率出现，则其概率空间为：éYùéb1b2Lb30ùêú=ê111úëPûêLúë303030û其熵为log30比特/符号，由于电平与色彩是互相独立的，因此有H(XY)=H(X)+H(Y)=log300这样，彩色电视系统的信息率与黑白电视系统信息率的比值为H(XY)log300=»2.5H(X)log10 5【2.13】每帧电视图像可以认为是由3×10个像素组成，所以像素均是独立变化，且每一像素又取128个不同的亮度电平，并设亮度电平等概率出现。问每帧图像含有多少信息量？若现有一广播员在约10000个汉字的字汇中选1000个来口述此电视图像，试问广播员描述此图像所广播的信息量是多少（假设汉字是等概率分布，并且彼此无依赖）？若要恰当地描述此图像，广播员在口述中至少需用多少汉字？解：每个像素的电平亮度形成了一个概率空间，如下：éXùéa1a2La128ùêú=ê111úëPûêLúë128128128û平均每个像素携带的信息量为：H(X)=log128=7比特/像素5每帧图像由3×10个像素组成，且像素间是独立的，因此每帧图像含有的信息量为：N6H(X)=NH(X)=2.1´10比特/帧如果用汉字来描述此图像，平均每个汉字携带的信息量为H(Y)=log10000=13.29比特/汉字，选择1000字来描述，携带的信息量为N4H(Y)=NH(Y)=1.329´10比特如果要恰当的描述此图像，即信息不丢失，在上述假设不变的前提下，需要的汉字个数为：NH(X)2.11065=»1.58´10字H(Y)13.29【2.14】为了传输一个由字母A、B、C和D组成的符号集，把每个字母编码成两个二元码脉冲序列，以00代表A，01代表B，10代表C，11代表D。每个二元码脉冲宽度为5ms。（1）不同字母等概率出现时，计算传输的平均信息速率？ 1113（2）若每个字母出现的概率分别为p=，p=，p=，p=，试计算传输的ABCD54410平均速率？解：假设不同字母等概率出现时，平均每个符号携带的信息量为H(X)=log4=2比特每个二元码宽度为5ms，每个字母需要2个二元码，则其传输时间为10ms，每秒传送n=100个，因此信息传输速率为：R=nH(X)=100´2=200比特/秒当不同字母概率不同时，平均传输每个字母携带的信息量为111310H(X)=log5+log4+log4+log=1.985比特/符号544103此时传输的平均信息速度为2R=nH(X)=1.985´10比特/秒【2.15】证明离散平稳信源有H(X|XX)£H(X|X)，试说明等式成立的条件。31221解：H(X3|X1X2)=-åååP(x1x2x3)logP(x3|x1x2)=-ååP(x1x2)åP(x3|x1x2)logP(x3|x1x2)X1X2X3£-P(xx)P(x|xx)logP(x|x)åå12å31232X1X2X3=H(X|X)32根据信源的平稳性，有H(X|X)=H(X|X)，因此有H(X|XX)£H(X|X)。322131221等式成立的条件是P(x|xx)=P(x|x)。31232【2.16】证明离散信源有H(XXLX)£H(X)+H(X)+L+H(X)，并说明等式成立12N12N的条件。证明： H(XXLX)=H(X)+H(X|X)+L+H(X|XXLX)12N121N12N-1而H(X|XXLX)N12N-1=-åååLP(x1x2LxN)logP(xN|x1x2LxN-1)X1X2XN=-ååLåP(x1x2LxN-1)åP(xN|x1x2LxN-1)logP(xN|x1x2LxN-1)X1X2XN-1XN£-ååLåP(x1x2LxN-1)åP(xN|x1x2LxN-1)logP(xN)X1X2XN-1XN=H(X)N即H(X|X)£H(X)212H(X|XX)£H(X)3123……代入上述不等式，有H(XXLX)£H(X)+H(X)+L+H(X)12N12N等号成立的条件是：P(x|xxLx)=P(x)N12N-1NP(x|xxLx)=P(x)N-112N-2N-1……P(x|x)=P(x)212即离散平稳信源输出的N长的随机序列之间彼此统计无依赖时，等式成立。【2.17】设有一个信源，它产生0、1序列的消息。它在任意时间而且不论以前发生过什么符号，均按P(0)=0.4，P(1)=0.6的概率发出符号。（1）试问这个信源是否是平稳的？2（2）试计算H(X)、H(X|XX)及limH(X)。312NN®¥44（3）试计算H(X)并写出X信源中可能有的所有符号。解： 该信源任一时刻发出0和1的概率与时间无关，因此是平稳的，即该信源是离散平稳信源。其信息熵为H(X)=-åP(x)logP(x)=0.971比特/符号信源是平稳无记忆信源，输出的序列之间无依赖，所以2H(X)=2H(X)=1.942比特/符号H(X|XX)=H(X)=0.971比特/符号3121limH(X)=limH(XXLX)=H(X)=0.971比特/符号N12NN®¥N®¥N4H(X)=4H(X)=3.884比特/符号4X信源中可能的符号是所有4位二进制数的排序，即从0000~1111共16种符号。【2.18】设有一信源，它在开始时以P(a)=0.6，P(b)=0.3，P(c)=0.1的概率发出X。如111果X为a时，则X为a、b、c的概率为；如果为b时，则X为a、b、c的概率为；122331如果X为c时，则X为a、b的概率为，为c的概率为0。而且后面发出X的概率只与12i2X有关，又当i³3时，P(X|X)=P(X|X)。试用马尔克夫信源的图示法画出状态i-1ii-121转移图，并计算此信源的熵H。¥解：信源为一阶马尔克夫信源，其状态转换图如下所示。11a:a:331b:31b:311c:b:1321a:c:23根据上述状态转换图，设状态极限概率分别为P(a)、P(b)和P(c)，根据切普曼—柯尔莫哥洛夫方程有 ì111Q(a)=Q(a)+Q(b)+Q(c)ï332ï111ïQ(b)=Q(a)+Q(b)+Q(c)í332ï11ïQ(c)=Q(a)+Q(b)33ïîQ(a)+Q(b)+Q(c)=1解得：31Q(a)=Q(b)=，Q(c)=84得此一阶马尔克夫的信息熵为：H¥=åQ(Ei)H(X|Ei)=1.439比特/符号pp2【2.19】一阶马尔克夫信源的状态图如右图所示，p0p1信源X的符号集为{0,1,2}并定义p=1-p。2pp（1）求信源平稳后的概率分布P(0)、P(1)和p22p22P(2)；2p（2）求此信源的熵H；¥（3）近似认为此信源为无记忆时，符号的概率分布等于平稳分布。求近似信源的熵H(X)并与H进行比较；¥（4）对一阶马尔克夫信源p取何值时，H取最大值，又当p=0和p=1时结果如何？¥解：根据切普曼—柯尔莫哥洛夫方程，可得ìppP(0)=pP(0)+P(1)+P(2)ï22ïppïP(1)=P(0)+pP(1)+P(2)í22ïppïP(2)=P(0)+P(1)+pP(2)22ïîP(0)+P(1)+P(2)=1 1解得：P(0)=P(1)=P(2)=3该一阶马尔克夫信源的信息熵为：H=Q(E)H(X|E)=-plogp-plogp+p比特/符号¥åii当信源为无记忆信源，符号的概率分布等于平稳分布，此时信源的概率空间为：éXùé012ùêú=ê111úëPûêë333úû此时信源的信息熵为H(X)=log3=1.585比特/符号由上述计算结果可知：H(X)³H(¥)。求一阶马尔克夫信源熵H的最大值，H=-plogp-plogp+p，有¥¥dH¥2(1-p)=logdpp2可得，当p=时，H达到最大值，此时最大值为log3=1.585比特/符号。¥3当p=0时，H=0比特/符号；p=1时，H=1比特/符号¥¥【2.20】黑白气象传真图的消息只有黑色和白色两种，即信源X={黑,白}，设黑色出现的概率为P(黑)=0.3，白色出现的概率为P(白)=0.7。（1）假设图上黑白消息出现前后没有关联，求熵H(X)；（2）假设消息前后有关联，其依赖关系为P(白|白)=0.9，P(黑|白)=0.1，P(白|黑)=0.2，P(黑|黑)=0.8，求此一阶马尔克夫信源的熵H。2（3）分别求上述两种信源的冗余度，并比较H(X)和H的大小，并说明其物理意义。2解：如果出现黑白消息前后没有关联，信息熵为：H(X)=-åpilogpi=0.881比特/符号当消息前后有关联时，首先画出其状态转移图，如下所示。 设黑白两个状态的极限概率为Q(黑)和Q(白)，根据切普曼—柯尔莫哥洛夫方程可得：ìQ(黑)=0.8Q(黑)+0.1Q(白)ïíQ(白)=0.2Q(黑)+0.9Q(白)ïîQ(黑)+Q(白)=1解得：12Q(黑)=，Q(白)=33此信源的信息熵为：H=Q(E)H(X|E)=0.553比特/符号¥åii两信源的冗余度分别为：H(X)g=1-=0.1191log2H¥g=1-=0.4471log2结果表明：当信源的消息之间有依赖时，信源输出消息的不确定性减弱。就本题而言，当有依赖时前面已是白色消息，后面绝大多数可能是出现白色消息；前面是黑色消息，后面基本可猜测是黑色消息。这时信源的平均不确定性减弱，所以信源消息之间有依赖时信源熵小于信源消息之间无依赖时的信源熵，这表明信源熵正是反映信源的平均不确定的大小。而信源剩余度正是反映信源消息依赖关系的强弱，剩余度越大，信源消息之间的依赖关系就越大。'