霍夫曼信源编码实验报告

实验二：Huffman 编码的实现实验学时：3实验类型：（演示、验证、综合、√设计、研究）实验要求：（√必修、选修）一、 实验目的 理解和掌握huffman 编码的基本原理和方法，实现对信源符号的huffman 编码。

二、 实验内容1. 理解和掌握huffman 编码的基本原理和方法2. 通过MATLAB 编程实现对单信源符号的huffma 编码3. 计算信源的信息熵、平均码长以及编码效率三、 实验原理1．Huffman 编码按信源符号出现的概率而编码，其平均码长最短，所以是最优码。

2．无失真信源编码定理：对于熵为H (X )的离散无记忆的平稳信源，必存在一种无失真编码，使每符号的平均码长满足不等式：()()1log log H S H S L r r≤<+ 3．二元Huffman 编码：若将编码设计为长度不等的二进制编码，即让待传字符串中出现概率大的字符采用尽可能短的码字，而把长的码字分配给概率小的信源符号。

构造方法如下：（a ） 将信源概率分布按大小以递减次序排列；合并两概率最小者，得到新信源；并分配0/1符号。

（b ） 新信源若包含两个以上符号返回（a ），否则到（c ）。

（c ） 从最后一级向前按顺序写出每信源符号所对应的码字。

四、 实验数据源1．12345[]:0.40.20.20.10.1s s s s s X P ⎧⋅⎨⎩:{0,1}X2．123456[]:0.240.200.180.160.140.08s s s s s s X P ⎧⋅⎨⎩:{0,1}X 五、实验组织运行要求以学生自主训练为主的开放模式组织教学六、实验条件（1）微机（2）MATLAB 编程工具七、实验原理七、实验代码clear% S=[0.4,0.2,0.2,0.1,0.1]; S=[0.24,0.20,0.18,0.16,0.14,0.08];% S=[0.20,0.19,0.18,0.17,0.15,0.10,0.01];S0=sort(S); %将序列进行升序排列S1=fliplr(S0); %将升序排列的概率进行左右翻转得到降序排列t=length(S1); %得到信源符号的个数coding_table=[S1']; %创建编码过程表,第一列for i=1:length(S1)-1s=coding_table(t,i)+coding_table(t-1,i); %最小两个值相加S1(t-1)=s;S1(t)=0;t=t-1;S1=fliplr(sort(S1)); %进行重新降序排列coding_table=[coding_table,S1']; %排序结果加入到编码过程表for j=1:length(S1)if s==S1(j)b(i)=j; %记录两个最小概率相加得到的值在新排序中的位置。

图像Huffman编码实验报告
1 实验目的
(1)熟练掌握Huffman编码的方法；
(2)理解无失真信源编码和限失真编码方法在实际图像信源编码应用中的差异。

2 实验内容与步骤
(1)针对“image1.bmp”、“image2.bmp”和“image3.bmp”进行灰度频率统计（即计算图像灰度直方图），在此基础上添加函数代码构造Huffman码表，针对图像数据进行Huffman编码，观察和分析不同图像信源的平均码长、编码效率和压缩比。

(2)针对任意一幅图像，得到其差分图像，对差分图像统计灰度频率，进行Huffman编码，计算平均码长、编码效率和压缩比，并与（1）对比。

3 实验结果
（1）对图像数据进行Huffman 编码，得到不同图像信源的平均码长、编码效率和压缩比如下：
image1：5.960179 0.994678 1.342242
image2：4.443604 0.992368 1.800341
image3：6.733643 0.996281 1.188064
(2)对lenna.bmp 进行Huffman 编码，得到其平均码长、编码效率和压缩比分别是：
5.294220 0.994358 1.511082。

一、实验目的1. 理解霍夫曼编码的基本原理和算法流程。

2. 掌握霍夫曼编码的构建过程和编码方法。

3. 通过实验验证霍夫曼编码在数据压缩方面的效果。

4. 提高编程能力和数据结构应用能力。

二、实验环境1. 操作系统：Windows 102. 编程语言：C++3. 开发工具：Visual Studio 2019三、实验原理霍夫曼编码是一种基于字符出现频率进行编码的数据压缩方法。

其基本原理如下：1. 对字符进行统计，得到每个字符出现的频率。

2. 根据频率对字符进行排序，频率高的字符排在前面。

3. 构建霍夫曼树，将频率高的字符放在树的左侧，频率低的字符放在树的右侧。

4. 从树根到叶子节点，为每个字符分配一个二进制编码，频率高的字符用较短的编码表示，频率低的字符用较长的编码表示。

四、实验步骤1. 定义一个结构体HuffmanNode，用于存储字符及其频率。

2. 实现一个函数用于统计字符频率。

3. 实现一个函数用于构建霍夫曼树。

4. 实现一个函数用于生成霍夫曼编码。

5. 实现一个函数用于解码霍夫曼编码。

6. 编写主函数，进行实验验证。

五、实验过程1. 定义结构体HuffmanNode，用于存储字符及其频率。

```cppstruct HuffmanNode {char ch;int weight;HuffmanNode lchild, rchild;};```2. 实现一个函数用于统计字符频率。

