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

课程 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 任务书 2010—2011学年第一学期 专业： 通信工程  学号：  070110101        姓名： 苟孟洛        课程设计名称：  信息论与编码课程设计    设计题目： 哈夫曼编码的分析与实现         完成期限：自 2010 年 12月 20 日至 2010  年 12 月 26 日共 1 周 一．设计目的 1、深刻理解信源编码的基本思想与目的； 2、理解哈夫曼编码方法的基本过程与特点； 3、提高综合运用所学理论知识独立分析和解决问题的能力； 4、使用MATLAB或其他语言进行编程。 二．设计内容 假设已知一个信源的各符号概率，编写适当函数，对其进行哈夫曼编码，得出码字，平均码长和编码效率，总结此编码方法的特点和应用。 三．设计要求 1、编写的函数要有通用性； 2、信源可以自由选择，符号信源与图像信源均可。 四．设计条件 计算机、MATLAB或其他语言环境 五、参考资料 [1]曹雪虹，张宗橙.信息论与编码.北京：清华大学出版社，2007. [2]王慧琴.数字图像处理.北京：北京邮电大学出版社，2007. 指导教师（签字）：                教研室主任（签字）：            批准日期：      年  月    日 摘要 哈夫曼编码(Huffman Coding)是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称"熵编码法"），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。 本课题通过MATLAB编写适当的函数，对一个随机信源进行哈夫曼编码，得出码字，平均码长和编码效率。从而理解信源编码的基本思想与目的以及哈夫曼编码方法的基本过程与特点，并且提高综合运用所学理论知识独立分析和解决问题的能力。 关键字：哈夫曼，信源编码，MATLAB 目  录 1 课题描述    1 2 哈夫曼编码的原理    .1 2.1哈夫曼编码的构造过程……………………………..………………….………..1 2.2哈夫曼编码的应用举例…………………………….……………..……….…….1 3 哈夫曼编码的实现过程    4 3.1 软件介绍    4 3.2设计内容    4 3.2设计步骤……………………………………………………………………………….....4 4 程序运行结果分析…………………………………………….…………………………….8 总  结    10 参考文献    11 1课题描述 哈夫曼编码是一种编码方式，以哈夫曼树─即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称"熵编码法"），用于数据的无损耗压缩。这一术语是指使用一张特别的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特别之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。 2哈夫曼编码的原理 2.1 哈夫曼编码的构造过程 实现哈夫曼算法的大致描述为： 初始化：将2n-1个结点的三个指针域的值置为空（可用－1表 示），权值为0； 输入：读入n个叶结点的权值存入向量的前个分量中，即形成有个结点的森林（一个结点为一棵树）； 排序：按权值排序（从小到大） 合并:把前两棵树组成一棵新树,放回森林,直至形成一棵树 最后输出哈夫曼编码 2.2哈夫曼编码应用举例 哈夫曼树被广泛的应用在各种技术中，其中最典型的就是在编码技术上的应用。利用哈夫曼树，我们可以得到平均长度最短的编码。这里我们以计算机操作码的优化问题为例来分析说明。 研究操作码的优化问题主要是为了缩短指令字的长度，减少程序的总长度以及增加指令所能表示的操作信息和地址信息。要对操作码进行优化，就要知道每种操作指令在程序中的使用频率。这一般是通过对大量已有的典型程序进行统计得到的。 设有7种不同的指令，其使用频率如下表所示： 指令 使用频（pi） I1 0.40 I2 0.30 I3 0.15 I4 0.05 I5 0.04 I6 0.03 I7 0.03     由于计算机内部只能识别0、1代码，所以若采用定长操作码，则需要3位（23＝8）。显然，有一条编码没有作用，这是一种浪费。一段程序中若有n条指令，那么程序的总位数为3×n。为了充分地利用编码信息和减少程序的总位数，我们可以采用变长编码。如果对每一条指令指定一条编码，使得这些编码互不相同且最短，是否可以满足要求呢？即是否可以如下表所示这样编码呢？ 指令 编码 I1 0 I2 1 I3 00 I4 01 I5 000 I6 001 I7 010     这样虽然可以使得程序的总位数达到最小，但机器却无法解码。例如对编码串0010110该怎么识别呢？第一个0可以识别为I1，也可以和第二个0组成的串00一起被识别为I3，还可以将前三位识别为I6，这样一来，这个编码串就有多种译法。因此，若要设计变长的编码，则这种编码必须满足这样一个条件：任意一个编码不能成为其它任意编码的前缀。我们把满足这个条件的编码叫做前缀编码。 利用哈夫曼算法，可以使我们设计出最优的前缀编码。首先，我们以每条指令的使用频率为权值构造哈夫曼树，如下图6.27所示：         对于该二叉树，我们可以规定向左的分支标记为1，向右的分支标记为0。这样，从根结点开始，沿线到达各频度指令对应的叶结点，所经过的分支代码序列就构成了相应频度指令的哈夫曼编码，如下图所示： 指令 编码 I1 0 I2 10 I3 110 I4 11100 I5 11101 I6 11110 I7 11111     可以验证，该编码是前缀编码。若一段程序有1000条指令，其中I1大约有400条，I2大约有300条，I3大约有150，I4大约有50条，I5大约有40，I6大约有30，I7大约有30条。对于定长编码，该段程序的总位数大约为3×1000＝3000。采用哈夫曼编码后，该段程序的总位数大约为 1×400＋2×300＋3×150＋5×（50＋40＋30＋30）＝2200。可见，哈夫曼编码中虽然大部分编码的长度大于定长编码的长度3，却使得程序的总位数变小了。可以算出该哈夫曼编码的平均码长为： 3哈夫曼编码的实现过程 3.1软件介绍 MATLAB以矩阵作为基本编程单元，它提供了各种矩阵的运算与操作，并有较强的绘图功能。MATLAB集科学计算、图像处理、声音处理于一身，是一个高度的集成系统，有良好的用户界面，并有良好的帮助功能。MATLAB不仅流行于控制界，在机械工程、生物工程、语音处理、图像处理、信号分析、计算机技术等各行各业中都有极广泛的应用。MATLAB语言的特点1．编程效率高  2．用户使用方便 3．扩充能力强  4．语句简单，内涵丰富 5．高效方便的矩阵和数组运算 6．方便的绘图功能 3.2设计内容 已知一个信源的各符号概率，编写适当函数，对其进行哈夫曼编码，得出码字，平均码长和编码效率，总结此编码方法的特点和应用。 3.3设计步骤 MATLAB的操作界面MATLAB操作界面主要分为：任务栏、命令窗、命令历史窗、当前目录浏览器、工作空间浏览器及一个“启动按钮” 任务栏：位于软件的正上方。各个菜单分别为：文件、编辑、视窗、调试、桌面、窗体、帮助这几个窗口，点击每个窗口可以选择需要的操作。 命令窗(Command Window)：位于软件操作界面的右侧。在此窗口里，可以输入各种指令、函数、变量表达式并进行各种操作。该窗口用于输入命令并显示除图形以外的所有执行结果。窗口中的“>>”为命令 提示 春节期间物业温馨提示小区春节期间温馨提示物业小区春节温馨提示春节物业温馨提示物业春节期间温馨提示 符，直接在其后面输入命令并按下回车键后，会出现计算结果在命令后面。 命令历史窗(Command History)：位于软件操作界面的左下方。这个窗口记录了命令窗口已经运行过的所有命令（指令、函数等），允许用户对这些命令进行选择、复制。 程序如下：（假定随机信源为3,1,3,2,4,3,2,1,2,3） clear all; I=[3,1,3,2,4,3,2,1,2,3]; len=length(I); t=2; biaozhi=0; b(1)=I(1); for i=2:len for j=1:i-1 if I(j)==I(i) biaozhi=1; break; end  end if biaozhi==0 b(t)=I(i); t=t+1; end  biaozhi=0; end fprintf('信源总长度:\n'); disp(len); %信源总长度 fprintf('字符:\n'); disp(b ); L=length(b); for i=1:L a=0; for j=1:len if b(i)==I(j) a=a+1; count(i)=a; end end end count=count/len;%各字符概率 fprintf('各字符概率:\n'); disp(count); p=count; %%%%%%%%%%%%%%%%%%%%%%%%%%% s=0; l=0; H=0; N=length(p); for i=1:N H=H+(- p(i)*log2(p(i)));%计算信源信息熵 end fprintf('信源信息熵:\n'); disp(H); tic; for i=1:N-1 %按概率分布大小对信源排序 for j=i+1:N if p(i)