编写matlab函数实现哈弗曼编码算法.docx

编写matlab函数实现哈弗曼编码算法.docx

《编写matlab函数实现哈弗曼编码算法.docx》由会员分享，可在线阅读，更多相关《编写matlab函数实现哈弗曼编码算法.docx（11页珍藏版）》请在冰点文库上搜索。

编写matlab函数实现哈弗曼编码算法

西南科技大学

课程设计报告

课程名称：

数字通信课程设计

设计名称：

编写Matlab函数实现哈夫曼编码的算法

******

学号:

********

班级：

通信0802

指导教师：

胥磊（老师）

起止日期：

2011.6.28-2011.7.4

西南科技大学信息工程学院制

课程设计任务书

学生班级：

通信0802学生姓名：

林正红学号：

********

设计名称：

编写Matlab函数实现哈夫曼编码的算法

起止日期：

2011.6.28-2011.7.4指导教师：

胥磊（老师）

设计要求：

1、理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法；

2、考虑一个有8种可能符号的信源，各种符号发生的概率分别为：

0.30、0.16、0.14、0.12、0.11、0.09、0.06、0.04；

3、根据Huffman编码算法，得到码树和Huffman码；

4、编写M函数，以8个信源产生的概率向量为变量，返回Huffman编码算法的编码结果，返回信源熵和编码的码字长度。

课程设计学生日志

时间

设计内容

2011.6.29---2011.6.30

上网查询相关知识点，并结合知识点看《matlab》、《现代通信原理》、《数字电视原理》等书籍。

2011.6.30

结合设计的具体要求，确定总体设计方案

2011.7.1

根据各个功能按模块化格式编写小程序，并实现其部分功能。

2011.7.2

整理程序，并调试。

2011.7.3

检查各项指标是否完成并修改程序，直到程序正确为止。

2011.7.4

最后完成报告的书写，准备答辩。

课程设计考勤表

周

星期一

星期二

星期三

星期四

星期五

课程设计评语表

指导教师评语：

成绩：

指导教师：

年月日

编写Matlab函数实现哈夫曼编码的算法

一、设计目的和意义

通过使用matlab编写哈夫曼编码的算法，以及最终算法实现的整个过程中，让我们学习Matlab软件的使用和编程；进一步深入理解Huffman编码算法的原理；提高独立进行算法编程的能力。

在此过程中，还需要用到数字电视原理里面的相关内容。

所以也能进一步了解关于熵编码，前缀码，信息量和信息熵，无失真信源编码定理，变字长编码等概念有更清晰的认识，也可以通过实验中的数据与等字长编码进行比较，体现出来变字长编码的优越性。

二、设计原理

1、熵编码

熵编码即编码过程中按熵原理不丢失任何信息的编码，解码后能无失真地恢复原图像。

信息熵为信源的平均信息量。

常见的熵编码有：

行程编码（RLE）、LZW编码、香农（Shannon）编码、哈夫曼（Huffman）编码和算术编码（arithmeticcoding）。

熵编码的基本原理就是给出现概率较大的符号一个较短码字，而给出现概率较小的符号

2、哈夫曼编码

在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称"熵编码法"），用于数据的无损耗压缩。

这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。

这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。

哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。

哈夫曼压缩属于可变代码长度算法一类。

意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。

因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。

2.1变字长编码定理:

最佳编码定理

在变字长编码中，对于出现概率大的信息符号，编以短字长的码,对于出现概率小的信息符号编以长字长的码，如果码字长度严格按照符号概率的大小的相反顺序排列，则平均码字长一定小于按任何其他符号顺序排列方式得到的码字长度。

2.2Huffman编码步骤

1）信源符号按概率大小顺序排列，按逆次序分配码字的长度。

2）出现概率最小的两个符号概率相加合成一个新概率。

3）将合成概率看成一个新组合符号概率，将新组合符号和其余符号一起重新按概率大小排序，再将最小概率的两个符号组成一个新的组合符号概率，计算出其出现概率。

重复上述做法，直到最后只剩下两个符号概率，且这两个概率相加等于1为止。

4）将上面得到的各符号用线连接起来，得到一个前缀码的码树。

树的端点对应N个信源。

每个节点的两个分支用二进制码的两个码元符号“0”，“1”分别表示。

从根节点开始沿着相反的路径，经过一个或者几个节点到达端点，将一路上遇到的二进制码元各符号顺序连接起来，这就是这个端点对应的信源符号的Huffman码的码字。

3、有关该信源编码的计算

设有N个码元组成的离散，无记忆符号集（说明：

以下均以本设计中要求的8个码元为例进行说明），其中每个符号由一个二进制码字（即代码）表示，但是字长不同。

若各符号出现的概率分别为P（x1），P（x2），……，P（xn），且各符号xi的以li个码元编码，则有如下结论：

