【文章內(nèi)容簡介】 所有這些經(jīng)典編碼方法，都是通過以 短碼來表示常出現(xiàn)的符號(hào)這個(gè)原則來實(shí)現(xiàn)概率的均勻化，從而得到高的信息載荷效率；同時(shí)，通過遵守克拉夫特不等式關(guān)系來實(shí)現(xiàn)碼字的唯一可譯。 編碼的逆過程，利用不同編碼方法實(shí)現(xiàn)的生成的碼字通過其相應(yīng)方法實(shí)現(xiàn)對碼字的譯碼，還原出從信源輸入的信息。進(jìn)行編碼是為了壓縮信源符號(hào)的冗余度，在傳輸、譯碼后，還能恢復(fù)出原始信息。 二、 算術(shù)解碼的理論基礎(chǔ) 算術(shù)編碼算法的基本原理 算術(shù)編碼是一種無失真的編碼方法，能有效地壓縮信源冗余度，使編成的碼率趨于信的熵 ，它是無損壓縮的一種。算術(shù)編碼的基本原理是：根據(jù)信源可能發(fā)現(xiàn)的不 同符號(hào)序列的概率，把 [0 ， 1) 區(qū)間劃分為互不重疊的子區(qū)間，子區(qū)間的寬度恰好是各符號(hào)序列概率 。 這樣信源發(fā)出的不同符號(hào)序列將與各子區(qū)間一一對應(yīng) ， 因此每個(gè)子區(qū)間內(nèi)的任意個(gè)實(shí)數(shù)都可以用來表示對應(yīng)的符號(hào)序列，這個(gè)數(shù)就是該符號(hào)序列所對應(yīng)的碼字。顯然 ，串符號(hào)序列發(fā)生的概率越大，對應(yīng)的子區(qū)間就越寬，要表達(dá)它所用的比特?cái)?shù)就減少，因相應(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ù)編碼在對符號(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ù)編碼的原因是因?yàn)槭孪戎谰_的信源概率是很難的，而且是不切 7 實(shí)際的。當(dāng)壓縮消息時(shí)，我們不能期待一個(gè)算術(shù)編碼器獲得最大的效率， 所能做的最有效的方法是在編碼過程中估算概率。盡管從編碼效率上看不如已知概率表的情況，但正是由于算術(shù)編碼自適應(yīng)的調(diào)整對個(gè)符號(hào)概率的估 計(jì)值，這點(diǎn)比哈弗曼編碼相比，具有實(shí)時(shí)性好 、 靈活性高 、 適應(yīng)性強(qiáng)等特點(diǎn)，在圖像壓縮、視頻圖像編碼等領(lǐng)域都得到了廣泛的應(yīng)用。 算術(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 成員對多幅圖像 的測試結(jié)果表明，算術(shù)編碼比霍夫曼編碼提高了 10%左右的效率，因此在 JPEG 擴(kuò)展系統(tǒng)中用算術(shù)編碼取代霍夫曼編碼。 算術(shù)編碼雖然具有其獨(dú)特的優(yōu)點(diǎn)，但我們?nèi)孕枰⒁庀旅鎺讉€(gè)問題： （ 1）由于實(shí)際的計(jì)算機(jī)的精度不可能無限長，運(yùn)算中出現(xiàn)溢出是一個(gè)明顯的問題，但多 數(shù)機(jī)器都有 16 位、 32 位或者 64 位的精度，因此這個(gè)問題可使用比例縮放方法解決。 （ 2）算術(shù)編碼器對整個(gè)消息只產(chǎn)生一個(gè)碼字，這個(gè)碼字是在間隔 [0, 1)中的一個(gè)實(shí)數(shù)， 因此譯碼器在接受到表示這個(gè)實(shí)數(shù)的所有位之前不能進(jìn)行譯碼。 （ 3）算術(shù)編碼也是 一種對錯(cuò)誤很敏感的編碼方法，如果有一位發(fā)生錯(cuò)誤就會(huì)導(dǎo)致整個(gè)消 息譯錯(cuò)。算術(shù)編碼隨著序列長度的增加，相應(yīng)子區(qū)間的寬度也不斷縮小，要表示這段子區(qū)間所需精度，直觀地說就是比特?cái)?shù)也不斷增加。這不但要占用相當(dāng)大的存儲(chǔ)空間，還增加了編碼延時(shí)，這對實(shí)時(shí)系統(tǒng)是十分不利的。為了解決這些難點(diǎn)，針對不同的應(yīng)用方向，人們對傳統(tǒng)的算術(shù)編碼方法進(jìn)行了改進(jìn)，在保證足夠精度的前提下，提高了編碼速度?；谒阈g(shù)編碼算法人們提出了二進(jìn)制自適應(yīng)的算術(shù)編碼以及 MQ 算術(shù)編碼器，分別在軟件及上提高編碼的效率。 算術(shù)編碼的分析過程 在算術(shù)編碼 中，消息用 0 到 1 之間的實(shí)數(shù)進(jìn)行編碼，算術(shù)編碼用到兩個(gè)基本的參數(shù)：符號(hào)的概率和它的編碼間隔。信源符號(hào)的概率決定壓縮編碼的效率，也決定編碼過程中信源符號(hào)的間隔，而這些間隔包含在 0 到 1 之間。編碼過程中的間隔決定了符號(hào)壓縮后的輸出。算 8 術(shù)編碼的過程，實(shí)際上就是依據(jù)信源符號(hào)的發(fā)生概率對碼區(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ī)律對輸入信息進(jìn)行編碼。 圖 算術(shù)編碼的譯碼分析框圖 讀取編碼結(jié)果，找到所屬區(qū)間范圍從而譯出碼字。靜態(tài)型算術(shù)編碼的編碼值是變化的然后找所對應(yīng)的區(qū)間；自適應(yīng)型算術(shù)編碼的編碼值是不變的，只需改變概率區(qū)間，然后用此 9 編碼值找到所對應(yīng)的區(qū)間，從而譯出碼字。 （ 1） 靜態(tài)算術(shù) 編碼舉例 假設(shè)一則消息 “static_tree”具有如下的概率分布： 字符 概率 _ a e r s t 下面用算術(shù)編碼方法給該消息編碼。 一旦字符的概率已知，就沿著 “概率線 ”為每一個(gè)單獨(dú)的符號(hào)設(shè)定一個(gè)范圍，哪一個(gè)被設(shè)定到哪一段范圍并不重要，只要編碼和解碼都以同樣方式進(jìn)行就可以，這里所用的 6 個(gè)字符被分配的范圍（ range）如下： 字符 概率 范圍 _ 0≤r a ≤r e ≤r r ≤r s ≤r t ≤r 對 “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。 （ 2） 對消息第一字符 s 編碼： s 的 range low=， s 的 range high= 因此，下一個(gè)區(qū)間的 low 和 high 為： Low=low+rangerange low=0+1= High=low+rangerange high=0+1= Range=highlow==