3.10 熵編碼

3.10.1 熵編碼的基本概念

在前面幾節中我們分別討論了預測編碼和各種變換編碼，這些編碼都可以看成是通過解除空間或時間上的相關性，將原始信號轉換成另一種形式（預測誤差或變換系數）來表達。在這種新形式下，信源可以近似認為是無記憶的，即各樣值之間已沒有相關性，再經過量化后信源只產生有限個數的符號，因此可近似看成是一個離散無記憶信源（見圖3-42）。根據3.2.2節的論述可知，對于離散無記憶信源只要各事件出現的概率不相等，該信源就仍然有冗余存在，還有進一步進行數據壓縮的可能性，這就是在熵編碼中所考慮的問題。

如前所述，在預測編碼、變換編碼、子帶編碼或小波變換之后，將預測誤差、變換系數或子帶信號量化，將造成少量信息的丟失。存在信息丟失的編碼方法稱為有損編碼。本節介紹的熵編碼不引起信息損失。無信息損失的編碼方法稱為無損編碼。

我們以下式所表示的一個具有4個電平（即4個符號）的離散信源為例來進行討論。

該信源中4個符號出現的概率是比特/符號。如果用表3-1第三行所示的2位的二進制數碼來代表這4種電平，例如用10來表示電平s3，這一過程叫編碼，10稱為碼字，如表3-1所示的符號與碼字一一對應關系的集合稱為碼表或碼本。

表3-1 一個4符號信源的碼表

在第一種編碼方式中（表中第三行），每個符號所給予的碼字長度都相同，平均碼長N＝2比特/符號，N大于熵（1.75比特/符號）。也可以改換成另一種編碼方式，如表3-1中第四行所示。在這種編碼方式中各符號所對應的碼有不同的長度，稱為變長編碼VLC（VariableLengthCod-ing）。設符號si所對應的碼的字長為n（si）比特，則平均碼長為

將第二種編碼方式中各個符號的碼字長及其對應的概率代入（3-150）式，對于本例而言，N＝1.75比特/符號，正好等于信源的熵。顯然第二種編碼方式比第一種具有更低的數據率，并且已達到了基本極限。這意味著，按照香農信息論，不可能再找到任何其他的無失真編碼方式，其平均字長比這種編碼方式更短。

當用二進符號表示輸出碼字時，相當于從一個新符號集A＝｛0，1｝中，選取符號ai（i＝1，2）來代表原信源所輸出的序列。為了達到數據壓縮的目的，應使新符號集A的概率模型盡可能接近于等概率分布。也就是說，使信源A的熵最大，每個符號ai平均攜帶的信息量最多，從而表達原信源輸出所需要的符號ai數目最少。這從下面的例子中可以得到證實。當采用表3-1中的第2種編碼方式時，原輸出序列與編碼后的序列有如下關系：

可以看出，用方式Ⅱ編碼后的序列中0和1出現的重復頻率相同，因此這種編碼方式能夠給出較低的數據率。在（3-151）式中，編碼方式Ⅱ只用14個符號，而編碼方式Ⅰ需用16個符號表示同一個原始信源序列。

如果編碼符號集A中符號的個數為M，經編碼以后可能達到的最大熵值則為log2M。若原信源的熵為H（X），經編碼后的平均碼長為，編碼符號集中一個符號所攜帶的平均信息量則為H（A）＝H（X）/。顯然

我們將編碼效率η定義為

當η＝1時，有

這就是在編碼中可能達到的最小平均碼長的極限。當M取2時，例如A＝｛0，1｝，最小平均碼長則等于原信源的熵。熵編碼的宗旨在于找到信源符號集內的符號與碼字的一一對應關系，以使平均碼長達到上述極限。不難看出，這種編碼方式是無失真的。

實際應用中的熵編碼方式主要有霍夫曼編碼和算術編碼兩種，下面分別進行介紹。

3.10.2 霍夫曼編碼

霍夫曼（Huffman）編碼的基本思想是，對出現概率較大的符號si取較短的碼長，而對概率較小的符號則取較長的碼長，因此它是一種變長碼?；舴蚵a通常被稱為最優碼。最優的含義是，對于給定的符號集和概率模型，找不到任何其他整數碼比霍夫曼碼有更短的平均字長。所謂整數碼是指每個符號所對應的碼字的位數都是整數。

現在通過M＝2的例子來介紹霍夫曼碼的編碼過程。設原信源為

