第八章 無失真信源編碼

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

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

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

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

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

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

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

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

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