《信息论与编码理论1B卷答案》由会员分享，可在线阅读，更多相关《信息论与编码理论1B卷答案（6页珍藏版）》请在金锄头文库上搜索。
1、 第 1 页 共 6 页广州大学广州大学 2015-2016 学年第学年第 1 学期考试学期考试 B 卷答案卷答案课程 信息论与编码理论 1 考试形式（闭卷，考试）学院 系 专业 班级 学号 姓名_ _题次一二三四五六七八九十总分评卷人分数151471 100评分一、一、单项选择题（每题单项选择题（每题 3 分，总计分，总计 15 分）分） 1当底为 2 时，自信息的单位为（ B ） 。 A 奈特 B 比特 C 奈特/符号 D 比特/符号2下列量当交换位置时（ C ）没有对称性。YX,A B C D );(YXI),(YXH)|(YXH)|,(ZYXI3 下列性质不是离散集的熵性质的是 （ C
2、 ） A 对称性 B 非负性 C 不确定性 D 可加性 4下列数组中（ A ）不满足两个字母上的 Kraft 不等式。 A (1，1，1) B (2,2) C (1,2,3) D （3，3，3） 5异字头码中平均码长最短的称为最佳码，下列编码方法不能得到最佳码的是（D ） A Shannon-Fano 编码 B Huffman 编码 C 算术编码 D LZ 编码二、填空题（每空二、填空题（每空 2 分，总计分，总计 14 分）分）1若二元离散无记忆中，则当给出比特的信源序列，其中25. 0)0(p75. 0) 1 (p100有个 ，则其自信息为比特，整个序列的熵为比特/符号.513log520
3、02)3log432(10022若一个信道的输入熵为比特/符号，输出熵为比特/符号，1 . 2)(XH2)(YH比特/符号，则2.9 比特/符号，散布度为 0.8 比特/符号。2 . 1);(YXI),(YXH3平均互信息对信源概率分布是 上 凸函数，对信道的状态转移概率分布是 下 凸函数。4在二元 LZ 编码中，若信源有个，某段信源序列共有个字典，则码长KM 。 KM22loglog三、计算题三、计算题（71 分）第 2 页 共 6 页1） （15 分）设随机变量的联合概率分布如下：的联合概率分布如下：YX,。分别求。XYZ );(),|(),(),(ZXIYXHYHXH解: 的分布率为XX
4、01p21 21则比特/符号. .3 分1)(XH的分布率为YY01p41 43则比特/符号. .6 分3log432)(2YH= ,=)0()0, 0()0|0(YPYXpYXp1) 1() 1, 0() 1|0(YPYXpYXp31=0,= )0()0, 1()0|1(YPYXpYXp) 1() 1, 1() 1|1(YPYXpYXp32) 1|0(log) 1 , 0()0|0(log)0 , 0()|(22ppppYXH) 1|1 (log) 1 , 1 ()0|1 (log)0 , 1 (22pppp=比特/符号. .10 分32log210log031log411log412222
5、213log432Z01Y X010 41 4110 21Z X010 21010 21第 3 页 共 6 页p21 21=1,=0)0()0, 0()0|0(ZPZXpZXp) 1() 1, 0() 1|0(ZPZXpZXp=0,=1)0()0, 1()0|1(ZPZXpZXp) 1() 1, 1() 1|1(ZPZXpZXp则) 1() 1|1 (log) 1 , 1 () 1()0|1 (log)0 , 1 ()0() 1|0(log) 1 , 0()0()0|0(log)0 , 0();(2222XpppXpppXpppXpppZXI=0 比特/符号. . .15 分2） （22 分）
6、若离散无记忆信源的概率分布为 4 . 03 . 02 . 01 . 0dcbaU 分别构造二元，三元 Huffman 编码（要求码长方差最小，但不需求出） ，Shannon编码，Fano 编码，Shannon-Fano-Elias 编码。 并求中二元 Huffman 编码的编码效率。 （只列出式子即可）解:对信源按概率从大到小排序, ,建立码树则有二元 Huffman 编 1 . 02 . 03 . 04 . 0abcdU码: .4 分,000a,001b,01c1d要进行三元 Huffman 编码,则需要添加一个空信源,成为, 01 . 02 . 03 . 04 . 0eabcdU建立码树则
7、有三元 Huffman 编码: .8 分,00a,01b, 1c2dShannon 编码如下:信源码长累加概率码字d2000c20.401b30.7101a40.91110第 4 页 共 6 页.12 分 Fano 编码如下:信源概率第 1 次分组第 2 次分组第 3 次分组码字d0.400c0.3010b0.10110a0.1111111.16 分 Shannon-Fano-Elias 编码信源概率)(xF)(xF)(xl二元)(xF码字a0.10.10.0550.0000100001b0.20.30.240.0001000001c0.30.60.4530.011011d0.410.830.
8、110110.20 分 二元 Huffman 编码的平均码长为 =1.9.21 分l4 . 013 . 022 . 031 . 03 编码效率为.22 分 9 . 1 )4 . 0 , 3 . 0 , 2 . 0 , 1 . 0(2log)()(HlUH RUH3） （12 分）若二元信源，对 10011 进行算术编码。1 , 041)0(p43) 1 (p解：,码长.4 分32)43()41()10011(sP6 )(1log sPl利用,.6 分)()()()(rFsPsFr sF)0() 1 (, 0)0(PFF.8 分)10011( sF)0()1001()1001(PPsF)1001
9、0()0()100()100(PPPsF)10010()1000() 1(PPsF第 5 页 共 6 页=.10 分)10010()1000()0(PPP=0.541015625=(0.100010). 编码为 100010. .12 分 4） （22 分）对输入流 1101110 分别用 LZ-77，LZ-78，LZW 和 KY 算法进行编码,并对 LZW 编码进行解码。 解：LZ-77 编码：(0,0,1),(1,1,0),(2,1,0),(3,2,1),(4,1, eof). .4 分LZ-78 编码：将输入流序列分段为 1，10，11，10，则有字典段号短语11210311410码字为
10、(0,1),(1,0),(1,1), (1,0) .9 分LZW 编码：初始字典 码字12词条01新词条输出码3456111100111110NYYYYN22134,eof编码为初始字典和数列 2，2，1，3，4,eof. .13 分解码：收到初始字典和数列 2，2，1，3，4,eof 后重构字典和输出流如下：1)输入 2，输出 1，由于下一个输入为 2，则存 11 为新词条 3，2)输入 2，输出 1，由于下一个输入为 1，则存 10 为新词条 4，3)输入 1，输出 0，由于下一个输入为 3，则存 01 为新词条 5，第 6 页 共 6 页4)输入 3，输出 11，由于下一个输入为 4，则存 111 为新词条 6，5)输入 4，输出 10，由于下一个输入为 eof，则终止。译码为 1101110。 .17 分KY 编码：1）由于前 4 位没有重复段，首次读入第五位 1，令，则00D11D，令，则，动态字典为；110111DDDDDS 112DDD 2021DDDS 11, 020DD2）读入第六位 1，则，动态字典为；12022DDDDS 11, 1, 0210DDD3）读入第七位 0，则，动态字典为.22 分012022DDDDDS 11, 1, 0210DDD
