1、第 1 页 共 5 页 2011-2012 信息论与编码理论 1 B 卷答案 一、 单项 选择题（每 题 3 分，总计 15 分） 1当底为 e 时，熵的单位为（ C ）。 A 奈 特 B 哈特 C 奈 特 /符号 D 哈特 /符号 2下列 关系式中 ( B )正确 。 A )();( XIYXI B );(),( YXIYXH C )|()|( XYHYXH D );();( YXHYXI 3 下列 （ D ）陈述是正确的 。 A Shannon 编码是最优码 B LZ 编码是异字头码 C Huffman 编码可以不需要知道信源的分布 D 典型序列的数目不一定比非典型的多 4下列数组中（ A
2、 ）不满足二个字母上的 Kraft 不等式。 A (1， 1， 1) B (2,2,2,2) C (3,3,3) D （ 4， 4， 4） 5 下列（ D ）是只对输出对称的。 A 316121 216131B 2.04.04.04.02.04.04.04.02.0 C 323131323231D 2.04.04.0 4.02.02.0二、填空题（每 空 2 分，总计 20 分） 1 若二元离散无记忆中 25.0)0( p ， 75.0)1( p ，则当给出 100 比特的信源序列，其中有 5 个 1，则其自信息为 3log5200 2 比特 ，整个序列的熵为 )3log432(1002比特
3、/符号 . 2 若某离散信道信道转移概率矩阵为5.025.025.025.05.025.025.025.05.0 ，则其信道容量为5.13log2 比特 /符号 ；转移概率矩阵为25.05.025.05.025.025.025.025.05.0，则其信道容量为 5.13log2 比特 /符号 。 3. 两个相同的 BSC 做级联信道，其信道转移矩阵分别为 pp pp1 1， 则级联信道的信道转移矩阵为 222222122 22221 pppp pppp，无穷多个级联后的矩阵为 5.05.0 5.05.0。 4若 一个信道的输入熵为 6.2)( XH 比特 /符号 ， 输出熵为 3.2)( YH
4、 比特 /符号 ，7.1);( YXI 比特 /符号 ，则 ),( YXH 3.2 比特 /符号 ， 散布 度为 0.6 比特 /符号 。 第 2 页 共 5 页 5 在二元 LZ 编码中，若 信源有 K 个，某段信源序列共有 M 个字典，则码长 KM 22 loglog 。 6 存在 D 元唯一可译码，其平均码长必小于 1log )( DUH。 三 、 判断题 （每 题 2 分，总计 10 分） 1. 概率 小 的事件自信息大 （ ） 2. 若一个码字集合中的码字长度满足 Kraft 不等式 ，则其必为 逗点 码。 （ ） 3. 若码字都被配置在树的叶子节点处，则这种码一定是 异字头 码。（
5、 ） 4. 平均互信息是下 凸函数。（ ） 5. 算数编码需要知道信源的分布。 （ ） 四 、 计算题 （ 55 分） 1）（ 15 分）设随机变量 YX, 的联合概率分布如下： XYZ 。分别求 );(),|(),(),( ZXIYXHYHXH 。 解 : X 的分布率为 X 0 1 p 21 21 则 1)( XH 比特 /符号 . Y 的分布率为 Y 0 1 p 41 43 则 3lo g432)(2YH比特 /符号 . Y X 0 1 0 41 41 1 0 21 Z X 0 1 0 21 0 第 3 页 共 5 页 )0( )0,0()0|0( YP YXpYXp=1,)1( )1,
6、0()1|0( YP YXpYXp=31 )0( )0,1()0|1( YP YXpYXp=0,)1( )1,1()1|1( YP YXpYXp= 32 )1|0(log)1,0()0|0(log)0,0()|( 22 ppppYXH )1|1(log)1,1()0|1(log)0,1( 22 pppp = 32lo g210lo g031lo g411lo g412222 = 213log432 比特 /符号 . Z 0 1 p 21 21 )0( )0,0()0|0( ZP ZXpZXp=1,)1( )1,0()1|0( ZP ZXpZXp=0 )0( )0,1()0|1( ZP ZXpZ
7、Xp=0,)1( )1,1()1|1( ZP ZXpZXp=1 则)1( )1|1(l o g)1,1()1( )0|1(l o g)0,1()0( )1|0(l o g)1,0()0( )0|0(l o g)0,0();( 2222 Xp ppXp ppXp ppXp ppZXI=0 比特 /符号 . 2）（ 20 分）若离散无记忆信源的概率分布为 4.03.02.01.0 dcbaU 分别构造二元，三元 Huffman 编码（要求码长方差最小，但不需求出）， Shannon编码， Fano 编码， Shannon-Fano-Elias 编码。 并求 中二元 Huffman 编码的编码效率。
8、（只列出式子即可） 1 0 21 第 4 页 共 5 页 解 :对信源按概率从大到小排序 , 1.02.03.04.0 abcdU,建立码树则有二元 Huffman 编码 : ,000a ,001b ,01c 1d 要进行三元 Huffman 编码 ,则需要添加一个空信源 ,成 为 01.02.03.04.0 eabcdU, 建立码树则有三元 Huffman 编码 : ,00a ,01b ,1c 2d Shannon 编码如下 : 信源 码长 累加概率 码字 d 2 0 00 c 2 0.4 01 b 3 0.7 101 a 4 0.9 1110 Fano 编码如下 : 信源 概率 第 1 次
9、分组 第 2 次分组 第 3 次分组 码字 d 0.4 0 0 c 0.3 1 0 10 b 0.1 1 0 110 a 0.1 1 111 Shannon-Fano-Elias 编码 信源 概率 )(xF )(xF )(xl 二元 )(xF 码字 a 0.1 0.1 0.05 5 0.00001 00001 b 0.2 0.3 0.2 4 0.000100 0001 c 0.3 0.6 0.45 3 0.011 011 d 0.4 1 0.8 3 0.110 110 二元 Huffman 编码的平均码长为 l = 4.013.022.031.03 =1.9 编码效率为9.1 )4.0,3.0
10、,2.0,1.0(2lo g )()( Hl UHRUH 第 5 页 共 5 页 3） （ 20 分） 若离散无记忆信道的信道转移矩阵为4341 2121，用两种方法求该信道容量。 方法一 : 方法二 : 令输入概率为 )1,( pp 时达到了信道容量 ,则代入 );( YXI 中 ,得到关 于 p 的函数 ,另其导数为 0,解得 p = 3429795.0 ,则当 )1,( pp = )6 5 7 0 2 0 5.0,3 4 2 9 7 9 5.0(时达到信道容量 ,为 0345.0 . 8 1 1 2 8 1.0 175.0l o g75.025.0l o g25.0 5.0l o g5.05.0l o g5.075.025.0 5.05.0 10 6 2 2 5 6 2.0 3 7 7 4 3 8.18 1 1 2 8 1.0 121 238 1 1 2 8 1.0 175.025.0 5.05.0110)628082.0,371918.0()2,2()1(),0( 10 CCww 0 3 4 5.00 3 4 5 3 6.1lo g )6 4 9 7 7 3.03 8 4 7 6 3.0lo g ()22lo g (10 C)6 5 7 0 2 0 5.0,3 4 2 9 7 9 5.0(75.025.0 5.05.0)1(),0()1(),0( wwqq
