《編碼理論》課件第3章

第3章無失真信源編碼方法

3.1霍夫曼碼和其他編碼方法

3.2算術(shù)編碼

3.3游程編碼

3.4通用編碼

3.1霍夫曼碼及其他編碼方法

3.1.1二元霍夫曼碼

1952年霍夫曼提出了一種構(gòu)造最佳碼的方法，它是一種逐個(gè)符號(hào)的編碼方法。所得的碼字是異前置碼的變長碼，其平均碼長最短，是最佳變長碼，又稱霍夫曼碼，二元霍夫曼碼編碼步驟如下：

(1)將n元信源U的各個(gè)符號(hào)ui按概率分布p（ui）以遞減次序排列起來。

(2)將兩個(gè)概率最小的信源符號(hào)合并成一個(gè)新符號(hào)，新符號(hào)的值為兩個(gè)信源符號(hào)值的和，從而得到只包含n－1個(gè)符號(hào)的新信源，稱為U信源的縮減信源U1。

(3)把縮減信源U1的符號(hào)仍按概率大小以遞減次序排列，然后將其中兩個(gè)概率最小的符號(hào)合并成一個(gè)符號(hào)，這樣又形成了n－2個(gè)符號(hào)的縮減信源U2。

(4)依次繼續(xù)下去，直至信源最后只剩下１個(gè)符號(hào)為止。(5)將每次合并的兩個(gè)信源符號(hào)分別用0和1碼符號(hào)表示。(6)從最后一級(jí)縮減信源開始，向前返回，就得出各信源符號(hào)所對(duì)應(yīng)的碼符號(hào)序列，即得各信源符號(hào)對(duì)應(yīng)的碼字。

［例3-1］離散無記憶信源

對(duì)應(yīng)的霍夫曼編碼如圖3－1所示。

信源熵：

(比特/信源符號(hào))平均碼長：

(碼符號(hào)/信源符號(hào))編碼效率：

圖3－1例3－1霍夫曼編碼

【例3－2】離散無記憶信源

的兩種霍夫曼編碼如圖3－2所示。

圖3－2例3－2的兩種霍夫曼編碼

圖3-3中（a）、（b)所示兩種方案的霍夫曼編碼平均碼長都為

(碼符號(hào)/信源符號(hào))信源熵：

(比特/信源符號(hào))編碼效率：

圖3－3例3－2對(duì)應(yīng)的霍夫曼樹

兩種碼有相同的平均碼長，有相同的編碼效率，但每個(gè)信源符號(hào)的碼長卻不相同，其均方差也不同。下面分別計(jì)算兩種碼的均方差σ2，即

(方法a方差)(方法b方差)可見，方法（a）的方差比方法（b）的方差要小許多。方法(a）的具體編碼原則是把合并后的概率總是放在其他相同概率的信源符號(hào)之上（或之左）;方法（b)的編碼原則是把合并后的概率放在其他相同概率的信源符號(hào)之下（或之右）。從上面的分析可以看出，方法（a)要優(yōu)于方法（b)。

可見，霍夫曼碼得到的碼并非是惟一的。因?yàn)閷?duì)縮減信源的兩個(gè)概率最小的符號(hào)，可以任意的用0和1碼，所以可得到不同的碼，但它們只是碼字具體結(jié)構(gòu)不同，而其碼長不變，平均碼長也不變，因此沒有本質(zhì)區(qū)別。另外，若當(dāng)縮減信源中縮減合并后的符號(hào)的概率與其他信源符號(hào)概率相同時(shí)，從編碼方法上來說，對(duì)等概率的符號(hào)哪個(gè)放在上面、哪個(gè)放在下面是沒有區(qū)別的，但得到的碼是不同的。對(duì)這兩種不同的碼，它們的碼長各不同，然而平均碼長是相同的。在編碼中，對(duì)等概率消息，若將新合并的消息排列到上支路，可以證明它將縮短碼長的方差，即編出的碼更接近等長碼；同時(shí)可使合并的元素重復(fù)編碼次數(shù)減少，使短碼得到充分利用。

3.1.2

m元霍夫曼碼

前面討論的二元霍夫曼碼的編碼方法可以推廣到m元編碼中，不同的只是每次把概率最小的m個(gè)符號(hào)合并成一個(gè)新的信源符號(hào)，并分別用0，1，…，m－1等碼元來表示。

為了使短碼得到充分利用，使平均碼長最短，必須使最后一步的縮減信源有m個(gè)信源符號(hào)。因此，對(duì)于m元編碼，信源U的符號(hào)個(gè)數(shù)n必須滿足：n＝（m－1）Q＋m

（3-1）

式中：n—信源符號(hào)個(gè)數(shù)；m—進(jìn)制數(shù)（碼元數(shù)）；Q—縮減次數(shù)。

對(duì)于二元碼，總能找到一個(gè)Q滿足式（3－1）。但對(duì)于m元碼，n為任意正整數(shù)時(shí)不一定能找到一個(gè)Q滿足式（3－1），此時(shí)，可以人為地增加一些概率為零的符號(hào)，以滿足式（3－1），然后取概率最小的m個(gè)符號(hào)合并成一個(gè)新符號(hào)（結(jié)點(diǎn)），并把這些符號(hào)的概率相加作為該結(jié)點(diǎn)的概率，重新按概率由大到小順序排隊(duì)，再取概率最小的m個(gè)符號(hào)（結(jié)點(diǎn)）合并；如此下去直至樹根。

下面給出m元霍夫曼的編碼步驟：

(1)驗(yàn)證所給n是否滿足式（3－1），若不滿足該式，可以人為地增加一些概率為零的符號(hào)，以使最后一步有m個(gè)信源符號(hào)。

(2)將信源符號(hào)按概率遞減次序排列，取概率最小的m個(gè)符號(hào)合并成一個(gè)新結(jié)點(diǎn)，并分別用0，1，…，m－１給各分支賦值,把這些符號(hào)的概率相加作為該新結(jié)點(diǎn)的概率。

(3)將新結(jié)點(diǎn)和剩下結(jié)點(diǎn)重新排隊(duì)，重復(fù)步驟（2），如此下去直至樹根。

