【正文】 0≤r a ≤r e ≤r r ≤r s ≤r t ≤r 對(duì) “state_tree”的算術(shù)編碼過程為： 初始化時(shí) ， 被分割的范圍 range=highlow=[0,1） ,下一個(gè)范圍的低、高端分別由下式計(jì)算： Low=low+rangerange low High=low+rangerange high 10 其中等號(hào)右邊的 low 為上一個(gè)被編碼字符的范圍低； range low 和 range high 分別為被編碼符號(hào)已給定的字符出現(xiàn)概率范圍的 low 和 high。靜態(tài)型算術(shù)編碼的編碼值是變化的然后找所對(duì)應(yīng)的區(qū)間；自適應(yīng)型算術(shù)編碼的編碼值是不變的，只需改變概率區(qū)間，然后用此 9 編碼值找到所對(duì)應(yīng)的區(qū)間，從而譯出碼字。 算術(shù)編碼的編碼分析框圖如下： 圖 算術(shù)編碼的編碼分析框圖 靜態(tài)算術(shù)編碼和自適應(yīng)型算術(shù)編碼在編碼前都需要初始化概率空間，靜態(tài)算術(shù)編碼的字符概率是固定的，因此找到相應(yīng)的概率空間可直接按區(qū)間 分割進(jìn)行編碼；自適應(yīng)型算術(shù)編碼在編碼前需要統(tǒng)計(jì)輸入的文本信息的符號(hào)類型和每個(gè)符號(hào)的個(gè)數(shù)，期初假定每個(gè)符號(hào)概率相等，然后輸入一個(gè)符號(hào)后，找到相應(yīng)的概率空間所有的符號(hào)概率會(huì)進(jìn)行更新，然后依次規(guī)律對(duì)輸入信息進(jìn)行編碼。編碼過程中的間隔決定了符號(hào)壓縮后的輸出。 算術(shù)編碼的分析過程 在算術(shù)編碼 中，消息用 0 到 1 之間的實(shí)數(shù)進(jìn)行編碼，算術(shù)編碼用到兩個(gè)基本的參數(shù)：符號(hào)的概率和它的編碼間隔。為了解決這些難點(diǎn)，針對(duì)不同的應(yīng)用方向，人們對(duì)傳統(tǒng)的算術(shù)編碼方法進(jìn)行了改進(jìn)，在保證足夠精度的前提下，提高了編碼速度。算術(shù)編碼隨著序列長度的增加，相應(yīng)子區(qū)間的寬度也不斷縮小，要表示這段子區(qū)間所需精度，直觀地說就是比特?cái)?shù)也不斷增加。 （ 2）算術(shù)編碼器對(duì)整個(gè)消息只產(chǎn)生一個(gè)碼字，這個(gè)碼字是在間隔 [0, 1)中的一個(gè)實(shí)數(shù)， 因此譯碼器在接受到表示這個(gè)實(shí)數(shù)的所有位之前不能進(jì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)的想法，用一個(gè)浮點(diǎn)輸出數(shù)值 代替一個(gè)流的輸入符號(hào)，較長的復(fù)雜的消息輸出的數(shù)值中就需要更多的位數(shù)； （ 4）算術(shù)編碼實(shí)現(xiàn)方法復(fù)雜一些，但 JPEG 成員對(duì)多幅圖像 的測試結(jié)果表明，算術(shù)編碼比霍夫曼編碼提高了 10%左右的效率，因此在 JPEG 擴(kuò)展系統(tǒng)中用算術(shù)編碼取代霍夫曼編碼。當(dāng)壓縮消息時(shí)，我們不能期待一個(gè)算術(shù)編碼器獲得最大的效率， 所能做的最有效的方法是在編碼過程中估算概率。信源符號(hào)的概率根據(jù)編碼時(shí)符號(hào)出現(xiàn)的頻繁程度動(dòng)態(tài)地進(jìn)行修改，在編碼期間估算信源符號(hào)概率的過程叫做建模。本課程設(shè)計(jì)中以靜態(tài)算術(shù)編碼算法進(jìn)行仿真。 算術(shù)編碼可以是靜態(tài)的或者自適應(yīng)的。 這樣信源發(fā)出的不同符號(hào)序列將與各子區(qū)間一一對(duì)應(yīng) ， 因此每個(gè)子區(qū)間內(nèi)的任意個(gè)實(shí)數(shù)都可以用來表示對(duì)應(yīng)的符號(hào)序列，這個(gè)數(shù)就是該符號(hào)序列所對(duì)應(yīng)的碼字。 二、 算術(shù)解碼的理論基礎(chǔ) 算術(shù)編碼算法的基本原理 算術(shù)編碼是一種無失真的編碼方法，能有效地壓縮信源冗余度，使編成的碼率趨于信的熵 ，它是無損壓縮的一種。 編碼的逆過程，利用不同編碼方法實(shí)現(xiàn)的生成的碼字通過其相應(yīng)方法實(shí)現(xiàn)對(duì)碼字的譯碼，還原出從信源輸入的信息。其他方法都是這些經(jīng)典方法的變形和發(fā)展。離散無記憶信源的變長編碼定理指出：若離散無記憶信源的輸出符號(hào)序列為 ， 式中 A＝｛ ɑk|k=1,? ,K｝ ,符號(hào)熵為 H(U)，對(duì) U進(jìn) 行唯一可譯的變長編碼，編碼字母表B 的符號(hào)數(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 時(shí) ,必有嚻＜ M； H(U)離 logK 越遠(yuǎn)，則嚻越小于 M。只要 V中各個(gè)碼字的長度 Ni(i＝ 1，?，‖ V‖ ) 6 滿足克拉夫特不等式。實(shí)質(zhì)上，定長編碼方法提高信息載荷能力的關(guān)鍵是利用了漸近等分性 ,通過選擇足夠大的 M,把本 來各個(gè)符號(hào)概率不等［因而 H(U)＜ logK］的信源輸出符號(hào)序列變換為概率均勻的典型序列，而碼字的唯一可譯性則由碼字的定長性來解決。 特別 ,若有 K＝ L,那么 ,只要 H(U)＜ logK,就可能有 N＜ M，從而提高信息載荷的效率。式中 H(U)是信源輸出序列的符號(hào)熵。 (1)離散無記憶信源的定長編碼定理 對(duì)于任意給定的 ε ＞ 0，只要滿足條件 N/M≥ (H(U)+ε )/logL 那么 ,當(dāng) M 足夠大時(shí) ,上述編碼幾乎沒有失真 。下面的幾個(gè)編碼定理，提供了解決這個(gè)矛盾的方法?？墒牵谶@些條件下，碼字序列的每個(gè)碼元所載荷的平均信息量不但不能高于，反而會(huì)低于信源輸出序列的每個(gè)符號(hào)所載荷的平均信息量。為了使信源的每個(gè)輸出符號(hào)序列都能分配到一個(gè)獨(dú)特的碼字與之對(duì)應(yīng)，至少應(yīng)滿足關(guān)系 ‖ V‖＝ L≥‖ U‖＝ K，或者 N/M≥ logK/logL； 假若編碼符號(hào)表 B 的符號(hào)數(shù) L與信源符號(hào)表 A的符號(hào)數(shù) K 相等，則編碼后的碼字序列的長度 N必須大于或等于信源輸出 符號(hào)序列的長度 M；反之，若有 N＝ M，則必須有 L≥ K。它總共可以編出 L 個(gè)不同的碼字。所謂對(duì)這個(gè)信源的輸出進(jìn)行編碼，就是用一個(gè)新的符號(hào)表 B 的符號(hào)序列集合 V 來表示信源輸出的符號(hào)序列集合 U。 5 信源編碼的一般問題可以表述如下：若某信源的輸出為長度等于 M 的符號(hào)序列集合 式中符號(hào) A 為信源符號(hào)表，它包含著 K 個(gè)不同的符號(hào)， A=｛ ɑk|k=1,? ,K｝，這個(gè)信源至多可以輸出 K 個(gè)不同的符號(hào)序列。 一般來說，減少信源輸出符號(hào)序列中的剩余度、提高符號(hào)平均信息量的基本途徑有兩個(gè)： 一是使序列中的各個(gè)符號(hào)盡可能地互相獨(dú)立； 二是使序列中各個(gè)符號(hào)的出現(xiàn)概率盡可能地相等。 概率均勻化：使編碼中各個(gè)符號(hào)出現(xiàn)的概率盡可能地相等。 針對(duì)信源輸出符號(hào)序列的統(tǒng)計(jì)特性，尋找一定的方法把信源輸出符號(hào)序列變換為最短的碼字序列。 以上幾個(gè)編碼定理，在有記憶信源或連續(xù)信 源的情形也有相應(yīng)的類似結(jié)果。 表 11 由表中可以看出，在碼字序列中碼元 0 和 1 的概率分別為 10/21 和 11/21，二者近乎相等，實(shí)現(xiàn)了概率的均勻化。最后，按照與編碼過程相反的順序讀出各 個(gè)符號(hào)序列所對(duì)應(yīng)的二進(jìn)制數(shù)字組，就可分別得到各該符號(hào)序列的碼字。 霍夫曼編碼方法的具體過程是：首先把信源的各個(gè)輸出符號(hào)序列按概率遞降的順序排列起來，求其中概率最小的兩個(gè)序列的概率之和，并把這個(gè)概率之和看作是一個(gè)符號(hào)序列的概率，再與其他序列依概率遞降順序排列（參與求概率之和的這兩個(gè)序列不再出現(xiàn)在新的排列之中），然后，對(duì)參與概率求和的兩個(gè)符號(hào)序列分別賦予二進(jìn)制數(shù)字 0 和 1。其他方法都是這些經(jīng)典方法的變形和發(fā)展。離散無記憶信源的變長編碼定理指出：若離散無記憶信源的輸出符號(hào)序列 ， 式中 A＝｛ ɑk|k=1,? ,K｝ ,符號(hào)熵為 H(U)，對(duì) U進(jìn)行 唯一可譯的變長編碼，編碼字母表 B 的符號(hào)數(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 時(shí) ,必有嚻＜ M； H(U)離 logK 越遠(yuǎn)，則嚻越小于 M。只要 V中各個(gè)碼字的長度 Ni(i＝ 1， ? ， ‖ V‖ )滿足克拉夫特不等式 。實(shí)質(zhì)上，定長編碼方法 提高信息載荷能力的關(guān)鍵是利用了漸近等分性 ,通過選擇足夠大的 M,把本來各個(gè)符號(hào)概率不等［因而 H(U)＜ logK］的信源輸出符號(hào)序列變換為概率均勻的典型序列，而碼字的唯一可譯性則由碼字的定長性來解決。 通常 ,信源的符號(hào)熵 H(U)＜ logK，因此 ,上述條件還可以表示為 【 H(U)+ε 】/logL≤ N/M≤ logK/logL