最佳變長(zhǎng)編碼方式的探究

1、ZHENGZHOU UNIVERSITY OF INDUSTRIAL TECHNOLOGY最佳變長(zhǎng)編碼方式的探究論文題目：最佳變長(zhǎng)編碼方式的探究專業(yè)：通信工程班 級(jí)：14級(jí)通信工程 學(xué) 號(hào)：1401120125姓 名：吳萬(wàn)強(qiáng)指導(dǎo)教師:魏平俊2016年12月最佳變長(zhǎng)編碼方式的探究吳萬(wàn)強(qiáng)（鄭州工業(yè)應(yīng)用技術(shù)學(xué)院信息工程學(xué)院14級(jí)通信工程班 河南 鄭州）摘要：信源的編碼方法提高了通信的有效性。信源的編碼方法分為定長(zhǎng)編碼 和變長(zhǎng)編碼，定長(zhǎng)編碼要實(shí)現(xiàn)無(wú)失真，需要的編碼長(zhǎng)度大，效率不高；變長(zhǎng)編碼 的編碼長(zhǎng)度不需要很大就可以達(dá)到相當(dāng)高的編碼效率，而且可以實(shí)現(xiàn)無(wú)失真編 碼。香農(nóng)編碼、費(fèi)諾編碼和霍夫曼編碼是常見(jiàn)的

2、離散無(wú)記憶信源編碼方法。關(guān)鍵字：定長(zhǎng)編碼變長(zhǎng)編碼香農(nóng)編碼費(fèi)諾編碼霍夫曼編碼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引言人類社會(huì)的生存和發(fā)展無(wú)時(shí)不刻都離不開(kāi)信息的獲取、傳遞、再生、控制和 利用。信息論正式一門(mén)把信息作為研究對(duì)象的科學(xué)，以揭示信息的本質(zhì)特性和規(guī) 律為基礎(chǔ)，應(yīng)用概率論。隨機(jī)過(guò)程和樹(shù)立統(tǒng)計(jì)等方法來(lái)研究信息的存儲(chǔ)、傳輸、 處理、控制和利用。它主要研究如何提高信息系統(tǒng)的可靠性、有效性、保密性和 認(rèn)證性，以使信息系統(tǒng)最優(yōu)化。許多科學(xué)技術(shù)問(wèn)題（如無(wú)線電通訊、電視、遙測(cè)、 圖像和聲音識(shí)別等）都必須以信息論為理論指導(dǎo)才能很好地解決。信息論的研究 對(duì)象又可以是廣義的信息傳輸和信息處理系統(tǒng)。從最普通的電報(bào)、電話、傳真、 電視、雷達(dá)、聲納，一直到各類生物神經(jīng)

5、的感知系統(tǒng)，以及大到人類社會(huì)系統(tǒng)， 可以用同一的信息論觀點(diǎn)加以闡述，都可以概括成某種隨機(jī)過(guò)程或統(tǒng)計(jì)學(xué)的數(shù) 學(xué)模型加以深入研究。2發(fā)展歷程信息論從誕生到今天，已有半個(gè)多世紀(jì)的歷程，現(xiàn)已成為一門(mén)獨(dú)立的理論學(xué) 科?；仡櫵陌l(fā)展歷史，可以知道理論是如何從實(shí)踐中經(jīng)過(guò)抽象、概括、提高而 逐步形成的。2.1信息論形成的背景和基礎(chǔ)信息論是在長(zhǎng)期的通信工程實(shí)踐和理論研究的基礎(chǔ)上發(fā)展起來(lái)的。電的通信 系統(tǒng)(電信系統(tǒng))已有170多年的歷史了。法拉第(M. Faraday)于1820年一1830 年期間發(fā)現(xiàn)電磁感應(yīng)的基本規(guī)律后，不久莫爾斯(F. B. Morse)就建立起電報(bào)系 統(tǒng)(18321835)。1876年，貝