(4)取樹根到葉子（信源符號(hào)對(duì)應(yīng)結(jié)點(diǎn)）的各樹枝上的值，得到各符號(hào)碼字?！纠?－3】已知信源

其三元霍夫曼編碼如圖3-4所示.，四元霍夫曼編碼如圖（3-5）所示。

圖3-4例3-3三元霍夫曼編碼圖3－5例3－3四元霍夫曼編碼

信源熵：

(比特/信源符號(hào))兩種編碼的平均碼長分別為：

因?yàn)閘b3＝1.58(比特/信源符號(hào)),lb4＝2(比特/信源符號(hào))，所以它們的編碼效率分別為：

可見，要發(fā)揮霍夫曼編碼的優(yōu)勢(shì)，一般情況下，信源符號(hào)集的元數(shù)應(yīng)遠(yuǎn)大于碼元數(shù)。對(duì)例3－3，若編五元碼，只能對(duì)每個(gè)信源符號(hào)賦予一個(gè)碼數(shù)，等于沒有編碼，當(dāng)然也無壓縮可言。那么，什么樣的編碼能獲得最佳的壓縮效果呢？下面將討論這個(gè)問題。

3.1.4香農(nóng)編碼

香農(nóng)第一定理指出了平均碼長與信源信息熵之間的關(guān)系，同時(shí)也指出了可以通過編碼使平均碼長達(dá)到極限值，這是一個(gè)很重要的極限定理。至于如何去構(gòu)造一個(gè)緊致碼(最佳碼)，定理并沒有直接給出。香農(nóng)第一定理指出，選擇每個(gè)碼字的長度li使之為滿足式-logp(ui)≤li<-logp(ui)+1的整數(shù)，就可以得到惟一可譯碼，這種編碼方法稱為香農(nóng)編碼。按照香農(nóng)編碼方法編出來的碼可以使平均碼長L不超過上界，但并不一定能使L為最短，即編出來的不一定是緊致碼。

可見，香農(nóng)編碼方法剩余度稍大，實(shí)用性不強(qiáng)，但有其重要的理論意義。二元香農(nóng)碼的編碼過程如下：

（1）將信源發(fā)出的n個(gè)消息（符號(hào)）按其概率的遞減次序依次排列。

(2)為了編成惟一可譯碼，首先計(jì)算第i個(gè)信源符號(hào)的累加概率：

(3)將累加概率pi(為小數(shù))變換成二進(jìn)制數(shù)。

(4)根據(jù)碼長li，取小數(shù)點(diǎn)后li位數(shù)作為第i個(gè)信源符號(hào)的碼字,li可由下式確定：

式中：［X］——取大于或等于X的最小整數(shù)。

(3－2)(3－3)【例3－4】已知

求香農(nóng)編碼。

解計(jì)算第i個(gè)信源符號(hào)的碼字。設(shè)i=4，首先求第4個(gè)信源符號(hào)的二元碼字長l4：再計(jì)算累加概率p4：

將累加概率p4變換成二進(jìn)制數(shù)：

故變換成二進(jìn)制數(shù)為0.100…，根據(jù)碼長l4=3取小數(shù)點(diǎn)后三位100,作為第4個(gè)信源符號(hào)的碼字。其他信源符號(hào)的二元碼字可用同樣方法求得，如表3－1所示。

表3－1香農(nóng)編碼

由表3－1可以看出，一共有5個(gè)三位的碼字，各碼字之間至少有一位數(shù)字不相同，故是惟一可譯碼。

信源符號(hào)概率累加概率碼字長度二元碼字0.200.002.3430000.190.202.4130010.180.392.4830110.170.572.5631000.150.742.7431010.100.893.34411100.010.996.6671111110平均碼長：

(碼符號(hào)/信源符號(hào))平均信息傳輸速率：

(比特/碼符號(hào))由上面的編碼過程和例題分析可知，利用香農(nóng)編碼方法求表3－1中信源符號(hào)的碼字比較繁瑣。能否緊緊把握香農(nóng)編碼的核心思想而改進(jìn)其具體的編碼過程呢?香農(nóng)編碼方法的核心思想是：每個(gè)碼字的碼長li滿足-logp(ui)≤li<-logp(ui)+1并取整。在此基礎(chǔ)上，不采用累加概率轉(zhuǎn)換為二進(jìn)制數(shù)的編碼方法，而是求出每個(gè)碼字碼長后，利用樹圖法找到一組碼長滿足要求的樹碼。這樣，改進(jìn)的香農(nóng)編碼方法的具體內(nèi)容如下：

（1）根據(jù)每個(gè)信源符號(hào)的概率大小，按式(3－3)計(jì)算其碼字的碼長li。

(2)利用二元樹圖法，根據(jù)所求碼字碼長的大小，構(gòu)造出即時(shí)碼。圖3－6二元樹圖

根據(jù)二元樹圖，可以得到滿足要求的即時(shí)碼。

上面所討論的是二元香農(nóng)編碼，利用改進(jìn)的香農(nóng)編碼方法可以把它推廣到r元香農(nóng)編碼中，即

（1）根據(jù)每個(gè)信源符號(hào)的概率大小，按式(3－3)計(jì)算其碼字的碼長li。

（2）利用r元樹圖法，根據(jù)所求碼字碼長的大小，構(gòu)造出即時(shí)碼。3.1.5費(fèi)諾編碼

費(fèi)諾編碼屬于統(tǒng)計(jì)匹配編碼，但它不是最佳的編碼方法。費(fèi)諾編碼步驟如下：

(1)將信源消息（符號(hào)）按其出現(xiàn)的概率由大到小依次排列。

(2)將依次排列的信源符號(hào)按概率值分為兩大組，使兩個(gè)組的概率之和近于相同，并對(duì)各組分別賦予一個(gè)二進(jìn)制碼元“0”和“1”。

(3)將每一大組的信源符號(hào)進(jìn)一步再分成兩組，使劃分后的兩個(gè)組的概率之和近于相同，并又分別賦予一個(gè)二進(jìn)制符號(hào)“0”和“1”。

(4)如此重復(fù)，直至每個(gè)組只剩下一個(gè)信源符號(hào)為止。

(5)信源符號(hào)所對(duì)應(yīng)的碼字即為費(fèi)諾碼。

【例3－5】離散獨(dú)立信源