```cppvoid StatFrequency(char str, int freq) {int length = strlen(str);for (int i = 0; i < 256; ++i) {freq[i] = 0;}for (int i = 0; i < length; ++i) {freq[(int)str[i]]++;}}```3. 实现一个函数用于构建霍夫曼树。

```cppHuffmanNode CreateHuffmanTree(int freq, int length) {HuffmanNode nodes = new HuffmanNode[length + 1];for (int i = 0; i < length; ++i) {nodes[i].ch = 'a' + i;nodes[i].weight = freq[i];nodes[i].lchild = nullptr;nodes[i].rchild = nullptr;}for (int i = length; i < length + 1; ++i) {nodes[i].ch = '\0';nodes[i].weight = 0;nodes[i].lchild = nullptr;nodes[i].rchild = nullptr;}for (int i = 0; i < length - 1; ++i) {HuffmanNode minNode1 = &nodes[0];HuffmanNode minNode2 = &nodes[1];for (int j = 0; j < length + 1; ++j) {if (nodes[j].weight < minNode1->weight) {minNode2 = minNode1;minNode1 = &nodes[j];} else if (nodes[j].weight < minNode2->weight && nodes[j].weight > minNode1->weight) {minNode2 = &nodes[j];}}nodes[i].weight = minNode1->weight + minNode2->weight;nodes[i].lchild = minNode1;nodes[i].rchild = minNode2;minNode1->parent = &nodes[i];minNode2->parent = &nodes[i];}return &nodes[length - 1];}```4. 实现一个函数用于生成霍夫曼编码。

实验三信源编码实验一、实验目的：1、掌握哈夫曼编码的Matlab实现方法。

2、掌握VC++读取信源数据的方法。

3、运行编译好的霍夫曼编码、算术编码、游程编码编码程序，比较霍夫曼编码、算术编码、游程编码编码的编码效果二、实验内容与步骤1、Huffman编码实验1）编写计算信息熵的M文件参考程序：function h=entropy(p)%H=ENTROPY(P)返回概率矢% 量P的熵函数if length (find(p<0))~=0error('Not a prob.vector,negative component(s)')endif abs (sum(p)-1)>10e-10error ('Not a prob.vector,components do not add up to 1') endh=sum(-p.*log2(p));求信源X=[x1,x2,…,x9]，其相应的概率为p=[0.2,0.15,0.13,0.12,0.1,0.09,0.08,0.07,0.06];利用编写的程序计算信息熵，并记录数值。

2）编写程序实现Huffman编码编写实现Huffman编码的M文件，编译后运行，验证程序的正确性并记录编码结果。

参考程序：function [h,l]=huffman(p);%HUFFMAN 哈夫曼编码生成器% [h,l]=huffman(p),返回哈夫曼编码矩阵H及码字长度if length (find (p<0))~=0,erro('Not a prob.vector,negative component(s)')endif abs(sum(p)-1)>10e-10,error('Not a prob.vector,components do not add up to 1') endn=length(p);q=p;m=zeros(n-1,n);for i=1:n-1[q,l]=sort(q);m(i,:)=[l(1:n-i+1),zeros(1,i-1)];q=[q(1)+q(2),q(3:n),1];endfor i=1:n-1c(i,:)=blanks(n*n);endc(n-1,n)='0';c(n-1,2*n)='1';for i=2:n-1c(n-i,1:n-1)=c(n-i+1,n*(find(m(n-i+1,:)==1))-(n-2):n*(fi nd(m(n-i+1,:)==1)));c(n-i,n)='0';c(n-i,n+1:2*n-1)=c(n-i,1:n-1);c(n-i,2*n)='1';for j=1:i-1c(n-i,(j+1)*n+1:(j+2)*n)=c(n-i+1,n*(find(m(n-i+1,:)==j+1 )-1)+1:n*find(m(n-i+1,:)==j+1));endendfor i=1:nh(i,1:n)=c(1,n*(find(m(1,:)==i)-1)+1:find(m(1,:)==i)*n); ll(i)=length(find(abs(h(i,:))~=32));endl=sum(p.*ll);在命令行后输入》p=[0.1 0.3 0.05 0.09 0.21 0.25];》[H,l]=huffman(p)记录运行结果，并说明编码结果是否正确，计算编码效率。

