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

信息论与编码理论习题答案全解第二章信息量和熵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的概率错成另外一个奇数，其余正确接收，求收到一个数字平均得到的信息量。解：8,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的分布律再由)|(xyp可知5.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--?=4.711310?(c)由条件可知Lu为典型序列，若设元素个数为TM，则根据定理))(())((22)1(εεσ'+'-≤≤'-UHLTUHLM其中εσ='，σε='，可知(i)1.0=='εσ，05.0=='σε，1884=L下边界：84..1431))((29.02)1(?='-'-εσUHL上边界：))((2ε'+UHL=24..16202故24..162084..1431229.0≤≤?TM(ii)610-=='εσ，310-=='σε，111071.4?=L111081.3))((29999.02)1(?'-?='-εσUHL))((2ε'+UHL=111082.32?故11111082.31081.3229999.0??≤≤?TM3.4(a)各码是否满足异字头条件？是否为唯一可译码？(b)当收到1时得到多少关于字母a1的信息？(c)当收到1时得到多少关于信源的平均信息？解：①码A是异头字码，而B为逗点码，都是唯一可译码。②码A32.14.01log)()1|(log)1;(21121===apapaIbit码B014.04.0log)1()()1,(log)1()()1()1|(log)1;(1121121=?===papappappapaIbit③码AU=｛4321,,,aaaa｝∑==41)1;()1|()1;(kkkaIapuI=0)1;()1|(11+aIap=1.32bit=05.006.007.008.090.010.012.013.014.016.010*********aaaaaaaaaaU码B∑==41)1;()1|()1;(kkkaIapuI=0bit（收到1后，只知道它是码字开头，不能得到关于U的信息。）3.5令离散无记忆信源(a)求最佳二元码,计算平均码长和编码效率。(b)求最佳三元码,计算平均码长和编码效率。解：(a)0101010101010.050.060.070.080.090.100.120.130.140.110.230.150.160.190.270.310.580.42101010100001001110011011100100011101010111a2a3a4a5a6a7a8a9a10a∑-=kkppUHlog)(=3.234bit平均码长∑=kkknpn=3.26=DnRlog=效率%2.99log)()(===DnUHRUHη(b)0.160.140.130.120.100.090.080.070.060.05010120120120210.110.240.330.4311a2a3a4a5a6a7a8a9a10a0001021012202122110111平均码长∑=kkknpn=2.11DnRlog==3.344效率%6.96)(==RUHη3.6令离散无记忆信源?=2.0.....3.0...5.0.....3.........2.........1aaaU(a)求对U的最佳二元码、平均码长和编码效率。(b)求对U2的最佳二元码、平均码长和编码效率。(c)求对U3的最佳二元码、平均码长和编码效率。解：(a)0.50.30.210.501011a2a3a10001n=0.5×1+0.3×2+2×0.2=1.5∑=-=485.1log)(kkppUHbit%99)(==RUHη(b)∵离散无记忆∴H(U1U2)=2H(U)=2.97bitp(a1a1)=0.25,p(a1a2)=0.15,p(a1a3)=0.1,p(a2a1)=0.15,p(a2a2)=0.09p(a2a3)=0.06,p(a3a1)=0.1,p(a3a2)=0.06,p(a3a3)=0.040.250.150.150.10.10.090.060.060.0411aa21aa12aa31aa13aa22aa32aa23aa33aa1000101011011100000001011001110.10.150.20.250.30.450.55010110101010101132==∑kknpn5.122==nnDnUUHlog)(221=η=397.2=0.99(c)有关3U最佳二元类似略3.7令离散无记忆信源=)()()(21..........2.........1ikapapapaaaU且0≤P(a1)≤P(a2)≤….≤P(ak)<1。定义Qi=∑-=11)(ikkap,i>1，而Q1=0，今按下述方法进行二元编码。消息ak的码字为实数Qk的二元数字表示序列的截短（例如1/2的二元数字表示序列为1/2→10000…，1/4→0100…）,保留的截短序列长度nk是大于或等于I(ak)的最小整数。(a)对信源??=161,161,161,161,81,81,41,41.....8......7.......6.......5......4......3.......2...1aaaaaaaaU构造码。(b)证明上述编码法得到的码满足异字头条件，且平均码长n满足H(U)≤n≤H(U)+1。解：(a)(b)反证法证明异字头条件令k<-2=""122+--≤≤k=""a=""i=""k=""n=""p=""q=""’，若k=""≤<--'2<=""从而得k=""又由1)()(+≤≤k=""可知，=""是k="">这与假设ka是ka'的字头（即kkkpQQ+='）相矛盾，故满足异字头条件。由已知可得11log1log+<≤kkkpnp对不等号两边取概率平均可得∑∑∑+<≤kkkkkkkkkppnppp11log1log即1)()(+<≤UHnUH3.8扩展源DMC，???=4.0,6.02.....1aaU(a)求对U的最佳二元码、平均码长和编码效率。(b)求对U2的最佳二元码、平均码长和编码效率。(c)求对U3的最佳二元码、平均码长和编码效率。(d)求对U4的最佳二元码、平均码长和编码效率。解：(a)01=C，2C=1，n=197.0)(=UHbit%97)(==RUHη(b)DMC信道11aa21aa12aa22aa00011011110.60.401010.360.240.240.1622=n，1=n，%97)(==nUHη(c)111aaa211aaa121aaa112aaa221aaa212aaa122aaa222aaa01111000001100101110011010.2160.1440.1440.1440.0960.0960.0960.0640.160.1920.2040.