哈夫曼编码的分析与实现

吉林建筑大学电气与计算机学院信息理论与编码课程设计报告设计题目：哈夫曼编码的分析与实现专业班级：电子信息工程131学生姓名：学号：指导教师：设计时间：2016.11.21－2016.12.2教师评语：成绩评阅教师日期1第1章概述1.1设计的作用、目的通过完成具体编码算法的程序设计和调试工作，提高编程能力，深刻理解信源编码、信道编译码的基本思想和目的，掌握编码的基本原理与编码过程，增强逻辑思维能力，培养和提高自学能力以及综合运用所学理论知识去分析解决实际问题的能力，逐步熟悉开展科学实践的程序和方法。主要目的是加深对理论知识的理解，掌握查阅有关资料的技能，提高实践技能，培养独立分析问题、解决问题及实际应用的能力。通过课程设计各环节的实践，应达到如下要求：1．理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法；2．根据哈夫曼编码算法，考虑一个有多种可能符号（各种符号发生的概率不同）的信源，得到哈夫曼编码和码树；3．掌握哈夫曼编码的优缺点；4．通过完成具体编码算法的程序设计和调试工作，提高编程能力，深刻理解信源编码、信道编译码的基本思想和目的，掌握编码的基本原理与编码过程，增强逻辑思维能力，培养和提高自学能力以及综合运用所学理论知识去分析解决实际问题的能力，逐步熟悉开展科学实践的程序和方法。1.2设计任务及要求1.理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法；2.掌握哈夫曼编码/费诺编码方法的基本步骤及优缺点；3.深刻理解信道编码的基本思想与目的，理解线性分组码的基本原理与编码过程；4.能够使用MATLAB或其他语言进行编程，编写的函数要有通用性。1.3设计内容一个有8个符号的信源X，各个符号出现的概率为：04.005.006.007.01.012.017.039.0)(87654321xxxxxxxxXPX进行哈夫曼编码，并计算平均码长、编码效率、冗余度。2第2章哈夫曼编码的分析与实现2.1哈夫曼编码介绍及原理哈夫曼编码(HuffmanCoding)是一种熵编码编码压缩方式，哈夫曼编码是可变字长编码(VLC)的一种。哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是不同符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。哈夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。下面给出具体的Huffman编码算法。(1)首先统计出每个符号出现的频率，如本次课程设计x1到x7的出现频率分别为0.39，0.17，0.12，0.1，0.07，0.06，0.05，0.04。(2)从左到右把上述频率按从小到大的顺序排列。(3)每一次选出最小的两个值，作为二叉树的两个叶子节点，将和作为它们的根节点，这两个叶子节点不再参与比较，新的根节点参与比较。(4)重复(3)，直到最后得到和为1的根节点。(5)将形成的二叉树的左节点标0，右节点标1。把从最上面的根节点到最下面的叶子节点途中遇到的0,1序列串起来，就得到了各个符号的编码。2.2哈夫曼编码步骤（1）将信源消息符号按其出现的概率大小依次排列为12nppp（2）取两个概率最小的字母分别分配以0和1两个码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进制符号的字母重新排队。（3）对重排后的两个概率小符号重复步骤（2）的过程。（4）不断继续上述过程，直到最后两个符号配以0和1为止。（5）从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码子。3010101010101012.4哈夫曼编码特点（1）哈弗曼的编码方法保证了概率大的符号应对于短码，概率小的应对于长码，充分利用了短码；（2）缩减信源的最后两个码子总是最后一位不同，从而保证了哈弗曼码是及时码。（3）哈夫曼码没有错误保护功能，在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。但如果码串中有错误，哪怕仅是1位出现错误，不但这个码本身译错，更糟糕的是后面的数据串也会接着被译错，全乱了套，这种现象称为错误传播(errorpropagation)。计算机对这种错误也无能为力，说不出错在哪里，更谈不上去纠正它；（4）哈夫曼编码只能用整数来表示单个符号而不能用小数，这很大程度上限制了压缩效果；（5）哈夫曼所有位都是合在一起的，如果改动其中一位就可以使其数据变得面目全非。2.5设计步骤设一个有8个符号的信源X，各个符号出现的概率为：04.005.006.007.01.012.017.039.0)(87654321xxxxxxxxXPX则有两种哈夫曼编码方法，（0,1）编码或者（1,0）编码。表1哈夫曼（0,1）编码过程框图信源符号概率编码过程码字码长X10.390.390.390.390.390.390.61111X20.170.170.170.190.250.360.390013X30.120.120.130.170.190.250113X40.10.10.120.130.1700004X50.070.090.10.1201004X60.060.070.0901014X70.050.06000105X80.04000115ix()ipxiWiK4该哈夫曼码的平均码长K为81()0.39*1+0.17*3+0.12*3+0.1*4+0.07*4+0.06*4+0.05*5+0.04*5=2.63iiiKpxK（码元/符号）信源熵()Hx为81()()log()=-=bitiiiHxpxpx（0.39log0.39+0.17log0.17+0.12log0.12+0.1log0.1+0.07log0.07+0.06log0.06+0.05log0.05+0.04log0.04）2.58（/符号）编码效率()2.580.982.63HXK冗余度11-0.977=0.02表2哈夫曼（1,0）编码过程框图信源符号概率编码过程码字码长X10.390.390.390.390.390.390.61101X20.170.170.170.190.250.360.391103X30.120.120.130.170.190.251003X40.10.10.120.130.1711114X50.070.090.10.1210114X60.060.070.0910104X70.050.06111015X80.04111005信源熵()Hx为81()()log()=-=bitiiiHxpxpx（0.39log0.39+0.17log0.17+0.12log0.12+0.1log0.1+0.07log0.07+0.06log0.06+0.05log0.05+0.04log0.04）2.58（/符号）ix()ipxiWiK101010101010105该哈夫曼码的平均码长K为81()0.39*1+0.17*3+0.12*3+0.1*4+0.07*4+0.06*4+0.05*5+0.04*5=2.63iiiKpxK（码元/符号）编码效率()2.580.982.63HXK冗余度11-0.977=0.02通过以上的两种不同的编码方式进行比较，我们发现其实以上两种编码的码虽然不同，但是其知识将原来的1换成了0，0换成了1，他的码长，编码效率，冗余度是没有变化的。需要注意的是，对于多进制哈夫曼编码，为了提高编码效率，就要使长码的符号数量尽量少，概率尽量小，所以信源符号数最好满足rnrm)1(，其中r为进制数，n为缩减的次数。比如说如果要进行三进制编码，那么最好信源具有7个符号，第一次合并后减少2个称为5个，第二次合并后又减少2个称为3个，这样给每一个赋予三进制符号就没有浪费的了。但是如果信源只有6个符号的话，为了减少最长码的数量，那么应该在第一次合并是添置为零的虚拟符号1个，事实上只合并2个概率最小的符号，后面每次合并3个，就可以是的最长的码的符号数量最少，也就是长码的概率最小，从而得到最高的编码效率。但是对于信源的某一个符号来说，有时候可能还会比定长码长。例如当信源有5个是，采用定长码方式可用3个二进制符号组成码字。而用变长码是有时候码字却长达4个二进制符号。所以编码简单化的代价就是要有大量的储存设备用来缓冲码字长度的差异，也就是码方差小的码质量好的原因。设一秒钟送一个信源符号，输出码字却只有5个二进制符号，若希望平均每秒输出61.2_k个二进制的信息率输出，才能从长久计算，输出和输入保持平衡。当储存量不够大的时候，可能有时取空，有时溢出。例如信源连续发出短码时，就会出现取空，就是说还没有存入就要输出。连续发出长码时，就会出现溢出，就是说存入太多，以致于存满了还未取出就要再次存入。所以应估计所需的存储器容量，才能使上述现象发生的概率小至可以容忍。当我们计算两个概率之和时，假设这两种的概率之和与上方概率有相同，我们应该把这个和概率放在其相同概率上方还是下方，我们就此进行讨论；设我们有一组概率为；0.4，0.2，0.2，0.1，0.1，则离散无记忆信源61.01.02.02.04.0)(54321xxxxxXPX当概率相同放在下方时，哈夫曼编码为：当概率相同放在上方时，哈夫曼编码为：则上面两表给出的哈夫曼平均码长相等，即K=符号码元2.2)(81iKixip编码效率也相同，即=965.0)(KXHqiiiiKkapKkE12__2__21但是两种码的质量不完全相同，可用码方差来表示，即信源编码概率编码过程码字码长X10.4002X20.2102X30.2112X40.10103X50.10113信源编码概率编码过程码字码长X10.40.40.40.61.00.20.40.40.20.20.211X20.2012X30.20002X40.100104X50.100114010101010101010.40.40.60.20.20.20.40.20.41.001表3哈夫曼编码方法一表4哈夫曼编码方法二736.12116.022由此可见放在上面的哈夫曼编码比放在下面的哈夫曼编码得到的码方差要小许多，故应该放在上面。2.6哈弗曼树原理及过程哈夫曼树（Huffmantree），又名最优树，指给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffmantree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。哈夫曼树是一种树形结构，用哈夫曼树的方法解编程题的算法就叫做哈夫曼算法。树并不是指植物，而是一种数据结构，因为其存放方式颇有点象一棵树有树叉因而称为树。最简哈夫曼树是由德国数学家冯。哈夫曼发现的，此树的特点就是引出的路程最短。哈弗曼最优二叉树步骤：1、初始化：根据给定的n个权值12n,,棵二叉树的集合12,,,nFTTT，其中每棵二叉树中只有一个带权iw的根结点，左右子树均空。2、找最小树：在F中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。3、删除与加入：在F中删除这两棵树，并将新的二叉树加入F中。4、判断：重复前两步（2和3），直到F中只含有一棵树为止。该树即为哈夫曼树。图1哈夫曼（0,1）编码树图形00000001111111X100101000000001000011011001118哈夫曼树也