基于算術(shù)編碼的信源編碼解碼系統(tǒng)設(shè)計(jì)與仿真(共26頁)

1、*實(shí)踐(shjin)教學(xué)* XXXX大學(xué)(dxu)計(jì)算機(jī)與通信(tng xn)學(xué)院2014年春季學(xué)期 通信系統(tǒng)仿真訓(xùn)練 題 目：基于算術(shù)編碼的信源編碼/解碼系統(tǒng)設(shè)計(jì)與仿真 專業(yè)班級(jí)： XXXXXXXXXXXXXXX 姓 名： XXXXX 學(xué) 號(hào)： XXXXXXXX 指導(dǎo)教師： XXXXX 成 績(jī)： 摘 要隨著(su zhe)社會(huì)的飛速發(fā)展，數(shù)字化已經(jīng)成了現(xiàn)今通信技術(shù)的主流發(fā)展方向，而實(shí)現(xiàn)數(shù)字化的重要步驟就是對(duì)信源進(jìn)行編碼。信源編碼理論是信息論的一個(gè)重要分支，其理論基礎(chǔ)是信源編碼的兩個(gè)(lin )定理：無失真信源編碼定理和限失真信源編碼定理。信源編碼是以提高通信有效性為目的的編碼。通常通過壓縮信

2、源的冗余度來實(shí)現(xiàn)。人們經(jīng)過不斷地探索，創(chuàng)造了許多種有效的信源編碼的方法，比如說哈弗曼編碼、算術(shù)編碼、游程編碼等，通過這些有效地信源編碼方式，很好的提高了通信的有效性。 本文從算術(shù)編碼原理、以及研究算術(shù)編碼的目的意義等，到具體算術(shù)編碼方案的分析比較以及其 MATLAB 語言的實(shí)現(xiàn)方案，有重點(diǎn)的對(duì)算術(shù)編碼的編碼過程進(jìn)行了分析和闡述。具體說就是針對(duì)信源輸出符號(hào)序列的統(tǒng)計(jì)特性，尋找(xnzho)一定的方法把信源輸出符號(hào)序列變換為最短碼字的序列的方法。設(shè)計(jì)利用MATLAB語言設(shè)計(jì)并實(shí)現(xiàn)了基于算術(shù)編碼的信源編碼/解碼過程。算術(shù)編碼是一種能夠趨近于熵極限的最佳編碼方式對(duì)出現(xiàn)概率較大的符號(hào)使用短碼，對(duì)概率較小

3、的符號(hào)使用長(zhǎng)碼。過本課程設(shè)計(jì)可以實(shí)現(xiàn)從鍵盤隨意輸入待傳輸信息，根據(jù)算術(shù)編碼原理輸出編碼結(jié)果，如果選擇譯碼，會(huì)輸出之前輸入的傳輸信息。關(guān)鍵詞 ： 算術(shù)編碼 譯碼 MATLAB仿真目 錄 TOC o 1-3 h z u HYPERLINK l _Toc390438510 一、信源編碼(bin m) 信源編碼(bin m)1.1 信源編碼(bin m)的概念 信源編碼是為了減少信源輸出符號(hào)序列中的剩余度、提高符號(hào)的平均信息量，對(duì)信源輸出的符號(hào)序列所施行的變換。具體說，就是針對(duì)信源輸出符號(hào)序列的統(tǒng)計(jì)特性來尋找某種方法，把信源輸出符號(hào)序列變換為最短的碼字序列，使后者的各碼元所載荷的平均信息量最大，同時(shí)又

4、能保證無失真地恢復(fù)原來的符號(hào)序列。既然信源編碼的基本目的是提高碼字序列中碼元的平均信息量，那么，一切旨在減少剩余度而對(duì)信源輸出符號(hào)序列所施行的變換或處理，都可以在這種意義下歸入信源編碼的范疇，例如(lr)過濾、預(yù)測(cè)、域變換和數(shù)據(jù)壓縮等。當(dāng)然，這些都是廣義的信源編碼。 1.2 信源編碼簡(jiǎn)介 信源編碼是以提高通信有效性為目的的編碼。通常通過壓縮信源的冗余度來實(shí)現(xiàn)。采用的一般方法是壓縮每個(gè)信源符號(hào)的平均比特?cái)?shù)或信源的碼率，同樣多的信息用較少的碼率來傳輸，使單位時(shí)間內(nèi)傳送的平均信息來量增加，從而提高通信的有效性。信源編碼理論是信息論的一個(gè)重要分支，其理論基礎(chǔ)是信源編碼的兩個(gè)定理：無失真信源編碼定理和限

5、失真信源編碼定理。前者是離散信源或數(shù)字編碼的基礎(chǔ)，后者則是連續(xù)信源或模擬信號(hào)的基礎(chǔ)。編碼實(shí)質(zhì)上就是對(duì)信源的原始符號(hào)按一定規(guī)則進(jìn)行的一種變換。編碼可分為信源編碼和信道編碼。由于信源符號(hào)之間存在分布不均勻和相關(guān)性，使得信源存在冗余度，信源編碼的主要任務(wù)就是減少冗余，提高編碼效率。信源編碼是為了減少信源輸出符號(hào)序列中的剩余度、提高符號(hào)的平均信息量，對(duì)信源輸出的符號(hào)序列所施行的變換。具體說，就是針對(duì)信源輸出符號(hào)序列的統(tǒng)計(jì)特性來尋找某種方法，把信源輸出符號(hào)序列變換為最短的碼字序列，使后者的各碼元所載荷的平均信息量最大，同時(shí)又能保證無失真地恢復(fù)原來的符號(hào)序列。信源編碼的基本途徑有兩個(gè)：使序列中的各個(gè)符號(hào)盡