6、爾(A. G. BELL)又發(fā)明了電話系統(tǒng)。1864年麥克 斯韋(Maxell)預(yù)言了電磁波的存在，年赫茲(H. Hertz)用實(shí)驗(yàn)證明了這一預(yù)言。 接著1895年英國(guó)的馬可尼(G.Marconi)和俄國(guó)的波波夫(A. C.HoHoB)發(fā)明了 無(wú)線電通信。隨著工程技術(shù)的發(fā)展，有關(guān)理論問(wèn)題的研究也逐步深入。1832年莫爾斯電 報(bào)系統(tǒng)中高效率編碼方法對(duì)后來(lái)香農(nóng)的編碼理論是有啟發(fā)的。1885年凱爾文 (L.Kelvin)曾經(jīng)研究過(guò)一條電纜的極限傳信率問(wèn)題。1922年卡遜(J. R. Carson) 對(duì)調(diào)幅信號(hào)的頻譜結(jié)構(gòu)進(jìn)行了研究，并建立了信號(hào)頻譜概念。1924年奈奎斯特 (H. Nyquist)指出

7、，如果以一個(gè)確定的速度來(lái)傳輸電報(bào)信號(hào)，就需要一定的帶寬。 他把信息率與帶寬聯(lián)系起來(lái)了。1928年哈特萊(R. V. Hartley)發(fā)展了奈奎斯 特的工作，并提出把消息考慮為代碼或單語(yǔ)的序列。他的工作對(duì)后來(lái)香農(nóng)的思想 是有影響的。1936年阿姆斯特朗(E. H. Armstrong)認(rèn)識(shí)到在傳輸過(guò)程中增加帶寬的辦法 對(duì)抑制噪聲干擾肯定有好處。根據(jù)這一思想他提出了寬偏移的頻率調(diào)制方法，該 方法是有劃時(shí)代意義的。20世紀(jì)40年代初期，由于軍事上的需要，維納在研究 防空火炮的控制問(wèn)題時(shí)，提出了“平穩(wěn)時(shí)間序列的外推，內(nèi)插與平滑及其工程應(yīng) 用”的論文。他把隨機(jī)過(guò)程和數(shù)理統(tǒng)計(jì)的觀點(diǎn)引入通信和控制系統(tǒng)中來(lái)，

8、揭示了 信息傳輸和處理過(guò)程的統(tǒng)計(jì)本質(zhì)。他還利用早在30年代初他本人提出的“廣義 諧波分析理論”對(duì)信息系統(tǒng)中的隨機(jī)過(guò)程進(jìn)行譜分析。這就使通信系統(tǒng)的理論研 究面貌煥然一新，產(chǎn)生了質(zhì)的飛躍。2.2 Shannon信息論的建立和發(fā)展1948年6月和10月，Shannon在貝爾實(shí)驗(yàn)室出版的著名的貝爾系統(tǒng)技術(shù) 雜志上發(fā)表了兩篇有關(guān)通信的數(shù)學(xué)理論的文章。在這兩篇論文中，他用概率 測(cè)度和樹(shù)立統(tǒng)計(jì)的方法系統(tǒng)地討論了通信的基本問(wèn)題，首先嚴(yán)格定義了信息的度 量一熵的概念，又定義了信道容量的概念，得出了幾個(gè)重要而帶有普遍意義的結(jié) 論，并由此奠定了現(xiàn)代信息論的基礎(chǔ)。Shannon理論的核心是：揭示了在通信系統(tǒng)中采用適當(dāng)

