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

1、 PAGE22 / NUMPAGES25*實(shí)踐教學(xué)*計算機(jī)與通信學(xué)院 通信系統(tǒng)仿真訓(xùn)練 題 目：基于算術(shù)編碼的信源編碼/解碼系統(tǒng)設(shè)計與仿真 摘 要隨著社會的飛速發(fā)展，數(shù)字化已經(jīng)成了現(xiàn)今通信技術(shù)的主流發(fā)展方向，而實(shí)現(xiàn)數(shù)字化的重要步驟就是對信源進(jìn)行編碼。信源編碼理論是信息論的一個重要分支，其理論基礎(chǔ)是信源編碼的兩個定理：無失真信源編碼定理和限失真信源編碼定理。信源編碼是以提高通信有效性為目的的編碼。通常通過壓縮信源的冗余度來實(shí)現(xiàn)。人們經(jīng)過不斷地探索，創(chuàng)造了許多種有效的信源編碼的方法，比如說哈弗曼編碼、算術(shù)編碼、游程編碼等，通過這些有效地信源編碼方式，很好的提高了通信的有效性。本文從算術(shù)編碼原理、以

2、與研究算術(shù)編碼的目的意義等，到具體算術(shù)編碼方案的分析比較以與其 MATLAB 語言的實(shí)現(xiàn)方案，有重點(diǎn)的對算術(shù)編碼的編碼過程進(jìn)行了分析和闡述。具體說就是針對信源輸出符號序列的統(tǒng)計特性，尋找一定的方法把信源輸出符號序列變換為最短碼字的序列的方法。設(shè)計利用MATLAB語言設(shè)計并實(shí)現(xiàn)了基于算術(shù)編碼的信源編碼/解碼過程。算術(shù)編碼是一種能夠趨近于熵極限的最佳編碼方式對出現(xiàn)概率較大的符號使用短碼，對概率較小的符號使用長碼。過本課程設(shè)計可以實(shí)現(xiàn)從鍵盤隨意輸入待傳輸信息，根據(jù)算術(shù)編碼原理輸出編碼結(jié)果，如果選擇譯碼，會輸出之前輸入的傳輸信息。關(guān)鍵詞 ：算術(shù)編碼 譯碼 MATLAB仿真目 錄 TOC o 1-3 h

3、 z u HYPERLINK l _Toc390438510一、信源編碼 PAGEREF _Toc390438510 h 1HYPERLINK l _Toc3904385111.1 信源編碼的概念 PAGEREF _Toc390438511 h 1HYPERLINK l _Toc3904385121.2 信源編碼簡介 PAGEREF _Toc390438512 h 1HYPERLINK l _Toc3904385131.3信源編碼的目的： PAGEREF _Toc390438513 h 2HYPERLINK l _Toc3904385141.4信源編碼的原理 PAGEREF _Toc39043

4、8514 h 2HYPERLINK l _Toc390438515二、算術(shù)解碼的理論基礎(chǔ) PAGEREF _Toc390438515 h 7HYPERLINK l _Toc3904385162.1 算術(shù)編碼算法的基本原理 PAGEREF _Toc390438516 h 7HYPERLINK l _Toc3904385172.2算術(shù)編碼的特點(diǎn) PAGEREF _Toc390438517 h 7HYPERLINK l _Toc3904385182.3 算術(shù)編碼的分析過程 PAGEREF _Toc390438518 h 8HYPERLINK l _Toc3904385192.4算術(shù)編碼舉例 PAGE

5、REF _Toc390438519 h 9HYPERLINK l _Toc390438520三、算術(shù)編碼MATLAB仿真實(shí)現(xiàn) PAGEREF _Toc390438520 h 15HYPERLINK l _Toc3904385213.1 MATLAB 仿真程序?qū)崿F(xiàn) PAGEREF _Toc390438521 h 15HYPERLINK l _Toc3904385223.2仿真設(shè)計流程圖 PAGEREF _Toc390438522 h 15HYPERLINK l _Toc3904385233.3 算術(shù)編碼仿真設(shè)計 PAGEREF _Toc390438523 h 16HYPERLINK l _Toc

