信息論-第4章(哈夫曼編碼和游程編碼)

信息論基礎(chǔ)TheBasisofInformationTheory主題No4：哈夫曼編碼和游程編碼概述將原始數(shù)據(jù)進(jìn)行壓縮的方法就是壓縮編碼,壓縮編碼可分為“無(wú)失真壓縮編碼”和“有失真壓縮編碼”兩種.“無(wú)失真壓縮編碼”應(yīng)用在要求絕對(duì)正確地恢復(fù)原始數(shù)據(jù)的場(chǎng)合如計(jì)算機(jī)文件資料;“有失真壓縮編碼”主要應(yīng)用在多媒體數(shù)據(jù)的壓縮上如圖像壓縮等.基于信源的統(tǒng)計(jì)特性而產(chǎn)生的壓縮編碼方法統(tǒng)稱“統(tǒng)計(jì)編碼”,這些方法都是通過(guò)使用較短的代碼來(lái)代替較長(zhǎng)的,大量重復(fù)出現(xiàn)(概率較高的)的原始數(shù)據(jù),從而達(dá)到壓縮的目的.本章介紹的“哈夫曼編碼”,“游程編碼”,“基于字典的編碼”,“算術(shù)編碼”均為無(wú)失真壓縮編碼方法.變長(zhǎng)編碼在第二章中，我們已經(jīng)學(xué)習(xí)了有關(guān)變長(zhǎng)碼的理論知識(shí)，現(xiàn)在介紹編碼的具體實(shí)現(xiàn)方法。常用變長(zhǎng)碼的編碼方法有三種：（2）費(fèi)諾編碼；（1）香農(nóng)編碼；（3）哈夫曼編碼.(1)香農(nóng)編碼香農(nóng)編碼：根據(jù)信源中各個(gè)消息的概率直接計(jì)算出代碼:ni取小于I(xi)+1的最大整數(shù).香農(nóng)編碼方法簡(jiǎn)單，但不能保證得到的編碼方案為最優(yōu)方案。香農(nóng)編碼的例子消息符號(hào)符號(hào)概率p(xi)-

log2p(xi)碼長(zhǎng)X10.202.343X20.192.413X30.182.483X40.17

2.563X50.152.743X60.103.344x70.016.667例1：對(duì)下面離散信源進(jìn)行香農(nóng)編碼：香農(nóng)編碼分析可求得該信源的信源熵：以及平均碼長(zhǎng)：由此得到該編碼的平均信息傳輸率：(比特/符號(hào))(碼元/符號(hào))(比特/碼元時(shí)間)(2)費(fèi)諾（Fano）編碼費(fèi)諾編碼：將信源中的各個(gè)消息分成兩組，盡可能使兩組中各個(gè)消息的概率和相接近，然后對(duì)每組內(nèi)的消息繼續(xù)分組，直到每組只包含一個(gè)消息。通過(guò)分組過(guò)程得到各個(gè)消息的編碼，但不能保證得到的編碼方案為最優(yōu)方案。費(fèi)諾（Fano）編碼的例子下面是對(duì)例1進(jìn)行費(fèi)諾編碼：消息符號(hào)符號(hào)概率p(xi)第一次第二次第三次第四次碼字碼長(zhǎng)x10.2000002x2

0.19100103x30.1810113x40.17

10102x50.15101103x6

0.101011104x70.01111114費(fèi)若（Fano）編碼分析同樣可求得該信源的信源熵：以及平均碼長(zhǎng)：由此得到該編碼的平均信息傳輸率：(比特/符號(hào))(碼元/符號(hào))(比特/碼元時(shí)間)（3）哈夫曼（Huffman）編碼哈夫曼編碼：將信源中的各個(gè)消息按概率排序，不斷將概率最小的兩個(gè)消息進(jìn)行合并，直到合并為一個(gè)整體，然后根據(jù)合并的過(guò)程分配碼字，得到各個(gè)消息的編碼。該方法簡(jiǎn)單明了，并且可以保證最終的編碼方案一定是最優(yōu)編碼方案。哈夫曼（Huffman）編碼的例子下面是對(duì)例1進(jìn)行哈夫曼編碼：X6:0.10X7:0.010.11X5:0.15X4:0.17X3:0.18X2:0.19X1:0.200.260.350.390.611.00對(duì)應(yīng)的編碼如下：信源x1x2x3x4x5x6x7編碼101100000101001100111碼長(zhǎng)2233344哈夫曼（Huffman）編碼分析(碼元/符號(hào))得平均碼長(zhǎng)：(比特/碼元時(shí)間)由此得到該編碼的平均信息傳輸率：

