最佳变长编码方式的探究

1、ZHENGZHOU UNIVERSITY OF INDUSTRIAL TECHNOLOGY最佳变长编码方式的探究论文题目：最佳变长编码方式的探究专业：通信工程班 级：14级通信工程 学 号：1401120125姓 名：吴万强指导教师:魏平俊2016年12月最佳变长编码方式的探究吴万强（郑州工业应用技术学院信息工程学院14级通信工程班 河南 郑州）摘要：信源的编码方法提高了通信的有效性。信源的编码方法分为定长编码 和变长编码，定长编码要实现无失真，需要的编码长度大，效率不高；变长编码 的编码长度不需要很大就可以达到相当高的编码效率，而且可以实现无失真编 码。香农编码、费诺编码和霍夫曼编码是常见的

2、离散无记忆信源编码方法。关键字：定长编码变长编码香农编码费诺编码霍夫曼编码Abstract： Encoding method improves the effectiveness of the source of communication. Source coding method is divided into fixed-length coding and variable length coding, fixed-length coding to achieve distortion requires a large code length,the efficiencyis not h

3、igh;variabl el engthcod e lengthcodingcanbe achieved without requiring a high relatively high coding efficiency, and can achievelosslessencoding.Shannoncoding,FennocodingandHuffmancodingisa commondiscretememoryl esssourcecodingmethods.Keyword: Fixed-bngth encoding Variable length coding Shannon codi

4、ng Fennocoding Huffmancoding1引言人类社会的生存和发展无时不刻都离不开信息的获取、传递、再生、控制和 利用。信息论正式一门把信息作为研究对象的科学，以揭示信息的本质特性和规 律为基础，应用概率论。随机过程和树立统计等方法来研究信息的存储、传输、 处理、控制和利用。它主要研究如何提高信息系统的可靠性、有效性、保密性和 认证性，以使信息系统最优化。许多科学技术问题（如无线电通讯、电视、遥测、 图像和声音识别等）都必须以信息论为理论指导才能很好地解决。信息论的研究 对象又可以是广义的信息传输和信息处理系统。从最普通的电报、电话、传真、 电视、雷达、声纳，一直到各类生物神经

5、的感知系统，以及大到人类社会系统， 可以用同一的信息论观点加以阐述，都可以概括成某种随机过程或统计学的数 学模型加以深入研究。2发展历程信息论从诞生到今天，已有半个多世纪的历程，现已成为一门独立的理论学 科。回顾它的发展历史，可以知道理论是如何从实践中经过抽象、概括、提高而 逐步形成的。2.1信息论形成的背景和基础信息论是在长期的通信工程实践和理论研究的基础上发展起来的。电的通信 系统(电信系统)已有170多年的历史了。法拉第(M. Faraday)于1820年一1830 年期间发现电磁感应的基本规律后，不久莫尔斯(F. B. Morse)就建立起电报系 统(18321835)。1876年，贝

6、尔(A. G. BELL)又发明了电话系统。1864年麦克 斯韦(Maxell)预言了电磁波的存在，年赫兹(H. Hertz)用实验证明了这一预言。 接着1895年英国的马可尼(G.Marconi)和俄国的波波夫(A. C.HoHoB)发明了 无线电通信。随着工程技术的发展，有关理论问题的研究也逐步深入。1832年莫尔斯电 报系统中高效率编码方法对后来香农的编码理论是有启发的。1885年凯尔文 (L.Kelvin)曾经研究过一条电缆的极限传信率问题。1922年卡逊(J. R. Carson) 对调幅信号的频谱结构进行了研究，并建立了信号频谱概念。1924年奈奎斯特 (H. Nyquist)指出

7、，如果以一个确定的速度来传输电报信号，就需要一定的带宽。 他把信息率与带宽联系起来了。1928年哈特莱(R. V. Hartley)发展了奈奎斯 特的工作，并提出把消息考虑为代码或单语的序列。他的工作对后来香农的思想 是有影响的。1936年阿姆斯特朗(E. H. Armstrong)认识到在传输过程中增加带宽的办法 对抑制噪声干扰肯定有好处。根据这一思想他提出了宽偏移的频率调制方法，该 方法是有划时代意义的。20世纪40年代初期，由于军事上的需要，维纳在研究 防空火炮的控制问题时，提出了“平稳时间序列的外推，内插与平滑及其工程应 用”的论文。他把随机过程和数理统计的观点引入通信和控制系统中来，

