【正文】 的主要任務(wù) 就是減少冗余，提高編碼效率。具體說，就是針對信源輸出符號序列的統(tǒng)計特性來尋找某種方法，把信源輸出符號序列變換為最短的碼字序列，使后者的各碼元所載荷的平均信息量最大，同時又能保證無失真地恢復(fù)原來的符號序列。采用的一般方法是壓縮每個信源符號的平均比特數(shù)或信源的碼率。 2 ： 信源存在冗余度。 信源編碼的主要任務(wù)就是減少冗余，提高編碼效率。 通常通過壓縮信源的冗余度來實現(xiàn)。 一 般來說，減少信源輸出符號序列中的剩余度、提高符號平均信息量的基本途徑有兩個：① 使序列中的 各個符號盡可能地互相獨立； ② 使序列中各個符號的出現(xiàn)概率盡可能地相等。 信源編碼的一般問題可以表述如下：若某信源的輸出為長度等于 M 的符號序列集合 式中符號 A 為信源符號表，它包含著 K 個不同的符號， A=｛ ɑk|k=1,? ,K｝，這個信源至多可以輸出 K 個不同的符號序列。所謂對這個信源的輸出進(jìn)行編碼，就是用一個新 的符號表 B 的符號序列集合 V來表示信源輸出的符號序列集合 U。它總共可以編出 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?？墒牵谶@些條件下，碼字序列的每個碼元所載荷的平均信息量不但不能高于，反而會低于信源輸出序列的每個符號所載荷的平均信息量。下面的幾個編碼定理，提供了解決這個矛盾的方法。 離 散 無 記 憶 信源 的 定 長編 碼 定 理對 于 任 意 給定 的 ε ＞ 0 ， 只 要滿 足 條 件 3 N/M≥ (H(U)+ε )/logL 那么 ,當(dāng) M 足夠大時 ,上述編碼幾乎沒有失真 。式中 H(U)是信源輸出序列的符號熵。由上面這個條件可以看出， H(U)離 logK 越遠(yuǎn) ,通過編碼所能獲得的效率改善就越顯著。 離散無記憶信源的變長編碼定理變長編碼是指 V的各個碼字的長度不相等。 這 ‖ V‖ 個碼字就能唯一地正確劃分和譯碼。 具體實現(xiàn)唯一可譯變長編碼的方法很多，但比較經(jīng)典的方法還是仙農(nóng)編碼法、費諾編碼法和霍夫曼編碼法。所有這些經(jīng)典編碼方法，都是通過以短碼來表示 常出現(xiàn)的符號這個原則來實現(xiàn)概率的均勻化，從而得到高的信息載荷效率；同時，通過遵守克拉夫特不等式關(guān)系來實現(xiàn)碼字的唯一可譯。繼續(xù)這樣的操作 ,直到剩下一個以 1 為概率的符號序列。 例如，某個離散無記憶信源的輸出符號序列及其對應(yīng)的概率分布為 4 對這些輸出符號序列進(jìn)行霍夫曼編碼的具體步驟和結(jié)果如表。同時，由于碼字序列長度滿足克拉夫特不等式 22+32+22＝ 1 因而碼字是唯一可譯的，不會在長的碼字序列中出現(xiàn)劃錯碼字的情況。在實際工程應(yīng)用中，往往并不追求無差錯的信源編碼和譯碼，而是事先規(guī)定一個譯碼差錯率的容許值，只要實際的譯碼差錯率不超過這個容許值即認(rèn)為滿意（見信息率 失真理論和多用戶 信源編碼）。 解除相關(guān)性：使序列中的各個符號盡可能地互相獨立。 信源編碼的實現(xiàn)方法： 離散信源編碼有香農(nóng)編碼、費諾編碼、赫夫曼編碼、游程編碼、冗余位編碼；連續(xù)信源編碼有最 佳標(biāo)量量化、矢量量化；相關(guān)信源編碼的預(yù)測編碼、差值編碼；變換編碼的子帶編碼、小波變換。前者稱為解除相關(guān)性，后者稱為概率均勻化。 記‖ U‖ =K。若 V 的各個序列的長度等于 I，即 式中新的符號表 B 共含 L 個符號， B=｛ bl|l=1,? ,L｝。類似地 ,記‖ V‖＝ L。只有滿足這些條件，才能保證無差錯地還原出原來的信源輸出符號序列 (稱為碼字的唯一可譯性 )。這與編碼的基本目標(biāo)是直接相矛盾的。它們既能改善信息載荷效率，又能保證碼字唯一可譯。反之 ,若這個條件不滿足，就不可能實現(xiàn)無失真的編碼。 通常 ,信源的符號熵 H(U)＜ logK，因此 ,上述條件還可以表示為 【 H(U)+ε 】 /logL≤ N/M≤ logK/logL。由上面這個條件可以看出， H(U)離 logK 越遠(yuǎn) ,通過編碼所能獲得的效率改善就越顯著。 (2)離散無記憶信源的變長編碼定理 變長編碼是指 V的各個碼字的長度不相等。 這 ‖ V‖個碼字就能唯一地正確劃分和譯碼。 具體實現(xiàn)唯一可譯變長編碼的方法很多，但比較經(jīng)典的方法還是仙農(nóng)編碼法、費諾編碼法和霍夫曼編碼法。所有這些經(jīng)典編碼方法，都是通過以 短碼來表示常出現(xiàn)的符號這個原則來實現(xiàn)概率的均勻化，從而得到高的信息載荷效率；同時，通過遵守克拉夫特不等式關(guān)系來實現(xiàn)碼字的唯一可譯。進(jìn)行編碼是為了壓縮信源符號的冗余度，在傳輸、譯碼后，還能恢復(fù)出原始信息。算術(shù)編碼的基本原理是：根據(jù)信源可能發(fā)現(xiàn)的不 同符號序列的概率，把 [0 ， 1) 區(qū)間劃分為互不重疊的子區(qū)間，子區(qū)間的寬度恰好是各符號序列概率 。顯然 ，串符號序列發(fā)生的概率越大，對應(yīng)的子區(qū)間就越寬，要表達(dá)它所用的比特數(shù)就減少，因相應(yīng)的碼字就越短。在靜態(tài)算術(shù)編碼中，信源符號的概率是固定的 。在自適應(yīng)算術(shù)編碼中，自適應(yīng)算術(shù)編碼在對符號序 列進(jìn)行掃描的過程中，可一次完成兩個過程，即根據(jù)恰當(dāng)?shù)母怕使烙嬆Ｐ秃彤?dāng)前符號序列中各符號出現(xiàn)的頻率，自適應(yīng)地調(diào)整各符號的概率估計值，同時完成編碼。需要開發(fā)態(tài)算術(shù)編碼的原因是因為事先知道精確的信源概率是很難的，而且是不切 7 實際的。盡管從編碼效率上看不如已知概率表的情況，但正是由于算術(shù)編碼自適應(yīng)的調(diào)整對個符號概率的估 計值，這點比哈弗曼編碼相比，具有實時性好 、 靈活性高 、 適應(yīng)性強(qiáng)等特點，在圖像壓縮、視頻圖像編碼等領(lǐng)域都得到了廣泛的應(yīng)用。 算術(shù)編碼雖然具有其獨特的優(yōu)點，但我們?nèi)孕枰⒁庀旅鎺讉€問題： （ 1）由于實際的計算機(jī)的精度不可能無限長，運算中出現(xiàn)溢出是一個明顯的問題，但多 數(shù)機(jī)器都有 16 位、 32 位或者 64 位的精度，因此這個問題可使用比例縮放方法解決。 （ 3）算術(shù)編碼也是 一種對錯誤很敏感的編碼方法，如果有一位發(fā)生錯誤就會導(dǎo)致整個消 息譯錯。這不但要占用相當(dāng)大的存儲空間，還增加了編碼延時，這對實時系統(tǒng)是十分不利的?；谒阈g(shù)編碼算法人們提出了二進(jìn)制自適應(yīng)的算術(shù)編碼以及 MQ 算術(shù)編碼器，分別在軟件及上提高編碼的效率。信源符號的概率決定壓縮編碼的效率，也決定編碼過程中信源符號的間隔，而這些間隔包含在 0 到 1 之間。算 8 術(shù)編碼的過程，實際上就是依據(jù)信源符號的發(fā)生概率對碼區(qū)間分割的過程。 圖 算術(shù)編碼的譯碼分析框圖 讀取編碼結(jié)果，找到所屬區(qū)間范圍從而譯出碼字。 （ 1） 靜態(tài)算術(shù) 編碼舉例 假設(shè)一則消息 “static_tree”具有如下的概率分布： 字符 概率 _ a e r s t 下面用算術(shù)編碼方法給該消息編碼。 （ 2） 對消息第一字符 s 編碼： s 的 range low=， s 的 range high= 因此，下一個區(qū)間的 low 和 high 為： Low=low+rangerange low=0+1= High=low+rangerange high=0+1= Range=highlow== s 將區(qū)間 [0,1） =[,） (3)對第二個字符 t 編碼，使用的新生范圍為 [,），因為 t 的 range low=,range high=,因此下一個 low,high 分別為 Low=+＝ High=+＝ Range== t 將 [,） =[,） (4)對第三個字符 a 編碼，在新生成的 [,）中進(jìn)行分割，因為 a 的 range low=,range high=,因此下一個 low,high 分別為 Low=+＝