哈夫曼编码的分析与实现.doc

《哈夫曼编码的分析与实现.doc》由会员分享，可在线阅读，更多相关《哈夫曼编码的分析与实现.doc（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、精品文档，仅供学习与交流，如有侵权请联系网站删除吉林建筑大学电气与计算机学院信息理论与编码课程设计报告设计题目： 哈夫曼编码的分析与实现 专业班级： 电子信息工程 131 学生姓名： 学 号： 指导教师： 设计时间： 2016.11.212016.12.2 教师评语：成绩 评阅教师 日期 【精品文档】第 13 页第1章 概述1.1设计的作用、目的通过完成具体编码算法的程序设计和调试工作，提高编程能力，深刻理解信源编码、信道编译码的基本思想和目的，掌握编码的基本原理与编码过程，增强逻辑思维能力，培养和提高自学能力以及综合运用所学理论知识去分析解决实际问题的能力，逐步熟悉开展科学实践的程序和方法。

2、主要目的是加深对理论知识的理解，掌握查阅有关资料的技能，提高实践技能，培养独立分析问题、解决问题及实际应用的能力。 通过课程设计各环节的实践，应达到如下要求： 1理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法； 2根据哈夫曼编码算法，考虑一个有多种可能符号（各种符号发生的概率不同）的信源，得到哈夫曼编码和码树； 3掌握哈夫曼编码的优缺点； 4通过完成具体编码算法的程序设计和调试工作，提高编程能力，深刻理解信源编码、信道编译码的基本思想和目的，掌握编码的基本原理与编码过程，增强逻辑思维能力，培养和提高自学能力以及综合运用所学理论知识去分析解决实际问题的能力，逐步熟悉开展科学实践的程序

3、和方法。1.2设计任务及要求1. 理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法；2. 掌握哈夫曼编码/费诺编码方法的基本步骤及优缺点；3. 深刻理解信道编码的基本思想与目的，理解线性分组码的基本原理与编码过程；4. 能够使用MATLAB或其他语言进行编程，编写的函数要有通用性。1.3设计内容一个有8个符号的信源X，各个符号出现的概率为：进行哈夫曼编码，并计算平均码长、编码效率、冗余度。第2章 哈夫曼编码的分析与实现2.1哈夫曼编码介绍及原理哈夫曼编码(Huffman Coding)是一种熵编码编码压缩方式，哈夫曼编码是可变字长编码(VLC)的一种。哈夫曼压缩是个无损的压缩算法，一

4、般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是不同符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。 哈夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。下面给出具体的Huffman编码算法。(1) 首先统计出每个符号出现的频率，如本次课程设计x1到x7的出现频率分别为0.39，0.17，0.12，0.1，0.07，0.06，0.05，0.04。(2) 从左到右把上述频率按从

5、小到大的顺序排列。(3) 每一次选出最小的两个值，作为二叉树的两个叶子节点，将和作为它们的根节点，这两个叶子节点不再参与比较，新的根节点参与比较。(4) 重复(3)，直到最后得到和为1的根节点。 (5) 将形成的二叉树的左节点标0，右节点标1。把从最上面的根节点到最下面的叶子节点途中遇到的0,1序列串起来，就得到了各个符号的编码。2.2 哈夫曼编码步骤（1）将信源消息符号按其出现的概率大小依次排列为（2）取两个概率最小的字母分别分配以0和1两个码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进制符号的字母重新排队 。（3）对重排后的两个概率小符号重复步骤（2）的过程。（4）不断继续上

6、述过程，直到最后两个符号配以0和1为止。（5）从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码子。2.4 哈夫曼编码特点 （1）哈弗曼的编码方法保证了概率大的符号应对于短码，概率小的应对于长码，充分利用了短码； （2）缩减信源的最后两个码子总是最后一位不同，从而保证了哈弗曼码是及时码。 （3）哈夫曼码没有错误保护功能，在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。但如果码串中有错误，哪怕仅是1位出现错误，不但这个码本身译错，更糟糕的是后面的数据串也会接着被译错，全乱了套，这种现象称为错误传播(error propagation)。计算机对这种错误也无能为力

