信源編碼

對輸入信息進行編碼，優化信息和壓縮信息並且打成符合標準的數據包。

信源編碼的作用之一是，即通常所説的數據壓縮；作用之二是將信源的模擬信號轉化成數字信號，以實現模擬信號的數字化傳輸。

最原始的信源編碼就是莫爾斯電碼，另外還有ASCII碼和電報碼都是信源編碼。但現代通信應用中常見的信源編碼方式有：Huffman編碼、算術編碼、L-Z編碼，這三種都是無損編碼，另外還有一些有損的編碼方式。信源編碼的目標就是使信源減少冗餘，更加有效、經濟地傳輸，最常見的應用形式就是壓縮。

另外，在數字電視領域，信源編碼包括 通用的MPEG—2編碼和H.264（MPEG—Part10 AVC）編碼等。

相應地，信道編碼是為了對抗信道中的噪音和衰減，通過增加冗餘，如校驗碼等，來提高抗干擾能力以及糾錯能力。

不同類型的信源，是否存在有每種信源的最佳的信源編碼，這通常是用信源編碼定理來表示。最簡單、最有實用指導意義的信源編碼定理是離散、無記憶型信源的二進制變長編碼的編碼定理。它證明，一定存在一種無失真編碼，當把N個符號進行編碼時，平均每個符號所需二進碼的碼長滿足

。

其中H（U）是信源的符號熵（比特），這就是説，最佳的信源編碼應是與信源信息熵H（U）統計匹配的編碼，代碼長度可接近符號熵。這一結論不僅表明最佳編碼存在，而且還給出具體構造碼的方法，即按概率特性編成不等長度碼。對不同類型信源，如離散或連續、無或有記憶、平穩或非平穩、無或限定失真等，可以構成不同的組合信源，它們都存在各自的信源編碼定理。但它們中絕大部分僅是屬於理論上的存在性定理，這給具體尋找和實現不同類型信源的信源編碼，帶來了相當的難度。

信源編碼根據信源的性質進行分類，則有信源統計特性已知或未知、無失真或限定失真、無記憶或有記憶信源的編碼；按編碼方法進行分類可分為分組碼或非分組碼、等長碼或變長碼等。然而最常見的是討論統計特性已知條件下，離散、平穩、無失真信源的編碼，消除這類信源剩餘度的主要方法有統計匹配編碼和解除相關性編碼。比如仙農碼、費諾碼、赫夫曼碼，它們屬於不等長度分組碼，算術編碼屬於非分組碼；預測編碼和變換編碼是以解除相關性為主的編碼。對限定失真的信源編碼則是以信息率失真R（D）函數為基礎，最典型的是矢量量化編碼。對統計特性未知的信源編碼稱為通用編碼。

以簡單的數據壓縮為例即可説明信源編碼的應用。若有一離散、無失真、無記憶信源，它含有五種符號U₀～U₄及其對應概率P_i，對它進行兩種編碼：等長碼和最佳哈夫曼碼（見表1）。

其中，等長碼的平均碼長：=3，即三位碼。若採用哈夫曼編碼，平均碼長

，即不足兩位碼。這就是説，數據壓縮了以上。

[信源]->[信源編碼]->[信道編碼]->[信道傳輸+噪聲]->[信道解碼]->[信源解碼]->[信宿]

一般信息論的書上都會有信源編碼和信道編碼的具體講解，包括具體的編碼方法。

既然信源編碼的基本目的是提高碼字序列中碼元的平均信息量，那麼，一切旨在減少剩餘度而對信源輸出符號序列所施行的變換或處理，都可以在這種意義下歸入信源編碼的範疇，例如過濾、預測、域變換和數據壓縮等。當然，這些都是廣義的信源編碼。

一般來説，減少信源輸出符號序列中的剩餘度、提高符號平均信息量的基本途徑有兩個：①使序列中的各個符號儘可能地互相獨立；②使序列中各個符號的出現概率儘可能地相等。前者稱為解除相關性，後者稱為概率均勻化。

信源編碼的一般問題可以表述如下：若某信源的輸出為長度等於M的符號序列集合 式中符號A為信源符號表，它包含着K個不同的符號，A={ɑk|k=1,…,K}，這個信源至多可以輸出KM個不同的符號序列。記‖U‖=KM。所謂對這個信源的輸出進行編碼，就是用一個新的符號表B的符號序列集合V來表示信源輸出的符號序列集合U。若V的各個序列的長度等於 N，即 式中新的符號表B共含L個符號，B={bl|l=1,…,L}。它總共可以編出LN個不同的碼字。類似地,記‖V‖=LN。為了使信源的每個輸出符號序列都能分配到一個獨特的碼字與之對應，至少應滿足關係 ‖V‖=LN≥‖U‖=KM

