算術編碼理論及誤差分析研究＊

韋 偉 游 彬 萬 福 劉俊起

（海軍指揮學院信息戰(zhàn)研究系 南京 211800）

1 引言

在數(shù)字時代飛速發(fā)展的今天，壓縮技術已經(jīng)成為數(shù)據(jù)傳輸中必不可少的關鍵技術，數(shù)據(jù)壓縮就是在一定精度所要求的條件下，以最少的數(shù)碼表示信息所發(fā)出的信號。數(shù)據(jù)壓縮技術分為：無損壓縮和有損壓縮。無損壓縮是指將壓縮后的數(shù)據(jù)進行還原，還原后的數(shù)據(jù)與原來的數(shù)據(jù)完全相同。有損壓縮是指壓縮后的數(shù)據(jù)還原后與原來的數(shù)據(jù)有所不同，但不會造成人對原始資料表達的信息造成誤解。

早在1948年C.E.Shannon［1］提出信息論的時候，就提出了算術編碼的思想。算術編碼的概念是Elias在上世紀六十年代初期提出來的，直到八十年代才開始進入實用化階段。Langdon［2］和Rissanen［3］等人在此期間對算術編碼作了大量的理論研究。算術編碼屬信源編碼［4］，信源編碼又分為離散編碼和連續(xù)編碼，算術編碼也屬于離散編碼。論文主要通過對算術編碼和譯碼的分析從而得出算術編碼在實際應用中出現(xiàn)的誤差，本文最后還闡述了在程序算法設計中通過損失精度來實現(xiàn)算術編碼的思想。

2 算術編碼理論的基本思想

算術編碼的基本思想是：從整個符號序列出發(fā)，將各信源序列概率映射到［0，1）區(qū)間上，使每個符號序列對應于區(qū)間內(nèi)的一點，也就是一個二進制的小數(shù)。這些點把［0，1）區(qū)間分成許多小段，每段的長度等于某一信源序列的概率。再在段內(nèi)取一個二進制小數(shù)，其長度可與該序列的概率匹配，達到高效率編碼的目的［5］。這種方法與香農(nóng)編碼法比較類似，只是兩者考慮的信源對象有所不同，在香農(nóng)編碼中研究的是單個信源符號，而在算術編碼中研究的是信源符號序列。

定義各符號的積累概率為：

則由式（1）可得：P1＝0；P2＝p1；…；Pn＝Pn－1＋pn－1。如圖1所示累積概率的分布。

圖1 信源符號對應的概率區(qū)間

對于整個信源符號序列而言，要把一個算術碼字賦給它，就必須確定這個算術碼字所對應的位于［0，1）區(qū)間內(nèi)的實數(shù)范圍，即由整個信源符號序列的概率本身確定0和1之間的一個實數(shù)區(qū)間。隨著符號序列中的符號數(shù)量的增加，用來代表它的區(qū)間減小，而用來表達區(qū)間所需的信息單位（如比特）的數(shù)量則增大。

每個符號序列中隨著符號數(shù)量的增加，即信源符號的不斷輸入，用于代表符號序列概率的區(qū)間將隨之減小，區(qū)間減小的過程如圖2所示。

圖2 以二元序列為例

由圖2我們可以發(fā)現(xiàn)，輸入信源序列為｛01111｝，當輸入第一個‘0’時，概率空間被分割成兩部分，p（0）和p（1）兩個部分，代表‘0’的是p（0）區(qū)間；再輸入‘1’時，p（0）區(qū)間再次分割，分割成p（00）和p（01）兩個區(qū)間，其中p（01）區(qū)間表示‘01’輸入；以此類推，可以得到代表‘01111’的區(qū)間是p（01111）。

我們在輸入序列對應的區(qū)間內(nèi)任意取一點，代表輸入序列，并將取得的這個點作為依據(jù)進行編碼，這種方式所得到的碼字就稱為算術編碼。

3 算術編碼的譯碼理論

算術編碼譯碼的過程其實就是編碼過程的逆過程，先根據(jù)編碼所得碼字確定第一個碼字所在的范圍，再將原本的［0，1）繼續(xù)按信源分布概率減小，繼續(xù)將累積概率和劃分的區(qū)間進行比對，從而得出第二個碼字，以此類推，從而不斷得出原來的碼字。

以二進制編碼為例，每一步比較C－P（α）與A（α）p（0），這里α為前面已譯出的序列串，A（α）是序列串α對應的寬度，P（α）是序列α的累積概率值，即為α對應區(qū)間的下界值，A（α）p（0）是此區(qū)間內(nèi)下一個輸入為‘0’所占的子區(qū)間寬度。

譯碼規(guī)定為：

若C－P（α）＜A（α）p（0），則譯輸出符號為0；

若C－P（α）＞A（α）p（0），則譯輸出符號為1。

