關(guān)于算術(shù)編碼教學(xué)的幾點注記

王大星，朱鶴鳴

（滁州學(xué)院數(shù)學(xué)科學(xué)學(xué)院，安徽滁州 239000）

關(guān)于算術(shù)編碼教學(xué)的幾點注記

王大星，朱鶴鳴

（滁州學(xué)院數(shù)學(xué)科學(xué)學(xué)院，安徽滁州 239000）

隨著科學(xué)技術(shù)的發(fā)展，信息、通信類本科生學(xué)習(xí)信息論是十分必要的。算術(shù)編碼是基于統(tǒng)計的、無損數(shù)據(jù)壓縮效率最高的編碼方法。針對算術(shù)編碼教學(xué)中存在的問題，本文進一步探討了算術(shù)編碼的編碼、譯碼過程，提出了編碼過程中需要注意的問題，并將算術(shù)編碼與哈夫曼編碼做了比較。最后，用Matlab實現(xiàn)了算術(shù)編碼的具體實例。

算術(shù)編碼；數(shù)據(jù)壓縮；二叉樹；哈夫曼編碼

隨著信息技術(shù)的發(fā)展，編碼技術(shù)已經(jīng)在媒體技術(shù)、網(wǎng)絡(luò)技術(shù)、無線通信技術(shù)、數(shù)字電視技術(shù)等方面得到廣泛應(yīng)用。因此，信息與計算科學(xué)與電子信息類等專業(yè)的本科生應(yīng)該具備一定的信息論基本理論以及信源、信道編碼理論和技術(shù)等方面的基本知識。為了滿足需要，許多高校在本科教學(xué)中開設(shè)了信息論與編碼課程。信息論［1］［2］是一門應(yīng)用概率論、隨機過程和數(shù)理統(tǒng)計等方法來研究信息的存儲、傳輸和處理中一般規(guī)律的學(xué)科。編碼理論則與信息論一脈相承，它以信息論基本原理為理論依據(jù)，講述編碼的理論知識和實現(xiàn)方法。

算術(shù)編碼在圖像數(shù)據(jù)壓縮標準（如JPEGJBIG）中扮演了重要的角色，是無失真變長編碼的一種.算術(shù)編碼中，消息用0和1之間的實數(shù)進行編碼，該編碼用到兩個基本的參數(shù)：符號的概率和它的編碼間隔.信源符號的概率決定了壓縮編碼的效率，也決定了編碼過程中信源符號的間隔，而這些間隔包含在0到1之間.編碼過程中的間隔決定了符號壓縮后的輸出。作者在教學(xué)過程中發(fā)現(xiàn)，教材中這部分內(nèi)容介紹得相當粗略，定理的證明晦澀難懂，而且很少有例題分析。這些將導(dǎo)致學(xué)生在學(xué)習(xí)時顯得很吃力。作者針對以上問題，結(jié)合多年來的教學(xué)經(jīng)驗探討有關(guān)算術(shù)編碼的教學(xué)問題，將教材中的理論細化，并作適當?shù)难由?，以期給教師和學(xué)生帶來些許幫助。

1 教學(xué)中采用二叉樹解釋算術(shù)編碼的編譯碼過程

下面給出一個簡化的計算程序來理解算術(shù)碼編譯碼的基本要點。不是一般性，我們僅考慮二進信源，即信源字母集為χ＝｛0，1｝。對n長的信源字母列x n＝（x1，x2，…，x n）∈χn進行編碼。

（1）先對所有x n∈χn，計算概率p（x n）＝p（x1，x2，…，x n）；

當信源是Markov信源時，p（x n）＝p（x1）p（x2｜x1）…p（x n｜x n－1）。

（2）在χn上建立一個字典序，對x n，yn∈χn，稱x n＞y n，如果在第一個滿足xi≠yi的第i個分量上x i＝1，yi＝0，這個條件等價于＞，也等價于它們對應(yīng)的二進制小數(shù)0.

我們記x n（i）表示χn中在字典序下第i個n長的向量。

（3）用一個二叉樹［4］來表示｛x n：xn∈χn｝，A為根節(jié)點，每個x n對應(yīng)第n層上一個節(jié)點，那么從根節(jié)點到該節(jié)點的路上經(jīng)過的邊上的符號就是x1x2…x n。顯然，按字典排序如果x n＞yn，其充分必要條件是x n對應(yīng)之節(jié)點在y n對應(yīng)的節(jié)點的右邊。

假設(shè)X1，X2…為無記憶信源，服從公共分布為伯努利分布，p（1）＝θ，p（0）＝1－θ.下面來計算F（1011010），如圖1所示。

