桂林理工大学2009年春季信息论与编码考试试题与答案

桂林理工大学2009年春季信息论与编码考试试题与答案考试时间：7月14日（21周周二）下午15：00-17：00；地点：4525教室1)闭卷考试，不能参考课本、笔记等。2)考试中需要一些计算，请准备计算器3)题较多，需要熟练，有速度4)解题时，先把公式写上，即使没有结果，也会适当给分一.填空题（每空一分，共20分）2.自信息是对事物状态（或它的存在方式）的不确定性的一种描述，其中自信息()Ix=)(1logxp；事件发生前，它表示时件发生的不确定性，事件发生后，它表示事件所含有的信息量。2.离散信源的熵有如下含义：在信源输出之前，它表示信源的平均不确定性；在信源输出之后，它表示每个消息（或符号）所提供的平均信息量；它的单位是：比特/符号。当信源等概率分布时，其熵最大，最大值为（设信源有q个符号）qlog。2.离散平稳信源（有记忆）其各维联合概率分布与时间起点无关。对于有限记忆长度的离散平稳信源，可用有记忆长度的条件熵表示其熵。3.平均互信息是输入分布的上凸函数，是信道传递概率的下凸函数。3.信道的信息传输率就是平均互信息，信道容量定义为固定信道的最大信息传输率。3.有如下串联信道，1YXZW信道信道2信道3写出(),(;),(;),(,)HXIXYIXZIXW的大小关系);();();()(WXIZXIYXIXH4.连续信源的差熵的表达式是()hX=Rdxxpxp)(log)(，它其实并不是实际信源输出的绝对熵，只是和离散信源的熵在形式上统一起来了。差熵可以为负值。4.写出香农公式：)1log(0WNpWCst它给出了信息传输率tC、带宽W、信噪比之间的关系。它给出了达到无失真传输速率的理论极限值，又称为香农极限5.信源编码是通过压缩信源冗余度来提高信息传输率，而信道编码增加冗余度来提高信号的抗干扰能力。5.非奇异码、唯一可译码、即时码的包含关系是：非奇异码唯唯一可译码即时码。5.香农第一定理是无失真变长信源编定理，他指出是无失真信源压缩的极限值；该定理又被称为无噪信道编码定理。为了提高编码效率，有时需要对N次扩展信源进行编码；对于变长码，在N不太大时，就能达到较高效率，所以比等长码更具优势，5.在给定信源的情况下，对它进行编码，不同的编码方式会有不同的平均码长；平均码长最短的码叫做紧致码（或最佳码）。5.在信源编码中，平均码长定义为：qiiilspL1)(，信息传输率定义为：LsHR)(，编码效率定义为：rLsHlog)(。6.译码的错误概率与信道的统计特性有关，也与译码规则有关。6.香农第二定理是有噪信道编码定理，他指出当信息传输率R＜C时，只要码长n足够长，并采取适当的编码、译码方式，可以使得译码的平均错误概率任意小。8.霍夫曼编码是否是最佳码？是，其平均码长界限为：1)()(sHLsHrr。9.线性分组码中，（7，3）码的码率（信息传输率）为73。10.线性分组码的最小汉明距离等于3。已知最小汉明距离为d，其纠错与检错能力为：检测e个随机错误时，de+1;纠正t个随机错、错误时，d2t+1；纠正t个错误，同时检测e个错误时，dt+e+1。二：（10分）离散无记忆信源X的信源空间（概率空间）为：02111(),,244aaaXpx123=1（1）求每个信源符号（123,,aaa）的自信息。（2）求信源X的信息熵（3）信源符号123(,,)aaa的概率如何分布时，才能使信源的熵最大？最大熵是多少？（4）写出二次扩展信源2X的信源空间（5）求二次扩展信源2X的信息熵（6）信源的输出形成一个消息序列：0012002110，求此序列中平均每个符号携带的信息量。（7）信源不断输出，消息序列趋于无限长，求此序列中平均每个符号携带的信息量。解：（1）12log)(1log)(11apaI（比特）24log)(1log)(22apaI（比特）24log)(1log)(33apaI（比特）（2）5.1)(log)()(log)()(log)()(332211apapapapapapXH（比特/符号）（3）信源符号123(,,)aaa等概率分布时，才能使信源的熵最大，最大熵为：5850.13log)(maxXH（比特/符号）（4）16/116/18/116/116/18/18/18/14/1222120121110020100)(22XPX（5）)(2)(2XHXH=35.12（比特/符号）（6）5.1)4/1(1log)4/1(1log)2/1(1log101235I（比特/符号）（7）因为信源输出无限长时，其序列概率分布与信源一样，所以每个符号的信息量为：5.1)(XHI（比特/符号）三.（10分）设信源12()0.6,0.4Xxxpx通过一个干扰信道，输出信号为12[,]Yyy，其信道矩阵（传递矩阵）为：516631,44P求：（1）输出信号Y的概率分布（2）求XY、的联合概率矩阵()Pxy（3）求后向概率矩阵(|)Pxy（3）噪声熵(|)HYX（4）信道疑义度（或损失熵）(|)HXY（5）平均互信息(;)IXY解：（1）2.08.0)(21yyyPY（2）1.03.01.05.0)(xyPXY（3）5.0375.05.0625.0)/(/yxPYX（4）7145.041log1.043log3.061log1.065log5.0)/(log)()/(2121ijijjixyPyxPXYH（5）9635.05.0log1.0375.0log3.05.0log1.0625.0log5.0)/(log)()/(2121ijjijiyxPyxPYXH（6）0074.0)/()()/()();(YXHXHXYHYHYXI四.（5分）计算下面几类信道的信道容量C,并指出输入概率如何分布时，才能达到此信道容量：11/21/20000003/53/101/100000001P有噪无损信道：等概率分布时，585.13loglogrC2101001P无噪有损信道：等概率分布时，12loglogsC（比特/符号）31111336611116633P对称离散信道：等概率分布时0817.0)6/1log(6/1)6/1log(6/1)3/1log(3/1)3/1log(3/14log)()(4321ppppHYHC、、、写出下面几类连续信源的差熵()hX：4高斯信源2221()()exp()22xmpx其中23,4m0471.32log21)(2exh（比特/自由度）5指数分布信源()(0;0)xpxex其中1/44427.3log)(exh（比特/自由度）五：（10分）有二元对称信道，其信道矩阵如下所示。该信道以1500个二元符号/秒的速度传输输入符号。现有一消息序列共有14000个二元符号，并设在这个消息中1(0)(1)2pp。问从信息传输的角度考虑，10秒钟内能否将信息此序列无失真地传送完？信道矩阵：0.980.020.020.98P解：8586.0)02.0,98.0(2log)/()()/()();(HXYHYHYXHXHYXI（比特/符号）4102878.18586.0101500);(101500YXII总(比特)因为总IXH410400.1)(14000所以知，不能将信息序列无失真传送完、。六：(10分)设在平均功率受限的高斯加性波形信道中，信道带宽为4KHz，又设（信号功率+噪声功率）/噪声功率=20dB。（即10lg(1)20snPdBP，其中lg是以10为底的对数）。1)试计算该信道传送的最大信息率R(单位时间)。2)若信噪比降为10dB（即10lg(1)10snPdBP），要达到相同的最大信息传输速率，信道带宽应为多少？解：（1）由10lg(1)20snPdBP知：2101NsPP又4105675.2)1log(NsPPWTR（比特/秒）（2）由题意知：信噪降低为10dB后，101NsPP所以,要使R=R’的W=HzR310810log七：(5分)离散信源的概率空间为：34121111(),,,8824ssssSps，采用香农编码，iisw求每个码字iw的码长，并用树图法构造此码。解：香农编码的马场满足：iiPl1log故：43214321llllssss、、、对应码长、、、分别为：1、2、3、3.树图法构造的码为：0010000114321ssss八：(5分)有一离散信道，其信道矩阵为：111236111623111362，输入概率分布为：11()2px，231()()4pxpx。分别按极大似然法和最小错误概率法确定译码规则，并计算相应的错误概率。解：根据极大似然译码规则，可选的译码函数为：332211)()()(aYFaYFaYF平均错误概率：21)3161(41)6131(41)3161(21EP根据最小错误概率法，先求出联合概率分布81241121121812411216141，则译码函数为：331211)()()(aYFaYFaYF平均错误概率：4583.02411)121121()24181()121241(PE九：(10分)设线性分组码的生成矩阵为：G求其对应的一致校验矩阵H错误图样及伴随式若接收码字为000110，传输是否正确？用伴随式法求译码结果。解：100100101010011001G100110010001001011H错误图样以及对应的伴随式为：ES100000010000001000000100000010000001100010001100101011因为)110(100010001100101011011000THR对应错误图样知错误发生在第一个位置所以用伴随式法译码结果为;(100110)十：(15分)一阶二元马尔科夫信源，1)求信源的稳态分布2)求信源的熵3)用三个符号合成一个新符号，作为新的信源，求新信源的概率分布4)对此新信源进行二元霍夫曼编码5)求每个基本信源符号（非合成符号）对应的平均码长6)求编码效率解：假设信源的转移概率分布为：8.02.01.09.0（1）设稳态信源分布为：2110QQ，则21QQ*8.02.01.09.0=21QQ-------1又121QQ-----------2联立以上两式得：313221、QQ所以信源稳态分布为：3132（2）信源的熵：0.5533)08,2.0()1.0,9.0(21HQHQH（比特/符号）（3）54.09.09.032)0/0()0/0()0()000(PPpP06.01.09.032)0/1()0/0()0()001(PPpP0133.02.01.032)1/0()0/1()0()010(PppP0533.08.01.032)1/1()0/1()0()011(PppP06.09.02.031)0/0()1/0()1(