信息编码之M进制的哈弗曼编码(共23页)

1、精选优质文档-倾情为你奉上青岛农业大学课 程 论 文（设计） 题 目： M进制哈夫曼编码的分析与实现 姓 名： 学 院： 理学与信息科学学院 专 业： 信息与计算科学专业 班 级： 学 号： 指导教师： 2014年 6 月26 日专心-专注-专业目 录摘要1Abstract2引言31 课题描述32 信源编码的基本概念42.1 通信系统的模块42.2 信息的度量与编码42.3 无失真编码算法63 信源最佳化84 哈夫曼编码特点及应用95 编码 105.1 二元哈夫曼编码规则 105.2 M进制哈夫曼编码115.3 C+程序146 总结 19参考文献 20M进制哈夫曼编码的分析与实现 信息与计算科

2、学 李栋 指导教师 吴慧摘要：哈夫曼编码(Huffman Coding)是一种编码方式，也是可变字长编码(VLC)的一种。这种方法完全依据字符出现的概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作哈夫曼编码。对于M进制哈弗曼编码，为了提高编码效率，就要使长码的符号数量尽量少、概率尽量小，所以应使合并的信源符号位于缩减信源序列尽可能高的位置上，以减少再次合并的次数，充分利用短码。本文将采用三进制哈夫曼编码作为例子来诠释M进制哈夫曼编码。在三进制哈夫曼编码中，得出码字、平均码长和编码效率，构造哈夫曼树，沿着根节点到叶节点从左到右依次为0、1、2，保证平均码长最小。在本文中采用V

3、isual C+6.0进行编程，此程序中具有输入字符集大小和权值大小，构造哈夫曼树，并对用户输入的字符串进行编码等功能。关键词：哈弗曼编码；信源；哈夫曼树；Visual C+6.0；Analysis and implementation of M binary Huffman codingStudent majoring in Information and Computing Sciences Li DongTutor Wu HuiAbstract：The Huffman code (Huffman Coding) is a kind of encoding, and variable le

4、ngth coding(VLC) is a kind of. The average length of this method on the basis of fully probabilisticcharacter appears to construct different prefix the shortest codeword, sometimes called the best code, generally known as Huffman coding. For the M systemHavermann coding, in order to improve the codi

5、ng efficiency, it is necessary to makethe number of long code symbols as little as possible, probability as small as possible,so should make the source symbols in the source sequence with reduced as far as possible the high position, to reduce the number of merged again, make full use of short code.

6、This paper will use the three binary Huffman coding as an example to explain the Mbinary Huffman coding.In the three binary Huffman coding, the code word, the average code length and coding efficiency, Huffman tree structure, along the root node to the leaf nodes from left to right: 0, 1, 2, the ave

7、rage code length minimum. In this paper by using VisualC+6.0 programming, the input character set size and weight with this program,Huffman tree structure, and code functions for string input by the user.Key words: The Hoffman code;Source;Huffman tree;Visual C+6.0引言在这个信息量爆炸的时代，凡是能载荷一定信息量，且码字的平均长度最短，

8、可分离的变长码的码字集合称为最佳变长码。为此，必须将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字最短。能获得最佳码的编码方法主要有：香农（Shannon）、费诺（Fano）、哈夫曼（Huffman）编码等。哈夫曼(Huffman)编码是一种常用的压缩编码方法，是Huffman于1952年为压缩文本文件建立的。它的基本原理是频繁使用的数据用较短的代码代替，较少使用的数据用较长的代码代替，每个数据的代码各不相同。哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号用一个特定长度的位序列替代。因此，在文件中出现频率高的符

9、号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。哈夫曼编码是哈夫曼树的一个应用，是一种最优的前缀技术，然而其存在的不足却制约了它的直接应用。首先，其解码时间为O(lavg)，其中lavg为码字的平均长度；其次，更为重要的是，解码器需要知道哈夫曼编码树的结构，因而编码器必须为解码器保存或传输哈夫曼编码树。对于小量数据的压缩而言，这是很大的开销。因而，应用哈夫曼编码的关键是如何降低哈夫曼编码树的存储空间。目前流行的很多压缩方法都是用了该技术，如GZIB、ZLIB、PNC等。1 课题描述在通信的数字化过程中，对于时间连续和取值连续的原始语音和图像等模拟信号来说，如果要以数字方式进行传输，

