无失真信源编码之霍夫曼编码

1、无失真信源编码无失真信源编码 游程游程编码编码信息理论与编码工程技术学院工程技术学院电气与电子信息系电气与电子信息系郭堃郭堃Page 2课程简介课程简介 寻找通信过程中的共同规律，以提高寻找通信过程中的共同规律，以提高通信的通信的有效性有效性、可可靠性靠性和和保密性保密性，使通信，使通信系统达到最优化。系统达到最优化。 本次课内容概要本次课内容概要Page 3无失真信源编码无失真信源编码霍夫曼编码霍夫曼编码1、编码过程及码树的构造2、霍夫曼编码效率3、多元霍夫曼编码霍夫曼编码优缺点霍夫曼编码优缺点 莫尔斯电码莫尔斯电码Page 4一、无失真信源编码一、无失真信源编码信源编码简介信源编码简介 信

2、源编码就是把信源符号变换到码符号的一种映射。 编码的目的就是将原始数据进行压缩，提高通信效率。 信源编码分为：无失真压缩编码和限失真压缩编码。Page 5数据压缩原理数据压缩原理 根据信源的统计特性，用短码来代替频繁出现的原始数据，从而达到压缩的目的。常见的信源编码方法常见的信源编码方法“霍夫曼编码”、“游程编码”、“字典编码”、“算术编码”等 Page 6Page 7编码器模型编码器模型编码器编码器信源符号集合：S1,S2,Sn代码集合：W1,W2,Wn码元集合：C1,C2,CmHello0000 0 0100 0100 1110, ,1实现的方法：实现的方法：概率匹配编码概率匹配编码 根据

3、信源符号的概率不同，编码的码长不同：概率大概率大的信源符号，所编的代码代码短短；概率小概率小的信源符号所编的代码长代码长，这样使平均码长最短。 Page 8霍夫曼编码简介霍夫曼编码简介 霍夫曼编码(Huffman Coding) ，属于概率匹配编码，是变长码(VLC)的一种。 Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造码字，使编码的平均长度最短。其编码效率在所有的无失真信源编码方法中是最高的，属于最佳编码。Page 9二、霍夫曼编码二、霍夫曼编码1 1、编码过程及码树的构造、编码过程及码树的构造（1）将q个信源符号按概率分布由大到小的顺序排列起来例：信源发出的

4、符号集合为：1 . 01 . 02 . 02 . 04 . 0)(54321isPsssssS二元二元HuffmanHuffman码的编码步骤码的编码步骤(2)将码符号0,1分配给两个最小概率的信 源符号，并将其概率值合并，成为一 个信源符号01(3)再重新排序，分配0,1, 重复步骤(2)，直至最后剩下两个信源01010110100000100011(4)从树根到叶子节点顺序写出树枝编码，即可的到相应编码Page 10编码编码符号符号 概率概率1.0 1.0 2.0 2.0 4.0 54321SSSSS00110010000011)/(2 . 28 . 06 . 04 . 04 . 0信信源

5、源符符号号码码元元 L965. 02 . 2122. 2)( LSH 霍夫曼编码的效率：霍夫曼编码的效率：Page 113 3、多元霍夫曼编码、多元霍夫曼编码r r元霍夫曼编码：元霍夫曼编码：(2) 每次合并r个最小概率成为新信源，减 少 个符号。(3) 满足式 才能充分利用短码信源缩减次数若不满足，则需增加 的0概率项(1) 将最小概率的r个符号分配码元)1(10 r，1 rrrq)1( 21, qqpp每次合并时信源符号减少的数量Page 12例例 四元四元HuffmanHuffman码码4, 2328, 2,8 rq而而时时 补二项补二项0007.002.005.008.008.010.010.018.015.015.020.018.022.020.040.022.010987654321SSSSSSSSSS013211230023rrq)1(6S4S1S2001113S2S02338S7S5S033032031030020100321Page 13霍夫曼编码效率高, , 常用于文件传真, 语音处理和图象处理的数据压缩。优点:三、霍夫曼编码优缺点三、霍夫曼编码优缺点1 Page 14Page 15（1）霍夫曼编码没有错误纠正能力，一般只能适合于低噪声优