信息論編碼報告---算術(shù)編碼

1、基于Matlab的算術(shù)編碼的研究摘要算術(shù)編碼屬信源編碼信源編碼又分為離散編碼和連續(xù)編碼，算術(shù)編碼也屬于離散編碼。本文對算術(shù)編碼的編碼理論和譯碼理論做了詳細的分析，并根據(jù)理論知識在Matlab中搭建算術(shù)編碼的系統(tǒng)，實現(xiàn)了對算術(shù)編碼的整個過程的重現(xiàn)。算術(shù)編碼所需參數(shù)很少，不像哈弗曼編碼那樣需要一個很大的碼表以及大的存儲來存儲計算過程的計算值。但是算術(shù)編碼的計算復(fù)雜性相對較大。關(guān)鍵詞：算術(shù)編碼、Matlab1、 課題研究背景及意義在一個壓縮系統(tǒng)中,無論是有損壓縮還是無損壓縮,編碼往往是必須的環(huán)節(jié)。算術(shù)編碼在數(shù)據(jù)壓縮中,提供了一種有效去除冗余度的機制,是一種到目前為止編碼效率最高的統(tǒng)計熵編碼方法,它比

2、著名的Huffman編碼效率提高10%左右,但是由于其編碼復(fù)雜性和實現(xiàn)技術(shù)的限制以及一些專利權(quán)的限制,所以并不像Huffman編碼那樣應(yīng)用廣泛。國外對算術(shù)編碼的研究較多,取得了許多重要的應(yīng)用,但大多都有專利保護,如JPEG,JPEG2000,JBIG中均采用了算術(shù)編碼;國內(nèi)的研究相對較少,應(yīng)用不是很廣泛,至今了解的人還不是很多。其實在 Shannon 最早提出信息論后不久，Elias 就提出了基本的算術(shù)編碼的想法，1987 年 Witten 等人在文獻中提出了算術(shù)編碼在數(shù)據(jù)壓縮方面的應(yīng)用，指出其比 Huffman 編碼具有更好的壓縮效率，它能夠在不要求概率分布形式的情況下表現(xiàn)出良好的性質(zhì)，這使

3、得算術(shù)編碼在數(shù)據(jù)壓縮方面得到廣泛應(yīng)用及研究。但是另一方面，包括 Huffman 編碼在內(nèi)的早期編碼模式都是采用固定的碼字來表示每一個需要編碼的符號，而從加密的角度來看這些算法都是使用簡單的字母替換，即用一個符號或字符串替換另一個符號或字符串，所以都很容易被破解，不能提供真正意義上的數(shù)據(jù)安全。相反，算術(shù)編碼并不是采用固定碼字來表示每個符號，它的壓縮模式是將一段消息用一個0,1)的真子集（子區(qū)間）來表示，而這個區(qū)間被初始化為0,1)，并且每編碼一個符號區(qū)間就縮小一次。使每一個新區(qū)間都能唯一地表示一段消息。它可以根據(jù)所使用的模型，保證用一段無限逼近信息熵的比特數(shù)來傳輸消息。2、 算術(shù)編碼基本思想21

4、 算術(shù)編碼基本思想算術(shù)編碼是60年代提出提出一種編碼概念，一直到1976年才有其實用技術(shù)的相關(guān)介紹，它的基本原理是：將待編碼的信息數(shù)據(jù)看作是多個符號組成的符號序列，將被編碼信息數(shù)據(jù)的符號序列表示成實數(shù)0和1之間的一個間隔（Interval）。無論信息有多長，其輸出僅僅是一個數(shù)，而且是一個介于0和1之間的二進制小數(shù)。信息越長，編碼表示它的間隔越小，表示這一間隔所需的二進制位越多。例如算術(shù)編碼對某條信息的符號序列輸出為1010001111，那么它表示小數(shù)0.1010001111，也即十進制數(shù)0.64。算術(shù)編碼用到的兩個基本參數(shù)：符號的概率和它的編碼間隔。信源符號的概率決定壓縮編碼的效率，也決定編碼

