信息论与编码理论1(A卷答案).doc

2012-2013 (2) 信息论与编码理论1 A卷答案一、 单项选择题（每题3分，总计15分） 1当底为e时，平均互信息的单位为（ C ）。A 奈特 B 哈特 C 奈特/符号 D 哈特/符号2下列量当交换位置时（ C ）没有对称性。A B C D 3下列（ A ）陈述是错误的。A 算术编码不需要知道信源的分布 B LZ编码不需要知道信源的分布 C 游程编码不需要知道信源的分布 D KY编码不需要知道信源的分布4下列数组中（ A ）不满足两个字母上的Kraft不等式。A (1，2，1) B (2,2) C (1,2,3) D （3，3，3） 5下列译码法则中（ A ）一定是错误概率最小的。A 最大后验概率译码准则 B 最大似然译码准则 C 最小距离译码准则 D 最大先验概率译码准则二、填空题（每空2分，总计12分）1若某离散信道转移概率矩阵为，则其信道容量为比特/符号。2若一个信道的输入熵为比特/符号，输出熵为比特/符号，比特/符号，则_3.4比特/符号_，疑义度为1.2比特/符号_。3平均互信息对信源概率分布是上凸函数，对信道的状态转移概率分布是下凸函数。4对信源任一个元唯一可译码的平均码长必大于等于。三、计算题（73分）1）（15分）设随机变量的联合概率分布如下： 01010 ，为模2加。分别求。解: 的分布率为01则比特/符号.3分的分布率为01则=0.811比特/符号. .6分01010=,= =0,= =0.688比特/符号. .10分01 =,=1 =,=0则=0.2075比特/符号. .15分2）（22分）若离散无记忆信源的概率分布为 分别构造二元，三元Huffman编码（要求码长方差最小，但不需求出），Shannon编码，Fano编码，Shannon-Fano-Elias编码。 并求中二元Huffman编码的编码效率。（只列出式子即可）解:对信源按概率从大到小排序, ,建立码树则有二元Huffman编码: .4分要进行三元Huffman编码,则需要添加一个空信源,成为,建立码树则有三元Huffman编码: ,.8分Shannon编码如下:信源码长累加概率码字200020.40140.7101140.8110050.91110050.9511110.12分Fano编码如下:信源概率第1次分组第2次分组第3次分组第4次分组第5次分组码字0.4000.310100.1101100.11011100.0510111100.05111111.16分Shannon-Fano-Elias编码信源概率 二元码字0.10.10.0550.00001000010.050.150.12560.0010000010000.050.20.17560.0010110010110.40.60.430.0110110.10.70.6550.101001101000.31.00.8530.110110.20分二元Huffman编码的平均码长为=2.2, .21分编码效率为.22分3）（14分）若二元信源，对1101011进行算术编码。解：,码长利用, = = = = =0.48419189453125=(0.0111101). 编码为0111110.4）（22分）对输入流0100100100111分别用LZ-77，LZ-78，LZW和KY算法进行编码,并对LZW编码进行解码。 解：LZ-77编码：(0,0,0),(0,0,1),(2,1,0),(3,3,1),(3,3,1),(1,1,eof). .4分LZ-78编码：将输入流序列分段为0，1，00，10，01，001，11，则有字典段号短语10213004105016001711码字为(0,0),(0,1),(1,0), (2,0),(1,1),(3,1),(2,1) .9分LZW编码：初始字典 码字12词条01新词条输出码345678910001100001000110001111NYYYYYYYY121354322,eof编码为初始字典和数列1，2，1，3，5，4，3，2，2,eof. .13分解码：收到初始字典和数列1，2，1，3，5，4，3，2，2,eof.后重构字典和输出流如下：1) 输入1，输出0，由于下一个输入为2，则存01为新词条3，2) 输入2，输出1，由于下一个输入为1，则存10为新词条4，3) 输入1，输出0，由于下一个输入为3，则存00为新词条5，4) 输入3，输出01，由于下一个输入为5，则存010为新词条6，5) 输入5，输出00，由于下一个输入为4，则存001为新词条7，6) 输入4，输出10，由于下一个输入为3，则存100为新词条8，7) 输入3，输出01，由于下一个输入为2，则存011为新词条9，8) 输入2，输出1，由于下一个输入为2，则存11为新词条10，9) 输入2，输出1，由于下一个输入为eof，则终止。译码为0100100100111。 .17分KY编码：1）由于前4位没有重复段，首次读入第五位1，令，则，令，则，动态字典为；2）读入第六位0，则，令，则，动态字典为；3）读入第七位0，则，动态字典为；4）读入第八