第4章熵保持編碼4.1

Huffman編碼

4.2游程編碼

4.3

Golomb編碼與通用變長碼

4.4算術編碼

4.5字典碼

習題與思考題

4.1

Huffman編碼

4.1.1

Huffman碼的構造

1.最佳碼和最佳編碼定理

在介紹具體的Huffman編碼方法之前，先介紹最佳碼的概念和最佳編碼定理。

對于某一信源和某一碼符號集來說，若有一個唯一可譯碼，其平均長度小于所有其它唯一可譯碼的平均長度，則該碼稱為緊致碼，或稱最佳碼。

變字長最佳編碼定理：在變字長編碼中，對于概率大的信源符號編以短字長的碼，對于概率小的符號編以長字長的碼；如果碼字長度嚴格按照所對應符號出現概率大小逆順序排列，則平均碼字長度一定小于其他任何符號順序排列方法。證明：設最佳排列方式的碼字平均長度為，則

其中,P(ai)為信源符號ai的出現概率，ni為給符號ai編成的碼字的長度，而P(ai)≥P(as),nl≤ns(l，s=1,2,…,m)。

如將al的碼字與as的碼字互換，其余碼字不變，經過這樣的互換以后，平均碼字長度變為，則應為加上兩碼字互換后與互換前的平均長度之差，即

因為ns≥nl

，P(al)≥P(as)，所以≥。這就是說，是最短的。證畢。

2.二元Huffman碼

Huffman編碼理論正是基于如上定理的，其碼字為最佳碼。具體的二進制Huffman編碼步驟如下：

(1)將信源消息符號按其出現的概率大小降序排列；

(2)取兩個概率最小的符號分別配以0和1兩個碼元，并將這兩個概率相加作為一個新符號的概率，與未分配的符號重新排隊；

(3)對重排后的兩個概率最小符號重復步驟(2)的過程。

(4)不斷繼續上述過程，直到最后兩個符號配以0和1為止。

(5)從最后一級開始，向前返回得到各個信源符號所對應的碼元序列，即相應的碼字。

下面我們給出一個具體的例子來說明這種編碼方法。

【例4-1】已知6符號離散信源的出現概率為

，試計算它的熵、Huffman編碼、平

均碼長及編碼效率。

【解】該離散信源的熵為

Huffman編碼過程如圖4-1所示。圖4-1霍夫曼編碼示例平均碼長為

編碼效率為

在上面例子中，由于每個符號的編碼碼長數正好等于每個符號出現的自信息量，因此最后達到了理想的編碼效率。實際信源編碼過程中，由于很難保證每個符號的編碼碼長等于其自信息量這一點，因此編碼效率一般都小于100%。另外需要指出的是，Huffman編碼碼字本身并不是唯一的，但是Huffman編碼的平均碼長是唯一的。造成Huffman編碼碼字不唯一的原因主要有兩個：

①每次對信源縮減時，賦予信源最后兩個概率最小的符號，因為0和1可以是任意的，所以可以得到不同的Huffman碼，但不會影響碼字的長度；

②對信源進行縮減時，兩個概率最小的符號合并后的概率與其他信源符號的概率相同，這兩者在縮減信源中進行概率排序時位置次序可以任意，因此會得到不同的Huffman碼。此時，會影響碼字的長度，一般將合并的概率放在上面，這樣可獲得較小的碼方差。

【例4-2】設有離散無記憶信源

，試用不同的合并排序法進行Huffman編碼。

【解】表4-1和表4-2給出了兩種不同的合并排序法的Huffman編碼的結果。在兩個概率最小的符號合并后的概率與其他信源符號的概率相同時，表4-1將合并后的符號概率排在幾個相同概率符號的最后，而表4-2則排在最前，這樣就能得到不同碼字長度的Huffman碼。表4-1

Huffman編碼方法一表4-2

Huffman編碼方法二由表4-1和表4-2可以看到，對同一個信源，由于信源符號縮減時排序的不同，造成了不同的碼長。這兩種碼的平均碼長分別為

可見，雖然兩種方法的Huffman碼的碼長不同，但平均碼長還是一樣的，因而編碼效率也相同。在這種情況下，這兩種碼的質量可以根據碼方差來衡量。碼方差越小，說明越接近等長碼，因而質量越好。碼方差定義為

根據式（4-1），可以計算表4-1和表4-2的碼方差分別為1.36和0.16。因而編碼方法二得到的碼要優于編碼方法一得到的碼。

由此得出，在Huffman編碼過程中，為得到碼方差最小的碼，當重新排列縮減信源的概率分布時，應使合并的概率和盡量處于最高的位置，這樣可使合并的信源符號重復編碼次數減少，使得碼的方差變小。從以上編碼的實例中可以看出，Huffman編碼的核心思想為：合二為一，即把兩個概率最小的信源符號合并成一個新的信源符號，直到剩下最后一個符號，其概率為1。

Huffman碼具有以下兩個明顯特點，這兩個特點保證了所得的Huffman碼一定是緊致碼：

(1)Huffman碼的編碼方法保證了概率大的符號對應于短碼，概率小的符號對應于長碼，而且所有短碼都得到了充分利用；

(2)每次縮減信源的最后二個碼字總是最后一位不同，前面各位相同。

3.r元Huffman碼

上面討論的是二元Huffman碼，它的編碼方法同樣可以推廣到r元編碼中來。不同的只是“合2為1”變為“合r為1”，即每次把r個概率最小的符號合并成一個新的信源符號，并分別用0、1、…、r－1等碼元表示。

為了充分利用短碼，使Huffman碼的平均碼長為最短，必須使最后一步的縮減信源有r個信源符號。因此，對于r元編碼，信源X的符號個數q必須滿足

q=(r－1)θ+r(4-2)

其中,θ表示縮減的次數，r－1為每次縮減所減少的信源符號個數。對于二元碼，信源X的信源符號個數q必須滿足：q=q+2,因此，q為任意正整數時一定能找到一個q使式q=(r－1)q+r滿足。

而對于r元碼，q為任意正整數時不一定能找到一個整數q使式q=(r－1)q+r滿足。若q不滿足式q=(r－1)q+r時，則用虛設符號方法，增補一些概率為零的信源符號，即添加一些信源符號：sq+1,sq+2,…,sq+t，并使它們對應的概率為零，即pq+1=pq+2=…=pq+t=0。此時，使得q+t滿足式q+t=(r－1)q+r。另外，由于添設的信源符號的概率為0，因此對實際的Huffman編碼過程沒有影響。這樣得到的r元Huffman碼一定是緊致碼。