6、3904385243.4結(jié)果分析 PAGEREF _Toc390438524 h 21HYPERLINK l _Toc390438525設(shè)計總結(jié) PAGEREF _Toc390438525 h 21HYPERLINK l _Toc390438526參考文獻(xiàn) PAGEREF _Toc390438526 h 23信源編碼1.1 信源編碼的概念信源編碼是為了減少信源輸出符號序列中的剩余度、提高符號的平均信息量，對信源輸出的符號序列所施行的變換。具體說，就是針對信源輸出符號序列的統(tǒng)計特性來尋找某種方法，把信源輸出符號序列變換為最短的碼字序列，使后者的各碼元所載荷的平均信息量最大，同時又能保證無失真地恢

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

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

9、編碼中各個符號出現(xiàn)的概率盡可能地相等，即概率均勻化。采用的一般方法是壓縮每個信源符號的平均比特數(shù)或信源的碼率。即同樣多的信息用較少的碼率傳送,使單位時間傳送的平均信息量增加,從而提高通信的有效性。1.3信源編碼的目的：1、信源存在冗余度。2、原因是信源符號之間存在概率分布不均勻和相關(guān)性。3、信源編碼的主要任務(wù)就是減少冗余，提高編碼效率。4、信源編碼是以提高通信的有效性為目的編碼。5、通常通過壓縮信源的冗余度來實(shí)現(xiàn)。6、即用較少的碼字傳送較多的信息，使單位時間傳送的平均信息量增加，從而提高通信的有效性。1.4信源編碼的原理一般來說，減少信源輸出符號序列中的剩余度、提高符號平均信息量的基本途徑有兩

10、個：使序列中的各個符號盡可能地互相獨(dú)立；使序列中各個符號的出現(xiàn)概率盡可能地相等。前者稱為解除相關(guān)性，后者稱為概率均勻化。信源編碼的一般問題可以表述如下：若某信源的輸出為長度等于M的符號序列集合式中符號A為信源符號表，它包含著K個不同的符號，A=k|k=1,K，這個信源至多可以輸出K個不同的符號序列。記U=K。所謂對這個信源的輸出進(jìn)行編碼，就是用一個新的符號表B的符號序列集合V來表示信源輸出的符號序列集合U。若V的各個序列的長度等于 N，即式中新的符號表B共含L個符號，B=bl|l=1,L。它總共可以編出L個不同的碼字。類似地,記VL。為了使信源的每個輸出符號序列都能分配到一個獨(dú)特的碼字與之對應(yīng)

11、，至少應(yīng)滿足關(guān)系 VLUK，或者 N/MlogK/logL；假若編碼符號表B的符號數(shù)L與信源符號表A的符號數(shù)K相等，則編碼后的碼字序列的長度N必須大于或等于信源輸出符號序列的長度M；反之，若有NM，則必須有LK。只有滿足這些條件，才能保證無差錯地還原出原來的信源輸出符號序列(稱為碼字的唯一可譯性)。可是，在這些條件下，碼字序列的每個碼元所載荷的平均信息量不但不能高于，反而會低于信源輸出序列的每個符號所載荷的平均信息量。這與編碼的基本目標(biāo)是直接相矛盾的。下面的幾個編碼定理，提供了解決這個矛盾的方法。它們既能改善信息載荷效率，又能保證碼字唯一可譯。離散無記憶信源的定長編碼定理對于任意給定的0，只要

12、滿足條件 N/M(H(U)+)/logL那么,當(dāng)M足夠大時,上述編碼幾乎沒有失真;反之,若這個條件不滿足，就不可能實(shí)現(xiàn)無失真的編碼。式中H(U)是信源輸出序列的符號熵。通常,信源的符號熵H(U)logK，因此,上述條件還可以表示為 H(U)+/logLN/MlogK/logL特別,若有KL,那么,只要H(U)logK,就可能有NM，從而提高信息載荷的效率。由上面這個條件可以看出，H(U)離logK越遠(yuǎn),通過編碼所能獲得的效率改善就越顯著。實(shí)質(zhì)上，定長編碼方法提高信息載荷能力的關(guān)鍵是利用了漸近等分性,通過選擇足夠大的M,把本來各個符號概率不等因而H(U)logK的信源輸出符號序列變換為概率均勻的