5、過程中信源符號的間隔，而這些間隔包含在0到1之間，編碼過程中的間隔決定符號壓縮后的輸出。給定事件序列的算術(shù)編碼步驟如下：（1） 編碼器在開始時將“當(dāng)前間隔”L,H設(shè)置為0,1；（2） 對每一個事件編碼器按步驟（a）和（b）進行處理：（a） 編碼鍵當(dāng)前間隔分為子間隔每一個事件一個；（b） 一個子間隔的大小與下一個將出現(xiàn)的事件的概率成比例，編碼器選擇的子間隔對應(yīng)于下一個確切發(fā)生的事件，并使它成為新的當(dāng)前間隔。（3）最后輸出的“當(dāng)前間隔”的下邊界就是給定事件序列的算術(shù)編碼。在傳輸任何信息之前的信息完整范圍是0,1，當(dāng)一個符號被處理時，這一范圍就依據(jù)分配給這一符號的那部分變窄。初始的區(qū)間是0,1，區(qū)間

6、長度（以下用變量R表示）為1，區(qū)間上限（以下用變量H表示）為1，下限（以下用變量L表示）為0。依據(jù)下列公式得到新的區(qū)間： 公式2-1 公式2-2公式中表示新的區(qū)間下限，表示新的區(qū)間上限，表示編碼字符分配的間隔低端，表示編碼字符分配的間隔高端。下面舉例說明算術(shù)編碼的編碼過程: 某條信息中可能出現(xiàn)的字符僅有abc三種，出現(xiàn)的概率分別為：=1/6，=1/3，=1/2。要壓縮的信息序列為bccb。將0,1區(qū)間按照概率的比例分配給三個字符，即a從0.0000到0.1667, b從0.1667到0.5, c從0.5到1.0000。如圖2-1所示：圖2-1 第一步區(qū)間劃分第一個字符b被編碼時，b的=0.16

7、67，=0.5因此 公式2-3 公式2-4按照概率分配比例劃分b對應(yīng)的區(qū)間0.1667,0.5。第二個字符c編碼時使用新生成的范圍0.1667,0.5，c的=0.5，=1，因此 公式2-5 公式2-4劃分的結(jié)果可以用圖形表示，如圖2-2所示:圖2-2 第二步區(qū)間劃分對下一個字符c使用新生成的范圍重復(fù)以上步驟，得到新的范圍0.4167,0.5最后一個字符b，得到新的范圍0.4306,0.4584該區(qū)間就代表整個bccb序列。在這個區(qū)間內(nèi)隨便選擇一個容易變成二進制的數(shù)來代表該區(qū)間，例如0.4375，將它變成二進制0.0111，去掉前面沒有太多意義的0和小數(shù)點，我們可以輸出0111，這就是信息被壓縮

8、后的結(jié)果，算術(shù)壓縮過程完成。2.2自適應(yīng)算術(shù)編碼的基本原理在上一節(jié)討論的算術(shù)編碼中，我們把信源的統(tǒng)計特性被看作是固定不變的，這在實際應(yīng)用中顯然不太實際。為解決使編碼技術(shù)適應(yīng)信源統(tǒng)計特性變化的問題，前人提出了自適應(yīng)算術(shù)編碼方法，自適應(yīng)算術(shù)編碼在一次掃描中可完成兩個過程，即概率模型的建立過程和掃描編碼過程。自適應(yīng)算術(shù)編碼在掃描符號序列前并不知道各符號的統(tǒng)計概率，這時假定每個概率相等，并平均分配區(qū)間0,1,然后在掃描符號序列的過程中不斷調(diào)整各個符號的概率。還以前面所舉的例子為例:abc三種字符的初始概率將為=1/3，=1/3，=1/3以此概率分配來劃分0,1區(qū)間，a從0.0000到0.3333，b從

9、0.3333到0.6667，c從0.6667到1.0000。下邊我們研究概率的自適應(yīng)更新：出現(xiàn)的字符序列為bccb；（1）由于字符b的出現(xiàn)導(dǎo)致abc三種字符的概率分配發(fā)生了變化，調(diào)整后的概率分配為=1/4，=2/4，=1/4以調(diào)整后的概率根據(jù)上一節(jié)的分析進行區(qū)間分配（以下步驟均根據(jù)新的概率和上一節(jié)的公式作相應(yīng)得區(qū)間分配）。（2）下一個字符c出現(xiàn)后，調(diào)整后的概率分配為=1/5，=2/5，=2/5（3）第三個字符c出現(xiàn)后，調(diào)整后的概率分配為=1/6，=2/6，=3/6（4）最后一個字符b出現(xiàn)后，調(diào)整后的概率分配為=1/7，=3/7，=3/7根據(jù)以上步驟完成編碼。類似的，譯碼時，每譯出一個字符便進行