8、揭示了 信息传输和处理过程的统计本质。他还利用早在30年代初他本人提出的“广义 谐波分析理论”对信息系统中的随机过程进行谱分析。这就使通信系统的理论研 究面貌焕然一新，产生了质的飞跃。2.2 Shannon信息论的建立和发展1948年6月和10月，Shannon在贝尔实验室出版的著名的贝尔系统技术 杂志上发表了两篇有关通信的数学理论的文章。在这两篇论文中，他用概率 测度和树立统计的方法系统地讨论了通信的基本问题，首先严格定义了信息的度 量一熵的概念，又定义了信道容量的概念，得出了几个重要而带有普遍意义的结 论，并由此奠定了现代信息论的基础。Shannon理论的核心是：揭示了在通信系统中采用适当

9、的编码后能够实现高 效率和高可靠地传输信息，并得出了信源编码定理和信道编码定理。从数学观点 看，这些定理是最优编码的存在定理。但从工程观点看，这些定理不是结构性的， 不能从定理的结果直接得出实现最优编码的具体途径。然而，它们给出了编码的 性能极限，在理论上阐明了通信系统中各种因素的相互关系，为人们寻找出最佳 通信系统提供了重要的理论依据。而其理论到目前主要经历了以下几个方面的发展：Shannon信息理论的数学 严格化、无失真信源编码定力和技术的发展、信道纠错编码的发展、限失真信源 编码的提出和发展、多用户、网络信息论的发展、信息保密与安全理论的提出与 发展，从此以后，纠错码和密码学相结合的研究

10、迅速发展起来。3变长编码在学过信息论与编码技术以后，对这方面内容已有了基础的了解。为了进行 更深入的了解，在查阅了很多资料后，可知通信的根本问题是如何将信源输出的 信息在接收端的信宿精确地或近似地复制出来，而这最重要的一步就是信源的编 码，一个好的开端才能为以后的传输及接受、解码提供有利得条件。首先要了解什么是信源编码。为了减少信源输出符号序列中的剩余度、提高 符号的平均信息量，对信源输出的符号序列所施行的变换。具体说，就是针对信 源输出符号序列的统计特性来寻找某种方法，把信源输出符号序列变换为最短的 码字序列，使后者的各码元所载荷的平均信息量最大，同时又能保证无失真地恢 复原来的符号序列。既

11、然信源编码的基本目的是提高码字序列中码元的平均信 息量，那么，一切旨在减少剩余度而对信源输出符号序列所施行的变换或处理， 都可以在这种意义下归入信源编码的范畴，例如过滤、预测、域变换和数据压缩 等。一般来说，减少信源输出符号序列中的剩余度、提高符号平均信息量的基本 途径有两个使序列中的各个符号尽可能地互相独立使序列中各个符号的出现概率尽可能地相等。前者称为解除相关性，后者 称为概率均匀化。在通信过程中，如何在不失真或允许一定失真条件下，用尽可 能少的符号来传送信源信息，提高信息传输率；在信道受干扰的情况下，如何增 加信号的抗干扰能力，同时又使得信息传输率最大。这就产生了多种信源编码方 式。为了

12、有效传播信息，最理想状态即为无失真传输。无失真信源编码的实质： 对离散信源进行适当的变换，是变形后形成的新的码符号信源(信道的输入信源) 尽可能为等概率分布，以使新信源的每个码符号平均所携带的信息量达到最大， 使信道的信息传输率R达到信道容量C，实现信源与信道的统计匹配。为了衡量各种编码是否达到极限情况，定义变长码的编码效率为门=4B。L通过编码效率n来衡量各种编码性能的优劣。为了衡量各种编码与最佳编码的差 距，定义的剩余度为：1-门=1-4B，信息传输率定义为：R = =门。LL注意：虽然R与n在数值上相同，但它们的单位不同，编码效率n没有单位， 而信息编码传输率R的单位是比特/码符号，在无

13、失真信源编码中又分为定长编 码、变长编码机最佳变长编码。下面便是对定长编码与变长编码的解释。3.1定长编码定理定理1 (等长信源编码定理)一个熵为H (s)的离散无记忆信源，若对其N 次扩展信源等长r元编码，码长为1，对于任意e大于0,只要满足- H(S) +， N log r当N无穷大时，则可以实现几乎无失真编码，反之，若： H(S)-2s，则不 N log r可能实现无失真编码，当N趋向于无穷大时，译码错误率接近于1。在定长编码中，K是定值，编码的目的即为找到最小的L值。要实现无失真 的信源编码，不但要求信源符号与码字是一一对应的，而且还要求有码字组成的 码符号序列的逆变换也是唯一的。由定