其費(fèi)諾編碼如圖3－7所示。

圖3－7例3－5的費(fèi)諾編碼

信源熵：

(比特/信源符號(hào))平均碼長：

(碼符號(hào)/信源符號(hào))編碼效率：

【例3－6】離散無記憶信源

信源熵：

(比特/信源符號(hào))平均碼長：

(碼符號(hào)/信源符號(hào))編碼效率：

圖3－8例3－6的費(fèi)諾編碼

由上述分析可見，費(fèi)諾碼考慮了信源的統(tǒng)計(jì)特性，使經(jīng)常出現(xiàn)的信源符號(hào)能對(duì)應(yīng)碼長短的編碼字。顯然，費(fèi)諾碼仍然是一種相當(dāng)好的編碼方法。但是，這種編碼方法不一定能使短碼得到充分利用。尤其當(dāng)信源符號(hào)較多，并有一些符號(hào)概率分布很接近時(shí)，分兩大組的組合方法就很多?？赡苣撤N分配結(jié)果會(huì)使得后面小組的“概率和”相差較遠(yuǎn)，因而使平均碼長增加，所以費(fèi)諾碼不一定是最佳碼。費(fèi)諾碼的編碼方法實(shí)際上是構(gòu)造碼樹的一種方法，所以費(fèi)諾碼是一種即時(shí)碼。

3.1.6香農(nóng)－費(fèi)諾－埃利斯碼

香農(nóng)－費(fèi)諾－埃利斯碼不是分組碼，它根據(jù)信源符號(hào)的積累概率分配碼字，不是最佳碼，但它的編碼和譯碼效率都很高。

設(shè)信源

定義信源符號(hào)積累概率

(3－4)式中：ui,uk∈{u1,u2,…,un}。

定義信源符號(hào)修正的積累概率函數(shù)：

（3－5）

由信源符號(hào)積累概率定義可知，F(xiàn)(uk＋1)和F(uk)都是小于1的正數(shù)，可將這些小于1的正數(shù)映射到區(qū)間（0，1]內(nèi)，圖3-9描繪了積累概率分布。

圖3－9積累概率分布圖

由式（3－7）可得香農(nóng)－費(fèi)諾－埃利斯碼平均碼長L為

可見，此碼也是熵編碼，且平均碼長比霍夫碼的平均碼長要多1位碼元。

【例3－7】離散無記憶信源

的香農(nóng)－費(fèi)諾－埃利斯碼編碼如表3－2所示。

表3－2例3－7的香農(nóng)－費(fèi)諾－埃利斯碼碼表

用霍夫曼碼對(duì)例3－7編碼，其編碼效率為100%?？梢?，香濃－費(fèi)諾－埃利斯碼不是最佳碼，它比霍夫曼碼每位信源符號(hào)多1位碼元。

前面討論了信源編碼原理及各種編碼方法,霍夫曼碼的編碼方法保證了概率大的符號(hào)對(duì)應(yīng)于短碼，概率小的符號(hào)對(duì)應(yīng)于長碼，而且所有短碼得到充分利用；且每次縮減信源的最后兩個(gè)碼字總是最后一位不同，前面各位相同，這兩個(gè)特點(diǎn)保證了所得的霍夫曼碼一定是最佳碼。對(duì)信源的N次擴(kuò)展信源同樣可以采用霍夫曼編碼方法，因?yàn)榛舴蚵a是最佳碼，所以編碼后單個(gè)信源符號(hào)所編得的平均碼長隨N的增加很快接近于極限值—信源的熵。

費(fèi)諾碼不一定是最佳碼，但有時(shí)也可獲得最佳的編碼效果。費(fèi)諾碼也是統(tǒng)計(jì)匹配碼，但這種方法不一定能使短碼得到充分利用，這種編碼方法得到碼字是即時(shí)碼。費(fèi)諾編碼方法同樣適合于m元編碼，只需每次分成m組即可。

前面討論了信源編碼原理及各種編碼方法?；舴蚵a的編碼方法保證了概率大的符號(hào)對(duì)應(yīng)于短碼，概率小的符號(hào)對(duì)應(yīng)于長碼，而且所有短碼得到充分利用；且每次縮減信源的最后兩個(gè)碼字總是最后一位不同，前面各位相同。這兩個(gè)特點(diǎn)保證了所得的霍夫曼碼一定是最佳碼。對(duì)信源的N次擴(kuò)展信源同樣可以采用霍夫曼編碼方法，因?yàn)榛舴蚵a是最佳碼，所以編碼后單個(gè)信源符號(hào)所編得的平均碼長隨N的增加很快接近于極限值——信源的熵。

費(fèi)諾碼不一定是最佳碼，但有時(shí)也可獲得最佳的編碼效果。費(fèi)諾碼也是統(tǒng)計(jì)匹配碼，但這種方法不一定能使短碼得到充分利用，這種編碼方法得到碼字是即時(shí)碼。費(fèi)諾編碼方法同樣適合于m元編碼，只需每次分成m組即可。

霍夫曼碼編碼構(gòu)造出來的碼不是惟一的，可是其平均碼長卻是相同的，所以不影響編碼效率和數(shù)據(jù)壓縮性能?；舴蚵a對(duì)不同信源其編碼效率也不盡相同。當(dāng)信源概率是2的負(fù)次冪時(shí)，霍夫曼碼的編碼效率達(dá)到100％；當(dāng)信源概率相等時(shí)，其編碼效率最低。這就告訴我們，在使用霍夫曼碼方法編碼時(shí)，只有當(dāng)信源概率分布很不均勻時(shí)，霍夫曼碼才會(huì)收到顯著的效果。應(yīng)用霍夫曼碼時(shí)，需要與其他編碼結(jié)合起來使用，才能進(jìn)一步提高數(shù)據(jù)壓縮比。例如，在JPEG(靜態(tài)圖像處理標(biāo)準(zhǔn))中，先對(duì)圖像像素進(jìn)行DCT變換、量化、Z形掃描、游程編碼后，再進(jìn)行霍夫曼編碼。因?yàn)榛舴蚵a是變長碼，所以它有變長碼的缺點(diǎn)。最后，因?yàn)樾旁捶?hào)與碼字之間不能用某種有規(guī)律的數(shù)字方法對(duì)應(yīng)起來，所以只能通過某種查表方法建立它們的對(duì)應(yīng)關(guān)系。當(dāng)N增大時(shí)，信源符號(hào)增多，所需存儲(chǔ)的容量增大，使設(shè)備復(fù)雜化，同時(shí)也使編譯碼時(shí)查表搜索時(shí)間增加。盡管如此，霍夫曼方法還是一種較具體和有效的無失真信源編碼方法，它可以編制成在計(jì)算機(jī)上實(shí)現(xiàn)的程序。

