信息論第八章

1、信息論第八章第1頁，共25頁，2022年，5月20日，1點22分，星期一8.1 霍夫曼(Huffman)碼8.1.1 二元霍夫曼碼 8.1.2 r元霍夫曼碼 8.1.3 Huffman碼的最佳性 第2頁，共25頁，2022年，5月20日，1點22分，星期一香農(nóng)編碼：1、碼長2、按照算出的碼長、用樹圖法編出相應的即時碼。一般香農(nóng)編碼的 不是最短的，即不是最佳碼。第3頁，共25頁，2022年，5月20日，1點22分，星期一例8.1 用香農(nóng)編碼方法編成二元惟一可譯碼. 編碼 第4頁，共25頁，2022年，5月20日，1點22分，星期一8.1.1 二元霍夫曼碼1、二元Huffman碼的編碼步驟將q個信

2、源符號按概率分布由大到小的 順序排列起來：(2)將碼符號0,1分配給兩個最小概率的信 源符號，并將其概率值合并，成為一個 信源符號，q個符號的 信源縮減成q-1 個 信源。(3)排序 ，分配0,1, 重復步驟(2), 得縮減 信源 第5頁，共25頁，2022年，5月20日，1點22分，星期一(4)直至最后信源只含兩個符號，分配碼 符號0,1.(5) 從最后一級信源開始，向前返回，碼 符號順序列出，得相應碼字。例8.1第6頁，共25頁，2022年，5月20日，1點22分，星期一構造出碼樹第7頁，共25頁，2022年，5月20日，1點22分，星期一原因：(1) 最小概率分配0,1時可任意。各 碼長

3、 不變, 不變, 碼形式不同.(2) 縮減合并后的符號概率與其它符號概 率相同時, 概率大小次序當上下移動 時, 不違反規(guī)定。編碼后 不同, 碼不 同, 但 相同。Huffman編碼方法得到的碼并不唯一。第8頁，共25頁，2022年，5月20日，1點22分，星期一2、例8.1 新合并概率放上面碼長比較第9頁，共25頁，2022年，5月20日，1點22分，星期一問題：碼長相同，哪種編碼好？碼長度方差小的碼序列長度變化較小，從實現(xiàn)的角度更好。第10頁，共25頁，2022年，5月20日，1點22分，星期一編碼方法補充： 在霍夫曼編碼過程中，在縮減信源時，使合并得來的概率盡量處于最高的位置。3、霍夫曼

4、碼具有的三個特點(1) 短碼得到充分利用 則(2) 各次縮減信源中最小概率的兩個符號 有相同的碼長。(3) 各次縮減信源中最小概率的兩個符號 的碼字只有最后一位碼元不同。第11頁，共25頁，2022年，5月20日，1點22分，星期一8.1.2 r元霍夫曼碼注意三點(2) 每次合并r個最小概率成為新信源，減 少 個符號。(3) 滿足式 才能充分利用短碼.信源縮減次數(shù)若不滿足, 增加 的概率項(1) 將最小概率的r個符號分配碼元第12頁，共25頁，2022年，5月20日，1點22分，星期一例8.2 四元Huffman碼補二項第13頁，共25頁，2022年，5月20日，1點22分，星期一8.1.3

5、Huffman碼的最佳性1、定理8.1(1) 若對于給定分布的任何信源，存在一個最佳即時碼，此碼滿足以下性質(2) 兩個最小概率的信源符號所對應的 碼字具有相同的碼長。(3) 兩個最小概率的信源符號對應的碼 字，除最后一位碼元不同外，前面 各位碼元都相同。第14頁，共25頁，2022年，5月20日，1點22分，星期一2、定理 8.2 C是 Huffman 碼。 可以證明 r 元霍夫曼碼一定是最佳碼。而且信源的N次擴展也可以采用Huffman 編碼方法，當N增大時，快速 二元 Huffman 碼一定是最佳即時碼。即第15頁，共25頁，2022年，5月20日，1點22分，星期一(1) 無失真編碼效

6、率高, , 常用于文件傳 真, 語音處理和圖象處理的數(shù)據(jù)壓縮.(2) 解決速率匹配問題，設備較復雜, 信源與信 道間需增加緩沖寄存器, 變速入, 恒速出。Huffman 碼的優(yōu)點和缺點(3) 克服誤差擴散：限制霍夫曼碼僅能應用于 優(yōu)質信道（=10-6）以限制擴散的可能性。(4) 要求了解信源的統(tǒng)計分布。(5) 算法復雜度隨著信源符號串長度的增加而 迅速增長。第16頁，共25頁，2022年，5月20日，1點22分，星期一Fano 碼的編碼步驟：(1) 將信源符號以概率遞減的次序排列. (2) 劃分成兩大組，使每組的概率和近似 相等，并分別賦予碼符號“0”和“1”.(3) 將每大組的信源符號再分成

7、兩大組， 重復(2), 直至每小組只剩一個信源符號.(4) 信源符號所對應的碼符號序列則為 編得的碼字。8.2 費諾(Fano)碼第17頁，共25頁，2022年，5月20日，1點22分，星期一例8.4 第18頁，共25頁，2022年，5月20日，1點22分，星期一例8.1費諾碼的編碼方法實際上是構造碼樹的一種方法,是即時碼,當概率和相差較遠時,會使平均碼長增加.一般不是最佳碼.第19頁，共25頁，2022年，5月20日，1點22分，星期一它是采用信源符號的累積分布函數(shù)來分配碼字.1、設信源符號集且所有定義累積分布函數(shù)定義修正的累積分布函數(shù)8.3 香農(nóng)-費諾-埃利斯碼第20頁，共25頁，2022年，5月20日，1點22分，星期一(1) 是每臺階的上界值(2) 處于對應臺階的中點(3) 每臺階的高度是該符號的概率(4) 當?shù)?1頁，共25頁，2022年，5月20日，1點22分，星期一可采用 的數(shù)值作為符號的碼字.碼字，取多長？選取第22頁，共25頁，2022年，5月20日，1點22分，星期一 用替代 所帶來的誤差小于 , 其值仍在同臺階以內(nèi)不同的對應不同的臺階，即區(qū)域，沒有重疊，是即時碼。書中證明第23頁，共25頁，2022年，5月20日，1點22分，星期一例8.5 求香農(nóng)費