信息论与编码理论习题答案.doc

信息论与编码理论习题答案 第二章信息量和熵 2.2八元编码系统，码长为3，第一个符号用于同步，每秒1000个码字，求它的 信息速率。 解：同步信息均相同，不含信息，因此 每个码字的信息量为2?log8=2?3=6bit 因此，信息速率为6?1000=6000bit/s 2.3掷一对无偏骰子，告诉你得到的总的点数为：(a)7;(b)12。问各得到多少信 息量。 解：(1)可能的组合为1，6,2，5,3，4,4，3,5，2,6，1 61p(a)=366 得到的信息量=log1=log6=2.585bitp(a) (2)可能的唯一，为6，6 1p(b)=36 得到的信息量=log1=log36=5.17bitp(b) 2.4经过充分洗牌后的一副扑克（52张），问： (a)任何一种特定的排列所给出的信息量是多少？ (b)若从中抽取13张牌，所给出的点数都不相同时得到多少信息量？ 1解：(a)p(a)=52! 信息量=log1=log52!=225.58bitp(a) ?13!?13种点数任意排列(b)?13?4?花色任选 13!?413413 p(b)=1313C52A52 13信息量=logC52?log413=13.208bit 2.9随机掷3颗骰子，X表示第一颗骰子的结果，Y表示第一和第二颗骰子的 点数之和，Z表示3颗骰子的点数之和，试求H(Z|Y)、H(X|Y)、H(Z|X,Y)、H(X,Z|Y)、H(Z|X)。 解：令第一第二第三颗骰子的结果分别为x1,x2,x3，x1，x2，x3相互独立， 则X?x1，Y?x1?x2，Z?x1?x2?x3 H(Z|Y)=H(x3)=log6=2.585bit H(Z|X)=H(x2?x3)=H(Y) 12345366log36+log18+log12+log9+loglog6)+3636363636536 =3.2744bit =2?( H(X|Y)=H(X)-I(X;Y)=H(X)-H(Y)-H(Y|X) 而H(Y|X)=H(X)，所以H(X|Y)=2H(X)-H(Y)=1.8955bit 或H(X|Y)=H(XY)-H(Y)=H(X)+H(Y|X)-H(Y) 而H(Y|X)=H(X)，所以H(X|Y)=2H(X)-H(Y)=1.8955bit H(Z|X,Y)=H(Z|Y)=H(X)=2.585bit H(X,Z|Y)=H(X|Y)+H(Z|XY)=1.8955+2.585=4.4805bit 2.10设一个系统传送10个数字，0，1，9。奇数在传送过程中以0.5的概 率错成另外一个奇数，其余正确接收，求收到一个数字平均得到的信息量。 解： i?0,2,4,6,8 I(X;Y)=H(Y)-H(Y|X) 因为输入等概，由信道条件可知， 1?p(y?ii为奇数)?10?p(y?ii为偶数)?1(1?1?1?1?1)?1 ?102888810? 即输出等概，则H(Y)=log10 H(Y|X)=?i?p(xyijj)logp(yj|xi) =?p(xiyj)logp(yj|xi)-?p(xiyj)logp(yj|xi) ji偶ji奇 =0-?p(xiyj)logp(yj|xi) ji奇 =- =i?1,3,5,7，9?p(x)p(yii|xi)logp(yi|xi)-?i?ji1，3，5，7，9?p(x)p(yij|xi)logp(yj|xi)11111?log2?5+?log8?4?51021024 13=?=1bit44 I(X;Y)=H(Y)-H(Y|X)=log10-1=log5=2.3219bit 2.11令u1,u2,?，u8为一等概消息集，各消息相应被编成下述二元码字u1=0000，u2=0011，u3=0101，u4=0110， u5=1001，u6=1010，u7=1100，u8=1111 通过转移概率为p的BSC传送。求： (a)接收到的第一个数字0与u1之间的互信息量。(b)接收到的前二个数字00与u1之间的互信息量。(c)接收到的前三个数字000与u1之间的互信息量。(d)接收到的前四个数字0000与u1之间的互信息量。 解： 即I(u1;0)，I(u1;00)，I(u1;000)，I(u1;0000) 111p(0)=(1?p)?4+p?4=882 I(u1;0)=logp(0|u1)1?p=log=1+log(1?p)bit1p(0) 2 11p(00)=2(1?p)2?4(1?p)p?2p2=84 p(00|u1)(1?p)2 I(u1;00)=log=log=21?log(1?p)bit1/4p(00) 11p(000)=(1?p)3?3(1?p)2p?3(1?p)p2?p3=88 I(u1;000)=31+log(1?p)bit 1p(000)0=(1?p)4?6(1?p)2p2?p48 8(1?p)4 I(u1;0000bit)=log(1?p)4?6(1?p)2p2?p4 2.12计算习题2.9中I(Y;Z)、I(X;Z)、I(X,Y;Z)、I(Y;Z|X)、I(X;Z|Y)。 解：根据题2.9分析 13216621610216log216+logloglogH(Z)=2(+216216321662161015216212162521627216loglogloglog+)21615216212162521627 =3.5993bit I(Y;Z)=H(Z)-H(Z|Y)=H(Z)-H(X)=1.0143bitI(X;Z)=H(Z)-H(Z|X)=H(Z)-H(Y)=0.3249bitI(X,Y;Z)=H(Z)-H(Z|XY)=H(Z)-H(X)=1.0143bit I(Y;Z|X)=H(Z|X)-H(Z|XY)=H(Y)-H(X)=0.6894bitI(X;Z|Y)=H(Z|Y)-H(Z|XY)=H(X)-H(X)=0bit 2.14对于任意概率事件集X,Y,Z，证明下述关系式成立(a)H(Y,Z|X)?H(Y|X)+H(Z|X)，给出等号成立的条件(b)H(Y,Z|X)=H(Y|X)+H(Z|X,Y) (c)H(Z|X,Y)?H(Z|X) 证明：(b)H(Y,Z|X)=-?p(xyz)logp(yz|x) xyz =-?p(xyz)logp(y|x)p(z|xy) xyz =-?p(xyz)logp(y|x)-?p(xyz)logp(z|xy)xyzxyz =H(Y|X)+H(Z|XY)(c)H(Z|X,Y)=-?p(xyz)logp(z|xy) xyz =?p(xy)-?p(z|xy)logp(z|xy) xyz ?p(xy)-?p(z|x)logp(z|x) xyz =-?p(xyz)logp(z|x) xyz =H(Z|X) 当p(z|xy)=p(z|x)，即X给定条件下，Y与Z相互独立时等号成立(a)上式(c)左右两边加上H(Y|X)，可得 H(Y|X)+H(Z|X,Y)?H(Y|X)+H(Z|X) 于是H(Y,Z|X)?H(Y|X)+H(Z|X) ?1,?1? 2.28令概率空间X?11?，令Y是连续随机变量。已知条件概率密度为?,?22? 2.1莫尔斯电报系统中，若采用点长为0.2s，1划长为0.4s，且点和划出现的概率分别为2/3和1/3，试求它的信息速率(bits/s)。 214 ?0.2?0.4?秒3315231 ?log3?0.9183比特/符号每个符号的熵为?log 323 15 ?3.444比特/秒所以，信息速率为0.9183?4 解:平均每个符号长为: 2.2一个8元编码系统，其码长为3，每个码字的第一个符号都相同(用于同步)，若每秒产生1000个码字，试求其信息速率(bitss)。解:同步信号均相同不含信息,其余认为等概,每个码字的信息量为3*2=6比特； 所以，信息速率为6?1000?6000比特/秒 2.3掷一对无偏的骰子，若告诉你得到的总的点数为：(a)7；(b)12。试问各得到了多少信息量? 66 )?2.585比特所以，得到的信息量为log2(3636 11 ?5.17比特(b)一对骰子总点数为12的概率是所以，得到的信息量为log2 3636 解:(a)一对骰子总点数为7的概率是 2.4 经过充分洗牌后的一付扑克(含52张牌)，试问：(a)任何一种特定排列所给出的信息量是多少?(b)若从中抽取13张牌，所给出的点数都不相同时得到多少信息量? 解:(a)任一特定排列的概率为 11 ,所以，给出的信息量为?log2?225.58比特52!52! 13!?413413 (b)从中任取13张牌,所给出的点数都不相同的概率为?13 13A52C52 13 C52 ?13.21比特.所以，得到的信息量为log2 413 2.5设有一个非均匀骰子，若其任一面出现的概率与该面上的点数成正比，试求各点出现时所给出的信息量，并求掷一次平均得到的信息量。 i ,i?1,2,3,4,5,621 I(x?1)?4.392比特I(x?i)?log2I(x?2)?3.392比特 I(x?3)?2.807比特i 解:易证每次出现i点的概率为,所以 I(x?4)?2.392比特21 I(x?5)?2.070比特I(x?6)?1.807比特H(X)? i?16 ii log2?2.398比特2121 2.6园丁植树一行，若有3棵白杨、4棵白桦和5棵梧桐。设这12棵树可随机地排列，且每一种排列都是等可能的。若告诉你没有两棵梧桐树相邻时，你得到了多少关于树的排列的信息? 解:可能有的排列总数为 12! ?27720没有两棵梧桐树相邻的排列数可如下图求得，YXYXY 3!4!5! ?7? XYXYXYXYXY图中X表示白杨或白桦，它有?种排法，Y表示梧桐树可以栽种的位置，它 ?3? 有? ?8?8?7?种排法，所以共有?*?=1960种排法保证没有两棵梧桐树相邻，因此若告诉你没有两棵梧桐树相邻时，得到关?5?5?3? 27720?log21960=3.822比特 于树排列的信息为log2 2.7某校入学考试中有1/4考生被录取，3/4考生未被录取。被录取的考生中有50%本市，而落榜考生中有10本市，所有本市的考生都学过英语，而外地落榜考生中以及被录取的外地考生中都有40%学过英语。(a)当己知考生本市时，给出多少关于考生是否被录取的信息?(b)当已知考生学过英语时，给出多少有关考生是否被录取的信息?(c)以x表示是否落榜，y表示是否为本市学生，z表示是否学过英语，x、y和z取值为0或1。试求H(X)，H(Y|X)，H(Z|YZ)。 解:X=0表示未录取，X=1表示录取；Y=0表示本市，Y=1表示外地；Z=0表示学过英语，Z=1表示未学过英语，由此得 31p(x?0)?,p(x?1)?, 44 p(y?0)?p(x?0)p(y?0x?0)?p(x?1)p(y?0x?1)31111?,41042514 p(y?1)?1?, 55 p(z?0)?p(y?0)p(z?0y?0)?p(y?1)p(z?0y?1)144013?,55100251312 p(z?1)?1?, 2525 ? (a)p(x?0y?0)?p(y?0x?0)p(x?0)/p(y?0)? 1313?/?104581115 p(x?1y?0)?p(y?0x?1)p(x?1)/p(y?0)?/? 2458 p(x?0y?0)p(x?1y?0) I(X;y?0)?p(x?0y?0)log2?p(x?1y?0)log2 p(x?0)p(x?1) 3535 ?log2?log288 44 ?0.4512比特 (b)p(x?0z?0) ?(p(z?0y?0,x?0)p(y?0x?0)?p(z?0y?1,x?0)p(y?1x?0)p(x?0)/p(z?0)19431369?(?)?/?101010425104p(x?1z?0) ?(p(z?0y?0,x?1)p(y?0x?1)?p(z?0y?1,x?1)p(y?1x?1)p(x?1)/p(z?0)11211335?(?)?/?225425104I(X;z?0)?p(x?0z?0)log2 p(x?0z?0) p(x?0) 6935 6935?log2?log231041104 44 ?0.02698比特 ?p(x?1z?0)log2 p(x?1z?0)p(x?1) 341 (c)H(X)?log2?log24?0.8113比特 434 H(YX)?p(x?0)p(y?0x?0)log2p(y?0x?0)?p(x?0)p(y?1x?0)log2p(y?1x?0)? p(x?1)p(y?0x?1)log2p(y?0x?1)?p(x?1)p(y?1x?1)log2p(y?1x?1)3139101111 ?log210?log2?log22?log2241041094242?0.6017比特 2.8在A、B两组人中进行民意测验，组A中的人有50%讲真话(T)，30%讲假话(F)，20%拒绝回答(R)。而组B中有30%讲真话，50%讲假话和20%拒绝回答。设选A组进行测验的概率为p，若以I(p)表示给定T、F或R条件下得到的有关消息组A或组B的平均信息量，试求I(p)的最大值。解:令 X?A,B?,Y?T,F,R?，则 P(T)?P(TA)P(A)?P(TB)P(B) ?0.5p?0.3?(1?p)?0.3?0.2p 同理P(F)?0.5?0.2p,P(R)?0.2I(p)?I(X;Y)?H(Y)?H(YX) ?(0.3?0.2p)log2(0.3?0.2p)?(0.5?0.2p)log2(0.5?0.2p)?0.2log20.2?(0.5plog22?0.3plog210?0.2plog25?0.3(1?p)log210?0.5(1?p)log22?0.2(1?p)log25) ?0.3log20.3?0.5log20.5?(0.3?0.2p)log2(0.3?0.2p)?(0.5?0.2p)log2(0.5?0.2p)令I(p)?0.2log2 (0.5?0.2p) ?0,得p?0.5 0.3?0.2p ?I(p)max?I(p)p?0.5?0.03645比特 2.9随机掷三颗骰子，以X表示第一颗骰子抛掷的结果，以Y表示第一和第二颗骰子抛掷的点数之和，以Z表示三颗骰子的点数之和。试求H(Z|Y)、H(X|Y)、H(Z|XY)，H(XZ|Y)和H(Z|X)。 解:令X=X1,Y=X1+X2,Z=X1+X2+X3,H(X1)=H(X2)=H(X3)=log26比特H(X)=H(X1)=log26=2.585比特H(Y)=H(X2+X3) = 2( 12363364365361log236?log2?log2?log2?log2)?log26363623633643656 =3.2744比特H(Z)=H(X1+X2+X3) ?2( 1321662161021615216 log2216?log2?log2?log2?log2 216216321662161021615212162521627216log2?log2?log2)216212162521627 =3.5993比特 所以 H(Z/Y)=H(X3)=2.585比特H(Z/X)=H(X2+X3)=3.2744比特H(X/Y)=H(X)-H(Y)+H(Y/X)=2.585-3.2744+2.585=1.8955比特 H(Z/XY)=H(Z/Y)=2.585比特H(XZ/Y)=H(X/Y)+H(Z/XY)=1.8955+2.585=4.4805比特2.12 计算习题2.9中的I(Y；Z)，I(X；Z)，I(XY；Z)，I(Y；Z|X)和I(X；Z|Y)。解:I(Y;Z)=H(Z)-H(Z/Y)=H(Z)-H(X3)=3.5993-2.585=1.0143比特I(X;Z)=H(Z)-H(Z/X)=3.5993-3.2744=0.3249比特I(XY;Z)=H(Z)-H(Z/XY)=H(Z)-H(Z/Y)=1.0143比特 I(Y;Z/X)=H(Z/X)-H(Z/XY)=H(X2+X3)-H(X3)=3.2744-2.585=0.6894比特I(X;Z/Y)=H(Z/Y)-H(Z/XY)=H(Z/Y)-H(Z/Y)=0 2.10 设有一个系统传送10个数字：0,1,?,9。奇数在传送时以0.5的概率错成另外的奇数，而其它数字总能正确接收。试求收到一个数字平均得到的信息量。 解:设系统输出10个数字X等概,接收数字为Y, 9 显然 w(j)?Q(i)p(j)?191 i?0 10?p(ji)?，H(Y)=log10 i?110H(Y/X)?x)?yx?p(x,y)log2p(y?偶 ?yx?p(x,y)log2p(yx)?奇 ?0?p(x)p(xx)log2p(xx)? p(x)p(yx)log 2 p(yx) i?奇 y?x,奇x?奇 ?5? 110?12?log?5?4?110?1 228?log28?1比特所以I(X;Y)= log210?1?2.3219比特 2.11令ul,u2,?,u8为一等概消息集，各消息相应被编成下述二元码字: ul=0000，u2=0011，u3=0101，u4=0110u5=1001，u6=1010，u7=1100，u8=1111通过转移概率为p的BSC传送。试求：(a)接收的第一个数字0与ul之间的互信息量。 (b)接收的前二个数字00与ul之间的互信息量。(c)接收的前三个数字000与ul之间酌互信息量。(d)接收的前四个数字0000与ul之间的互信息量。 解:（a）接收前一个数字为0的概率8 w(0)?q(ui)p(0ui)? i?0 I(u1;0)?logp(01)2 w(0)?log1?p 21?1?log2(1?p)bits 2 8 （b）同理 w(00)?q(ui)p(00i)? 4 i?0 I(up(00u1)(1?p)2 1;00)?log2w(00)?log21 ?2?2log2(1?p)bits 8 （c）同理 w(000)?q(ui)p(ui)? i?0 I(up(u1)(1?p)3 1;000)?log2w(000)?log21 ?3?3log2(1?p)bits8 （d）同理 w(0000)?q(ui)p(ui)?1(1?p)6?6p2(1?p)28 ?p4)i?0 第1章绪论 1.1信源、编码器、信道、干扰、译码器、信宿1.2香农 1.3通信系统模型 1.4信号是消息的表现形式，是物理的，比如电信号、光信号等。消息是信息的载荷者，是 信号的具体内容，不是物理的，但是又比较具体，例如语言、文字、符号、图片等。信息包含在消息中，是通信系统中被传送的对象，消息被人的大脑所理解就形成了信息。1.5略 第2章信息的统计度量 2.1少 2.2y的出现有助于肯定x的出现、y的出现有助于否定x的出现、x和y相互独立2.3FTTTF 2.42.12比特 2.5依题意，题中的过程可分为两步，一是取出一枚硬币恰好是重量不同的那一枚，设其发 生的概率为p1，由于每枚硬币被取出的概率是相同的，所以 p1? 181 所需要的信息量 I?A?logp1?6.34?bit? 二是确定它比其他硬币是重还是轻，设其发生的概率为p2，则 p2? 12 12 1162 总的概率 p?p1p2? 181? ? 所需要的信息量 I?logp?log162?7.34?bit? 2.6设A表示“大学生”这一事件，B表示“身高1.60m以上”这一事件，则 p?A?0.25 p?B?0.5 p?B|A?0.75 故 p?A|B? p?AB?p?B? ? p?A?p?B|A? p?B? ? 0.75?0.25 0.5 ?0.375 1p?A|B? 10.375 I?A|B?log ?log ?1.42?bit? 2.7四进制波形所含的信息量为log4?2?bit?，八进制波形所含信息量为log8?3?bit?，故 四进制波形所含信息量为二进制的2倍，八进制波形所含信息量为二进制的3倍。2.8 I?2?log2p?bit?I?3?log3p?bit?I?3?I?2?log23?1.585 故以3为底的信息单位是比特的1.585倍。2.9（1）J、Z（2）E（3）X 2.10（1）两粒骰子向上面的小圆点数之和为3时有(1,2)和(2,1)两种可能性，总的组合数为 C6?C6?36，则圆点数之和为3出现的概率为 1 1 p3? 236 ? 118 ?4.17?bit? 故包含的信息量为 （2）小圆点数之和为7的情况有(1,6),(6,1),(2,5),(5,2),(3,4),(4,3)，则圆点数之和为7出现的概率为 p7? 636 ?16 I?3?logp3?log 118 ?2.585?bit? 故包含的信息量为 I?7?logp7?log 16 2.11对于男性，是红绿色盲的概率记作p?a1?7%，不是红绿色盲的概率记作p?a2?93%， 这两种情况各含的信息量为 I?a1?log?1p?a1?logI?a2?log?p?a2?log 100710093 ?3.83?bit? ?0.105?0.366?bit? ?0.105?bit? 平均每个回答中含有的信息量为 H?A?p?a1?log?1p?a1?p?a2?log?1p?a2? 7100 ?3.83? 93100 对于女性，是红绿色盲的概率记作p?b1?0.5%，不是红绿色盲的概率记作p?b2?99.5%，则平均每个回答中含有的信息量为 H?B?p?b1?log?1p?b1?p?b2?log?1p?b2? 51000 ?log 10005 ?9951000 ?log 1000995 ?0.045?bit? 所以 H?A?H?B? ?1?12 1? ?log242? 2.12天平有3种状态，即平衡，左重，左轻，所以每称一次消除的不确定性为log3，12个 球中的不等重球（可较轻，也可较重）的不确定性为：?log?,所以3次测量可以找出该球。3log3?log24 2.13（1）当最后3场比赛麦克胜的次数比大卫多时，麦克最终才能胜，因此 P?胜?P?麦克胜3场?P?大卫胜少于3场?+P?麦克胜2场?P?大卫胜少于2场?P?麦克胜1场?P?大卫胜0场?18?78?38?48?38?18?2264 ? ，因为 2264 2264 2264 2064 同理 P?负? ，P?平?1? ? ? 麦克最终比赛结果的熵为 222222222020?222220?H?,?log?log?log? 646464646464?646464?log64?2?6? 4464 2264 log22? 2064 2064log20 ?4.4594?4.3219 ?6?3.0659?1.3506 因为胜、负、平这3种结果接近等概，所以该随机变量的熵接近最大熵。 （2）假定大卫最后3场比赛全部获胜，那么麦克也必须全部获胜最后3场比赛最终才能得平，否则就是负。麦克3场比赛全部获胜的可能性是2?3?1/8，因此在假定大卫最后3场比赛全部获胜的情况下麦克的最终比赛结果的条件熵是 2.14（1）假定一个家庭里有k个女孩，1个男孩，相应的概率是0.5k?0.5，因此女孩的平 ? ?1.5835比特果 7?1? H?3?log7?0.5436比特果 8?8? 均数是0.5?k0.5k?1，女孩的平均数和男孩的平均数相等。 k?1 （2）H?X?0.5ilog?0.5i?2 i?1 ? 2.15（1）根据题意，可以得到： p?E?p?F?p?U?1 1.0p?E?0.5p?F?0.0p?U?0.95 由式可以得到： p?F?1.9?2p?E? 将式代入式得到： p?E?0.9?p?U ? 由于p?E?,p?F?,p?U?的取值必须在0到1之间，由式和式可以得到p?E?的取值范围在0.9到0.95之间。(2)就业情况的熵为 ?1?1 H?p?E?log?pFlog? pE?p?F?1? ?p?E?log?1.9?2p?E?log pE? ?1 ?pUlog?p?U ? ? ?1 ?pE?0.9? ?1 ?p?E?0.9?log1.9?2pE? 它在p?E?的取值范围内的曲线如图所示。