信息学基础2A卷答案.doc

1、 第 1 页 共 6 页 院、系领导 审批并签名 A 卷 广州大学 2013-2014 学年第 2 学期考试卷 课程 信息 学 基础 考试形式（ 闭 卷，考试） 学院 系 专业 班级 学号 姓名 _ _ 题次 一 二 三 四 五 六 七 八 九 十 总分 评卷人 分数 15 12 73 100 评分 一、 单项 选择题（每 题 3 分，总计 15 分） 1当底 为 e 时， 熵 的单位为（ C ）。 A 奈 特 B 哈 特 C 奈 特 /符号 D 哈 特 /符号 2下列 量 中， （ B ） 可正可负 。 A )(xI B );( yxI C );( YZXI D )|,( ZYXI 3 下列

2、 （ C ）陈述是 错误 的 。 A 即时码 一定是非奇异码 B 唯一可译码的 码长 一定 满足 Kraft 不 等式 C 即时码 一定是 不等长的 D 若存在某个唯一可译码，则一定存在同样码长的即时码 4下列数组中（ B ）不 满足 三 个字母上的 Kraft 不等式。 A (1， 1， 1) B (1， 1， 1， 1) C (1， 2， 2， 1) D （ 3， 3， 3） 5下列 译码法则中 （ A ） 一定 是 错误概率最小的 。 A 最大后验概率译码准则 B 最大似然译码准则 C 最小距离译码准则 D 最大先验概率译码准则 二、填空题（每 空 2 分，总计 12 分） 1 若某离散

3、 信道转移概 率矩阵为5.025.025.025.05.025.025.025.05.0，则其信道容量为 233log b/s。 2若 一个信道的输入熵为 4.3)( XH 比特 /符号 ， 输出熵为 2.3)( YH 比特 /符号 ，1);( YXI 比特 /符号 ，则 ),( YXH 5.6 比特 /符号 ， 疑义度为 2.4 比特 /符号 . 3 平均互信息 对信源概率分布 是 上 凸 函数 ， 对信道的状态转移概率分布 是 下 凸 函 数 。 4 由 Sardinas-Patterson 算法 可知 码字集合 0， 01， 10， 110的后缀集合为 0， 1， 10 。 第 2 页

4、共 6 页 三 、 计算题 （ 73 分） 1）（ 15 分）设随机变量 YX, 的联合概率分布如下： 1XYZ 。分别求 );(),|(),(),( ZXIYXHYHXH 。 解： X 的分布率为 X 0 1 p 21 21 则 1)( XH 比特 /符号 .3 分 Y 的分布率为 Y 0 1 p 41 43 则 3lo g432)(2YH=0.811 比特 /符号 . . .6 分 )0( )0,0()0|0( YP YXpYXp=1,)1( )1,0()1|0( YP YXpYXp=31 )0( )0,1()0|1( YP YXpYXp=0,)1( )1,1()1|1( YP YXpYX

5、p= 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 Y X 0 1 0 41 41 1 0 21 Z X 0 1 0 21 0 1 0 21 第 3 页 共 6 页 = 32lo g210lo g031lo g411lo g412222 = 213log432 =0.688 比特 /符号 . .10 分 Z 1 2 p 21 21 )0( )0,0()1|0( ZP ZXpZXp=1,)1( )1,0()2|0( ZP ZXpZXp=0 )0( )0,1()1|1( ZP ZXpZX

6、p=0,)1( )1,1()2|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=1 比特 /符号 . .15 分 2）（ 22 分）若离散无记忆信源的概率分布为 25.025.015.01.025.0 54321 aaaaaU 分别构造二元，三元 Huffman 编码（要求码长方差最小，但不需求出）， Shannon编码， Fano 编码， Shannon-Fano-Elias 编码。 并求 中