6、可能地相互獨(dú)立，即解除相關(guān)性；使編碼中各個(gè)符號(hào)出現(xiàn)的概率盡可能地相等，即概率均勻化。采用的一般方法是壓縮每個(gè)信源符號(hào)的平均比特?cái)?shù)或信源的碼率。即同樣多的信息用較少的碼率傳送,使單位時(shí)間內(nèi)傳送的平均信息量增加,從而提高通信的有效性。1.3信源編碼(bin m)的目的：1、信源存在(cnzi)冗余度。2、原因(yunyn)是信源符號(hào)之間存在概率分布不均勻和相關(guān)性。3、信源編碼的主要任務(wù)就是減少冗余，提高編碼效率。4、信源編碼是以提高通信的有效性為目的編碼。5、通常通過壓縮信源的冗余度來實(shí)現(xiàn)。6、即用較少的碼字傳送較多的信息，使單位時(shí)間內(nèi)傳送的平均信息量增加，從而提高通信的有效性。1.4信源編碼的原

7、理一般來說，減少信源輸出符號(hào)序列中的剩余度、提高符號(hào)平均信息量的基本途徑有兩個(gè)：使序列中的各個(gè)符號(hào)盡可能地互相獨(dú)立；使序列中各個(gè)符號(hào)的出現(xiàn)概率盡可能地相等。前者稱為解除相關(guān)性，后者稱為概率均勻化。信源編碼的一般問題可以表述如下：若某信源的輸出為長(zhǎng)度等于M的符號(hào)序列集合式中符號(hào)A為信源符號(hào)表，它包含著K個(gè)不同的符號(hào)，A=k|k=1,K，這個(gè)信源至多可以輸出K個(gè)不同的符號(hào)序列。記U=K。所謂對(duì)這個(gè)信源的輸出進(jìn)行編碼，就是用一個(gè)新的符號(hào)表B的符號(hào)序列集合V來表示信源輸出的符號(hào)序列集合U。若V的各個(gè)序列的長(zhǎng)度等于 N，即式中新的符號(hào)表B共含L個(gè)符號(hào)，B=bl|l=1,L。它總共可以編出L個(gè)不同的碼字。

8、類似地,記VL。為了使信源的每個(gè)輸出符號(hào)序列都能分配到一個(gè)獨(dú)特的碼字與之對(duì)應(yīng)，至少應(yīng)滿足關(guān)系 VLUK，或者 N/MlogK/logL；假若編碼符號(hào)表B的符號(hào)數(shù)L與信源符號(hào)表A的符號(hào)數(shù)K相等，則編碼后的碼字序列的長(zhǎng)度N必須大于或等于信源輸出符號(hào)序列的長(zhǎng)度M；反之，若有NM，則必須有LK。只有滿足這些條件，才能保證無差錯(cuò)地還原出原來的信源輸出符號(hào)序列(稱為碼字的唯一可譯性)?？墒牵谶@些條件下，碼字序列的每個(gè)碼元所載荷的平均信息量不但不能高于，反而會(huì)低于信源輸出序列的每個(gè)符號(hào)所載荷的平均信息量。這與編碼的基本目標(biāo)是直接相矛盾的。下面的幾個(gè)編碼定理，提供了解決這個(gè)矛盾的方法。它們既能改善信息載荷效

9、率，又能保證碼字唯一可譯。離散(lsn)無記憶信源的定長(zhǎng)編碼定理對(duì)于任意給定的0，只要滿足條件 N/M(H(U)+)/logL那么(n me),當(dāng)M足夠大時(shí),上述編碼幾乎沒有失真;反之,若這個(gè)條件不滿足，就不可能實(shí)現(xiàn)無失真的編碼。式中H(U)是信源輸出序列的符號(hào)熵。通常,信源的符號(hào)熵H(U)logK，因此(ync),上述條件還可以表示為 【H(U)+】/logLN/MlogK/logL特別,若有KL,那么,只要H(U)logK,就可能有NM，從而提高信息載荷的效率。由上面這個(gè)條件可以看出，H(U)離logK越遠(yuǎn),通過編碼所能獲得的效率改善就越顯著。實(shí)質(zhì)上，定長(zhǎng)編碼方法提高信息載荷能力的關(guān)鍵是利

10、用了漸近等分性,通過選擇足夠大的M,把本來各個(gè)符號(hào)概率不等因而H(U)logK的信源輸出符號(hào)序列變換為概率均勻的典型序列，而碼字的唯一可譯性則由碼字的定長(zhǎng)性來解決。離散無記憶信源的變長(zhǎng)編碼定理變長(zhǎng)編碼是指V的各個(gè)碼字的長(zhǎng)度不相等。只要V中各個(gè)碼字的長(zhǎng)度 Ni(i1，V)滿足克拉夫特不等式。這 V個(gè)碼字就能唯一地正確劃分和譯碼。離散無記憶信源的變長(zhǎng)編碼定理指出：若離散無記憶信源的輸出符號(hào)序列 ，式中 Ak|k=1,K,符號(hào)熵為H(U)，對(duì)U進(jìn)行唯一可譯的變長(zhǎng)編碼，編碼字母表B的符號(hào)數(shù)為L(zhǎng),即B=bl|l=1,L,那么必定存在一種編碼方法，使編出的碼字Vi(vi1,viNi)，(i=1,V)，具有

