信息论基础期末试卷B答案

第1页共5页○?○?大学2008-2009学年第一学期2006级信息与计算科学专业本科卷B参考答案与评分标准课程名称信息论基础课程号（???）考试形式（闭卷笔试）时间（120分钟））一、（15分）解：（1）由图可知一阶马尔可夫信源的状态空间}2,1,0{AE，平稳后信源的概率分布就等于一阶马尔可夫信源状态的极限分布，即)()(iiaPEQ，3,2,1i；EEi，Aai；----------------（1分）从状态图中分析可知，这三个状态都是正规常返态，所以此马尔可夫链具有各态历经性，平稳后状态的极限分布存在。可得状态一步转移矩阵PPPPPPP000，1)2()1()0()2()1()0()2()1()0(QQQQQQPQQQT----------------（2分）得：3/1)2()1()0(QQQ，----------------（2分）则可得：3/1)2()1()0(ppp；----------------（2分）(2)一阶马尔可夫信源的熵321()(|)iiiHHQEHXE(0)(|)(1)(|1)(2)(|2)PHXEPHXPHX111(,0,)(,,0)(0,,)333HPPHPPHPPloglog()PPPPHP；----------------（4分）(3)当0P,0H当1P,1H；----------------（2分）因为信息熵是表示信源的平均不确定性，题中当0P或1P时表明信源从某一状态出发转移到另一状态的情况是一定发生或一定不发生，即是确定的事件。当1P时，从0状态一定转移到2状态，2状态一定转移到1状态，1状态一定转移到0状态。所以不论从何状态起信源输出的序列一定是021021序列，完全确定的。当0P时，0状态永远处于0状态，1状态永远处于1状态，2状态用于处于2第2页共5页状态。信源输出的符号序列也是确定的。所以当1P或0P时，信源输出什么符号不存在不确定性，完全是确定的，因此确定信源的信息熵等于零。----------------（4分）二、（20分）解：如下图所示,其中PPPPQ1qqqqQ2；----------------（2分）----------------（2分）它们都是二元对称离散信道；又因为11()CHP，21()CHq；所以这个和信道容量为：122221112log2loglog2(1)2(1)22CCcippqqCppqq----------------（4分）其中，Q1的利用率qqppppCCqqppppP1111)1()1()1(21其中，Q2的利用率qqppqqCCqqppqqP1112)1()1()1(22----------------（2分）由此得：qqppqqqqppppqqppqqPaPaPqqppppPaPaP111243111121)1()1(2)1(21)()()1()1(2)1(21)()(----------------（2分）三、（12分）解：要将此信源编码成为r元唯一可译变长码，其码字对应的码长)3,2,3,2,1,1(),,,,,(654321llllll必须满足克拉夫特不等式，即132321161rrrrrrrili；----------------（5分）所以要满足122232rrr，其中r是大于或等于1的正整数；----------------（2分）可见，当1r时，不能满足Kraft不等式；----------------（1分）第3页共5页当2r时,1824222,不能满足Kraft；----------------（1分）当3r时,127262729232,满足Kraft；----------------（1分）所以，求得r的最大值下限值等于3。----------------（2分）四、(15分)解：信源的概率分布为：)152,152,51,51,31()(isp二元霍夫曼码：00，10，11，010，011；----------------（7分）码长：2，2，2，3，3；----------------（2分）当信源给定时，二元霍夫曼码是最佳二元码；所以对于概率分布为)51,51,51,51,51(的信源，其最佳二元码就是二元霍夫曼码。----------------（2分）这二元霍夫曼码一定是三个信源符号的码长为2（码符号/信源符号），另二个信源符号的码长为3（码符号/信源符号），其平均码长最短。因此，上述对概率分布为)152,152,51,51,31(信源所编的二元霍夫曼码也是概率分布为)51,51,51,51,51(信源的最佳二元码。----------------（4分）五、(20分)解：令信道输入为mx时输出y的转移概率为(|)NmPyx，则最小错误概率译码实际上为最大后验概率译码)()|()()|(ywxyPmQymPmN，其中MmmNxyPmQyw1)|()()(----------------（3分）对于给定的y和所有的m，其()wy必然相同，所以)|()|('ympymp就可化为比较如下式子)|()()|()(''mNmNxyPmQxyPmQ----------------（3分）则当先验等概时()(')QmQm上式化为)|()|('mNmNxyPxyP，此即最大似然译码。----------------（4分）所以，当先验等概时，最小错误概率译码与最大似然译码是等价的。---------（2分）因为2M且输入等概，所以由题可知，当收到2y判为1x时应为错，同理，收到1y区间中任一序列，判为2x也为错。这样：)1(43421pPPPPPeee；----------------（4分）当收到的序列属于Y3时无法判定为X1或X2，但此时必然有错误发生。所以，有错而不能判决的概率为：22)1(6PPPe----------------（4分）六、(18分)第4页共5页解：信源sPS9.01.021ss（1）iiisPsPsHlog210.469比特/符号----------------（2分）剩余度2log1sH0.531=53.1％；----------------（2分）(2)码符号}1,0{X，对信源S编紧致码为：1s0，12s----------------（2分）其平均码长1L码符号/信源符号；----------------（1分）(3)当2N时iPS2=81.0,09.0,09.0,01.0,,,224133212111ssssssss----------------（2分）紧致码（即霍夫曼码）为,4,3,21码字iW0,10,110,111码长il1,2,3,3----------------（3分）平均码长NLN=21iiilP410.645码符号/信源符号3N时，iPS3=32222223876543219.0,9.01.0,9.01.0,9.01.0,9.01.0,9.01.0,9.01.0,1.0,,,,,,,----------------（1分）对信源3S进行霍夫曼编码，其紧致码为,8,7,6,5,4,3,21码字iW0,100,101,110,11100,11101,11110,11111码长il1,3,3,3,5,5,5,5----------------（3分）平均码长NLN=31iiilP810.533码符号/信源符号。----------------（2分）