信息论与编码课程设计哈夫曼编码的分析与实现

实验一一、实验背景*哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。

Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般叫作Huffman编码。

二、实验要求*利用程序实现哈夫曼编码，以加深对哈夫曼编码的理解，并锻炼编程能力。

三、代码分析#include<stdio.h>#define n 3 //叶子数目#define m (2*n-1) //结点总数#define maxval 10000.0 //maxval是float类型的最大值#define maxsize 100 //哈夫曼编码的最大位数typedef struct //定义霍夫曼树结构体{char ch; //消息float weight; //所占权重int lchild,rchild,parent; //定义左孩子、右孩子}hufmtree;typedef struct //定义霍夫曼编码结构体{char bits[n]; //位串int start; //编码在位串中的起始位置char ch; //字符}codetype;void huffman(hufmtree tree[]); //建立哈夫曼树void huffmancode(codetype code[],hufmtree tree[]); //根据哈夫曼树求出哈夫曼编码void decode(hufmtree tree[]); //依次读入电文，根据哈夫曼树译码void main(){printf(" ——哈夫曼编码——\n");printf("信源共有%d个符号\n",n);hufmtree tree[m]; //m个结点，即有m个树形结构codetype code[n]; //信源有n个消息，则需要n个编码int i,j; //循环变量huffman(tree); //建立哈夫曼树huffmancode(code,tree); //根据哈夫曼树求出哈夫曼编码printf("【输出每个字符的哈夫曼编码】\n");for(i=0;i<n;i++){printf("%c: ",code[i].ch);for(j=code[i].start;j<n;j++)printf("%c ",code[i].bits[j]);//“消息：该消息的编码”printf("\n");}printf("【读入电文，并进行译码】\n");decode(tree); //依次读入电文，根据哈夫曼树译码}void huffman(hufmtree tree[]) //建立哈夫曼树{int i,j,p1,p2; //p1,p2分别记住每次合并时权值最小和次小的两个根结点的下标float small1,small2,f;char c;for(i=0;i<m;i++) //初始化{tree[i].parent=0;tree[i].lchild=-1;tree[i].rchild=-1;tree[i].weight=0.0;}printf("【依次读入前%d个结点的字符及权值(中间用空格隔开)】\n",n);for(i=0;i<n;i++) //读入前n个结点的字符及权值{printf("输入第%d个字符为和权值",i+1);scanf("%c %f",&c,&f);getchar(); //吸收回车符tree[i].ch=c;tree[i].weight=f; //将接收到的结点的字符及权值存入它对应的结构体数据中}for(i=n;i<m;i++) //进行n-1次合并，产生n-1个新结点{p1=0;p2=0;small1=maxval;small2=maxval; //maxval是float类型的最大值for(j=0;j<i;j++) //选出两个权值最小的根结点{if(tree[j].parent==0) //还未找到父结点的if(tree[j].weight<small1) //如果有比最小的还小的{small2=small1; //改变最小权、次小权及对应的位置small1=tree[j].weight;p2=p1;p1=j;}else if(tree[j].weight<small2) //如果有比最小的大，但比第二小的小的{small2=tree[j].weight; //改变次小权及位置p2=j;}}//找出的两个结点是新节点i的两个孩子tree[p1].parent=i;tree[p2].parent=i;tree[i].lchild=p1; //最小权根结点是新结点的左孩子tree[i].rchild=p2; //次小权根结点是新结点的右孩子tree[i].weight=tree[p1].weight+tree[p2].weight;}} //huffman//codetype code[]为求出的哈夫曼编码//hufmtree tree[]为已知的哈夫曼树void huffmancode(codetype code[],hufmtree tree[]) //根据哈夫曼树求出哈夫曼编码{int i,c,p;codetype cd; //缓冲变量for(i=0;i<n;i++){cd.start=n; //编码在位串中的起始位置cd.ch=tree[i].ch;c=i; //从叶结点出发向上回溯，第i个叶结点p=tree[i].parent; //tree[p]是tree[i]的父结点while(p!=0){cd.start--;if(tree[p].lchild==c)cd.bits[cd.start]='0'; //tree[i]是左子树，生成代码'0' elsecd.bits[cd.start]='1'; //tree[i]是右子树，生成代码'1' c=p; //c记录此时的父结点p=tree[p].parent; //p记录新的父结点，即原来的父结点的父结点，向上溯回}code[i]=cd; //第i+1个字符的编码存入code[i] }} //huffmancodevoid decode(hufmtree tree[])//依次读入电文，根据哈夫曼树译码{int i,j=0;char b[maxsize];i=m-1; //从根结点开始往下搜索printf("输入发送的编码：");gets(b);printf("译码后的字符为");while(b[j]!='\0'){if(b[j]=='0')i=tree[i].lchild; //走向左子树elsei=tree[i].rchild; //走向右子树if(tree[i].lchild==-1) //如果回到叶结点，则把该结点的消息符号输出{printf("%c",tree[i].ch);i=m-1; //回到根结点}j++;}printf("\n");if(tree[i].lchild!=-1&&b[j]=='\0') //电文读完，但尚未到叶子结点printf("\nERROR\n"); //输入电文有错}//decode四、实验补充说明解码时，以回车键结束输入电文。

