无失真信源编码之霍夫曼编码范例.ppt

无失真信源编码 ——游程编码 信息理论与编码 工程技术学院 电气与电子信息系 郭堃 Page ? * 课程简介 寻找通信过程中的共同规律，以提高通信的有效性、可靠性和必威体育官网网址性，使通信系统达到最优化。 本次课内容概要 Page ? * 无失真信源编码 霍夫曼编码 1、编码过程及码树的构造 2、霍夫曼编码效率 3、多元霍夫曼编码 霍夫曼编码优缺点 莫尔斯电码 Page ? * 一、无失真信源编码 信源编码简介 信源编码就是把信源符号变换到码符号的一种映射。 编码的目的就是将原始数据进行压缩，提高通信效率。 信源编码分为：无失真压缩编码和限失真压缩编码。 Page ? * 数据压缩原理 根据信源的统计特性，用短码来代替频繁出现的原始数据，从而达到压缩的目的。 常见的信源编码方法 “霍夫曼编码”、“游程编码”、“字典编码”、“算术编码”等 Page ? * Page ? * 编码器模型 编码器 信源符号集合： {S1,S2,…Sn} 代码集合： {W1,W2,…Wn} 码元集合： {C1,C2,…Cm} Hello 0000 0 0100 0100 111 0,1 实现的方法：概率匹配编码 根据信源符号的概率不同，编码的码长不同：概率大的信源符号，所编的代码短；概率小的信源符号所编的代码长，这样使平均码长最短。 Page ? * 霍夫曼编码简介 霍夫曼编码(Huffman Coding) ，属于概率匹配编码，是变长码(VLC)的一种。 Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造码字，使编码的平均长度最短。其编码效率在所有的无失真信源编码方法中是最高的，属于最佳编码。 Page ? * 二、霍夫曼编码 1、编码过程及码树的构造 （1）将q个信源符号按概率分布由大到小的顺序排列起来 例：信源发出的符号集合为： 二元Huffman码的编码步骤 (2)将码符号0,1分配给两个最小概率的信 源符号，并将其概率值合并，成为一 个信源符号 0 1 (3)再重新排序，分配0,1, 重复步骤(2)，直至最后剩下两个信源 0 1 0 1 0 1 1 01 000 0010 0011 (4)从树根到叶子节点顺序写出树枝编码，即可的到相应编码 Page ? * 编码 符号 概率 霍夫曼编码的效率： Page ? * 3、多元霍夫曼编码 r元霍夫曼编码： (2) 每次合并r个最小概率成为新信源，减 少 个符号。 (3) 满足式 才能充分利用短码 信源缩减次数 若不满足，则需增加 的0概率项 (1) 将最小概率的r个符号分配码元 每次合并时信源符号减少的数量 Page ? * 例 四元Huffman码 补二项 Page ? * 霍夫曼编码效率高, , 常用于文 件传真, 语音处理和图象处理的数据压缩。 优点: 三、霍夫曼编码优缺点 Page ? * Page ? * （1）霍夫曼编码没有错误纠正能力，一般只能适合于低噪声优质信道中传输。 （2）霍夫曼编码硬件实现较复杂，且需要根据实际通信系统特性设计合适的缓冲寄存器。 （3）霍夫曼编码是概率匹配编码，需预先知道信源的概率分布。 不足之处: 谢谢各位！