【例4-3】信源X有6種符號，輸出概率為0.32、0.22、0.18、0.16、0.08和0.04，試用三元Huffman碼編碼該信源。

【解】在本例中，r=3，若取q=6，則不能找到滿足q=(r－1)q+r的整數q。因此必須采用虛設符號方法，添設1個概率為0的符號，使得q=7，q=2，從而滿足式q=(r－1)q+r。

因此，信源X的三元Huffman碼編碼過程及碼字如表4-3所示，其中符號s7是假設的信源符號，這樣編碼使短碼得到充分利用，平均碼長為最短。根據表4-3所示的編碼過程，我們可以畫出如圖4-2所示的三元Huffman碼的碼樹。表4-3三元Huffman碼圖4-2表4-3中三元Huffman碼的碼樹另外，需要指出的是：

(1)當信源符號個數q不滿足式q=(r－1)q+r時，所得的樹一定是非整樹。

(2)當信源符號q滿足式q=(r－1)q+r時，則得到的r元Huffman碼樹一定是整樹。所以二元Huffman碼樹一定是整樹。

這里，整數是指r元樹的每一個非葉節點具有r個子節點；反之，若不滿足這一點，就是非整數。

從樹的角度來看，這種編碼方法是盡量利用短碼。首先，把一階節點全都用上；如果碼字不夠時，再從某個節點伸出若干枝，引出二階節點作為終端節點，生成碼字；再不夠時，再伸出三階節點。如此類推，顯然這樣得到的碼，其平均碼長最短。4.1.2截斷Huffman編碼

實際編碼時，Huffman編碼器一般都采用事先設計好的碼表。由于Huffman編碼是無損編碼，因而碼表中信源符號與碼字是一一對應的，這樣當信源的符號數非常多時，其對應的碼表也就會非常大。碼表大所需的存儲空間就大，因而編碼器的空間復雜度會提高；同樣的碼表，查表的時間也會變長，因而編碼器的時間復雜度也會提高。因此，Huffman編碼的輸入符號數經常受限于可實現的碼表大小。在實際的語音圖像壓縮編碼應用中，輸入符號數一般還是非常多的。例如，用于壓縮連續色調靜止圖像的JPEG標準，其直流系數的理論動態范圍在－1024～+1023之間，而差分值DIFF的理論動態范圍更高，達到－2047～+2047。如果每個值都賦予一個碼字，則碼表需要212－1=4095項。為此，JPEG采用將碼字截斷為“前綴碼(SSSS)+尾碼”的方法，對碼表進行了簡化。

前綴碼用來指明尾碼的有效位數(設為B位)，用標準的Huffman編碼；尾碼則直接用B位自然二進制碼。當前綴碼給定后，它為定長碼。對于8位量化的圖像，SSSS的范圍為0～11，故其碼表只需12項，如表4-4所示。根據DIFF的值由表4-4查出其前綴碼字和尾碼的位數B后，則可以按式(4-3)得到B位尾碼的碼字。

按此規則，當DIFF非負時，尾碼的最高位是“1”；而當DIFF為負數時，尾碼的最高位應為“0”。解碼時可據此來判斷DIFF的正負。當然，采用這種截斷Huffman碼的編碼效率會比采用標準Huffman碼的編碼效率稍微差一點。(4-3)表4-4

JPEG基本系統中DC系數的差分值的典型Huffman編碼表

【例4-4】對于靜止圖像的色度編碼，設相鄰兩塊的DC系數的差值DIFF為37或－37,請給出對應的截斷Huffman編碼。

【解】編碼過程如下：當DIFF=37時,根據表4-4可知,37在32～63范圍內，因此色度碼字的前綴碼字為111110，尾碼位數B為6；又根據式(4-3)，可知37對應的6位二進制原碼為100101；因此DIFF=37時對應的截斷Huffman編碼碼字為111110100101。同理可得，當DIFF=－37時，前綴碼字為111110,尾碼位數B為6；37對應的6位二進制反碼為011010；因此DIFF為－37時對應的截斷Huffman編碼碼字為111110011010。解碼時，由前綴碼111110可知尾碼有6位，然后取6比特數據得到100101或011010。若為100101，最高位是1，立即可知DIFF=(100101)2=37；若為011010，最高位是0，可知DIFF=－(011010)2=－(100101)2=－37。4.1.3自適應Huffman編碼

前面介紹的兩種Huffman編碼都屬于靜態編碼，在實際編碼前已根據輸入符號集的概率分布將碼表設計好。但實際應用中，信源符號出現的概率很少能精確預知，這很容易造成編碼器使用的碼表并不能實現最佳匹配，即各碼字長度嚴格按照所對應符號出現概率的大小逆序排列，因此得不到最佳編碼。一個解決辦法是先對信源符號的出現概率進行統計并制定相應的碼表，然后再用這個碼表編碼信源。這需要對信源的數據掃描兩次：第一次統計信源符號出現概率，安排碼字；第二次編碼信源符號，壓縮數據。由于解碼端必須使用與編碼端相同的碼表，因此碼表也必須隨數據一起傳送，這就極大地降低了編碼效率，或者限制了碼表不能太大。這種方法只有在對傳輸速率要求不高且被壓縮數據塊比碼表大得多時才有效。這種方法稱為半自適應編碼，實際應用中很少采用。實用的動態(自適應)Huffman編碼，其主要思想是編碼器和解碼器都從一顆空的Huffman樹開始，隨著符號的讀入和處理而按相同的方式修改碼樹。在處理過程的每步中，解碼器和編碼器都使用相同的碼字，但這些碼字在前后步中可能發生變化。我們稱編碼器和解碼器是以“鎖定”或“鏡像”方式工作，其操作是一一對應。

編碼器從一顆空的Huffman樹開始工作，對任何符號都沒有分配碼字。它把輸入的第一個符號直接輸出，然后把它添加到碼樹中，賦予碼字。當下次再見到這個符號時，就把它的當前碼字輸出，并將它的出現概率加1。由于這樣做修改了各個符號出現的概率，那么就要檢查該碼樹是否還是Huffman樹(即最佳碼字)。如果不是，就重新安排碼字。解碼器鏡像編碼器的相同步驟。當它讀入一個未壓縮符號時，將它添加到樹中，并賦予一個碼字；當它讀入一個壓縮后的碼字后，就利用當前的Huffman樹來確定它屬于哪個符號；然后利用與編碼器相同的方式對Huffman樹進行更新。