哈夫曼編碼的擴(kuò)展我們介紹的哈夫曼編碼方法是對(duì)具有多個(gè)獨(dú)立消息的信源進(jìn)行二進(jìn)制編碼,如果編碼符號(hào)（碼元）不是二進(jìn)制的0和1,而是D進(jìn)制，同樣可以按照哈夫曼編碼的方法來(lái)完成：只要將哈夫曼編碼樹(shù)由二叉樹(shù)換成D叉樹(shù),每次合并的節(jié)點(diǎn)由兩個(gè)改為D個(gè),分配碼元時(shí),從左到右將0到D－1依次分配給各個(gè)路段,最后從根節(jié)點(diǎn)到各個(gè)葉節(jié)點(diǎn)（消息）讀出編碼結(jié)果即可.游程編碼的基本原理很多信源產(chǎn)生的消息有一定相關(guān)性,往往連續(xù)多次輸出同樣的消息,同一個(gè)消息連續(xù)輸出的個(gè)數(shù)稱為游程(Run-Length).我們只需要輸出一個(gè)消息的樣本和對(duì)應(yīng)重復(fù)次數(shù),就完全可以恢復(fù)原來(lái)的消息系列.原始消息系列經(jīng)過(guò)這種方式編碼后,就成為一個(gè)個(gè)編碼單元(如下圖),其中標(biāo)識(shí)碼是一個(gè)能夠和消息碼區(qū)分的特殊符號(hào).消息碼標(biāo)識(shí)碼

游程長(zhǎng)度該編碼方式就稱為游程編碼(RLC).例如：有一個(gè)信源:經(jīng)過(guò)游程編碼，得到：BBBBBBBBBBXXXXXXXXJJJJJJJJJAAAAAAAAAAAAAAAAAUUUUUUUUUUUUUUUUUUUUB#10X#8J#9A#17U#20其中＃為標(biāo)識(shí)碼.游程編碼用于二值圖像的壓縮圖像在計(jì)算機(jī)中是用像素表示的,我們將一幅圖像分成很多行,每行又分成很多像素,每個(gè)像素用亮度值和彩色數(shù)據(jù)表示.二值圖像是指像素只有兩種取值:0表示背景(底色),1表示前景(內(nèi)容).如果二值圖像完全采用按像素儲(chǔ)存的方式來(lái)表示,需要的儲(chǔ)存空間是非常大的.為了對(duì)二值圖像進(jìn)行壓縮,需要對(duì)二值圖像數(shù)據(jù)的統(tǒng)計(jì)特性進(jìn)行分析,統(tǒng)計(jì)特性表明,二值圖像中的黑白像素出現(xiàn)的概率相差很大;且同一種像素連續(xù)出現(xiàn)的概率也很大,即平均游程長(zhǎng)度比較長(zhǎng),采用游程編碼一定可以取得滿意效果.文件傳真壓縮方法簡(jiǎn)介在二值圖像的一行掃描像素中,黑白游程總是相間的,只要知道第一個(gè)游程的顏色,后面各個(gè)游程的顏色也就可以確定了.如果將第一個(gè)游程的顏色固定為白色,則所有第奇數(shù)個(gè)游程也是白色游程,而所有第偶數(shù)個(gè)游程必然是黑色游程.實(shí)際情況下,有可能第一個(gè)游程的顏色為黑色,我們就需要人為在他前面插入一個(gè)游程長(zhǎng)度為零的白色游程,以滿足“第一個(gè)游程的顏色固定為白色”的規(guī)定.在游程顏色已經(jīng)規(guī)定后,游程編碼時(shí)就可以將“消息碼”和“標(biāo)識(shí)碼”省略,只保留游程長(zhǎng)度數(shù)據(jù)即可.文件傳真壓縮方法具體流程主要利用終止碼和形成碼(見(jiàn)書(shū)本P43-44),一般A4的紙每行的像素為1728,具體編碼規(guī)則如下:（1）當(dāng)游程長(zhǎng)度小于64時(shí)，直接用一個(gè)對(duì)應(yīng)的終止碼表示。（2）當(dāng)游程長(zhǎng)度在64到1728之間時(shí)，用一個(gè)形成碼加一個(gè)終止碼表示。例如:白游程為662時(shí)用640形成碼(白)加22終止碼(白)表示,即:011001110000011.黑游程為256時(shí)用256形成碼(黑)加0終止碼(黑)表示,即:0000010110110000110111.（3）每行開(kāi)始必須為白游程,如果實(shí)際情況是從黑游程開(kāi)始,就用一個(gè)長(zhǎng)度為零的白游程作為開(kāi)始.每行結(jié)束必須加一個(gè)同步碼EOL.（4）每頁(yè)文件必須以同步碼EOL開(kāi)始,連續(xù)6個(gè)EOL碼表示文件傳輸結(jié)束.文件傳真壓縮的例子及壓縮比例的計(jì)算如果某行掃描的結(jié)果如下表所示:白游程黑游程白游程黑游程