11、平均長(zhǎng)度嚻： MH(U)/logL嚻MH(U)/logL+1若L=K，則當(dāng)H(U)logKlogL時(shí),必有嚻M；H(U)離logK越遠(yuǎn)，則嚻越小于M。具體實(shí)現(xiàn)唯一可譯變長(zhǎng)編碼的方法很多，但比較經(jīng)典的方法還是仙農(nóng)編碼法、費(fèi)諾編碼法和霍夫曼編碼法。其他方法都是這些經(jīng)典方法的變形和發(fā)展。所有這些經(jīng)典編碼方法，都是通過以短碼來表示常出現(xiàn)的符號(hào)這個(gè)原則來實(shí)現(xiàn)概率的均勻化，從而得到高的信息載荷效率；同時(shí)，通過遵守克拉夫特不等式關(guān)系來實(shí)現(xiàn)碼字的唯一可譯?；舴蚵幋a方法的具體過程是：首先把信源的各個(gè)輸出符號(hào)序列按概率遞降的順序排列起來，求其中概率最小的兩個(gè)序列的概率之和，并把這個(gè)概率之和看作是一個(gè)符號(hào)序列的概

12、率，再與其他序列依概率遞降順序排列（參與求概率之和的這兩個(gè)序列不再出現(xiàn)在新的排列之中），然后，對(duì)參與概率求和的兩個(gè)符號(hào)序列分別賦予二進(jìn)制數(shù)字0和1。繼續(xù)這樣的操作,直到剩下一個(gè)以1為概率的符號(hào)序列。最后，按照與編碼過程相反的順序讀出各個(gè)符號(hào)序列所對(duì)應(yīng)的二進(jìn)制數(shù)字組，就可分別得到各該符號(hào)序列的碼字。例如，某個(gè)離散無記憶信源的輸出(shch)符號(hào)序列及其對(duì)應(yīng)的概率分布為對(duì)這些輸出符號(hào)序列(xli)進(jìn)行霍夫曼編碼的具體步驟和結(jié)果如表。表1-1由表中可以看出，在碼字序列中碼元0和1的概率分別(fnbi)為10/21和11/21，二者近乎相等，實(shí)現(xiàn)了概率的均勻化。同時(shí)，由于碼字序列長(zhǎng)度滿足克拉夫特不等式

13、 22+32+221因而碼字是唯一可譯的，不會(huì)在長(zhǎng)的碼字序列中出現(xiàn)劃錯(cuò)碼字的情況。以上幾個(gè)編碼定理，在有記憶信源或連續(xù)信源的情形也有相應(yīng)的類似結(jié)果。在實(shí)際工程應(yīng)用中，往往并不追求無差錯(cuò)的信源編碼和譯碼，而是事先規(guī)定一個(gè)譯碼差錯(cuò)率的容許值，只要實(shí)際的譯碼差錯(cuò)率不超過這個(gè)容許值即認(rèn)為滿意（見信息率-失真理論和多用戶信源編碼）。針對(duì)信源輸出符號(hào)序列的統(tǒng)計(jì)特性，尋找一定的方法把信源輸出符號(hào)序列變換為最短的碼字序列。1、解除相關(guān)性：使序列中的各個(gè)符號(hào)盡可能地互相獨(dú)立。2、概率均勻化：使編碼中各個(gè)符號(hào)出現(xiàn)的概率盡可能地相等。信源編碼的實(shí)現(xiàn)方法：離散信源編碼有香農(nóng)編碼、費(fèi)諾編碼、赫夫曼編碼、游程(yu ch

14、n)編碼、冗余位編碼；連續(xù)信源編碼有最佳標(biāo)量量化、矢量量化；相關(guān)信源編碼的預(yù)測(cè)編碼、差值編碼；變換編碼的子帶編碼、小波變換。 一般來說，減少信源輸出符號(hào)序列中的剩余度、提高(t go)符號(hào)平均信息量的基本途徑有兩個(gè)： 一是使序列中的各個(gè)符號(hào)盡可能地互相獨(dú)立；二是使序列中各個(gè)符號(hào)(fho)的出現(xiàn)概率盡可能地相等。前者稱為解除相關(guān)性，后者稱為概率均勻化。信源編碼的一般問題可以表述如下：若某信源的輸出為長(zhǎng)度等于M的符號(hào)序列集合式中符號(hào)A為信源符號(hào)表，它包含著K個(gè)不同的符號(hào)，A=k|k=1,K，這個(gè)信源至多可以輸出K個(gè)不同的符號(hào)序列。記U=K。所謂對(duì)這個(gè)信源的輸出進(jìn)行編碼，就是用一個(gè)新的符號(hào)表B的符號(hào)

15、序列集合V來表示信源輸出的符號(hào)序列集合U。若V的各個(gè)序列的長(zhǎng)度等于 I，即式中新的符號(hào)表B共含L個(gè)符號(hào)，B=bl|l=1,L。它總共可以編出L個(gè)不同的碼字。類似地,記VL。為了使信源的每個(gè)輸出符號(hào)序列都能分配到一個(gè)獨(dú)特的碼字與之對(duì)應(yīng)，至少應(yīng)滿足關(guān)系 VLUK，或者 N/MlogK/logL；假若編碼符號(hào)表B的符號(hào)數(shù)L與信源符號(hào)表A的符號(hào)數(shù)K相等，則編碼后的碼字序列的長(zhǎng)度N必須大于或等于信源輸出符號(hào)序列的長(zhǎng)度M；反之，若有NM，則必須有LK。只有滿足這些條件，才能保證無差錯(cuò)地還原出原來的信源輸出符號(hào)序列(稱為碼字的唯一可譯性)?？墒?，在這些條件下，碼字序列的每個(gè)碼元所載荷的平均信息量不但不能高于