10、在发送端必须首先进行模/数(A/D)变换，将原始信号转换为时间离散和取值离散的数字信号。模拟信号数字化之后一般会导致传输信号的带宽明显增加，这样就会占用更多的信道资源，使得传输效率降低，或者无法实现实时传输。为了提高传输效率，一方面需要采用压缩编码技术，在保证一定信号质量的前提下，尽可能地去除信号中的冗余信息，从而减少信号速率和传输所用带宽。另一方面，即使是原本就以数字形式存在的数据和文字信息，也同样存在一个需要通过压缩编码降低信息冗余提高传输效率的问题。由于这些处理都是针对信源发送信息所进行的，因此一般将其称为信源编码。信源编码的基本目的是提高码字序列中码元的平均信息量，那么，一切旨在减少剩

11、余度而对信源输出符号序列所施行的变换或处理，都可以在这种意义下归入信源编码的范畴，例如过滤、预测、域变换和数据压缩等。作为现代数据无损压缩的灵魂算法，哈夫曼编码正广泛应用于各种图像、音频、视频及各种多媒体信息的压缩环境中。2 信源编码的基本概念2.1 通信系统的模块信源信源编码信道编码信道信道译码信源译码信宿噪声2.2 信息的度量与编码信息是指消息中包含的有效内容，度量信息量的原则首先是能度量任何消息并与消息的种类无关，其次度量方法应该与消息的重要程度无关，最后消息中所含信息量和消息内容的不确定性有关。信息熵的输出可以用随机过程来描述。对于一个离散无记忆平稳随机过程，其信息量（熵）定义为： 其

12、中X表示信源取值集合，p(x)是信源取值x的概率。 信源编码是数字通信中的重要环节，它的主要目的是减少冗余，提高编码效率。信源编码可分为两类：无失真编码和有失真编码。无失真编码只对信源冗余度进行压缩，不会改变信源的熵，又称冗余度压缩编码，它能保证码元序列经译码后能无失真的恢复成信源符号序列，如哈夫曼编码，香农编码。有失真编码在允许的失真范围内把编码后的信息率压缩到最小，有失真信源编码的失真范围受限，所以又称为限失真信源编码。信源编码就是把信源符号序列变换到码符号序列的一种映射。若要实现无失真编码，那么这种映射必须是一一对应的、可逆的。一般来说，人们总希望把信源所有的信息毫无保留的传递到接受端，

13、即实现无失真传输，所以首先要对信源实现无失真编码。信源编码有以下三种主要方法： （1）匹配编码根据信源符号的概率不同，编码的码长不同,这样使平均码长最短。将要讲到的哈夫曼编码就是概率匹配编码。 （2）变换编码先对信号进行变换，从一种信号空间变换为另一种信号空间，然后针对变换后的信号进行编码。一般是把分布在时空域的信号（如时域的语音信号和平面空间的图像信号）映射到变换域（如频域的频谱信号和其他正交矢量空间域），原来相关性很强的原始信号经过变换后，得到的变换域系数相互独立，并且能量集中在少数低序系数上，这样只需对少量的变换域的系数进行编码，达到数据压缩的目的。常用的变换编码有DFT、沃尔什变换、小

14、波变换等。 (3)识别编码识别编码主要用于印刷或打字机等有标准形状的文字、符号和数据的编码，比如中文文字和语音的识别。后两种信源编码均为有失真的信源编码。最原始的信源编码就是莫尔斯电码，另外还有ASCII码和电报码都是信源编码。但现代通信应用中常见的信源编码方式有：哈夫曼编码、算术编码、L-Z编码，这三种都是无损编码。而哈夫曼编码作为变长码满足变长信源编码定理。该编码定理是香农信息论中非常重要的一个定理，它指出，要做到无失真的信源编码，信源每个符号所需要的平均码元数就是信源的熵值，如果小于这个值，则唯一可译码不存在，可见，熵是无失真信源编码的极限值。定理还指出，通过对扩展信源进行编码，当N趋向