9、的編碼后能夠?qū)崿F(xiàn)高 效率和高可靠地傳輸信息，并得出了信源編碼定理和信道編碼定理。從數(shù)學(xué)觀點(diǎn) 看，這些定理是最優(yōu)編碼的存在定理。但從工程觀點(diǎn)看，這些定理不是結(jié)構(gòu)性的， 不能從定理的結(jié)果直接得出實(shí)現(xiàn)最優(yōu)編碼的具體途徑。然而，它們給出了編碼的 性能極限，在理論上闡明了通信系統(tǒng)中各種因素的相互關(guān)系，為人們尋找出最佳 通信系統(tǒng)提供了重要的理論依據(jù)。而其理論到目前主要經(jīng)歷了以下幾個(gè)方面的發(fā)展：Shannon信息理論的數(shù)學(xué) 嚴(yán)格化、無(wú)失真信源編碼定力和技術(shù)的發(fā)展、信道糾錯(cuò)編碼的發(fā)展、限失真信源 編碼的提出和發(fā)展、多用戶、網(wǎng)絡(luò)信息論的發(fā)展、信息保密與安全理論的提出與 發(fā)展，從此以后，糾錯(cuò)碼和密碼學(xué)相結(jié)合的研究

10、迅速發(fā)展起來(lái)。3變長(zhǎng)編碼在學(xué)過(guò)信息論與編碼技術(shù)以后，對(duì)這方面內(nèi)容已有了基礎(chǔ)的了解。為了進(jìn)行 更深入的了解，在查閱了很多資料后，可知通信的根本問(wèn)題是如何將信源輸出的 信息在接收端的信宿精確地或近似地復(fù)制出來(lái)，而這最重要的一步就是信源的編 碼，一個(gè)好的開(kāi)端才能為以后的傳輸及接受、解碼提供有利得條件。首先要了解什么是信源編碼。為了減少信源輸出符號(hào)序列中的剩余度、提高 符號(hào)的平均信息量，對(duì)信源輸出的符號(hào)序列所施行的變換。具體說(shuō)，就是針對(duì)信 源輸出符號(hào)序列的統(tǒng)計(jì)特性來(lái)尋找某種方法，把信源輸出符號(hào)序列變換為最短的 碼字序列，使后者的各碼元所載荷的平均信息量最大，同時(shí)又能保證無(wú)失真地恢 復(fù)原來(lái)的符號(hào)序列。既

11、然信源編碼的基本目的是提高碼字序列中碼元的平均信 息量，那么，一切旨在減少剩余度而對(duì)信源輸出符號(hào)序列所施行的變換或處理， 都可以在這種意義下歸入信源編碼的范疇，例如過(guò)濾、預(yù)測(cè)、域變換和數(shù)據(jù)壓縮 等。一般來(lái)說(shuō)，減少信源輸出符號(hào)序列中的剩余度、提高符號(hào)平均信息量的基本 途徑有兩個(gè)使序列中的各個(gè)符號(hào)盡可能地互相獨(dú)立使序列中各個(gè)符號(hào)的出現(xiàn)概率盡可能地相等。前者稱為解除相關(guān)性，后者 稱為概率均勻化。在通信過(guò)程中，如何在不失真或允許一定失真條件下，用盡可 能少的符號(hào)來(lái)傳送信源信息，提高信息傳輸率；在信道受干擾的情況下，如何增 加信號(hào)的抗干擾能力，同時(shí)又使得信息傳輸率最大。這就產(chǎn)生了多種信源編碼方 式。為了

12、有效傳播信息，最理想狀態(tài)即為無(wú)失真?zhèn)鬏敗o(wú)失真信源編碼的實(shí)質(zhì)： 對(duì)離散信源進(jìn)行適當(dāng)?shù)淖儞Q，是變形后形成的新的碼符號(hào)信源(信道的輸入信源) 盡可能為等概率分布，以使新信源的每個(gè)碼符號(hào)平均所攜帶的信息量達(dá)到最大， 使信道的信息傳輸率R達(dá)到信道容量C，實(shí)現(xiàn)信源與信道的統(tǒng)計(jì)匹配。為了衡量各種編碼是否達(dá)到極限情況，定義變長(zhǎng)碼的編碼效率為門(mén)=4B。L通過(guò)編碼效率n來(lái)衡量各種編碼性能的優(yōu)劣。為了衡量各種編碼與最佳編碼的差 距，定義的剩余度為：1-門(mén)=1-4B，信息傳輸率定義為：R = =門(mén)。LL注意：雖然R與n在數(shù)值上相同，但它們的單位不同，編碼效率n沒(méi)有單位， 而信息編碼傳輸率R的單位是比特/碼符號(hào)，在無(wú)