3.2算術(shù)編碼

3.2.1積累概率的遞推公式

設(shè)信源

定義信源符號(hào)的積累概率：

ui，u

k∈U

（3-11）由式（3－11）可知：

F（u

k）∈〔0，1）由式（3－11）得:F（u1）＝0，F(xiàn)（u2）＝p（u1），F(xiàn)（u3）＝p（u1）＋p（u2），…且p（ui）＝F（ui＋1）－F（ui）

因?yàn)镕（ui）和F（ui＋1）都是小于1的正數(shù)，因此可用［0，1）區(qū)間的兩個(gè)點(diǎn)來表示，p（ui）就是這兩點(diǎn)間的小區(qū)間的長度。不同的符號(hào)對(duì)應(yīng)不同的小區(qū)間，這些小區(qū)間互不重疊，小區(qū)間內(nèi)的任意的一個(gè)點(diǎn)可作為該符號(hào)的編碼，且此編碼為即時(shí)碼。

設(shè)基本離散獨(dú)立信源序列：

S＝s1s2…sk…sn，(Sk∈U,k＝1，2，…，n則信源序列的積累概率的遞推公式：

（3－12）

式中：F（Su

r）—信源序列S添加一個(gè)新的信源符號(hào)u

r后所得到的新序列Su

r的積累概率；

p（S）—信源序列S

的概率；

F（u

r）—信源符號(hào)ur的積累概率；

p（Su

r）—信源序列S添加一個(gè)新的信源符號(hào)u

r后所得到的新序列Su

r的概率；

p（u

r）—信源符號(hào)u

r的概率。

3.2.2算術(shù)編碼原理

由前面的討論可知，信源符號(hào)的積累概率將區(qū)間［0，1）分成許多互不重疊的小區(qū)間，每個(gè)信源符號(hào)對(duì)應(yīng)一個(gè)不同的小區(qū)間，每個(gè)小區(qū)間的長度等于這個(gè)信源符號(hào)的概率，在此小區(qū)間內(nèi)取一點(diǎn)，該點(diǎn)的取值可作為這個(gè)信源符號(hào)的碼字。這個(gè)原理同樣適用于信源序列。把信源序列的積累概率映射到［0，1）區(qū)間上，使每個(gè)序列對(duì)應(yīng)該區(qū)間內(nèi)的一個(gè)點(diǎn)，這些點(diǎn)把區(qū)間［0，1)分成許多不同的小區(qū)間，這些小區(qū)間的長度等于對(duì)應(yīng)序列的概率，在小區(qū)間內(nèi)取一個(gè)浮點(diǎn)小數(shù)，使其長度與該序列的概率相匹配，因而達(dá)到高效編碼的目的。

設(shè)小區(qū)間左、右端點(diǎn)的值分別用low和high表示，用range表示小區(qū)間的長度，則小區(qū)間左、右端點(diǎn)的遞推公式：

式中：low（Sur）—信源序列S添加一個(gè)新符號(hào)ur后所得到的新序列Sur對(duì)應(yīng)區(qū)間的左端點(diǎn)值；

high（Sur）—信源序列S添加一個(gè)新信源符號(hào)ur后所得到的新序列Sur對(duì)應(yīng)區(qū)間的右端點(diǎn)值；

low（S）—信源序列S對(duì)應(yīng)區(qū)間的左端點(diǎn)值；

range（S）—信源序列S對(duì)應(yīng)區(qū)間的寬度值；

low（ur）—信源符號(hào)ur對(duì)應(yīng)區(qū)間的左端點(diǎn)值；

high（ur）—信源符號(hào)ur對(duì)應(yīng)區(qū)間的右端點(diǎn)值。

（3－13）

使用公式（3-13）計(jì)算小區(qū)間端點(diǎn)值的步驟：

(1)給出信源符號(hào)對(duì)應(yīng)的區(qū)間；

(2)初始時(shí)設(shè)S＝Φ（Φ代表空集），low（Φ）＝0，high（Φ）＝1，range（Φ）＝1；

(3)輸入信源序列的一個(gè)符號(hào)ur，根據(jù)公式（3-13）計(jì)算序列Sur的左右端點(diǎn)值。依次下去，直至全部信源序列對(duì)應(yīng)的區(qū)間被確定為止。

【例3－8】設(shè)信源

求信源序列abda對(duì)應(yīng)的小區(qū)間。

解各個(gè)信源符號(hào)對(duì)應(yīng)的小區(qū)間如表3－3所示。

表3－3例3－8信源符號(hào)對(duì)應(yīng)的小區(qū)間

不同的信源符號(hào)分別對(duì)應(yīng)不同的小區(qū)間,哪個(gè)符號(hào)被設(shè)在哪個(gè)區(qū)段并不重要,也就是說不需要各符號(hào)按概率順序排列,只要編碼和解碼都以同樣的方式進(jìn)行就可以。

信源序列abda對(duì)應(yīng)小區(qū)間的左、右端點(diǎn)的值如表3－4所示,信源序列abda對(duì)應(yīng)區(qū)間端點(diǎn)值的計(jì)算如下。

表3－4信源序列abda對(duì)應(yīng)小區(qū)間的端點(diǎn)值

輸入信源序列的第1個(gè)符號(hào)a：

設(shè)low(Φ)＝0，high(Φ)＝1，range(Φ)＝1；

low(Φa)＝low(Φ)＋range(Φ)×low(a)＝0＋10＝0.000

high(Φa)＝low(Φ)＋range(Φ)high(a)＝0＋10.5＝0.500

輸入信源序列的第2個(gè)符號(hào)b：

low(ab)＝low(a)＋range(a)low(b)＝0.00＋0.50.5＝0.250

