哈夫曼编码的分析与实现

吉林建筑大学电气与计算机学院信息理论与编码课程设计报告设计题目:哈夫曼编码的分析与实现专业班级:电子信息工程设计题目:哈夫曼编码的分析与实现专业班级:电子信息工程131学生姓名:号：指导教师:设计时间:2016.11.21—2016.12.2第1章概述1.1设计的作用、目的通过完成具体编码算法的程序设计和调试工作，提高编程能力，深刻理解信源编码、信道编译码的基本思想和目的，掌握编码的基本原理与编码过程，增强逻辑思维能力，培养和提高自学能力以及综合运用所学理论知识去分析解决实际问题的能力，逐步熟悉开展科学实践的程序和方法。主要目的是加深对理论知识的理解，掌握查阅有关资料的技能，提高实践技能，培养独立分析问题、解决问题及实际应用的能力。通过课程设计各环节的实践，应达到如下要求：理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法；根据哈夫曼编码算法，考虑一个有多种可能符号(各种符号发生的概率不同)的信源，得到哈夫曼编码和码树；掌握哈夫曼编码的优缺点；通过完成具体编码算法的程序设计和调试工作，提高编程能力，深刻理解信源编码、信道编译码的基本思想和目的，掌握编码的基本原理与编码过程，增强逻辑思维能力，培养和提高自学能力以及综合运用所学理论知识去分析解决实际问题的能力，逐步熟悉开展科学实践的程序和方法。1.2设计任务及要求理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法；掌握哈夫曼编码/费诺编码方法的基本步骤及优缺点；深刻理解信道编码的基本思想与目的，理解线性分组码的基本原理与编码过程；能够使用MATLAB或其他语言进行编程，编写的函数要有通用性。1.3设计内容一个有8个符号的信源X，各个符号出现的概率为：TOC\o"1-5"\h\zX］「xxxxxxXX=<12345678P(X)」［0.390.170.120.10.070.060.050.04进行哈夫曼编码，并计算平均码长、编码效率、冗余度。第2章哈夫曼编码的分析与实现2.1哈夫曼编码介绍及原理哈夫曼编码(HuffmanCoding)是一种熵编码编码压缩方式，哈夫曼编码是可变字长编码(VLC)的一种。哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是不同符号(例如，文本文件中的字符)用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。哈夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。下面给出具体的Huffman编码算法。首先统计出每个符号出现的频率，如本次课程设计x1到x7的出现频率分别为0.39，0.17，0.12，0.1，0.07，0.06，0.05，0.04。从左到右把上述频率按从小到大的顺序排列。每一次选出最小的两个值，作为二叉树的两个叶子节点，将和作为它们的根节点，这两个叶子节点不再参与比较，新的根节点参与比较。重复(3)，直到最后得到和为1的根节点。将形成的二叉树的左节点标0，右节点标1。把从最上面的根节点到最下面的叶子节点途中遇到的0,1序列串起来，就得到了各个符号的编码。2.2哈夫曼编码步骤将信源消息符号按其出现的概率大小依次排列为p>p>->p取两个概率最小的字母分别分配以0和1两个码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进制符号的字母重新排队。对重排后的两个概率小符号重复步骤(2)的过程。不断继续上述过程，直到最后两个符号配以0和1为止。从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码子。