其編碼的具體步驟如下。

（1）合并：將信源中最小概率的兩個事件合并成一個事件。由于這些事件是統計獨立的，合并后的事件出現的概率等于原來兩個事件的概率和。

（2）置換：將合并后的信源的事件重新按概率大小排列（概率相等的事件可按任意順序排列）。

（3）若合并后的信源中事件的個數大于2，重復執行步驟（1）和（2）；若合并信源中事件個數等于2，則進行步驟（4）。

（4）賦值：在最后得到的信源

中，給x（m－2）1和x（m－2）2分別賦值0（或1）和1（或0）。

（5）反推：由于x2（m－2）（或x1（m－2））一定是由兩個事件構成的，因此，對應于這兩個事件的碼字由x2（m－2）的碼字分別加上0和1構成。以此類推，一直到返回原信源符號為止。

現在利用圖3-43來說明上述編碼過程。假設構成信源的符號以及它們各自出現的概率為

圖3-43中從左到右用虛線標出的4個部分表示4個合并與置換的步驟。在第1步中，概率最小的s4和s5合并，其合成事件的概率為13/60。由于1/5＜13/60＜1/4，因此合成事件在第2步中排在s2和s3之間。以此類推，在第4步中，只剩下了兩個事件，合并過程結束。然后給每一個節點（圖中〇點處）的兩個分支分別賦以0和1。如圖所示的樹狀結構稱為碼樹。從樹根（圖中用箭頭指出的節點）到左端樹梢的各個分支所經過的碼串接起來就構成該樹梢上符號所對應的碼字。例如，從樹根經過兩個節點到s3所構成的碼為11。

由于一個節點的上下兩個分支既可賦值0（或1），也可賦值1（或0值），而且對概率相同的兩個事件的排列順序也是任意的，因此對同一信源所構成的霍夫曼碼并不是唯一的，但是它們的平均字長卻是一樣的。

這樣構造的霍夫曼碼是無歧義的。所謂無歧義是指在譯碼過程中，對某個碼字的解釋是唯一的。現在舉一個例子來說明。對于表3-1所給出的信源概率模型，讀者根據霍夫曼碼的構碼過程，可以證明表中給出的第二種碼即為霍夫曼碼。假設該信源輸出序列和編碼后的序列如（3-151）式所示，當接收端收到碼流01001101000111…時，按照碼表，以0開頭的碼字只有0，因此解出第一個符號為s1；除去已解的碼0以后，碼流則剩下1001101000111，碼表中以一個1開頭的碼只有10，因此得到第二個符號s2；除掉10之后，碼流剩下01101000111，第一個碼0決定了譯碼結果只能是s1；在剩余碼流1101000111中，開頭的兩個碼為11，而碼表中2比特的碼字只有10，因此可以斷定應該按3位來譯碼，得到s3；以此類推。

由以上譯碼過程可以看出，雖然霍夫曼碼是變長的，碼流中又沒有分隔碼字的標識符，但由于它獨特的前綴（Prefix）特性，即短碼字永遠不會成為長碼字的開頭，因此，完全能夠從碼流直接恢復原信源所輸出的符號序列來。

值得注意的是：①由于霍夫曼構碼過程的最基本依據是信源的概率分布，如果信源的實際概率模型與構碼時所假設的概率模型有差異，實際的平均碼長將大于預期值，編碼效率下降。如果差異很大，則有可能比使用定長碼（如表3-1中的第一種編碼方式）的平均字長還要長。對于這種情況，解決的辦法是更換碼表，使之與實際概率模型相匹配；或者直接使用定長碼。②霍夫曼碼對傳輸錯誤十分敏感，如果碼流中出現1比特錯誤，不僅對應的碼字會譯錯，而且由于前綴特性被破壞，可能使后續的譯碼在錯誤的碼字邊界上進行，從而使錯誤傳播下去。

3.10.3 算術編碼

算術編碼是另一種能夠趨近于熵極限的最佳編碼方式，它與霍夫曼編碼一樣，也是對出現概率較大的符號采用短碼，對概率較小的符號采用長碼。但是它的編碼原理卻與霍夫曼編碼很不相同，也不局限于非使用整數碼不可，這使得它比霍夫曼碼有更高的效率。

1.算術編碼的基本原理