high(ab)＝low(a)＋range(a)high(b)＝0.00＋0.50.75＝0.375

同理可計(jì)算出其它數(shù)據(jù)。圖3－10信源序列abda對(duì)應(yīng)區(qū)間劃分

解碼是編碼的逆過程，即根據(jù)接收到的碼字翻譯出對(duì)應(yīng)的信源序列。解碼步驟如下：

(1)判斷碼字落在哪個(gè)符號(hào)區(qū)間，翻譯出1個(gè)符號(hào)。

(2)將碼字減去剛翻譯出的符號(hào)的左端點(diǎn)值。

(3)用剛翻譯出的符號(hào)對(duì)應(yīng)的區(qū)間的長度去除步驟

（2）的結(jié)果，判斷此值落在哪個(gè)符號(hào)區(qū)間，翻譯出1個(gè)新符號(hào)。

(4)重復(fù)步驟（2）、（3），直至全部信源序列被翻譯完為止。

下面以碼字0.359375為例,說明解碼過程。

碼字0.359375落在［0，0.5）之間,即0.359375∈［0，0.5），于是翻譯出第1個(gè)符號(hào)為a；用符號(hào)a對(duì)應(yīng)區(qū)間的長度0.5去除碼字與符號(hào)a的左端點(diǎn)值的差得0.71875,

即(0.359375－0)／０.5＝0.71875∈［0.5,0.75)，則翻譯出第2個(gè)符號(hào)為b；用符號(hào)b對(duì)應(yīng)區(qū)間的長度0.25去除碼字0.71875與符號(hào)b的左端點(diǎn)值的差得0.875,于是翻譯出第3個(gè)符號(hào)為d；用符號(hào)d對(duì)應(yīng)區(qū)間的長度0.125去除碼字0.875與符號(hào)d的左端點(diǎn)值的差得0,碼字0落在［0，0.5）之間,即0∈［0,0.5),于是翻譯出第4個(gè)符號(hào)為a。因此，碼字0.359375對(duì)應(yīng)的序列為abda,解碼正確。

【例3－9】已知信源

求信源序列efbfcafdcc對(duì)應(yīng)的區(qū)間端點(diǎn)值。

解信源符號(hào)區(qū)間劃分如表3－5所示。例3－9信源序列對(duì)應(yīng)的小區(qū)間端點(diǎn)值如表3－6所示。

表3－5例3-9信源符號(hào)對(duì)應(yīng)區(qū)間的端點(diǎn)值

表3－6信源序列efbfcafdcc對(duì)應(yīng)區(qū)間的端點(diǎn)值

3.2.3算術(shù)編碼是熵編碼

從上面的分析可知，不同的信源系列對(duì)應(yīng)不同的小區(qū)間，可取小區(qū)間內(nèi)的一點(diǎn)作為該序列的碼字。怎樣選取該點(diǎn)呢？可以選區(qū)間的左端點(diǎn)的值作為碼字，也可以選取區(qū)間的中點(diǎn)作為碼字。碼字長度選取的原則主要是使其與該序列的概率匹配，所以可根據(jù)下式選碼長L：

取信源序列碼字的前L位，若后面有尾數(shù)就進(jìn)位到第L位,這樣得到的數(shù)就是序列的編碼C。

例如：p（S）＝3/16，序列S左端點(diǎn)的值為0.011011,則L＝3,得序列S的碼字C＝100。

下面證明這樣得到的碼字C必然在序列對(duì)應(yīng)的小區(qū)間內(nèi),因此是可以惟一解碼的碼字。

根據(jù)碼字C的選取可以知道，當(dāng)F（S）在L位以后沒有尾數(shù)時(shí)C＝F（S），否則C>F（S）,所以

C≥F（S）

（3－15）

由式（3－14）可知：

（3－16）

則信源序列S對(duì)應(yīng)區(qū)間的右端點(diǎn)的值：

（3－17）

根據(jù)二進(jìn)制小數(shù)截去位數(shù)的影響得：

（3－18）

由式（3－17）和式（3－18）得：

C<F（S）＋p（S）

（3－19）因此信源序列S碼字C落在該序列對(duì)應(yīng)的區(qū)間［F（S），F(xiàn)（S）＋p（S））內(nèi)。

根據(jù)信源編碼定理可知信源序列S的平均碼長滿足：

平均每個(gè)信源符號(hào)的碼長：

（3－20）對(duì)于無記憶信源有H（Sn）＝nH（S），則（3－21）

3.2.4算術(shù)編碼方法

實(shí)際編碼時(shí)，用遞推公式可逐位計(jì)算序列的積累概率，只要存儲(chǔ)器容量允許，無論序列有多長，皆可一直計(jì)算下去，直至序列結(jié)束。

下面給出用序列積累概率的遞推公式進(jìn)行序列的算術(shù)編碼的計(jì)算步驟：

(1)根據(jù)式(3-11)計(jì)算信源符號(hào)的積累概率；

(2)初始時(shí)設(shè)S＝Φ，F(xiàn)（Φ）＝0，p（Φ）＝1（Φ代表空集）；

(3)根據(jù)式（3－12）計(jì)算序列的積累概率F（Sui）和序列的概率p（Sui）。

(4)根據(jù)式（3－14）計(jì)算碼長L。

(5)將F(S)寫成二進(jìn)制數(shù)的形式,如果小數(shù)點(diǎn)后只有L位數(shù)據(jù)，則取其前L位作為序列S的碼字；如果小數(shù)點(diǎn)后有多于L位數(shù)據(jù)，則取其前L位加1作為序列S的碼字。【例3－10】設(shè)二元獨(dú)立信源

求信源序列1010的算術(shù)編碼。

解信源符號(hào)的積累概率：F（0）＝0；F（1）＝0.25,則信源序列1010算術(shù)編碼的相關(guān)數(shù)據(jù)如表3－7所示，表中數(shù)據(jù)為二進(jìn)制形式。表3－7信源序列1010算術(shù)編碼

表3-7中數(shù)據(jù)的計(jì)算：因?yàn)镕(Φ)＝0,

p(Φ)＝1，則輸入信源序列的第1個(gè)符號(hào)1：

F(Φ1)＝F(Φ)＋p(Φ)F(1)＝0＋10.25＝0.01