圖1 計算F（1011010）二叉樹圖

（5）譯碼時仍用樹圖逐層進行判決，假設(shè)從接收到的碼字可計算出對應(yīng)的F（x n），先從根節(jié)點開始比較F（x n）和p（0）。如果F（x n）＞p（0），則從0往下的子樹在x n的左邊，于是第一位譯出x1＝1，反之若F（x n）＜p（0），則譯出x1＝0。如果已經(jīng)譯出x1＝0，則繼續(xù)比較F（x n）和p（00），如F（x n）＞p（00），則譯出x2＝0。如此類推，直到譯出最后一個x n為止。

2 算術(shù)編碼教學(xué)中需要注意的問題

由于實際的計算機的精度不可能無限長，運算中出現(xiàn)溢出是一個明顯的問題，但多數(shù)機器都有16位、32位或者64位的精度，因此這個問題可使用比例縮放方法解決。首先，算術(shù)編碼器對整個消息只產(chǎn)生一個碼字，這個碼字是在間隔［0，1）中的一個實數(shù)，因此譯碼器在接受到表示這個實數(shù)的所有位之前不能進行譯碼。其次，算術(shù)編碼也是一種對錯誤很敏感的編碼方法，如果有一位發(fā)生錯誤就會導(dǎo)致整個消息譯錯。再次，算術(shù)編碼可以是靜態(tài)的或者自適應(yīng)的。在靜態(tài)算術(shù)編碼中，信源符號的概率是固定的。在自適應(yīng)算術(shù)編碼中，信源符號的概率根據(jù)編碼時符號出現(xiàn)的頻繁程度動態(tài)地進行修改，在編碼期間估算信源符號概率的過程叫做建模。需要開發(fā)靜態(tài)算術(shù)編碼的原因是因為事先知道精確的信源概率是很難的，而且是不切實際的。當壓縮消息時，我們不能期待一個算術(shù)編碼器獲得最大的效率，所能做的最有效的方法是在編碼過程中估算概率。算術(shù)編碼的靜態(tài)與自適應(yīng)模型因此動態(tài)建模就成為確定編碼器壓縮效率的關(guān)鍵。最后，算術(shù)編碼非常依賴計算機的計算能力和存儲能力。過去，這種依賴極大地限制了它的發(fā)展，在提出的最初幾年，算術(shù)編碼壓縮算法只在極小的范圍內(nèi)有原型實現(xiàn)。隨著計算機科學(xué)技術(shù)的發(fā)展，許多算術(shù)編碼的實現(xiàn)在執(zhí)行速度上已經(jīng)能夠被人們接受［4］。如前面所說的那樣，實現(xiàn)算術(shù)編碼的核心問題在于如何獲得正確的頻率，以及如何高效地實現(xiàn)精確的乘法計算。

在算術(shù)編碼高階上下文模型的實現(xiàn)中，對內(nèi)存的需求量是一個十分棘手的問題。因為我們必須保持對已出現(xiàn)的上下文的計數(shù)，而高階上下文模型中可能出現(xiàn)的上下文種類太多了，數(shù)據(jù)結(jié)構(gòu)的設(shè)計將直接影響到算法實現(xiàn)的成功與否。在1階上下文模型中，使用數(shù)組來進行出現(xiàn)次數(shù)的統(tǒng)計是可行的，但對于2階或3階上下文模型，數(shù)組大小將依照指數(shù)規(guī)律增長，現(xiàn)有計算機的內(nèi)存滿足不了我們的要求。比較聰明的辦法是采用樹結(jié)構(gòu)存儲所有出現(xiàn)過的上下文。利用高階上下文總是建立在低階上下文的基礎(chǔ)上這一規(guī)律，我們將0階上下文表存儲在數(shù)組中，每個數(shù)組元素包含了指向相應(yīng)的1階上下文表的指針，1階上下文表中又包含了指向2階上下文表的指針…由此構(gòu)成整個上下文樹。樹中只有出現(xiàn)過的上下文才擁有已分配的節(jié)點，沒有出現(xiàn)過的上下文不必占用內(nèi)存空間。在每個上下文表中，也無需保存所有256個字符的計數(shù)，只有在該上下文后面出現(xiàn)過的字符才擁有計數(shù)值。由此，我們可以最大限度地減少空間消耗。

3 總結(jié)算術(shù)編碼與哈夫曼編碼的區(qū)別