信息论与编码课程设计--统计信源熵与哈夫曼编码信息论与编码课程设计信息论与编码课程设计报告设计题目:统计信源熵与哈夫曼编码专业班级学号学生姓名指导教师教师评分2015年 3 月 25 日1信息论与编码课程设计目录一、设计任务与要求...................................................................... ...........................................3 二、设计思路...................................................................... .......................................................3 三、设计流程图...................................................................... (5)四、程序运行及结果...................................................................... ...........................................6 五、心得体会...................................................................... . (8)参考文献...................................................................... (9)附录:源程序...................................................................... .. (10)2信息论与编码课程设计一、设计任务与要求1.1设计目的信息论与编码是信息、通信、电子工程专业的基础，对理论研究和工程应用均有重要的作用。

20180902一、需求分析1、问题描述利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。

但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（解码）。

对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。

试为这样的信息收发站设计一个哈夫曼编译码系统。

2、基本要求（1）初始化（Initialzation）。

从数据文件DataFile.txt中读入字符及每个字符的权值，建立哈夫曼树HuffTree；（2）编码（EnCoding）。

用已建好的哈夫曼树，对文件ToBeTran.txt 中的文本进行编码形成报文，将报文写在文件Code.txt中；（3）译码（Decoding）。

利用已建好的哈夫曼树，对文件CodeFile.txt 中的代码进行解码形成原文，结果存入文件Textfile.txt中；（4）输出（Output）。

输出DataFile.txt中出现的字符以及各字符出现的频度（或概率）；输出ToBeTran.txt及其报文Code.txt；输出CodeFile.txt及其原文Textfile.txt；二、概要设计1.数据结构本程序需要用到以一个结构体HTNode，以及一个二维数组HuffmanCode。

2.程序模块本程序包含两个模块，一个是实现功能的函数的模块，另一个是主函数模块。

系统子程序及功能设计本系统共有七个子程序，分别是：a.int min1(HuffmanTree t,int i)//进行比较b.void select(HuffmanTree t,int i,int *s1,int *s2)//求权值最小的两个数c.void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,char *u,int n)///* w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n 个字符的赫夫曼编码HC */d.void Initialzation(HuffmanTree *HT,HuffmanCode *HC)//初始化e.int EnCoding(HuffmanTree *HT,HuffmanCode *HC)//对文件ToBeTran.txt中的文本进行编码形成报文，将报文写在文件Code.txt 中f.int pipei(char *c,int n,HuffmanCode *HC)//在huffmancode寻找匹配的编码g.void Decoding(HuffmanTree *HT,HuffmanCode *HC)//对文件CodeFile.txt中的代码进行解码形成原文，结果存入文件Textfile.txt中3.各模块之间的调用关系以及算法设计主函数调用Initialzation，EnCoding，Decoding。

课程设计任务书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编写适当的函数，对一个随机信源进行哈夫曼编码，得出码字，平均码长和编码效率。

从而理解信源编码的基本思想与目的以及哈夫曼编码方法的基本过程与特点，并且提高综合运用所学理论知识独立分析和解决问题的能力。