還有一個問題就是，解碼器如何知道當前輸入是一個未壓縮符號，還是一個變長碼字。為消除歧義，每個未壓縮符號都用一個特殊的變長出口碼字(escapecode)開頭。一旦解碼器讀入這個特殊的出口碼字，就知道后續符號為第一次出現(這個符號的編碼位數定長，是事先設定好的)。另外，這個特殊的出口碼字不能是已用于各符號的任何變長碼字。既然每次更新碼樹都要修改符號的碼字，那么這個出口碼字也應該修改。一個很自然的解決辦法就是在Huffman樹中加入空枝，其出現概率為0，它能分到一個變長碼字，這即為每個未壓縮符號前的出口碼字。當碼樹更新后，空枝的位置及其碼字都將改變，但是任一時刻，該出口碼字都存在且唯一，解碼器用它來輔助識別未壓縮符號。

4.2游程編碼

游程長度編碼，簡稱游程編碼(Run-LengthCoding,RLC)的基本思想是,將具有相同數值(或字符等)的、連續出現的信源符號構成的符號串用其數值(或字符等)及串的長度表示。以圖像編碼為例，灰度值相同的相鄰像素的連續長度(像素數目)稱為連續的游程，又稱游程長度，簡稱游程。如果給出了形成串的像素的灰度值及串長度，就能無失真地恢復出原來的數據流，如圖4-3所示。圖4-3

RLC編碼示例游程編碼往往與其他編碼方法結合使用。例如，在MPEG視頻編碼中，對圖像塊作完離散余弦變換和量化后，經Z字形掃描將“0”系數組織成“0”游程，作游程編碼，再與非“0”系數結合組成二維事件(RUN，Level)進行Huffman編碼，其中，RUN代表“0”游程的長度，Level代表在該“0”游程后面的非“0”系數的數值。

顯然，平均游程長度越長，游程編碼的效率越高。當平均游程長度很短時，游程編碼的效率非常低。在圖像的游程編碼中，它只適合灰度等級比較少的圖像，例如它特別適合二值圖像。4.2.1二值圖像的游程編碼

二值圖像是指僅有黑和白兩個亮度值的圖像(國際建議規定用“1”代表黑，“0”代表白)。二值圖像的應用非常普遍，如經掃描得到的氣象圖、工程圖、地圖及由文字組成的文件圖像(黑白報紙、書籍等)。二值圖像是灰度圖像的一個特例，它最經典的通信方式是傳真。因此，二值圖像壓縮也往往指對數字傳真機掃描文件的編碼。此外，二值圖像壓縮還大量用于圖文的光盤存儲，而且傳真本身也已經從圖形、文字等二值圖像發展到連續色調圖片的傳輸。在二值圖像的游程編碼中，游程符號集合X={黑，白}，每一掃描行均由交替出現的白像素游程(連續出現的白像素)和黑像素游程(連續出現的黑像素)組成。對不同長度的白游程和黑游程按其出現的概率的不同分別配以不同長度的碼字，就是二值圖像的RLC。由于RLC利用了多個像素間的相關性，故可得到較低的碼率下限，每像素平均碼長滿足：

其中,PW和PB分別為白像素和黑像素出現的概率,lW和lB分別為白游程長和黑游程長的平均像素數(平均長度)，hWB則為每個像素的熵值。(4-4)在理想情況下，先分別統計出圖像白游程長為i的概率PiW和黑游程長為i的概率PiB，然后根據Huffman編碼原則按游程(RL)出現概率分配碼字，即可使平均碼長接近hWB。但在實際應用中，RL在行間、頁間出現的概率都不相同，且為求得該概率，需要存儲數據并做統計計算，難以實時實現。為此，CCITT的T.4建議推薦以8幅標準傳真樣張為統計樣本，統計各種RL出現的概率并以此編出Huffman表，稱之為改進型Huffman編碼(MHC)，作為文件傳真三類機一維編碼的國際標準。實際編碼過程中首先數RL長度、然后查表，可以實現實時編碼。MHC碼的平均編碼效率可達86.9%，差錯靈敏度低，它也基本上適合中文文件傳真的樣張。為保證傳真文件具有足夠的清晰度，CCITT規定ISO的A4幅面(210mm×297mm)為可接受的輸入文件的最小尺寸，對它的掃描分辨率應達到1188(或2376)條掃描線，每條線標準采樣1728點。根據統計，實際RL多在0～63之間，故MHC碼表分為結尾碼和組合基干碼兩種，如表4-5所示。具體編碼規則如下：

①RL=0～63時，用相應的結尾碼編碼；

②RL=64～1728時，用“組合基干碼+結尾碼”編碼。

③行結束時添加行同步碼EOL。

例如RL(黑)=128，編碼為“000011001000(組合基干碼)+0000110111(結尾碼)”。表4-5傳真文件編碼的MH碼表4.2.2

JPEG圖像量化系數的編碼

JPEG(JointPhotographicExpertsGroup)是指由ISO和IEC兩個組織機構聯合組成的專家組，負責制定靜態的數字圖像數據壓縮編碼標準，其制定的標準也稱JPEG標準。在實際的JPEG圖像壓縮編碼標準中，圖像量化系數的熵編碼是結合了游程編碼和Huffman編碼。

JPEG采用8×8的圖像塊，經離散余弦變換后得到64個系數。第1個系數稱為直流系數，后63個系數稱為交流系數，如圖4-4(a)和(b)所示。圖4-4

JPEG圖像系數二維到一維的過程首先，利用Z形掃描將二維系數矩陣轉換成一維系數矩陣，Z掃描過程如圖4-4(b)所示。掃描完成后二維系數矩陣與一維系數數組ZZ(k)的對應關系如圖4-4(c)所示。ZZ(0)為直流系數，對它的編碼方法已經在4.1.2節中進行過介紹。其次，非零交流系數按“NNNN/SSSS+尾碼”的編碼方式編碼，其中4位“NNNN”為當前非零值相對前一個非零交流系數的零游程計數，表示ZRL=0～15；而4位“SSSS”+“尾碼”則用于編碼當前非零值，其含義與直流系數編碼類似，“SSSS”代表尾碼的比特數。但這里將“NNNN/SSSS”組合為一個新的前綴碼，然后用Huffman編碼方法編碼，其碼表如表4-6所示。若ZRL>15，則用“NNNN/SSSS=1111/0000”編碼，再對ZRL=ZRL-16繼續編碼。若最后一個“零游程/非零值”只有零游程，則直接發送塊結束碼字EOB，否則不需要發送EOB。最后，具體的交流系數編碼步驟如下：