16、，反而會(huì)低于信源輸出序列的每個(gè)符號(hào)所載荷的平均信息量。這與編碼的基本目標(biāo)是直接相矛盾的。下面的幾個(gè)編碼定理，提供了解決這個(gè)矛盾的方法。它們既能改善信息載荷效率，又能保證碼字唯一可譯。(1)離散無記憶信源的定長(zhǎng)編碼定理對(duì)于任意給定的0，只要滿足條件 N/M(H(U)+)/logL那么(n me),當(dāng)M足夠大時(shí),上述編碼幾乎(jh)沒有失真;反之,若這個(gè)條件不滿足，就不可能實(shí)現(xiàn)無失真的編碼。式中H(U)是信源輸出序列(xli)的符號(hào)熵。通常,信源的符號(hào)熵H(U)logK，因此,上述條件還可以表示為 【H(U)+】/logLN/MlogK/logL。特別,若有KL,那么,只要H(U)logK,就可能

17、有NM，從而提高信息載荷的效率。由上面這個(gè)條件可以看出，H(U)離logK越遠(yuǎn),通過編碼所能獲得的效率改善就越顯著。實(shí)質(zhì)上，定長(zhǎng)編碼方法提高信息載荷能力的關(guān)鍵是利用了漸近等分性,通過選擇足夠大的M,把本來各個(gè)符號(hào)概率不等因而H(U)logK的信源輸出符號(hào)序列變換為概率均勻的典型序列，而碼字的唯一可譯性則由碼字的定長(zhǎng)性來解決。(2)離散無記憶信源的變長(zhǎng)編碼定理變長(zhǎng)編碼是指V的各個(gè)碼字的長(zhǎng)度不相等。只要V中各個(gè)碼字的長(zhǎng)度 Ni(i1，V)滿足克拉夫特不等式。這 V個(gè)碼字就能唯一地正確劃分和譯碼。離散無記憶信源的變長(zhǎng)編碼定理指出：若離散無記憶信源的輸出符號(hào)序列為 ， 式中 Ak|k=1,K,符號(hào)熵為

18、H(U)，對(duì)U進(jìn)行唯一可譯的變長(zhǎng)編碼，編碼字母表B的符號(hào)數(shù)為L(zhǎng),即B=bl|l=1,L,那么必定存在一種編碼方法，使編出的碼字Vi(vi1,viNi)，(i=1,V)，具有平均長(zhǎng)度嚻： MH(U)/logL嚻MH(U)/logL+1；若L=K，則當(dāng)H(U)logKlogL時(shí),必有嚻M；H(U)離logK越遠(yuǎn)，則嚻越小于M。具體實(shí)現(xiàn)唯一可譯變長(zhǎng)編碼的方法很多，但比較經(jīng)典的方法還是仙農(nóng)編碼法、費(fèi)諾編碼法和霍夫曼編碼法。其他方法都是這些經(jīng)典方法的變形和發(fā)展。所有這些經(jīng)典編碼方法，都是通過以短碼來表示常出現(xiàn)的符號(hào)這個(gè)原則來實(shí)現(xiàn)概率的均勻化，從而得到高的信息載荷效率；同時(shí)，通過遵守克拉夫特不等式關(guān)系來實(shí)

19、現(xiàn)碼字的唯一可譯。編碼的逆過程，利用不同編碼方法實(shí)現(xiàn)的生成的碼字通過其相應(yīng)方法實(shí)現(xiàn)對(duì)碼字的譯碼，還原出從信源輸入的信息。進(jìn)行編碼是為了壓縮信源符號(hào)的冗余度，在傳輸、譯碼后，還能恢復(fù)出原始信息。二、 算術(shù)解碼(jim)的理論基礎(chǔ) 2.1 算術(shù)編碼(bin m)算法的基本原理算術(shù)編碼是一種無失真的編碼方法，能有效地壓縮信源冗余度，使編成的碼率趨于信的熵 ，它是無損壓縮的一種。算術(shù)編碼的基本原理是：根據(jù)信源可能發(fā)現(xiàn)的不同符號(hào)序列的概率，把 0 ，1) 區(qū)間劃分為互不重疊的子區(qū)間，子區(qū)間的寬度恰好是各符號(hào)序列概率 。 這樣信源發(fā)出的不同符號(hào)序列將與各子區(qū)間一一對(duì)應(yīng) ， 因此每個(gè)子區(qū)間內(nèi)的任意個(gè)實(shí)數(shù)都可

20、以用來表示對(duì)應(yīng)的符號(hào)序列，這個(gè)數(shù)就是該符號(hào)序列所對(duì)應(yīng)的碼字。顯然 ，串符號(hào)序列發(fā)生的概率越大，對(duì)應(yīng)的子區(qū)間就越寬，要表達(dá)它所用的比特?cái)?shù)就減少(jinsho)，因相應(yīng)的碼字就越短。算術(shù)編碼可以是靜態(tài)的或者自適應(yīng)的。在靜態(tài)算術(shù)編碼中，信源符號(hào)的概率是固定的 。本課程設(shè)計(jì)中以靜態(tài)算術(shù)編碼算法進(jìn)行仿真。在自適應(yīng)算術(shù)編碼中，自適應(yīng)算術(shù)編碼在對(duì)符號(hào)序列進(jìn)行掃描的過程中，可一次完成兩個(gè)過程，即根據(jù)恰當(dāng)?shù)母怕使烙?jì)模型和當(dāng)前符號(hào)序列中各符號(hào)出現(xiàn)的頻率，自適應(yīng)地調(diào)整各符號(hào)的概率估計(jì)值，同時(shí)完成編碼。信源符號(hào)的概率根據(jù)編碼時(shí)符號(hào)出現(xiàn)的頻繁程度動(dòng)態(tài)地進(jìn)行修改，在編碼期間估算信源符號(hào)概率的過程叫做建模。需要開發(fā)態(tài)算術(shù)編

