无失真信源编码方法理论研究及其应用.doc

江西理工大学2008届本科生毕业设计(论文)摘 要无失真信源编码理论，作为信息论的研究理论基础，一直以来都受到人们的广泛关注。无失真信源编码是一种可逆编码的基础，即是指当信源符号转换成代码后，可从代码无失真到恢复原信源符号。本文主要介绍了无失真编码的几种常用方法：香农码、费诺码、算术码和哈夫曼码。分别详细阐述了各个编码方法的编码原理、编码过程以及算术码和哈夫曼码的改进优化。并且结合数字网络的快速发展，介绍了无失真信源编码方法及哈夫曼编码的软件仿真，对其对图象压缩的性能进行了分析。文章的最后两章介绍了无失真编码在MP3和数字电视广播中的应用，对未来的发展趋势也进行了阐述。无失真编码技术也在信息化、网络化、高科技化的特殊时代环境背景下，迎来了发展的机遇与挑战。无失真编码的应用领域越来越广，因而编码方法有待进一步的深入研究。 关键字：无失真；编码方法；图象压缩48 AbstractWithout distortion source coding theory, information theory research as a theoretical basis, have been subject to peoples attention. Without distortion source coding is the basis of a reversible coding, refers when the source code into symbols, from the code without distortion to restore the original source symbols. This paper without distortion of several commonly used method of coding: Shannon code, for Connaught code, and arithmetic code Huffman code. Were elaborated on the various coding method of coding theory, coding process and arithmetic code and Huffman code to improve optimization. And with the rapid development of digital networks, introduced without distortion source coding methods and Huffman coding software simulation, the image compression to the performance analysis. The articles final two chapters on the non-coding distortion in the MP3 and digital television broadcasting of the future trend of development have also carried out on. Lossless coding technology is information technology, network-based, high-tech environment of the special context of the era, ushered in the development of the opportunities and challenges. Lossless coding applications more widely, thus coding method to be further in-depth study.Keyword： source Without distortion Coding technology Image compression目 录第一章 绪论11.1无真编码方法的形成背景和发展1.2 无失真编码方法的应用领域第二章 无失真信源编码 22.1 编码定理.32.2 常用编码方法72.2.1 香农编码方法8.2.2.2 费诺编码方法92.2.3 哈夫曼编码方法102.2.4 算术编码方法11第三章 哈夫曼编码和算术编码的改进优化12 3.1 哈夫曼编码算法的分析改进14 3.2 算术编码算法的改进13 第四章 哈夫曼编码的软件实现 154.1 仿真软件MATLAB简介4.2 哈夫曼编解码流程图4.3 仿真结果分析第五章 无失真编码技术的实际应用 155.1 在MP3中的音频压缩17 5.2 在数字电视广播中的应用16第六章 无失真编码技术的未来发展趋势总结20致谢21参考文献22 附录23第一章 绪论“信息”这个词相信大家都不陌生，几乎每时每刻都会接触到。不仅在通信，电子行业其他各个领域也都十分重视信息，所谓进入了“信息时代”。信息不是静止的，它会产生也会消亡，人们要获取它，并完成它的传输，交换，处理，检测，识别，存储，显示功能。而在信息传输的过程中，我们就要涉及到信源编码技术的研究。象图象压缩传输，视频和音频的压缩处理等都要用到无失真编码。通过本章的学习，可以了解以下问题：无失真编码的形成背景和发展趋势；编码技术的具体应用领域。1.1无失真编码技术的形成背景和发展信息论理论基础的建立,一般来说开始于香农(C.E.Shanon)研究通信系统时所发表的论文。随着研究是深入与发展，信息论具有了较为宽广的内容。信息在早些时期的定义是有Nyquest,H 和 Hartley,L.V.R在20世纪20年代提出来的。1924年Nyquest,H解释了信号带宽度量方法；1936年阿姆斯特朗提出了增大带宽可以使抗干扰能力加强。1948年香农公开发表通信的数学理论，这是一篇关于现代信息论的开创性权威论文，为信息论的创立作出了独特的贡献。香农因此也成为了信息论的奠基人。50年代信息论在学术界引起了巨大的反响。1951年美国IRE成立了信息论组，并于1955年正式出版了信息论汇刊。60年代信道编码技术发展到了高峰，找到了大量可纠正多个错误的码，而且提出了可实现的译码方法。其次是卷积码和概率译码有了重大突破，提出了序列译码和ViterbiYI 译码方法。到了70年代，有关信息论的研究，从点到点间的单用户通信推广到多用户系统的研究。1972年盖弗发表了有关广播信道的研究，以后陆续有关于多人接入信道和广播信道模型的研究，但由于这些问题比较难，到目前为止，多用户信息论研究得不多，还有许多尚待解决的课题。信息论主要用在通信领域，在含噪信道中传输信息的最优方法到今天还不十分清楚。在这样的特殊时代和背景下，无失真编码方法的研究课题应运而生。 1.2无失真编码技术的应用领域随着网络技术的不断新起和发展，信息在网络中的传输已经成为人们获取信息的主要来源。而如何正确无误地从一方传递信息给另一方，无失真编码技术体现出了其功能与作用。数字图象压缩就要用到编码技术，还有视频和音频都要用到编码。另外，电报常用的莫尔斯码就是按信息论的基本编码原则设计出来的；一些商品上的粗细条纹组成的标签中我们可以得知生产厂家的生产日期和价格，都是用到条行码设计出来的，非常方便非常有用。每出版一本书，都给定一个国际标准书号（ISBN），大大方便了图书的销售和编目收藏工作。可以说，人们在日常生活和生产实践中，正在越来越多地使用到无失真编码技术。第二章 无失真信源编码 由于信源符号之间存在分布不均匀和相关性，使得信源存在冗余度，信源编码的主要任务就是减少冗余，提高编码效率。信源编码的基础是信息论中的两个编码定理：无失真编码定理和限失真编码定理。前者是可逆编码的基础。可逆是指当信源转换成代码后，可以从代码无失真地恢复原信源符号。无失真编码或可逆编码只适用于离散信源。信源编码定理出现后，编码方法就趋于合理化。本章讨论离散信源无失真编码，从无失真编码定理出发，重点讨论以香农码，费诺码，哈夫曼码和算术码为代表的最佳码。2.1编码定理2.1.1编码的定义 将信源消息分成若干组，即符号序列Xi,Xi=(X1,X2XlXL),序列的每个符号取自符号集A，Xla1,a2,ai,an。而每个符号序列Xi依照固定的码表映射成一个码字Yi，这样的码称为分组码，有时也叫块码。只有分组码才有对应的码表，而非分组码中则不存在码表。K长码字编码器 如图2-1所示的信源编码器，如果L长序列 信源输出的符号序列长度为1，即信源符号集 X=x1,x2, ,xn 图2-1 信源编码器 源概率空间为 一元信道是常用的一种信道，他的信道基本符号集为0，1。若将信源X通过一个二元信道传输，就必须把信源符号xi变成符号组成的码字序列，即编码。可用不同的码字符号序列，如表2-1所示。 表2-1 不同的码符号序列信源符号xi信源符号出现概率码 表信源符号xi信源符号出现概率P(xi)码 表码1码2码1码2X1P(X1)000X3P(x3)10001X2P(X2)0101X4P(x4)11111一般情况下，码可分为两类：一类是固定长度的码，码中所有码字长度都相同，如表2-1中的码就是定长码。另一类 是可变码，码中的码字长短不一，如表中码2就变长码。奇异码和非奇异码：若信源和码字是一一对应的，则该码为非奇异码。反之则为奇异码。如表2-2中的码字是奇异码，码2是非奇异码。表2-2 不同的码字信源符号xi符号出现概率p(xi)码1码 2码 3码 4 X1 1/20011X21/410101001X31/80000100001X41/8000110000001表2-2中的码3是唯一可译码，但码2不是唯一可译码。一般情况下，可将码作如下分类：非分组码奇异码 码分组码非唯一可译码 非奇异码 非即时码 唯一可译码 即时码例2-1-1设二进制码树中Xx1,x2,x3,x4,K1=1,K2=2,K3=2,K4=3,应用上述判断定理，可得 -Ki =21+22+22+23=1因此，不存在满足这种Ki的唯一可译码。可以用树码进行检查，由图2-1-3所示，要形成上述码字，必然在中间节点放置码字，如a1a1处，这样就产生了延长码。如码字为0，10，11，110。如果将各个长度改成K1=1，K2=2，K3=3，K4=3，则此时 -Ki =21+22+23+23=1这样的码就存在唯一可译码，如0，10，110，111。但是必须注意，克劳夫特不等式只是用来说明唯一可译码是否存在，并不能作为唯一可译码 的判断。如码字0，10，010，111，虽然满足克劳夫特不等式，但它不是唯一可译码。 X=（X1X2）, （2-1-1） Xla1,a2,ai,an变换成由KL个符号组成的码序列（有时也叫做码字，以下均用码字来叙述。） Y=（Y1Y2YkYKL）, （2-1-2） Ykb1,b2,bj,bm。变换的要求是能够无失真或无差错地从Y恢复X，也就是能够正确地进行反变换或译码，同时希望传送Y时所需要的信息率最小。在无失真的信源编码定理中相应的有定长编码定理和变长编码定理，下面我们分别加以讨论。 2.1.2 定长和变长编码定理1. 定长编码定理在定长编码中，K是定值,且K=KL.我们的目的是寻找最小K值。要实现无失真的信源编码,不但要求信源符号Xi(i=1,2,q)与码字Y i，（i=1,2,q)）是一一对应的，而且还要求由码字组成的码符号序列的逆变换也是唯一的。也就是说，由一个码表编出的任意一串有限长码字符号只能被唯一地反译成所对应的信源符号序列。定长编码定理：由L个符号组成的，每个符号的熵为HL（X）的无记忆平稳信源符号序列X1X2,可用KL个符号Y1Y2，,YK, , (每个符号有m中可能值)进行定长编码。对任意0，0，只要 mHL(X)+ （2-1-3）则当L足够大时，必可使译码差错小于；反之，当 mL(X)-2 （2-1-4） 时，译码差错一定是有限值，而当L足够大时，译码几乎必定成错。 通过上述编码定理，使我们对信源平均符号熵HL（X）有叫好的理解。当编码器容许的输出信息率，也就是当每个信源符号所必须输出的码长是 = m （2-1-5） 时，只要KHL（X），这种编码器一定可以做到几乎无失真，也就是收端译码差错概率接近于零，条件是所取符号数L足够大。将上述定理的条件（2-1-3）式改写成 KLmLHL（X）=H（X）上式大于号左边为KL长码字所能携带的最大信息量，右边为L长信源符号的信息量。=HL（X）时，则为临界状态，可能无失真，也可能有失真。例如，某信源有8种等概率符号，L=1，信源序列熵达到最大值： H1（X）=28=3比特即该信源符号肯定可以用3比特的信息率进行无失真的编码。2. 变长编码定理在变长编码中，码长K是变化的，我们可根据信源各个符号的统计特性，如概率大的符号用短码，如例2-2-1可用1或2比特，而对概率小的X7，X8用较长的码，这样的大量信源符号编成码后平均每个信院符号所需的输出符号数就可以降低，从而提高编码效率。下面分别给出单个符号（L=1）和符号序列的变长编码定理。 单个符号变长编码定理： 若一离散无记忆信源的符号熵为H（X），每个信源符号用M进制码元进行变长编码，一定存在一种无失真编码方法，其码字平均长度满足下列不等式 +1 （2-1-6） 离散平稳无记忆序列变长编码定理：对于平均符号熵为HL（X）的离散平稳无记忆源，必存在一种无失真编码方法，使平均信息率满足不等式 HL（X）HL（X）+ （2-1-7）其中为任意小数。 可从（2-1-6）式推出（2-1-7）式。设用进制码元作变长编码，序列长度为L个信源符号，则由2-3-1式可以得到平均码字 满足下列不等式 +1 已知平均输出信息率为 = 则 HL（X） HL（X）+ 当L足够大时，可使，这就得到了（2-1-8）。 用变长编码来达到相当高的编码效率，一般要求的符号长度L可以比定长编码小得多。从（2-1-8）式可得编码效率的下界： （2-1-8）例如用二进制，m=2, =1,仍用前面的例（2-1-6），H（X）=2.55比特/符号，如要求 90 ，则 就可以了。编码效率总是小于1的，我们可以用它来衡量各种编码方法的优劣。另外为了衡量各种编码方法最佳的差距，定义码的剩余度为 （2-1-9）例 2-1-2 设离散的无记忆信源、概率空间为 其信源为 比特/符号 若用二元定长编码（0，1）来构造一个即时码： 。这时平均码长 =1二元码符号/信源符号编码效率为 输出的信息率为 R=.0811比特/二元码符号 再对长度为2 的信源序列进行变长编码，其即时码如表2-3所示表 2-3 L=2时信源序列的变长编码序列序列概率即时码序列序列概率即时码x1x29/160 x2x13/16110 x1x23/1610 x2x11/16111这个码字平均长度 二元码符号/信源符号每个单一符号的平均码长 二元码符号/信源符号 其编码效率比特/二元码符号R2=0.961比特/二元码符号可见编码复杂了些，但信息传输率有提高。 用同样的方法可进一步将信源的长度增加，L=3或L=4，对这些信源序列进行X进行编码，并求出其编码效率为 这时信息传输率分别为 R3=0.985比特/二元码符号如果对这一信源采用定长二元编码，要求编码效率达到96时，允许译码错误概率-5 。则根据前面所学，自信息的方差 2H（X） 很明显，定长编码需要的信源序列长，使得码表很大，且总存在译码差错；而变长码编码效率达到96 时，只需L=2。因此用变长码编码时，L不需要很大就可达到相当高的编码效率，而且可实现无失真编码。2.2常用编码方法凡是能载荷一定信息量，且码字的平均长度最短，可分离的变长码字集合都可称为最佳码。为次必须将概率大的信息符号编以短码字，概率小的符号编以长的码字，使得平均码字长度最短。能获得最佳码方法主要有：香农（Shannon）,费诺 (Fano)，哈夫曼(Huffman)编码和算术编码等。下面我们分别介绍这几种编码方法。2.2.1香农编码方法 香农第一定理指出了平均码长与信源之间的关系，同时也指出了可以通过编码使平均码长达到极限值，这是一个很重要的极限定理。如何构造这种码？香农第一定理指出，选择每个码字的长度K满足下式 就可以得到这种码。这种编码称为香农编码。香农编码法多余度稍大，实用性不大，但有重要的理论意义。编码方法如下：(1) 将信源消息符号按其出现的概率大小依次排列 p(x1) p(x2) p(xn) (2) 确定满足下列不等式的整数码长Ki: 2p(xi) Ki2p(xi)+1(3) 为了编成唯一可译码，计算第i个消息的累加概率 (4) 将累加概率变换成二进制数。(5) 取二进数的小数点后Ki位即为该消息符号的二进制码字。表2-4 香农编码过程信源消息符号xi符号概p(xi)累加概Pi-2p(xi)码字长Ki码字x10.2002.343000x20.190.22.413001x30.180.392.483011x40.170.572.563100x50.150.742.743101x60.100.893.3441110x70.010.996.6671111110香农编码的C实现：从上面可看出，香农编码按照概率从大到小排序，进行类加取对数实现。2.2.2费诺编码方法费诺编码属于概率匹配编码，但他不是最佳的编码方法。编码过程如下：(1) 将信源消息符号按其出现的概率大小依次排列： p(x1) p(x2) p(xn)。(2) 将依次排列的信源符号按概率值分两大组，使两个组的概率之和近于相同，并对各组赋予一个二进制码元“0”和“1”。(3) 将每一大组的信源符号进一步再分成两组，使划分的两组的概率之和近于相同，并又赋予两个组一个二进制符号“0”和“1”。(4) 如此重复，直至每个组只剩下一个信源符号为止。(5) 信源符号所对应的码字即为费诺码。下面再以上面的例子来求费诺码。编码过程参见表2-5。该费诺码的平均码长 码元/符号 信息传输速率 =0.953比特/码元显然费诺码要比上述香农码的平均码长小，消息传输速率大，说明编码效率高。 表2-5 费诺编码过程消息符号 xi各个消息概率p(xi)第一次分组第二次分组第三次分组第四次分组二元码字码长KiX10.20 00002X20.19100103X30.1810113X40.1710102X50.15101103X60.101011104X70.01 1111142.2.3 哈夫曼编码方法(1) 将信源消息符号按其出现的概率大小依次排列：P(x1) p(x2) p(xn)(2)取两个小概率最小的字母分别配以0和1两码元,并将这两个概率相加作为一个新字母的概率,与未分配的二进制符号的字母重新排队。(3)对重新排后的两个概率最小符号重复步骤(2)的过程。(4)不断继续上述过程,直到最后两个符号配以0和1为止。(5)从最后一级开始,向前返回得到各个信源符号所对应的8元符序列,即相应的码字。我们还是用上面的例子中的信源, 哈夫曼编码过程如表2-6所示。表 2-6 哈夫曼编码过程信源符号xi概率p(xi)编码过程码字Wi码字Ki x10.2010 2 x20.19 11 2 x30.18 0003 x40.17 0013 x50.15 0103 x60.10 01104 x70.01 01114该哈夫曼编码的平均码长为 =2.72 码元/符号信息传输速率 =0.9596 比特/码元 由此可见, 哈夫曼码的平均码长最小，消息传输速率最大,编码效率最高。哈夫曼编码方法得到的码并非是唯一的。 造成非唯一的原因如下：（1） 每次对信源缩减时,赋予信源最后两个概率小的符号，用0和1是可以任意的,所以可以得到不同的哈夫曼码,但不会影响码字的长度。（2） 对信源进行缩减时, 两个概率小的符号合并后的概率与其他信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可以获得较小的码方差。下面举例来说明。 例 2-2-1 设有离散无记忆信源 可有两种哈夫曼编码方法，如表 （2-7）和表（2-8）所示，码树见图（2-2）(a) 和 (b) 所示。 表2-7 哈夫曼编码方法一信源符号xi概率p(xi)编码过程码字Wi码字Ki x10.4 0.4 0.40 0.6 01.0 0.2 0.40 0.41 0.20 0.210 0.211 11 x20.2102 x30.20003 x40.100104 x50.100114 表2-8 哈夫曼编码方法二信源符号xi概率p(xi)编码过程码字Wi码字Ki x10.4 0.4 0.4 0.6 01.0 0.2 0.4 0 0.4 1 0.2 0 0.2 10 0.211 002 x20.2102 x30.2112 x40.10103 x50.10113 （a） (b)图2-2 哈夫曼树由表（2-2-4）和表（2-2-5）给出哈夫曼码的平均码长相等： 码元/符号编码效率也相等： 但是两种码的质量不完全相同,可用码方差来表示： 2l=E(ki-)2= (ki)2表（2-2-4）中哈夫曼码的方差为2 =1.36；表（2-2-5）中哈夫曼码的方差为2 =0.16。 因此可见，第二种哈夫曼编码方法得到的码方差比第一种哈夫曼编码方法得到的码方差小许多。故第二种哈夫曼码的质量比较好。下面看下哈夫曼编码的具体编码过程：若执行自定义编译，请输入Y继续。否则程序将结束。请输入哈夫曼编码测试数据，注意小写，空格由大写字母T代替，并且字符数小于27。如下输入aTbTcTb设T秒内有N个信源符号输出，信源输出符号速率S=N/T，若符号的平均码长为，则信道传输速率 R=S （2-2-1）时可以满足条件。 N个码字的长度分别为Ki,i=1,2,N,即在此期间输入存储器比特，输出至信道RT比特，则在存储器内还剩下X比特， （2-2-2） 已知K i是随机变量，其均值和方差分别为 （2-2-3）变长编码可以无失真地译码，这是理想的情况。如果这种变长码由信道传送时，有某一个符号错了。因为一个码字前面有某个字母错了，就可能误认为是另一个码字而点断，结果后面一系列的码字也会译错，这常称为差错的扩散。当然也可以采用某些措施，使错了一段以后，能恢复正常的码字分离和译码，这一般要求在传输过程中差错很少，或加纠错用的监督码位，但是这样一来又增加信息率。前面介绍的几种最佳编码都能实现，因为它们具体规定了编码的方法，能使无失真编码的效率非常接近于1。其他如定长编码以及以后将要讨论的限失真信源编码和信道编码，都还没有具体的实用编法，只是证明了存在性和大致方法。所以在压缩信源信息率的实用设备中，哈夫曼编码还是比较常用的。2.2.4 算术编码方法以上所讨论的无损编码，都是建立在符号和码字相对应的基础上的，这种编码通常称为块码或分组码。此时符号应是多元的，而且不考虑符号相关性。为了克服这种局限性，就需要跳出分组码的范畴，研究非分组码的编码方法，算术码为其中之一。算术编码的基本思路是：从全序列出发，将各个信源的概率映射到0，1区间上，使每个序列对应这区间的一点，也就是一个二进制的小数。这些点把0，1区间分成许多小段，每个小段的长度等于某一序列的概率。再在段内取一个二进制小数，其长度可与该序列的概率匹配，达到高效率的编码目的。 如果信源符号集为A=a0,a1,am-1,信源序列X=(x0,x1,xl,xL-1),xlA,共有mL种可能序列。由于考虑是全序列，也许是整页纸上的信息作为一个序列，因而序列长度L很大。实用中很难得到对眼序列的概率，只能从已知的信源符号概率P=p(a0),p(a1),p(am-1)=p0,p1,pr,pm-1中递推得到。定义各符号的累积概率为 （2-2-4） 显然，由上式可得P0=0，P1= p0，P2=p0+ p1等，而且pr =Pr+1Pr （2-2-5）由于Pr+1和Pr都是小于1的正数，可用0，1区间内的两个点来表示，则Pr就是这两点间的小区间的长度，如图2-3所示。 图2-3信源符号概率和累积概率不同的符号有不同的小区间，它们互不重叠，所以可将这种小区间内的任何一点作为该符号的代码。以后将计算这代码所需的长度，使之能与其概率匹配。实用中，采用积累概率P（S）表示码字C（S），符号概率p(S)表示状态区间A（S），则有 C（Sr）= C（S）+ A（S）Pr A（Sr）= A（S）pr （2-2-9） 对于二进制符号组成的序列，r =0，1。实际编码过程是这样的：先置两个存储器C和A，起始时可令 A（）=1，C=（）=0其中代表空集。每输入一个信源符号，存储器C和A就按照（2-2-9）式进行更新一次 ，直至程序结束，就可将存储器C的内容作为码字输出。由于A（S）是递增的，而这增量随着序列的增长而减小，因为这增量是序列的概率与信源符号的积累概率的乘积；所以C的前面就位一般已固定，在以后计算中不会被更新，因而可以输出。只需保留后面几位用做更新。译码也可逐位进行，与编码过程相似。例 2-4-1 有简单的四个符号a,b,c,d构成序列S=abda,各个符号及其对应概率如表2-4-1，算术编码过程如下： 设起始状态为空序列 ，则A（）=1，C（） =0。 表 2-9各符号及其对元概率符号符号概率pi符号累积概率Pj符号符号概率pi符号累积概率Pj a 0.100(1/2) 0.000 c 0.001(1/8) 0.110 b 0.010(1/4) 0.100 d 0.001(1/8) 0.111译码可通过对上述编码后的数值大小来比较进行，即判断码字C（S）落在哪个区间就可以得出一个相应的符号序列。根据递推公式的相反过程译出符号。具体译码顺序是后编的先译，故称为LIFO算术码，步骤如下： C（abda）=0.0101110.10,0.1) 第一个符号为a；放大至0，1)(Pa-1)：C（abda）21=0.101110.1,0.110)第二个符号为b；去掉累积概率Pb： 0.10111-0.1=0.00111放大至0，1)(Pb-1)：0.0011122=0.1110.111，1） 第三个符号为d；去掉累积概率Pd： 0.111-0.111=0放大至0，1)(Pd-1)：0 24=00,0.1) 第四个符号为a。算术编码从性能上看具有许多优点，特别是由于所需的参数很少，不象哈夫曼那样需要一个很大的码表，常设计成自适应算术编码来针对一些信源概率未知或非平稳情况。但是在实际实现时还有一些问题，如计算复杂性，计算的精度以及存储量等，随着这些问题的解决，算术编码正在进入实用阶段，但要扩大应用范围或进一步提高性能，降低造价，还需进一步改进。这就是我们下有章要介绍到的算术编码的改进。第3章 哈夫曼码和算术码的改进优化上一章所讲到的各种编码算法中,实用性较强的一般是算术码和哈夫曼码,但是在实际实现时也还是存在一些问题,如计算复杂性,计算的精度以及存储量等,因而,这两种编码方法还有待我们进一步去改进和优化。3.1哈夫曼编码算法的分析改进1. 基本概念（1）图像熵设图像灰度级序列a 1, a2，a n出现的概率集合为P 1,p2，p n，定义图像熵H为 （3-1-1）（2）平均码字长度设有n个图像灰度级(k =1, 2，,n), (k = 1, 2，n)为第k个图像灰度级的编码长度其相应出现的概率为(k= 1, 2，,n)，则该n个图像灰度级序列的编码长度为 （3-1-2）（3）平均偏离方差设图像灰度级序列(k =1, 2，,n), 其相应出现的概率为,(k= 1, 2，,n),(k = 1, 2，n)为第k个图像灰度级的编码长度, 该组灰度级序列的平均码长为R, 定义该组灰度级序列的平均偏离方差为 （3-1-3）2.Huffman编码的具体方法 先按出现的概率大小排队，把2个最小的概率相加，作为新的概率和剩余的概率重新排队.再把最小的2个概率相加，再重新排队，直到最后变成1.每次相加时都将“0”和“1”赋以相加的2个概率，读出时由该符号开始一直到最后的1，将路线上遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的Huffman编码。例1设有7个图像灰度级序列，按出现概率的大小顺序进行排序(见表3-1-1)，其编码见图（3-1）表3-1 7个图象灰度的出现概率灰度等级概率灰度等级概率a1 0.20 a5 0.15a2 0.19 a6 0.10a3 0.18 a7 0.01a4 0.17图3-1 表（3-1）的编码表1编码的平均码长R= 0.202+ 0.192+ 0.183+0. 173 +0.154+0.104+0.014=2.72 bit.相应的图像熵为H=(0.20lb0.20+0.19lb0.19+0.18lb0.18+0.17lb0.17+0.15lb0.15+0.10lb0.10+0.01lb0.01)=0.4644+0.4552+0.4453+0.4346+0.4106+0.3322+0.0664=2.61性质1 在Huffman编码中，平均码字长度等于其内部结点值的和。由性质1易得性质2。性质2 同一组灰度级序列的多种的平均码长相等。3Huffman编码的不唯一性因为Huffman编码的步骤是任取的，因此编码不唯一。 例2设有8个图像灰度级序列，按出现概率的大小进行排序(见表3-1-2)。对于该组图像灰度级序列，下面给出3种不同的H uffman编码，由于其图像熵只与图像灰度级序列出现的概率有关，因此这3种编码的图像熵皆为H=(0.46lb0.46+0.15lb0.15+0.15lb0.15+0.09lb0.09+0.06lb0.06+0.03lb0.03+0.03lb0.03+0.03lb0.03)=0.515338+0.410550+0.410550+0.312651+0.243534+0.151767+0.151767+0.151767=2.35编码方案1见图（3-2）。表3-2 8个图像灰度级的出现概率灰度等级概率灰度等级概率a1 0.46 a5 0.06a2 0.15 a6 0.03a3 0.15a7 0.03a4 0.09 a8 0.03 图3-2 表2的编码1 编码方案1的平均码长R = 0.461+0.15x3+0.153+ 0.093+0.065+ 0.0353= 2.38 bit.依次类推，编码方案2的平码长R= 0.46 1+ 0.153+ 0.153+ 0.094+ 0.064+ 0.034+ 0.035 2= 2. 38 hit。4对Huffman编码的讨论由以上计算可知，表2的编码方案的图像熵和平均码长均相同，现计算它们的平均偏离方差。编码1：D=0.46（1-2.38）2+0.15(3-2.38)22+0.09(3-2.38)2+0.06(5-2.38)2+0.03(5-2.38)23=2.06编码2: D=0.46（1-2.38）2+0.15(3-2.38)22+0.09(4-2.38)2+0.06(4-2.38)2+0.03(5-2.38)22=1.88由计算结果可知，选择不同的编码方案，所得到的平均偏离方差不同。当图像灰度级出现的概率集合固定时，平均偏离方差卞要取决于由Huffman的构造过程中叶结点到根结点的路径长度，从而得出定理1。定理1在H uffm an编码过程中，当出现2个以上最小概率的结点时，若选择树中叶结点概率为最小者与叶结点概率为最大者进行合并，则得到相应编码的平均偏离方差为最小。5Huffman编码算法的优化 1) 先将各信源符号出现的概率由大到小排列；2) 按定理中的方法将最小的2个概率相加，形成1个新的概率集合，再按1)方法重排，如此反复进行直到只有2个概率为止； 3) 分配码字。哈夫曼(huffman)树，又称最优树，是带权路径长度最小的二叉树。树的带权路径长度是树中所有叶子结点的带权路径长度之和，通常记，其中n为叶子结点数目，为第i个叶子结点的权值，为第i个叶子结点的路径长度。根据这个定义，求取哈夫曼树的带权路径长度(WPL) 必须获取各个叶子结点的权值和所处路径长度。通过对哈夫曼算法的研究，提出一种求取哈夫曼树WPL的改进方法。5.1 求WPL的改进方法由于以下条件成立:(1) 叶子结点i的带权路径长度 ，即w1连续相加次。(2) 构造哈夫曼树过程中，选取权值最小的结点作为左右子树构造一棵新的二叉树，且新置的二叉树的根结点权伯为其左右子树上根结点的权值之和。 新置结点的产生，叶子结点的权值被累计相加到这结点的权值中，等价于叶子结点的权值被相乘了相应次数。所以得到改进求取WPL的方法为：相加所有新置结点的权值即为该哈夫曼树的WPL。例如3:v,e,r,y,g,o,a,d在某个文件中出现的次数分别为5,29,7,8,14.23.3.11，对这8个结点构造哈夫曼树，得到结果如图（3-3）所示，生成哈夫曼树的状态图如图（3-4）所示。传统求解WPL的方法为：根据图（