10、一次概率分配的更新，以調(diào)整后的概率分配進行下一步區(qū)間劃分。重復(fù)操作，完成譯碼。自適應(yīng)算術(shù)編碼方式通常無需先定義概率模型，假定所有字符的初始概率相等，均為1/N(N為字符種類數(shù))，然后根據(jù)字符出現(xiàn)的情況進行自適應(yīng)概率更新。隨著編(譯)碼過程的進行，概率分配將逐漸趨于信源的實際概率分布。這種方法對于無法進行概率統(tǒng)計的信源比較合適。3、 算術(shù)編碼的譯碼思想算術(shù)編碼的譯碼過程其實就是編碼過程的逆過程，先根據(jù)編碼所得碼字確定一個碼字所在的范圍，再將原本的0，1）繼續(xù)按信源分布概率 減小，繼續(xù)將累積概率和劃分的區(qū)間進行對比，從而得出第二個碼字，以此類推，從而不斷得出原來的碼字。以二進制編碼為例，每一步比較

11、C-P(a)與A(a)p(0),這里a為前面已譯出的序列串，A(a)是序列串a(chǎn)對應(yīng)的寬度，P(a)是序列a的累積概率值，即為a對應(yīng)區(qū)間的下界值，A(a)p(0)是此區(qū)間內(nèi)下一個輸入為0所占的子區(qū)間寬度。譯碼規(guī)定為:若C-P(a)<A(a)p(0)，則譯碼輸出符號為0；若C-P(a)>A(a)p(0)，則譯碼輸出符號為1。4、 算術(shù)編碼的性能分析算術(shù)編碼過程中產(chǎn)生的編碼值都統(tǒng)一分布在半開區(qū)間0,1)之間，而這是算術(shù)編碼達到最優(yōu)壓縮效率的必要條件，但并非是充分條件。編碼最后的結(jié)果可以在最后的編碼區(qū)間low, high)之間，選擇任意一個數(shù)值來表示，這個值的長度（比特數(shù)）可以任意長，當(dāng)然

12、這個值也可以用比特數(shù)最少的值來表示，如下式所示 bits 公式4-1下面我們詳細介紹滿足第二種選擇以達到最優(yōu)壓縮的充分條件。首先，我們需要知道的是一個壓縮文件仍然存在冗余，包括：把最終編碼值 v 保存為整數(shù)字節(jié)所需多余的比特數(shù)；需要一個固定或者可變長度的比特數(shù)來表示已經(jīng)編碼的符號個數(shù)；一些記錄概率的信息（包括每個符號的概率 P 以及累積概率 Cum_freq）。假設(shè)這些所有的冗余可以用一個正數(shù)比特 表示，可以從式(4-1)推出，若編碼一個字符串 S，編碼每個符號平均所用的比特數(shù)應(yīng)滿足下面的不等式： bits/符號 公式4-2其中，即可得： bits/符號 公式4-3另外，我們定義 E·

13、;表示期望值（平均值）的運算符，所以編碼每個符號所需的比特數(shù)的期望值為： 公式4-4又因為編碼每個符號所需的平均碼字長度不能小于熵值 ，所以有下式成立： 公式4-5同時，可以從中看出 公式4-6也就是說，算術(shù)編碼確實能達到最優(yōu)壓縮效率。這里我們可能會問為什么算術(shù)編碼的每一步都是以區(qū)間的形式表示，而不是單個的編碼值。其實這是因為算術(shù)編碼的最優(yōu)性不僅體現(xiàn)在輸出二元符號，而且對于多元符號來說也是能夠滿足的，因此我們可以在最終的編碼區(qū)間中為不同的輸出符號選擇最優(yōu)的編碼值。5、 算術(shù)編碼的Matlab實現(xiàn)與分析51 總體框架設(shè)計 根據(jù)算術(shù)編碼的原理進行程序設(shè)計，主要分成以下幾個模塊進行設(shè)計包括：符號累計