2.4哈夫曼编码特点（1）哈弗曼的编码方法保证了概率大的符号应对于短码，概率小的应对于长码，充分利用了短码；（2）缩减信源的最后两个码子总是最后一位不同，从而保证了哈弗曼码是及时码。（3）哈夫曼码没有错误保护功能，在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。但如果码串中有错误，哪怕仅是1位出现错误，不但这个码本身译错，更糟糕的是后面的数据串也会接着被译错，全乱了套，这种现象称为错误传播（errorpropagation）o计算机对这种错误也无能为力，说不出错在哪里，更谈不上去纠正它；（4）哈夫曼编码只能用整数来表示单个符号而不能用小数，这很大程度上限制了压缩效果；（5）哈夫曼所有位都是合在一起的，如果改动其中一位就可以使其数据变得面目全非。2.5设计步骤设一个有8个符号的信源X，各个符号出现的概率为:XP(XXP(X)12345670.390.170.120.10.070.060.05x80.04则有两种哈夫曼编码方法，（0,1）编码或者（1,0）编码。表1哈夫曼（0,1）编码过程框图信源符号xi概率、P(x.)iX10.39X20.17X30.12X40.1X50.07X60.06X70.05X80.040.390.170.120.10.090.07)0.06」10.390.170.130.120.1I0.09J0编码过程0.390.190.170.12人0.390.250.190.13〕00.17J10.390.61、0.360.39J0.25〕1码字Wi码长Ki110013011300004010040101400010500011511该哈夫曼码的平均码长K为—^8K=妥p3)K=0.39*1+0.17*3+0.12*3+0/4+0.07*4+0.06*4+0.05*5+0.04*5i=1二2.63(码元/符号)信源熵H(x)为H(x)=—£p(x)logp(x)=-(0.39log0.39+0.17log0.17+0.12log0.12+0.1log0.1iii=1+0.07log0.07+0.06log0.06+0.05log0.05+0.04log0.04)二2.58(bit/符号)编码效率壁=螳.0.98K2.63冗余度丫=1—门=1-0.977=0.02表2哈夫曼(1,0)编码过程框图信源符号x概率p(x.)iX10.39X20.17X30.12X40.1X50.07X60.06X70.05X80.04编码过程0.390.390.390.390.170.170.190.2540.120.13▲017A.19]0.1,.12夕13]/0.17J0.09个/°.1〕/信源符号x概率p(x.)iX10.39X20.17X30.12X40.1X50.07X60.06X70.05X80.04编码过程0.390.390.390.390.170.170.190.2540.120.13▲017A.19]0.1,.12夕13]/0.17J0.09个/°.1〕/0.12J尸0/0.07]/0.09〕0/0.06J>000.36100.390.61O.25〕°码字称码长Ki01110310031111410114101041110151110051编码效率H(X)2.58门=—=—="0.98K2.63冗余度y=1-n=1-0.977=0.02通过以上的两种不同的编码方式进行比较，我们发现其实以上两种编码的码虽然不同，但是其知识将原来的1换成了0，0换成了1,他的码长，编码效率，冗余度是没有变化的。需要注意的是，对于多进制哈夫曼编码，为了提高编码效率，就要使长码的符号数量尽量少，概率尽量小，所以信源符号数最好满足m=(r-1)n+r，其中r为进制数，n为缩减的次数。比如说如果要进行三进制编码，那么最好信源具有7个符号，第一次合并后减少2个称为5个，第二次合并后又减少2个称为3个，这样给每一个赋予三进制符号就没有浪费的了。但是如果信源只有6个符号的话，为了减少最长码的数量，那么应该在第一次合并是添置为零的虚拟符号1个，事实上只合并2个概率最小的符号，后面每次合并3个，就可以是的最长的码的符号数量最少，也就是长码的概率最小，从而得到最高的编码效率。但是对于信源的某一个符号来说，有时候可能还会比定长码长。例如当信源有5个是，采用定长码方式可用3个二进制符号组成码字。而用变长码是有时候码字却长达4个二进制符号。所以编码简单化的代价就是要有大量的储存设备用来缓冲码字长度的差异，也就是码方差小的码质量好的原因。设一秒钟送一个信源符号，输出码字却只有5个二进制符号，若希望平均每秒输出_=2.61个二进制的信息率输出，才能从长久计算，输出和输入保持平衡。当储存量不够大的时候，可能有时取空，有时溢出。例如信源连续发出短码时，就会出现取空，就是说还没有存入就要输出。连续发出长码时，就会出现溢出，就是说存入太多，以致于存满了还未取出就要再次存入。所以应估计所需的存储器容量，才能使上述现象发生的概率小至可以容忍。当我们计算两个概率之和时，假设这两种的概率之和与上方概率有相同，我们应该把这个和概率放在其相同概率上方还是下方，我们就此进行讨论；设我们有一组概率为；0.4,0.2,0.2,0.1,0.1，则离散无记忆信源