15、于无穷时，平均码长可以趋进该极限值。还可以证明，如果我们不确切知道信源的概率分布，我们用估计的概率分布去进行编码时，平均码长会加长，但是如果估计的偏差不大的话，平均码长也不会增加太多。2.3 无失真编码算法编码器：编码器可以看作这样一个系统，它的输入端为原始信源S，其符号集为S,而信道所能传输的符号集为X，编码器的功能是用符号集X中的元素，将原始信源的符号Si变换为相应的码字符号Wi,编码器输出端得符号集为C。 编码器X S C 奇异码与非奇异码若一种分组码中所有码字都不相等，则称分组码为非奇异码，否则为奇异码。唯一可译码与非唯一可译码任意有限长码元序列，如果只能唯一分割成一个个码字便称为唯一

16、可译码。唯一可译码得物理意义是指不仅要求不同的码字表示不同的信源符号，而且还要求对由信源符号构成的符号序列进行编码时，在接受端仍能正确译码而不发生混淆。唯一可译码首先是非奇异码且任意有限长的码字序列不会雷同。即时码与非即时码无需考虑后续的码符号就可以从码符号序列中译出码字，这样的唯一可译码称为即时码变长码及变长编码定理信源符号数、码符号数、码字长度之间满足什么条件才可以构成即时码和唯一可译码呢？Kraft不等式和McMillan不等式回答了这个问题。这两个不等式在形式上是完全一样的。设信源符号集为，码符号集为，对信源进行编码，得到的码为，码长分别为。即时码存在的充要条件是： 这称为Kraft不

17、等式。由上式可知，给定r和q，只要允许码字长度可以足够长，则码长总可以满足Kraft不等式而得到即时码，Kraft不等式指出了即时码的码长必须满足的条件。后来McMillan证明对于唯一可译码得码长也必须满足此不等式。在码长的选择上唯一可译码并不比即时码有更宽松的条件。对于唯一可译码，该不等式又称为McMillan不等式。唯一可译码存在的充要条件是： 其中r为码符号个数，为码字长度，q为信源符号个数无失真变长信源编码定理离散无记忆信源S的N次扩展信源，其熵为，并且编码器的码元符号集为A：对信源进行编码，总可以找到一种编码方法，构成唯一可译码，使信源S中每个符号所需要的平均码长满足当时则有式中，

18、其中是扩展信源的信源符号所对应的码字长度，因此是扩展信源中每个符号的平均码长，而是信源S中单个信源符号所需的平均码长。这里要注意与的区别：它们都是单个信源符号所需的码符号的平均数，但是的含义是，为了得到这个平均值，不是对单个信源符号进行编码，而是对N个信源符号序列进行编码，然后对N求平均。该定理指出，要做到无失真信源编码，每个信源符号平均所需最少的r元码元数就是信源的熵值。若编码的平均码长小于信源的熵值，则唯一可译码不存在，在译码或反变换时必然要带来失真或差错，同时定理还指出，通过对扩展信源进行变长编码，当时，平均码长可达到这个极限值。可见，信源的信息熵H(S)是无失真信源编码码长的极限值，也

19、可认为信源熵是表示每个信源符号平均所需最少的码元符号数。3 信源最佳化通信系统的传输效率就是指给定信道的信道容量利用率，它表示信道的实际传信率与信道容量的比值，可以写成： =R/C可见要提高传输效率，基本任务就是要改造信源，使其熵值最大化，此时趋于1，而这个过程就是信源最佳化得过程。信源熵H(X)最大化实质上就是寻求一种最佳的概率分布。根据熵函数的性质，在离散信源情况下，当各个符号间彼此独立而出现的概率相等时，信源熵达到最大值。因此，一般的熵值最大化应当包括两个步骤：1、符号独立化，解除符号间的相关性；2、各符号概率均匀化。为了衡量各种编码是否已达到极限情况，我们定义变长码的编码效率。设对信源

