2.3 無失真信源編碼定理

編碼分為信源編碼和信道編碼，其中信源編碼又分為無失真編碼和限失真編碼，無失真信源編碼定理是離散信源編碼的基礎，而限失真信源編碼定理是連續信源編碼的基礎。本節討論無失真信源編碼的相關概念。

通信的目的是信息通過信道進行傳遞，傳遞的過程有兩個重要問題需要注意。一個是在不失真或者允許一定失真條件下，如何用盡可能少的符號來傳遞信息，提高信息的傳輸率，另一個是如何在信道受干擾的情況下增強信號抗干擾能力，提高傳輸可靠性并使信息傳輸率最大。

人們都希望將所有信息沒有任何損失地傳遞到接收端，實現無失真通信，那么首先要對信源進行無差錯編碼。這里重點討論離散信源的無失真編碼定理。

對信源進行編碼，就是設計一個編碼器，將信源的原始符號按照一定的數學規則進行變換，生成適合信道傳輸的符號，通常稱為碼元（碼序列）。

將離散信源輸出信息定義為離散符號集，如下所示：

即，序列中每個符號x_i屬于符號序列X_l，多個X_l構成信源消息組。

那么信源編碼就是將上面的輸出轉換成如下結果：

這種碼元序列，通常稱為碼字，所有碼字集合稱為碼。編碼就是從信源符號到碼元的映射，要想實現無失真信源編碼，這種映射必須一一對應，就是每個信源消息可以編成一個碼字，反之，每個碼字只能翻譯成一個固定消息。這種碼稱為唯一可譯碼。

在給消息分配碼字的時候分配多少可以做到無失真譯碼？碼字越多，所需要的信息率就越大，很明顯，我們希望信息率越小越好，但是信息率小到多少能保證無失真呢？首先要給出關于碼的定義。

（1）二元碼

如果碼符號集為X={0，1}，所得到的碼字都是二元序列，稱為二元碼。

如果將信源通過二元信道進行傳輸，那么就需要將信源符號轉換為由0和1組成的二元碼序列，這也是數字圖像處理最為常用的一種方法。

（2）等長碼（定長碼）

如果一組碼中所有碼字的長度都相等，稱之為等長碼。

（3）變長碼

如果一組碼中所有碼字的長度都不相同，稱之為變長碼。

（4）非奇異碼

如果一組碼中所有碼字都不相同，即所有信源符號映射到不同的碼元序列，它們之間是一一對應的，那么稱之為非奇異碼。

（5）奇異碼

如果一組碼中有相同的碼字，即所有信源符號映射到相同的碼元序列，那么稱之為奇異碼。

（6）同價碼

如果碼符號集中每個碼符號所占用的傳輸時間都相同，則所得到的碼為同價碼。一般來講，二元碼都是同價碼。

（7）碼的N次擴展碼

假設某碼C，它把信源S中的符號s_i轉化成碼C中的碼字W_i，則碼C的N次擴展碼是所有N個碼字組成的碼字序列的集合。

（8）唯一可譯碼

如果碼的任意一串有限長的碼符號序列只能被唯一地譯成所對應的信源符號序列，那么此碼稱為唯一可譯碼。否則就稱為非唯一可譯碼。

可以看出，信源編碼分為定長和變長兩種方法。定長的碼字長度K是固定的，對應的編碼定理叫作定長信源編碼定理，是尋找最小K值的編碼方法。后者的K是變值，對應的編碼定理叫作變長編碼定理。

1.定長編碼定理

一個熵為H（S）的離散無記憶信源，若對信源長為N的符號序列進行等長編碼，假設碼字為從r個字母的碼符號集中選取l個碼元組成，對于任意ε大于0，只要滿足

當N無窮大時，則可以實現幾乎無失真編碼，反之，若

則不可能實現無失真編碼，當N趨向無窮大時，譯碼錯誤率接近1。該公式的證明過程略，讀者感興趣可以參考相關書籍。

上式可以變換為

公式左邊表示長為l的碼符號所能載荷的最大信息量，而右邊代表長為N的序列平均攜帶的信息量。因此，只要碼字傳輸的信息量大于信源序列攜帶的信息量，就可以實現無失真編碼。

上式還可以變換為