X][xxxxx]P(X)「[0.40.20.20.i0.51J当概率相同放在下方时，哈夫曼编码为：表3哈夫曼编码方法信源编码概率编码过程码字码长X10.40.40.40.6]°/pi〜Y1.0002X20.20.2/0.4、J/0.4J1102X30.2/°.2]「/。.2J1112X40.1〕J0.2J10103X50.1〕10113当概率相同放在上方时，哈夫曼编码为:表4哈夫曼编码方法二信源编码概率编码过程码字码长X10.40.40.40.6]。1.00.2刀0.4]00.4J0.2]。0.2J14。』1/111X20.2012X30.20002X40.100104X50.100114则上面两表给出的哈夫曼平均码长相等，即K=28p(xi)Ki=2.2码元符号i=1编码效率也相同，即门=H^X1=0.965

K(¥k-K¥-K但是两种码的质量不完全相同，可用码方差来表示，即82=(¥k-K¥-K由此可见放在上面的哈夫曼编码比放在下面的哈夫曼编码得到的码方差要小许多，故应该放在上面。2.6哈弗曼树原理及过程哈夫曼树(Huffmantree)，又名最优树，指给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffmantree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。哈夫曼树是一种树形结构，用哈夫曼树的方法解编程题的算法就叫做哈夫曼算法。树并不是指植物，而是一种数据结构，因为其存放方式颇有点象一棵树有树叉因而称为树。最简哈夫曼树是由德国数学家冯。哈夫曼发现的，此树的特点就是引出的路程最短。哈弗曼最优二叉树步骤：1、初始化：根据给定的。个权值｛七七,…气｝构成n棵二叉树的集合F=｛T,T，…,T｝，其中每棵二叉树中只有一个带权w的根结点，左右子树均空。12ni2、找最小树：在F中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。3、删除与加入：在F中删除这两棵树，并将新的二叉树加入F中。4、判断：重复前两步(2和3)，直到F中只含有一棵树为止。该树即为哈夫曼树。图1哈夫曼(0,1)编码树图形哈夫曼(1,0)编码树图形1111哈夫曼树也可以是k叉的，只是在构造k叉哈夫曼树时需要先进行一些调整。构造哈夫曼树的思想是每次选k个权重最小的元素来合成一个新的元素，该元素权重为k个元素权重之和。但是当k大于2时，按照这个步骤做下去可能到最后剩下的元素少于k个。解决这个问题的办法是假设已经有了一棵哈夫曼树(且为一棵满k叉树)，则可以计算出其叶节点数目为(k-1)・n•k+1式子中的nk表示子节点数目为k的节点数目。于是对给定的n个权值构造k叉哈夫曼树时，可以先考虑增加一些权值为0的叶子节点，使得叶子节点总数为(-1)・n•k+1这种形式,然后再按照哈夫曼树的方法进行构造即可。第3章哈夫曼编码C语言实现3.1C语言编程3.1.1程序介绍本程序的编码和运行都是在VS2008中实现的，整个程序虽然看似庞大，但编写过程清晰，采用模块化编写，各个问题逐个击破，也方便对程序的管理和运行。整个程序的编写分为五大部分：main主函数，xiaoxi子函数，add子函数，coding子函数，ordination子函数。五大部分紧密相连，环环相扣，共同实现程序的编码。Main（）主函数主要负责其它函数的调用和最后结果的输出；Xiaoxi（）子函数主要负责输入需要的概率数据；Add（）子函数负责概率相加以便于排序；coding（）子函数负责具体编码工作。从右往左逐列编码，在每一列从下往上逐个编码，与上课时学习的方法稍有不同，其原理相同。ordination（）子函数主要负责各个概率间以及概率和的排序。该程序的优点有以下四个方面：1、程序在刚运行的时候需要输入概率数据，程序会启动蜂鸣器，提示需要输入数据；在输入需要输入的数据个数之后，会再次启动蜂鸣器提醒需要输入概率数程序具有的提醒功能是本程序的一大特色。2、程序在输入完需要的数据后，会自动排序，而不需要再去麻烦的排序。3、程序在运行过程中会自动检错（错误报警）：a、当输入的概率大于1或小于0的时候，系统会自动提示错误；b、当输入的概率之和大于1时，系统会自动检错。4、程序的编码过程清晰，编码过程中所有的概率都会在显示窗口显示出来，更清楚易懂。5、若两概率之和与另一概率相等，概率之和会自动排在后面。a、理论上讲求和排序的时候是按照列的形式，但程序按照行的形式。当然了，再完美的计划也会有破绽，这个程序也不可避免地存在些小缺点：b、出错报警时增加蜂鸣器长时间工作；c、add函数语句重复，流程图中已经进行了修改。程序使用说明：该程序是在VS2008环境下编写的，运行也需要在VS2008中运行，请确

保你在装载有VS2008环境下运行。3.2程序流程图以及说明说明主程序说明三重循环初始化，使其所有值为2显示“三重循环初始化，使其所有值为2显示“请输入消息个数”，响蜂鸣器调用获取概率函数，将返回值给y数组a一维，存放输入概率数组b，二维存放编码过程概率数组c，三维，存放编码每个位置即时编码；数组d，一维存放码长i为整型变量计数编码次数m为整型n，x为控制循环整型变量，y为检错控制整型变量，K为存放平均码长浮点型变量，H为存放信源熵浮点型变量，调用获取概率函数，将返回值给yY=0存在错误，结束程序图3主程序流程图3.3C语言源程序#include<stdio.h>#include<math.h>#definew10floata[w],b[w][w]={0},f[w]={0};inti,c[w][w][w],d[w]={0},m;xiaoxi(){intn;floatP=0;printf("\n请分别输入消息概率(区间在[0,1],概率之和应为):\n\a");for(n=0;n<m;n++){scanf("%f",&a[n]);if(a[n]>=1||a[n]<=0){printf("出错，概率应在[0,1]范围内\n");return(0);break;}P+=a[n];}if(P!=1){printf("出错，概率和应为1\n");return(0);}elsereturn(1);}ordination(intf,float*e){intg,j;floatk;for(g=0;g<f-1;g++)for(j=g+1;j<f;j++)if(e[g]<e[j]){k=e[g];e[g]=e[j];e[j]=k;}}coding(){intj,k,t,r;i=m-3;r=0;c[i+1][0][0]=0;c[i+1][1][0]=1;for(;i>=0;i--){t=0;for(k=m-2-i;k>=0;k--){if((f[i]==b[i+1][k])&&(t==0)){t=1;for(r=0;c[i+1][k][r]!=2;r++){c[i][m-i-2][r]=c[i+1][k][r];c[i][m-i-1][r]=c[i+1][k][r];}c[i][m-i-2][r]=0;c[i][m-i-1][r]=1;}}for(j=m-i-3;j>=0;j--)for(k=m-2-i;k>=0;k--)if(b[i][j]=b[i+1][k])for(r=0;c[i+1][k][r]!=2;r++)c[i][j][r]=c[i+1][k][r];}}add(){intj;for(i=0;i<m;i++)b[0][i]=a[i];for(i=1;i<m;i++){b[i][m-i-1]=b[i-1][m-i-1]+b[i-1][m-i];f[i-1]=b[i][m-i-1];for(j=0;j<m-i-1;j++)b[i][j]=b[i-1][j];ordination(m-i,b[i]);}}main(){intn,x,y;floatK=0,H=0;for(n=0;n<w;n++)for(x=0;x<w;x++)for(y=0;y<w;y++)c[n][x][y]=2;printf("\n请输入消息个数:\n\a");scanf("%d",&m);printf("\n");y=xiaoxi();if(y=1);{ordination(m,a);add();coding();printf("\n编码过程如下:\n");for(n=0;n<m;n++){printf("\n第％d列:",n+1);for(x=0;x<m;x++){if(b[n][x]==0)break;printf("\t%5.4f",b[n][x]);}printf("\n");}printf("\n");for(n=0;n<m;n++){printf("概率为％5审的符号编码后码字为:\t",a[n]);for(x=0;x<m;x++){if(c[0][n][x]==2)break;printf("%d",c[0][n][x]);d[n]++;}K+=a[n]*d[n];H+=(-a[n]*log10l(a[n]))/log10l(2);printf("\t其码长为:％d\n",d[n]);}printf("\n平均码长K=");printf("%3.2f",K);printf("\n信源«=%3.2f",H);printf("\n编码效率n=(H/K)=%3.2f%%”,H*100/K);printf("\n冗余度y=(-n)=%3.2f\n",1-H/K);}}

3.4程序步骤及运行本程序会对输入的概率自动检错，任何输入大于1或小于0的概率，或概率之和不等于1，系统都会提示错误。Q3C:\Windosyste-m32\cmcle-jce-请输入消息个数：8请分别输入消息概率｛区间在[oq],概宰之和应为M：0.020.03001Q.760OSQ.430.050.03出诸，概率,和应为1图4仿真纠错情况及结果进行哈弗曼编码:第一步，输入你所需要的概率个数：如你需要输入概率x1~x8，请输入8,点回车键。第二步，输入你所需要的概率，程序会自动排序：如输入概*x1~x8，分别点回车键确认，否则请按退格键。第三步，输入完成后，按下回车键，程序会出现结果。图5哈夫曼（1,0）编码运行结果显示各列重新排列的概率值

刃'D^ProgramFilesrxB&)\Micnc?softVisualStudio\Cofhftion\MSDev9&\Bin\Debug\a.exe'|i=i|即图5哈夫曼（1,0）编码运行结果显示各列重新排列的概率值Q.060.950.64请分别输入消息概率0.390.17G.12Q.060.950.64编吗过程0.39900.17000.120Q0.109Q0.0GS06.05000.04000.39300.17000.12G00.10300.39900.17000.120Q0.109Q0.0GS06.05000.04000.39300.17000.12G00.10300.0900&.07G06.OGO0第3.列0.12000.13300.17600.39300.2560Q.36Q00.3990第6列;0.39001.909012344455为为为为为为为为rzTrrdTnTTnT?0.12000.13300.17600.39300.2560Q.36Q00.3990第6列;0.39001.909012344455为为为为为为为为rzTrrdTnTTnT?马马rdTrzrr

-.fl?而???而彳

其其苴箕苴八其其苴一1nniun0000oiso0101HMH1kl00011^ZT..'.-1.■习,--,^rx^rx^-,\7圭主了壬车马马rfTrfT马Fd^rdrrdrLLF马马马马马马马局同扁扁扁肩扁扁号号号号号号号号符3第差弟u^iV—MJVL^MIrn—:-CT"-,r^r~Tlj*n2.__h.口.--Ij^TTAl—I「3.390SH.17RR9.1G0@3.070G3.3G0@W-MhWM9.&—-c~.—-c~.志芯上查基X忐慕十rnn:-3J.1■mam"T-m-lmXHaJ4mi平力码长W-2.fc3轻源fr2-5S编袒效=<HZK>=VB.W1XL冗余度T=(1-n)=0-02Pressanytocont±nue图6哈夫曼（0,1）编码树运行结果显示各列重新排列的概率值从运行结果可知该结果与理论一致，并且可以看出哈夫曼编码的3个特点：（1）哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码。（2）缩减信源的最后二个码字总是最后一位码元不同，前面各位码元相同（二元编码情况），从而保证了哈夫曼是即时码。（3）每次缩减信源的最长两个码字有相同的码长。这三个特点保证了所得的哈夫曼码一定是最佳码。因此哈夫曼是一种应用广泛而有效的数据压缩技术。利用哈夫曼编码进行通信可以大大提高信道利用率，加快信息传输速度，降低传输成本。数据压缩的过程称为编码，解压的过程称为译码。进行信息传递时，发送端通过一个编码系统对待传数据（明文）预先编码，而接受端将传来的数据（密文）进行译码。第4章总结本次课程设计，让我对哈夫曼编码以及c语言有了更深的理解和操作能力。开始针对题目进行分析，将所涉及的知识点，及相关函数做了分析，大体能够把握整体的设计流程及思路。再通过查阅相关资料，使自己的知识也更加丰富了，明白了哈夫曼编码的原理以及仿真的实现。首先对给题目进行了计算，进行哈夫曼编码，求出平均码长，编码效率，开始时不是很顺利，以前学的很多书本上的东西记得不太清楚了，经过复习课本的内容，掌握原理后顺利求出结果。然后是利用c语