13、失真信源編碼中又分為定長(zhǎng)編 碼、變長(zhǎng)編碼機(jī)最佳變長(zhǎng)編碼。下面便是對(duì)定長(zhǎng)編碼與變長(zhǎng)編碼的解釋。3.1定長(zhǎng)編碼定理定理1 (等長(zhǎng)信源編碼定理)一個(gè)熵為H (s)的離散無(wú)記憶信源，若對(duì)其N 次擴(kuò)展信源等長(zhǎng)r元編碼，碼長(zhǎng)為1，對(duì)于任意e大于0,只要滿足- H(S) +， N log r當(dāng)N無(wú)窮大時(shí)，則可以實(shí)現(xiàn)幾乎無(wú)失真編碼，反之，若： H(S)-2s，則不 N log r可能實(shí)現(xiàn)無(wú)失真編碼，當(dāng)N趨向于無(wú)窮大時(shí)，譯碼錯(cuò)誤率接近于1。在定長(zhǎng)編碼中，K是定值，編碼的目的即為找到最小的L值。要實(shí)現(xiàn)無(wú)失真 的信源編碼，不但要求信源符號(hào)與碼字是一一對(duì)應(yīng)的，而且還要求有碼字組成的 碼符號(hào)序列的逆變換也是唯一的。由定

14、長(zhǎng)編碼定理可知，當(dāng)編碼器容許的輸出信 息率，也就是當(dāng)每個(gè)信源符號(hào)必須輸出的碼長(zhǎng)是L=Kl/log m。由定理表明，只 要碼字所能攜帶的信息量大于信源序列輸出的信息量，則可以使傳輸幾乎無(wú)失 真，但是條件是L足夠大。這就為傳輸帶來(lái)了很大的麻煩，并且實(shí)現(xiàn)起來(lái)很困難， 并且編碼效率也不高。而要達(dá)到編碼效率接近1的理想編碼器雖有存在性，但在 實(shí)際上時(shí)不可能的，因?yàn)?非常大，無(wú)法實(shí)現(xiàn)。由此而產(chǎn)生了變長(zhǎng)編碼。3.2變長(zhǎng)編碼定理定理2無(wú)失真變長(zhǎng)信源編碼定理(香農(nóng)第一定理)：離散無(wú)記憶信源S的N 次擴(kuò)展信源SN其熵為H(SN)，并且編碼器的碼元符號(hào)集為A： L，。2，白對(duì)信源SN進(jìn)行編碼，總可以找到一個(gè)編碼方法

15、，構(gòu)成單義可譯碼，使信源S中每個(gè)符號(hào)所需要的平均碼長(zhǎng)滿足 些 匕 些 +1。當(dāng)趨于無(wú)窮是，則得： log r N logr Nlim L=H(S)這個(gè)定理是香農(nóng)信息論中非常重要得一個(gè)定理，他指出，要做到無(wú) N 3失真的信源編碼，信源每個(gè)符號(hào)所需要的平均碼元數(shù)就是信源的熵值，如果小于 這個(gè)值，則唯一可譯碼不存在，可見(jiàn)，熵是無(wú)失真信源編碼額極限值。定理還指 出，通過(guò)對(duì)擴(kuò)展信源進(jìn)行編碼，當(dāng)N趨向于無(wú)窮時(shí)，平均碼長(zhǎng)可以趨近該極限值。由 H(S) 匕 匕 log r H(S)nlog r 就是編碼后 log r N logr NNN每個(gè)信源符號(hào)所攜帶的平均信息量。定義輸出信息率：R =她logr。香農(nóng)第