21、碼的原因是因?yàn)槭孪戎谰_的信源概率是很難的，而且是不切實(shí)際的。當(dāng)壓縮消息時(shí)，我們不能期待一個(gè)算術(shù)編碼器獲得最大的效率， 所能做的最有效的方法是在編碼過程中估算概率。盡管從編碼效率上看不如已知概率表的情況，但正是由于算術(shù)編碼自適應(yīng)的調(diào)整對(duì)個(gè)符號(hào)概率的估計(jì)值，這點(diǎn)比哈弗曼編碼相比，具有實(shí)時(shí)性好 、 靈活性高 、 適應(yīng)性強(qiáng)等特點(diǎn)，在圖像壓縮、視頻圖像編碼等領(lǐng)域都得到了廣泛的應(yīng)用。2.2算術(shù)編碼的特點(diǎn)算術(shù)編碼的優(yōu)點(diǎn)：（1）不必預(yù)先定義概率模型，自適應(yīng)模式具有獨(dú)特的優(yōu)點(diǎn)；（2）信源符號(hào)概率接近時(shí)，建議使用算術(shù)編碼，這種情況下其效率高于霍夫曼編碼；（3）算術(shù)編碼繞過了用一個(gè)特定的代碼替代一個(gè)輸入符號(hào)的想

22、法，用一個(gè)浮點(diǎn)輸出數(shù)值代替一個(gè)流的輸入符號(hào)，較長(zhǎng)的復(fù)雜的消息(xio xi)輸出的數(shù)值中就需要更多的位數(shù)；（4）算術(shù)編碼實(shí)現(xiàn)方法復(fù)雜一些，但 JPEG 成員(chngyun)對(duì)多幅圖像的測(cè)試結(jié)果表明，算術(shù)編碼比霍夫曼編碼提高了 10%左右的效率，因此在 JPEG 擴(kuò)展系統(tǒng)中用算術(shù)編碼取代霍夫曼編碼。算術(shù)編碼雖然具有其獨(dú)特的優(yōu)點(diǎn)，但我們?nèi)孕枰⒁庀旅鎺讉€(gè)(j )問題：（1）由于實(shí)際的計(jì)算機(jī)的精度不可能無限長(zhǎng)，運(yùn)算中出現(xiàn)溢出是一個(gè)明顯的問題，但多數(shù)機(jī)器都有 16 位、32 位或者 64 位的精度，因此這個(gè)問題可使用比例縮放方法解決。（2）算術(shù)編碼器對(duì)整個(gè)消息只產(chǎn)生一個(gè)碼字，這個(gè)碼字是在間隔0, 1

23、)中的一個(gè)實(shí)數(shù)，因此譯碼器在接受到表示這個(gè)實(shí)數(shù)的所有位之前不能進(jìn)行譯碼。（3）算術(shù)編碼也是一種對(duì)錯(cuò)誤很敏感的編碼方法，如果有一位發(fā)生錯(cuò)誤就會(huì)導(dǎo)致整個(gè)消息譯錯(cuò)。算術(shù)編碼隨著序列長(zhǎng)度的增加，相應(yīng)子區(qū)間的寬度也不斷縮小，要表示這段子區(qū)間所需精度，直觀地說就是比特?cái)?shù)也不斷增加。這不但要占用相當(dāng)大的存儲(chǔ)空間，還增加了編碼延時(shí)，這對(duì)實(shí)時(shí)系統(tǒng)是十分不利的。為了解決這些難點(diǎn)，針對(duì)不同的應(yīng)用方向，人們對(duì)傳統(tǒng)的算術(shù)編碼方法進(jìn)行了改進(jìn)，在保證足夠精度的前提下，提高了編碼速度?；谒阈g(shù)編碼算法人們提出了二進(jìn)制自適應(yīng)的算術(shù)編碼以及 MQ 算術(shù)編碼器，分別在軟件及上提高編碼的效率。2.3 算術(shù)編碼的分析過程在算術(shù)編碼中，

24、消息用0到1之間的實(shí)數(shù)進(jìn)行編碼，算術(shù)編碼用到兩個(gè)基本的參數(shù)：符號(hào)的概率和它的編碼間隔。信源符號(hào)的概率決定壓縮編碼的效率，也決定編碼過程中信源符號(hào)的間隔，而這些間隔包含在 0到1之間。編碼過程中的間隔決定了符號(hào)壓縮后的輸出。算術(shù)編碼的過程，實(shí)際上就是依據(jù)信源符號(hào)的發(fā)生概率對(duì)碼區(qū)間分割的過程。算術(shù)編碼的編碼分析框圖如下：圖2.1 算術(shù)(sunsh)編碼的編碼分析框圖靜態(tài)算術(shù)編碼和自適應(yīng)型算術(shù)編碼在編碼前都需要初始化概率空間，靜態(tài)算術(shù)編碼的字符概率是固定的，因此找到相應(yīng)的概率空間可直接(zhji)按區(qū)間分割進(jìn)行編碼；自適應(yīng)型算術(shù)編碼在編碼前需要統(tǒng)計(jì)輸入的文本信息的符號(hào)類型和每個(gè)符號(hào)的個(gè)數(shù)，期初假定每

