哈夫曼编码的代码实现

中南大学

信息论编码实验报告

专业班级:电子信息1002 指导老师：赵颖 姓名:付永军 学号:0909100707

1

目录

一.实验目的 ..................................................................................... 3 二、实验内容 .................................................................................. 3 三、实验原理 .................................................................................. 4 1.1使用MATLAB 实现香农码编码。 ...................................... 4 1.2、使用MATLAB 实现HUFFMAN 编码. ............................... 7 2.1、使用C++实现香农码编码 ........................

吉林建筑大学

电气与计算机学院

信息理论与编码课程设计报告

设计题目： 哈夫曼编码的分析与实现 专业班级： 电子信息工程 131 学生姓名： 学 号： 指导教师：

设计时间： 2016.11.21－2016.12.2

教师评语： 成绩 评阅教师 日期

第1章 概述

1.1设计的作用、目的

通过完成具体编码算法的程序设计和调试工作，提高编程能力，深刻理解信源编码、信道编译码的基本思想和目的，掌握编码的基本原理与编码过程，增强逻辑思维能力，培养和提高自学能力以及综合运用所学理论知识去分析解决实际问题的能力，逐步熟悉开展科学实践的程序和方法。主要目的是加深对理论知识的理解，掌握查阅有关资料的技能，提高实践技能，培养独立分析问题、解决问题及实际应用的能力。

通过课程设计各环节的实践，应达到如下要求：

1．理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法； 2．根据哈夫曼编码算

哈夫曼编码及Matlab实现

哈夫曼编码是一种所得码字是异前置的变长码，其平均码长最短，被称为最佳变长码，也称为哈夫曼编码。 其具体编码方法如下：

（1）将信源信息（符号）按概率大小排队；

（2）从最小概率的两个消息开始编码，并给予一定的编码规则，如小概率的下支路编为1（或0），大概率的上支路变为0（或1），若两者概率相等，仍是下支路为1上支路为0；

（3）将已经编码的两个消息对应概率合并，并重新按概率大小排队，重复步骤（2）；

（4）重复步骤（3），直至合并概率归一为止；

（5）变成的变长码是按后出先编方式，即从概率归一的树根沿编码路线逆行至对应的消息。

实验内容：

给定离散信源：

u2u3u4u5u6u7??U??u1??p??0.200.190.180.170.150.100.01? ????对其进行哈夫曼编码，其理论结果如下： 消息 （U） 概率 (p) 0.20 0.19 0.18 0.17 0.15 0.10 0.01

0.20 0.26 0.35 0.39 0.61 1.0 0.19 0.20 0.26 0.35 0.39

1．哈夫曼编码的方法

编码过程如下 :

(1) 将信源符号按概率递减顺序排列 ;

(2) 把两个最小的概率加起来 , 作为新符号的概率 ; (3) 重复步骤 (1) 、 (2), 直到概率和达到 1 为止 ;

(4) 在每次合并消息时，将被合并的消息赋以1和0或0和1； (5) 寻找从每个信源符号到概率为1处的路径，记录下路径上的1和0； (6) 对每个符号写出\、\序列（从码数的根到终节点）。

2．哈夫曼编码的特点

①哈夫曼方法构造出来的码不是唯一的 。

原因

·在给两个分支赋值时 , 可以是左支 ( 或上支 ) 为 0, 也可以是右支 ( 或下支 ) 为 0, 造成编码的不唯一。

·当两个消息的概率 相等时, 谁前谁后也是随机的 , 构造出来的码字就不是唯一的。

②哈夫曼编码码字字长参差不齐 , 因此硬件实现起来不大方便。 ③哈夫曼编码对不同的信源的编码效率是不同的。

· 当信源概率是 2 的负幂时 , 哈夫曼码的编码效率达到 100%; · 当信源概率相等时 , 其编码效率最低。

· 只有在概率分布很不均匀时 , 哈夫曼编码才会收到显著的效果 , 而在信源分布均匀的情况下 , 一般不使用哈夫曼编码。

④对信源进行哈夫曼编码后 ,

#include #include #include

#define n 6 /* 叶子数目 */ #define m 2*n-1 /* 结点总数 */ #define Maxval 1 /* 最大权值 */ typedef char datatype;

typedef struct //定义为结构类型 { float weight; //权值 datatype data; int lchild, rchild, parent; } hufmtree; hufmtree tree[m]; typedef struct { char bits[n]; /* 编码数组位串，其中n为叶子结点数目*/ int start; /* 编码在位串的起始位置 */ datatype data; } codetype; codetype code[n];