16、一 N定理可以表述如下：若RH(S)就存在唯一可譯變長(zhǎng)碼，若RH(S)則不存在可譯 變長(zhǎng)碼。定義：變長(zhǎng)編碼效率為門(mén)=史納，在變長(zhǎng)編碼中，碼長(zhǎng)L是變化的，可 Ln log r根據(jù)信源各個(gè)符號(hào)的統(tǒng)計(jì)特性，對(duì)概率大的符號(hào)用短碼，而對(duì)概率小的符號(hào)用長(zhǎng) 碼。這樣大量信源符號(hào)編成碼后，平均每個(gè)信源符號(hào)所需的輸出符號(hào)數(shù)就可以降 低，從而提高編碼效率。用變長(zhǎng)編碼來(lái)達(dá)到相當(dāng)高的編碼效率，一般所要求的符 號(hào)長(zhǎng)度L可以比定長(zhǎng)編碼小得多的多。很明顯，定長(zhǎng)碼需要的信源序列長(zhǎng)，這使 得碼表很大，切總存在譯碼差錯(cuò)。而變長(zhǎng)碼要求編碼效率達(dá)到96%時(shí)，只需L=2 因此用變長(zhǎng)碼編碼時(shí)，L不需要很大就可達(dá)到相當(dāng)高的編碼效率，而且可

17、實(shí)現(xiàn)無(wú) 失真編碼。并且隨著信源序列長(zhǎng)度的增加，編碼效率越來(lái)越接近于1，編碼后的 信息傳輸率R也越來(lái)越接近于無(wú)噪無(wú)損二元對(duì)稱信道的信道容量C=1bit/二元碼 符號(hào)，達(dá)到信源與信道匹配，使信道得到充分利用。但變長(zhǎng)編碼方式也有優(yōu)劣的 區(qū)分，下面就變長(zhǎng)編碼即香農(nóng)編碼，費(fèi)諾編碼，霍夫曼編碼進(jìn)行比較分析。4三種變長(zhǎng)編碼的定義與過(guò)程4.1香農(nóng)編碼方法香農(nóng)第一定理指出了平均碼長(zhǎng)與信源之間的關(guān)系，同時(shí)也指出了可疑通過(guò)編 碼使平均碼長(zhǎng)達(dá)到極限值，這是一個(gè)很重要的極限定理。香農(nóng)第一定理指出，選 擇每個(gè)碼字的長(zhǎng)度Li滿足下式：-log p（Si） Li p *p。12q（2）按照上式（1）計(jì)算出每個(gè)信源符號(hào)的碼長(zhǎng)L

18、i。（3）為了變成唯一可譯碼，計(jì)算第i信源符號(hào)的累加概率：Gi = t1 pk。k=1（4）將累加概率Gi用二進(jìn)制數(shù)表示。（5）取Gi對(duì)應(yīng)二進(jìn)制數(shù)的小數(shù)點(diǎn)后Li位構(gòu)成該信源符號(hào)的二進(jìn)制碼字。由此可見(jiàn)香農(nóng)編碼法多余度稍大，實(shí)用性不強(qiáng)，但他是依據(jù)編碼定理而來(lái)， 因此具有重要的理論意義。4.2費(fèi)諾編碼方法費(fèi)諾編碼屬于概率編碼，但不是最佳的編碼方法。只有當(dāng)信源的概率分布呈 現(xiàn)p （Si） = r頊分布形式的條件下，才能達(dá)到最優(yōu)碼的性能。二元費(fèi)諾碼的編碼步驟如下：（1）信源符號(hào)以概率遞減的次序排列。（2）將排列好的信源符號(hào)按概率值劃分成兩大組，使每組的概率之和接近 于相等，并對(duì)每組各賦予一個(gè)二元符號(hào)0和