13、典型序列，而碼字的唯一可譯性則由碼字的定長性來解決。離散無記憶信源的變長編碼定理變長編碼是指V的各個碼字的長度不相等。只要V中各個碼字的長度 Ni(i1，V)滿足克拉夫特不等式。這 V個碼字就能唯一地正確劃分和譯碼。離散無記憶信源的變長編碼定理指出：若離散無記憶信源的輸出符號序列 ，式中 Ak|k=1,K,符號熵為H(U)，對U進(jìn)行唯一可譯的變長編碼，編碼字母表B的符號數(shù)為L,即B=bl|l=1,L,那么必定存在一種編碼方法，使編出的碼字Vi(vi1,viNi)，(i=1,V)，具有平均長度嚻： MH(U)/logL嚻MH(U)/logL+1若L=K，則當(dāng)H(U)logKlogL時,必有嚻M；

14、H(U)離logK越遠(yuǎn)，則嚻越小于M。具體實(shí)現(xiàn)唯一可譯變長編碼的方法很多，但比較經(jīng)典的方法還是仙農(nóng)編碼法、費(fèi)諾編碼法和霍夫曼編碼法。其他方法都是這些經(jīng)典方法的變形和發(fā)展。所有這些經(jīng)典編碼方法，都是通過以短碼來表示常出現(xiàn)的符號這個原則來實(shí)現(xiàn)概率的均勻化，從而得到高的信息載荷效率；同時，通過遵守克拉夫特不等式關(guān)系來實(shí)現(xiàn)碼字的唯一可譯。霍夫曼編碼方法的具體過程是：首先把信源的各個輸出符號序列按概率遞降的順序排列起來，求其中概率最小的兩個序列的概率之和，并把這個概率之和看作是一個符號序列的概率，再與其他序列依概率遞降順序排列（參與求概率之和的這兩個序列不再出現(xiàn)在新的排列之中），然后，對參與概率求和的兩

15、個符號序列分別賦予二進(jìn)制數(shù)字0和1。繼續(xù)這樣的操作,直到剩下一個以1為概率的符號序列。最后，按照與編碼過程相反的順序讀出各個符號序列所對應(yīng)的二進(jìn)制數(shù)字組，就可分別得到各該符號序列的碼字。例如，某個離散無記憶信源的輸出符號序列與其對應(yīng)的概率分布為對這些輸出符號序列進(jìn)行霍夫曼編碼的具體步驟和結(jié)果如表。表1-1由表中可以看出，在碼字序列中碼元0和1的概率分別為10/21和11/21，二者近乎相等，實(shí)現(xiàn)了概率的均勻化。同時，由于碼字序列長度滿足克拉夫特不等式 22+32+221因而碼字是唯一可譯的，不會在長的碼字序列中出現(xiàn)劃錯碼字的情況。以上幾個編碼定理，在有記憶信源或連續(xù)信源的情形也有相應(yīng)的類似結(jié)果

16、。在實(shí)際工程應(yīng)用中，往往并不追求無差錯的信源編碼和譯碼，而是事先規(guī)定一個譯碼差錯率的容許值，只要實(shí)際的譯碼差錯率不超過這個容許值即認(rèn)為滿意（見信息率-失真理論和多用戶信源編碼）。針對信源輸出符號序列的統(tǒng)計特性，尋找一定的方法把信源輸出符號序列變換為最短的碼字序列。1、解除相關(guān)性：使序列中的各個符號盡可能地互相獨(dú)立。2、概率均勻化：使編碼中各個符號出現(xiàn)的概率盡可能地相等。信源編碼的實(shí)現(xiàn)方法：離散信源編碼有香農(nóng)編碼、費(fèi)諾編碼、赫夫曼編碼、游程編碼、冗余位編碼；連續(xù)信源編碼有最佳標(biāo)量量化、矢量量化；相關(guān)信源編碼的預(yù)測編碼、差值編碼；變換編碼的子帶編碼、小波變換。一般來說，減少信源輸出符號序列中的剩余

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

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

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

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

