《編碼理論》課件第3章

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

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

3.2算術(shù)編碼

3.3游程編碼

3.4通用編碼

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

3.1.1二元霍夫曼碼

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

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

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

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

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

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

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

信源熵：

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

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

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

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

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

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

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

(碼符號/信源符號)信源熵：

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

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

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

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

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

3.1.2

m元霍夫曼碼

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

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

（3-1）

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

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

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

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

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

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

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

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

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

信源熵：

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

因為lb3＝1.58(比特/信源符號),lb4＝2(比特/信源符號)，所以它們的編碼效率分別為：

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

3.1.4香農(nóng)編碼

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

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

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

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

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

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

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

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

求香農(nóng)編碼。

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

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

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

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

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

信源符號概率累加概率碼字長度二元碼字0.200.002.3430000.190.202.4130010.180.392.4830110.170.572.5631000.150.742.7431010.100.893.34411100.010.996.6671111110平均碼長：

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

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

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

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

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

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

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

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

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

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

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

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

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

(5)信源符號所對應(yīng)的碼字即為費諾碼。

【例3－5】離散獨立信源

其費諾編碼如圖3－7所示。

圖3－7例3－5的費諾編碼

信源熵：

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

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

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

信源熵：

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

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

圖3－8例3－6的費諾編碼

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

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

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

設(shè)信源

定義信源符號積累概率

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

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

（3－5）

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

圖3－9積累概率分布圖

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

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

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

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

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

用霍夫曼碼對例3－7編碼，其編碼效率為100%。可見，香濃－費諾－埃利斯碼不是最佳碼，它比霍夫曼碼每位信源符號多1位碼元。

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

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

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

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

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

3.2算術(shù)編碼

3.2.1積累概率的遞推公式

設(shè)信源

定義信源符號的積累概率：

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）

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

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

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

（3－12）

式中：F（Su

r）—信源序列S添加一個新的信源符號u

r后所得到的新序列Su

r的積累概率；

p（S）—信源序列S

的概率；

F（u

r）—信源符號ur的積累概率；

p（Su

r）—信源序列S添加一個新的信源符號u

r后所得到的新序列Su

r的概率；

p（u

r）—信源符號u

r的概率。

3.2.2算術(shù)編碼原理

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

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

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

high（Sur）—信源序列S添加一個新信源符號ur后所得到的新序列Sur對應(yīng)區(qū)間的右端點值；

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

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

low（ur）—信源符號ur對應(yīng)區(qū)間的左端點值；

high（ur）—信源符號ur對應(yīng)區(qū)間的右端點值。

（3－13）

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

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

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

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

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

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

解各個信源符號對應(yīng)的小區(qū)間如表3－3所示。

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

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

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

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

輸入信源序列的第1個符號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個符號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

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

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

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

(2)將碼字減去剛翻譯出的符號的左端點值。

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

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

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

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

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

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

【例3－9】已知信源

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

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

表3－5例3-9信源符號對應(yīng)區(qū)間的端點值

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

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

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

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

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

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

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

C≥F（S）

（3－15）

由式（3－14）可知：

（3－16）

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

（3－17）

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

（3－18）

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

C<F（S）＋p（S）

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

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

平均每個信源符號的碼長：

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

3.2.4算術(shù)編碼方法

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

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

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

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

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

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

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

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

解信源符號的積累概率：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ù)的計算：因為F(Φ)＝0,

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

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

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

輸入信源序列的第2個符號0：

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

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

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

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

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

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

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

【例3－12】已知信源

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

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

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

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

p(Φ)＝1，則

輸入信源序列的第1個符號a：

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

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

輸入信源序列的第2個符號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

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

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

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

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

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

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

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

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è)S＝Φ，P（Φ）＝0.111…1,F（Φ）＝0.000…0

（2）輸入1個信源個符號，用遞推公式（3-22）~（3-25）計算p（S1）、p（S0）、F（S0）、F（S1）；

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

（1）

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

（2）

計算：

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，這種情況在具體實現(xiàn)時是很不經(jīng)濟(jì)的，如果用浮點數(shù)表示就可解決此問題。若p（S）前面出現(xiàn)了m個0，可將其左移m位，以保留足夠的有效位數(shù)，同時F（S）也左移m位，然后再用遞推公式進(jìn)行計算。

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

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

3.3.1游程和游程序列

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

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

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

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

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

3.3.2游程編碼是熵編碼

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

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

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

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

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

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

（3－28）

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

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

每個白像素的平均碼長：

代入式（3－29）得：

（3－30）

同理對黑游程可求出：

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

3.4通用編碼

3.4.1分段編碼

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

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

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

y1,y2,y3,…，

yc

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

若j>i,則

yj

＝y(tǒng)iur

（3－39）

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

(3－40）

式中：m—信源符號集中元素個數(shù)；

i—信源序列的第i段段號；

r—信源符號集中第r個信源符號的序號；

Nj—第j段的碼字。

第j段編碼的碼長

(3－41)將Nj編成二進(jìn)制碼，取lj位傳送出去；在接收端，由i可以找到第i段，再加上一個信源符號ur就可無差錯地恢復(fù)第j段。用m除以Nj后所得的商為i,余數(shù)為r。下面舉例說明這種編碼方法。[例3-13]設(shè)信源符號集為：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段匹配碼

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

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

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

[例3-14]

信源符號集為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的編碼字典表

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

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

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

則

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

(3－46)及

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

(3－48)(3－49)則

n≈Kc

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

(3－51)現(xiàn)考慮平穩(wěn)無記憶m元信源序列。設(shè)信源符號概率為pi(i＝0,1,…,m－1)。當(dāng)最長的段長K→∞時，典型的段中ai將出現(xiàn)piK個。這種段型共有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→∞時,(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壓縮算法的基本思想是建立一個編碼表(轉(zhuǎn)換表)，韋爾奇稱之為串表，該表將輸入字符串映射成定長的碼字輸出，通常碼長設(shè)為12bit?？梢园褦?shù)字圖像當(dāng)做一個一維比特串，算法在產(chǎn)生輸出串的同時動態(tài)地更新編碼表，這樣碼表與串表對應(yīng)產(chǎn)生壓縮信源的特殊性質(zhì)。LZW編碼形成經(jīng)過了兩個階段：LZ編碼和LZW編碼。LZ碼將變長的輸入符號串映射成定長或長度可測的碼字，LZ算法將長度不同的符號串(短語)編碼成一個一個的新“單詞”，它們形成了一本“短語詞典”的索引。若單詞的碼字短于它所代表的短語，就達(dá)到