在变字长编码时每个符号的平均码长为：

信源熵（信息熵：

指一团数据所带的信息量，平均信息量就是信息熵（entropy）为：

三、详细设计步骤

1、设计流程的分析

首先，通过自己前两天翻阅的通信原理，软件技术基础，数字电视原理等资料中，正确理解马夫曼的编码原理及实现方法，并且理解平均码长及信息熵等概念。

然后，按照题目所给的要求，通过自己计算得出题目中8个信源的编码结果，以便与实验结果相比较，判断实验中的结果是否正确。

其中，8个符号发送的概率分别为：

0.30、0.16、0.14、0.11、0.10、0.09、0.06、0.04；（注：

题目中最开始的0.11是0.12，但是为了满足各符号概率相加必须为1的要求，我将题目中的0.12改为了0.11）。

通过自己分析，得到的编码结果为：

0.30【10】、0.16【111】、0.14【110】、0.11【011】、

0.10【010】、0.09【000】、0.06【0011】、0.04【0010】

然后，根据试验中的编码结果得到各个码长，在按照实验原理中平均码长和信息熵的计算方法计算出平均码长及信息熵，以便与实验结果相对比。

通过计算，得出信源熵为2.7656bit/符号，编码的码字长度为2.8。

2、试验程序的具体实现流程

1）程序的输入：

以一维数组的形式输入要进行huffman编码的信源符号概率，在运行该程序前，显示文字提示信息，提示所要输入的概率矢量；然后对输入的概率矢量进行合法性判断，原则为：

如果概率矢量中存在小于0的项，则输入不合法，提示重新输入；如果概率矢量的求和大于1，则输入也不合法，提示重新输入。

2）huffman编码具体实现原理：

在输入的概率矩阵p正确的前提条件下,对p进行排序，并用矩阵L记录p排序之前各元素的顺序，然后将排序后的概率数组p的前两项，即概率最小的两个数加和，得到新的一组概率序列，重复以上过程，最后得到一个记录概率加和过程的矩阵p以及每次排序之前概率顺序的矩阵a。

3）新生成一个n-1行n列，并且每个元素含有n个字符的空白矩阵，然后进行huffman编码，具体分析如下：

◆将c矩阵的第n-1行的第一和第二个元素分别令为0和1（表示在编码时，根节点之下的概率较小的元素后补0，概率较大的元素后补1，后面的编码都遵守这个原则）

◆然后对n-i-1的第一、二个元素进行编码，首先在矩阵a中第n-i行找到值为1所在的位置，然后在c矩阵中第n-i行中找到对应位置的编码（该编码即为第n-i-1行第一、二个元素的根节点），则矩阵c的第n-i行的第一、二个元素的n-1的字符为以上求得的编码值，根据之前的规则，第一个元素最后补0，第二个元素最后补1，则完成该行的第一二个元素的编码，最后将该行的其他元素按照“矩阵c中第n-i行第j+1列的值等于对应于a矩阵中第n-i+1行中值为j+1的前面一个元素的位置在c矩阵中的编码值”的原则进行赋值，重复以上过程即可完成huffman编码。

4）根据理论公式，并结合程序中的数据，计算信源熵和平均码长，其比值即为编码密码效率。

5）具体的实现程序参见附录中的相关说明。

四、设计结果及分析

1、设计结果

运行程序之后，结果如下：

Huffman编码结果为:

h=10

111

110

011

010

000

0011

0010

编码的平均码长为:

l=2.8000

信源熵为:

hh=2.7656

分析后得到的结论如下：

将实验结果与通过理论分析的结果相对比，发现完全相同，说明实验程序是正确的，也说明自己对哈弗曼编码原理的理解是正确的。

在分析结果的同时，也得到了以下结论。

2、设计结果的分析

1）在哈夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应使合并后的新符号尽可能排在靠前的位置，这样可使合并后的新符号重复编码次数减少，使短码得到充分利用。

2）哈夫曼的编码效率相当高，对编码器的要求也简单得多。

3）哈夫曼它保证了信源概率大的符号对应于短码，概率小的符号对应于长码；每次缩减信源的最后两个码字总是最后一位码元不同，前面的各位码元都相同；每次缩减信源的最长两个码字有相同的码长。

4）霍夫曼的编法并不一定是唯一的，具体原因如下：

♦每次对缩减信源两个概率最小的符号分配“0”和“1”码元是任意的，所以可得到不同的码字。

只要在各次缩减中保持码元分配的一致性，即能得到可分离码字。

♦不同的码元分配，得到的具体码字不同，但码长li不变，平均码长也不变，所以没有本质区别；

♦缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方法上来说，这几个符号的次序可任意排列，编出的码都是正确的，但得到的码字不相同。

五、体会

1、实验中遇到的问题

