第八章 無失真信源編碼

第八章無失真的信源編碼8.1霍夫曼(Huffman)碼8.2費諾(Fano)碼8.3香農(nóng)—費諾—埃利斯碼8.1霍夫曼(Huffman)碼8.1.1二元霍夫曼碼8.1.2r元霍夫曼碼8.1.3Huffman碼的最佳性香農(nóng)編碼：1、碼長2、按照算出的碼長、用樹圖法編出相應(yīng)的即時碼。一般香農(nóng)編碼的不是最短的，即不是最佳碼。例8.1

用香農(nóng)編碼方法編成二元惟一可譯碼.編碼

8.1.1二元霍夫曼碼1、二元Huffman碼的編碼步驟將q個信源符號按概率分布由大到小的順序排列起來：(2)將碼符號0,1分配給兩個最小概率的信源符號，并將其概率值合并，成為一個信源符號，q個符號的信源縮減成q-1

個信源。(3)排序，分配0,1,重復(fù)步驟(2),得縮減信源(4)直至最后信源只含兩個符號，分配碼符號0,1.(5)從最后一級信源開始，向前返回，碼符號順序列出，得相應(yīng)碼字。例8.1構(gòu)造出碼樹原因：(1)最小概率分配0,1時可任意。各碼長不變,不變,碼形式不同.(2)縮減合并后的符號概率與其它符號概率相同時,概率大小次序當上下移動時,不違反規(guī)定。編碼后不同,碼不同,但相同。Huffman編碼方法得到的碼并不唯一。2、例8.1新合并概率放上面碼長比較問題：碼長相同，哪種編碼好？碼長度方差小的碼序列長度變化較小，從實現(xiàn)的角度更好。編碼方法補充：在霍夫曼編碼過程中，在縮減信源時，使合并得來的概率盡量處于最高的位置。3、霍夫曼碼具有的三個特點(1)短碼得到充分利用則(2)各次縮減信源中最小概率的兩個符號有相同的碼長。(3)各次縮減信源中最小概率的兩個符號的碼字只有最后一位碼元不同。8.1.2r元霍夫曼碼注意三點(2)每次合并r個最小概率成為新信源，減少個符號。(3)滿足式才能充分利用短碼.信源縮減次數(shù)若不滿足,增加的概率項(1)將最小概率的r個符號分配碼元例8.2

四元Huffman碼補二項8.1.3Huffman碼的最佳性1、定理8.1(1)若對于給定分布的任何信源，存在一個最佳即時碼，此碼滿足以下性質(zhì)(2)兩個最小概率的信源符號所對應(yīng)的碼字具有相同的碼長。(3)兩個最小概率的信源符號對應(yīng)的碼字，除最后一位碼元不同外，前面各位碼元都相同。2、定理8.2C是Huffman碼?？梢宰C明r

元霍夫曼碼一定是最佳碼。而且信源的N次擴展也可以采用Huffman編碼方法，當N增大時，快速二元Huffman碼一定是最佳即時碼。即(1)無失真編碼效率高,,常用于文件傳真,語音處理和圖象處理的數(shù)據(jù)壓縮.(2)解決速率匹配問題，設(shè)備較復(fù)雜,信源與信道間需增加緩沖寄存器,

變速入,恒速出。Huffman碼的優(yōu)點和缺點(3)克服誤差擴散：限制霍夫曼碼僅能應(yīng)用于優(yōu)質(zhì)信道（<=10-6）以限制擴散的可能性。(4)要求了解信源的統(tǒng)計分布。(5)算法復(fù)雜度隨著信源符號串長度的增加而迅速增長。Fano

碼的編碼步驟：(1)將信源符號以概率遞減的次序排列.(2)劃分成兩大組，使每組的概率和近似相等，并分別賦予碼符號“0”和“1”.(3)將每大組的信源符號再分成兩大組，重復(fù)(2),直至每小組只剩一個信源符號.(4)信源符號所對應(yīng)的碼符號序列則為編得的碼字。8.2費諾(Fano)碼例8.4例8.1費諾碼的編碼方法實際上是構(gòu)造碼樹的一種方法,是即時碼,當概率和相差較遠時,會使平均碼長增加.一般不是最佳碼.它是采用信源符號的累積分布函數(shù)來分配碼字.1、設(shè)信源符號集且所有定義累積分布函數(shù)定義修正的累積分布函數(shù)8.3香農(nóng)-費諾-埃利斯碼(1)是每臺階的上界值．(2)處于對應(yīng)臺階的中點．(3)每臺階的高度是該符號的概率(4)當可采用的數(shù)值作為符號的碼字.碼字，取多長？選取用替代所帶來的誤差小于,其值仍在同臺階以內(nèi)．不同的對應(yīng)不同的臺階，即區(qū)域，沒有重疊，是即時碼。書中證明例8.5

求香農(nóng)—費諾—埃利斯碼Shannon-Fano-Elias碼雖然不是最佳碼，但它發(fā)展成為算術(shù)碼，其編碼和譯碼可由計算獲得，效率很高。作業(yè)：(香農(nóng)碼、Huffman碼、Fano碼)1.畫出任一種編碼的實現(xiàn)流程圖。2.使用Matlab或C++語言編程，完成編碼。要求：已知：信源符號個數(shù)q,符號概率;輸入：信源符號個數(shù)和概率，在程序運行時從鍵盤輸入；輸出：編碼3.自己舉例,給出編碼的程序執(zhí)行結(jié)果。4.作業(yè)提交Word文檔——（1）作業(yè)題目；（2）算法流程圖；（3）程序驗證例子；（