21、logL+1；若L=K，則當(dāng)H(U)logKlogL時,必有嚻M；H(U)離logK越遠(yuǎn)，則嚻越小于M。具體實(shí)現(xiàn)唯一可譯變長編碼的方法很多，但比較經(jīng)典的方法還是仙農(nóng)編碼法、費(fèi)諾編碼法和霍夫曼編碼法。其他方法都是這些經(jīng)典方法的變形和發(fā)展。所有這些經(jīng)典編碼方法，都是通過以短碼來表示常出現(xiàn)的符號這個原則來實(shí)現(xiàn)概率的均勻化，從而得到高的信息載荷效率；同時，通過遵守克拉夫特不等式關(guān)系來實(shí)現(xiàn)碼字的唯一可譯。編碼的逆過程，利用不同編碼方法實(shí)現(xiàn)的生成的碼字通過其相應(yīng)方法實(shí)現(xiàn)對碼字的譯碼，還原出從信源輸入的信息。進(jìn)行編碼是為了壓縮信源符號的冗余度，在傳輸、譯碼后，還能恢復(fù)出原始信息。二、 算術(shù)解碼的理論基礎(chǔ)2.

22、1 算術(shù)編碼算法的基本原理算術(shù)編碼是一種無失真的編碼方法，能有效地壓縮信源冗余度，使編成的碼率趨于信的熵 ，它是無損壓縮的一種。算術(shù)編碼的基本原理是：根據(jù)信源可能發(fā)現(xiàn)的不同符號序列的概率，把 0 ，1) 區(qū)間劃分為互不重疊的子區(qū)間，子區(qū)間的寬度恰好是各符號序列概率 。 這樣信源發(fā)出的不同符號序列將與各子區(qū)間一一對應(yīng) ， 因此每個子區(qū)間的任意個實(shí)數(shù)都可以用來表示對應(yīng)的符號序列，這個數(shù)就是該符號序列所對應(yīng)的碼字。顯然 ，串符號序列發(fā)生的概率越大，對應(yīng)的子區(qū)間就越寬，要表達(dá)它所用的比特數(shù)就減少，因相應(yīng)的碼字就越短。算術(shù)編碼可以是靜態(tài)的或者自適應(yīng)的。在靜態(tài)算術(shù)編碼中，信源符號的概率是固定的 。本課程設(shè)

23、計中以靜態(tài)算術(shù)編碼算法進(jìn)行仿真。在自適應(yīng)算術(shù)編碼中，自適應(yīng)算術(shù)編碼在對符號序列進(jìn)行掃描的過程中，可一次完成兩個過程，即根據(jù)恰當(dāng)?shù)母怕使烙嬆Ｐ秃彤?dāng)前符號序列中各符號出現(xiàn)的頻率，自適應(yīng)地調(diào)整各符號的概率估計值，同時完成編碼。信源符號的概率根據(jù)編碼時符號出現(xiàn)的頻繁程度動態(tài)地進(jìn)行修改，在編碼期間估算信源符號概率的過程叫做建模。需要開發(fā)態(tài)算術(shù)編碼的原因是因?yàn)槭孪戎谰_的信源概率是很難的，而且是不切實(shí)際的。當(dāng)壓縮消息時，我們不能期待一個算術(shù)編碼器獲得最大的效率， 所能做的最有效的方法是在編碼過程中估算概率。盡管從編碼效率上看不如已知概率表的情況，但正是由于算術(shù)編碼自適應(yīng)的調(diào)整對個符號概率的估計值，這點(diǎn)比