25、個(gè)符號(hào)概率相等，然后輸入一個(gè)符號(hào)后，找到相應(yīng)的概率空間所有的符號(hào)概率會(huì)進(jìn)行更新，然后依次規(guī)律對(duì)輸入信息進(jìn)行編碼。圖2.2 算術(shù)(sunsh)編碼的譯碼分析框圖 讀取編碼結(jié)果，找到所屬區(qū)間范圍從而譯出碼字。靜態(tài)型算術(shù)編碼的編碼值是變化的然后找所對(duì)應(yīng)的區(qū)間；自適應(yīng)型算術(shù)編碼的編碼值是不變的，只需改變概率區(qū)間，然后用此編碼值找到所對(duì)應(yīng)的區(qū)間，從而譯出碼字。2.4算術(shù)編碼舉例（1） 靜態(tài)算術(shù)編碼舉例 假設(shè)一則消息“static_tree”具有如下的概率分布： 字符(z f) 概率(gil) _ 0.1 a 0.1 e 0.3 r 0.1 s 0.1 t 0.3 下面用算術(shù)(sunsh)編碼方法給該消息

26、編碼。 一旦字符的概率已知，就沿著“概率線”為每一個(gè)單獨(dú)的符號(hào)設(shè)定一個(gè)范圍，哪一個(gè)被設(shè)定到哪一段范圍并不重要，只要編碼和解碼都以同樣方式進(jìn)行就可以，這里所用的6個(gè)字符被分配的范圍（range）如下： 字符 概率 范圍 _ 0.1 0r0.1 a 0.1 0.1r0.2 e 0.3 0.2r0.5 r 0.1 0.5r0.6 s 0.1 0.6r0.7 t 0.3 0.7r0.6,0.7） (3)對(duì)第二個(gè)字符t編碼，使用的新生范圍為0.6,0.7），因?yàn)閠的range low=0.7,range high=1.0,因此下一個(gè)low,high分別為 Low=0.6+0.10.70.67 High=

27、0.6+0.11.00.70 Range=0.7-0.67=0.03 t將0.6,0.7）=0.67,0.70） (4)對(duì)第三個(gè)字符a編碼，在新生成的0.67,0.70）中進(jìn)行分割，因?yàn)閍的range low=0.10,range high=0.2,因此下一個(gè)low,high分別為 Low=0.67+0.030.10.673 High=0.67+0.030.20.676 Range=0.676-0.673=0.003 a將0.67,0.70）=0.673,0.676） (5)對(duì)第四個(gè)字符t編碼，在新生成的0.673,0.676）上進(jìn)行分割。因?yàn)閠的range low=0.70,range hi

28、gh=1.0,則下一個(gè)low,high分別為 Low=0.673+0.0030.70.6751 High=0.673+0.0031.00.676 Range=0.0009 t將0.673,0.676）=0.6751,0.676） 同理得到下面各字符e,s,t,r,e,e編碼所得到的范圍分別為0.67528,0.67555)，0.67528,0.675307),0.6752989,0.675307),0.67530295,0.67530376),0.675303112,0.675303355），0.6753031606,0.6753032335）,0.6753031824,0.675303233

29、5）。最后選取最后區(qū)間的中點(diǎn)作為編碼的輸出結(jié)果0.6753032079。 通過編碼(bin m)，最后的下界值0.6753032079就是(jish)消息“state_tree”的唯一編碼。然后解碼過判斷哪一個(gè)符號(hào)(fho)能擁有我們已編碼的消息落在的空間來找出消息中的第一個(gè)符號(hào)。由于0.6753032079落在0.6,0.7）之間，因此可解得第一個(gè)符號(hào)是s。在解出s后，由于我們知道s的范圍的上界和下界，利用編碼的逆作用，首先去掉s的下界值0.6，得0.075 3032079，然后用s的范圍range=0.1去除所得到的0.075 3032079，即得到0.75 3032079，接著找出它所在

30、的區(qū)間，就是t的原來范圍0.7,1.0）。去掉t的下界值0.7，得0.05 3032079，然后用t的range=0.3除該數(shù)得出0.176 772 02，該值所屬范圍就是字符a如此操作下去便得到消息的準(zhǔn)確譯碼綜述，可以得到解碼公式為：(Number-range low)/range=number其中，number為符串的編碼。算術(shù)編碼(bin m)舉例 在編碼之前，假設(shè)(jish)每個(gè)信源符號(hào)的頻率相等（如都等于1），并計(jì)算累積頻率從輸入流中讀入一個(gè)字符(z f)，并對(duì)該符號(hào)進(jìn)行算術(shù)編碼；更新該符號(hào)的頻率，并更新累積頻率；由于在解碼之前，解碼器不知道是哪個(gè)信源符號(hào)，所以概率更新應(yīng)該在解碼之后

31、進(jìn)行對(duì)應(yīng)的，編碼器也應(yīng)在編碼后進(jìn)行概率更新。 設(shè)某信源可能發(fā)出三種符號(hào)a，b，c，對(duì)符號(hào)序列bccb進(jìn)行自適應(yīng)算術(shù)編碼： 初始時(shí)刻，我們對(duì)a，b，c，三者出現(xiàn)的概率一無所知（即采用自適應(yīng)模型），認(rèn)為三者出現(xiàn)的概率相等，暫時(shí)都為1/3，頻率都為1，則累積頻率為3。將區(qū)間0,1)按概率分布劃分給三個(gè)字符，如下圖所示： 向編碼器輸入第一個(gè)字符b，落入?yún)^(qū)間0.3333,0.6667)。此時(shí)b的頻率增加了1變?yōu)?，累積頻率也增加了1變?yōu)?；概率分布更新為： 再輸入字符c，落入?yún)^(qū)間0.5834,0.6667)。此時(shí)c的頻率增加了1變?yōu)?，累積頻率也增加了1變?yōu)?；概率分布更新為：接著輸入第三個(gè)字符c，落入