19、1。（3）將每一大組的信源符號(hào)再分成兩組，使劃分后兩大組的概率之和接近 于相等，再分別賦予一個(gè)二元符號(hào)。（4）依次下去，直至每個(gè)小組只剩下一個(gè)信源符號(hào)為止。（5）信源符號(hào)所對(duì)應(yīng)的碼字即為費(fèi)諾碼。針對(duì)同一信源，費(fèi)諾碼要比香農(nóng)碼的平均碼長(zhǎng)小，消息傳輸速率大，編碼效 率高。費(fèi)諾碼具有以下性質(zhì)：（1）費(fèi)諾碼的編碼方法實(shí)際上是一種構(gòu)造碼樹(shù)的方法，所以費(fèi)諾碼是即時(shí)碼。（2）費(fèi)諾碼考慮了信源的統(tǒng)計(jì)特性，使概率大的信源符號(hào)能對(duì)應(yīng)碼長(zhǎng)較短的 碼字，從而有效地提高了編碼效率。（3）費(fèi)諾碼不一定是最佳碼，因?yàn)橘M(fèi)諾碼編碼方法不一定能使最短碼得到充 分利用。當(dāng)信源符號(hào)較多時(shí)，若有一些符號(hào)概率分布很接近，分兩大組的組合方

20、 法就會(huì)很多?？赡苣撤N分大組的結(jié)果，會(huì)后面小組的“概率和”相差較遠(yuǎn)，從而 使平均碼長(zhǎng)增加。4.3霍夫曼編碼方法1952年，霍夫曼（Huffman）提出了一種構(gòu)造最佳碼的方法，這是一種最佳 的逐個(gè)符號(hào)的編碼方法，一般就稱作霍夫曼碼。二元霍夫曼編碼設(shè)S = y ,s ,.、，其對(duì)應(yīng)的該概率分布為P（s ） = p ,p -p ，則其編碼步12 Qi12, q驟如下：（1）將q個(gè)信源符號(hào)按概率遞減的方式排列。（2）用0,1碼符號(hào)分別表示概率最小的兩個(gè)信源符號(hào)，并將這兩個(gè)概率最 小的信源符號(hào)合并成一個(gè)新的符號(hào)，從而得到只包含q-1個(gè)符號(hào)的新信源，稱作 S信源的縮減信源S1O（3）將縮減信源、】仍按概率

21、大小以遞減次序排列，再將其最后兩個(gè)概率最 小的符號(hào)合并成一個(gè)符號(hào)，并分別用0,1碼符號(hào)表示，這樣又形成了由q-2個(gè)符 號(hào)構(gòu)成的縮減信源S2。（4）依次繼續(xù)下去，直到縮減信源只剩下兩個(gè)符號(hào)為止，將這最后兩個(gè)符 號(hào)分別用0，1碼符號(hào)表示。（5）從最后一級(jí)縮減信源開(kāi)始，向前返回，沿信源縮減過(guò)程的反方向取出 所編的碼元，得出個(gè)信源符號(hào)所對(duì)應(yīng)的碼符號(hào)序列，即為所對(duì)應(yīng)信源符號(hào)的碼字。按霍夫曼碼的編碼方法，可知這種碼有如下特征。（1）它是一種分組碼：各個(gè)信源編碼都被映射成一組固定次序的碼符號(hào)。（2）它是一種唯一可解碼：任何碼符號(hào)序列只能以一種方式譯碼。（3）它是一種即時(shí)碼：由于代表信源符號(hào)的節(jié)點(diǎn)都是終端節(jié)點(diǎn)

22、，因此其編 碼不可能是其他終端節(jié)點(diǎn)所對(duì)應(yīng)的編碼的前綴，即霍夫曼碼所得的碼字為即時(shí) 碼。所以，一串碼符號(hào)中每個(gè)碼字都可不考慮其后的碼符號(hào)直接解碼出來(lái)。霍夫曼的譯碼：對(duì)接收的霍夫曼碼序列可通過(guò)從左到右檢查各個(gè)符號(hào)進(jìn)行譯 碼。例如本例，若接收到的霍夫曼碼序列為0001 10 11 010 10 11，可譯為信 源符號(hào)序列a a a a a a。6 2 1 4 2 1說(shuō)明：（1）霍夫曼碼是一種即時(shí)碼，可用碼樹(shù)形式進(jìn)行表示。（2）每次對(duì)縮減信源最后兩個(gè)概率最小的符號(hào)，用0,1碼可以使任意的， 所以可得到不同的碼，但碼長(zhǎng)Li不變，平均碼長(zhǎng)也不變。（3）當(dāng)縮減信源中縮減合并后得到的新符號(hào)的概率與其他信源符號(hào)