哈夫曼編碼屬于碼字長度可變的編碼類，即從下到上的編碼方法。同其他碼字長度可變的編碼一樣，可區(qū)別的不同碼字的生成是基于不同符號出現(xiàn)的不同概率。生成哈夫曼編碼算法基于一種稱為“編碼樹”的技術(shù)。算法步驟如下：① 初始化，根據(jù)符號概率的大小按由大到小順序?qū)Ψ栠M行排序。②把概率最小的兩個符號組成一個新符號，即新符號的概率等于這兩個符號概率之和。③ 重復(fù)第②步，直到形成一個符號為止，其概率最后等于1。④ 從編碼樹的根開始回溯到原始的符號，并將每一個下分枝賦值為1，上分枝賦值為0。

采用哈夫曼編碼時有兩個問題值得注意：① 哈夫曼編碼沒有錯誤保護功能，在譯碼時，如果碼串中沒有錯誤，那么就能一個接一個地正確譯出代碼。但如果碼串中有錯誤，哪怕僅僅是1位出現(xiàn)錯誤，也會引起一連串的錯誤，這種現(xiàn)象稱為錯誤傳播。計算機對這種錯誤也無能為力，說不出錯在哪里，更談不上去糾正它。② 哈夫曼編碼是可變長度碼，因此很難隨意查找或調(diào)用壓縮文件中間的內(nèi)容，然后再譯碼，這就需要在存儲代碼之前加以考慮。

而算術(shù)編碼的基本原理是將編碼的消息表示成實數(shù)0和1之間的一個間隔，消息越長，編碼表示它的間隔就越小，表示這一間隔所需的二進制位就越多。算術(shù)編碼用到兩個基本的參數(shù)：符號的概率和它的編碼間隔。信源符號的概率決定壓縮編碼的效率，也決定編碼過程中信源符號的間隔，而這些間隔包含在0到1之間。編碼過程中的間隔決定了符號壓縮后的輸出。給定事件序列的算術(shù)編碼步驟如下：① 編碼器在開始時將“當前間隔”［L，H］設(shè)置為［0，1］。②對每一事件，編碼器按步驟A和B進行處理。A.編碼器將“當前間隔”分為子間隔，每一個事件一個。B.一個子間隔的大小與下一個將出現(xiàn)的事件的概率成比例，編碼器選擇子間隔對應(yīng)于下一個確切發(fā)生的事件，并使它成為新的“當前間隔”。③ 最后輸出的“當前間隔”的下邊界就是該給定事件序列的算術(shù)編碼。

算術(shù)編碼是一種到目前為止編碼效率最高的統(tǒng)計熵編碼方法，它比著名的哈夫曼編碼效率提高10%左右，但由于其編碼復(fù)雜性和實現(xiàn)技術(shù)的限制以及一些專利權(quán)的限制，所以并不像哈夫曼編碼那樣應(yīng)用廣泛。算術(shù)編碼有兩點優(yōu)于哈夫曼碼：① 它的符號表示更緊湊；② 它的編碼和符號的統(tǒng)計模型是分離的，可以和任何一種概率模型協(xié)同工作。后者非常重要，因為只要提高模型的性能就可以提高編碼效率。

哈夫曼碼字必定是整數(shù)的比特長，這樣就會產(chǎn)生問題：如一個符號的概率為0.3，則編碼該符號的最優(yōu)比特數(shù)大約是1.6，那么哈夫曼不得不將其碼字設(shè)為1比特或2比特，并且每種選擇都會得到比理論上可能的長度更長的壓縮消息。而算術(shù)編碼可以解決這個問題。算術(shù)編碼是一種高效清除字串冗余的算法。它避開用一個特定碼字代替一串輸入符號的思想，而用一個單獨的浮點數(shù)來代替一串輸入符號，避開了哈夫曼編碼中比特數(shù)必須取整的問題。但是算術(shù)編碼的實現(xiàn)有兩大缺陷：① 很難在具有固定精度的計算機完成無限精度的算術(shù)操作。② 高度復(fù)雜的計算量不利于實際應(yīng)用。

算術(shù)編碼是一種無失真的編碼方法，能有效地壓縮信源冗余度，屬于熵編碼的一種。算術(shù)編碼的一個重要特點就是可以按分數(shù)比特逼近信源熵，突破了哈夫曼編碼每個符號只不過能按整數(shù)個比特逼近信源熵的限制。對信源進行算術(shù)編碼，往往需要兩個過程，第一個過程是建立信源概率表，第二個過程是對信源發(fā)出的符號序列進行掃描編碼。而自適應(yīng)算術(shù)編碼在對符號序列進行掃描的過程中，可一次完成上述兩個過程，即根據(jù)恰當?shù)母怕使烙嬆Ｐ秃彤斍胺栃蛄兄懈鞣柍霈F(xiàn)的頻率，自適應(yīng)地調(diào)整各符號的概率估計值，同時完成編碼。盡管從編碼效率上看不如已知概率表的情況，但正是由于自適應(yīng)算術(shù)編碼具有實時性好、靈活性高、適應(yīng)性強等特點，在圖像壓縮、視頻圖像編碼等領(lǐng)域都得到了廣泛的應(yīng)用。