7、，说不出错在哪里，更谈不上去纠正它； （4）哈夫曼编码只能用整数来表示单个符号而不能用小数，这很大程度上限制了压缩效果； （5）哈夫曼所有位都是合在一起的，如果改动其中一位就可以使其数据变得面目全非。2.5设计步骤设一个有8个符号的信源X，各个符号出现的概率为：则有两种哈夫曼编码方法，（0,1）编码或者（1,0）编码。表1 哈夫曼（0,1）编码过程框图信源符号 概率 编码过程码字 码长 X10.39 0.39 0.39 0.39 0.39 0.39 0.61 111 X20.17 0.17 0.17 0.19 0.25 0.36 0.390013 X30.12 0.12 0.13 0.17 0

8、.19 0.250113 X40.1 0.1 0.12 0.13 0.1700004 X50.07 0.09 0.1 0.1201004 X60.06 0.07 0.0901014 X70.05 0.06000105 X80.04000115该哈夫曼码的平均码长 为信源熵为编码效率冗余度 表2 哈夫曼（1,0）编码过程框图信源符号 概率 编码过程码字 码长 X10.39 0.39 0.39 0.39 0.39 0.39 0.61 101 X20.17 0.17 0.17 0.19 0.25 0.36 0.391103 X30.12 0.12 0.13 0.17 0.19 0.251003 X4

9、0.1 0.1 0.12 0.13 0.1711114 X50.07 0.09 0.1 0.1210114 X60.06 0.07 0.0910104 X70.05 0.06111015 X80.04111005信源熵为该哈夫曼码的平均码长 为编码效率冗余度 通过以上的两种不同的编码方式进行比较，我们发现其实以上两种编码的码虽然不同，但是其知识将原来的1换成了0，0换成了1，他的码长，编码效率，冗余度是没有变化的。需要注意的是，对于多进制哈夫曼编码，为了提高编码效率，就要使长码的符号数量尽量少，概率尽量小，所以信源符号数最好满足，其中r为进制数，n为缩减的次数。比如说如果要进行三进制编码，那么

10、最好信源具有7个符号，第一次合并后减少2个称为5个，第二次合并后又减少2个称为3个，这样给每一个赋予三进制符号就没有浪费的了。但是如果信源只有6个符号的话，为了减少最长码的数量，那么应该在第一次合并是添置为零的虚拟符号1个，事实上只合并2个概率最小的符号，后面每次合并3个，就可以是的最长的码的符号数量最少，也就是长码的概率最小，从而得到最高的编码效率。但是对于信源的某一个符号来说，有时候可能还会比定长码长。例如当信源有5个是，采用定长码方式可用3个二进制符号组成码字。而用变长码是有时候码字却长达4个二进制符号。所以编码简单化的代价就是要有大量的储存设备用来缓冲码字长度的差异，也就是码方差小的码

11、质量好的原因。设一秒钟送一个信源符号，输出码字却只有5个二进制符号，若希望平均每秒输出个二进制的信息率输出，才能从长久计算，输出和输入保持平衡。当储存量不够大的时候，可能有时取空，有时溢出。例如信源连续发出短码时，就会出现取空，就是说还没有存入就要输出。连续发出长码时，就会出现溢出，就是说存入太多，以致于存满了还未取出就要再次存入。所以应估计所需的存储器容量，才能使上述现象发生的概率小至可以容忍。当我们计算两个概率之和时，假设这两种的概率之和与上方概率有相同，我们应该把这个和概率放在其相同概率上方还是下方，我们就此进行讨论；设我们有一组概率为；0.4，0.2，0.2，0.1，0.1，则离散无记

12、忆信源当概率相同放在下方时，哈夫曼编码为： 表3 哈夫曼编码方法一 信源编码概率0.4 1.0 0.6编码过程码字码长X10.40.4 0.2 0.4 0.4 0.2 0.20.2002X20.2102X30.2112X40.10103X50.10113 当概率相同放在上方时，哈夫曼编码为： 表4 哈夫曼编码方法二信源编码概率编码过程码字码长X10.4 0.4 0.4 0.6 1.0 0.2 0.4 0.4 0.2 0.2 0.2 11X20.2012X30.20002X40.100104X50.100114 则上面两表给出的哈夫曼平均码长相等，即 编码效率也相同，即但是两种码的质量不完全相同