14、概率的計算，計算編碼區(qū)間，對小數(shù)進行二進制轉(zhuǎn)換，輸出編碼結(jié)果，判斷是否譯碼，譯碼輸出。流程如圖5-1所示：圖5-1 程序流程52模塊設(shè)計5.2.1 算術(shù)編碼碼字長度的確定編碼碼字的長度主要是由信源符號概率矩陣P和被編碼的信源序列M決定，由兩者決定該信源序列的發(fā)生概率p(S)，然后求出它的比特信息量，通過向上取整以確定碼字長度l。5.2.2 算術(shù)編碼碼字長度的確定由上一節(jié)中的對算術(shù)編碼理論的詳細分析中，可知只需求得各個信源符號的積累概率，并根據(jù)式（2-1）和式（2-2）,每輸入一個信源符號，存儲器a1和a2的內(nèi)容就按照這兩個式子更新一次，直至信源符號輸入完畢，就可將計算區(qū)間的中間值作為該序列的碼

15、字輸出。此時存儲器的輸出的碼字為十進制小數(shù)形式，若要轉(zhuǎn)為二進制碼字則需要一個轉(zhuǎn)換函數(shù)dectobin。在5.2.3中將介紹這一函數(shù)。5.2.3小數(shù)十進制轉(zhuǎn)換為二進制該函數(shù)的目的是將十進制小數(shù)以二進制的形式來表示，作為算術(shù)編碼的碼字。二進制的比特數(shù)由人為確定。根據(jù)十進制小數(shù)的性質(zhì)與二進制之間的關(guān)系，將十進制的小數(shù)部分乘以2，若超過1則輸出1，再減去1繼續(xù)做下一位的運算，否則輸出0且直接做下一位的運算，直到二進制的長度為l。至此十進制小數(shù)到二進制的轉(zhuǎn)換完成。5.2.4算術(shù)編碼譯碼模塊該模塊的目的是將信源序列經(jīng)算術(shù)編碼后轉(zhuǎn)成的碼字重新還原成符號序列，驗證能否正確地恢復(fù)所發(fā)送的信息。譯碼過程是上述編碼

16、過程的逆過程，關(guān)鍵是要確定碼字落在哪一個空間以確定相應(yīng)的符號序列。根據(jù)遞推公式的相反過程譯出每個符號。首先計算積累概率，先譯碼出發(fā)送的信源序列的第一個符號，利用遞減，找出第一個大于0的點，就是第一個符號，要求第二個符號的話必須去掉第一個符號的積累概率，再除以第一個符號的發(fā)送概率，以此求得落在哪個區(qū)間來確定發(fā)送的第二個符號，以此類推，直至求出發(fā)送序列的長度n的所有譯碼。53 程序?qū)崿F(xiàn)與分析假設(shè)一組信源有六個符號及其分布概率pa=0.1;pb=0.1;pc=0.3;pd=0.1;pe=0.1;pf=0.3發(fā)送的輸入碼字為abce ，算術(shù)編解碼系統(tǒng)的運行結(jié)果如圖5-2所示。由該圖可知，發(fā)送該序列的碼

17、字長度為12，即需要12比特的信息量來表示該序列。算術(shù)編碼的碼字為 000000111001。算術(shù)譯碼結(jié)果為abce與發(fā)送序列完全相同，說明該系統(tǒng)設(shè)計正確。若分布概率保持不變，發(fā)送的輸入碼字為abceddf,其運行結(jié)果如圖5-3所示。由該圖可知，發(fā)送該序列的碼字長度為21，算術(shù)編碼的碼字為000000111001001101100，譯碼結(jié)果與發(fā)送序列完全相同，說明該系統(tǒng)設(shè)計正確。 圖5-2 程序運行結(jié)果圖5-3 運行結(jié)果6、 心得體會 通過查找相關(guān)資料，然后進行算術(shù)編碼理論研究和程序設(shè)計，盡管設(shè)計的程序存在封裝性不高，過于簡單的缺點，但是在這過程中，我受益匪淺，首先對算術(shù)編碼的原理、發(fā)展和應(yīng)用有了系統(tǒng)的認識，其次深入了解了Matlab編程方式，有了一定的編程基礎(chǔ)。當(dāng)然，整個程序過于粗糙，沒有進行優(yōu)化，希望日后能夠改正這一缺陷，完善系統(tǒng)。參考文獻1 韋彬，游彬，萬福等算術(shù)編碼理論及誤差分析研究J艦船電子工程，2011，（12）：69712 王大星，朱鶴鳴關(guān)于算術(shù)編碼教學(xué)的幾點注記J滁州學(xué)院學(xué)報2011，（13）：97993 徐蘇珊，馬國強，徐建建算術(shù)熵編碼CABACJ電子測量技術(shù)2005，（4）：674 毛文娟，王建立，張孝三算術(shù)編碼在圖像壓縮系統(tǒng)中的