32、區(qū)間(q jin)0.6334,0.6667)。此時(shí)c的頻率又增加了1變?yōu)?，累積頻率也又增加了1變?yōu)?；概率分布更新為：最后輸入字符b，鎖定區(qū)間0.6390,0.6501)，然后在這個(gè)區(qū)間內(nèi)任意選擇(xunz)一個(gè)實(shí)數(shù)，例如0.64，再將其轉(zhuǎn)化為二進(jìn)制數(shù)l位（連續(xù)乘以2取整）。 即輸出8位。最后的編碼(bin m)結(jié)果為：11011011。譯碼過程和編碼過程類似：設(shè)信源符號(hào)a，b，c的原概率皆為1/3。a. 11011011B=0.64D，落入?yún)^(qū)間0.3333,0.6667)，所以譯碼器譯為b，概率分布更新為：b. 0.64落入?yún)^(qū)間(q jin)0.5834,0.6667)，譯為c，概率分布

33、更新為：c. 0.64落入?yún)^(qū)間(q jin)0.6334,0.6667)，譯為c，概率分布更新為： d. 0.64落入?yún)^(qū)間(q jin)0.6501,0.6667)，譯為b。如果有停止位或者定長(zhǎng)，則譯碼結(jié)束，譯出的原序列為：bccb。一旦字符的概率已知，就沿著“概率線”為每一個(gè)單獨(dú)的符號(hào)設(shè)定一個(gè)范圍，哪一個(gè)被設(shè)定到哪一段范圍并不重要，只要編碼和解碼都以同樣方式進(jìn)行就可以。離散信源編碼有香農(nóng)編碼、費(fèi)諾編碼、赫夫曼編碼、游程編碼、冗余位編碼；連續(xù)信源編碼有最佳標(biāo)量量化、矢量量化；相關(guān)信源編碼的預(yù)測(cè)編碼、差值編碼；變換編碼的子帶編碼、小波變換。本章主要舉例說明了算術(shù)編碼的基本原理，讓讀者能夠理解算術(shù)

34、編碼的基本應(yīng)用方法。三、 算術(shù)編碼MATLAB仿真(fn zhn)實(shí)現(xiàn) 3.1 MATLAB 仿真(fn zhn)程序?qū)崿F(xiàn) MATLAB是由美國(guó) mathworks 公司發(fā)布的主要面對(duì)(min du)科學(xué)計(jì)算、可視化以及交互式程序設(shè)計(jì)的高科技計(jì)算環(huán)境。它將數(shù)值分析、矩陣計(jì)算、科學(xué)數(shù)據(jù)可視化以及非線性動(dòng)態(tài)系統(tǒng)的建模和仿真等諸多強(qiáng)大功能集成在一個(gè)易于使用的視窗環(huán)境中，為科學(xué)研究、工程設(shè)計(jì)以及必須進(jìn)行有效數(shù)值計(jì)算的眾多科學(xué)領(lǐng)域提供了一種全面的解決方案，并在很大程度上擺脫了傳統(tǒng)非交互式 程序設(shè)計(jì)語言（ 如 C、Fortran） 的編輯模式，代表了當(dāng)今國(guó)際科學(xué)計(jì)算軟件的先進(jìn)水平。 MATLAB 由一系列

35、工具組成。這些工具方便用戶使用 MATLAB的函數(shù)和文件，其中許多工具采用的是圖形用戶界面。包括 MATLAB 桌面和命令窗口、歷史命令窗口、編輯器和調(diào)試器、路徑搜索和用于用戶瀏覽幫助、工作空間 、文件的瀏覽器。隨著 MATLAB 的商業(yè)化以及軟件本身的不斷升級(jí)，MATLAB 的用戶界面也越來越精致，更加接近 Windows 的標(biāo)準(zhǔn)界面，人機(jī)交互性更強(qiáng)，操作更簡(jiǎn)單。而且新版本的 MATLAB 提供了完整的聯(lián)機(jī)查詢、幫助系統(tǒng)，極大的方便了用戶的使用。簡(jiǎn)單的編程環(huán)境提供了比較完備的調(diào)試系統(tǒng)，程序不必經(jīng)過編譯就可以直接運(yùn)行，而且能夠及時(shí)地報(bào)告出現(xiàn)的錯(cuò)誤及進(jìn)行出錯(cuò)原因分析。 MATLAB7. 1 版本

36、是在 2005 年更新的，本文主要應(yīng)用 MATLAB7. 1 中發(fā)布的影像處理工具箱中的相關(guān)函數(shù)和命令來實(shí)現(xiàn)基于算術(shù)編碼實(shí)現(xiàn)圖像壓縮理論算法的仿真。MATLAB7. 1是一套功能十分強(qiáng)大的工程計(jì)算及數(shù)據(jù)分析應(yīng)用軟件,廣泛應(yīng)用于工業(yè)、電子、控制、信號(hào)及圖像處理等各領(lǐng)域。MATLAB7. 1 本身除了提供強(qiáng)大的圖形繪制和輸出功能外 ,同時(shí)還發(fā)布了影像處理工具箱(Image Processing Toolbox),專門用于圖像的處理.在通常情況下，可以用它來代替底層編程語言，如 C 和 C+。在計(jì)算要求相同的情況下，使用 MATLAB 的編程工作量會(huì)大大減少。 3.2仿真設(shè)計(jì)流程圖 本課程設(shè)計(jì)的軟件