实验六 Huffman 编码一、实验目的：掌握Huffman 编码的方法二、实验内容：对信源123456,,,,,()0.250.250.020.150.10.05a a a a a a X P X ⎧⎫⎛⎫=⎨⎬ ⎪⎝⎭⎩⎭进行二进制Huffman 编码。

并计算其平均码长，编码效率。

三、实验步骤（1）将概率按从小到大的顺序排列（2）给两个概率最小的信源符号1()P a 和2()P a 各分配一个码位“0”和“1”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和最为新符号的概率，结果得到一个只包含（n-1）个信源符号的新信源，称为信源的第一次缩减信源，用S1表示。

（3）将缩减信源S1的符号仍按概率从大到小的顺序排列，重复步骤2，得到只含（n-2）个符号的缩减信源S2。

（4）重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩的两个符号的概率之和为1。

然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。

四、实验数据及结果分析（1）将信源符号按概率从小到大的顺序排列。

P=（0.25 0.25 0.2 0.15 0.1 0.05）；（2）输出每个灰度级的编码00010000001111001（3）计算其平均码长和编码效率平均码长L=2.4500编码效率xiaolv=0.9891（4）运行截图如下所示：图一运行及结果五、代码附录n=input('N=');%输入信源符号的个数L=0; H=0;for i=1:nP(i)=input('P=');%输入信源符号概率分布s=s+P(i);endif s~=1error('不符合概率分布');endP=sort(P);p=P;mark=zeros(n-1,n); %mark为n-1行，n列矩阵，用来记录每行概率排列次序for i=1:n-1[P,num]=sort(P); %对输入元素排序并记录mark(i,:)=[num(1:n-i+1),zeros(1,i-1)];P=[P(1)+P(2),P(3:n),1];endfor i=1:n-1table(i,:)=blanks(n*n); %blanks 创建空格串endtable(n-1,n)='1';table(n-1,2*n)='0'for i=2:n-1table(n-i,1:n-1)=table(n-i+1,n*(find(mark(n-i+1,:)==1))-(n-2):n*(find(mark(n-i+1,:)==1))); %按mark的记录依次赋值table(n-i,n)='1';table(n-i,n+1:2*n-1)=table(n-i,1:n-1);table(n-i,2*n)='0';for j=1:i-1table(n-i,(j+1)*n+1:(j+2)*n)=table(n-i+1,n*(find(mark(n-i+1,:)==j+1)-1)+1:n*find(mark(n-i+1,:)==j+1));%mark的记录依次赋值endend%得到编码后的码字for i=1:nW(i,1:n)=table(1,n*(find(mark(1,:)==i)-1)+1:find(mark(1,:)==i)*n);l(i)=length(find(abs(W(i,:))~=32));%32表示空字符，要找不是空字符的个数，即为每个数编码的个数L=L+p(i)*l(i); %计算平均码长H=H-p(i)*log2(p(i));%计算信源熵endxiaolv=H/L; %计算编码效率disp('输出每个概率的编码');disp(W);disp('输出平均码长L：');disp(L);disp('输出编码效率xiaolv：');disp(xiaolv);六，实验总结：通过该实验，掌握了Huffman编码。

信息论与编码实验报告实验课程名称：赫夫曼编码（二进制与三进制编码）专业信息与计算科学班级信息与计算科学1班学生姓名李林钟学号 2013326601049指导老师王老师一、实验目的利用赫夫曼编码进行通信可以大大提高通信利用率，缩短信息传输时间，降低传输成本。

赫夫曼编码是信源编码中最基本的编码方法。

●理解赫夫曼编码，无论是二进制赫夫曼编码，还是m 进制赫夫曼编码，都要理解其编码原理和编码步骤。

● 回顾无失真信源编码定理，理解无失真编码的基本原理和常用编码方法。

●掌握二进制赫夫曼编码和m 进制赫夫曼编码的基本步骤，能计算其平均码长，编码效率等。

●应用二进制赫夫曼编码或m 进制赫夫曼编码处理简单的实际信源编码问题。

二、实验环境与设备1、操作系统与编程软件：windows 操作系统，cfree5.0， Visual C++ 6.0。

