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

第二章信息量和熵2.2八元编码系统，码长为3，第一个符号用于同步，每秒1000个码字，求它的信息速率。解：同步信息均相同，不含信息，因此每个码字的信息量为28log=23=6bit因此，信息速率为61000=6000bit/s2.3掷一对无偏骰子，告诉你得到的总的点数为：(a)7;(b)12。问各得到多少信息量。解：(1)可能的组合为{1，6},{2，5},{3，4},{4，3},{5，2},{6，1})(ap=366=61得到的信息量=)(1logap=6log=2.585bit(2)可能的唯一，为{6，6})(bp=361得到的信息量=)(1logbp=36log=5.17bit2.4经过充分洗牌后的一副扑克（52张），问：(a)任何一种特定的排列所给出的信息量是多少？(b)若从中抽取13张牌，所给出的点数都不相同时得到多少信息量？解：(a))(ap=!521信息量=)(1logap=!52log=225.58bit(b)花色任选种点数任意排列13413!13)(bp=1352134!13A=1352134C信息量=1313524loglogC=13.208bit2.9随机掷3颗骰子，X表示第一颗骰子的结果，Y表示第一和第二颗骰子的点数之和，Z表示3颗骰子的点数之和，试求)|(YZH、)|(YXH、),|(YXZH、)|,(YZXH、)|(XZH。解：令第一第二第三颗骰子的结果分别为321,,xxx，1x，2x，3x相互独立，则1xX，21xxY，321xxxZ)|(YZH=)(3xH=log6=2.585bit)|(XZH=)(32xxH=)(YH=2(361log36+362log18+363log12+364log9+365log536)+366log6=3.2744bit)|(YXH=)(XH-);(YXI=)(XH-[)(YH-)|(XYH]而)|(XYH=)(XH，所以)|(YXH=2)(XH-)(YH=1.8955bit或)|(YXH=)(XYH-)(YH=)(XH+)|(XYH-)(YH而)|(XYH=)(XH，所以)|(YXH=2)(XH-)(YH=1.8955bit),|(YXZH=)|(YZH=)(XH=2.585bit)|,(YZXH=)|(YXH+)|(XYZH=1.8955+2.585=4.4805bit2.10设一个系统传送10个数字，0，1，…，9。奇数在传送过程中以0.5的概率错成另外一个奇数，其余正确接收，求收到一个数字平均得到的信息量。解：信道XY9,7,5,3,1i8,6,4,2,0i√Χ);(YXI=)(YH-)|(XYH因为输入等概，由信道条件可知，101)8181818121(101)(101)(为偶数为奇数iiypiiyp即输出等概，则)(YH=log10)|(XYH=)|(log)(ijjjiixypyxp=)|(log)(ijjijixypyxp偶-)|(log)(ijjijixypyxp奇=0-)|(log)(ijjijixypyxp奇=-)|(log)|()(97,5,3,1iiiiiixypxypxp，-)|(log)|()(97531ijjiiijixypxypxp，，，，＝=10121log25+1012141log845=4341=1bit);(YXI=)(YH-)|(XYH=log10-1=log5=2.3219bit2.11令{821,,uuu，}为一等概消息集，各消息相应被编成下述二元码字1u=0000，2u=0011，3u=0101，4u=0110，5u=1001，6u=1010，7u=1100，8u=1111通过转移概率为p的BSC传送。求：(a)接收到的第一个数字0与1u之间的互信息量。(b)接收到的前二个数字00与1u之间的互信息量。(c)接收到的前三个数字000与1u之间的互信息量。(d)接收到的前四个数字0000与1u之间的互信息量。解：即)0;(1uI，)00;(1uI，)000;(1uI，)0000;(1uI)0(p=4)1(81p+481p=21)0;(1uI=)0()|0(log1pup=211logp=1+)1log(pbit)00(p=]2)1(4)1(2[8122pppp=41)00;(1uI=)00()|00(log1pup=4/1)1(log2p=)]1log(1[2pbit)000(p=])1(3)1(3)1[(813223pppppp=81)000;(1uI=3[1+)1log(p]bit)0000(p=])1(6)1[(814224pppp)0000;(1uI=42244)1(6)1()1(8logpppppbit2.12计算习题2.9中);(ZYI、);(ZXI、);,(ZYXI、)|;(XZYI、)|;(YZXI。解：根据题2.9分析)(ZH=2(216log2161+3216log2163+6216log2166+10216log21610+15216log21615+21216log21621+25216log21625+27216log21627)=3.5993bit);(ZYI=)(ZH-)|(YZH=)(ZH-)(XH=1.0143bit);(ZXI=)(ZH-)|(XZH=)(ZH-)(YH=0.3249bit);,(ZYXI=)(ZH-)|(XYZH=)(ZH-)(XH=1.0143bit)|;(XZYI=)|(XZH-)|(XYZH=)(YH-)(XH=0.6894bit)|;(YZXI=)|(YZH-)|(XYZH=)(XH-)(XH=0bit2.14对于任意概率事件集X,Y,Z，证明下述关系式成立(a))|,(XZYH)|(XYH+)|(XZH，给出等号成立的条件(b))|,(XZYH=)|(XYH+),|(YXZH(c)),|(YXZH)|(XZH证明：(b))|,(XZYH=-xyzxyzpxyzp)|(log)(=-xyzxyzpxypxyzp)]|()|(log[)(=-xyzxypxyzp)|(log)(-xyzxyzpxyzp)|(log)(=)|(XYH+)|(XYZH(c)),|(YXZH=-xyzxyzpxyzp)|(log)(=xyxyp)([-zxyzpxyzp)|(log)|(]xyxyp)([-zxzpxzp)|(log)|(]=-xyzxzpxyzp)|(log)(=)|(XZH当)|(xyzp=)|(xzp，即X给定条件下，Y与Z相互独立时等号成立(a)上式(c)左右两边加上)|(XYH，可得)|(XYH+),|(YXZH)|(XYH+)|(XZH于是)|,(XZYH)|(XYH+)|(XZH2.28令概率空间21,211,1X，令Y是连续随机变量。已知条件概率密度为其他,022,41)|(xyxyp，求：(a)Y的概率密度)(y(b));(YXI(c)若对Y做如下硬判决1,111,01,1yyyV求);(VXI，并对结果进行解释。解：(a)由已知，可得)1|(xyp=elsey01341)1|(xyp=elsey03141)(y=)1(xp)1|(xyp+)1(xp)1|(xyp=elseyyy0318111411381(b))(YHC=11134log4128log81=2.5bit)|(XYHC=13)1|(log)1|()1(dyxypxypxp31)1|(log)1|()1(dyxypxypxp=dydy311341log412141log4121=2bit);(YXI=)(YHC-)|(XYHC=0.5bit(c)由)(y可得到V的分布律V-101p1/41/21/4再由)|(xyp可知V-101p(V|x=-1)1/21/20p(V|x=1)01/21/25.14log2412log21)(VHbit2]2log212log21[21)|(XVH=1bit);(VXI=)|()(XVHVH=0.5bit2.29令)(1xQ和)(2xQ是同一事件集U上的两个概率分布，相应的熵分别为1)(UH和2)(UH。(a)对于10，证明)(xQ=)(1xQ+)1()(2xQ是概率分布(b))(UH是相应于分布)(xQ的熵，试证明)(UH1)(UH+)1(2)(UH证明：(a)由于)(1xQ和)(2xQ是同一事件集U上的两个概率分布，于是)(1xq0，)(2xq0dxxqx)(1=1，dxxqx)(2=1又10，则)(xq=)(1xq+)1()(2xq0dxxqx)(=dxxqx)(1+dxxqx)()1(2=1因此，)(xQ是概率分布。(b))(UH=dxxqxqxqxqx)]()1()(log[)]()1()([2121=dxxqxqxqx)]()1()(log[)(211dxxqxqxqx)]()1()(log[)()1(212xdxxqxq)(log)(11xdxxqxq)(log)()1(22（引理2）=1)(UH+)1(2)(UH第三章信源编码——离散信源无失真编码3.1试证明长为N的D元等长码至多有1)1(DDDN个码字。证：①在D元码树上，第一点节点有D个，第二级有2D，每个节点对应一个码字，若最长码有N，则函数有NiiD1=DDDN1)1(=1)1(DDDN，此时，所有码字对应码树中的所有节点。②码长为1的D个；码长为2的2D个，…，码长为N的ND个∴总共NiiD1=1)1(DDDN个3.2设有一离散无记忆信源996.0,004.0,21aaU。若对其输出的长为100的事件序列中含有两个或者少于两个1a的序列提供不同的码字。(a)在等长编码下，求二元码的最短码长。(b)求错误概率（误组率）。解:(a)不含1a的序列1个长为100的序列中含有1个1a的序列1100C=100个长为100的序列中含有2个1a的序列2100C=4950个∴所需提供码的总数M=1+100+4950=5051于是采用二元等长编码DMNloglog=12.3，故取N=13(b)当长度为100的序列中含有两个或更多的1a时出现错误，因此错误概率为eP=11000100)996.0(C-991100)996.0)(004.0(C9822100)996.0()004.0(C=310775.73.3设有一离散无记忆信源，U=43,41,21aa，其熵为)(UH。考察其长为L的输出序列，当0LL时满足下式)()(UHLuIPLr(a)在=0.05，=0.1下求0L(b)在=310，=810下求0L(c)令T是序列Lu的集合，其中)()(UHLuIL试求L=0L时情况(a)(b)下，T中元素个数的上下限。解：)(UH=kkpplog=34log434log41=0.81bit)]([kaIE=)(UH2I=})]()({[2UHaIEk=])([2kaIE-)(2UH=kkkUHpp)()(log22=0.471则根据契比雪夫大数定理22)()(LUHLuIPILr(a)L=22I=2)05.0(1.0471.0=1884(b)L22I=238)10(10471.0=