《哈夫曼编码的分析与实现》由会员分享，可在线阅读，更多相关《哈夫曼编码的分析与实现（21页珍藏版）》请在金锄头文库上搜索。
1、吉林建筑大学电气与计算机学院信息理论与编码课程设计报告设计题目专业班级学生姓名哈夫曼编码的分析与实现电子信息工程131学号指导教师2016.11.212016.12.2设计时间第 1 章 概述1.1 设计的作用、目的通过完成具体编码算法的程序设计和调试工作，提高编程能力，深刻理解 信源编码、信道编译码的基本思想和目的，掌握编码的基本原理与编码过程，增 强逻辑思维能力，培养和提高自学能力以及综合运用所学理论知识去分析解决实 际问题的能力，逐步熟悉开展科学实践的程序和方法。主要目的是加深对理论知 识的理解，掌握查阅有关资料的技能，提高实践技能，培养独立分析问题、解决 问题及实际应用的能力。通过课程
2、设计各环节的实践，应达到如下要求： 1理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法； 2根据哈夫曼编码算法，考虑一个有多种可能符号（各种符号发生的概率 不同）的信源，得到哈夫曼编码和码树；3掌握哈夫曼编码的优缺点；4通过完成具体编码算法的程序设计和调试工作，提高编程能力，深刻理 解信源编码、信道编译码的基本思想和目的，掌握编码的基本原理与编码过程， 增强逻辑思维能力，培养和提高自学能力以及综合运用所学理论知识去分析解决 实际问题的能力，逐步熟悉开展科学实践的程序和方法。1.2 设计任务及要求1. 理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法；2. 掌握哈夫曼编码/费
3、诺编码方法的基本步骤及优缺点；3. 深刻理解信道编码的基本思想与目的，理解线性分组码的基本原理与编 码过程；4. 能够使用 MATLAB 或其他语言进行编程，编写的函数要有通用性。1.3 设计内容一个有8个符号的信源X,各个符号出现的概率为：XP(X)x80.04x xx x x x x1 2 3 4 5 6 70.39 0.17 0.12 0.1 0.07 0.06 0.05进行哈夫曼编码,并计算平均码长、编码效率、冗余度。第 2 章 哈夫曼编码的分析与实现2.1 哈夫曼编码介绍及原理哈夫曼编码(Huffman Coding)是一种燔编码编码压缩方式，哈夫曼编码是可 变字长编码(VLC)的一
4、种。哈夫曼压缩是个无损的压缩算法，一般用来压缩文本 和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是不同符号(例如， 文本文件中的字符)用一个特定长度的位序列替代。因此，在文件中出现频率高 的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。哈夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而 对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于 实际信息的符号长度。下面给出具体的 Huffman 编码算法。(1) 首先统计出每个符号出现的频率，如本次课程设计X到x7的出现频率 分别为 0.39， 0.17， 0.12， 0.1， 0.07，
5、0.06， 0.05， 0.04。(2) 从左到右把上述频率按从小到大的顺序排列。(3) 每一次选出最小的两个值，作为二叉树的两个叶子节点，将和作为它们 的根节点，这两个叶子节点不再参与比较，新的根节点参与比较。(4) 重复(3)，直到最后得到和为 1 的根节点。(5) 将形成的二叉树的左节点标 0，右节点标 1。把从最上面的根节点到最 下面的叶子节点途中遇到的 0,1 序列串起来，就得到了各个符号的编码。2.2 哈夫曼编码步骤(1) 将信源消息符号按其出现的概率大小依次排列为p pp12n(2) 取两个概率最小的字母分别分配以 0 和 1 两个码元，并将这两个概率 相加作为一个新字母的概率，
6、与未分配的二进制符号的字母重新排队 。(3) 对重排后的两个概率小符号重复步骤(2)的过程。(4) 不断继续上述过程，直到最后两个符号配以 0 和1 为止。(5) 从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即 相应的码子。2.4 哈夫曼编码特点（1）哈弗曼的编码方法保证了概率大的符号应对于短码，概率小的应对于长 码，充分利用了短码；（2）缩减信源的最后两个码子总是最后一位不同，从而保证了哈弗曼码是及 时码。（3）哈夫曼码没有错误保护功能，在译码时，如果码串中没有错误，那么就 能一个接一个地正确译出代码。但如果码串中有错误，哪怕仅是 1 位出现错误， 不但这个码本身译错，更糟糕的
7、是后面的数据串也会接着被译错，全乱了套，这 种现象称为错误传播（error propagation）。计算机对这种错误也无能为力，说不出 错在哪里，更谈不上去纠正它；（4）哈夫曼编码只能用整数来表示单个符号而不能用小数，这很大程度上限 制了压缩效果；（5）哈夫曼所有位都是合在一起的，如果改动其中一位就可以使其数据变得 面目全非。2.5 设计步骤x x x x x x x12345670.39 0.17 0.12 0.1 0.07 0.06 0.05x80.04设一个有8个符号的信源X,各个符号出现的概率为:L p（ x）则有两种哈夫曼编码方法，（0,1）编码或者（1,0）编码。表 1 哈夫曼（
8、0,1 ）编码过程框图信源符 号x1X10.39X20.17X30.12X40.1X50.07X60.06X70.05X80.040.390.39编码过程0.390.390.390.61、0.360.250.39 J码字Wi码长K111001301130000401004010140001050001151该哈夫曼码的平均码长K为8K = p(x )K = 0.39*l+0.17*3+0.12*3+04+0.07*4+0.06*4+0.05*5+0.04*5 iii=1=2.63 (码元/符号)信源熵H (x)为H(x)= 一工p(x )log p(x )=- (0.39log0.39+0.1
9、7log0.17+0.12log0.12+0.1log0.1 iii=1+0.07log0.07+0.06log0.06+0.05log0.05+0.04log0.04)=2.58(bit / 符号)编码效率HX)=竺0.98K 2.63冗余度Y = 1 -n = 1-0.977=0.02表 2 哈夫曼(1,0 )编码过程框图信源符概率号xiP (x.)1X10.39X20.17X30.12X40.1X50.07X60.06X70.05X80.04编码过程0.390.390.390.390.170.170.190.25A0.120.1317A.19 0.1f.12怡.13/0.17 J0.09
10、a/0.1 / 0.1200.01 0.090/ 0.06 J000.36100.390.610.25i/0.39 丿。码字Wi码长KI01110310031111410114101041110151110051信源熵H (x)为H(x) =- p(x)log p(x)=-(0.39log0.39+0.17log0.17+0.12log0.12+0.1log0.1ii i=1+0.07log0.07+0.06log0.06+0.05log0.05+0.04log0.04)=2.58(bit / 符号)该哈夫曼码的平均码长K为8K = p(x )K 二 0.39*1+0.17*3+0.12*3+
11、04+0.07*4+0.06*4+0.05*5+0.04*5iii=1=2.63 (码元/符号)编码效率冗余度H(X )2.58耳 =K 2.63沁 0.98Y = 1 -n = 1-0.977=0.02通过以上的两种不同的编码方式进行比较，我们发现其实以上两种编码的码 虽然不同，但是其知识将原来的 1 换成了0，0 换成了 1，他的码长，编码效率， 冗余度是没有变化的。需要注意的是，对于多进制哈夫曼编码，为了提高编码效率，就要使长码的 符号数量尽量少，概率尽量小，所以信源符号数最好满足m = (r- 1)n + r，其中 r 为进制数， n 为缩减的次数。比如说如果要进行三进制编码，那么最好
12、信源具 有7个符号，第一次合并后减少2个称为 5个，第二次合并后又减少2个称为 3 个，这样给每一个赋予三进制符号就没有浪费的了。但是如果信源只有 6 个符号 的话，为了减少最长码的数量，那么应该在第一次合并是添置为零的虚拟符号1 个，事实上只合并 2 个概率最小的符号，后面每次合并 3个，就可以是的最长的 码的符号数量最少，也就是长码的概率最小，从而得到最高的编码效率。但是对 于信源的某一个符号来说，有时候可能还会比定长码长。例如当信源有 5 个是， 采用定长码方式可用 3 个二进制符号组成码字。而用变长码是有时候码字却长达 4 个二进制符号。所以编码简单化的代价就是要有大量的储存设备用来缓
13、冲码字 长度的差异，也就是码方差小的码质量好的原因。设一秒钟送一个信源符号，输 出码字却只有5个二进制符号，若希望平均每秒输出k = 2.61个二进制的信息率 输出，才能从长久计算，输出和输入保持平衡。当储存量不够大的时候，可能有 时取空，有时溢出。例如信源连续发出短码时，就会出现取空，就是说还没有存 入就要输出。连续发出长码时，就会出现溢出，就是说存入太多，以致于存满了 还未取出就要再次存入。所以应估计所需的存储器容量，才能使上述现象发生的 概率小至可以容忍。当我们计算两个概率之和时，假设这两种的概率之和与上方概率有相同，我 们应该把这个和概率放在其相同概率上方还是下方，我们就此进行讨论； 设我们有一组概率为；0.4， 0.2， 0.2， 0.1， 0.1，则离散无记忆信源XP(X)xxxx12340.10.4 0.2 0.2 0.1当概率相同放在下方时，哈夫曼编码为：表3哈夫曼编码方法信源编码概 率编码过程码字码 长X10.40.4040.6 10L。002X20.20.2/ 0.4100.4 102X30.2卜20.2 :112X40.1J 02 10103X50.1L /丿10113当概率相同放在上方时，哈夫曼编码为：表4哈夫曼编码方法二信源编码概 率编码过程码字码 长X10.40.40.40.6$1.00.2刁 0.4 y0.4 j0.2。0.2 J1.0.2/