7、二元 Huffman 编码的编码效率。（只列出式子即可） 解 :对信源按概率从大到小排序 , 1.015.025.025.025.0 23415 aaaaaU,建立码树则有二元Huffman 编码 : 101a ,0102 a 0113a ， ,114a 005a .4 分 进行三元 Huffman 编码 ,不 需要添加空信源 ,建立码树则有三元 Huffman 编码 : 01a ，,102a 113a ， 124a , ,25a .8 分 Shannon 编码如下 : 信源 码长 累加概率 码字 5a 2 0 00 第 4 页 共 6 页 4a 2 0.25 01 1a 2 0.5 10 3

8、a 3 0.75 110 2a 4 0.9 1110 .12 分 Fano 编码如下 : 信源 概率 第 1次分组 第 2 次分组 第 3 次分组 码字 5a 0.25 0 0 00 4a 0.25 1 01 1a 0.25 1 0 10 3a 0.15 1 0 110 2a 0.1 1 111 .16 分 Shannon-Fano-Elias 编码 信源 概率 )(xF )(xF )(xl 二元 )(xF 码字 1a 0.25 0.25 0.125 3 0.001000 001 2a 0.1 0.35 0.3 5 0.010010 01001 3a 0.15 0.5 0.425 4 0.01

9、1001 0110 4a 0.25 0.75 0.625 3 0.1010000 101 5a 0.25 1.0 0.875 3 0.11000 110 . .20 分 二元 Huffman 编码的平均码长为l = 2.0215.0225.0325.0325.02 =2.7, .21 分 编码效率为7.2 )25.0,15.0,1.0,25.0,25.0(2lo g )()( Hl UHRUH .22 分 3） （ 14 分） 若二元信源 1,0 ， 41)0( p ， 43)1( p ，对 10011进行算术编码。 32 )43()41()10011( sP ,码长 6)(1log sPl

10、第 5 页 共 6 页 利用 )()()()( rFsPsFrsF , )0()1(,0)0( PFF , )10011( sF )0()1 0 0 1()1 0 0 1( PPsF )1 0 0 1 0()0()1 0 0()1 0( PPPsF = )10010()1000()0( PPP =0.2705078125=(0.010001). 编码为 010010. 4） （ 22 分）对输入流 10111001 分别用 LZ-77， LZ-78， LZW 和 KY 算法进行编码 ,并对 LZW编码进行解码。 解： LZ-77 编码： (0,0,1),(0,0,0),(2,1,1),(4,2

11、,0)(3,1, eof) ， . .4分 LZ-78 编码： 将输入流序列分段为 0， 1， 00， 10， 01， 001，则 有字典 段号 短语 1 1 2 10 3 11 4 10 5 01 码字为 (0,1), (0,0), (1,0),(1,1), (1,0),(2,1) . .9 分 LZW 编码： 初始字典 码字 1 2 词条 0 1 输出码 3 4 5 6 7 8 10 01 11 110 00 010 2 1 2 5 1 4 编码为初始字典和数列 2， 1， 2， 5， 1， 4， eof. . .13 分 解码：收到初始字典和数列 2， 1， 2， 5， 1， 4， eo

12、f.后重构字典和输出流如下： 1) 输入 2，输出 1，由于下一个输入为 1，则存 10 为新词条 3， 2) 输入 1，输出 0，由于下一个输入为 2，则存 01 为新词条 4， 3) 输入 2，输出 1，由于下一个输入为 5，则存 11 为新词条 5， 4) 输入 5，输出 11，由于下一个输入为 1，则存 110 为新词条 6， 第 6 页 共 6 页 5) 输入 1，输出 0，由于下一个输入为 4，则存 00 为新词条 7， 6) 输入 4，输出 01，由于下一个输入为 eof，则终止。 译码为 10111001。 . .17 分 KY 编码： 1） 读 入前 6 位，令 00D ， 11D ，则 0111011 DDDDDDS ，令 012 DD ，则21121 DDDDS ，动态字典为 10 2 D ； 2）读入第 7 位 0，则 021122 DDDDDS ，动态字典为 0,10 02 DD ； 3）读入第 8 位 1，则 1021123 DDDDDDS ，动态字典为 1,0,10 102 DDD .22 分