HUFFMAN(hufmtree tree[ ]) { int i, j, p1,p2; char ch; float small

安徽大学

本科毕业论文（设计、创作）

题 目： 哈夫曼编码与算术编码压缩效率比较 学生姓名： 李伟 学号： E20714134 院（系）： 计算机科学与技术 专业： 软件工程 入学时间： 2007 年 9 月 导师姓名： 韩莉 职称/学位： 讲师/硕士 导师所在单位： 安徽大学计算机科学与技术学院 完成时间： 2011 年 5 月

哈夫曼编码与算术编码压缩效率比较

摘要

算术编码和哈夫曼编码都利用信源符号的概率分布特性进行编码，使平均码长逼近信息 熵是压缩编码算法的第一要求，算术编码比哈夫曼编码逼近信息熵的能力要强，但是编码效率和实现往往是一对矛盾，编码效率的提高，往往要在实现上付出代价，所以，选择压缩算 要权衡这两点。本论文开篇先引入了信息论的一些概念，因为编码理论发源于信息论，是各 种编码算法的数学基础。然后在第2章分析了算术编码原理，并从无限精度的算术编码原理 过渡到在计算机上能够实现的二进制编码原理。在第3章紧接着介绍了哈夫曼编码原理，并 讨论了怎样

哈夫曼编码的C语言实现

编码原理程序步骤的分析：

哈夫曼码是用概率匹配方法进行信源编码。编程时应该注意：1，概率大的符号对应于短码，概率小的对应于长码，充分利用短码；2缩减信源的最后二个码字，总是最后一位不同，保证了哈夫曼码是即时码。程序步骤：（见信息论课本p88页内容）

（l）将信号源的符号按照出现概率递减的顺序排列。

（2）将两个概率最小的字母分别配以0和1两个码元，并将这两个概率相加作为一个新字母的概率

（3）重排后的两个概率最小符号重复步骤(2)过程。

（4）不断继续上述过程，直到最后两个符号配以0和1为止

（5）从最后一级开始向前返回各个信源符号所对应的码元序列，及相应的码字。

根据以上规则编码可知：哈夫曼编码实际上构造了一个码树，码树从最上层的端点开始构造，到树根结束，最后得到一个横放的码树，所以编出的码是即时码。哈夫曼编码概率大的符号对应于短码，概率小的符号对应于长码，使平均码长最小。每次对概率最小的两个符号求概率之和形成缩减信源时，构造出两个树枝，由于给两个树枝赋码元时是任意的，因此编出的码字不惟一。

程序源代码如下;

#include <stdio.h>

#include #include

哈夫曼编码 综合设计报告

LD

1

武汉工程大学计算机科学与工程学院 综合设计报告

目 录

摘 要 ……………………………………………………………………………………… I Abstract …………………………………………………………………………………... II 第一章 课题背景…………………………………………………………………….…….. 1 1.1 课题背景 ……………………………………………………………………….……...1 1.2 课题内容 ………………………………………………..………………………….… 1 第二章 设计简介及设计方案论述 ………………………………………………….…….. 2 2.1 设计简介 ………………………………………………..……………………….….…2 2.2 问题分析 ………………………………………………..……………………….….…2 2.3 设计方案 ………………………………………………..……………………….….…3 第三章 详细设计…………………………………………………………..………….…….. 4 3.1 主要流程图 ……………………………………………..…………

（1）哈夫曼编码所形成的码字不是唯一的，但编码效率是唯一的 在对最小的两个

概率符号赋值时，可以规定为大的为“1”、小的为“0”，反之也可以。如果两个符号的出现概率相等时，排列时无论哪个在前都是可以的，所以哈夫曼所构造的码字不是唯一的，对于同一个信息源，无论上述的前后顺序如何排列，它的平均码长是不会改变的，所以编码效率是唯一的。 （2）只有当信息源各符号出现的概率很不平均的时候，哈夫曼编码的效果才明显。 （3）哈夫曼编码必须精确地统计出原始文件中每个符号的出现频率，如果没有这些精确的统计，将达不到预期的压缩效果。霍夫曼编码通常要经过两遍操作，第一遍进行统计，第二遍产生编码，所以编码速度相对慢。另外实现的电路复杂，各种长度的编码的译码过程也是比较复杂的，因此解压缩的过程也比较慢。 （4）哈夫曼编码只能用整数来表示单个符号而不能用小数，这很大程度上限制了压缩效果。

（5）哈夫曼所有位都是合在一起的，如果改动其中一位就可以使其数据变得面

目全非

运动估计基本思想是将图像序列的每一帧分成许多互不重叠的宏块，并认为宏块内所有象素的位移量都相同，然后对每个宏块到参考帧某一给定特定搜索范围内根据一定的匹配准则找出与当前块最相似的块，即匹配块，匹配块与当前块的

实验一 离散信源及其信息测度

一、实验目的

1、理解信源编码的意义； 2、熟悉 MATLAB程序设计；

3、掌握哈夫曼编码的方法及计算机实现；

二、实验原理

通信的根本问题是如何将信源输出的信息在接收端的信宿精确或近似的复制出来。为了有效地复制信号，就通过对信源进行编码，使通信系统与信源的统计特性相匹配。

若接收端要求无失真地精确地复制信源输出的信息，这样的信源编码即为无失真编码。即使对于一个小的时间段内，连续信源输出的信息量也可以是无限大的，所以对其是无法实现无失真编码的；而离散信源输出的信息量却可以看成是有限的，所以只有离散信源才可能实现无失真编码。

凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合都可以称为最佳码。为此必须将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字长度最短。

变字长编码的最佳编码定理：在变字长码中，对于概率大的信息符号编以短字长的码；对于概率小的信息符号编以长字长的码。如果码字长度严格按照符号概率的大小顺序排列，则平均码字长度一定小于俺任何顺序排列方式得到的码字长度。

哈夫曼编码就是利用了这个定理，讲等长分组的信源符号，根据其概率分布采用不等长编码。概率大的分组，使用