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

******************實踐教學(xué)*******************計算機與通信學(xué)院通信系統(tǒng)仿真訓(xùn)練題目：基于算術(shù)編碼的信源編碼/解碼系統(tǒng)設(shè)計與仿真信源編碼1.1信源編碼的概念信源編碼是為了減少信源輸出符號序列中的剩余度、提高符號的平均信息量，對信源輸出的符號序列所施行的變換。具體說，就是針對信源輸出符號序列的統(tǒng)計特性來尋找某種方法，把信源輸出符號序列變換為最短的碼字序列，使后者的各碼元所載荷的平均信息量最大，同時又能保證無失真地恢復(fù)原來的符號序列。既然信源編碼的基本目的是提高碼字序列中碼元的平均信息量，那么，一切旨在減少剩余度而對信源輸出符號序列所施行的變換或處理，都可以在這種意義下歸入信源編碼的范疇，例如過濾、預(yù)測、域變換和數(shù)據(jù)壓縮等。當(dāng)然，這些都是廣義的信源編碼。1.2信源編碼簡介信源編碼是以提高通信有效性為目的的編碼。通常通過壓縮信源的冗余度來實現(xiàn)。采用的一般方法是壓縮每個信源符號的平均比特數(shù)或信源的碼率，同樣多的信息用較少的碼率來傳輸，使單位時間內(nèi)傳送的平均信息來量增加，從而提高通信的有效性。信源編碼理論是信息論的一個重要分支，其理論基礎(chǔ)是信源編碼的兩個定理：無失真信源編碼定理和限失真信源編碼定理。前者是離散信源或數(shù)字編碼的基礎(chǔ)，后者則是連續(xù)信源或模擬信號的基礎(chǔ)。編碼實質(zhì)上就是對信源的原始符號按一定規(guī)則進行的一種變換。編碼可分為信源編碼和信道編碼。由于信源符號之間存在分布不均勻和相關(guān)性，使得信源存在冗余度，信源編碼的主要任務(wù)就是減少冗余，提高編碼效率。信源編碼是為了減少信源輸出符號序列中的剩余度、提高符號的平均信息量，對信源輸出的符號序列所施行的變換。具體說，就是針對信源輸出符號序列的統(tǒng)計特性來尋找某種方法，把信源輸出符號序列變換為最短的碼字序列，使后者的各碼元所載荷的平均信息量最大，同時又能保證無失真地恢復(fù)原來的符號序列。信源編碼的基本途徑有兩個：使序列中的各個符號盡可能地相互獨立，即解除相關(guān)性；使編碼中各個符號出現(xiàn)的概率盡可能地相等，即概率均勻化。采用的一般方法是壓縮每個信源符號的平均比特數(shù)或信源的碼率。即同樣多的信息用較少的碼率傳送,使單位時間內(nèi)傳送的平均信息量增加,從而提高通信的有效性。1.3信源編碼的目的：1、信源存在冗余度。2、原因是信源符號之間存在概率分布不均勻和相關(guān)性。3、信源編碼的主要任務(wù)就是減少冗余，提高編碼效率。4、信源編碼是以提高通信的有效性為目的編碼。5、通常通過壓縮信源的冗余度來實現(xiàn)。6、即用較少的碼字傳送較多的信息，使單位時間內(nèi)傳送的平均信息量增加，從而提高通信的有效性。1.4信源編碼的原理一般來說，減少信源輸出符號序列中的剩余度、提高符號平均信息量的基本途徑有兩個：①使序列中的各個符號盡可能地互相獨立；②使序列中各個符號的出現(xiàn)概率盡可能地相等。前者稱為解除相關(guān)性，后者稱為概率均勻化。信源編碼的一般問題可以表述如下：若某信源的輸出為長度等于M的符號序列集合式中符號A為信源符號表，它包含著K個不同的符號，A=｛ɑk|k=1,…,K｝，這個信源至多可以輸出K個不同的符號序列。記‖U‖=K。所謂對這個信源的輸出進行編碼，就是用一個新的符號表B的符號序列集合V來表示信源輸出的符號序列集合U。若V的各個序列的長度等于N，即式中新的符號表B共含L個符號，B=｛bl|l=1,…,L｝。它總共可以編出L個不同的碼字。類似地,記‖V‖＝L。為了使信源的每個輸出符號序列都能分配到一個獨特的碼字與之對應(yīng)，至少應(yīng)滿足關(guān)系‖V‖＝L≥‖U‖＝K，或者N/M≥logK/logL；假若編碼符號表B的符號數(shù)L與信源符號表A的符號數(shù)K相等，則編碼后的碼字序列的長度N必須大于或等于信源輸出符號序列的長度M；反之，若有N＝M，則必須有L≥K。只有滿足這些條件，才能保證無差錯地還原出原來的信源輸出符號序列(稱為碼字的唯一可譯性)?？墒?，在這些條件下，碼字序列的每個碼元所載荷的平均信息量不但不能高于，反而會低于信源輸出序列的每個符號所載荷的平均信息量。這與編碼的基本目標(biāo)是直接相矛盾的。下面的幾個編碼定理，提供了解決這個矛盾的方法。它們既能改善信息載荷效率，又能保證碼字唯一可譯。離散無記憶信源的定長編碼定理對于任意給定的ε＞0，只要滿足條件N/M≥(H(U)+ε)/logL那么,當(dāng)M足夠大時,上述編碼幾乎沒有失真;反之,若這個條件不滿足，就不可能實現(xiàn)無失真的編碼。式中H(U)是信源輸出序列的符號熵。通常,信源的符號熵H(U)＜logK，因此,上述條件還可以表示為【H(U)+ε】/logL≤N/M≤logK/logL特別,若有K＝L,那么,只要H(U)＜logK,就可能有N＜M，從而提高信息載荷的效率。由上面這個條件可以看出，H(U)離logK越遠,通過編碼所能獲得的效率改善就越顯著。實質(zhì)上，定長編碼方法提高信息載荷能力的關(guān)鍵是利用了漸近等分性,通過選擇足夠大的M,把本來各個符號概率不等［因而H(U)＜logK］的信源輸出符號序列變換為概率均勻的典型序列，而碼字的唯一可譯性則由碼字的定長性來解決。離散無記憶信源的變長編碼定理變長編碼是指V的各個碼字的長度不相等。只要V中各個碼字的長度Ni(i＝1，…，‖V‖)滿足克拉夫特不等式。這‖V‖個碼字就能唯一地正確劃分和譯碼。離散無記憶信源的變長編碼定理指出：若離散無記憶信源的輸出符號序列，式中A＝｛ɑk|k=1,…,K｝,符號熵為H(U)，對U進行唯一可譯的變長編碼，編碼字母表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)＜logK＝logL時,必有嚻＜M；H(U)離logK越遠，則嚻越小于M。具體實現(xiàn)唯一可譯變長編碼的方法很多，但比較經(jīng)典的方法還是仙農(nóng)編碼法、費諾編碼法和霍夫曼編碼法。其他方法都是這些經(jīng)典方法的變形和發(fā)展。所有這些經(jīng)典編碼方法，都是通過以短碼來表示常出現(xiàn)的符號這個原則來實現(xiàn)概率的均勻化，從而得到高的信息載荷效率；同時，通過遵守克拉夫特不等式關(guān)系來實現(xiàn)碼字的唯一可譯。霍夫曼編碼方法的具體過程是：首先把信源的各個輸出符號序列按概率遞降的順序排列起來，求其中概率最小的兩個序列的概率之和，并把這個概率之和看作是一個符號序列的概率，再與其他序列依概率遞降順序排列（參與求概率之和的這兩個序列不再出現(xiàn)在新的排列之中），然后，對參與概率求和的兩個符號序列分別賦予二進制數(shù)字0和1。繼續(xù)這樣的操作,直到剩下一個以1為概率的符號序列。最后，按照與編碼過程相反的順序讀出各個符號序列所對應(yīng)的二進制數(shù)字組，就可分別得到各該符號序列的碼字。例如，某個離散無記憶信源的輸出符號序列及其對應(yīng)的概率分布為對這些輸出符號序列進行霍夫曼編碼的具體步驟和結(jié)果如表。表1-1由表中可以看出，在碼字序列中碼元0和1的概率分別為10/21和11/21，二者近乎相等，實現(xiàn)了概率的均勻化。同時，由于碼字序列長度滿足克拉夫特不等式2×2+3×2+2×2＝1因而碼字是唯一可譯的，不會在長的碼字序列中出現(xiàn)劃錯碼字的情況。以上幾個編碼定理，在有記憶信源或連續(xù)信源的情形也有相應(yīng)的類似結(jié)果。在實際工程應(yīng)用中，往往并不追求無差錯的信源編碼和譯碼，而是事先規(guī)定一個譯碼差錯率的容許值，只要實際的譯碼差錯率不超過這個容許值即認(rèn)為滿意（見信息率-失真理論和多用戶信源編碼）。針對信源輸出符號序列的統(tǒng)計特性，尋找一定的方法把信源輸出符號序列變換為最短的碼字序列。1、解除相關(guān)性：使序列中的各個符號盡可能地互相獨立。2、概率均勻化：使編碼中各個符號出現(xiàn)的概率盡可能地相等。信源編碼的實現(xiàn)方法：離散信源編碼有香農(nóng)編碼、費諾編碼、赫夫曼編碼、游程編碼、冗余位編碼；連續(xù)信源編碼有最佳標(biāo)量量化、矢量量化；相關(guān)信源編碼的預(yù)測編碼、差值編碼；變換編碼的子帶編碼、小波變換。一般來說，減少信源輸出符號序列中的剩余度、提高符號平均信息量的基本途徑有兩個：一是使序列中的各個符號盡可能地互相獨立；二是使序列中各個符號的出現(xiàn)概率盡可能地相等。前者稱為解除相關(guān)性，后者稱為概率均勻化。信源編碼的一般問題可以表述如下：若某信源的輸出為長度等于M的符號序列集合式中符號A為信源符號表，它包含著K個不同的符號，A=｛ɑk|k=1,…,K｝，這個信源至多可以輸出K個不同的符號序列。記‖U‖=K。所謂對這個信源的輸出進行編碼，就是用一個新的符號表B的符號序列集合V來表示信源輸出的符號序列集合U。若V的各個序列的長度等于I，即式中新的符號表B共含L個符號，B=｛bl|l=1,…,L｝。它總共可以編出L個不同的碼字。類似地,記‖V‖＝L。為了使信源的每個輸出符號序列都能分配到一個獨特的碼字與之對應(yīng)，至少應(yīng)滿足關(guān)系‖V‖＝L≥‖U‖＝K，或者N/M≥logK/logL；假若編碼符號表B的符號數(shù)L與信源符號表A的符號數(shù)K相等，則編碼后的碼字序列的長度N必須大于或等于信源輸出符號序列的長度M；反之，若有N＝M，則必須有L≥K。只有滿足這些條件，才能保證無差錯地還原出原來的信源輸出符號序列(稱為碼字的唯一可譯性)?？墒?，在這些條件下，碼字序列的每個碼元所載荷的平均信息量不但不能高于，反而會低于信源輸出序列的每個符號所載荷的平均信息量。這與編碼的基本目標(biāo)是直接相矛盾的。下面的幾個編碼定理，提供了解決這個矛盾的方法。它們既能改善信息載荷效率，又能保證碼字唯一可譯。(1)離散無記憶信源的定長編碼定理對于任意給定的ε＞0，只要滿足條件N/M≥(H(U)+ε)/logL那么,當(dāng)M足夠大時,上述編碼幾乎沒有失真;反之,若這個條件不滿足，就不可能實現(xiàn)無失真的編碼。式中H(U)是信源輸出序列的符號熵。通常,信源的符號熵H(U)＜logK，因此,上述條件還可以表示為【H(U)+ε】/logL≤N/M≤logK/logL。特別,若有K＝L,那么,只要H(U)＜logK,就可能有N＜M，從而提高信息載荷的效率。由上面這個條件可以看出，H(U)離logK越遠,通過編碼所能獲得的效率改善就越顯著。實質(zhì)上，定長編碼方法提高信息載荷能力的關(guān)鍵是利用了漸近等分性,通過選擇足夠大的M,把本來各個符號概率不等［因而H(U)＜logK］的信源輸出符號序列變換為概率均勻的典型序列，而碼字的唯一可譯性則由碼字的定長性來解決。(2)離散無記憶信源的變長編碼定理變長編碼是指V的各個碼字的長度不相等。只要V中各個碼字的長度Ni(i＝1，…，‖V‖)滿足克拉夫特不等式。這‖V‖個碼字就能唯一地正確劃分和譯碼。離散無記憶信源的變長編碼定理指出：若離散無記憶信源的輸出符號序列為，式中A＝｛ɑk|k=1,…,K｝,符號熵為H(U)，對U進行唯一可譯的變長編碼，編碼字母表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)＜logK＝logL時,必有嚻＜M；H(U)離logK越遠，則嚻越小于M。具體實現(xiàn)唯一可譯變長編碼的方法很多，但比較經(jīng)典的方法還是仙農(nóng)編碼法、費諾編碼法和霍夫曼編碼法。其他方法都是這些經(jīng)典方法的變形和發(fā)展。所有這些經(jīng)典編碼方法，都是通過以短碼來表示常出現(xiàn)的符號這個原則來實現(xiàn)概率的均勻化，從而得到高的信息載荷效率；同時，通過遵守克拉夫特不等式關(guān)系來實現(xiàn)碼字的唯一可譯。編碼的逆過程，利用不同編碼方法實現(xiàn)的生成的碼字通過其相應(yīng)方法實現(xiàn)對碼字的譯碼，還原出從信源輸入的信息。進行編碼是為了壓縮信源符號的冗余度，在傳輸、譯碼后，還能恢復(fù)出原始信息。二、算術(shù)解碼的理論基礎(chǔ)2.1算術(shù)編碼算法的基本原理算術(shù)編碼是一種無失真的編碼方法，能有效地壓縮信源冗余度，使編成的碼率趨于信的熵，它是無損壓縮的一種。算術(shù)編碼的基本原理是：根據(jù)信源可能發(fā)現(xiàn)的不同符號序列的概率，把[0，1)區(qū)間劃分為互不重疊的子區(qū)間，子區(qū)間的寬度恰好是各符號序列概率。這樣信源發(fā)出的不同符號序列將與各子區(qū)間一一對應(yīng)，因此每個子區(qū)間內(nèi)的任意個實數(shù)都可以用來表示對應(yīng)的符號序列，這個數(shù)就是該符號序列所對應(yīng)的碼字。顯然，串符號序列發(fā)生的概率越大，對應(yīng)的子區(qū)間就越寬，要表達它所用的比特數(shù)就減少，因相應(yīng)的碼字就越短。算術(shù)編碼可以是靜態(tài)的或者自適應(yīng)的。在靜態(tài)算術(shù)編碼中，信源符號的概率是固定的。本課程設(shè)計中以靜態(tài)算術(shù)編碼算法進行仿真。在自適應(yīng)算術(shù)編碼中，自適應(yīng)算術(shù)編碼在對符號序列進行掃描的過程中，可一次完成兩個過程，即根據(jù)恰當(dāng)?shù)母怕使烙嬆Ｐ秃彤?dāng)前符號序列中各符號出現(xiàn)的頻率，自適應(yīng)地調(diào)整各符號的概率估計值，同時完成編碼。信源符號的概率根據(jù)編碼時符號出現(xiàn)的頻繁程度動態(tài)地進行修改，在編碼期間估算信源符號概率的過程叫做建模。需要開發(fā)態(tài)算術(shù)編碼的原因是因為事先知道精確的信源概率是很難的，而且是不切實際的。當(dāng)壓縮消息時，我們不能期待一個算術(shù)編碼器獲得最大的效率，所能做的最有效的方法是在編碼過程中估算概率。盡管從編碼效率上看不如已知概率表的情況，但正是由于算術(shù)編碼自適應(yīng)的調(diào)整對個符號概率的估計值，這點比哈弗曼編碼相比，具有實時性好、靈活性高、適應(yīng)性強等特點，在圖像壓縮、視頻圖像編碼等領(lǐng)域都得到了廣泛的應(yīng)用。2.2算術(shù)編碼的特點算術(shù)編碼的優(yōu)點：（1）不必預(yù)先定義概率模型，自適應(yīng)模式具有獨特的優(yōu)點；（2）信源符號概率接近時，建議使用算術(shù)編碼，這種情況下其效率高于霍夫曼編碼；（3）算術(shù)編碼繞過了用一個特定的代碼替代一個輸入符號的想法，用一個浮點輸出數(shù)值代替一個流的輸入符號，較長的復(fù)雜的消息輸出的數(shù)值中就需要更多的位數(shù)；（4）算術(shù)編碼實現(xiàn)方法復(fù)雜一些，但JPEG成員對多幅圖像的測試結(jié)果表明，算術(shù)編碼比霍夫曼編碼提高了10%左右的效率，因此在JPEG擴展系統(tǒng)中用算術(shù)編碼取代霍夫曼編碼。算術(shù)編碼雖然具有其獨特的優(yōu)點，但我們?nèi)孕枰⒁庀旅鎺讉€問題：（1）由于實際的計算機的精度不可能無限長，運算中出現(xiàn)溢出是一個明顯的問題，但多數(shù)機器都有16位、32位或者64位的精度，因此這個問題可使用比例縮放方法解決。（2）算術(shù)編碼器對整個消息只產(chǎn)生一個碼字，這個碼字是在間隔[0,1)中的一個實數(shù)，因此譯碼器在接受到表示這個實數(shù)的所有位之前不能進行譯碼。（3）算術(shù)編碼也是一種對錯誤很敏感的編碼方法，如果有一位發(fā)生錯誤就會導(dǎo)致整個消息譯錯。算術(shù)編碼隨著序列長度的增加，相應(yīng)子區(qū)間的寬度也不斷縮小，要表示這段子區(qū)間所需精度，直觀地說就是比特數(shù)也不斷增加。這不但要占用相當(dāng)大的存儲空間，還增加了編碼延時，這對實時系統(tǒng)是十分不利的。為了解決這些難點，針對不同的應(yīng)用方向，人們對傳統(tǒng)的算術(shù)編碼方法進行了改進，在保證足夠精度的前提下，提高了編碼速度?；谒阈g(shù)編碼算法人們提出了二進制自適應(yīng)的算術(shù)編碼以及MQ算術(shù)編碼器，分別在軟件及上提高編碼的效率。2.3算術(shù)編碼的分析過程在算術(shù)編碼中，消息用0到1之間的實數(shù)進行編碼，算術(shù)編碼用到兩個基本的參數(shù)：符號的概率和它的編碼間隔。信源符號的概率決定壓縮編碼的效率，也決定編碼過程中信源符號的間隔，而這些間隔包含在0到1之間。編碼過程中的間隔決定了符號壓縮后的輸出。算術(shù)編碼的過程，實際上就是依據(jù)信源符號的發(fā)生概率對碼區(qū)間分割的過程。算術(shù)編碼的編碼分析框圖如下： 圖2.1算術(shù)編碼的編碼分析框圖靜態(tài)算術(shù)編碼和自適應(yīng)型算術(shù)編碼在編碼前都需要初始化概率空間，靜態(tài)算術(shù)編碼的字符概率是固定的，因此找到相應(yīng)的概率空間可直接按區(qū)間分割進行編碼；自適應(yīng)型算術(shù)編碼在編碼前需要統(tǒng)計輸入的文本信息的符號類型和每個符號的個數(shù)，期初假定每個符號概率相等，然后輸入一個符號后，找到相應(yīng)的概率空間所有的符號概率會進行更新，然后依次規(guī)律對輸入信息進行編碼。圖2.2算術(shù)編碼的譯碼分析框圖讀取編碼結(jié)果，找到所屬區(qū)間范圍從而譯出碼字。靜態(tài)型算術(shù)編碼的編碼值是變化的然后找所對應(yīng)的區(qū)間；自適應(yīng)型算術(shù)編碼的編碼值是不變的，只需改變概率區(qū)間，然后用此編碼值找到所對應(yīng)的區(qū)間，從而譯出碼字。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ù)編碼方法給該消息編碼。