24、哈弗曼編碼相比，具有實(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）信源符號概率接近時，建議使用算術(shù)編碼，這種情況下其效率高于霍夫曼編碼；（3）算術(shù)編碼繞過了用一個特定的代碼替代一個輸入符號的想法，用一個浮點(diǎn)輸出數(shù)值代替一個流的輸入符號，較長的復(fù)雜的消息輸出的數(shù)值中就需要更多的位數(shù)；（4）算術(shù)編碼實(shí)現(xiàn)方法復(fù)雜一些，但 JPEG 成員對多幅圖像的測試結(jié)果表明，算術(shù)編碼比霍夫曼編碼提高了 10%左右的效率，因此在 JPEG 擴(kuò)展系統(tǒng)中用算術(shù)編碼取代霍夫曼編碼

25、。算術(shù)編碼雖然具有其獨(dú)特的優(yōu)點(diǎn)，但我們?nèi)孕枰⒁庀旅鎺讉€問題：（1）由于實(shí)際的計算機(jī)的精度不可能無限長，運(yùn)算中出現(xiàn)溢出是一個明顯的問題，但多數(shù)機(jī)器都有 16 位、32 位或者 64 位的精度，因此這個問題可使用比例縮放方法解決。（2）算術(shù)編碼器對整個消息只產(chǎn)生一個碼字，這個碼字是在間隔0, 1)中的一個實(shí)數(shù)，因此譯碼器在接受到表示這個實(shí)數(shù)的所有位之前不能進(jìn)行譯碼。（3）算術(shù)編碼也是一種對錯誤很敏感的編碼方法，如果有一位發(fā)生錯誤就會導(dǎo)致整個消息譯錯。算術(shù)編碼隨著序列長度的增加，相應(yīng)子區(qū)間的寬度也不斷縮小，要表示這段子區(qū)間所需精度，直觀地說就是比特數(shù)也不斷增加。這不但要占用相當(dāng)大的存儲空間，還增加

26、了編碼延時，這對實(shí)時系統(tǒng)是十分不利的。為了解決這些難點(diǎn)，針對不同的應(yīng)用方向，人們對傳統(tǒng)的算術(shù)編碼方法進(jìn)行了改進(jìn)，在保證足夠精度的前提下，提高了編碼速度?；谒阈g(shù)編碼算法人們提出了二進(jìn)制自適應(yīng)的算術(shù)編碼以與 MQ 算術(shù)編碼器，分別在軟件與上提高編碼的效率。2.3 算術(shù)編碼的分析過程在算術(shù)編碼中，消息用0到1之間的實(shí)數(shù)進(jìn)行編碼，算術(shù)編碼用到兩個基本的參數(shù)：符號的概率和它的編碼間隔。信源符號的概率決定壓縮編碼的效率，也決定編碼過程源符號的間隔，而這些間隔包含在 0到1之間。編碼過程中的間隔決定了符號壓縮后的輸出。算術(shù)編碼的過程，實(shí)際上就是依據(jù)信源符號的發(fā)生概率對碼區(qū)間分割的過程。算術(shù)編碼的編碼分析框

27、圖如下：圖2.1 算術(shù)編碼的編碼分析框圖靜態(tài)算術(shù)編碼和自適應(yīng)型算術(shù)編碼在編碼前都需要初始化概率空間，靜態(tài)算術(shù)編碼的字符概率是固定的，因此找到相應(yīng)的概率空間可直接按區(qū)間分割進(jìn)行編碼；自適應(yīng)型算術(shù)編碼在編碼前需要統(tǒng)計輸入的文本信息的符號類型和每個符號的個數(shù)，期初假定每個符號概率相等，然后輸入一個符號后，找到相應(yīng)的概率空間所有的符號概率會進(jìn)行更新，然后依次規(guī)律對輸入信息進(jìn)行編碼。圖2.2 算術(shù)編碼的譯碼分析框圖 讀取編碼結(jié)果，找到所屬區(qū)間圍從而譯出碼字。靜態(tài)型算術(shù)編碼的編碼值是變化的然后找所對應(yīng)的區(qū)間；自適應(yīng)型算術(shù)編碼的編碼值是不變的，只需改變概率區(qū)間，然后用此編碼值找到所對應(yīng)的區(qū)間，從而譯出碼字。

28、2.4算術(shù)編碼舉例（1）靜態(tài)算術(shù)編碼舉例假設(shè)一則消息“static_tree”具有如下的概率分布： 字符概率 _0.1 a 0.1 e 0.3 r 0.1 s 0.1 t 0.3下面用算術(shù)編碼方法給該消息編碼。 一旦字符的概率已知，就沿著“概率線”為每一個單獨(dú)的符號設(shè)定一個圍，哪一個被設(shè)定到哪一段圍并不重要，只要編碼和解碼都以同樣方式進(jìn)行就可以，這里所用的6個字符被分配的圍（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)對第二個字

