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

院、系领导 审批并签名 B 卷 广州大学 2013-2014 学年第 2 学期考试卷 课程 信息学基础 考试形式（闭卷，考试） 学院 系 专业 班级 学号 姓名_ _ 题次 一 二 三 四 五 六 七 八 九 十 总分 评卷人 分数 15 12 73 100 评分 单项选择题（每分，总计分） B C D 3．下列（ D ）陈述是错误的。 A 即时码一定是非奇异码 B 唯一可译码的码长一定满足Kraft不等式 C 即时码一定是不等长的 D 若存在某个唯一可译码，则一定存在同样码长的即时码 4．下列数组中（ A ）不满足2个字母上的Kraft不等式。 A (1，1，1) B (2，2，2，2) C (1，2，2，1) D （3，3，3） 5．下列译码法则中（ D ）一定是错误概率最小的。 A 最大后验概率译码准则 B 最大似然译码准则 C 最小距离译码准则 D 最大先验概率译码准则 二、填空题（每分，总计分），则其信道容量为 1 。 2．若一个信道的输入熵为比特/符号，输出熵为比特/符号，比特/符号，则 3.2 ，疑义度为 0.2 . 3．平均互信息对信源概率分布是 上 凸函数，对信道的状态转移概率分布是 下 凸函数。 4．由Sardinas-Patterson算法 三、（分）的联合概率分布如下： 0 1 0 1 0 。分别求。 解：的分布率为 0 1 则比特/符号……………………………………………………………………..3分 的分布率为 0 1 则=0.811比特/符号. …………………………………………..……..6分 0 1 0 0 1 0 =,= =0,= ===0.688比特/符号. ……………..10分 1 2 3 =,=0 =0,=1 则=1比特/符号. …………………..15分 2）（22分）若离散无记忆信源的概率分布为 分别构造二元，四元Huffman编码（要求码长方差最小，但不需求出），Shannon编码，Fano编码，Shannon-Fano-Elias编码。 并求①中二元Huffman编码的编码效率。（只列出式子即可） 解:对信源按概率从大到小排序, ,建立码树则有二元Huffman编码: ，……………….4分 进行三元Huffman编码,不需要添加空信源,建立码树则有三元Huffman编码: ，，,………….8分 Shannon编码如下: 信源 码长 累加概率 码字 3 0 000 3 0.2 001 3 0.4 010 3 0.6 100 3 0.8 110 ……………………………………………………………………………….12分 Fano编码如下: 信源 概率 第1次分组 第2次分组 第3次分组 码字 0.2 0 0 00 0.2 1 01 0.2 1 0 10 0.2 1 0 110 0.2 1 111 ……………………………………………………………………………….16分 Shannon-Fano-Elias编码 信源 概率 二元 码字 0.2 0.25 0.125 3 0.001000 001 0.2 0.35 0.3 3 0.010010 010 0.2 0.5 0.425 3 0.011001 011 0.2 0.75 0.625 3 0.1010000 101 0.2 1.0 0.875 3 0.11000 110 …………………………………………………………………………………………….….20分 二元Huffman编码的平均码长为=3, …….21分