2、编程语言：C 语言以及C++语言 三、实验内容1. 二进制赫夫曼编码原理及步骤： （1）信源编码的计算设有N 个码元组成的离散、无记忆符号集，其中每个符号由一个二进制码字表示，信源符号个数n 、信源的概率分布P={p(s i )},i=1,…..,n 。

且各符号xi 的以li 个码元编码，在变长字编码时每个符号的平均码长为∑==ni li xi p L 1)( ；信源熵为：)(log )()(1xi p xi p X H ni ∑=-= ；唯一可译码的充要条件：11≤∑=-ni Ki m ；其中m 为码符号个数，n 为信源符号个数，Ki 为各码字长度。

（2）二元霍夫曼编码规则（1）将信源符号依出现概率递减顺序排序。

（2）给两个概率最小的信源符号各分配一个码位“0”和“1”，将两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含（n-1）个信源符号的新信源。

称为信源的第一次缩减信源，用s1 表示。

（3）将缩减信源 s1 的符号仍按概率从大到小顺序排列，重复步骤(2)，得到只含（n-2）个符号的缩减信源s2。

信息论与编码课程小结报告----09网工xxx 200940450611.哈夫曼编码简介哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。

uffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。

2.哈夫曼编码原理哈夫曼编码(Huffman Coding)是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。

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

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

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

这种方法是由David.A.Huffman发展起来的。

例如，在英文中，e的出现概率很高，而z的出现概率则最低。

当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去25个位（不是26）。

用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。

二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。

倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。

3哈夫曼编码步骤首先，哈夫曼编码是哈夫曼树的一个应用，哈夫曼书又称优二树，是一种带路径长度最短的二叉树，所谓树的带权路径长度，就是树中所有的叶节点的权值乘上其到根节点的路径长度（若根节点为0，叶节点到根节点的路径长度为叶节点的层数）。

树的带全路径长度记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N 个权值Wi(i=1,2,...n)构成一棵有N哥叶节点的二叉树，相应的叶节点的路径长度为Li(i=1,2,...n)。

目录一：实验原理----------------------------1二：程序源代码--------------------------1三：实验分析-----------------------------6四：实验结论---------------------------7赫夫曼编码一：实验原理哈夫曼编码的具体步骤归纳如下：① 概率统计（如对一幅图像，或m幅同种类型图像作灰度信号统计），得到n个不同概率的信息符号。

② 将n个信源信息符号的n个概率，按概率大小排序。

③ 将n个概率中，最后两个小概率相加，这时概率个数减为n-1个。

④ 将n-1个概率，按大小重新排序。

⑤ 重复③，将新排序后的最后两个小概率再相加，相加和与其余概率再排序。

⑥ 如此反复重复n-2次，得到只剩两个概率序列。

⑦ 以二进制码元(0.1)赋值，构成哈夫曼码字。

编码结束。

哈夫曼码字长度和信息符号出现概率大小次序正好相反，即大概信息符号分配码字长度短，小概率信息符号分配码字长度长。

C、哈夫曼编码的特点(1)哈夫曼编码的构造顺序明确，但码不是唯一的(因以大赋1还是小的赋1而异；(2)哈夫曼编码的字长参差不齐，硬件实现不方便；(3)只有在概率分布很不均匀时，哈夫曼编码才有显著的效果，而在信源分布均匀时，一般不使用哈夫曼编码。

二：程序源代码：#define MAXVALUE 10000#define MAXLEAF 30#define MAXNODE 59#define MAXBIT 10#define LENTH 30#include "stdio.h"#include<iostream>typedef struct{float gailv;int flag;int parent;int lchild;int rchild;char ch;int t;}HNodeType;typedef struct{int bit[MAXBIT];int start;}HCodeType;typedef struct{float gailv;char letter;}mytype; /*it's the type of data save in file*/typedef struct filehuff{int count;mytype mydata[MAXLEAF];filehuff(){count=0; };};filehuff filedata;char code[MAXVALUE];HNodeType HuffNode[MAXNODE];void savetofile(){FILE *fp;if((fp=fopen("datafile.txt","wb"))==NULL){printf("打开失败 ....");return;}if(fwrite(&filedata,sizeof(filedata),1,fp)!=1) printf("写入文件失败 ....");fclose(fp);}void openfile(){ FILE *fp;if((fp=fopen("datafile.txt","rb"))==NULL){return;}fread(&filedata,sizeof(filedata),1,fp);}void translate(){char c;int i,j,k=0,m,n=0;printf("请输入你想要译码的二进制序列 ");printf("\n");getchar();scanf("%c",&c);for(i=0;(i<MAXVALUE)&&(c=='1'||c=='0');i++){ code[i]=c;scanf("%c",&c);}printf("对应的信源符号为：");for(j=0;j<=MAXVALUE&&HuffNode[j].parent!=-1;j++) m=j+1;for(j=0,k=m;j<=i;j++){if(code[j]=='0'){n=HuffNode[k].lchild;if(n==-1){printf("%c",HuffNode[k].ch);k=m;j--;continue;}k=n;}else{n=HuffNode[k].rchild;if(n==-1){printf("%c",HuffNode[k].ch);k=m;j--;continue;}k=n;}}}void Huffman(){HCodeType HuffCode[MAXLEAF],cd;int i,j,m1,m2,x1,x2,c,p,m;if(filedata.count==0){ printf("\n输入信源符号总数 : ");scanf("%d",&m);filedata.count=m;for(i=0;i<2*m-1;i++){ HuffNode[i].gailv=0;HuffNode[i].parent=-1;HuffNode[i].flag=0;HuffNode[i].lchild=-1;HuffNode[i].rchild=-1;HuffNode[i].ch='a';}for(i=0;i<m;i++){ printf("请输入 (概率,信源符号):");scanf("%f %c",&HuffNode[i].gailv,&HuffNode[i].ch); filedata.mydata[i].gailv=HuffNode[i].gailv; filedata.mydata[i].letter=HuffNode[i].ch;savetofile();}}else{ m=filedata.count;for(i=0;i<2*m-1;i++){ HuffNode[i].gailv=0;HuffNode[i].parent=-1;HuffNode[i].flag=0;HuffNode[i].lchild=-1;HuffNode[i].rchild=-1;HuffNode[i].ch=3;}for(i=0;i<m;i++){ HuffNode[i].gailv=filedata.mydata[i].gailv;HuffNode[i].ch=filedata.mydata[i].letter;}}for(i=0;i<m-1;i++){ m1=m2=MAXVALUE;x1=x2=0;for(j=0;j<m+i;j++){ if(HuffNode[j].gailv<m1&&HuffNode[j].flag==0){ m2=m1;x2=x1;m1=HuffNode[j].gailv;x1=j;}else if(HuffNode[j].gailv<m2&&HuffNode[j].flag==0){ m2=HuffNode[j].gailv;x2=j;}}HuffNode[x1].parent=m+i;HuffNode[x2].parent=m+i;HuffNode[x1].flag=1;HuffNode[x2].flag=1;HuffNode[m+i].gailv=HuffNode[x1].gailv+HuffNode[x2].gailv;HuffNode[m+i].lchild=x1;HuffNode[m+i].rchild=x2;}for(i=0;i<m;i++){ cd.start=m-1;c=i;p=HuffNode[c].parent;while(p!=-1){ if(HuffNode[p].lchild==c)cd.bit[cd.start]=0;else cd.bit[cd.start]=1;cd.start--;c=p;p=HuffNode[c].parent;}for(j=cd.start+1;j<m;j++)HuffCode[i].bit[j]=cd.bit[j]; HuffCode[i].start=cd.start;}printf("对应的赫夫曼编码如下：");printf("\n信源符号概率编码\n");for(i=0;i<m;i++){printf("%c %f ",HuffNode[i].ch,HuffNode[i].gailv); for(j=HuffCode[i].start+1;j<m;j++)printf("%d",HuffCode[i].bit[j]);printf("\n");}printf("按任意键继续......\n");}main(){char yn;printf("\n");printf("\n");printf(" 信息论与编码实验 \n");openfile();Huffman();for(;;){printf("\n是否想要把序列译码为信源符号 ?: (输入 y or n) "); scanf("%c",&yn);if(yn=='y'||yn=='Y')translate();elsebreak;}return 0;system("pause");}三：实验分析编码实例如下：由图中可以看出，符合基本的赫夫曼编码的原理，概率大的用短码，概率小的用长码。