P(Φ1)＝p(Φ)p(1)＝0.11

輸入信源序列的第2個(gè)符號(hào)0：

F(10)＝F(1)＋p(1)F(0)＝0.01＋０．７５０＝０．０１

P(10)＝p(1)p(0)＝０．７５０．２５＝0.0011

同理可計(jì)算出其它數(shù)據(jù)，信源序列1010算術(shù)編碼對(duì)應(yīng)圖解如圖3-11所示。

圖3-11信源序列1010算術(shù)編碼圖解

【例3－11】設(shè)二元獨(dú)立信源

求信源序列11111100的算術(shù)編碼。

表3－8信源序列11111100算術(shù)編碼

【例3－12】已知信源

求信源序列abda的算術(shù)編碼。

解信源符號(hào)的積累概率如表3－9所示。信源序列abda的算術(shù)編碼如表3－10所示。表3－9例3－12信源符號(hào)的積累概率

表3－10信源序列abda算術(shù)編碼

表3-10中數(shù)據(jù)的計(jì)算，設(shè)F(Φ)＝0,

p(Φ)＝1，則

輸入信源序列的第1個(gè)符號(hào)a：

F(Φa)＝F(Φ)＋p(Φ)F(a)＝0＋1×0＝(0.0)2

P(Φ1)＝p(Φ)p(a)＝１×0.5＝(0.1)2

輸入信源序列的第2個(gè)符號(hào)b：

F(ab)＝F(a)＋p(a)F(b)＝０＋0.5×0.5＝(0.01)2

P(ab)＝p(a)p(b)＝0.5×0.25＝(0.001)2

同理可計(jì)算出其它數(shù)據(jù)，由此得序列abda的編碼為0101110。編碼圖解如圖3-12所示。

圖3－12信源序列abda算術(shù)編碼圖解

每次遞推運(yùn)算中都有乘法,當(dāng)序列概率和符號(hào)的積累概率展開成二進(jìn)位小數(shù)后的位數(shù)較多且要求精度較高時(shí)，就有一定的運(yùn)算量。這種運(yùn)算必須在輸入一個(gè)信源符號(hào)的時(shí)間內(nèi)完成，以保證實(shí)時(shí)編譯碼。要消除乘法，有兩種方法:一種方法是，編碼對(duì)象是二元序列，而且其符號(hào)概率較小的一個(gè)為2-k的形式，其中k是正整數(shù)，此時(shí)乘以2-k等于移位，乘以1-2-k等于移位和相減,這樣就可做到完全沒有乘法運(yùn)算，可加快運(yùn)算速度；另一種方法就是采用3.2.5節(jié)中介紹的不做乘法的算術(shù)編碼。關(guān)于計(jì)算精度問題，即使在二元序列的情況下，精度問題仍存在。隨著遞推運(yùn)算的延續(xù)，F(xiàn)(S)和p(S)的小數(shù)位數(shù)也將逐步增加，若不能隨時(shí)輸出和加以截?cái)?，運(yùn)算器將難于容納,但有所截?cái)啾厝唤档途?而精度不夠會(huì)影響編、譯碼的正確性。這是因?yàn)殡S著序列長度增大，小區(qū)間數(shù)目越來越多，長度越來越短,計(jì)算精度不夠，會(huì)使有些小區(qū)間互相重疊或消失(即長度零)。

前者使惟一性喪失，后者使無碼字可編。這當(dāng)然會(huì)造成差錯(cuò)，因此算術(shù)編碼也就不是無損編碼，而且這些差錯(cuò)還會(huì)擴(kuò)散。另一個(gè)問題是存儲(chǔ)量問題。編成的碼字的長度也是隨序列占的長度增加而不斷增長,若不及時(shí)輸出，存儲(chǔ)量將非常大；但若輸出過早，運(yùn)算過程中可能還需調(diào)整已輸出的部分，那就來不及了。但當(dāng)未輸出部分的前面各位都是“1”時(shí)，后面在計(jì)算時(shí)略有增加，就可能進(jìn)位到已輸出部分。尤其當(dāng)這種連“1”很長時(shí)，原以為保留很多位應(yīng)已足夠，但仍會(huì)影響已輸出部分。從理論上說，這種連“1”的長度可以達(dá)到無限，當(dāng)然出現(xiàn)這種情況的概率也接近零。這類問題常稱為進(jìn)位問題，在實(shí)際應(yīng)用時(shí)也必須設(shè)法解決。

3.2.5不做乘法的算術(shù)編碼

從上面的討論可知，信源序列不同，其積累概率的值不同。這些相異的值對(duì)應(yīng)區(qū)間［0，1）上不同的點(diǎn)，它們把區(qū)間［0，1）分成許多小區(qū)間段，這些小區(qū)間的長度等于對(duì)應(yīng)序列的概率。一般情況下，取小區(qū)間的左端點(diǎn)的值作為序列的編碼，使其長度與該序列的概率相匹配，這樣便可求得序列的碼字C（S），并達(dá)到高效編碼的目的。由于每次使用遞推公式進(jìn)行計(jì)算時(shí)都有乘法運(yùn)算，因而若要求精度較高，就有一定的計(jì)算量。這種運(yùn)算必須在輸入一個(gè)信源符號(hào)的時(shí)間內(nèi)完成，以保證實(shí)時(shí)編、解碼，但有時(shí)會(huì)造成困難。那么怎樣才能消除乘法?下面討論這個(gè)問題。

信源序列積累概率的遞推公式為

F（Sur）＝F（S）＋p（S）F（ur）p（Sur）＝p（S）p（ur）

則二元信源序列積累概率的遞推公式如下：

F（S0）＝F（S）＋p（S）F（0）＝F（S）F（S1）＝F（S）＋p（S）F（1）p（S1）＝p（S）p（1）

p（S0）＝p（S）p（0）

且

p（S）＝p（S0）＋

p（S1），F(xiàn)（1）＝p（0）

如果令p（S1）≈2-qp（S）,則不做乘法的二進(jìn)制算術(shù)編碼的遞推公式為p（S0）＝p（S）－p（S1）

F（S0）＝F（S）

F（S1）＝F（S）＋p（S）F（1）＝

F（S）＋p（S）p（0）＝

F（S）＋

p（S0）