①根據ZZ(k)的幅度范圍,由表4-6查出尾碼的位數SSSS=B。表4-6交流系數的尾碼編碼比特數②計數非零交流系數前的零游程值NNNN=ZRL，由NNNN/SSSS從表4-7和表4-8中查出前綴碼字。

③按式(4-3)直接寫出B位尾碼的碼字。

【例4-5】某圖像塊的殘差數據如下所示，PRED=8，JPEG編碼過程如下：

(1)Z形掃描：ZZ(0)=12，ZZ(1)=5，ZZ(2)=-2，ZZ(4)=2，ZZ(8)=1，ZZ(31)=-1。

(2)DC系數編碼：DIFF=ZZ(0)-PRED=12-8=4。由表4-4知，B=3，前綴為100，尾碼DIF=100，故編碼為101100。

(3)AC系數編碼：第1個非零值ZZ(1)與ZZ(0)之間的ZRL=0，故NNNN=0；ZZ(1)=5，故SSSS=3；NNNN/SSSS=0/3。由表4-7知前綴碼字為100，后綴碼字為101，故ZZ(1)的編碼為100101。同理，第2個非零值ZZ(2)的NNNN/SSSS=0/2，故前綴碼字為01，－2的反碼為01，因此編碼為0101。

同理，可得到ZZ(4)的編碼為“11011，10”，ZZ(8)的編碼為“111010，1”。表4-7亮度交流系數碼表表4-8色度交流系數碼表

ZZ(31)=-1：由于NNNN=31－8－1=22>15，故先編碼ZRL=16，碼字為“11111111001”；此后有NNNN=22－16=6，此時的SSSS=1，故NNNN/SSSS=6/1，前綴的編碼為“1111011”，－1的反碼為0，后綴的編碼為0，從而ZZ(31)的編碼為“11111111001+1111011+0”。

此后無非零值，直接用EOB結束本塊數據，編碼為“1010”。

原始碼流需要8×8×8=512bit，壓縮后碼流一共有49bit，壓縮比為512∶49=10.45∶1。

4.3

Golomb編碼與通用變長碼

4.3.1一元碼

一元碼定義為非負整數n的一元碼為n-1個1后跟1個0；或者為n－1個0后跟1個1。

按此定義，整數n的一元碼長度是n比特，如表4-9所示。表4-9整數n的一元碼字4.3.2

Golomb編碼

S.W.Golomb在1966年提出一種編碼方法，可以使服從幾何分布的正整數數據流的平均碼長最短，該方法無需使用Huffman編碼算法，而是直接給出最佳變長碼。

設數據流中整數n出現的概率為

p(n)=(1－p)n－1p,

0≤p≤1(4-5)

求出滿足下式的b值(一定存在)

(1－p)b+(1－p)b+1≤1<(1－p)b－1+(1－p)b

(4-6)

得到b值后，就可以按“前綴碼+尾碼”的格式進行整數n的Golomb編碼。具體步驟如下：

(1)如果b≠2k，前綴碼是q+1位一元碼字，

，為下取整函數；尾碼是對的余數r=n－1－qb的二進制編碼，r∈{0,1,…,b－1}，余數前個用比特編碼，后面用比特編碼，且最高位為1。

(2)如果b=2k，前綴碼產生規則同b≠2k時相同；尾碼則直接用n的二進制表示的最低k位表示。這類特殊的Golomb碼又叫做G(k)。

【例4-6】給出b=3，4，5時的Golomb碼。

【解】如果取b=3，則可能的余數為0、1、2，第1個余數用1比特編碼，后面余數用2比特編碼，高位為1保持尾碼的前綴性，因此余數與尾碼的對應關系為0

0、110、211；而前綴碼根據編碼規則，對于n=1,2,…，其前綴碼的位數分別為1,1,1,2,2,2，…位。若取表4-9右邊一列的一元碼字，則分別為1,1,1,01,01,01，…。表4-10

b=3,4,5和n≤10的Golomb碼字4.3.3指數Golomb碼與通用變長碼

相同前綴的Golomb碼的信息表達能力主要在于尾碼。可是從表4-10可見，其尾碼長度隨n增長緩慢，因為它主要取決于b。而所謂指數Golomb碼，可以讓同一個前綴下的Golomb碼字數呈指數級增長。本質上，指數Golomb碼就是以G(0)碼為前綴，再加上q+m位尾碼(或稱后綴)，尾碼事實上就q+m位二進制碼。q就是G(0)碼中“0”的個數(均取“0…01”形式的一元碼)，而m≥0則為指數Golomb的階數。此時，尾碼增加1位，即m增加1，碼字數就可以翻一番。指數Golomb碼已經應用在視頻編碼中，如在我國制定的AVS(先進音視頻編碼系統)標準中，就已經采用m階指數Golomb碼，如表4-11所示。指數Golomb碼的優勢在于硬件復雜度較低，可以根據閉合公式解析碼字，無需查表；還可以根據整數n的分布靈活選取或自適應改變階數m，以達到較好的壓縮性能。對于指數哥倫布編碼，當m和q確定后，其編碼正整數n的范圍為［2q+m－2m,2q+m+1－2m－1］。表4-11

m階指數Golomb碼表由于0階指數Golomb碼的前綴碼始終比其尾碼多1位，如表4-11階數為0時所示，因此可以把q位尾碼嵌入到q+1位前綴碼中。這就是ITUH.26L(H.264建議前身)甚低碼率視頻壓縮算法采用的通用變長碼(UVLC)，如表4-12所示。可以看到，UVLC實質上就是一種前后綴交織的0階指數Golomb碼。

UVLC碼的優點在于：同等碼長的UVLC碼它不僅“異字頭”，也是“異字尾”。因此，只要碼長已知，如果正向譯碼出錯，還可以反向譯碼。這樣降低了碼字的誤碼敏感性。表4-12

