信息学基础2A卷答案

第1页共6页院、系领导审批并签名A卷广州大学20132014学年第2学期考试卷课程信息学基础考试形式（闭卷，考试）学院系专业班级学号姓名_题次一二三四五六七八九十总分评卷人分数151273100评分一、单项选择题（每题3分，总计15分）1当底为E时，熵的单位为（C）。A奈特B哈特C奈特/符号D哈特/符号2下列量中，（B）可正可负。ABCDXIYXIYZXI|,ZYI3下列（C）陈述是错误的。A即时码一定是非奇异码B唯一可译码的码长一定满足KRAFT不等式C即时码一定是不等长的D若存在某个唯一可译码，则一定存在同样码长的即时码4下列数组中（B）不满足三个字母上的KRAFT不等式。A1，1，1B1，1，1，1C1，2，2，1D（3，3，3）5下列译码法则中（A）一定是错误概率最小的。A最大后验概率译码准则B最大似然译码准则C最小距离译码准则D最大先验概率译码准则二、填空题（每空2分，总计12分）1若某离散信道转移概率矩阵为，则其信道容量为B/S。502023LOG2若一个信道的输入熵为比特/符号，输出熵为比特/符号，43XHYH比特/符号，则56比特/符号，疑义度为24比特/符号1YXI,Y3平均互信息对信源概率分布是上凸函数，对信道的状态转移概率分布是下凸函数。第2页共6页4由SARDINASPATTERSON算法可知码字集合0，01，10，110的后缀集合为0，1，10。三、计算题（73分）1）（15分）设随机变量的联合概率分布如下YX,。分别求。1XYZ,|,ZXIYHX解的分布率为X01P2则比特/符号3分1XH的分布率为YY01P43则0811比特/符号6分3LOG422YH,0,0|YPXPYXP11,01|0YPXPXP30104102ZX0102010第3页共6页0,0,10|1YPXPYXP1,1|YPXPXP32|0LOG,|LOG,|22H1|LOG,0|LOG,22P0688比特/符号334L2L4210分Z12P,00,1|0ZPXZXP11,02|0ZPXPZX0,1,|P,|P则1|LOG1,0|LOG,10|LOG1,0|LOG0,2222XPXPXPXPZXI1比特/符号15分2）（22分）若离散无记忆信源的概率分布为2501025431AAU分别构造二元，三元HUFFMAN编码（要求码长方差最小，但不需求出），SHANNON编码，FANO编码，SHANNONFANOELIAS编码。并求中二元HUFFMAN编码的编码效率。（只列出式子即可）解对信源按概率从大到小排序,建立码树则有二元1052052341AAUHUFFMAN编码，4分10A,23,4进行三元HUFFMAN编码,不需要添加空信源,建立码树则有三元HUFFMAN编码，01A，,8分,102A34,5SHANNON编码如下第4页共6页信源码长累加概率码字5A200042025011205103A30751102409111012分FANO编码如下信源概率第1次分组第2次分组第3次分组码字5A0250004025010110250103A015011020111111116分SHANNONFANOELIAS编码信源概率XFXL二元XF码字1A02502501253000100000120103503500100100100130150504254001100101104A02507506253010100001015025100875301100011020分二元HUFFMAN编码的平均码长为27,L20152052021分编码效率为22分72,1,52LOGHUR第5页共6页3）（14分）若二元信源，对10011进行算术编码。1,04P31,码长32410SP6LOGSP利用,RFSPRF01,010S11010PSF027050781250010001编码为010010P4）（22分）对输入流10111001分别用LZ77，LZ78，LZW和KY算法进行编码,并对LZW编码进行解码。解LZ77编码0,0,1,0,0,0,2,1,1,4,2,03,1,EOF，4分LZ78编码将输入流序列分段为0，1，00，10，01，001，则有字典段号短语11210311410501码字为0,1,0,0,1,0,1,1,1,0,2,19分LZW编码初始字典码字12词条01输出码34567810011111000010212514编码为初始字典和数列2，1，2，5，1，4，EOF13分解码收到初始字典和数列2，1，2，5，1，4，EOF后重构字典和输出流如下1输入2，输出1，由于下一个输入为1，则存10为新词条3，第6页共6页2输入1，输出0，由于下一个输入为2，则存01为新词条4，3输入2，输出1，由于下一个输入为5，则存11为新词条5，4输入5，输出11，由于下一个输入为1，则存110为新词条6，5输入1，输出0，由于下一个输入为4，则存00为新词条7，6输入4，输出01，由于下一个输入为EOF，则终止。