即

p（S1）≈2-qp（S）（3-22）p（S0）＝p（S）－p（S1）（3-23）F（S0）＝F（S） （3-24）

F（S1）＝

F（S）＋

p（S0）

（3-25）

不做乘法的算術(shù)編碼步驟：

（1）初始時(shí)，設(shè)S＝Φ，P（Φ）＝0.111…1,F（Φ）＝0.000…0

（2）輸入1個(gè)信源個(gè)符號(hào)，用遞推公式（3-22）~（3-25）計(jì)算p（S1）、p（S0）、F（S0）、F（S1）；

（3）重復(fù)步驟（2），直至信源序列結(jié)束。由于序列S是用子區(qū)間[F(S),F(S)＋p(S))中的一個(gè)點(diǎn)表示其編碼的,因此解碼時(shí)只要判斷序列的碼字落在哪個(gè)區(qū)間,就一定能正確的譯碼。與編碼過程相對(duì)應(yīng)，下面給出不做乘法的二進(jìn)制算術(shù)譯碼步驟：

（1）

設(shè)P（S*）＝0.1111,C(S*)就是已編出的碼字。

（2）

計(jì)算：

p（S*1）＝2-qp（S*）

p（S*0）＝p（S*）－p（S*1）

（3）將碼字C(S*)與p（S*0）比較，確定當(dāng)前字符是1還是0：

若C(S*)－p（S*0）<０，則當(dāng)前字符為0

若C(S*)－p（S*0）≥０，則當(dāng)前字符為1

（4）重復(fù)步驟（2）、（3）直到解碼結(jié)束。

由于右移q位后使p（S）前面出現(xiàn)了越來越多的0，這種情況在具體實(shí)現(xiàn)時(shí)是很不經(jīng)濟(jì)的，如果用浮點(diǎn)數(shù)表示就可解決此問題。若p（S）前面出現(xiàn)了m個(gè)0，可將其左移m位，以保留足夠的有效位數(shù)，同時(shí)F（S）也左移m位，然后再用遞推公式進(jìn)行計(jì)算。

由不做乘法的二進(jìn)制算術(shù)編碼、譯碼的過程看到，q的確定是非常重要的。根據(jù)p（S1）≈2-qp（S）可知，實(shí)際應(yīng)用時(shí)，可以取2-q近似等于二元序列中小概率符號(hào)的概率值。在實(shí)際問題中,小概率符號(hào)不可能正好等于2-q,只能使2-q的值接近小概率符號(hào)的值。這樣對(duì)編碼有什么影響呢？當(dāng)序列很長時(shí)，序列的概率已很小，碼字長度將接近此概率倒數(shù)的對(duì)數(shù)。按2-q編碼時(shí)，每個(gè)符號(hào)“0”需要q比特，每個(gè)符號(hào)“1”需要-lb（1-2-q）比特，所以每個(gè)符號(hào)的平均碼長L為信源的熵為

H(U)＝－p(0)lbp(0)－（1－p（0））lb（1－p(0)）當(dāng)p(0)＝2-q時(shí),L＝H(U),此時(shí)編碼效率等于1。一般實(shí)際編碼中，p（0）≈2-q，此時(shí)編碼效率可在95%以上?？梢?，用2-q來近似所造成的損失并不大，但近似后的計(jì)算量卻減小很多，尤其是當(dāng)符號(hào)的小概率值很小時(shí)，損失更小。所以在用算術(shù)編碼對(duì)二元信源序列編碼時(shí)，經(jīng)常采用這種近似。 3.3游程編碼

3.3.1游程和游程序列

算術(shù)編碼是解決小消息信源問題的一種很好的方案，另外，游程編碼也是解決小消息信源問題的一種很好的方案。下面介紹游程編碼的相關(guān)知識(shí)。

二元序列只有兩種值，分別用“0”和“1”表示，這兩種符號(hào)可連續(xù)出現(xiàn)，就形成了“0”游程和“1”游程?！?”游程和“1”游程總是交替出現(xiàn)的，連“0”符號(hào)的個(gè)數(shù)稱“0”游程長度，連“1”符號(hào)的個(gè)數(shù)稱“1”游程長度。這樣可把二元序列變換為游程長度序列，且二者是可逆的。例如：二元序列為 000011111001111110000000111111…

對(duì)應(yīng)的游程長度序列為

452676…如果規(guī)定序列從“0”開始，那么很容易將游程長度序列恢復(fù)成二元序列。游程長度序列是多元序列，如果計(jì)算出各個(gè)游程長度的概率，就可對(duì)各游程長度進(jìn)行霍夫曼編碼或用其他編碼方法進(jìn)行處理，以達(dá)到壓縮編碼的目的。

多元信源序列也存在相應(yīng)的游程長度序列。m元序列有m種游程，且某個(gè)游程L（ur）的前面和后面出現(xiàn)什么符號(hào)對(duì)應(yīng)的游程是無法確定的，因此這種變換必須再加一些符號(hào)，才能使m元序列和其對(duì)應(yīng)的游程長度序列是可逆的。

3.3.2游程編碼是熵編碼

二元序列中，不同的“0”游程長度對(duì)應(yīng)不同的概率；不同的“1”游程長度也對(duì)應(yīng)不同的概率，這些概率叫游程長度概率。對(duì)不同的游程長度，按其不同的發(fā)生概率，分配不同的碼字，這就是游程編碼的基本思想。游程編碼可以將兩種符號(hào)游程分別按其概率進(jìn)行編碼，也可以將兩種游程長度混合起來一起編碼。下面討論游程長度編碼平均碼長的極限值。

考慮兩種游程分開編碼的情況。為了討論方便，規(guī)定兩種游程分別用白、黑表示。白游程熵：

(3－26)式中：lw—白游程長度；

p(lw)—白游程長度概率；

L—白游程最大長度。根據(jù)信源編碼定理可知白游程平均碼長LW應(yīng)滿足：

(3－27)令為白游程長的平均像素值，則

（3－28）

由式（3－27）和（3－28）得：

(3－29)令每個(gè)白像素的熵值為hＷ,則

每個(gè)白像素的平均碼長：

代入式（3－29）得：

（3－30）

同理對(duì)黑游程可求出：

(3－31)(3－32)每個(gè)像素平均碼長：

