王大星，朱鶴鳴

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

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

王大星，朱鶴鳴

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

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

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

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

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

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

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

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

當(dāng)信源是Markov信源時(shí)，p（x n）＝p（x1）p（x2｜x1）…p（x n｜x n－1）。

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

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

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

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

圖1 計(jì)算F（1011010）二叉樹圖

（5）譯碼時(shí)仍用樹圖逐層進(jìn)行判決，假設(shè)從接收到的碼字可計(jì)算出對應(yīng)的F（x n），先從根節(jié)點(diǎn)開始比較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。如此類推，直到譯出最后一個(gè)x n為止。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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

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

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

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

［5］趙風(fēng)光，倪興芳.算術(shù)編碼與數(shù)據(jù)加密［J］.通信學(xué)報(bào)，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é)團(tuán)隊(duì)項(xiàng)目；安徽省高校省級自然科學(xué)研究項(xiàng)目（KJ2011Z277）；滁州學(xué)院科研基金資助項(xiàng)目（2010kj009B）

2011－04－19