14、长编码定理可知，当编码器容许的输出信 息率，也就是当每个信源符号必须输出的码长是L=Kl/log m。由定理表明，只 要码字所能携带的信息量大于信源序列输出的信息量，则可以使传输几乎无失 真，但是条件是L足够大。这就为传输带来了很大的麻烦，并且实现起来很困难， 并且编码效率也不高。而要达到编码效率接近1的理想编码器虽有存在性，但在 实际上时不可能的，因为1非常大，无法实现。由此而产生了变长编码。3.2变长编码定理定理2无失真变长信源编码定理(香农第一定理)：离散无记忆信源S的N 次扩展信源SN其熵为H(SN)，并且编码器的码元符号集为A： L，。2，白对信源SN进行编码，总可以找到一个编码方法

15、，构成单义可译码，使信源S中每个符号所需要的平均码长满足 些 匕 些 +1。当趋于无穷是，则得： log r N logr Nlim L=H(S)这个定理是香农信息论中非常重要得一个定理，他指出，要做到无 N 3失真的信源编码，信源每个符号所需要的平均码元数就是信源的熵值，如果小于 这个值，则唯一可译码不存在，可见，熵是无失真信源编码额极限值。定理还指 出，通过对扩展信源进行编码，当N趋向于无穷时，平均码长可以趋近该极限值。由 H(S) 匕 匕 log r H(S)nlog r 就是编码后 log r N logr NNN每个信源符号所携带的平均信息量。定义输出信息率：R =她logr。香农第

16、一 N定理可以表述如下：若RH(S)就存在唯一可译变长码，若RH(S)则不存在可译 变长码。定义：变长编码效率为门=史纳，在变长编码中，码长L是变化的，可 Ln log r根据信源各个符号的统计特性，对概率大的符号用短码，而对概率小的符号用长 码。这样大量信源符号编成码后，平均每个信源符号所需的输出符号数就可以降 低，从而提高编码效率。用变长编码来达到相当高的编码效率，一般所要求的符 号长度L可以比定长编码小得多的多。很明显，定长码需要的信源序列长，这使 得码表很大，切总存在译码差错。而变长码要求编码效率达到96%时，只需L=2 因此用变长码编码时，L不需要很大就可达到相当高的编码效率，而且可

17、实现无 失真编码。并且随着信源序列长度的增加，编码效率越来越接近于1，编码后的 信息传输率R也越来越接近于无噪无损二元对称信道的信道容量C=1bit/二元码 符号，达到信源与信道匹配，使信道得到充分利用。但变长编码方式也有优劣的 区分，下面就变长编码即香农编码，费诺编码，霍夫曼编码进行比较分析。4三种变长编码的定义与过程4.1香农编码方法香农第一定理指出了平均码长与信源之间的关系，同时也指出了可疑通过编 码使平均码长达到极限值，这是一个很重要的极限定理。香农第一定理指出，选 择每个码字的长度Li满足下式：-log p（Si） Li p *p。12q（2）按照上式（1）计算出每个信源符号的码长L

18、i。（3）为了变成唯一可译码，计算第i信源符号的累加概率：Gi = t1 pk。k=1（4）将累加概率Gi用二进制数表示。（5）取Gi对应二进制数的小数点后Li位构成该信源符号的二进制码字。由此可见香农编码法多余度稍大，实用性不强，但他是依据编码定理而来， 因此具有重要的理论意义。4.2费诺编码方法费诺编码属于概率编码，但不是最佳的编码方法。只有当信源的概率分布呈 现p （Si） = r顼分布形式的条件下，才能达到最优码的性能。二元费诺码的编码步骤如下：（1）信源符号以概率递减的次序排列。（2）将排列好的信源符号按概率值划分成两大组，使每组的概率之和接近 于相等，并对每组各赋予一个二元符号0和

19、1。（3）将每一大组的信源符号再分成两组，使划分后两大组的概率之和接近 于相等，再分别赋予一个二元符号。（4）依次下去，直至每个小组只剩下一个信源符号为止。（5）信源符号所对应的码字即为费诺码。针对同一信源，费诺码要比香农码的平均码长小，消息传输速率大，编码效 率高。费诺码具有以下性质：（1）费诺码的编码方法实际上是一种构造码树的方法，所以费诺码是即时码。（2）费诺码考虑了信源的统计特性，使概率大的信源符号能对应码长较短的 码字，从而有效地提高了编码效率。（3）费诺码不一定是最佳码，因为费诺码编码方法不一定能使最短码得到充 分利用。当信源符号较多时，若有一些符号概率分布很接近，分两大组的组合方

20、 法就会很多。可能某种分大组的结果，会后面小组的“概率和”相差较远，从而 使平均码长增加。4.3霍夫曼编码方法1952年，霍夫曼（Huffman）提出了一种构造最佳码的方法，这是一种最佳 的逐个符号的编码方法，一般就称作霍夫曼码。二元霍夫曼编码设S = y ,s ,.、，其对应的该概率分布为P（s ） = p ,p -p ，则其编码步12 Qi12, q骤如下：（1）将q个信源符号按概率递减的方式排列。（2）用0,1码符号分别表示概率最小的两个信源符号，并将这两个概率最 小的信源符号合并成一个新的符号，从而得到只包含q-1个符号的新信源，称作 S信源的缩减信源S1O（3）将缩减信源、】仍按概率