13、，可用码方差来表示，即 由此可见放在上面的哈夫曼编码比放在下面的哈夫曼编码得到的码方差要小许多，故应该放在上面。2.6哈弗曼树原理及过程哈夫曼树（Huffman tree），又名最优树，指给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。哈夫曼树是一种树形结构，用哈夫曼树的方法解编程题的算法就叫做哈夫曼算法。树并不是指植物，而是一种数据结构，因为其存放方式颇有点象一棵树有树叉因而称为

14、树。 最简哈夫曼树是由德国数学家冯。哈夫曼 发现的，此树的特点就是引出的路程最短。 哈弗曼最优二叉树步骤：1、初始化： 根据给定的n个权值构成n棵二叉树的集合，其中每棵二叉树中只有一个带权的根结点，左右子树均空。2、 找最小树：在F中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。3、删除与加入：在F中删除这两棵树，并将新的二叉树加入F中。4、判断：重复前两步（2和3），直到F中只含有一棵树为止。该树即为哈夫曼树。 图1 哈夫曼（0,1）编码树图形0 X 0 111100000111 01000100110111011100

15、111011111图2 哈夫曼（1,0）编码树图形 哈夫曼树也可以是k叉的，只是在构造k叉哈夫曼树时需要先进行一些调整。构造哈夫曼树的思想是每次选k个权重最小的元素来合成一个新的元素，该元素权重为k个元素权重之和。但是当k大于2时，按照这个步骤做下去可能到最后剩下的元素少于k个。解决这个问题的办法是假设已经有了一棵哈夫曼树(且为一棵满k叉树)，则可以计算出其叶节点数目为式子中的nk表示子节点数目为k的节点数目。于是对给定的n个权值构造k叉哈夫曼树时,可以先考虑增加一些权值为0的叶子节点，使得叶子节点总数为这种形式,然后再按照哈夫曼树的方法进行构造即可。第3章 哈夫曼编码C语言实现3.1 C语言

16、编程 3.1.1程序介绍本程序的编码和运行都是在VS2008中实现的， 整个程序虽然看似庞大，但编写过程清晰，采用模块化编写，各个问题逐个击破，也方便对程序的管理和运行。整个程序的编写分为五大部分： main 主函数， xiaoxi 子函数， add 子函数， coding子函数， ordination 子函数。五大部分紧密相连，环环相扣，共同实现程序的编码。 Main（）主函数主要负责其它函数的调用和最后结果的输出； Xiaoxi（）子函数主要负责输入需要的概率数据； Add（）子函数负责概率相加以便于排序； coding（）子函数负责具体编码工作。 从右往左逐列编码，在每一列从下往上逐个编

17、码，与上课时学习的方法稍有不同，其原理相同。ordination（）子函数主要负责各个概率间以及概率和的排序。该程序的优点有以下四个方面： 1、程序在刚运行的时候需要输入概率数据，程序会启动蜂鸣器，提示需要输入数据；在输入需要输入的数据个数之后，会再次启动蜂鸣器提醒需要输入概率数程序具有的提醒功能是本程序的一大特色。 2、程序在输入完需要的数据后，会自动排序，而不需要再去麻烦的排序。 3、程序在运行过程中会自动检错（错误报警）： a、当输入的概率大于 1 或小于 0 的时候，系统会自动提示错误； b、当输入的概率之和大于 1 时，系统会自动检错。 4、程序的编码过程清晰，编码过程中所有的概率都

18、会在显示窗口显示出来，更清楚易懂。 5、若两概率之和与另一概率相等，概率之和会自动排在后面。 a、理论上讲求和排序的时候是按照列的形式，但程序按照行的形式。当然了，再完美的计划也会有破绽，这个程序也不可避免地存在些小缺点： b、出错报警时增加蜂鸣器长时间工作； c、add 函数语句重复，流程图中已经进行了修改。程序使用说明：该程序是在 VS2008 环境下编写的，运行也需要在 VS2008 中运行，请确保你在装载有 VS2008 环境下运行。3.2程序流程图以及说明主程序N结束定义全局数组 a, b, c ,d 定义全局变量定义变量 n, x, y, K,开始输出编码过程中产生的新概率输出码字

