哈弗曼编码的分析与实现

《哈弗曼编码的分析与实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、吉林建筑大学电气与电子信息工程学院信息理论与编码课程设计报告设计题目:哈夫曼编码的分析与实现专业班级:电子信息工程111学生姓名:学号:10211134指导教师:吕卅王超设计时间:2014.11.24-2014.12.5教师评语：成绩评阅教师日期第1章概述11.1设计的作用、目的11.2设计任务及要求11.3设计内容1第2章费诺编码的分析与实现32」设计原理32.2设计步骤4第3章费诺编码的MATLAB实现73.1编程73.2运行结果及分析1721第4章总结19参考文献第1章概述1.1设计的作用、口的在当今信息化时代，数字信号充斥着各个角落。在数字信号的处理和传输中,信源编码是

2、首先遇到的问题，一个信源编码的好坏优劣直接影响到了后面的处理和传输。如何无失真地编码，如何使编码的效率最高，成为了大家研究的对象。哈夫曼编码就是其中的一种，哈夫曼编码的编码方案。它由最优二叉树既哈夫曼树得到编码，码元内容为到根结的路径中与父节点的左右子树的标识。所以哈夫曼在编码在数字通信中冇着重要的意义。可以根据信源符号的使用概率的高低来确定码元的长度。既实现了信源的无失真地编码，又使得编码的效率最高。《信息论与编码》是一门理论与实践密切结合的课程，课程设让是其实践性教学坏节之一，同时也是对课堂所学理论知识的巩固和补充。其主要目的是加深对理论知识的理解，掌握查阅冇关资料的技能，

3、提高实践技能，培养独立分析问题、解决问题及实际应用的能力。通过完成具体编码算法的程序设计和调试工作，提高编程能力，深刻理解信源编码、信道编译码的基本思想和冃的，掌握编码的基本原理与编码过程，增强逻辑思维能力，培养和提高自学能力以及综合运用所学理论知识去分析解决实际问题的能力，逐步熟悉开展科学实践的程序和方法。1.2设计任务及要求通过课程设计各环节的实践，应使学生达到如下要求：1.理解无失真信源编码的理论基础，常握无失真信源编码的基本方法；2.掌握哈夫曼编码/费诺编码方法的基本步骤及优缺点；3.深刻理解信道编码的基本思想与目的，理解线性分组码的基本原理与编码过程；4.能够使用MA

4、TLAB或其他语言进行编程，编写的函数要有通用性。1.3设计内容一个有8个符号的信源X,各个符号出现的概率为：西，x2,兀3，兀4,兀5，兀6X7X80.4().180.10.10.070.060.050.04_XP(X)编码方法：先将信源符号按其出现的概率大小依次排列，并取概率最小的字母分别配以0和1两个码元(先0后1或者先1后0,以后赋值固定)，再将这两个概率相加作为一个新字母的概率，与未分配的二进制符号的字母重新排队。并不断重复这一过程，直到最后两个符号配以0和1为止。最后从最后一级开始,向前返回得到各个信源符号所对应的码元序列，即为对应的码字。哈夫曼编码方式得到的码并非

5、唯一的。在对信源缩减时，两个概率最小的符号合并后的概率与其他信源符号的概率相同时，这两者在缩减中的排序将会导致不同码字，但不同的排序将会影响码字的长度，一般讲合并的概率放在上而,这样可获得较小的码方弟。第2章哈夫曼编码的分析与实现2.1设计原理哈夫曼编码（HuffmanCoding）是一种编码方式，哈夫曼编码是可变字长编码（VLC）的一种。Huffman于1952年提出种编码方法，该方法完全依据字符出现概率來构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码。1•哈夫曼编码步骤（1）将信源消息符号按照其出现的概率大小依次排列为Pl>p2>•->pn

6、（2）取两个概率最小的字母分别配以0和1两个码元，并将这两个概率相加作为一个新的概率，与未分配的二进制符号的字母重新排队。（3）对重新排列后的两个最小符号重复步骤（2）的过程。（4）不断重复上述过程，知道最后两个符号配以0和1为止。（5）从最后一级开始，向前返回得到的各个信源符号所对应的码元序列，即为相应的码字。2.哈夫曼编码特点哈夫曼编码是用概率匹配的方法进行信源匹配方法进行信源。它的特点是：（1）哈夫曼的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分应用了短码。（2）缩减信源的最后两个码字总是最后一位不同，从而保证了哈夫曼编码是即时码。（3）哈夫曼编码所

7、形成的码字不是唯一的，但编码效率是唯一的，在对最小的两个速率符号赋值时可以规定大的为“1”，小得为“0”，如果两个符号的出现概率相等时，排列时无论哪个在前都可以，所以哈夫曼所构造的码字不是唯一的，对于同一个信息源，无论上述的顺序如何排列，他的平均码长是不会改变的,所以编码效率是唯一的。（4）只有当信息源各符号出现的概率很不平均的时候，哈夫曼编码的效果才明显。（5）哈夫曼编码必须精确的统计出原始文件中每个符号出现频率，如果没有这些精确的统计将达不到预期效果。哈夫曼编码通常要经过两遍操作，第一遍