信息論第八章

信息論第八章第一頁(yè)，共二十五頁(yè)，編輯于2023年，星期六8.1霍夫曼(Huffman)碼8.1.1二元霍夫曼碼8.1.2r元霍夫曼碼8.1.3Huffman碼的最佳性第二頁(yè)，共二十五頁(yè)，編輯于2023年，星期六香農(nóng)編碼：1、碼長(zhǎng)2、按照算出的碼長(zhǎng)、用樹(shù)圖法編出相應(yīng)的即時(shí)碼。一般香農(nóng)編碼的不是最短的，即不是最佳碼。第三頁(yè)，共二十五頁(yè)，編輯于2023年，星期六例8.1

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

第四頁(yè)，共二十五頁(yè)，編輯于2023年，星期六8.1.1二元霍夫曼碼1、二元Huffman碼的編碼步驟將q個(gè)信源符號(hào)按概率分布由大到小的順序排列起來(lái)：(2)將碼符號(hào)0,1分配給兩個(gè)最小概率的信源符號(hào)，并將其概率值合并，成為一個(gè)信源符號(hào)，q個(gè)符號(hào)的信源縮減成q-1

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

四元Huffman碼補(bǔ)二項(xiàng)第十三頁(yè)，共二十五頁(yè)，編輯于2023年，星期六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)的碼字，除最后一位碼元不同外，前面各位碼元都相同。第十四頁(yè)，共二十五頁(yè)，編輯于2023年，星期六2、定理8.2C是Huffman碼。可以證明r

元霍夫曼碼一定是最佳碼。而且信源的N次擴(kuò)展也可以采用Huffman編碼方法，當(dāng)N增大時(shí)，快速二元Huffman碼一定是最佳即時(shí)碼。即第十五頁(yè)，共二十五頁(yè)，編輯于2023年，星期六(1)無(wú)失真編碼效率高,,常用于文件傳真,語(yǔ)音處理和圖象處理的數(shù)據(jù)壓縮.(2)解決速率匹配問(wèn)題，設(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)。第十六頁(yè)，共二十五頁(yè)，編輯于2023年，星期六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)碼第十七頁(yè)，共二十五頁(yè)，編輯于2023年，星期六例8.4第十八頁(yè)，共二十五頁(yè)，編輯于2023年，星期六例8.1費(fèi)諾碼的編碼方法實(shí)際上是構(gòu)造碼樹(shù)的一種方法,是即時(shí)碼,當(dāng)概率和相差較遠(yuǎn)時(shí),會(huì)使平均碼長(zhǎng)增加.一般不是最佳碼.第十九頁(yè)，共二十五頁(yè)，編輯于2023年，星期六它是采用信源符號(hào)的累積分布函數(shù)來(lái)分配碼字.1、設(shè)信源符號(hào)集且所有定義累積分布函數(shù)定義修正的累積分布函數(shù)8.3香農(nóng)-費(fèi)諾-埃利斯碼第二十頁(yè)，共二十五頁(yè)，編輯于2023年，星期六(1)是每臺(tái)階的上界值．(2)處于對(duì)應(yīng)臺(tái)階的中點(diǎn)．(3)每臺(tái)階的高度是該符號(hào)的概率(4)當(dāng)?shù)诙豁?yè)，共二十五頁(yè)，編輯于2023年，星期六可采用的數(shù)值作為符號(hào)的碼字.碼字，取多長(zhǎng)？選取第二十二頁(yè)，共二十五頁(yè)，編輯于2023年，星期六用替代所帶來(lái)的誤差小于,其值仍在同臺(tái)階以內(nèi)．不同的對(duì)應(yīng)不同的臺(tái)階，即區(qū)域，沒(méi)有重疊，是即時(shí)碼。書(shū)中證明第二十三頁(yè)，共二十五頁(yè)，編輯于2