3.4通用編碼

3.4.1分段編碼

設(shè)m元信源序列：

S＝s1,s2,…,sn，si∈{u1，u2，…，um},i＝1,2,…，n。

所謂分段編碼,就是將序列分成不同的幾段。分段規(guī)則是盡可能取最少個(gè)連著的信源符號(hào)，并保證各段都不相同。設(shè)信源序列按此規(guī)則分段的結(jié)果為

y1,y2,y3,…，

yc

(3－38)式中：c——序列段數(shù)。

若j>i,則

yj

＝y(tǒng)iur

（3－39）

即第j段是由第i段后續(xù)一個(gè)信源符號(hào)ur構(gòu)成的，或者說第j段可用兩個(gè)數(shù)字i和r來確定。由于r<m，這兩個(gè)數(shù)可用一個(gè)數(shù)Nj來表示，即Nj＝mi＋r

(3－40）

式中：m—信源符號(hào)集中元素個(gè)數(shù)；

i—信源序列的第i段段號(hào)；

r—信源符號(hào)集中第r個(gè)信源符號(hào)的序號(hào)；

Nj—第j段的碼字。

第j段編碼的碼長

(3－41)將Nj編成二進(jìn)制碼，取lj位傳送出去；在接收端，由i可以找到第i段，再加上一個(gè)信源符號(hào)ur就可無差錯(cuò)地恢復(fù)第j段。用m除以Nj后所得的商為i,余數(shù)為r。下面舉例說明這種編碼方法。[例3-13]設(shè)信源符號(hào)集為：U＝｛a0,a1,a2,a3｝,求信源序列a0

a0a2

a3

a1

a1

a0

a0

a0a3

a2

的LZ編碼？

解:將信源序列按上述規(guī)則分成7段：

a0，a0a2，a3，a1，a1

a0，a0

a0，a3a2

各段參量如表3-11所示。

表3－11例3－13分段編碼表

3.4.2段匹配碼

段匹配碼實(shí)質(zhì)上也是一種分段編碼，編碼規(guī)則也是盡可能取最少個(gè)連著的信源符號(hào)，并保證各段都不相同。段匹配碼將段號(hào)和信源符號(hào)分別進(jìn)行編碼，這樣處理后，在實(shí)際應(yīng)用時(shí)比較容易處理。若組成二元碼，段號(hào)所需碼長：

(3－42)式中:c——信源序列所分段數(shù)。每個(gè)信源符號(hào)所需碼長：

(3－43)式中：m——信源符號(hào)集中元素個(gè)數(shù)。

[例3-14]

信源符號(hào)集為U＝｛a0,a1,a2,a3｝，求信源序列a0

a0

a2

a3

a1

a1

a0

a0

a0

a3

a2的段匹配碼。

解:根據(jù)上述分段原則信源序列分為7段：

a0,a0

a2,a3,a1,a1

a0,a0

a0,a3

a2

編碼字典表如表3-12所示。

表3－12例3－14的編碼字典表

若組成二元碼，段號(hào)所需碼長l1＝［lb7］＝3,即3位二進(jìn)制數(shù)。m＝4,由式（3－43）得每個(gè)信源符號(hào)需用2位二進(jìn)制數(shù)，即a0，a1，a2，a3編碼分別為00，01，10，11。段號(hào)1～7編碼分別為

000，001，010，011，100，101，110則信源序列對(duì)應(yīng)編碼序列為

0000000100100101101101100010010100001101110由上述編碼方法可知，長為n的信源序列被分成了c段，每段二元碼符號(hào)長度為l1＝［lbc］,每個(gè)信源符號(hào)二元碼長l2＝［lbm］。每段所需二元符號(hào)的碼長為［lbc］＋［lbm］，則c段所需二元碼的碼長為c（［lbc］+［lbm］）。所以每個(gè)信源符號(hào)所需碼長L為

則

設(shè)長度為k的段有mk種。若把長度為n的序列分成c段后，設(shè)最大的段的長度為K,且所有長度小于或等于K的段型都存在，則有

(3－46)及

(3－47)當(dāng)Ｋ→∞時(shí)，式（3－46）和式（3－47）可分別近似為

(3－48)(3－49)則

n≈Kc

(3－50)將式(3－50)代入式（3－45）,得

(3－51)現(xiàn)考慮平穩(wěn)無記憶m元信源序列。設(shè)信源符號(hào)概率為pi(i＝0,1,…,m－1)。當(dāng)最長的段長K→∞時(shí)，典型的段中ai將出現(xiàn)piK個(gè)。這種段型共有N種,則

(3－52)則

(3－53)忽略較短的段型，則

n＝NK＝K2KH(U)

(3－54)所以

C≈N≈2KH(U)

(3－55)將式（3－55）代入式（3－51）得

(3－56)所以當(dāng)K→∞時(shí),(3－57)3.4.3

LZW碼

LZW算法首先用于UNIX等操作系統(tǒng)作為標(biāo)準(zhǔn)文件壓縮命令，然后運(yùn)用在數(shù)據(jù)通信系統(tǒng)，形成有專利保護(hù)的數(shù)據(jù)壓縮工具。LZW算法已經(jīng)作為一種通用壓縮方法，廣泛應(yīng)用于任何二值數(shù)據(jù)的壓縮。LZW壓縮算法的基本思想是建立一個(gè)編碼表(轉(zhuǎn)換表)，韋爾奇稱之為串表，該表將輸入字符串映射成定長的碼字輸出，通常碼長設(shè)為12bit?？梢园褦?shù)字圖像當(dāng)做一個(gè)一維比特串，算法在產(chǎn)生輸出串的同時(shí)動(dòng)態(tài)地更新編碼表，這樣碼表與串表對(duì)應(yīng)產(chǎn)生壓縮信源的特殊性質(zhì)。LZW編碼形成經(jīng)過了兩個(gè)階段：LZ編碼和LZW編碼。LZ碼將變長的輸入符號(hào)串映射成定長或長度可測(cè)的碼字，LZ算法將長度不同的符號(hào)串(短語)編碼成一個(gè)一個(gè)的新“單詞”，它們形成了一本“短語詞典”的索引。若單詞的碼字短于它所代表的短語，就達(dá)到