UVLC碼的結構

【例4-7】設有一信源的消息符號集為0，±1，±2，±3，±4，±5，其出現概率對稱且單調下降，如圖4-5所示。假設正負符號合在一起出現的概率為0.38，0.32，0.16，0.08，0.04，0.02。求此信息源的UVLC碼和Huffman碼。圖4-5對稱單調下降概率分布

【解】可以按照表4-12把這種符號映射到表4-13所示的UVLC碼。表4-13此信源的UVLC碼該信源也可以采用Huffman編碼，碼表如4-14所示。表4-14此信源的Huffman碼按照符號的出現概率計算出這種信源熵值為

采用UVLC編碼的平均碼字長度為

1×0.38+3×0.32+5×(0.16+0.08)+7×(0.04+0.02)=2.96bit

采用Huffman編碼的平均碼字長度為

1×0.38+3×0.32+4×0.16+5×0.08+5×0.02+6×0.02+7×0.02=2.74bit

計算出平均碼長為2.84bit。比較起來，Huffman碼平均碼長更接近于信源熵值，UVLC碼比Huffman碼稍差，但UVLC碼的編解碼的復雜度比Huffman碼低很多，實現更容易，因此在最新的視頻編碼標準H.264中，UVLC碼也是熵編碼的選擇方案之一。 4.4算術編碼

4.4.1算術編碼的起源

為了理解算術編碼方法，首先介紹香農編碼，因為算術編碼是沿著他們的思路發展的。

早在1948年，香農就提出將信源符號依其概率降序排序，用符號序列累計概率的二進制表示作為對信源的編碼，并從理論上證明了它的優越性。香農編碼方法歸結如下：

①設信源符號集共有L個符號，按符號出現概率大小進行排列，則

P(x1)≥P(x2)≥…≥P(xL)②計算概率的累計分布

③每一符號編碼的碼字長ni，它是符合以下不等式的最小整數。(4-8)(4-7)④編碼的方法：把Ci展開為二進小數，按照式(4-8)取ni位，當第ni+1位是1則進位，當第ni+1位是0則舍去，這個ni位二進碼就是符號xi的編碼。

按上面討論， 并趨近于1，則編碼碼字平均長度大于并趨近于信源的熵值。并且按上述方法編碼時，一個新的分配長度為ni比特的碼字是前一個累計分布再加上一個符號概率值成為新的分布值的二進小數表示值，由于上一個符號的概率值在未增長的碼位上必定有值，因此把它的數值加上去，未增長的碼位數字必然和前一個碼字不相同，所以按這個方法編碼的碼字符合前綴條件。

【例4-8】已知四個符號的信源{x1，x2，x3，x4};p(x1)=0.4，p(x2)=0.3，p(x3)=0.2，p(x4)=0.1。試計算該信源的香農碼。

【解】根據香農碼的計算步驟，可算得C1=0，C2=0.4，C3=0.7，C4=0.9，按前綴條件確定n1=2，n2=2，n3=3，n4=4。編成的香農碼為c1=00，c2=10，c3=110，c4=1111。

前述的Huffmen編碼比香農編碼更接近于熵值，故現在一般都采用Huffman碼。香農編碼是對符號集的單個符號編碼，Elias把香農編碼方法概念推廣到對符號序列的直接編碼，Rissanen將其推廣成為信源統計性質未知的普適信源，下節我們將介紹這種方法。4.4.2算術編碼的基本原理

設信源在第i時刻發出的符號為xi，把信源從開始到第n時刻發出的符號序列記為Sn，則

對于Markov信源，可以用條件概率p(x|S)來描述信源輸出一個新的符號的概率，符號序列Sn的發生概率為

p(Sn)=P(x1)P(x2︱x1)…P(xn︱x1…xn－1)(4-10)

在第n時刻，符號序列Sn由n個符號構成，由可能的各種符號序列構成概率之和，它滿足：(4-9)(4-11)例如，圖4-6中給出了二元符號集合{0，1}在最初時刻生長出的符號序列S1，S2，S3，及其可能構成的概率，假設序列中符號的出現概率是獨立無關的，設p(0)＜p(1)，p(0)=1/3，p(1)=2/3。S1就只有一個符號為1或0，其概率為p(1)或p(0)，把長度為1的間隔按1∶2的比例分割，就是序列S1的各種構成的概率。S2有4種構成為11，10，01，00，其中,11，10是由S1為1時發展而成，在符號出現概率獨立無關假定下p(xn|sn－1)=p(xn)，所以p(11)=p(1)p(1)，p(10)=p(1)p(0)。只要把S1分割為1的那一段p(1)再按1∶2的比例分割，就得到S2為11和10時的概率p(11)和p(10)。同樣把S1為0的一段P(0)再按1∶2的比例分割，就得到S2為01和00時的概率p(01)和p(00)，顯然p(11)+p(10)+p(01)+p(00)=1，符合式(4-11)，用此方法可以一步一步遞推出n個符號序列Sn的各種可能構成的概率p(Sn)。圖4-6符號序列Sn出現的概率和算術編碼編碼并不按單個符號編碼，而按符號序列的發展對序列進行整體編碼。借鑒香農用n個符號序列Sn出現的概率的累計分布C(Sn)，在區間［C(Sn)，C(Sn)+A(Sn))選取一點，用其二進制小數表示編碼，并把C(Sn)和A(Sn)的計算轉換成遞歸運算。A(Sn)稱為符號序列Sn編碼可用空間或值域(Range)，它的大小就是p(Sn)，即符號序列Sn的出現概率。

設在上一時刻信息的符號序列為S，這一時刻信源發出符號x，序列發展成為新的序列Sx。遞歸計算序列Sx的累計分布函數C(Sx)和編碼可用空間A(Sx)的遞推公式如下：

(1)累計分布函數的遞推：

C(Sx)=C(S)+A(S)P(x)(4-12)圖4-6中，如果x=1，有

如果x=0，有

C(S0)=C(S)+P(0)A(S)=C(S)

(2)編碼可用空間的遞推：

A(Sx)=p(Sx)=p(x)A(S)(4-13)

圖4-6中，如果x=1，有如果x=0，有

式(4-13)中，p(x)為符號出現的概率，P(x)為符號x的累積概率，如式(4-7)所示。對于圖4-6，有

