《2022年2022年霍夫曼编码 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年霍夫曼编码 .pdf（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、课程名称：信息论实验室：综合实验室实验时间： 2010.11.08 第 1 页 共 4 页实验二 Huffman 编码一、实验目的1复习 C+程序基本编写方法，熟悉VC 编程环境。2会用 VC 调试 Huffman 编码程序。二、实验内容1复习 C+代码基本语法（结构体、树等数据结构定义）2根据 Huffman 编码源代码，学习算法实现流程，培养自己动手能力，在C+ 编译器下按步调试跟踪算法。三、实验仪器、设备1计算机系统最低配置 256M 内存、 P4 CPU 。2C+ 编程软件 Visual C+ 7.0 （ Microsoft Visual Studio 2003）四、实验原理1 Huf
2、fman 编码原理：将信源符号按概率从大到小的顺序排列，令p(x1) p(x2) , p(xn) 给两个概率最小的信源符号p(xn-1) 和p(xn) 各分配一个码位“ 0”和“ 1”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含(n 1) 个信源符号的新信源。称为信源的第一次缩减信源，用S1表示。将缩减信源 S1的符号仍按概率从大到小顺序排列，重复步骤 2，得到只含 (n 2) 个符号的缩减信源 S2。重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号
3、所对应的码字。2Huffman 树的编码原理：步骤 1： 将各个符号及其出现频率分别作为不同的小二叉树（目前每棵树只有根节点）步骤 2： 在步骤 1中得到的树林里找出频率值最小的两棵树，将他们分别作为左、右子树连成一棵大一些的二叉树，该二叉树的频率值设为两棵子树频率之和。步骤 3： 对上面得到的树林重复步骤2的做法，直到所有符号都连入树中为止。五、实验步骤1VC 环境下，建一个C+ 控制台应用程序，并把源代码考到该程序目录下。2项目文件中含有一个预编译头文件，一个主函数入口文件和Huffman 编码算法文件。3在入口文件中，输入任一个离散信源进行编码调试。4设置好程序断点，仔细分析Huffma
4、n 树每步的建立过程。5输出离散信源中每个符号的Huffman 编码，并与手工运算的结果进行比较。六、实验注意事项1指针数据结构定义typedef struct unsigned long weight; int parent, lchild, rchild; HTNode, *HuffmanTree; typedef char* HuffmanCode; / 指向存放数组指针的数组即二维数组2二叉树生成操作放在数组中（节点n 和数组大小 m 关系为： m=2*n-1）。每次在树中找到两颗最小子树，其函数为Select(HuffmanTree HT, int n, int *s1, int*s
5、2)，实际实现的是在数组中找到最小两个元素。另外注意C+的数组起始索引是0， Matlab 起始索引是 1；程序中为了方便从1 开始索引数组， HT0.weight的大小设为 0 xffffffffL。为了输出二进制Huffman 码，程序最名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 4 页 - - - - - - - - - 课程名称：信息论实验室：综合实验室实验时间： 2010.11.08 第 2 页 共 4 页后对每个符号进行深度优先搜索，得到该符号的二进制字符
6、，然后进行字符串拷贝，直到最后输出。实验程序：预编译头文件：stdafx.h 以下代码#pragma once #include #include #include #include #include / stdafx.cpp : 只包括标准包含文件的源文件/ Huffman.pch 将成为预编译头/ stdafx.obj 将包含预编译类型信息#include stdafx.h / TODO: 在 STDAFX.H 中/ 引用任何所需的附加头文件，而不是在此文件中引用/ Huffman.cpp : 定义控制台应用程序的入口点。#include stdafx.h typedef struct u
7、nsigned long weight; int parent, lchild, rchild; HTNode, *HuffmanTree; typedef char* HuffmanCode; HuffmanCode HC; void Select(HuffmanTree HT, int n, int *s1, int *s2); void HuffmanCoding(unsigned long *w, int n) int i; if( n=1 ) return; int m = 2*n - 1; HuffmanTree p; HuffmanTree HT = (HuffmanTree)m
8、alloc(m+1)*sizeof(HTNode); memset(HT, 0, sizeof(HTNode) * (m+1); for( p=HT,i=1; iweight = *w; int s1, s2; for( i=n+1; i=m; +i ) Select(HT, i-1, &s1, &s2); HTs1.parent = i; HTs2.parent = i; HTi.lchild = s1; HTi.rchild = s2; HTi.weight = HTs1.weight + HTs2.weight; HC = (HuffmanCode)malloc(n+1)*sizeof(
9、char*); char *cd = (char*)malloc(n*sizeof(char); cdn-1 = 0; int start; unsigned long f; for( i=1; i=n; +i ) start = n - 1; int c; for( c=i, f=HTi.parent; f!=0; c=f, f=HTf.parent ) if( HTf.lchild = c ) cd-start = 0; else cd-start = 1; HCi = (char*)malloc(n-start)*sizeof(char); strcpy(HCi, &cdstart);
10、free( HT ); /free( cd ); void Select(HuffmanTree HT, int n, int *s1, int *s2) int i; HT0.weight = (unsigned long)(-1l); *s1 = *s2 = 0; for( i=1; i=n; i+ ) if( HTi.parent = 0 ) if( HTi.weight HT*s1.weight ) *s2 = *s1; *s1 = i; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - -
11、- - 第 2 页，共 4 页 - - - - - - - - - 课程名称：信息论实验室：综合实验室实验时间： 2010.11.08 第 3 页 共 4 页else if( HTi.weight HT*s2.weight ) *s2 = i; int _tmain(int argc, _TCHAR* argv) const int LEN = 8; int i; unsigned long weightLEN+1; weight0 = 0; weight1 = 1; weight2 = 1; weight3 = 2; weight4 = 1; weight5 = 1; weight6 = 1
12、; weight7 = 2; weight8 = 1; HuffmanCoding( weight, LEN ); for( i=1; i=LEN; i+ ) printf(%sn, HCi); return 0; 七、思考题根据 Huffman 算法的 C源程序，试着写出Huffman 编码的 Matlab 程序？编码流程：1.读入一幅图像的灰度值; 2.将矩阵的不同数统计在数组c的第一列中 ; 3.将相同的数占站整个数组总数的比例统计在数组p中; 4.找到最小的概率, 相加直到等于1, 把最小概率的序号存在tree 第一列中 , 次小放在第二列, 和放在 p像素比例之后 ; 5.C数组第一
13、维表示值, 第二维表示代码数值大小, 第三维表示代码的位数；6.把概率小的值为1标识，概率大的值为0标识；7.计算信源的熵；8.计算平均码长；9.计算编码效率 ；10.计算冗余度。Huffman 编码 m 文件及分析function h,l=huffman(p) if (length(find(p10e-10) error(Not a prob.vector,component do not add to 1) end n=length(p); q=p; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - -
14、- - - - 第 3 页，共 4 页 - - - - - - - - - 课程名称：信息论实验室：综合实验室实验时间： 2010.11.08 第 4 页 共 4 页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; end for i=1:n-1 c(i,:)=blanks(n*n); end c(n-1,n)=0; c(n-1,2*n)=1; for i=2:n-1 c(n-i,1:n-1)=c(n-i+1,n*(find(m(n-i+1,:)=1).
15、-(n-2):n*(find(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-1 c(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); end end for i=1:n h(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); end l=
16、sum(p.*ll); h,l=huffman(p),输入为一维行矩阵p，p为各符号的概率分布，概率和为1，各元素值为正，输出 H矩阵为对应每个符号概率的码字，L为输出码字的平均码长。Huffman .m 运用典型的 IF 和FOR 控制流循环语句，该程序包括两个IF 控制流和 5个FOR 循环结构。八、实验总结：通过本次实验，我学会了用C+ 编写和调试 Huffman 编码程序，复习了C+ 代码基本语法，明白了 Huffman 的编码原理，并通过学习和上网搜取资料，编写了并调试了Huffman 编码的 Matlab 程序，经实验证明结果是正确的。本次实验不仅锻炼了我的动手能力，还让我对学习信息论产生了浓厚的兴趣，为今后的学习打下了好的基础。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 4 页 - - - - - - - - -