课程设计-哈夫曼编码的分析和实现

课程设计任务书2010—2011学年第一学期专业：通信工程学号:070110101姓名：苟孟洛课程设计名称：信息论与编码课程设计设计题目：哈夫曼编码的分析与实现完成期限：自2010年12月2^日至2010年12月26日共±周设计目的1、深刻理解信源编码的基本思想与目的；2、理解哈夫曼编码方法的基本过程与特点；3、提高综合运用所学理论知识独立分析和解决问题的能力；4、使用MATLAB或其他语言进行编程。设计内容假设已知一个信源的各符号概率，编写适当函数，对其进行哈夫曼编码，得出码字，平均码长和编码效率，总结此编码方法的特点和应用。设计要求1、编写的函数要有通用性；2、信源可以自由选择，符号信源与图像信源均可。设计条件计算机、MATLAB或其他语言环境参考资料曹雪虹，张宗橙.信息论与编码.北京：清华大学出版社，2007.王慧琴.数字图像处理.北京：北京邮电大学出版社，2007.指导教师（签字）：教研室主任（签字）：批准日期：年月日摘要哈夫曼编码（HuffmanCoding）是一种编码方式，以哈夫曼树一即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称"熵编码法"），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。本课题通过MATLAB编写适当的函数，对一个随机信源进行哈夫曼编码，得出码字，平均码长和编码效率。从而理解信源编码的基本思想与目的以及哈夫曼编码方法的基本过程与特点，并且提高综合运用所学理论知识独立分析和解决问题的能力。关键字：哈夫曼，信源编码，MATLAB1课题描述错误！未定义书签。2哈夫曼编码的原理错误！未定义书签。TOC\o"1-5"\h\z\o"CurrentDocument"2.1哈夫曼编码的构造过程1\o"CurrentDocument"2.2哈夫曼编码的应用举例1\o"CurrentDocument"3哈夫曼编码的实现过程4\o"CurrentDocument"3.1软件介绍4\o"CurrentDocument"3.2设计内容4\o"CurrentDocument"3.2设计步骤4\o"CurrentDocument"4程序运行结果分析8总结10\o"CurrentDocument"参考文献111课题描述哈夫曼编码是一种编码方式，以哈夫曼树一即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称"熵编码法"），用于数据的无损耗压缩。这一术语是指使用一张特别的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特别之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。2哈夫曼编码的原理2.1哈夫曼编码的构造过程实现哈夫曼算法的大致描述为：初始化：将2n-1个结点的三个指针域的值置为空（可用一1表示），权值为0;输入：读入n个叶结点的权值存入向量的前个分量中，即形成有个结点的森林（一个结点为一棵树）；排序：按权值排序（从小到大）合并:把前两棵树组成一棵新树，放回森林，直至形成一棵树最后输出哈夫曼编码2.2哈夫曼编码应用举例哈夫曼树被广泛的应用在各种技术中，其中最典型的就是在编码技术上的应用。利用哈夫曼树，我们可以得到平均长度最短的编码。这里我们以计算机操作码的优化问题为例来分析说明。研究操作码的优化问题主要是为了缩短指令字的长度，减少程序的总长度以及增加指令所能表示的操作信息和地址信息。要对操作码进行优化，就要知道每种操作指令在程序中的使用频率。这一般是通过对大量已有的典型程序进行统计得到的。设有7种不同的指令，其使用频率如下表所示:指令使用频（P「）J10.401J20.30J30.15A0.05i0.04A0.03J70.03由于计算机内部只能识别0、1代码，所以若采用定长操作码，则需要3位（23=8）。显然，有一条编码没有作用，这是一种浪费。一段程序中若有!条指令，那么程序的总位数为3xn。为了充分地利用编码信息和减少程序的总位数，我们可以采用变长编码。如果对每一条指令指定一条编码，使得这些编码互不相同且最短，是否可以满足要求呢？即是否可以如下表所示这样编码呢？指令编码L0A1J300J401Js000A001J7010这样虽然可以使得程序的总位数达到最小，但机器却无法解码。例如对编码串0010110该怎么识别呢？第一个0可以识别为L，也可以和第二个0组成的串00一起被识别为13,还可以将前三位识别为16,这样一来，这个编码串就有多种译法。因此，若要设计变长的编码，则这种编码必须满足这样一个条件：任意一个编码不能成为其它任意编码的前缀。我们把满足这个条件的编码叫做前缀编码。

