信息论-第5章无失真信源编码详解.ppt

*/100 概率匹配编码（信源符号概率已知） - 分组码： 定长码， 变长码 - 非分组码 通用编码（信源符号概率未知） §本章小结 信源编码的主要目的是提高信息传输的有效性，分为如下几类 */100 典型序列的概率 ，个数 当序列长度N足够大时，有 §本章小结 信源序列渐近均分特性 唯一可译码必须满足Kraft不等式 */100 §本章小结 无失真信源编码定理（仙农第一定理） 若对信源X的N次扩展源 进行编码，当N足够大时，总能找到唯一可译的r进编码，使得X的平均码长任意接近信源的熵 */100 为编码信道信息传输速率 为无噪信道的容量 §本章小结 关于信源编码定理的另一种描述 只要编码后，信息传输速率不大于无噪声信道的容量，就可实现无失真信源编码。 */100 编码序列的特性 R的最大限制： 编码符号独立且编码符号等概率 无失真信源编码所采取的主要措施 (1)概率匹配（Huffman编码等）使编码符号等概率 (2)解除相关性，使信源变成无记忆 */100 无失真信源编码的限制 典型序列个数估计 ，若 则 ，即每个序列都是典型序列。要实现无失真，必须有 。与无编码情况一样。 当信源的熵接近 时，无失真信源编码的意义不大；此时信源冗余度 ，没有压缩的余地。 */100 信源压缩编码的下限 不采用信源编码时每信源符号的码长为 而通过压缩编码后的平均码长会减小，但大于等于 压缩编码的目的就是尽量降低传送每个信源符号时所需的比特数，而信源的熵 为无失真压缩码长的下限。 */100 Thank you! * */100 定理5.3.6 仙农第一定理 证明思路： 若对任意信源X的N次扩展源 进行编码，当N足够大时，总能找到唯一可译的r进制编码，使得X的平均码长任意接近信源的熵 利用定理(5.3.5)的不等式，就可得到定理的结果 */100 相关定义 编码速率： 编码效率： 信息传输速率： 编码剩余度： */100 对所有唯一可译码都要满足 无需一定满足，但存在这种关系，通常希望越小越好 一些结论 平均码长的上、下界 时， ，此时： 各信源符号出现概率为 li为整数 每码元平均所带信息量为 ,码元符号独立且等概 */100 例 5.3.2 用例5.2.1的信源模型，i) 对单信源符号 进行二元编码，即 ，求平均码长和编码效率；ii）编成2次扩展码，信源序列与码序列的映射关系为： 求平均码长和编码效率。 解： 1) */100 信源序列的概率： 2) 且： 与例5.2.1相比，可以看出，为得到同样编码效率所用的编码符号数比定长码小得多。 因此容易达到高的编码效率，是变长码的显著优点。 */100 §5.4 哈夫曼编码 本节主要内容 一、二元哈夫曼编码 二、多元哈夫曼编码 三、马氏源的编码 */100 定理5.4.1 对于任意一个含q个符号的信源，存在最优的二进制码，其中有两个最长的码字有相同的长度且仅最后一个码位有别，即其中一个的最末尾是0，而另一个的最末尾是1（或者相反） 若一个唯一可译码的平均码长小于所有其它唯一可译码，则称该码为最优码(或紧致码)。 应注意：最优是唯一可译码之间的比较，因此它的平均码长未必达到编码定理的下界。 §5.4.1 二元哈夫曼编码 */100 证明思路： 首先证明对于最优码，概率小的符号对应长度长的码字。 证明最长的码字有两个长度相同，且只有最后一位不同。 一个最优码唯一可译 满足Kraft不等式 存在与其同样码长的异前置码 */100 二元最优异前置码的构造方法 设信源S为 ，对应的码字为 将概率最小的两个码符号 合并，从而产生新的信源S‘ 设 ，对应的码字为 。对新信源编码后，按下面的关系就可恢复原来信源的码字： */100 证明思路： 设 若 对信源 是最优的异前置码，则 对信源 也是最优的异前置码 对S，有 */100 一些结论 我们可以采用合并两个最小概率符号的方法，逐步地按这样的路线去编码： 最后将2字母信源分配0、1符号；然后可逐步反推到原信源S，从而得到信源的最优编码。这种编码称做二元Huff