19、输出平均码长、信源熵，编码效率，冗余度初始输出提示 获取y=xiaoxi()ordination(m,a);Y数组 a 一维，存放输入概率数组 b，二维存放编码过程概率 数组 c，三维，存放编码每个位置即时编码；数组 d，一维存放码长 i 为整型变量 计数编码次数 m 为整型n， x 为控制循环整型变量， y 为检错控制整型变量， K 为存放平均码长浮点型变量， H 为存放信源熵浮点型变量，三重循环初始化，使其所有值为 2显示“请输入消息个数”，响蜂鸣器调用获取概率函数，将返回值给 yY=0 存在错误，结束程序调用获取概率函数，将返回值给 y说明图3 主程序流程图3.3 C语言源程序#incl

20、ude#include#define w 10float aw,bww=0,fw=0;int i,cwww,dw=0,m;xiaoxi()int n;float P=0;printf(n 请分别输入消息概率(区间在0,1,概率之和应为):na);for(n=0;n=1|an=0)printf(出错，概率应在0,1 范围内n);return(0);break;P+=an;if(P!=1)printf(出错，概率和应为1n);return(0);elsereturn(1);ordination(int f,float *e)int g,j;float k;for(g=0;gf-1;g+)for(j

21、=g+1;jf;j+)if(eg=0;i-)t=0;for(k=m-2-i;k=0;k-)if(fi=bi+1k)&(t=0)t=1;for(r=0;ci+1kr!=2;r+)cim-i-2r=ci+1kr;cim-i-1r=ci+1kr;cim-i-2r=0;cim-i-1r=1;for(j=m-i-3;j=0;j-)for(k=m-2-i;k=0;k-)if(bij=bi+1k)for(r=0;ci+1kr!=2;r+)cijr=ci+1kr;add()int j;for(i=0;im;i+)b0i=ai;for(i=1;im;i+)bim-i-1=bi-1m-i-1+bi-1m-i;fi

22、-1=bim-i-1;for(j=0;jm-i-1;j+)bij=bi-1j;ordination(m-i,bi);main()int n,x,y;float K=0,H=0;for(n=0;nw;n+)for(x=0;xw;x+)for(y=0;yw;y+)cnxy=2;printf(n 请输入消息个数:na);scanf(%d,&m);printf(n);y=xiaoxi();if(y=1);ordination(m,a);add();coding();printf(n 编码过程如下:n);for(n=0;nm;n+)printf(n 第%d列:,n+1);for(x=0;xm;x+)if