一旦字符的概率已知，就沿著“概率線”為每一個單獨的符號設(shè)定一個范圍，哪一個被設(shè)定到哪一段范圍并不重要，只要編碼和解碼都以同樣方式進行就可以，這里所用的6個字符被分配的范圍（range）如下：字符

概率

范圍

_

0.1

0≤r<0.1

a

0.1

0.1≤r<0.2

e

0.3

0.2≤r<0.5

r

0.1

0.5≤r<0.6

s

0.1

0.6≤r<0.7

t

0.3

0.7≤r<1.0

對“state_tree”的算術(shù)編碼過程為：初始化時，被分割的范圍range=high-low=[0,1）,下一個范圍的低、高端分別由下式計算：

Low=low+range×rangelow

High=low+range×rangehigh

其中等號右邊的low為上一個被編碼字符的范圍低；rangelow和rangehigh分別為被編碼符號已給定的字符出現(xiàn)概率范圍的low和high。

（2）對消息第一字符s編碼：s的rangelow=0.6，s的rangehigh=0.7因此，下一個區(qū)間的low和high為：

Low=low+range×rangelow=0+1×0.6=0.6

High=low+range×rangehigh=0+1×0.7=0.7

Range=high-low=0.7-0.6=0.1

s將區(qū)間[0,1）=>[0.6,0.7）

(3)對第二個字符t編碼，使用的新生范圍為[0.6,0.7），因為t的rangelow=0.7,rangehigh=1.0,因此下一個low,high分別為

Low=0.6+0.1×0.7＝0.67

High=0.6+0.1×1.0＝0.70

Range=0.7-0.67=0.03

t將[0.6,0.7）=>[0.67,0.70）

(4)對第三個字符a編碼，在新生成的[0.67,0.70）中進行分割，因為a的rangelow=0.10,rangehigh=0.2,因此下一個low,high分別為

Low=0.67+0.03×0.1＝0.673

High=0.67+0.03×0.2＝0.676

Range=0.676-0.673=0.003

a將[0.67,0.70）=>[0.673,0.676）

(5)對第四個字符t編碼，在新生成的[0.673,0.676）上進行分割。因為t的rangelow=0.70,rangehigh=1.0,則下一個low,high分別為

Low=0.673+0.003×0.7＝0.6751

High=0.673+0.003×1.0＝0.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.6753032335）。最后選取最后區(qū)間的中點作為編碼的輸出結(jié)果0.6753032079。通過編碼，最后的下界值0.6753032079就是消息“state_tree”的唯一編碼。然后解碼過判斷哪一個符號能擁有我們已編碼的消息落在的空間來找出消息中的第一個符號。由于0.6753032079落在[0.6,0.7）之間，因此可解得第一個符號是s。在解出s后，由于我們知道s的范圍的上界和下界，利用編碼的逆作用，首先去掉s的下界值0.6，得0.0753032079，然后用s的范圍range=0.1去除所得到的0.0753032079，即得到0.753032079，接著找出它所在的區(qū)間，就是t的原來范圍[0.7,1.0）。去掉t的下界值0.7，得0.053032079，然后用t的range=0.3除該數(shù)得出0.17677202，該值所屬范圍就是字符a……如此操作下去便得到消息的準(zhǔn)確譯碼綜述，可以得到解碼公式為：(Number-rangelow)/range=>number其中，number為符串的編碼。算術(shù)編碼舉例在編碼之前，假設(shè)每個信源符號的頻率相等（如都等于1），并計算累積頻率從輸入流中讀入一個字符，并對該符號進行算術(shù)編碼；更新該符號的頻率，并更新累積頻率；由于在解碼之前，解碼器不知道是哪個信源符號，所以概率更新應(yīng)該在解碼之后進行對應(yīng)的，編碼器也應(yīng)在編碼后進行概率更新。設(shè)某信源可能發(fā)出三種符號a，b，c，對符號序列bccb進行自適應(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.6667)。此時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ū)間內(nèi)任意選擇一個實數(shù)，例如0.64，再將其轉(zhuǎ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ū)間[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。一旦字符的概率已知，就沿著“概率線”為每一個單獨的符號設(shè)定一個范圍，哪一個被設(shè)定到哪一段范圍并不重要，只要編碼和解碼都以同樣方式進行就可以。離散信源編碼有香農(nóng)編碼、費諾編碼、赫夫曼編碼、游程編碼、冗余位編碼；連續(xù)信源編碼有最佳標(biāo)量量化、矢量量化；相關(guān)信源編碼的預(yù)測編碼、差值編碼；變換編碼的子帶編碼、小波變換。本章主要舉例說明了算術(shù)編碼的基本原理，讓讀者能夠理解算術(shù)編碼的基本應(yīng)用方法。三、算術(shù)編碼MATLAB仿真實現(xiàn)3.1MATLAB仿真程序?qū)崿F(xiàn)MATLAB是由美國mathworks公司發(fā)布的主要面對科學(xué)計算、可視化以及交互式程序設(shè)計的高科技計算環(huán)境。它將數(shù)值分析、矩陣計算、科學(xué)數(shù)據(jù)可視化以及非線性動態(tài)系統(tǒng)的建模和仿真等諸多強大功能集成在一個易于使用的視窗環(huán)境中，為科學(xué)研究、工程設(shè)計以及必須進行有效數(shù)值計算的眾多科學(xué)領(lǐng)域提供了一種全面的解決方案，并在很大程度上擺脫了傳統(tǒng)非交互式程序設(shè)計語言（如C、Fortran）的編輯模式，代表了當(dāng)今國際科學(xué)計算軟件的先進水平。MATLAB由一系列工具組成。這些工具方便用戶使用MATLAB的函數(shù)和文件，其中許多工具采用的是圖形用戶界面。包括MATLAB桌面和命令窗口、歷史命令窗口、編輯器和調(diào)試器、路徑搜索和用于用戶瀏覽幫助、工作空間、文件的瀏覽器。隨著MATLAB的商業(yè)化以及軟件本身的不斷升級，MATLAB的用戶界面也越來越精致，更加接近Windows的標(biāo)準(zhǔn)界面，人機交互性更強，操作更簡單。而且新版本的MATLAB提供了完整的聯(lián)機查詢、幫助系統(tǒng)，極大的方便了用戶的使用。簡單的編程環(huán)境提供了比較完備的調(diào)試系統(tǒng)，程序不必經(jīng)過編譯就可以直接運行，而且能夠及時地報告出現(xiàn)的錯誤及進行出錯原因分析。MATLAB7.1版本是在2005年更新的，本文主要應(yīng)用MATLAB7.1中發(fā)布的影像處理工具箱中的相關(guān)函數(shù)和命令來實現(xiàn)基于算術(shù)編碼實現(xiàn)圖像壓縮理論算法的仿真。MATLAB7.1是一套功能十分強大的工程計算及數(shù)據(jù)分析應(yīng)用軟件,廣泛應(yīng)用于工業(yè)、電子、控制、信號及圖像處理等各領(lǐng)域。MATLAB7.1本身除了提供強大的圖形繪制和輸出功能外,同時還發(fā)布了影像處理工具箱(ImageProcessingToolbox),專門用于圖像的處理.在通常情況下，可以用它來代替底層編程語言，如C和C++。在計算要求相同的情況下，使用MATLAB的編程工作量會大大減少。3.2仿真設(shè)計流程圖本課程設(shè)計的軟件算術(shù)編碼輸入的自符類型固定，每個字符的概率也是固定的。輸入的自符類型有“abcdef”每次輸入字符，更新字符的起始、終止區(qū)間。等最后一個字符編碼完成后，取起始值和終至值的中點作為編碼的結(jié)果輸出。譯碼的時候，讀取編碼的輸出結(jié)果，找到所在的區(qū)間，依次譯出編碼前輸入的字符信息。完成譯碼過程；自適應(yīng)算術(shù)編碼的概率模型不固定，先統(tǒng)計編碼的符號類型，以及每個符號的個數(shù)。譯碼前，假設(shè)每個符號的概率是相等的，然后每次輸入一個字符，相應(yīng)的字符概率發(fā)生變化，直至編出最后一個碼字，選取區(qū)間中間結(jié)果作為編碼的輸出，譯碼時，讀取中間結(jié)果，找到所屬概率區(qū)間，譯出碼字，然后變更概率區(qū)間，重新定位碼字。直至譯出最后一個碼字。圖3.1算術(shù)編碼設(shè)計流程圖上圖是算術(shù)編碼設(shè)計流程圖，無論是靜態(tài)型還是自適應(yīng)型算術(shù)編碼在編碼前都要初始化概率空間，但二者在編碼時的概率空間卻不一樣，前者固定不變，后者概率隨輸入字符變化而變化。然后進行區(qū)間分割，將字符串編成一個浮點小數(shù)，然后轉(zhuǎ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ù)編碼的主界面，按要求輸入字符串，例如’abcdef’。由于在轉(zhuǎn)化為二進制時受限于字長，因此輸入的字符串長度要適宜。（2）編碼程序段fori=1:k%開始算術(shù)編碼ifi==1%為字符串的第一個字符編碼，a1,a2分別表示個字符串區(qū)間的端點switch1%用“開關(guān)語句”檢測是什么字符，在做相應(yīng)的編碼處理casestring_s(i)=='a'a1=0;a2=0+pa;casestring_s(i)=='b'a1=pa;a2=pa+pb;casestring_s(i)=='c'a1=pa+pb;a2=pa+pb+pc;casestring_s(i)=='d'a1=pa+pb+pc;a2=pa+pb+pc+pd;casestring_s(i)=='e'a1=pa+pb+pc+pd;a2=pa+pb+pc+pd+pe;casestring_s(i)=='f'a1=pa+pb+pc+pd+pe;a2=1;endl=a2-a1;%計算各字符串編碼區(qū)間的長度endif(i>=2)&&(i<=k)%在第一個字符已編碼的基礎(chǔ)上為后續(xù)字符編碼switch1casestring_s(i)=='a'aa=a1;ab=a1+l*pa;a1=aa;a2=ab;casestring_s(i)=='b'aa=a1+l*pa;ab=a1+l*(pa+pb);a1=aa;a2=ab;casestring_s(i)=='c'aa=a1+l*(pa+pb);ab=a1+l*(pa+pb+pc);a1=aa;a2=ab;casestring_s(i)=='d'aa=a1+l*(pa+pb+pc);ab=a1+l*(pa+pb+pc+pd);a1=aa;a2=ab;casestring_s(i)=='e'aa=a1+l*(pa+pb+pc+pd);ab=a1+l*(pa+pb+pc+pd+pe);a1=aa;a2=ab;casestring_s(i)=='f'aa=a1+l*(pa+pb+pc+pd+pe);ab=a1+l*(pa+pb+pc+pd+pe+pf);a1=aa;a2=ab;endl=a2-a1;%計算各字符串編碼區(qū)間的長度endenddisp('編碼區(qū)間的起始值是：');disp(a1)%顯示編碼區(qū)間的起始值disp('編碼區(qū)間的終止值是：');disp(a2)%顯示編碼區(qū)間的終止值disp('本程序選擇區(qū)間中點做為編碼是：');disp((a1+a2)/2)%顯示編碼disp('本程序選擇區(qū)間中點做為編碼的二進制編碼是：');y=yu((a1+a2)/2,50);圖3.3編碼仿真上圖為靜態(tài)編碼仿真，通過對每一個字符編碼，不斷地進行區(qū)間分割，當(dāng)編到最后一個字符的時候，選取該字符的區(qū)間中點作為編碼結(jié)果，然后轉(zhuǎn)化為二進制，輸出。（3）、譯碼程序段whilei>=1&i<=k%譯碼對字符的確認(rèn)switch1caseym==1bm0=(bm0-0)/pa;decode(i)=new_string(1);caseym==2bm0=(bm0-pa)/pb;decode(i)=new_string(2);caseym==3bm0=(bm0-pa-pb)/pc;decode(i)=new_string(3);caseym==4bm0=(bm0-pa-pb-pc)/pd;decode(i)=new_string(4);caseym==5bm0=(bm0-pa-pb-pc-pd)/pe;decode(i)=new_string(5);caseym==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ù)編碼算法，運行MATLAB程序，算術(shù)編碼輸出結(jié)果為0.013706；輸入的字符經(jīng)過算術(shù)算法的解碼，輸出的符號串也是一致的，驗證了算術(shù)編碼算法是一種無失真的熵編碼方式。由于在編程中用到了bin2dec函數(shù)，它只能將不多于52為的二進制數(shù)譯成整數(shù)，因此輸入的符號個數(shù)受到限制，否則后產(chǎn)生誤碼。由于輸入的信息過多時，會產(chǎn)生誤碼，因此可以通過增加二進制位數(shù)來補償誤碼率問題，但二進制位數(shù)前提是不多于52位。，我們知道算術(shù)編碼是一種無失真的編碼方法，能有效地壓縮信源冗余度，屬于熵編碼的一種。算術(shù)編碼的一個重要特點就是可以按分?jǐn)?shù)比特近信源熵，突破了Haffman編碼每個符號只不過能按整數(shù)個比特逼近信源熵的限制。設(shè)計總結(jié)經(jīng)過幾周的課程設(shè)計，讓我對我的專業(yè)有了更加清楚的認(rèn)識。當(dāng)然，在設(shè)計的過程中出現(xiàn)了不少問題。例如，在應(yīng)用算術(shù)編碼算法的編程上，由于MATLAB編程知識的匱乏，導(dǎo)致編程的最終結(jié)果沒有完全出來。最終在同學(xué)和老師的幫助下，我順利解決了這些問題。同時，也經(jīng)過這次自我學(xué)習(xí)，我學(xué)到了很多算術(shù)編碼算法的知識。在課程設(shè)計的的過程中我學(xué)習(xí)到了很多東西，認(rèn)識到了信源編碼的基本目的是減少信源輸出符號序列的剩余度、提高碼字序列中碼元的平均信息量等等相關(guān)知識。在編程的過程中，又一次熟悉了通信系統(tǒng)仿真軟件Matlan的基本使用方法，能夠在該軟件的使用過程中解決隨時出現(xiàn)的問題，最重要的是提高了我綜合運用所學(xué)知識的能力和計算機的編程能力，為今后的工作和學(xué)習(xí)積累了寶貴的經(jīng)驗，對于以后的畢業(yè)設(shè)計以及之后的工作都有相當(dāng)重要的意義。最后，特別感謝在這次課程設(shè)計過程中給予我指導(dǎo)和幫助的老師和同學(xué)，使我能順利、按時完成本次課程設(shè)計，同時他們給予我的鼓勵也使我很感激，在以后的學(xué)習(xí)生活中，我會以更加積極、樂觀的心態(tài)去面對困難和挫折。

參考文獻[1]郭斌,王維東,葉青青.基于概率估計更新的CABAC加速算法[J].中國圖像學(xué)報，2009,14（3）：281-285[2]畢厚杰.新一代視頻壓縮編碼標(biāo)準(zhǔn)-H.264/AVC[M].北京：人民郵電出版社，2006:141-147[3]歐陽合，韓軍.H.264和MPEG-4視頻壓縮[M].國防科技大學(xué)出版社，2004:226-229[4]馮桂，林其偉，陳東華.信息論與編碼技術(shù)（第二版）.北京：清華大學(xué)出版社，2011.6[5]胡海明,李金良.基于上下文的自適應(yīng)二階二進制算術(shù)編碼算法[J].計算機工程與設(shè)計,2008,27（17）:3267-3269[6]余兆明，查日勇，黃磊，周海嬌.圖像編碼標(biāo)準(zhǔn)H.264技術(shù)[M].北京：人民郵電出版社，2005:71-92[7]劉奇衛(wèi).基于JPEG2000二進制算術(shù)編碼器的研究與設(shè)計[D].[碩士學(xué)位論文]浙江大學(xué),2006.[8]賈鑄.算術(shù)編碼算法在圖像壓縮中的應(yīng)用.電視技術(shù)，1999.11[9]江偉.H.264中基于上下文自適應(yīng)二進制算術(shù)編碼效率改進研究[D].[碩士學(xué)位論文]中南大學(xué),2010.[10]張德豐.詳解MATLAB數(shù)字圖像處理.北京：電子工業(yè)出版社，2010.7[11]馮玉珉,邵玉明,張星.數(shù)據(jù)圖像壓縮編碼.中國鐵道出版社,1993,9:15～60[12]ISO/IECFCD15444-1,JPEG2000ImageCodingSystem,2000[13]曹青,吳樂南.靜止圖像無失真編碼的新標(biāo)準(zhǔn)JPEG－LS.電子工程師.1999,2:12～14[15]陸桂富.H.264中自適應(yīng)算術(shù)編碼器的FPGA實現(xiàn)研究[D].[碩士學(xué)位論文]上海大學(xué),2006.[16]高展宏,徐文波.基于MATLAB的圖像處理案例教程.北京：清華大學(xué)出版社,2011.4[17]楊勝天.一個基于算術(shù)編碼的灰度圖象無損壓縮算法.計算機工程與科學(xué),2002,24(1):33～36[18]王新年,張濤.數(shù)字圖像壓縮技術(shù)實用教程.北京：機械工業(yè)出版社，2009.8基于C8051F單片機直流電動機反饋控制系統(tǒng)的設(shè)計與研究基于單片機的嵌入式Web服務(wù)器的研究MOTOROLA單片機MC68HC（8）05PV8/A內(nèi)嵌EEPROM的工藝和制程方法及對良率的影響研究基于模糊控制的電阻釬焊單片機溫度控制系統(tǒng)的研制基于MCS-51系列單片機的通用控制模塊的研究基于單片機實現(xiàn)的供暖系統(tǒng)最佳啟停自校正（STR）調(diào)節(jié)器單片機控制的二級倒立擺系統(tǒng)的研究基于增強型51系列單片機的TCP/IP協(xié)議棧的實現(xiàn)基于單片機的蓄電池自動監(jiān)測系統(tǒng)基于32位嵌入式單片機系統(tǒng)的圖像采集與處理技術(shù)的研究基于單片機的作物營養(yǎng)診斷專家系統(tǒng)的研究基于單片機的交流伺服電機運動控制系統(tǒng)研究與開發(fā)基于單片機的泵管內(nèi)壁硬度測試儀的研制基于單片機的自動找平控制系統(tǒng)研究基于C8051F040單片機的嵌入式系統(tǒng)開發(fā)基于單片機的液壓動力系統(tǒng)狀態(tài)監(jiān)測儀開發(fā)模糊Smith智能控制方法的研究及其單片機實現(xiàn)一種基于單片機的軸快流CO〈,2〉激光器的手持控制面板的研制基于雙單片機沖床數(shù)控系統(tǒng)的研究基于CYGNAL單片機的在線間歇式濁度儀的研制基于單片機的噴油泵試驗臺控制器的研制基于單片機的軟起動器的研究和設(shè)計基于單片機控制的高速快走絲電火花線切割機床短循環(huán)走絲方式研究基于單片機的機電產(chǎn)品控制系統(tǒng)開發(fā)基于PIC單片機的智能手機充電器基于單片機的實時內(nèi)核設(shè)計及其應(yīng)用研究基于單片機的遠程抄表系統(tǒng)的設(shè)計與研究基于單片機的煙氣二氧化硫濃度檢測儀的研制基于微型光譜儀的單片機系統(tǒng)單片機系統(tǒng)軟件構(gòu)件開發(fā)的技術(shù)研究基于單片機的液體點滴速度自動檢測儀的研制基于單片機系統(tǒng)的多功能溫度測量儀的研制基于PIC單片機的電能采集終端的設(shè)計和應(yīng)用基于單片機的光纖光柵解調(diào)儀的研制氣壓式線性摩擦焊機單片機控制系統(tǒng)的研制基于單片機的數(shù)字磁通門傳感器基于單片機的旋轉(zhuǎn)變壓器-數(shù)字轉(zhuǎn)換器的研究基于單片機的光纖Bragg光柵解調(diào)系統(tǒng)的研究單片機控制的便攜式多功能乳腺治療儀的研制基于C8051F020單片機的多生理信號檢測儀基于單片機的電機運動控制系統(tǒng)設(shè)計Pico專用單片機核的可測性設(shè)計研究基于MCS-51單片機的熱量計基于雙單片機的智能遙測微型氣象站MCS-51單片機構(gòu)建機器人的實踐研究基于單片機的輪軌力檢測基于單片機的GPS定位儀的研究與實現(xiàn)基于單片機的電液伺服控制系統(tǒng)用于單片機系統(tǒng)的MMC卡文件系統(tǒng)研制基于單片機的時控和計數(shù)系統(tǒng)性能優(yōu)化的研究基于單片機和CPLD的粗光柵位移測量系統(tǒng)研究單片機控制的后備式方波UPS提升高職學(xué)生單片機應(yīng)用能力的探究基于單片機控制的自動低頻減載裝置研究基于單片機控制的水下焊接電源的研究基于單片機的多通道數(shù)據(jù)采集系統(tǒng)基于uPSD3234單片機的氚表面污染測量儀的研制基于單片機的紅外測油儀的研究96系列單片機仿真器研究與設(shè)計基于單片機的單晶金剛石刀具刃磨設(shè)備的數(shù)控改造基于單片機的溫度智能控制系統(tǒng)的設(shè)計與實現(xiàn)基于MSP430單片機的電梯門機控制器的研制基于單片機的氣體測漏儀的研究基于三菱M16C/6N系列單片機的CAN/USB協(xié)議轉(zhuǎn)換器基于單片機和DSP的變壓器油色譜在線監(jiān)測技術(shù)研究基于單片機的膛壁溫度報警系統(tǒng)設(shè)計基于AVR單片機的低壓無功補償控制器的設(shè)計基于單片機船舶電力推進電機監(jiān)測系統(tǒng)基于單片機網(wǎng)絡(luò)的振動信號的采集系統(tǒng)基于單片機的大容量數(shù)據(jù)存儲技術(shù)的應(yīng)用研究基于單片機的疊圖機研究與教學(xué)方法實踐基于單片機嵌入式Web服務(wù)器技術(shù)的研究及實現(xiàn)基于AT89S52單片機的通用數(shù)據(jù)采集系統(tǒng)基于單片機的多道脈沖幅度分析儀研究機器人旋轉(zhuǎn)電弧傳感角焊縫跟蹤單片機控制系統(tǒng)基于單片機的控制系統(tǒng)在PLC虛擬教學(xué)實驗中的應(yīng)用研究基于單片機系統(tǒng)的網(wǎng)絡(luò)通信研究與應(yīng)用基于PIC16F877單片機的莫爾斯碼自動譯碼系統(tǒng)設(shè)計與研究基于單片機的模糊控制器在工業(yè)電阻爐上的應(yīng)用研究基于雙單片機沖床數(shù)控系統(tǒng)的研究與開發(fā)基于Cygnal單片機的μC/OS-Ⅱ的研究基于單片機的一體化智能差示掃描量熱儀系統(tǒng)研究