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

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

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

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

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

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

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

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

8、后的結(jié)果，算術(shù)壓縮過(guò)程完成。2.2自適應(yīng)算術(shù)編碼的基本原理在上一節(jié)討論的算術(shù)編碼中，我們把信源的統(tǒng)計(jì)特性被看作是固定不變的，這在實(shí)際應(yīng)用中顯然不太實(shí)際。為解決使編碼技術(shù)適應(yīng)信源統(tǒng)計(jì)特性變化的問(wèn)題，前人提出了自適應(yīng)算術(shù)編碼方法，自適應(yīng)算術(shù)編碼在一次掃描中可完成兩個(gè)過(guò)程，即概率模型的建立過(guò)程和掃描編碼過(guò)程。自適應(yīng)算術(shù)編碼在掃描符號(hào)序列前并不知道各符號(hào)的統(tǒng)計(jì)概率，這時(shí)假定每個(gè)概率相等，并平均分配區(qū)間0,1,然后在掃描符號(hào)序列的過(guò)程中不斷調(diào)整各個(gè)符號(hào)的概率。還以前面所舉的例子為例:abc三種字符的初始概率將為=1/3，=1/3，=1/3以此概率分配來(lái)劃分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é)的分析進(jìn)行區(qū)間分配（以下步驟均根據(jù)新的概率和上一節(jié)的公式作相應(yīng)得區(qū)間分配）。（2）下一個(gè)字符c出現(xiàn)后，調(diào)整后的概率分配為=1/5，=2/5，=2/5（3）第三個(gè)字符c出現(xiàn)后，調(diào)整后的概率分配為=1/6，=2/6，=3/6（4）最后一個(gè)字符b出現(xiàn)后，調(diào)整后的概率分配為=1/7，=3/7，=3/7根據(jù)以上步驟完成編碼。類似的，譯碼時(shí)，每譯出一個(gè)字符便進(jìn)行

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

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

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

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

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

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

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

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