编码复习（仅供参考）一、填空题1、 在二进制编码中，当信源给定后，无失真信源压缩的极限值是（信源熵H(U)），有失真信源压缩的极限值是（信息率失真函数R(D)）。2、 对A、B、C、D四个符号进行二元等长编码，则每个符号至少要用（2）位符号？若对该信源进行3次扩展，则平均码长最小值为（6）。3、 保密学的两个分支是_密码编码学_和_密码分析学_。4、 现代密码学的核心密码体制是_双钥密码体制（或称公开密钥密码体制）_。5、 已知GF(2)中的一个码组的全部码字为000000, 001110, 010101, 011011, 100011, 101101, 110110，若将该码组用于检错，能检出_2_位错码，若将该码组用于纠错，能纠出_1_位错码。6、 信源U=0，1，2，接受变量为V=0，1，2，失真函数为，则失真矩阵为_。7、 在通信系统中，编码问题可分为_信源编码_、_信道编码_、 _保密编码_三类。8、 自信息量的含义包括：事件发生前表示事件发生的_不确定性_，事件发生后表示事件所能提供的_信息量_。9、 二元序列为：111 110 001 100 001 111，则对应的游程长度序列为：_53244_。10、密码学的五元组是明文空间、_密文空间 _、_加密算法_、_密钥空间_、解密算法。11、解除信源相关性的两种主要编码方式是_预测编码_、_变换编码_。二、 判断题1、满足kraft不等式的码是惟一可译码。（ ）2、信源符号等概率分布时，信息熵最大。（ ）3、采用Huffman编码编出的码不是惟一的，但这并不影响编码效率和数据压缩性能。（ ）4、惟一可译码一定是即时码。（ ）5、连续信源的绝对熵为无穷大。（ ）6、某一信源，不管它是否输出符号，只要这些符号具有某些概率特性，就有信息量。 （ ） 7、异前缀码不一定是即时码。 （ ）8、二进制编码中，要使信息率小于R(D)，平均失真一定会超过失真限度D。 （ ）9、对于离散信源，只有当失真矩阵中每行至少有一个零元素时，才有R(Dmin=0)=H(U)。 （ ）10、连续信源的差熵代表了连续信源输出的信息量。（ ）三、 简答题1、 缩短码与原码的纠检错能力是否相同？为什么？答：缩短码与原码的纠检错能力相同，因为缩短码删除的都是0码元，对纠检错性能没有影响。2、 随机编码时，选择码字所遵循的原则是什么？答：在rN个长度为N的码符号序列中选择M个作为代表消息的码字，其选择必须遵循的原则为：M个码字中，任何两个不同的码字间的汉明距离要尽量大，即码字之间越不相似越好。3、 简述离散无失真编码的实质？答；离散无失真信源编码的实质是一种统计匹配编码，是根据信源符号的不同概率分布来分配与之相对应的码字。对概率大的、经常出现的符号分配短的码字，对概率小的、不经常出现才符号分配长的码字。这样使得信源符号的平均码长最短，从而保证信息传输系统的有效性。4、 简述变换编码能够实现数据高压缩率的原因？答：变换编码就是将原来在空间域上描述的信号，通过一种数学变换变换到变换域中进行描述。这些变换系数之间的相关性明显下降，并且能量常常集中于低频或低序系数区域中，这样就能较容易地实现码率的压缩.四、 计算题1、 设信源符号集，求信源序列的段匹配码。解：将信源序列分成7段a0, a0a2, a3, a1, a1a0, a0a0, a3a2 C=7 段号所需码长：m=4 信源符号所需码长：段号1234567段号编码000001010011100101110信源符号a0a1a2a3符号编码00011011则信源对应的编码序列为000 000 010 010 010 110 110 110 001 001 010 000 110 111 02、 （设有一个离散无记忆信源如下：试求其Huffman编码和费诺编码，并求其编码效率。解：Huffman编码（比特/信源符号）（码符号/信源符号）费诺编码其信源熵和平均码长与Huffman码都相同，因此编码效率也为100%3、 设某信道的信道矩阵为若信道输入符号先验等概，试选择译码规则，使其平均错误译码概率达到最小值，并计算。解：因为信源符号先验等概，因此采用最大似然准则译码，可 得译码函数为 最小平均错误译码概率为6674、 设某线性分组码的生成矩阵为：(1) 说明该线性分组码的码长n，信息位k，和监督位r各是多少？ (2) 写出所有许用码字； (3) 写出该码的一致监督矩阵H；解：（1）由生成矩阵可知 得 n = 7k = 3 r = n k = 4（2）所有许用码字为 0000000 0011101 01001111 0111010 1001110 1010011 1101001 1110100 （3）相应监督矩阵为5、 设一个信源，若接收符号为y=0，1，2，规定失真函数为汉明失真度，求Dmax和Dmin及信源的R(D)函数，并求选择何种信道可达到该Dmax和Dmin的失真。解：由题意可知失真矩阵为最大允许失真度为 若取j = 1，则信道矩阵为 最小允许失真度为 其信道矩阵为（当D在定义域内时）6、设消息集合中共有5个元素，这5个元素分别被编为a, b, abbd， bac, bbc码，判断其是否为惟一可译码？为什么？ 解：按照Sardinas和Patterson设计的判断方法，可构造出下表所列符号集序列S0S1S2S3abbdcdbacbdabbdbcbacbbc可以看到当n5时，Sn已没有新的后缀，而Sn中不包含S0中，因此S0是惟一可译码。7、一个离散无记忆等概信源，失真矩阵为 求和，并求选择何种信道可达到该和的失真。解：最大允许失真度为 若取j = 1，则信道矩阵为 最小允许失真度为 其信道矩阵为 其中a+b= 1