29、符t編碼，使用的新生圍為0.6,0.7），因?yàn)閠的range low=0.7,range high=1.0,因此下一個low,high分別為 Low=0.6+0.10.70.67 High=0.6+0.11.00.70 Range=0.7-0.67=0.03 t將0.6,0.7）=0.67,0.70） (4)對第三個字符a編碼，在新生成的0.67,0.70）中進(jìn)行分割，因?yàn)閍的range low=0.10,range high=0.2,因此下一個low,high分別為 Low=0.67+0.030.10.673 High=0.67+0.030.20.676 Range=0.676-0.673=

30、0.003 a將0.67,0.70）=0.673,0.676） (5)對第四個字符t編碼，在新生成的0.673,0.676）上進(jìn)行分割。因?yàn)閠的range low=0.70,range high=1.0,則下一個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.675

31、30295,0.67530376),0.675303112,0.675303355），0.6753031606,0.6753032335）,0.6753031824,0.6753032335）。最后選取最后區(qū)間的中點(diǎn)作為編碼的輸出結(jié)果0.6753032079。通過編碼，最后的下界值0.6753032079就是消息“state_tree”的唯一編碼。然后解碼過判斷哪一個符號能擁有我們已編碼的消息落在的空間來找出消息中的第一個符號。由于0.6753032079落在0.6,0.7）之間，因此可解得第一個符號是s。在解出s后，由于我們知道s的圍的上界和下界，利用編碼的逆作用，首先去掉s的下界值0.6，

32、得0.075 3032079，然后用s的圍range=0.1去除所得到的0.075 3032079，即得到0.75 3032079，接著找出它所在的區(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ù)編碼舉例 在編碼之前，假設(shè)每個信源符號的頻率相等（如都等于1），并計算累積頻率從輸入流中讀入一個字符，并對該符號進(jìn)行算術(shù)編碼

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

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

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

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

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

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

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

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

41、的主界面，按要求輸入字符串，例如abcdef。由于在轉(zhuǎn)化為二進(jìn)制時受限于字長，因此輸入的字符串長度要適宜。（2）編碼程序段for i=1:k %開始算術(shù)編碼if i=1 %為字符串的第一個字符編碼，a1,a2分別表示個字符串區(qū)間的端點(diǎn)switch 1 %用“開關(guān)語句”檢測是什么字符，在做相應(yīng)的編碼處理case string_s(i)=aa1=0; a2=0+pa; case string_s(i)=ba1=pa; a2=pa+pb;case string_s(i)=ca1=pa+pb; a2=pa+pb+pc;case string_s(i)=da1=pa+pb+pc; a2=pa+pb+pc

42、+pd; case string_s(i)=ea1=pa+pb+pc+pd; a2=pa+pb+pc+pd+pe; case string_s(i)=fa1=pa+pb+pc+pd+pe; a2=1;endl=a2-a1; %計算各字符串編碼區(qū)間的長度endif (i=2)&(i=1&i=k %譯碼對字符的確認(rèn)switch 1 case ym=1 bm0=(bm0-0)/pa;decode(i)=new_string(1);case ym=2 bm0=(bm0-pa)/pb;decode(i)=new_string(2);case ym=3 bm0=(bm0-pa-pb)/pc;decode(

43、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);endi=i+1; ym=YM(bm0);%調(diào)用單個字符譯碼子程序YM對第二個碼元與以后各碼元譯碼end圖3.4 算術(shù)編碼譯碼仿真 上圖為算術(shù)編碼譯碼圖示，通過選擇是否譯碼，確定對編碼的碼字是否譯出。按1，則譯出編碼前輸入的信息，得到編碼的譯碼結(jié)果。3.4結(jié)果分析 基于算術(shù)編碼算法，運(yùn)行MATLAB 程序，算術(shù)編碼輸出結(jié)果為0.013706；輸入的字符經(jīng)過算術(shù)算法的解碼，輸出的符號串也是一致的，驗(yàn)證了算術(shù)編碼算法是一種無失真的熵編碼方式。