21、大小以递减次序排列，再将其最后两个概率最 小的符号合并成一个符号，并分别用0,1码符号表示，这样又形成了由q-2个符 号构成的缩减信源S2。（4）依次继续下去，直到缩减信源只剩下两个符号为止，将这最后两个符 号分别用0，1码符号表示。（5）从最后一级缩减信源开始，向前返回，沿信源缩减过程的反方向取出 所编的码元，得出个信源符号所对应的码符号序列，即为所对应信源符号的码字。按霍夫曼码的编码方法，可知这种码有如下特征。（1）它是一种分组码：各个信源编码都被映射成一组固定次序的码符号。（2）它是一种唯一可解码：任何码符号序列只能以一种方式译码。（3）它是一种即时码：由于代表信源符号的节点都是终端节点

22、，因此其编 码不可能是其他终端节点所对应的编码的前缀，即霍夫曼码所得的码字为即时 码。所以，一串码符号中每个码字都可不考虑其后的码符号直接解码出来。霍夫曼的译码：对接收的霍夫曼码序列可通过从左到右检查各个符号进行译 码。例如本例，若接收到的霍夫曼码序列为0001 10 11 010 10 11，可译为信 源符号序列a a a a a a。6 2 1 4 2 1说明：（1）霍夫曼码是一种即时码，可用码树形式进行表示。（2）每次对缩减信源最后两个概率最小的符号，用0,1码可以使任意的， 所以可得到不同的码，但码长Li不变，平均码长也不变。（3）当缩减信源中缩减合并后得到的新符号的概率与其他信源符号

23、概率相 同时，从编码方法上来说，它们概率的排序是没有限制的，因此也可得到不同的 码。所以，对给定信源，用霍夫曼码方法得到的码并非唯一，但平均码长不变。5三种变长编码的实例分析与比较下面便通过两个例子进行说明5.1例题1设一信源符号有6个信源符号a,b,c,d,e,f，其概率分布为0.32、0.22、0.18、 0.16、0.08、0.04。通过计算可得到此信源的熵为:H(S)= 一 p(a)log p(a)二2.3526 (比特符号) i=1计算平均码长的公式L = p(a1)l C元码符号符号)i=15.1.1用香农编码方式香农码编码过程信 源符号符号概率p (a,)累加概率尸Gi-log

24、p(ai)码字长度Li码 字Gi 对应二 进制数a0.3201.642000.00000b0.220.322.1830100.01000c0.180.542.4731000.10000d0.160.72.631010.1240100e0.080.83.641110.11100f0.040.964.65111100.11110信源的平均码长为：L=Pj =2.84（二元码符号符号） i=1编码效率：n=H (S) /L=82.8%可以看出香农编码的效率并不高。5.1.2用费诺码编码方式费诺码编码过程信 源符号 ai各 个消息 概率pi第 一次分 组第二次分组a0.300b0.21c0.110d0

25、.161e0.0f0.0第 三次分 组第 四次分 组元码字码长Li0020121020110310111411114信源的平均码长为：L=P（a）l =2.4（二元码符号符号）i=1编码效率：n=H (S) /L=97.9%费诺编码的效率有明显的提高。5.1.3霍夫曼码编码方式霍夫曼编码过程徉提1:六a:，的j. j2 :. 2i：.2：UI：:i：2:j. j2 ：,22L业 L业匚、i：, I LE：d 112C：.1Ej. J Mti：.22 i 二i：.2E I112二：.lc1/ :,盖、匚住11-e：,i：EI j.12 1二:1二信源的平均码长为：L=U P(a =2.4(二元码

26、符号符号) i=1编码效率：n=H(S)/L=98.0%5.2例题2设一信源符号有6个信源符号a,b,c,d,e,f,g其概率分布为0.20,0.19,0.18,0.17,0.15,0.10,0.01通过计算可得到此信源的熵为：。元码符号符号)H (S) = -27 p(a )logp(a ) =2.61 (比特符号 i=1计算平均码长的公式L = 2 p(a )l1 i i=15.2.1香农编码过程信源 符号符 号概率累加-log pla)码字 长度11码字Gi对应二进制P (a,)概率G.数a0.2002.3430000.00000b0.190.22.4130010.00c0.180.392.4830110.0110d0.170.572.5631000.1001e0.150.742.7431010.10f0.100.893.34411100.11100g0.010.996.66711111100.1111110香农编码过程L=兄P(ai)li =3.14码符号信源