起初，对哈弗曼编码确实不怎么懂，通过查了很多资料以后，自己再计算了很多次，才完全理解了哈弗曼编码的原理。

这样也可以方便对程序的理解。

这个实验程序不是完全自己写的，是通过网上的很多个程序的综合分析最后选择的一个相对简单的程序实现方法，但是还遇到一个问题，就是对哈弗曼编码的原理懂了，可是还是看不懂程序实现中一些细节问题。

通过问同学和老师之后，基本解决了这个问题。

2、实验体会

本次设计，首先针对题目进行分析，将所涉及的知识点，及相关函数做了分析，大体能够把握整体的设计流程及思路。

再通过查阅相关资料，能对相关的知识做正确的记录，以便随时查看。

但是，由于平时忽略了细节知识点的学习，在此次设计中但面对高斯白噪声时便束手无措。

后来经过查找，发现从高斯分布中获取采样值时，采样点所组成的随机过程就是“高斯白噪声”。

在MATLAB中，使用函数randn（）就可以产生这样的噪声。

此外，在分析所设计的图中，根据相关的通信原理，数字电视原理和计算机软件技术基础的知识可以对结果作出判断，这样就提高了自己的相关知识，同时加深了对matlab的运用。

在这个课程设计过程中我遇到了很多困难，花了很多时间查阅资料，我们是学通信专业的，没有数字电视处理这门课程，但是这个设计中的哈弗曼编码原理在这门书上才有较详细的说明。

所以我结合软件技术基础，通信原理及数字电视处理这三门课程之后，才把这个设计的原理理解清楚了。

设计的过程中我也学到了东西，这些对以后的学习将有很大帮助。

但是我知道自己做的还不够，有些基本的设计要求我都没达到，我只是做了我自己能做的。

我也知道这样的设计对我们是很有帮助的，但是由于我自己的能力有限我就只能做到这么多了，还请老师谅解，谢谢！

由于本次设计运用了不同的知识，这样我就可以更好的将不同科目的知识进行联系学习，对牢靠的学习有着巨大的支持，是一件非常有意义的事情。

六、参考文献

[1]曹志刚，钱亚生.现代通信原理.清华大学出版社，2009.9

[2]张威.MATLAB基础与编程入门（第二版）.西安电子科技大学出版社，2008.1

[3]余兆明，余智．数字电视原理．西安电子科技大学出版社，2009.2

[4]杨述斌，李永全.数字信号处理实践教程.华中科技大学出版社，2007.1

[5]程佩青，数字信号处理教程.清华大学出版社，2010.5

程序附录：

p=input（'请输入数据:

'）%提示输入界面[0.30,0.16,0.14,0.11,0.10,0.09,0.06,0.04]

n=length（p）;

fori=1:

n

ifp（i）<0

fprintf（'\n提示：

概率值不能小于0!

\n'）;

p=input（'请重新输入数据:

'）

end

end

ifabs（sum（p））>1

fprintf（'\n哈弗曼码中概率总和不能大于1!

\n'）;

p=input（'请重新输入数据:

'）

end

q=p;

a=zeros（n-1,n）;%生成一个n-1行n列的数组

fori=1:

n-1

[q,l]=sort（q）

a（i,:

）=[l（1:

n-i+1）,zeros（1,i-1）]

q=[q

（1）+q

（2）,q（3:

n）,1];

end

fori=1:

n-1

c（i,1:

n*n）=blanks（n*n）;

end

c（n-1,n）='0';c（n-1,2*n）='1';

fori=2:

n-1

c（n-i,1:

n-1）=c（n-i+1,n*（find（a（n-i+1,:

）==1））-（n-2）:

n*（find（a（n-i+1,:

）==1）））

c（n-i,n）='0'%根据之前的规则，在分支的第一个元素最后补0

c（n-i,n+1:

2*n-1）=c（n-i,1:

n-1）

c（n-i,2*n）='1'%根据之前的规则，在分支的第一个元素最后补1

forj=1:

i-1

c（n-i,（j+1）*n+1:

（j+2）*n）=c（n-i+1,n*（find（a（n-i+1,:

）==j+1）-1）+1:

n*find（a（n-i+1,:

）==j+1））

end

end%完成huffman码字的分配

fori=1:

n

h（i,1:

n）=c（1,n*（find（a（1,:

）==i）-1）+1:

find（a（1,:

）==i）*n）

ll（i）=length（find（abs（h（i,:

））~=32））%计算每一个huffman编码的长度

end

l=sum（p.*ll）;%计算平均码长

fprintf（'\nHuffman编码结果为:

\n'）;h

fprintf（'\n编码的平均码长为:

\n'）;l

hh=sum（p.*（-log2（p）））;%计算信源熵

fprintf（'\n信源熵为:

\n'）;hh

fprintf（'\n编码效率为:

\n'）;t=hh/l%计算编码效率