假設一個具有4個電平的信源，其概率模型如表3-2所示。把各符號出現的概率表示在如圖3-44（a）所示的單位概率區間之中，區間的寬度代表概率值的大小。由圖可以看出，各符號所對應的子區間的邊界值，實際上是從左到右各符號的累積概率。在算術編碼中通常采用二進制的分數來表示概率，表3-2和圖3-44（a）中都標出了相應的二進概率數值。每個符號所對應的概率區間都是半開區間，即該區間包括左端點，而不包括右端點，如s1對應[0，0.001），s2對應[0.001，0.011），等等。

表3-2 一個4符號信源的概率模型

現在以符號序列s3s3s2s4…為例來解釋編碼過程。算術編碼所產生的碼字實際上是一個二進制分數值的指針，該指針指向所編的符號對應的概率區間。按照這一法則，序列的第一個符號為s3，我們用指向圖3-44（a）中第三個子區間的指針來代表這個符號。從原理上來講，指針指向[0.011，0.111）區間內的任何部位都可代表s3，但通常約定為指向它的左端點，由此得到碼字0.011。后續的編碼將在前面編碼指向的子區間內進行。將[0.011，0.111）區間再按符號的概率值劃分成4份，如圖3-44（b）所示。對第二個符號s3，指針指向0.1001（s3區間的左端），也就是碼字串變為0.1001。然后如圖（b）所示，s3所對應的子區間又被劃分為4份，開始對第三個符號進行編碼。余下的步驟以此類推。

總結上述劃分子區間的遞歸過程，可將算術編碼的基本法則歸納如下：

（1）初始狀態

　　　編碼點（指針所指處）C＝0

　　　區間寬度A＝1.0

（2）新編碼點C＝原編碼點C＋原區間A×Pi（3-158）

　　　新區間A＝原區間A×pi（3-159）

其中pi和Pi分別為所編符號si對應的概率和累積概率。

根據上述法則，對序列s3s3s2s4…進行編碼的過程如下。

第一個符號（s3）：

第二個符號（s3）：

第三個符號（s2）：

第四個符號（s4）：

該碼字串0.1010011用7b表示了4個符號，平均碼長為7/4＝1.75b/符號。

在解碼器中，當收到碼字串0.1010011時，由于這個碼字串指向子區間[0.011，0.111）[見圖3-44（a）]，因此，解出的第一個符號應為s3。然后，采取與編碼過程相反的步驟，即從碼字串中減去已解符號子區間的左端點的數值（累積概率），并將差值除以該子區間的寬度（概率值），則得到新碼字串（0.1010011－0.011）÷（0.1）＝0.100011。由圖3-44（a）中可以看出，新碼字串仍落在[0.011，0.111）區間之內，因此，解出的第二個符號仍為s3。后面的過程可以此類推。

在算術編碼中，一個值得注意的問題是進位。在霍夫曼編碼中，如（3-151）式所示，后續符號的碼字只是簡單地附加到已編好的碼字串之尾，并不改變已有的碼字串。而在算術編碼中則不同，如在上面的例子中，編完第三個符號之后得到的碼字串為0.10011，在對第四個符號編碼時，將碼串的前3位由0.100變成0.101，這便是由于相加運算中的進位引起的。

2.二進制算術編碼

二進制算術編碼是一種常用的算術編碼方法，所謂二進制是指輸入的字符只有兩種。如果信源字符集內包含有多個字符，則先將這些字符經過一系列的二進判決，變成二進制字符串。圖3-43所示的霍夫曼樹就是這樣的判決方法之一（不遵從霍夫曼概率置換原則的二進樹也可以）。在那里，字符s4的轉換過程可以分解成3次二進判決（100）。

在二進制算術編碼器的兩個輸入字符中，出現概率較大的一個通常稱為MPS（More Probable Symbol），另一個稱為LPS（Less Probable Symbol）。假設LPS出現的概率為Qe，MPS出現的概率則為（1－Qe），圖3-45表示出這兩個符號所對應的概率區間。

對這兩個符號構成的序列的編碼與前面介紹的算術編碼的基本原理是相同的，仍然是不斷劃分概率子區間的遞歸過程。如果我們規定編碼指針指向子區間的底部（見圖3-45），那么編碼規則為：

對于MPS

C＝C ?。?-160）

A＝A（1－Qe）＝A－AQe ?。?-161）

對于LPS

C＝C＋A（1－Qe）＝C＋A－AQe　（3-162）

A＝AQe　（3-163）

在霍夫曼編碼中，最短的碼字為1比特，所以即使在對最常出現的符號進行編碼時，也需要在前面已編好的碼字串上再增加1比特。而在算術編碼中，由（3-160）式可以看出，對MPS編碼不增加已編好的碼字串的長度。這是算術編碼比霍夫曼編碼優越的地方。

在具體實現上述算法時，如下幾個問題值得注意：

①在概率子區間不斷劃分的過程中，區間寬度A越來越小，因此，用來表示A的數字的位數則需要越來越多；

②完成（3-161）式至（3-163）式的運算都要用到成本較高（無論是用硬件實現還是用軟件實現）的乘法運算；

③當已編好的碼字串中連續出現多個1時，若后續編碼過程中在最后一位上加1，將連續改變前面已編好的碼字，產生連續多個0，直到出現1為止，這就是前面提到過的進位問題。

為了有效地實現編碼算法，人們提出了若干辦法來解決上述問題，從而構成了不同類型的二進制算術編碼器，如Q編碼器、QM編碼器和MQ編碼器等。下面我們僅簡單介紹其中的QM編碼器。

用有限精度的算術運算來計算概率區間A，可以保證A的有效數字的位數不至于隨碼字串的增加而增加。例如A＝0.001可以用1.0×2－3來表示，當A被分割到更小值時，則增加指數值，而有效數字的位數仍保持在規定的范圍之內。假設這個范圍選擇在0.75到1.5（十進制數字）之間，當A＜0.75時，將A乘以2（相當于2的負指數增加1），使有效數字保持在0.75～1.5之間，這樣，仍然可以用原來的位數表示，這無論對用硬件還是用軟件來實現編碼都是有利的。上述過程稱之為重新歸一化。乘2運算可以由將數據在寄存器中左移一位的操作來完成。顯然，當區間A重新歸一后，碼字串C也應當隨之歸一，否則C將不能指向正確的區間。

當1.5＞A≥0.75時，AQe≈Qe。利用這個近似式，可將（3-161）式至（3-163）式簡化而無需做乘法。此時二進概率區間變成如圖3-46所示。Qe一般比較小，只有當Qe接近于0.5的情況下，上述近似式引入的誤差才比較明顯。

當Qe接近0.5時，由此近似產生的誤差有可能發生LPS區間大于MPS區間的情況，圖3-47給出了一個例子。圖（a）中Qe＝0.5，初始的A＝1.35，MPS和LPS的區間分別為[0.0，0.85）和[0.85，1.35）。在下一個編碼周期中（圖（b）），區間A更新為A＝A－Qe＝0.85，LPS區間Qe＝0.5，MPS區間變成A－Qe＝0.35。在這種情況下，即Qe＞A－Qe時，需要將MPS和LPS符號及區間互換，這稱為條件互換（Conditional exchange）。圖（b）表示出了條件互換后的結果。在需要進行條件互換時，由于Qe≤0.5，我們有0.5≥Qe＞A－Qe，此時，兩個子區間（Qe和A－Qe）都小于0.75，肯定需要重新歸一化A和C。因此，條件互換總是放在編碼器檢測到需要重新歸一化之后再進行。

將重新歸一化和條件互換結合進（3-160）式至（3-163）式所表示的編碼過程，得到QM編碼器的編碼算法為：

對于MPS：

相應的解碼算法為：

為了簡單起見，這里沒有考慮條件交換。

關于進位的問題，可以用在編碼器輸出之前設置一個緩存器的辦法來解決。連續出現1的碼字串（如連續的8個1）先不輸出，而將它送入一個堆棧暫存，若后續編碼引起進位，則改變堆棧中的數據后再輸出。若不引起進位，則直接輸出堆棧中的碼字。

與霍夫曼編碼一樣，如果輸入信號的實際概率模型（二進編碼中的Qe值）與假設值不一樣，算術編碼的效率也要下降。為了提高編碼效率，可以通過一定方式實時地對實際輸入信號的Qe值進行估計，編碼器則根據所估值動態地更新Qe，這就構成了所謂的自適應二進制算術編碼。在QM編碼中，對概率的估值是通過一個預先設定的Qe表來實現的。該表包括一組按大小排序的Qe值，當編碼過程進行重新歸一化時，若因編碼LPS而導致歸一化，Qe更新為表中下一個較低的值；若因編碼MPS而導致歸一化，Qe則更新為相鄰的較高的值。