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

信息論與編碼——算術(shù)編碼主要內(nèi)容一、信息論概念二、算術(shù)編碼一、信息論概念

信息論或稱為通信的數(shù)學(xué)理論，應(yīng)用概率論和數(shù)理統(tǒng)計(jì)的方法研究有效地、可靠地、安全地傳遞信息的科學(xué)。

2.

分類◆信息論基礎(chǔ)（香農(nóng)信息論、狹義信息論）◆一般信息論◆廣義信息論一、信息論◆信息論基礎(chǔ)（香農(nóng)信息論、狹義信息論）在信息可以量度的基礎(chǔ)上，研究有效地、可靠地傳遞信息。（信息的量度、信道容量、信息率失真函數(shù)，與這三個概念相對應(yīng)的香農(nóng)三大定理，信源編碼、信道編碼）◆一般信息論研究信息傳輸和處理。

包括通信的全部統(tǒng)計(jì)問題：●Shannon：依附在信號上的信息

●Wiener：攜帶信息的信號◆廣義信息論

不僅包括一般信息論的所有研究內(nèi)容，還包括如醫(yī)學(xué)、生物學(xué)、心理學(xué)、遺傳學(xué)、語言學(xué)，甚至社會學(xué)和經(jīng)濟(jì)管理中有關(guān)信息的問題。香農(nóng)信息論的基本任務(wù)：為設(shè)計(jì)有效而可靠的通信系統(tǒng)提供理論依據(jù)通信系統(tǒng)的模型二、算術(shù)編碼1、算術(shù)編碼的定義2、自適應(yīng)算術(shù)編碼3、靜態(tài)算術(shù)編碼4、程序設(shè)計(jì)1、算術(shù)編碼的定義算術(shù)編碼是一種無損數(shù)據(jù)壓縮方法，也是一種熵編碼的方法。和其它熵編碼方法不同的地方在于，其他的熵編碼方法通常是把輸入的消息分割為符號，然后對每個符號進(jìn)行編碼，而算術(shù)編碼是直接把整個輸入的消息編碼為一個數(shù)，一個滿足(0.0≤n<1.0)的小數(shù)n。算術(shù)編碼在圖像數(shù)據(jù)壓縮標(biāo)準(zhǔn)(如JPEG，JBIG)中扮演了重要的角色。在算術(shù)編碼中，消息用0到1之間的實(shí)數(shù)進(jìn)行編碼，算術(shù)編碼用到兩個基本的參數(shù)：符號的概率和它的編碼間隔。信源符號的概率決定壓縮編碼的效率，也決定編碼過程中信源符號的間隔，而這些間隔包含在0到1之間。編碼過程中的間隔決定了符號壓縮后的輸出。分類算術(shù)編碼是用符號的概率和它的編碼間隔兩倆個基本參數(shù)來描述的。算術(shù)編碼可以是靜態(tài)的或是自適應(yīng)的。在自適應(yīng)算術(shù)編碼中，信源符號的概率根據(jù)編碼時符號出現(xiàn)的頻繁程度動態(tài)地進(jìn)行修改。在靜態(tài)算術(shù)編碼中，信源符號的概率是固定的。在編碼期間估算信源符號概率的過程叫建模。需要開發(fā)動態(tài)算術(shù)編碼的原因，是因?yàn)槭孪戎谰_的信源符號概率是很難的，而且是不切實(shí)際的。動態(tài)建模是確定編碼器壓縮效率的關(guān)鍵。2、自適應(yīng)算術(shù)編碼例1：算術(shù)編碼對某條信息的輸出為1010001111，那么它表示小數(shù)0.1010001111，也即十進(jìn)制數(shù)0.64。

考慮某條信息中可能出現(xiàn)的字符僅有abc三種，要壓縮保存的信息為bccb。采用的是自適應(yīng)模型，開始時暫時認(rèn)為三者的出現(xiàn)概率相等，也就是都為1/3，將0-1區(qū)間按照概率的比例分配給三個字符，即a從0.0000到0.3333，b從0.3333到0.6667，c從0.6667到1.0000。用圖形表示就是：+0.0000_Pa=1/3+0.3333

Pb=1/3

+0.6667