初始條件為C(φ)=0，A(φ)=1和P(φ)=0，p(φ)=1。可見，算術編碼在傳輸任何符號x之前，信息的完整范圍是［C(φ)，C(φ)+A(φ))=［0，1)。當處理符號x后區間寬度就依據x的出現概率p(x)變窄，大概率符號比小概率符號使區間變窄的范圍要小。然后在區間［C(S)，C(S)+A(S))找一代表點，對其值進行編碼。符號序列越長，相應的子區間就越窄，編碼表示該子區間所需的比特數也就越多。另外從上述迭代公式可知，符號串每一步新擴展的碼字C(Sx)都是由原符號串的碼字C(S)和新區間寬度A(Sx)的算術相加而得的，“算術碼”一詞由此得來。對于計算信源符號序列的累積計分布函數，還可以從樹圖的角度來考慮。假設二元符號序列串S={s1，s2，…，sn}，另一個二元序列串為Y={y1，y2，…，yn}。若兩個序列串中對某第一個i有si=1、yi=0，則認為S>Y。也就是說，把這個符號序列串看成二進制小數0.S和0.Y，當某一個si>yi，則二進制小數0.S>0.Y，也即對應S>Y。我們把二元符號序列排成一棵n階(n為序列串的長度)二元整樹，如圖4-7所示，可以看到，所有小于S的序列都在同一階S節點的左側。因此，根據累計分布函數的遞歸定義，信源符號序列S的累計分布函數：

例如，若輸入序列S=0111，由式(4-14)可知

圖4-7中所圈出的樹枝正好是式(4-15)中的項。(4-15)(4-14)圖4-7算術編碼輸入符號序列對應的樹另外，此序列S=0111按式(4-12)計算出的累計分布函數為

由上式可見，它的結果與式(4-15)所得的結果一致。因此,式(4-14)提供了一種簡單明了的計算累計分布函數的方法。

【例4-9】信源符號集S={a，b，c，d，e，!}，其中前5個符號為實際信源符號，最后一個符號“！”用來表示編碼結束。各概率和初始區間范圍如表4-15所示，試編碼字符串dead。表4-15信源符號及其概率分布

【解】編碼過程如下：

“d”，C(Sd)=C(φ)+P(d)A(φ)=0.4

A(Sd)=p(d)A(φ)=0.3區間［0.4，0.7)

“e”，C(Se)=C(S)+P(e)A(S)=0.4+0.7×0.3=0.61

A(Se)=p(e)A(S)=0.2×0.3=0.06區間［0.61，0.67)

“a”，C(Sa)=C(S)+P(a)A(S)=0.61

A(Sa)=p(a)A(S)=0.2×0.06=0.012區間［0.61，0.622)

“d”，C(Sd)=C(S)+P(d)A(S)=0.61+0.4×0.012=0.6148

A(Sd)=p(d)A(S)=0.3×0.012=0.0036區間［0.6148，0.6184)編碼符號“!”后的區間為［0.61804，0.6184)，區間寬度A(S)=0.00036。

解碼器無需知道最終區間的兩個端點值，只知道區間內的一個值就夠了。比如知道值0.6182，解碼端的過程如下：

由于0.6182∈［0.4，0.7)，故知道第1個符號為d；

則下一個符號的區間范圍應該為：a

［0.4，0.46)，b

［0.46，0.49)，c

［0.49，0.52)，d

［0.52，0.61)，e

［0.61，0.67)，!［0.67，0.7)。由于0.6182∈［0.61，0.67)，故知道第2個符號為e；

以此類推，可以解碼出符號a，d，！。當解碼出！符號時，解碼完成。4.4.3算術編碼的碼字計算與編碼效率

根據式(4-12)和式(4-13)可以計算出符號序列S對應不同的區間為［C(S)，C(S)+A(S))，那么如何在此區間內選取一點來代表此區間呢？該過程如下：

將符號序列的累計分布函數寫成二進制位的小數，取小數點后l位，若后面有尾數，就進位到第l位，這樣得到一個數C，并使l滿足：

則C=0.z1z2…zl，zi取0或1，得到符號序列S的碼字為z1z2…zl。例如：C(S)=0.101101000，A(S)=0.12，則l=4，可得到C=0.1100，S的碼字為1100。(4-16)這樣選取的數值C，一般由于l位后面有尾數，需要進位，從而滿足下面關系式：

當l位后面全為0時，此時C=C(S)。而由式(4-16)可知，A(S)≥2－l。將式(4-17)都加上C(S)，得

可見，數值C在區間［C(S)，C(S)+A(S))內，而信源符號序列對應的不同區間是不重疊的，所以編碼是即時碼。(4-17)(4-18)由于信源符號序列S的碼長滿足式(4-18)，而A(S)就是信源序列的出現概率p(S)，因此可以得到：

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

若信源是無記憶的，則H(Sn)=nH(S)，得(4-19)(4-20)(4-21)4.4.4二元算術編碼的實現