23、概率相 同時(shí)，從編碼方法上來(lái)說(shuō)，它們概率的排序是沒(méi)有限制的，因此也可得到不同的 碼。所以，對(duì)給定信源，用霍夫曼碼方法得到的碼并非唯一，但平均碼長(zhǎng)不變。5三種變長(zhǎng)編碼的實(shí)例分析與比較下面便通過(guò)兩個(gè)例子進(jìn)行說(shuō)明5.1例題1設(shè)一信源符號(hào)有6個(gè)信源符號(hào)a,b,c,d,e,f，其概率分布為0.32、0.22、0.18、 0.16、0.08、0.04。通過(guò)計(jì)算可得到此信源的熵為:H(S)= 一 p(a)log p(a)二2.3526 (比特符號(hào)) i=1計(jì)算平均碼長(zhǎng)的公式L = p(a1)l C元碼符號(hào)符號(hào))i=15.1.1用香農(nóng)編碼方式香農(nóng)碼編碼過(guò)程信 源符號(hào)符號(hào)概率p (a,)累加概率尸Gi-log

24、p(ai)碼字長(zhǎng)度Li碼 字Gi 對(duì)應(yīng)二 進(jìn)制數(shù)a0.3201.642000.00000b0.220.322.1830100.01000c0.180.542.4731000.10000d0.160.72.631010.1240100e0.080.83.641110.11100f0.040.964.65111100.11110信源的平均碼長(zhǎng)為：L=Pj =2.84（二元碼符號(hào)符號(hào)） i=1編碼效率：n=H (S) /L=82.8%可以看出香農(nóng)編碼的效率并不高。5.1.2用費(fèi)諾碼編碼方式費(fèi)諾碼編碼過(guò)程信 源符號(hào) ai各 個(gè)消息 概率pi第 一次分 組第二次分組a0.300b0.21c0.110d0

25、.161e0.0f0.0第 三次分 組第 四次分 組元碼字碼長(zhǎng)Li0020121020110310111411114信源的平均碼長(zhǎng)為：L=P（a）l =2.4（二元碼符號(hào)符號(hào)）i=1編碼效率：n=H (S) /L=97.9%費(fèi)諾編碼的效率有明顯的提高。5.1.3霍夫曼碼編碼方式霍夫曼編碼過(guò)程徉提1:六a:，的j. j2 :. 2i：.2：UI：:i：2:j. j2 ：,22L業(yè) L業(yè)匚、i：, I LE：d 112C：.1Ej. J Mti：.22 i 二i：.2E I112二：.lc1/ :,蓋、匚住11-e：,i：EI j.12 1二:1二信源的平均碼長(zhǎng)為：L=U P(a =2.4(二元碼

26、符號(hào)符號(hào)) i=1編碼效率：n=H(S)/L=98.0%5.2例題2設(shè)一信源符號(hào)有6個(gè)信源符號(hào)a,b,c,d,e,f,g其概率分布為0.20,0.19,0.18,0.17,0.15,0.10,0.01通過(guò)計(jì)算可得到此信源的熵為：。元碼符號(hào)符號(hào))H (S) = -27 p(a )logp(a ) =2.61 (比特符號(hào) i=1計(jì)算平均碼長(zhǎng)的公式L = 2 p(a )l1 i i=15.2.1香農(nóng)編碼過(guò)程信源 符號(hào)符 號(hào)概率累加-log pla)碼字 長(zhǎng)度11碼字Gi對(duì)應(yīng)二進(jìn)制P (a,)概率G.數(shù)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香農(nóng)編碼過(guò)程L=兄P(ai)li =3.14碼符號(hào)信源