20、S进行无失真编码所得到的平均码长为,则,定义 为编码效率，我们可以采用声码器技术，模式识别技术，变换编码技术以及相关编码技术等近几年来发展起来的效率较好的压缩信源方法来解除关联、压缩信源和提高传输效率。经过解除相关性之后，如果再使各符号的概率均匀化，就能进一步改造有剩余信源的输出，去掉冗余度，提高熵速率，使传输率接近信道容量进而使传输效率接近1。如香农-范诺编码，哈夫曼编码。这列编码的基本思想就是使各符号的概率均匀化，即出现概率大的符号编成短码，出现概率较小的符号编成长码，只是由于具体方法不同，得到的效果也不同。4 哈夫曼编码特点及应用哈夫曼编码是真正意义上的最佳编码。首先编码是非续长码，哈夫

21、曼编码实际上构造了一个码树，码树从最上面的端点开始构造，直到树根结束，最后得到一个横放的码树。其次，其编码的平均码长最小，哈夫曼编码采用概率匹配的方法来决定各码字的码长，概率大的符号对应于短码，概率小的符号对应于长码。最后，哈夫曼编码的码字并不唯一，每次对概率最小的两个符号求概率之和形成缩减信源时，就构造出两个树枝，由于对两个树枝附码元时是任意的，所以码字不唯一。另外在哈夫曼编码过程中，对缩减信源符号按概率由大到小的顺序排列时应使合并后的新符号尽可能的排在靠前的位置，这样可使合并后的新符号重新编码次数减少，使短码得到充分利用。 在实际应用中，首先每个信源符号所对应的码长不同，一般情况下，信源符

22、号以匀速输出，信道也是匀速传输的。通过哈夫曼编码后，会造成编码输出的信息速率不是常量，因而不能直接由信道来传送。为了适应信道，必须增加缓冲寄存器，将编码输出暂存在缓冲器中，然后再匀速向信道输出。但当缓冲器容量有限时，会出现缓冲器溢出或取空的现象。所以一般变长码只适用于有限长的信息传输，或者在输出一批消息后能暂停一下。其次，差错扩散的问题。变长码得一个的差错可能造成译码错误，并且还会造成同步错误，结果后面一系列码字也会译错。最后，哈夫曼码的编译码需要用查表的方法来进行。在信息传输过程中必须先存储与传输这一哈夫曼编码表。这会影响信息的传输效率，特别是当N增大时，所需存储的码表也增大，使得设备复杂化

23、，且查表搜索的开销增大。我们还须根据信源的统计特性，事先建立哈夫曼编码表，因此这种方法只适用于已知其统计特性的信源。尽管如此，哈夫曼方法还是一种有效的无失真信源编码方法，它便于硬件实现和计算机上的软件实现，适用于文件传真、语音处理和图像处理的数据压缩。在新世纪，广播电视数字化兴起，有线电视、卫星电视和地面无线广播电视的数字化都发展很快，有线数字电视的另一个发展趋势是利用IP技术的IPTV，数字电视地面无线广播技术新的应用领域是手机电视。我国数字电视地面无线广播系统技术研究较早，提出了多种方案，其中采用伪随机序列（PN）的时域同步频域处理技术等构成了基础性发明专利，所实现的性能优于按照ITU已有

24、的三项国际标准实现的系统。不仅在信道处理技术上而且在信源编码技术上我国也有可喜的创新，我国发布了AVS音视频编码标准，它的压缩效率与国际标准MPEG4/AVC相当，但复杂度低，AVS的部分技术已被吸纳进相应的国际标准。5 编码5.1 二元哈夫曼编码规则哈夫曼编码的步骤如下： 将信源消息符号按其出现的概率大小依次排列 取两个概率最小的字母分别配以0和1两码元,并将这两个概率相加作为一个新字母的概率,与未分配的二进符号的字母重新排队。 对重排后的两个概率最小符号重复步骤的过程。 不断继续上述过程,直到最后两个符号配以0和1为止。 从最后一级开始,向前返回得到各个信源符号所对应的码元序列,即相应的码