利用哈夫曼算法，可以使我们设计出最优的前缀编码。首先，我们以每条指令的使用频率为权值构造哈夫曼树，如下图6.27所示:对于该二叉树，我们可以规定向左的分支标记为1，向右的分支标记为0。这样，从根结点开始，沿线到达各频度指令对应的叶结点，所经过的分支代码序列就构成了相应频度指令的哈夫曼编码，如下图所示：指令编码J10J210J3110A11100i11101A11110J711111可以验证，该编码是前缀编码。若一段程序有1000条指令，其中I1大约有400条，I2大约有300条，I3大约有150，I4大约有50条，I5大约有40，I6大约有30，I7大约有30条。对于定长编码，该段程序的总位数大约为3x1000=3000。采用哈夫曼编码后，该段程序的总位数大约为1x400+2x300+3x150+5x(50+40+30+30)=2200。可见，哈夫曼编码中虽然大部分编码的长度大于定长编码的长度3,却使得程序的总位数变小了。可以算出该哈夫曼编码的平均码长为：=0.40x1+0.30x2+0.15x3+0.05x5+0.04xS+0.03x5+0.:03x5=2.20'3哈夫曼编码的实现过程3.1软件介绍MATLAB以矩阵作为基本编程单元，它提供了各种矩阵的运算与操作，并有较强的绘图功能。MATLAB集科学计算、图像处理、声音处理于一身，是一个高度的集成系统，有良好的用户界面，并有良好的帮助功能。MATLAB不仅流行于控制界，在机械工程、生物工程、语音处理、图像处理、信号分析、计算机技术等各行各业中都有极广泛的应用。MATLAB语言的特点1.编程效率高2.用户使用方便3.扩充能力强4.语句简单，内涵丰富5.高效方便的矩阵和数组运算6.方便的绘图功能3.2设计内容已知一个信源的各符号概率，编写适当函数，对其进行哈夫曼编码，得出码字，平均码长和编码效率，总结此编码方法的特点和应用。3.3设计步骤MATLAB的操作界面MATLAB操作界面主要分为：任务栏、命令窗、命令历史窗、当前目录浏览器、工作空间浏览器及一个“启动按钮”任务栏：位于软件的正上方。各个菜单分别为：文件、编辑、视窗、调试、桌面、窗体、帮助这几个窗口，点击每个窗口可以选择需要的操作。命令窗(CommandWindow)：位于软件操作界面的右侧。在此窗口里，可以输入各种指令、函数、变量表达式并进行各种操作。该窗口用于输入命令并显示除图形以外的所有执行结果。窗口中的“"为命令提示符，直接在其后面输入命令并按下回车键后，会出现计算结果在命令后面。命令历史窗(CommandHistory):位于软件操作界面的左下方。这个窗口记录了命令窗口已经运行过的所有命令(指令、函数等)，允许用户对这些命令进行选择、复制。程序如下：(假定随机信源为3,1,3,2,4,3,2,1,2,3)clearall;I=[3,1,3,2,4,3,2,1,2,3];len=length(I);t=2;biaozhi=0;b(1)=I(1);fori=2:lenforj=1:i-1ifI(j)==I(i)biaozhi=1;break;endendifbiaozhi==0b(t)=I(i);t=t+1;endbiaozhi=0;endfprintf('信源总长度:\n');disp(len);%信源总长度fprintf('字符:\n');disp(b);L=length(b);fori=1:La=0;forj=1:lenifb(i)==I①a=a+1;count(i)=a;endendendcount=count/len;%各字符概率fprintf('各字符概率:\n');disp(count);p=count;%%%%%%%%%%%%%%%%%%%%%%%%%%%s=0;l=0;H=0;N=length(p);fori=1:NH=H+(-p(i)*log2(p(i)));%计算信源信息熵endfprintf('信源信息熵:\n');disp(H);tic;fori=1:N-1%按概率分布大小对信源排序forj=i+1:Nifp(i)<p(j)m=p(j);p(j)=p(i);p(i)=m;endendendQ=p;m=zeros(N-1,N);fori=1:N-1%循环缩减对概率值排序，画出由每个信源符号概率到1.0处的路径[Q,l]=sort(Q);m(i,:)=[l(1:N-i+1),zeros(1,i-1)];Q=[Q(1)+Q(2),Q(3:N),1];endfori=1:N-1c(i,:)=blanks(N*N);endc(N-1,N)='0';c(N-1,2*N)='1';fori=2:N-1%对字符数组c码字赋值过程，记下沿路径的“1”和“0”；c(N-i,1:N-1)=c(N-i+1,N*(find(m(N-i+1,:)==1))-(N-2):N*(find(m(N-i+1,:)==1)));c(N-i,N)='0';c(N-i,N+1:2*N-1)=c(N-i,1:N-1);c(N-i,2*N)='1';forj=1:i-1c(N-i,(j+1)*N+1:(j+2)*N)=c(N-i+1,N*(find(m(N-i+1,:)==j+1)-1)+1:N*find(m(N-i+1,:)==j+1));endendfori=1:Nh(i,1:N)=c(1,N*(find(m(1,:)=i)-1)+1:find(m(1,:)=i)*N);%码字赋值ll(i)=length(find(abs(h(i,:))~=32));%各码字码长endl=sum(p.*ll);%计算平均码长n=H/l;%计算编码效率fprintf(编码的码字:\n');disp(h)%按照输入顺序排列的码字fprintf('平均码长:\n');disp(l)%输出平均码长fprintf(编码效率:\n');disp(n)%输出编码效率4程序运行结果分析运行结果如下图所示：运行结果分析：从运行结果可知该结果与理论一致，并且可以看出哈夫曼编码的3个特点⑴哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码。⑵缩减信源的最后二个码字总是最后一位码元不同，前面各位码元相同（二元编码情况），从而保证了哈夫曼是即时码。⑶每次缩减信源的最长两个码字有相同的码长。这三个特点保证了所得的哈夫曼码一定是最佳码。因此哈夫曼是一种应用广泛而有效的数据压缩技术。利用哈夫曼编码进行通信可以大大提高信道利用率，加快信息传输速度，降低传输成本。数据压缩的过程称为编码，解压的过程称为译码。进行信息传递时，发送端通过一个编码系统对待传数据（明文）预先编码，而接受端将传来的数据（密文）进行译码。要求数据这样一个简单的哈夫曼编码译码器。总结通过翻阅相关书籍，在网上查询资料学习有关哈夫曼编码的实现过程，我实在是获益匪浅，更加深刻的感觉到哈夫曼编码能够大大提高通信的效率，对于我们通信工程专业来说，学好这门科学是非常重要的，在以后的图像处理和压缩方面这门学科能给我们很大的帮助。同时，学习这门科学也是艰辛的，因为它比较难懂，这不仅需要我们发挥我们的聪明才智