4 算術(shù)編碼的程序?qū)崿F(xiàn)舉例

Matlab語言是由美國MathWorks公司推出的計算機軟件，經(jīng)過多年的逐步發(fā)展與不斷完善，現(xiàn)在已成為國際公認的最優(yōu)秀的科學(xué)計算與數(shù)學(xué)應(yīng)用軟件之一，是近幾年來在國內(nèi)外廣泛流行的一種可視化科學(xué)計算軟件。它集數(shù)值分析、矩陣運算、信號處理和圖形顯示于一體，構(gòu)成了一個方便的、界面友好的用戶環(huán)境，而且還具有可擴展性特征。在本文中，所用到的算術(shù)編碼就可以用Matlab進行實現(xiàn)。Matlab的語法規(guī)則比C語言等高級語言更簡單，更重要的是貼近人的思維方式的編程特點。所以，在我們進行圖像壓縮時，這是一種很好的方法。

軟件運行步驟：單擊“MATLAB”圖標－“file”－“New－M－file”，編寫好源程序之后，運行程序仿真即可。

下面我們用Matlab工具舉例實現(xiàn)算術(shù)碼的一個例子。其程序如下：

5 結(jié)束語

隨著信息技術(shù)的發(fā)展，各種媒體信息（特別是圖像和動態(tài)視頻）數(shù)據(jù)量非常之大。從家庭娛樂到專業(yè)的通信設(shè)備、從廉價的消費電子產(chǎn)品到昂貴的專業(yè)設(shè)備，應(yīng)用的例子舉不勝舉。算術(shù)編碼作為一種高效的數(shù)據(jù)編碼方法在文本，圖像，音頻等壓縮中有廣泛的應(yīng)用，甚至還可以將它應(yīng)用于文件的加解密［5］。算術(shù)編碼從性能上看具有許多優(yōu)點，特別是由于所需的參數(shù)很少，不像哈夫曼那樣需要一個很大的碼表，常設(shè)計成自適應(yīng)算術(shù)編碼來針對一些信源概率未知或非平穩(wěn)情況。但是在實際實現(xiàn)時還有一些問題，如計算復(fù)雜性，計算的精度以及存儲量等，隨著這些問題的解決，算術(shù)編碼正在進入實用階段，但要擴大應(yīng)用范圍或進一步提高性能，降低造價，還需進一步改進。所以，研究算術(shù)編碼有非常好的前景與實用價值。

［1］朱雪龍.應(yīng)用信息論基礎(chǔ)［M］.北京：清華大學(xué)出版社，2001.

［2］沈世鎰，吳忠華.信息論基礎(chǔ)與應(yīng)用［M］.北京：高等教育出版社，2005.

［3］嚴蔚敏.數(shù)據(jù)結(jié)構(gòu)（C語言版）［M］.北京：清華大學(xué)出版社，2007.

［4］仇佩亮.數(shù)字通信基礎(chǔ)［M］.北京：電子工業(yè)出版社，2007.

［5］趙風(fēng)光，倪興芳.算術(shù)編碼與數(shù)據(jù)加密［J］.通信學(xué)報，1999，20（4）：92－96.

Remarks on Arithmetic coding Teaching

Wang Daxing，Zhu Heming
（Department of Mathematics of Chuzhou university chuzhou 239012，China）

With the development of science and technology，it is necessary for the students of specialty on information science and communication technique to learn the course of Information Theory and Coding Theory.Arithmetic coding is the most powerful technique for lossless data compression.For problems in arithmetic teaching，the paper shows the process of arithmetic coding and decoding，illustrating with specific examples.The problems which needs attention in coding are proposed，and compared with the Huffman coding.Finally，we achieved specific examples of arithmetic coding with Matlab.

Arithmetic coding；Data compression；Binary tree；Huffman coding

TP301

A

1673－1794（2011）05－0097－04

王大星（1980－），男，碩士，講師，研究方向：密碼學(xué)。

滁州學(xué)院應(yīng)用數(shù)學(xué)省級教學(xué)團隊項目；安徽省高校省級自然科學(xué)研究項目（KJ2011Z277）；滁州學(xué)院科研基金資助項目（2010kj009B）

2011－04－19