25、字。5.2 M进制哈夫曼编码 在编m进制哈夫曼码时为了使平均码长最短,必须使最后一步缩减信源有m个信源符号。 对于m进制编码,若所有码字构成全树,可分离的码字数必为：非全树时，有s个码字不用： 第一次对最小概率符号分配码元时只取(ms)个,分别配以0,1,m-s-1,把这些符号的概率相加作为一个新符号的概率,与其它符号一起重新排列,以后每次取m个符号,分别配以0,1,m-1；如此下去,直至所有概率相加得1为止,即得到各符号的m进制码字。 例:对如下单符号离散无记忆信源编三进制哈夫曼码 这里：m =3，n =8 令k=3，m+k(m1)=9，则 s = 9n = 98 =1 所以第一次取ms=2

26、个符号进行编码。 以m =3为例，平均码长为 信息率为编码效率为例： 已知离散无记忆信源（1）分别求信源输出进行其三进制和四进制哈夫曼码编码（2）分别求出两种编码的平均码长和编码效率解：（1）三进制哈夫曼编码：四进制哈夫曼编码：（2） 两种编码的平均码长分别为：信息熵： 两种编码的编码效率分别为 5.3 C+程序void Huffmancoding(Huffmantree HT,Huffmancode HC,float w,int n) int i,m,c,s1,s2,start,f,k20,a,b,d,s3,s4,q,flase=0;float H=0.0,K=0.0,G;/char cd;

27、Huffmantree p;if(n<=1) printf("无法构成树！n");exit(0); m=n+4; HT=(Huffmantree)malloc(m+1) sizeof(HTnode); /0号单元未用for(p= HT+1,i=1;i<=n;i+,+p ) ( p).weight =wi; ( p).lchild =0; ( p).mchild =0; ( p).parent =0; ( p).rchild =0;for(;i<=m;i+,+p) ( p).weight =0; ( p).lchild =0; ( p).parent =0;

28、 ( p).mchild =0; ( p).rchild =0;a=1;b=n,d=1;while(b-a)>0) b=b-a; a=a 3; d+; s3=3+d (3-1); / s4=s3-n; /不用的码字数 q=3-s4; /第一次取符号数编码 if(q=1) flase=1; select1( HT,n,&s1); ( HT)s1.parent =n+1;( HT)i.rchild =s1; ( HT)i.weight =( HT)s1.weight; else if(q=2) flase=1; select2( HT,n,&s1,&s2); ( HT

29、)s1.parent =n+1; ( HT)s2.parent =n+1; if( HT)s1.weight=( HT)s2.weight) ( HT)n+1.mchild =s2; ( HT)n+1.rchild =s1; else ( HT)n+1.mchild =s1; ( HT)n+1.rchild =s2; ( HT)n+1.weight =( HT)s1.weight+( HT)s2.weight; if(flase=1) for(i=n+2;i<=m;i+)select3( HT,i-1,&s1,&s2,&s3); ( HT)s1.parent =i

30、; ( HT)s2.parent =i;( HT)s3.parent =i; ( HT)i.lchild =s1;( HT)i.mchild=s2;( HT)i.rchild=s3; ( HT)i.weight =( HT)s1.weight+( HT)s2.weight+( HT)s3.weight; else for(i=n+1;i<=m;i+) select3( HT,i-1,&s1,&s2,&s3); ( HT)s1.parent =i; ( HT)s2.parent =i;( HT)s3.parent =i; ( HT)i.lchild =s1;( HT

31、)i.mchild=s2;( HT)i.rchild=s3; ( HT)i.weight =( HT)s1.weight+( HT)s2.weight+( HT)s3.weight; HC=(Huffmancode)malloc(n+1) sizeof(char ); char cd; cd=(char )malloc(n sizeof(char); cdn-1='0' printf("信源哈夫曼编码如下:n"); for(i=1;i<=n;+i) start=n-1;ki=0; for(c=i,f=( HT)i.parent;f!=0;c=f,f=( HT)f.parent) ki+; if( HT)f.lchild=c) cd-start='2' else if( HT)f.mchild=c) cd-start='1' else cd-start='0' ( HC)i=(char )malloc(n-start) sizeof(char); strcpy( HC)i,&cdstart); printf("x%d=%f 的哈夫曼编码是 %st码长是 %dn",i,( HT)i.weight,( HC)i,ki); for(i=1;i<=