或者 N/M≥logK/logL

假若編碼符號表B的符號數L與信源符號表A的符號數K相等，則編碼後的碼字序列的長度N必須大於或等於信源輸出符號序列的長度M；反之，若有N=M，則必須有L≥K。只有滿足這些條件，才能保證無差錯地還原出原來的信源輸出符號序列(稱為碼字的唯一可譯性)。可是，在這些條件下，碼字序列的每個碼元所載荷的平均信息量不但不能高於，反而會低於信源輸出序列的每個符號所載荷的平均信息量。這與編碼的基本目標是直接相矛盾的。下面的幾個編碼定理，提供瞭解決這個矛盾的方法。它們既能改善信息載荷效率，又能保證碼字唯一可譯。

對於任意給定的ε>0，只要滿足條件 N/M≥(H(U)+ε)/logL

那麼，當M足夠大時，上述編碼幾乎沒有失真;反之,若這個條件不滿足，就不可能實現無失真的編碼。式中H(U)是信源輸出序列的符號熵。通常，信源的符號熵H(U)K，因此，上述條件還可以表示為 【H(U)+ε】/logL≤N/M≤logK/logL

特別，若有K=L,那麼,只要H(U)K,就可能有N<M，從而提高信息載荷的效率。由上面這個條件可以看出，H(U)離logK越遠,通過編碼所能獲得的效率改善就越顯著。實質上，定長編碼方法提高信息載荷能力的關鍵是利用了漸近等分性，通過選擇足夠大的M，把本來各個符號概率不等[因而H(U)K]的信源輸出符號序列變換為概率均勻的典型序列，而碼字的唯一可譯性則由碼字的定長性來解決。

變長編碼是指V的各個碼字的長度不相等。只要V中各個碼字的長度 Ni(i=1，…，‖V‖)滿足克拉夫特不等式 這 ‖V‖個碼字就能唯一地正確劃分和譯碼。離散無記憶信源的變長編碼定理指出：若離散無記憶信源的輸出符號序列為， 式中 A={ɑk|k=1,…,K},符號熵為H(U)，對U進行唯一可譯的變長編碼，編碼字母表B的符號數為L,即B={bl|l=1,…,L},那麼必定存在一種編碼方法，使編出的碼字Vi=(vi1,…,viNi)，(i=1,…,‖V‖)，具有平均長度嚻： MH(U)/logL≤嚻<MH(U)/logL+1

若L=K，則當H(U)K=logL時,必有嚻<M；H(U)離logK越遠，則嚻越小於M。

具體實現唯一可譯變長編碼的方法很多，但比較經典的方法還是仙農編碼法、費諾編碼法和霍夫曼編碼法。其他方法都是這些經典方法的變形和發展。所有這些經典編碼方法，都是通過以短碼來表示常出現的符號這個原則來實現概率的均勻化，從而得到高的信息載荷效率；同時，通過遵守克拉夫特不等式關係來實現碼字的唯一可譯。

霍夫曼編碼方法的具體過程是：首先把信源的各個輸出符號序列按概率遞降的順序排列起來，求其中概率最小的兩個序列的概率之和，並把這個概率之和看作是一個符號序列的概率，再與其他序列依概率遞降順序排列（參與求概率之和的這兩個序列不再出現在新的排列之中），然後，對參與概率求和的兩個符號序列分別賦予二進制數字0和1。繼續這樣的操作,直到剩下一個以1為概率的符號序列。最後，按照與編碼過程相反的順序讀出各個符號序列所對應的二進制數字組，就可分別得到各該符號序列的碼字。

例如，某個離散無記憶信源的輸出符號序列及其對應的概率分佈為對這些輸出符號序列進行霍夫曼編碼的具體步驟和結果如表。由表中可

以看出，在碼字序列中碼元0和1的概率分別為10/21和11/21，二者近乎相等，實現了概率的均勻化。同時，由於碼字序列長度滿足克拉夫特不等式 2×2-2+3×2-3+2×2-4=1

因而碼字是唯一可譯的，不會在長的碼字序列中出現劃錯碼字的情況。

以上幾個編碼定理，在有記憶信源或連續信源的情形也有相應的類似結果。在實際工程應用中，往往並不追求無差錯的信源編碼和譯碼，而是事先規定一個譯碼差錯率的容許值，只要實際的譯碼差錯率不超過這個容許值即認為滿意（見信息率-失真理論和多用户信源編碼）。