假設，表示平均每個符號的信息量，稱之為編碼信息率。可見，只有編碼信息率大于信源的熵，才能實現無失真編碼。也就是說，信源熵其實就是一個臨界值，當編碼器輸出信息率超過該臨界值時，就能無失真編碼，否則就無法不失真。

為了衡量編碼效果，定義

稱之為編碼效率。

那么最佳編碼效率為

該定理也說明，編碼信息率大于單符號熵時，可以做到幾乎無失真，前提是N必須足夠大。可以證明，當方差D[I（x）]和ε均為定值時，只要信源序列長度N滿足

即

譯碼差錯率就一定小于任意正數δ。

接下來看一個示例。考慮一個如下的離散無記憶信源

如果采用等長二元編碼，要求編碼效率η=0.96，允許錯誤率δ≤10^-5，那么N≥4.13×10⁷，也就是說長度要達到4130萬以上，技術實現非常困難，而且編碼效率也不高。為了解決這個問題，就出現了變長編碼。

變長編碼允許把等長消息變成不等長的碼序列，一般情況下把經常出現的消息編成短碼，不經常出現的消息編成長碼，從而使得平均碼長最短，提高通信效率，但是這種方式會增加編譯碼設備的復雜度。

2.變長編碼定理

設離散無記憶信源為

編碼后碼字

碼長為

對唯一可譯碼來講，信源符號與碼字一一對應，因此

碼的平均長度為

當信源給定時，信源的熵就是確定的，編碼后平均每個碼元攜帶的信息量也就是編碼后的信息傳輸率為

如果傳輸一個碼符號平均需要t秒，那么編碼后每秒信息量為

可以看出值越小，信息傳輸效率越高，如果有一個唯一可譯碼，它的平均碼長小于其他唯一可譯碼的長度，則稱此碼為緊致碼（最佳碼），無失真信源編碼的基本問題就是尋找緊致碼。從而就得到如下定理，即無失真變長信源編碼定理（香農第一定理）：

離散無記憶信源S的N次擴展信源S^N，其熵為H（S^N），并且編碼器的碼元符號集為A：{α₁，…，α_q}，對信源S^N進行編碼，總可以找到一種無失真編碼方法，構成唯一可譯碼，使信源S中每個符號s_i所需要的平均碼長滿足

當N→∞時，得到

其中

式中，λ_i是α_i對應的碼字長度，是無記憶擴展信源S^N中每個符號α_i的平均碼長，那么仍然是信源S中每一單個信源符號所需的平均碼長。和兩者都是每個信源符號所需的碼符號的平均數，表示為了得到這個平均值，不是對單個信源符號進行編碼，而是對N個信源符號的序列進行編碼。

這個定理是香農信息論中非常重要的一個定理，它指出，要做到無失真的信源編碼，信源每個符號所需要的平均碼元數就是信源的熵值，如果小于這個值，則唯一可譯碼不存在，在譯碼或反變換時必然帶來失真或差錯，可見，信源的信息熵是無失真信源編碼的極限值。定理還指出，通過對擴展信源進行編碼，當N趨向于無窮時，平均碼長可以趨近該極限值。

由

可以得到

就是編碼后每個信源符號所攜帶的平均信息量。定義

那么香農第一定理就可以表述為：

·如果R′＞H（S），則存在唯一可譯變長碼。

·如果R′＜H（S），則不存在唯一可譯變長碼。

若從信道角度講，信道的信息傳輸率為

由于

所以

當平均碼長達到極限值時，編碼后信道的信息傳輸率為

此時，信道的信息傳輸率等于無噪無損信道的信道容量C，編碼效率最高，即信息傳輸率最高。因此無失真信源編碼的實質就是對離散信源進行適當的變換，使變換后新的符號序列信源盡可能為等概率分布，以使新信源的每個碼符號平均所含的信息量達到最大，從而使信息傳輸率R達到信道容量C，實現信源和信道理想的統計匹配。這是香農第一定理的另一層含義，因此無失真信源編碼實質上就是無噪信道編碼問題。

因此，無失真信源編碼定理又稱為無噪信道編碼定理：若信道的信息傳輸率R不大于信道容量C，總能對信源的輸出進行適當的編碼，使得在無噪無損信道上能無差錯地以最大信息傳輸率C傳輸信息，若信息傳輸率R大于信道容量C，那么無差錯信息傳輸是不可能的。