37、算術(shù)編碼輸入的自符類型固定，每個(gè)字符的概率也是固定的。輸入的自符類型有“abcdef”每次輸入字符，更新字符的起始、終止區(qū)間。等最后一個(gè)字符編碼完成后，取起始值和終至值的中點(diǎn)作為編碼的結(jié)果輸出。譯碼的時(shí)候，讀取編碼的輸出結(jié)果，找到所在的區(qū)間，依次譯出編碼前輸入的字符信息。完成譯碼過程；自適應(yīng)算術(shù)編碼的概率模型不固定，先統(tǒng)計(jì)編碼的符號(hào)類型，以及每個(gè)符號(hào)的個(gè)數(shù)。譯碼前，假設(shè)每個(gè)符號(hào)的概率是相等的，然后每次輸入一個(gè)字符，相應(yīng)的字符概率發(fā)生變化，直至編出最后一個(gè)碼字，選取區(qū)間中間結(jié)果作為編碼的輸出，譯碼時(shí)，讀取中間結(jié)果，找到所屬概率區(qū)間，譯出碼字，然后變更概率區(qū)間，重新定位碼字。直至譯出最后一個(gè)碼字。

38、 圖3.1算術(shù)(sunsh)編碼設(shè)計(jì)流程圖 上圖是算術(shù)編碼設(shè)計(jì)流程圖，無論是靜態(tài)型還是自適應(yīng)型算術(shù)編碼在編碼前都要初始化概率空間，但二者在編碼時(shí)的概率空間卻不一樣，前者固定不變，后者概率隨輸入字符變化而變化。然后進(jìn)行區(qū)間分割，將字符串編成一個(gè)浮點(diǎn)小數(shù)，然后轉(zhuǎn)化為二進(jìn)制，作為(zuwi)結(jié)果之后選擇是否譯碼，確定是否譯出信源符號(hào)。3.3 算術(shù)編碼仿真(fn zhn)設(shè)計(jì)、顯示(xinsh)主界面程序段menu=. 請(qǐng)按下列(xili)要求輸入字符串：1、字符串長(zhǎng)度適宜； 2、可以輸入的字符僅限于：a,b,c,d,e,f ；3、輸入的字符一定要用英文狀態(tài)下的單引號(hào)引起來,例如：efbfcafdcc

39、。; disp(%) disp(menu) disp(%) 圖3.2算術(shù)編碼仿真主界面 上圖顯示的是靜態(tài)型算術(shù)編碼的主界面，按要求輸入字符串，例如abcdef。由于在轉(zhuǎn)化為二進(jìn)制時(shí)受限于字長(zhǎng)，因此輸入的字符串長(zhǎng)度要適宜。（2）編碼程序段for i=1:k %開始算術(shù)編碼if i=1 %為字符串的第一個(gè)字符編碼，a1,a2分別表示個(gè)字符串區(qū)間的端點(diǎn)switch 1 %用“開關(guān)(kigun)語句”檢測(cè)是什么(shn me)字符，在做相應(yīng)的編碼處理case string_s(i)=a a1=0; a2=0+pa; case string_s(i)=ba1=pa; a2=pa+pb;case stri

40、ng_s(i)=c a1=pa+pb; a2=pa+pb+pc;case string_s(i)=da1=pa+pb+pc; a2=pa+pb+pc+pd; case string_s(i)=e a1=pa+pb+pc+pd; a2=pa+pb+pc+pd+pe; case string_s(i)=f a1=pa+pb+pc+pd+pe; a2=1;end l=a2-a1; %計(jì)算各字符串編碼區(qū)間(q jin)的長(zhǎng)度end if (i=2)&(i=1&i=k %譯碼對(duì)字符(z f)的確認(rèn)switch 1 case ym=1 bm0=(bm0-0)/pa;decode(i)=new_string

41、(1);case ym=2 bm0=(bm0-pa)/pb;decode(i)=new_string(2);case ym=3 bm0=(bm0-pa-pb)/pc;decode(i)=new_string(3);case ym=4bm0=(bm0-pa-pb-pc)/pd; decode(i)=new_string(4);case ym=5 bm0=(bm0-pa-pb-pc-pd)/pe;decode(i)=new_string(5);case ym=6bm0=(bm0-pa-pb-pc-pd-pe)/pf; decode(i)=new_string(6);end i=i+1; ym=YM

42、(bm0);%調(diào)用單個(gè)字符譯碼子程序YM對(duì)第二個(gè)碼元及以后各碼元譯碼end 圖3.4 算術(shù)編碼(bin m)譯碼仿真 上圖為算術(shù)(sunsh)編碼譯碼圖示，通過選擇是否譯碼，確定對(duì)編碼的碼字是否譯出。按1，則譯出編碼前輸入的信息，得到編碼的譯碼結(jié)果。3.4結(jié)果(ji gu)分析 基于算術(shù)編碼算法，運(yùn)行MATLAB 程序，算術(shù)編碼輸出結(jié)果為0.013706；輸入的字符經(jīng)過算術(shù)算法的解碼，輸出的符號(hào)串也是一致的，驗(yàn)證了算術(shù)編碼算法是一種無失真的熵編碼方式。 由于在編程中用到了bin2dec函數(shù)，它只能將不多于52為的二進(jìn)制數(shù)譯成整數(shù)，因此輸入的符號(hào)個(gè)數(shù)受到限制，否則后產(chǎn)生誤碼。由于輸入的信息過多時(shí)，會(huì)產(chǎn)生誤碼，因此可以通過增加二進(jìn)制位數(shù)來補(bǔ)償誤碼率問題，但二進(jìn)制位數(shù)前提是不多于52位。，我們知道算術(shù)編碼是一種無失