由此，我們引入一個例子［5］，設二元無記憶信源S＝｛0，1｝，其中p（0）＝0.25，p（1）＝0.75。對二元序列α＝11111100進行算術編碼，編碼后并進行譯碼驗證。我們可以得到α序列發(fā)生的概率為p（α）＝p（111111100）＝ （0.75）6（0.25）2＝0.01112366。

我們通過一種算術編碼方式確定α的算術碼字長度，L可以等于p（α）的倒數(shù)的對數(shù)，其值為6.49，6.49 ＝7；可以得出P（α）的累積概率為0.82202148。

信源符號序列α的累積概率值的變化和區(qū)間寬度減小的過程如圖3所示。累積概率p（α）為輸入符號序列11111100的下界值。

圖3 算術編碼過程區(qū)間寬度減小圖解

取p（α）二進制表示小數(shù)點后L位，得到信源符號序列α的算術碼字為‘1101010’。則平均碼長為ˉL＝0.875，編碼效率為：η＝0.927。

4 算術編碼譯碼誤差分析

通過上面的分析，我們可以很容易地看出，在信源符號的不斷增加中，長符號序列和短符號序列相比，誤差在不斷增加。而整個［0，1）區(qū)間在不斷減小，隨著概率區(qū)間的減小，累積概率對概率的精度要求越來越高，從而算術編碼的誤差就在不斷增加。

以上面的例子來看，最后所得的碼為1101010，化成十進制碼后為0.828125，與原來的累積概率0.82202148相比較，千分位數(shù)據(jù)相差太大。我們在譯碼的時候可以發(fā)現(xiàn)，0.828125首先處在［0，1）的后3／4中，則譯出第一位碼為1，之后考慮［0.25，1）區(qū)間，0.828125又處在后3／4處，第二位再譯出一個1，以此類推，具體過程如圖4所示。

最終導致我們譯碼的時候小數(shù)點后第七位和第八位無法準確譯出。所以算術編碼具體編碼方式的選擇還存在一定的問題。

圖4 譯碼誤差分析

對于上述問題的解決方式目前只能通過在放棄一定精度的情況下編碼，Ian H.witten、Radford M.Nea和John G.Cleary等人發(fā)表論文［6］，提出了一種基于整數(shù)運算的算術編碼實現(xiàn)算法。在算法實現(xiàn)中，通過改進算法，把映射的區(qū)間擴大，如使用［0，1000）這個區(qū)間來映射概率。這樣，在處理過程中，精度比用［0，1）區(qū)間損失更大，但其優(yōu)點是處理速度加快，編碼容易。在編碼的過程中，還通過正規(guī)化提取等操作使得算法速度更快，效率更高［7］。

5 結語

本文分析了算術編碼的編碼和解碼理論，具體指出了編碼方式中的一些誤差和缺陷。通過本文，讀者可以對算術編碼有更為清晰的認識，對算術編碼的編碼選擇方式，譯碼過程會有更深的體會。算術編碼本身具有很好的數(shù)據(jù)屏蔽性能［8～9］，可以同時實現(xiàn)壓縮加密，而僅需損失少量的編碼效率。目前，算術編碼在圖像壓縮標準（如JPEG）［11］中得到了廣泛的應用，希望本文對算術編碼的具體實用人員有所幫助。

［1］C.E.Shannon.A mathematical Theory of Communication［J］.Bell System Technical Journal，1948，27：379～423，623～656

［2］Langdon G G，Jorma Rissanen.Compression of Black-White Images with Arithmetic Coding［J］.IEEE Trans.Commun.COM-29，1981（6）：858～867

［3］Langdon G G，Jorma Rissanen.A Double Adaptive File Compression Algorithm［J］.IEEE Trans.Commun.COM-31，1983：1253～1255

［4］John G.Proakis.Digital Communications（Fourth Edition）（張力軍，張宗橙，鄭寶玉，等譯）

［5］馮桂，林其偉，陳東華.信息論與編碼技術［M］.北京：清華大學出版社，2007，3

［6］Ian H.witten，Radford M.Nea，John G.Cleary.A-rithmetic Coding for Data Compression［J］.Communications of the ACM，1987，30（6）：520～541

［7］編 程 論 壇 ［EB／OL］.http：／／programbbs.com／bbs／view12-29356-1.htm

［8］倪興芳，姜峰.算術編碼與數(shù)據(jù)加密［J］.通信學報，1999，20（4）

［9］彭云，任俊彥，葉凡，等.一種適于硬件實現(xiàn)的算術編碼算法［J］.通信學報，2001，22（2）

［10］倪桂強，李彬，羅健欣.BWT與經(jīng)典壓縮算法研究［J］.計算機與數(shù)字工程，2010，38（11）

［11］余成波.信息論與編碼基礎.北京：機械工業(yè)出版社，2005