最佳變長編碼方式的探究

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19、1。（3）將每一大組的信源符號再分成兩組，使劃分后兩大組的概率之和接近 于相等，再分別賦予一個二元符號。（4）依次下去，直至每個小組只剩下一個信源符號為止。（5）信源符號所對應的碼字即為費諾碼。針對同一信源，費諾碼要比香農(nóng)碼的平均碼長小，消息傳輸速率大，編碼效 率高。費諾碼具有以下性質(zhì)：（1）費諾碼的編碼方法實際上是一種構造碼樹的方法，所以費諾碼是即時碼。（2）費諾碼考慮了信源的統(tǒng)計特性，使概率大的信源符號能對應碼長較短的 碼字，從而有效地提高了編碼效率。（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）依次繼續(xù)下去，直到縮減信源只剩下兩個符號為止，將這最后兩個符 號分別用0，1碼符號表示。（5）從最后一級縮減信源開始，向前返回，沿信源縮減過程的反方向取出 所編的碼元，得出個信源符號所對應的碼符號序列，即為所對應信源符號的碼字。按霍夫曼碼的編碼方法，可知這種碼有如下特征。（1）它是一種分組碼：各個信源編碼都被映射成一組固定次序的碼符號。（2）它是一種唯一可解碼：任何碼符號序列只能以一種方式譯碼。（3）它是一種即時碼：由于代表信源符號的節(jié)點都是終端節(jié)點

22、，因此其編 碼不可能是其他終端節(jié)點所對應的編碼的前綴，即霍夫曼碼所得的碼字為即時 碼。所以，一串碼符號中每個碼字都可不考慮其后的碼符號直接解碼出來?；舴蚵淖g碼：對接收的霍夫曼碼序列可通過從左到右檢查各個符號進行譯 碼。例如本例，若接收到的霍夫曼碼序列為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用香農(nóng)編碼方式香農(nóng)碼編碼過程信 源符號符號概率p (a,)累加概率尸Gi-log

24、p(ai)碼字長度Li碼 字Gi 對應二 進制數(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信源的平均碼長為：L=Pj =2.84（二元碼符號符號） i=1編碼效率：n=H (S) /L=82.8%可以看出香農(nóng)編碼的效率并不高。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業(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二信源的平均碼長為：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香農(nóng)編碼過程信源 符號符 號概率累加-log pla)碼字 長度11碼字Gi對應二進制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)編碼過程L=兄P(ai)li =3.14碼符號信源