23、(bnx=0)break;printf(t%5.4f,bnx);printf(n);printf(n);for(n=0;nm;n+)printf(概率为%5.4f 的符号编码后码字为:t,an);for(x=0;xm;x+)if(c0nx=2) break;printf(%d,c0nx);dn+;K+=an*dn;H+=(-an*log10l(an)/log10l(2);printf(t 其码长为: %dn,dn);printf(n 平均码长K=);printf(%3.2f,K);printf(n 信源熵=%3.2f,H);printf(n 编码效率=(H/K)=%3.2f%,H*100/K)

24、;printf(n 冗余度=（-）=%3.2fn,1-H/K);3.4程序步骤及运行本程序会对输入的概率自动检错，任何输入大于 1 或小于 0 的概率，或概率之和不等于 1 ，系统都会提示错误。 图4 仿真纠错情况及结果进行哈弗曼编码：第一步，输入你所需要的概率个数：如你需要输入概率 x1x8，请输入8，点回车键。第二步，输入你所需要的概率，程序会自动排序：如输入概率x1x8 ，分别点回车键确认，否则请按退格键。第三步，输入完成后，按下回车键，程序会出现结果。 图5 哈夫曼（1,0）编码运行结果显示各列重新排列的概率值 图6 哈夫曼（0,1）编码树运行结果显示各列重新排列的概率值 从运行结果可

25、知该结果与理论一致，并且可以看出哈夫曼编码的3个特点： (1) 哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码。 (2) 缩减信源的最后二个码字总是最后一位码元不同，前面各位码元相同（二元编码情况），从而保证了哈夫曼是即时码。 (3) 每次缩减信源的最长两个码字有相同的码长。 这三个特点保证了所得的哈夫曼码一定是最佳码。因此哈夫曼是一种应用广泛而有效的数据压缩技术。利用哈夫曼编码进行通信可以大大提高信道利用率，加快信息传输速度，降低传输成本。数据压缩的过程称为编码，解压的过程称为译码。进行信息传递时，发送端通过一个编码系统对待传数据（明文）预先编码，而接受端将传来的数据

26、（密文）进行译码。第4章 总结本次课程设计，让我对哈夫曼编码以及C语言有了更深的理解和操作能力。开始针对题目进行分析，将所涉及的知识点，及相关函数做了分析，大体能够把握整体的设计流程及思路。再通过查阅相关资料，使自己的知识也更加丰富了，明白了哈夫曼编码的原理以及仿真的实现。首先对给题目进行了计算，进行哈夫曼编码，求出平均码长，编码效率，开始时不是很顺利，以前学的很多书本上的东西记得不太清楚了，经过复习课本的内容，掌握原理后顺利求出结果。然后是利用C语言编写程序，由于我现在正在公司实习，接触到编程的东西比较多，所以对C语言编程还是比较熟悉的，所以我选择使用C语言来实现仿真，仔细研究后得到程序的算

27、法，还有我也参考了一部分网上的算法，但是在运行时还是出错了，之后又经过几次的修改，终于得出了结果，可是和自己计算的码却是相反的，而其它结果却是相同，让我疑惑了，我又仔细想了想了，原因应该出现在编码的时候，在编码过程中如果0和1赋值相反的话，就会出现这种情况，但是两种的码字应该都是正确的。过而能改，善莫大焉。在课程设计过程中，我们不断发现错误，不断改正，不断领悟，不断获取最终的检测调试环节，本身就是在践行过而能改，善莫大焉的知行观。这次课程设计终于顺利完成了，在设计中遇到了很多问题，最后在同事的指导下，终于迎刃而解。在今后社会的发展和学习实践过程中，一定要不懈努力，不能遇到问题就想到要退缩，一定

28、要不厌其烦的发现问题所在，然后一一进行解决，只有这样，才能成功的做成想做的事，才能在今后的道路上劈荆斩棘，而不是知难而退，那样永远不可能收获成功，收获喜悦，也永远不可能得到社会及他人对你的认可!最后通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，在设计过程中虽然遇到了一些问题，但经过一次又一次的思考，一遍又一遍的检查终于找出了原因所在，也暴露出了前期我在这方面的知识欠缺和经验不足。实践出真知，通过亲自动手制作，我掌握的知识不再是纸上谈兵，而且提高了自己的动手能力和独立思考的能力。在这过程

29、中我收获颇丰，在此期间也得到了同学的热心帮助，在这里忠心的感谢。这个课程设计对以后的工作也很有帮助，我会在以后的工作中多将理论与实际结合，从根本上解决问题，逐步提高自己的能力。参考文献1 曹雪虹，张宗橙.信息论与编码（第二版）.北京：清华大学出版社.20092 吕锋，王虹，刘皓春，苏扬.信息论与编码.北京：人民邮电出版社.20043 樊昌信，曹丽娜.通信原理（第六版）.北京：国防工业出版社.20064 王慧琴.数字图像处理.北京：北京邮电大学出版社.20075 孙丽华.信息论与纠错编码.电子工业出版社.20056 罗建军.MATLAB教程.电子工业出版社.20077 曹弋.MATLAB教程及实训.机械工业出版社.20088 苏金明，阮沈勇.MATLAB适用教程（第二版）.电子工业出版社.20089 王华，李有军.MATLAB电子仿真与应用教程（第二版）.国防工业出版社.2007