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