Pc=1/3

+1.0000現(xiàn)在拿到第一個字符b，把目光投向b對應(yīng)的區(qū)間0.3333-0.6667。這時由于多了字符b，三個字符的概率分布變成：Pa=1/4，Pb=2/4，Pc=1/4。好，按照新的概率分布比例劃分0.3333-0.6667這一區(qū)間，劃分的結(jié)果可以用圖形表示為：+0.3333

Pa=1/4

+0.4167Pb=2/4

+0.5834

Pc=1/4

+0.6667接著拿到字符c，現(xiàn)在要關(guān)注上一步中得到的c的區(qū)間0.5834-0.6667。新添了c以后，三個字符的概率分布變成Pa=1/5，Pb=2/5，Pc=2/5。用這個概率分布劃分區(qū)間0.5834-0.6667：+0.5834

Pa=1/5+0.6001

Pb=2/5

+0.6334

Pc=2/5

+0.6667

現(xiàn)在輸入下一個字符c，三個字符的概率分布為：Pa=1/6，Pb=2/6，Pc=3/6。來劃分c的區(qū)間0.6334-0.6667：+0.6334Pa=1/6+0.6390Pb=2/6+0.6501Pc=3/6+0.6667

輸入最后一個字符b，因?yàn)槭亲詈笠粋€字符，不用再做進(jìn)一步的劃分了，上一步中得到的b的區(qū)間為0.6390-0.6501，好，在這個區(qū)間內(nèi)隨便選擇一個容易變成二進(jìn)制的數(shù)，例如0.64，將它變成二進(jìn)制0.1010001111，去掉前面沒有太多意義的0和小數(shù)點(diǎn)，我們可以輸出1010001111，這就是信息被壓縮后的結(jié)果，就完成了一次最簡單的算術(shù)壓縮過程。其譯碼的過程跟編碼過程相似，具體如下表。自適應(yīng)算術(shù)編碼的譯碼過程：步驟間隔譯碼符號譯碼判決1[0.3333,0.6667)b0.64在[0.3333,0.6667)2[0.5834,0.6667)c0.64在[0.3333,0.6667)的最后1/4區(qū)間內(nèi)3[0.6334,0.6667)c0.64在[0.3333,0.6667)的最后2/5區(qū)間內(nèi)4[0.6390,0.6501)b0.64在[0.3333,0.6667)的最后第2和第3個1/6區(qū)間內(nèi)5譯碼結(jié)果：bccb3、靜態(tài)算術(shù)編碼

例如輸入的消息序列為：10001100101101編碼和譯碼過程步驟1：步驟2：步驟3：4、程序設(shè)計(jì)流程圖開始輸入字符判斷字符是否有效N輸出結(jié)果編碼譯碼Y開始編碼分配初始概率判斷讀入的字符分配在哪個區(qū)間重新分配概率判斷是否是最后一個字符轉(zhuǎn)化成二進(jìn)制輸出NY二進(jìn)制轉(zhuǎn)化成十進(jìn)制開始譯碼分配初始概率比較數(shù)據(jù)在哪個區(qū)間重新分配概率循環(huán)是否結(jié)束輸出譯碼結(jié)果NY自適應(yīng)算術(shù)編碼和譯碼流程圖:靜態(tài)算術(shù)編碼和譯碼流程圖開始編碼判斷讀入的字符分配在哪個區(qū)間循環(huán)是否結(jié)束輸出結(jié)果NY開始譯碼比較該數(shù)據(jù)在哪個區(qū)間循環(huán)是否結(jié)束輸出結(jié)果NY在算術(shù)編碼中需要注意的幾個問題：由于實(shí)際的計(jì)算機(jī)的精度不可能無限長，只能取一定的有效位，或者運(yùn)算中出現(xiàn)溢出，丟失數(shù)據(jù)，但多數(shù)機(jī)器都有16位、32位或者64位的精度，因此這個問題可使用比例縮放方法解決，當(dāng)然取精度誤差也是難免的。算術(shù)編碼器對整個消息只產(chǎn)生一個碼字，這個碼字是在間隔[0,1)中的一個實(shí)數(shù)，因此譯碼器在接受到表示這個實(shí)數(shù)的所有