实验一一、实验背景*哈夫曼编码(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四、实验补充说明解码时，以回车键结束输入电文。

Huffman编解码实验报告⽂本⽂件的⼆进制预统计Huffman编解码⼀、实验⽬的(1) 熟悉Huffman编解码算法；(2) 理解Huffman编码的最佳性。

⼆、实验内容1、编程思想霍夫曼（Huffman）编码是1952年为⽂本⽂件⽽建⽴，是⼀种统计编码。

属于⽆损压缩编码。

霍夫曼编码的码长是变化的，对于出现频率⾼的信息，编码的长度较短；⽽对于出现频率低的信息，编码长度较长。

这样，处理全部信息的总码长⼀定⼩于实际信息的符号长度。

计算机编程实现时，⾸先统计带编码的⽂本⽂件中各个字符出现的概率，然后将概率作为节点的权值构建huffman树。

编码时从叶⼦节点出发，如果这个节点在左⼦树上，则编码0，否则编码1，直到根节点为⽌，所得到的01序列即为该叶⼦节点的编码。

所有叶⼦节点的编码构成⼀个码本。

有两种译码⽅法：(1)按位读⼊码字，从已建好的Huffman树的根节点开始，若码字为“0”，则跳到左⼦树，若为“1”则跳到右⼦树，直到叶⼦结点为⽌，输出叶⼦接点所表⽰的符号。

（2）由于Huffman编码是唯⼀码，还有另⼀种译码⽅法，每读⼊⼀位编码就去码本中去匹配相应的码字，若匹配不成功，则继续读⼊下⼀个编码，直到匹配成功为⽌。

显然前⼀种⽅法⽐较简便，本程序采⽤便是该⽅法。

2、程序流程图3、编程实现本实验采⽤⽤C 语⾔程序语⾔，VC++ 6.0编程环境。

(1)数据结构构造存放符号及其权值的存储结构如下 typedef struct {unsigned char symbol; //符号的ASCII 码值 int sweight; //权值}syml_weit;syml_weit *sw;构造huffman 树存储结构如下：typedef struct {int weit; //权值int lchd; //左孩⼦地址 int rchd; //右孩⼦地址 int part; //双亲地址 }hufmtree;hufmtree *htree;(2)函数本程序共包含5个函数：⼀个主函数：void main()， 4个⼦函数：void CountWeight(unsigned char *DataBuf,int FileLen); void BuildTree();void HufmCode(unsigned char *DataBuf,int FileLen); void HufmDCode(unsigned char *CDataBuf,int CDataLen); 其功能分别CountWeight----计算⽂本⽂件中各符号的权值； BuildTree-------构建Huffman 树，形成码本； HufmCode---------对⽂本⽂件进⾏编码； HufmDCode-------进⾏译码。

1. 了解信源编码的基本原理和重要性；2. 掌握霍夫曼编码和算术编码的硬件实现方法；3. 分析信源编码在实际应用中的性能和优势；4. 通过实验，提高动手能力和理论联系实际的能力。

二、实验原理信源编码是一种将信源信息进行压缩的过程，其目的是减小数据传输和存储过程中的数据量，提高传输效率。

信源编码主要有两种方法：霍夫曼编码和算术编码。

1. 霍夫曼编码：根据信源中各个符号出现的概率，构建一棵霍夫曼树，将出现概率高的符号赋予较短的码字，出现概率低的符号赋予较长的码字。

霍夫曼编码具有无失真编码的特点，编码效率较高。

2. 算术编码：将信源中的符号按照一定的概率进行编码，码字长度不固定。

算术编码具有无失真编码的特点，编码效率较高，但实现较为复杂。

三、实验环境1. 硬件环境：FPGA开发板、信号发生器、示波器、数字存储示波器等；2. 软件环境：Quartus II、MATLAB、Simulink等。

四、实验内容1. 霍夫曼编码硬件实现（1）设计霍夫曼编码器：根据信源概率分布构建霍夫曼树，生成码字映射表；（2）输入信源数据，通过霍夫曼编码器进行编码；（3）输出编码后的码字，并验证码字长度是否符合霍夫曼编码规则。

2. 算术编码硬件实现（1）设计算术编码器：根据信源概率分布，生成码字映射表；（2）输入信源数据，通过算术编码器进行编码；（3）输出编码后的码字，并验证码字长度是否符合算术编码规则。

1. 根据信源概率分布，设计霍夫曼编码器和算术编码器；2. 在FPGA开发板上进行硬件编程，实现信源编码算法；3. 使用信号发生器产生信源数据，通过示波器观察编码后的码字；4. 使用数字存储示波器记录编码后的码字，分析编码效率；5. 对比霍夫曼编码和算术编码的编码效率，分析两种编码方法的优缺点。

六、实验结果与分析1. 霍夫曼编码：通过实验，验证了霍夫曼编码器能够根据信源概率分布生成码字映射表，编码后的码字长度符合霍夫曼编码规则。

计算机与信息工程学院综合性实验报告一、实验目的根据霍夫曼编码的原理，用MATLAB设计进行霍夫曼编码的程序，并得出正确的结果。

二、实验仪器或设备1、一台计算机。

2、MATLAB r2013a。

三、二元霍夫曼编码原理1、将信源消息符号按其出现的概率大小依次排列，p1>p2>…>p q2、取两个概率最小的字母分别配以0和1两个码元，并将这两个概率相加作为一个新字母的概率，从而得到只包含q-1个符号的新信源S1。

3、对重排后的缩减信源S1重新以递减次序排序，两个概率最小符号重复步骤(2)的过程。

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

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

四、霍夫曼编码实现程序function [outnum]=lml_huffman(a)%主程序，输入一组概率，输出此组概率的霍夫曼编码%a：一组概率值，如a=[0.2 0.3 0.1 0.4]等%outnum：输出的霍夫曼码，以cell中的字符数组表示if sum(a)~=1warning('输入概率之和不为“1”，但程序仍将继续运行')end[cho,sequ,i,l]=probality(a);global lmlcode %用于输出霍夫曼码，定义为cell型global cellnum %用于编码的累加计算cellnum=1;lmlcode=cell(l,1);j=1; %第一部分add_num=char;[l_add]=addnum(add_num,i,j,l);[output,m]=disgress(sequ,i,j,l,l_add);dealnum(output,m); %在全局变量中输出霍夫曼码j=2; %第二部分[l_add]=addnum(add_num,i,j,l);[output,n]=disgress(sequ,i,j,l,l_add);dealnum(output,n);[outnum]=comset(lmlcode,cho(1,:));%将概率和编码进行关联function [output]=addnum(input,i,j,l)%对概率矩阵中每一行最后两个不为0的数进行编码，即在某个编码后添加0,1或空%输出：% input：输入的某个未完成的编码% (i,j):当前检索目标在sequ矩阵中的位置% l:sequ矩阵的列数%PS: sequ矩阵在此函数中未用到%PS：此函数为编码第一步if j==(l-i)output=[input '0'];else if j==(l-i+1)output=[input '1'];elseoutput=input;endendfunction [ecode]=comset(code,pro)%将概率和编码进行关联%code：已编成的霍夫曼码%pro：输入的一组概率%ecode：最终完成的码l=length(code);ecode=cell(l,2);for i=1:llang(i)=length(code{i});end[a,b]=sort(lang);for i=1:lecode{i,1}=code{b(i)};ecode{i,2}=pro(i);endfunction [final,a]=dealnum(imput,m)%整理并在全局变量中输出已完成的霍夫曼码%输入： imput：程序运算后的生成cell型矩阵% m：标识数%输出： final：整理后的霍夫曼码% a：标识数global lmlcodeglobal cellnumif m==1lmlcode{cellnum}=imput;cellnum=cellnum+1;final='';a='';else if m==2[final1,a1]=dealnum(imput{1,1},imput{1,2});[final2,a2]=dealnum(imput{2,1},imput{2,2});[final3,a3]=dealnum(final1,a1);[final4,a4]=dealnum(final2,a2);final=[final3 final4];a=[a3 a4];elsefinal=imput;a=m;endendfunction [outnum,p]=findsumother(sequ,i,j,l,add_num)%当前检索目标在sequ(i,j)处为非1时的处理程序，即跳转到下一级进行整理%输入： sequ:概率转移矩阵% (i,j):当前检索目标在sequ矩阵中的位置% l:sequ矩阵的列数% add_num：当前进行的编码%输出：（与disgress类同）% outnum：进行霍夫曼编码，用cell型表示% p：标识数j=l-i+2-sequ(i,j);i=i-1;[add_num1]=addnum(add_num,i,j,l);[outnum,p]=disgress(sequ,i,j,l,add_num1);function [outnum1,outnum2,p,q]=findsumis1(sequ,i,j,l,add_num)%当前检索目标在sequ(i,j)处为1时的处理程序，%即对下一级的最小两概率进行求和移位编码整理%输入： sequ:概率转移% (i,j):当前检索目标在sequ矩阵中的位置% l:sequ矩阵的列数% add_num：当前进行的编码%输出：（与disgress类同）% outnum1&[outnum2：进行霍夫曼编码，用cell型表示% p&q：标识数i=i-1;j1=l-i;j2=l-i+1;[add_num1]=addnum(add_num,i,j1,l);[outnum1,p]=disgress(sequ,i,j1,l,add_num1);[add_num2]=addnum(add_num,i,j2,l);[outnum2,q]=disgress(sequ,i,j2,l,add_num2);function [output,m]=disgress(sequ,i,j,l,add_num)%当前检索目标，累加数，输出下一级霍夫曼码及其个数，此函数被调用次数最多%输入：sequ：概率转移矩阵% (i,j)：当前检索目标在sequ矩阵中的位置% l：sequ矩阵的列数% add_num：当前进行的编码%输出：output：进行霍夫曼编码，用cell型表示% m：标识数%PS：此函数为编码第二步if i~=1if sequ(i,j)==1[output1,output2,p,q]=findsumis1(sequ,i,j,l,add_num);output=cell(2);output{1,1}=output1;output{1,2}=p;output{2,1}=output2;output{2,2}=q;m=2;else if sequ(i,j)~=1[output1,p]=findsumother(sequ,i,j,l,add_num);output=output1;m=p;endendelseoutput=add_num;m=1;end五、实验程序实现方法演示若在command window中输入的概率数组为p=[0.1 0.15 0.20 0.25 0.30]使用子函数[output,sequ,i,j]=probality(p)对此组概率进行预处理，处理结果如下图所示：图5.1 概率数据处理过程简图图5.2 对图1中数据的转移方式标示图图2标明了对图1中各数据的位置转移过程。

一、问题描述1. 实验题目：huffman编解码2. 基本要求：初始化（I nitialization）。

从终端读入字符集大小n，以及n个字符和n个权值，建立Huffman 树，并将它存入hfmTree 中。

编码（E ncoding）。

利用已经建好的Huffman树（如果不在内存，则应从文件hfmTree 中读取），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。

解码（D ecoding）。

利用已经建立好的Huffman树将文件CodeFile中的代码进行解码，结果存入TextFile中。

打印代码文件（Print）。

将文件CodeFile以紧凑的格式显示在终端上，每行 50 个代码。

同时将此字符形式的编码文件写入文件CodePrint中。

打印Huffman树（T ree Printing）。

将已经在内存中的Huffman树以直观的形式（树或者凹入的形式）显示在终端上，同时将此字符形式的Huffman 树写入文件TreePrint中。

3. 测试数据：用下表给出的字符集和频度的实际统计数据建立Huffman树，并对以下报文进行编字符集大小 n，n个字符和 n个权值均从终端读入，初始化后的huffman树存储在hfmTree文件中，待编码文件为ToBeTran,编码结果以文本的方式存储在文件CodeFile中，解码文件存在TextFile中,打印的编码和赫夫曼树分别存储在CodePrint和TreePrint文件中。

用户界面可以设计为“菜单”方式：显示上述功能符号，再加上一个退出功能“Q”，表示退出（quit）。

用户键入一个选择功能符，此功能执行完毕后再显示此菜单，直至某次用户选择了Q为止。

二、需求分析1. 本程序可以根据输入字符集和频度建立huffman树并且对给定文本进行编解码，还可以直接读入建立好的huffman树再对给定文本编解码，打印编码、解码结果、表格形式及树形的huffman树。

第1篇一、实验目的1. 理解霍夫曼编码的基本原理和实现方法。

2. 掌握霍夫曼编码在数据压缩中的应用。

3. 通过实验，加深对数据压缩技术的理解。

二、实验环境1. 操作系统：Windows 102. 编程语言：C++3. 开发环境：Visual Studio 20194. 数据源：文本文件三、实验原理霍夫曼编码是一种常用的数据压缩算法，适用于无损数据压缩。

它通过使用变长编码表对数据进行编码，频率高的数据项使用短编码，频率低的数据项使用长编码。

霍夫曼编码的核心是构建一棵霍夫曼树，该树是一种最优二叉树，用于表示编码规则。

霍夫曼编码的步骤如下：1. 统计数据源中每个字符的出现频率。

2. 根据字符频率构建一棵最优二叉树，频率高的字符位于树的上层，频率低的字符位于树下层。

3. 根据最优二叉树生成编码规则，频率高的字符分配较短的编码，频率低的字符分配较长的编码。

4. 使用编码规则对数据进行编码，生成压缩后的数据。

5. 在解码过程中，根据编码规则恢复原始数据。

四、实验步骤1. 读取文本文件，统计每个字符的出现频率。

2. 根据字符频率构建最优二叉树。

3. 根据最优二叉树生成编码规则。

4. 使用编码规则对数据进行编码，生成压缩后的数据。

5. 将压缩后的数据写入文件。

6. 读取压缩后的数据，根据编码规则进行解码，恢复原始数据。

7. 比较原始数据和恢复后的数据，验证压缩和解码的正确性。

五、实验结果与分析1. 实验数据实验中，我们使用了一个包含10000个字符的文本文件作为数据源。

在统计字符频率时，我们发现字符“e”的出现频率最高，为2621次，而字符“z”的出现频率最低，为4次。

2. 实验结果根据实验数据，我们构建了最优二叉树，并生成了编码规则。

使用编码规则对数据源进行编码，压缩后的数据长度为7800个字符。

将压缩后的数据写入文件，文件大小为78KB。

接下来，我们读取压缩后的数据，根据编码规则进行解码，恢复原始数据。

比较原始数据和恢复后的数据，发现两者完全一致，验证了压缩和解码的正确性。

编码理论实验报告实验一霍夫曼编码中信息熵及编码效率的实验实验名称实验一霍夫曼编码中信息熵及编码效率的实验一、实验目的1. 掌握霍夫曼编码中信息熵的定义、性质和计算;2. 掌握霍夫曼编码中平均码字长度的定义和计算;3( 掌握霍夫曼编码中编码效率的定义和计算;4. 正确使用C语言实现霍夫曼编码中信息熵、平均码长和编码效率的求取。

二、实验内容1. 熟练列出霍夫曼编码中信息熵、平均码长和编码效率各自的计算公式;2. 正确使用C语言实现计算霍夫曼编码中信息熵、平均码长和编码效率的程序，并在Visual C++环境中验证。

三、实验原理1. 霍夫曼编码的基本原理按照概率大小顺序排列信源符号，并设法按逆顺序分配码字字长，使编码的码字为可辨识的。

2. 平均码长:L=?p(s)*l(单位为:码符号/信源符号) ii其中，p(s)为信源s在q个信源中出现的概率，l为信源s的二进制霍夫曼iiii编码。

3. 信息熵:H(S)=- ?p(s) *log p(s) (单位为:比特/信源符号) i2i其中，p(s)为信源s在q个信源中出现的概率。

ii4. 编码效率:η= H(S)/ L其中，H(S)为信息熵，L为平均码长。

四、实验步骤:1. Huffman编码示例如下图:信源符号概率信源缩减过程编码码长00 0 S1 0.4 0.4 0.4 0.6 00 2 1 0000 1 S2 0.2 0.2 0.4 0.4 10 2 01 1010 01 S3 0.2 0.2 0.2 11 2 11010 11 S4 0.15 0.2 010 3011 S5 0.05 011 3 2. 根据Huffman编码的例子，用C语言完成计算霍夫曼编码中信息熵的程序的编写，并在Visual C++环境中验证;3. 根据Huffman编码的例子，用C语言完成计算霍夫曼编码中平均码长的程序的编写，并在Visual C++环境中验证;4. 根据Huffman编码的例子，用C语言完成计算霍夫曼编码中编码效率的程序的编写，并在Visual C++环境中验证;实验程序:/*********** 霍夫曼编码信息熵、平均码长及编码效率的计算 ************ //按照实验步骤的要求完成程序，正确计算霍夫曼编码的信息熵、 //平均码长以及编码效率，并通过printf函数将三者的计算结果 //打印出来#include<stdio.h>#include<string.h>#include<math.h>#define CH_Num 5 //信源符号个数//主函数void main(){//编程1:定义double型数组gailv存放各信源符号出现的概率double gailv[CH_Num]={0.4,0.2,0.2,0.15,0.05};//编程2:定义int型数组code_len存放各信源符号的霍夫曼编码int code_len[CH_Num]={2,2,2,3,3};//编程3:定义double型变量aver_Len、Hs和code_ratio，分别//对应信息熵、平均码长及编码效率，并初始化为0double aver_Len=0,Hs=0,code_ratio=0;int i;//编程4:利用for循环计算平均码长aver_Lenfor(i=0;i<CH_Num;i++)aver_Len+=gailv[i]*code_len[i];//编程5:利用for循环计算信息熵Hsfor(i=0;i<CH_Num;++i)Hs+=-(gailv[i]*(log(gailv[i])/log(2)));//编程6:计算编码效率code_ratiocode_ratio=Hs/aver_Len;//编程7:利用三条printf语句分别打印平均码长、信息熵和编码效率printf("平均码长=%lf 比特/信源符号\n",aver_Len);printf("信源熵=%lf 码符号/信源符号\n",Hs);printf("编码效率=%lf\n",code_ratio); }运行结果如下图:实验心得:通过本次试验加深了对霍夫曼编码的基本原理的理解以及计算公式的记忆。

实验三Huffman编码专业：通信工程学号：姓名：一实验目的1 通过本实验实现信源编码——Huffman编码2 编写M文件实现，掌握Huffman编码方法实验要求1 了解matlab中M文件的编辑、调试过程2 编写程序实现Huffman编码算法二实验步骤1 输入Huffman编码程序2 运行程序，按照提示输入相应信息，并记录输入信息，及运行结果。

注：观察结果方法：data(1).Code显示a1的编码，同理显示data(2).Code，a2的编码结果。

三程序的流程图四Huffman编码程序clearN=input('请输入信源符号的个数：') ;for i=1:N%data(1).name=input('请输入各信源符号的名称：');data(i).p=input('请输入各信源符号发生的概率：');endfor i=1:Npp(i)=data(i).p;data(i).imap=i; %各符号在编码过程中的指针data(i).Code=''; %各符号的编码结果endfor j = 1:N % N——信源符号的个数for i = 1:N - jif (pp(i) > pp(i + 1))fT = pp(i);pp(i) = pp(i + 1);pp(i + 1) = fT;for k = 1:Nif data(k).imap == idata(k).imap = i + 1;elseif data(k).imap == i + 1data(k).imap = i;endendendendendp=pp;%%%%%%%%%%%%%%%%%%%%%%// 计算哈夫曼编码表%// 开始编码for i=1:N-1for k = 1:Nif data(k).imap== idata(k).Code = strcat('1',data(k).Code);elseif (data(k).imap== i + 1)data(k).Code = strcat('0',data(k).Code);endendp(i + 1) = p(i + 1)+p(i);for k = 1:Nif (data(k).imap == i)data(k).imap = i + 1;endendfor j = i + 1:N-1if p(j) >p(j + 1)fT =p(j);p(j) = p(j + 1);p(j + 1) = fT;for k = 1:Nif (data(k).imap == j)data(k).imap = j + 1;elseif (data(k).imap == j + 1)data(k).imap = j;endendendendend五实验小结本实验基于静态的Huffman编码，实现了对简单字符串的Huffman编码与解码。

实验名称 实验二 信源编码--------霍夫曼编码一、 实验目的1. 掌握信息熵的定义、性质和计算；2. 掌握平均码字长度和编码效率的计算；3． 掌握霍夫曼编码的原理；4． 熟练掌握二进制霍夫曼码的编码步骤；5． 正确使用C 语言实现霍夫曼编码。

二、实验内容1. 熟练画出霍夫曼编码图，正确求出字符串的二进制霍夫曼编码；2. 用C 语言正确编程，实现霍夫曼编码、解码，并在Visual C++环境中验证。

三、 实验原理1. 霍夫曼编码的基本原理按照概率大小顺序排列信源符号，并设法按逆顺序分配码字字长，使编码的码字为可辨识的。

2. 平均码长：L=∑p(s i )*l i （单位为：码符号/信源符号）其中，p(s i )为信源s i 在q 个信源中出现的概率，l i 为信源s i 的二进制霍夫曼编码。

3. 信息熵：H(S)=- ∑p(s i ) *log 2 p(s i ) （单位为：比特/信源符号）其中，p(s i )为信源s i 在q 个信源中出现的概率。

4. 编码效率：η= H(S)/ L其中，H(S)为信息熵，L 为平均码长。

四、 实验步骤：1. 将q 个信源符号按概率分布的大小，以递减次序排列起来，设 )()()(21q x p x p x p ≥≥≥2. 用“0”和“1”码符号分别代表概率最小的两个信源符号，并将这两个概率最小的符号合并成一个符号，合并的符号概率为两个符号概率之和，从而得到只包含q-1个符号的新信源，称为缩减信源。

3. 把缩减信源的符号仍旧按概率大小以递减次序排列，再将其概率最小的两个信源符号分别用“0”和“1”表示，并将其合并成一个符号，概率为两符号概率之和，这样又形成了q – 2 个符号的缩减信源。

4. 依此继续下去，直至信源只剩下两个符号为止。

将这最后两个信源符号分别用“0”和“1”表示。

5. 然后从最后一级缩减信源开始，向前返回，就得出各信源符号所对应的码符号序列，即对应的码字。

实验二 信源编码--------霍夫曼编码1. 掌握信息熵的定义、性质和计算；2. 掌握平均码字长度和编码效率的计算；3． 掌握霍夫曼编码的原理；4． 熟练掌握二进制霍夫曼码的编码步骤；5． 正确使用C 语言实现霍夫曼编码。

二、实验内容1. 熟练画出霍夫曼编码图，正确求出字符串的二进制霍夫曼编码；2. 用C 语言正确编程，实现霍夫曼编码、解码，并在Visual C++环境中验证。

三、 实验原理1. 霍夫曼编码的基本原理按照概率大小顺序排列信源符号，并设法按逆顺序分配码字字长，使编码的码字为可辨识的。

2. 平均码长：L=∑p(s i )*l i （单位为：码符号/信源符号）其中，p(s i )为信源s i 在q 个信源中出现的概率，l i 为信源s i 的二进制霍夫曼编码。

3. 信息熵：H(S)=- ∑p(s i ) *log 2 p(s i ) （单位为：比特/信源符号）其中，p(s i )为信源s i 在q 个信源中出现的概率。

4. 编码效率：η= H(S)/ L其中，H(S)为信息熵，L 为平均码长。

四、 实验步骤：1. 将q 个信源符号按概率分布的大小，以递减次序排列起来，设)()()(21q x p x p x p ≥≥≥2. 用“0”和“1”码符号分别代表概率最小的两个信源符号，并将这两个概率最小的符号合并成一个符号，合并的符号概率为两个符号概率之和，从而得到只包含q-1个符号的新信源，称为缩减信源。

3. 把缩减信源的符号仍旧按概率大小以递减次序排列，再将其概率最小的两个信源符号分别用“0”和“1”表示，并将其合并成一个符号，概率为两符号概率之和，这样又形成了 q – 2 个符号的缩减信源。

4. 依此继续下去，直至信源只剩下两个符号为止。

将这最后两个信源符号分别用“0”和“1”表示。

5. 然后从最后一级缩减信源开始，向前返回，就得出各信源符号所对应的码符号序列，即对应的码字。

/****************** 霍夫曼编码 **********************///2010-3-31：注释//程序共有8处需要补充#include<stdio.h>#include<string.h>#include<math.h>#define n 100#define m 2*n-1// 码结点的存储结构typedef struct{char ch;char bits[9];int len;}CodeNode;typedef CodeNode HuffmanCode[n+1];// 树结点的存储结构typedef struct{int weight;int lchild,rchild,parent;}HTNode;typedef HTNode HuffmanTree[m+1];int num;// 挑选权值最小的两个结点void select(HuffmanTree HT, int k, int &s1, int &s2){int i,j;int minl=32767;for(i=1;i<=k;i++)if(HT[i].weight<minl&&HT[i].parent==0){j=i;minl=HT[i].weight;}s1=j;minl=32767;for(i=1;i<=k;i++)if(HT[i].weight<minl&&HT[i].parent==0&&i!=s1){j=i;minl=HT[i].weight;}s2=j;}// 统计输入字符串st中出现的字符种类和各个字符在该字符串中出现的次数，// 出现的字符存放在str数组中，各个字符在该字符串中出现的次数存放在// cnt数组中，返回字符串st中字符种类数。

多媒体技术基础实验报告——霍夫曼编码学院：电子工程与光电技术学院专业：电子信息工程姓名：学号：任课老师：康其桔实验时间：一、实验内容及要求1、使用Matlab 编程实现霍夫曼编码2、通过键盘输入字符串3、在屏幕上显示编码结果二、实验原理霍夫曼编码是霍夫曼在1952年提出和描述的“从下到上”的熵编码方法。

根据给定数据集中各元素所出现的频率来压缩数据的一种统计压缩编码方法。

这些元素(如字母)出现的次数越多，其编码的位数就越少。

其基本步骤为： (1) 将压缩的各字符的出现概率按减少(或增加)的顺序进行排列。

(2) 将两个最小的概率进行组合相加得到一个新概率将这一新概率与其它概率一起继续执行1 和2 的操作直至最后概率为1.0。

(3) 对每对组合中的概率较大者指定为1,较小者指定为0。

(4) 画出由每个信源符号概率到1.0处的路径记下路径的1和0。

(5) 对每个信源符号由从右到左写出1/0序列，对概率较高的标1，对概率较低的标0(或对概率较高的标0，对概率较低的标1)，就得到了对应的Huffman 码。

下面举个例子来说明霍夫曼编码的具体过程。

设需要编码的信息为：BACDEBACDEBACDEBADEBAEBABABABB,统计各个字符出现的次数分别为B(10次)、A(8次)、C(3次)、D(4次)、E(5次)。

各个字符出现的概率为B(10/30)、A(8/30)、E(5/30)、D(4/30)、C(3/30)。

霍夫曼编码的过程如下： B(10/30)A(8/30)E(5/30) D(4/30) C(3/30) 霍夫曼编码后平均码长为2(10/308/305/30)3(4/303/30) 2.23b ⨯+++⨯+≈ 。

而信源熵 2.19H b =。

由此，我们可以看出，霍夫曼编码结果已经很接近理想信源熵。

三、设计方案设计的流程图如下：7/30 12/3018/30 30/30 B:11 A:10 E:00 D:011 C:010 1 010 0 1 1 0四、各模块设计（一）读入字符串并去除空格在Matalb中使用语句inputstring=input('请输入需要编码的字符:','s')，输入的字符串存入char型数组inputstring中。

霍夫曼编码的matlab实现一、实验目的。

利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。

本实验用Matlab语言编程实现霍夫曼（Huffman）编码。

二、实验原理。

霍夫曼（Huffman）编码算法是满足前缀条件的平均二进制码长最短的编-源输出符号，而将较短的编码码字分配给较大概率的信源输出。

算法是：在信源符号集合中，首先将两个最小概率的信源输出合并为新的输出，其概率是两个相应输出符号概率之和。

这一过程重复下去，直到只剩下一个合并输出为止，这个最后的合并输出符号的概率为1。

这样就得到了一张树图，从树根开始，将编码符号1 和0 分配在同一节点的任意两分支上，这一分配过程重复直到树叶。

从树根到树叶途经支路上的编码最后就构成了一组异前置码，就是霍夫曼编码输出。

离散无记忆信源：例如U u1 u2 u3 u4 u5P(U) = 0.4 0.2 0.2 0.1 0.1通过上表的对信源缩减合并过程，从而完成了对信源的霍夫曼编码。

三、实验步骤分为两步，首先是码树形成过程：对信源概率进行合并形成编码码树。

然后是码树回溯过程：在码树上分配编码码字并最终得到霍夫曼编码。

1、码树形成过程：将信源概率按照从小到大顺序排序并建立相应的位置索引。

然后按上述规则进行信源合并，再对信源进行排序并建立新的位置索引，直到合并结束。

在这一过程中每一次都把排序后的信源概率存入矩阵G中，位置索引存入矩阵Index中。

这样，由排序之后的概率矩阵G以及索引矩阵Index就可以恢复原概率矩阵P了，从而保证了回溯过程能够进行下去。

2、码树回溯过程：在码树上分配编码码字并最终得到Huffman 编码。

从索引矩阵M 的末行开始回溯。

(1) 在Index的末行2元素位置填入0和1。

(2) 根据该行索引1 位置指示，将索引1 位置的编码（‘1’）填入上一行的第一、第二元素位置，并在它们之后分别添加‘0’和‘1’。

(3) 将索引不为‘1’的位置的编码值（‘0’）填入上一行的相应位置（第3 列）。

一、实验目的1. 理解霍夫曼算法的基本原理和过程。

2. 掌握霍夫曼算法的编程实现。

3. 分析霍夫曼算法的复杂度和性能。

二、实验原理霍夫曼算法是一种贪心算法，用于数据压缩。

其基本思想是根据字符出现的频率，构造出一棵最优二叉树，从而得到最优的编码方案。

霍夫曼算法的步骤如下：1. 统计每个字符的出现频率。

2. 将频率相同的字符视为一类，按照频率从小到大排序。

3. 将排序后的字符中频率最小的两个字符合并成一个新字符，新字符的频率为两个字符频率之和。

4. 将新字符插入到排序后的字符中，并重新排序。

5. 重复步骤3和4，直到只剩下一个字符为止。

6. 根据合并的顺序，从根节点到叶子节点的路径上，将0和1分别赋给路径，形成每个字符的霍夫曼编码。

三、实验内容1. 编写程序实现霍夫曼算法。

2. 对给定的字符集进行编码和解码。

3. 分析霍夫曼算法的复杂度和性能。

四、实验步骤1. 编写程序，统计字符集的频率。

2. 根据频率构造最优二叉树。

3. 根据最优二叉树生成霍夫曼编码。

4. 编写解码程序，根据霍夫曼编码解码字符。

5. 测试程序，分析霍夫曼算法的复杂度和性能。

五、实验结果与分析1. 实验结果（1）霍夫曼编码示例假设字符集为：{a, b, c, d, e, f}，频率分别为：{4, 2, 3, 5, 7, 8}。

（2）霍夫曼编码根据霍夫曼算法，得到以下编码：a: 0b: 10c: 110d: 1110e: 1111f: 100（3）解码根据霍夫曼编码，解码结果为：{a, b, c, d, e, f}。

2. 实验分析（1）复杂度分析霍夫曼算法的时间复杂度为O(nlogn)，其中n为字符集的长度。

这是因为算法需要构建一个最优二叉树，而构建最优二叉树的时间复杂度为O(nlogn)。

（2）性能分析霍夫曼编码具有较好的压缩效果，其平均编码长度较其他编码方法短。

当字符集中字符的频率差异较大时，霍夫曼编码的压缩效果更明显。

六、实验总结通过本次实验，我们掌握了霍夫曼算法的基本原理和编程实现，分析了算法的复杂度和性能。