對于未知統計的非平穩二元信源，P(1)和P(0)是未知的，而且是變化中的，但是根據信源的馬爾可夫特性，用一段信息統計出的1和0出現的頻度f(1)和f(0)來分別替代P(1)和P(0)。例如，對于二值圖像，可用當前像素周圍的鄰近像素x1，x2，x3，x4小區域進行統計，或者用前一像素x1統計1和0出現的頻度f(1)和f(0)替代1和0出現的概率P(1)和P(0)，如圖4-8所示。Rissanen把這種區域范圍稱為模型的定義結構，采用了某一種定義結構，就可以統計得到1和0出現的頻度f(1)和f(0)。圖4-8模型的定義結構下面以圖4-8(b)結構統計像素x1的1和0出現的頻度f(1)和f(0)，在此把得到的頻度f(1)和f(0)分別作為x0出現1和0的概率。在下面討論中，假定1出現的概率低于0出現的概率(如果1的出現概率高于0的出現概率，對下式作相應更改即可)，設置“1”計數器n(1|z)，其初始值設置于3。若x1中出現“1”時，n(1|z)增加1。另一計數器是“0”計數器n(0|z)，初始值置于2k(s)+1。若x1中出現“0”時，n(0|z)增加1。每當n(1|z)中計數達到6時，把n(1|z)和n(0|z)中計數除2，以及把k(s)減少1，并且如果n(0|z)計數達到2k(s)+2－1時，使k(s)增加1。因此每當出現3個“1”時，n(1|z)恢復到初始置定數3，而n(0|z)從原來的初始置定數2k(s)+1除2成為2k(s)，如果這時不出現“1”而相繼出現許多個“0”，使n(0|z)計數器的計數達到2k(s)+2－1，亦即出現了2k(s)+2－1－2k(s)=3×2k(s)－1個“0”時，n(0|z)計數器恢復到原來的初始置定數2k(s)+1。k(s)會在兩個連續整數之間擺動，則“1”和“0”數目動態平衡時，它們出現的頻數之比近似為3∶3×2k(s)－1≈1∶2k(s)－1。我們就以2－k(s)作為p(1)的近似值。當信源非平穩時，所得到的頻數f(1)和f(0)能隨著p(1)和p(0)的變動而及時更新。Rissenan把k(s)稱做不對稱數(SkewNumber)。使用不對稱數，可把式(4-13)概率的遞推計算化成：(4-22)編碼時，用式(4-10)和式(4-12)遞推計算累計分布值C(Sn)和序列概率P(Sn)，并按P(Sn)的位數確定C(Sn)的位數作為編碼。于是，就把香農編碼發展成為對符號序列的直接編碼，并且這種編碼無需知道信源的統計，因此它也是一種普適編碼。我們再來分析這種方法的編碼效率。信源每發出一個符號，序列就增加一個符號，如把2－k(s)看成是p(1)的估值，根據式(4-13)增加一個符號“1”時，p(S1)為p(S)乘上2－k(s)，亦即以二進制小數表示p(S)增加了k(s)位，編成的碼C(S)按式(4-12)是以p(S1)來確定位數的，所以也增加了k(s)位。因此信源發出“1”時，編成的碼位數增長的期望值為－2－k(s)lb2－k(s)，則碼位數增長是符號“1”在熵值中的貢獻－p(1)lbp(1)的估值。同樣當信源發出“0”時，根據式(4-13),p(S0)=p(s)(1－2－k(s))，編成碼位數增長為－lb(1－2－k(s))。現在，“0”出現的概率為1－2－k(s)，位數的增長期望值為(1－2－k(s))lb(1－2－k(s))，它相當于“0”在信源熵值中的貢獻的估值。因此，隨著信息序列增長，這個方法編碼的碼率趨于信源的熵值。根據式(4-12)和式(4-13)進行遞推的編碼運算，成為只有加、減和乘法的運算，又因為采用不對稱數k(s)的冪近似來表示概率，乘法運算化成了移位操作，因此這種方法在實現中的復雜度大大簡化。

現在介紹具體的編解碼方法。假設p(1)＜p(0)，以及p(1)+p(0)=1，所以p(1)＜1/2。此時,符號排序時1在前0在后，因此累計分布P(1)=0，P(0)=p(1)。計算新的編碼可用空間A(S)值越來越小，可用浮點數表示A(S)，E(S)為其指數，例如A(S)=0.001011，可表示為1.011×2－3，則E(S)=3，E(S)用來控制A(S)的移位，使數據規范化。計算時，式(4-13)還可以作近似，規范化的A(S)用1.000×2－E(S)來代替，則A(S)的遞歸新值計算式成為

為了書寫方便，這里，2－(E(S)+k(S))=W(S1)，表示碼序列S隨后出現1的近似概率。編碼過程可歸結為以下遞歸過程。

初始化：A(S)=1.0，C(S)=0.0，E(S)=0。進入第(1)步。

第(1)步：按給定不對稱值k(S)，根據出現符號按式(4-24)分割編碼可用空間，計算A(S)，(4-24)(4-23)進入第(2)步。

第(2)步：按式(4-12)計算碼字C(S)，

進入第(3)步。

第(3)步：更新E(S)值,如果出現碼符x=0，則(4-26)(4-25)如果出現碼符x=1，則

回到第(1)步，或編碼終結。

【例4-10】符號信源給出碼序列0，0，1，0，在各碼位上假定k(S)的數值為3，1，1，1，給出上述編碼過程的結果。

【解】按上述編碼過程可得到表4-16所示的編碼結果。(4-27)表4-16例4-10的編碼過程從表中可見，隨著碼序列的增長，A(S)越來越小，C(S)作為小數位數也越來越長，但始終不超過1。另外也可以看到,C(Sx)在［C(S)，C(S)+A(S))區間發展，也就是隨著碼符數n的增長，算術編碼的碼字值不會超過C(Sn)+A(Sn)，但位數會越來越長。如果用定點計算需要無窮位數的運算器，用浮點運算就可以用有限位數的處理器如普通的16或32位運算器計算。在C(S)運算器之前加一個先進先出(FIFO)的寄存器Q，用“Q,C”來表示，Q和C之間的“,”表示運算時C的高位數可以通過移位移到Q中。FIFO寄存器Q的輸出就是算術編碼的碼字輸出。作浮點運算時，所得到E(S)值就會把A(S)和C(S)移位成為規范化的表示數。A(S)的規范化很簡單，把A(S)左移E(S)值位數即可。當A(S)移位時，在“Q,C”中左移相同位數即可，這時C(S)的高位就移了相應的位數到Q中，這個移位就稱為規范化。現在不必計算E(S)值，主要修改上面編碼過程的第(3)步改成下面的第(3′)步，把計算E(S)的增加值改成為對A(S)和C(S)移位即可,用SL(m)表示左移m位。而編碼過程的初始化不變，第(1)、(2)步的W(S1)按p(S1)算。編碼過程修改如下：

初始化：A(S)=1.0，C(S)=0.0，E(S)=0。進入第(1′)步。第(1′)步：按給定不對稱值k(S)，根據出現符號按以下方式分割編碼可用空間，計算A(S)，則

進入第(2′)步。

第(2′)步：按式(4-12)計算碼字C(S)，則

進入第(3′)步。(4-29)(4-28)第(3′)步：規范化，

如果出現碼符x=0，當A(S)＜1.0，則A(S)和C(S)都SL(1),

如果出現碼符x=1，則C(S)左移SL(k(S))，A(S)=1.0回到第(1′)步，或編碼終結。

例4-10的編碼運算可改為表4-17所示。表4-17例4-10的規范化編碼過程

【例4-11】把按照上例編好的碼進行譯碼。

【解】譯碼過程是編碼過程的逆運算。設碼符序列為SxiSb，S為已譯的碼序列。根據所譯出碼按照編碼過程同樣方法生成C(S)和A(S)，碼字C放在CBUF運算器進行與編碼時相反的操作。我們先看編碼過程的第(2′)步，由式(4-28)可見，如果xi=1，C(S1)=C(S)，碼字C在編碼可用空間［C(S),C(S)+p(S1))內。如果S后接的xi是0，碼字C≥C(S0)≥C(S)+p(S1)，根據式(4-28),有p(S1)=2－k(S)，所以先在CBUF運算器做一個差值CBUF=C－p(S1)=C－2－k(S)。如果差值為正，判定xi是0，該CBUF值保留即為剩余的碼字C，為譯后續序列Sb用；如果差值為負，判定xi是1，該CBUF值不用，恢復前一個碼字C，為譯后續序列Sb用。因此，可把譯碼過程歸結為以下四步：

初始化：A(S)=0，C(S)=輸入碼字C，進入第(1″)步。

第(1″)步：給定不對稱值k(S)，如果

CBUF=C－2－k(S)≥0，判定碼符x為0

CBUF=C－2－k(S)＜0，判定碼符x為1，恢復CBUF=C

進入第(2″)步。

第(2″)步：根據所判定碼符，計算編碼可用空間A(S)新值(4-30)進入第(3″)步。

第(3″)步：規范化，

如果碼符x=0，當A(S)＜1.0,則A(S)和C(S)和SL(1)，

如果碼符x=1，則C(S)進行SL(k(S))，A(S)=1.0

最后，回到第(1″)步，或譯碼終結。計算中對于碼字C要考慮由于前面所述的結轉運算的進位，根據限額數v，如果發現有v個1相連，就要考察這個比特；如果這個比特是0，可以丟棄它，因為它是多余的填充比特；如果這個比特是1，知道是從后面進位到這里的，不再往前進行。因此就在接收端補行進位，把前v個1改成0，而把其前一位0改為1。根據上面譯碼算法，例4-10的譯碼過程如表4-18所示。表4-18例4-10的譯碼過程 4.5字典碼

4.5.1

LZ碼的基本概念

字典編碼起源于20世紀70年代末。1977年和1978年,以色列兩位博士J.Ziv和A.Lempel陸續提出了兩種不同但又有聯系的關于文字數據壓縮的論文，該文中的碼習慣上簡稱為LZ碼［21］。這兩篇論文算法在后來的文獻里分別被稱做LZ77及LZ78，奠定了其后文字數據壓縮研究的基礎。其中，LZ78算法的精神類似于上述字典編碼法的觀念。1984年，T.A.Welch博士對LZ78算法加以改進，提出了所謂的LZW算法。至今，在處理文字數據壓縮的問題時，LZW算法一直是被廣泛使用。設想我們要用計算機來儲存以下一段9個字符的文字數據，即ABBBABAAB。如果每個字符都用8比特的ASCII碼來儲存，則需要72比特的內存。然而，如果該計算機擁有一個如表4-19中所示的字典1，借助該字典的信息，則僅需10比特的內存，亦即AB、BB、AB、A及AB等文字數據分別會先被編碼成10、11、10、00及10等十個比特，然后再存入內存，其省下的儲存空間高達86%。之后，如果一次以兩個比特的方式來讀取數據，然后通過同樣的字典進行譯碼，則內存所儲存的數據1011100010很快地就會被解讀出原來的文字數據為ABBBABAAB。表4-19計算機字典通過上面的例子可以看到，與Huffman碼正好形成鮮明對比的是：LZ碼及后來的改進算法都是將變長的輸入符號串映射成定長(或長度可預測)的碼字。LZ碼按照幾乎相等的出現概率編排輸入符號串，從而使頻繁出現的符號的串將比不常出現符號的串包含更多的符號。例如在一張將英文字母和符號串編碼成12位碼字的壓縮字符串表中(如表4-20所示)，不常用的字母如Z，獨占一個12位碼字；而常用的符號如空格(表4-20中用“空”表示)和零，則以不同長度的長串表示(實用中字符串長度可大于30)。如果輸入一個長串，就會被替換成一個12位碼字，此時壓縮比自然很高。實際上，表4-20也就是LZ碼使用的字典，所以LZ碼也是基于字典的壓縮編碼算法。表4-20一種LZ編碼的字典4.5.2

LZW算法

由T.A.Welch在1984年提出的LZW算法，是LZ系列碼中應用最廣、變形最多的LZ碼。它的標識只有一項，即指向字典的指針。LZ碼系列算法的共同點是：分解輸入流，使其成為長度各異的“短語”，并把它們存入“短語字典”，并給每個“短語”賦予一個碼字(通常就是短語的字典索引)。只要短語的碼字長度小于短語的長度，就達到了壓縮的目的。LZW編碼算法獨特的地方是先建立初始字典，再將輸入流分解為短語詞條，這個短語若不在初始字典內，就將其存入字典，這些新詞條和初始字典共同構成編碼器的字典。初始字典由信源符號集構成，每個符號是一個詞條。比如在英文文本的壓縮中，可以將擴展的ASCII碼作為初始字典，使其成為字典的前256項，這樣的初始字典足以應付普通的英文文本壓縮。

LZW算法將輸入字符串映射成定長(通常為12位)的碼字。LZW碼表(字典)具有所謂的“前綴性”——表中任何一個字符串的前綴字符串也在表中。這也就是說，如果由某個字符串S和某個單字符c所組成的字符串Sc在表中，則S也在表中，其中c叫前綴串S的擴展字符。

對碼表作出這樣的說明后，編碼前可以將其初始化以包含所有的單字符。在壓縮過程中，碼表里面存放著編碼器在壓縮過程中已經遇到的字符串，它動態反映消息的統計特性。LZW使用的是“貪婪”分析算法，即依次檢查各個字符，直到碰到碼表中沒有的字符串或者掃描完全部字符。除初始化碼表外，其他碼表項也是通過這種方法加入進碼表中的。LZW編碼算法流程如圖4-9所示。圖4-9

LZW編碼算法流程

【例4-12】試對一個最簡單的2字符串“ABBBABAAB”作LZW編碼。

【解】根據圖4-9給出的LZW編碼算法流程，可以得到如下的編碼步驟：

步驟0：將A及B字符存入字典里，也就是A及B字符之后分別會被編碼成索引值1及2；并讀入第一字符A，前綴串S