3.3 信息率—失真理論

本節將從信息論的角度，對在有信息損失情況下數據壓縮的理論極限做較為嚴謹的討論。有信息損失情況下的數據壓縮，就是將信源輸出的數據轉化為簡化的或壓縮的版本，而它的逼真度的損失不超出某一容限。它屬于信源編碼的范疇。

3.3.1 通信系統的一般模型

圖3-3為常見的簡單通信系統模型。我們將信道編、譯碼器歸入信道，所以信道可以看成是無噪聲的。

設信源產生離散隨機過程｛Ur｝，r＝－∞，…，－2，－1，0，1，2，…，∞，即隨機變量序列。u是信源符號U的樣，u∈A，A是信源符號集。信源的特征可以用符號集A以及相應的概率分布表示。A可以是實數集，有限集，波形集，二維空間的亮度分布集，等等。概率特征可記為p，它是一族N維概率密度或分布函數。對信源還可能有平穩、遍歷、獨立、限功率等制約。

設信源為恒速率信源，它每Ts秒產生A的一個符號，即信源符號率Rs為1/Ts。信源編碼器將每個長度為N的信源符號組編為K個編碼符號組成的碼字，編碼符號取自于符號集E，我們將該碼字姑且稱為編碼碼字。若E中包含a個符號，則可能構成的編碼碼字數M＝aK。設信道為恒速率數字信道，它的傳輸率為Rc＝1/Tc，即每Tc秒傳輸一個編碼符號。信源譯碼器將信道輸出還原為長N的、其形式可以為信宿接受的符號組，該符號組稱為還原碼字。由于編碼碼字數為M，還原碼字數也為M。還原碼字串成隨機過程｛Vr｝，v是V的樣，v∈B。B可以等于A，也可以不同于A。為了使全系統有協同的符號流量，須使，即在信源產生N個符號的期間，信道傳輸K個符號，同時譯碼器輸出N個符號。這將保證｛Vr｝與｛Ur｝有相同的符號率，只不過通常二者之間存在遲延而已。

如果編碼器是數據壓縮設備，則定義壓縮率（或稱碼的符號壓縮率）ξ＝K/N＝Ts/Tc＝Rc/Rs，即每個信源符號平均所需的編碼符號數。

前面已說明，信道可以是無噪聲的，因此可以認為信源序列｛Ur｝直接由編、譯碼器映射為信宿序列｛Vr｝。假設A中有l個符號，則可能出現的信源符號組u有lN種。如前所述，不論B是否與A相等，構成信宿序列的還原碼字vm只有M種。為了達到壓縮的目的，需要M＜lN。顯然，用M種碼字代表lN種信源符號組（二者長度均為N）有可能損失信息。

從信息論的觀點，逼真度的損失可以用失真來度量。定量地表征失真的是失真函數d（u，v），它是一個二元函數，它確定在信宿用v代替信源輸出u時失真的大小。所以，d（u，v）常為非負的實數集內的一個數值。由于U和V都是隨機量，d（u，v）也是隨機量，因此通常須定義平均失真：

這里〈 〉是在U∈A和V∈B上的數學期望。再考慮到信源輸出和信宿輸入均為隨機序列，可定義長度為N的符號組的平均失真為

對于不同的r，dr（·）可以相同，也可以不同。我們將這種以單符號失真來衡量逼真度的準則記為Fd。

數據壓縮的最基本問題是，在給定的一類編碼器GE和一類譯碼器GD下，可能達到的最佳性能，或最小平均失真有多大。最小平均失真由下式計算：

其中下確界inf是在給定類的所有編、譯碼器上確定的。因為編、譯碼器的構造受到實際的限制，所以沒有采用極小值，而取下確界。所謂某一類編、譯碼器是以它們的復雜性或壓縮要求，或其他約束條件來劃分的，例如，可以指所有的M級的量化器、所有的長度一定和符號集大小一定的分組碼，或給定形式且輸出熵受約束的所有的時不變濾波器等。

上述基本問題也可以逆向提出，即在給定一定的逼真度，或平均失真不超出D的條件下，所需傳輸的最低信息率（按每信源符號計）有多大，從而再據此設計編、譯碼器。信息論的有關基本定理是從這個角度出發的，因為這樣的命題更結合實際，也更嚴謹。

3.3.2 信息率—失真函數

信息率—失真理論，簡稱率失真理論，是信息論的一個分支，它研究信源的熵超過信道容量時出現的問題。香農在1948年的《通信的數學理論》中開始涉及這一問題，而Berger 1971年所著的《信息率失真理論》給讀者提供了這方面的系統知識。

根據3.3.1節的討論，設信源輸出被分割成長度為N的符號組。我們希望每一個符號組（或向量）u∈AN通過編、譯碼被變換為一個在意義下最佳的v∈BN（即使為最小），其中u表示（u1，…，uN），v表示（v1，…，vN）。

對于給定的信源，p（u），u∈AN是確定的。對于每個指定的條件概率分布P（v|u），u∈AN，v∈BN，可以得到信宿的概率分布為

而UN和VN間的互信息為

因為p（u）是給定的，互信息量將隨P（v/u）而改變，而p（v/u）反映了編、解碼器的性能。現在可以提出這樣一個問題，如果將平均失真限制在一個規定值D以下，I（UN；VN）至少要多大？也就是說，還原碼字中至少要包含信源符號組的多少信息才能滿足≤D？為了回答這一問題，需要定義信源[A，p]相對于Fd的率失真函數R（D），即

其中PD是滿足的所有條件概率分布P（v/u）的集合，即

當信源為平穩、無記憶時，（3-21）式可以簡化為

這就是說，為了使失真度不大于D，信源序列傳送給信宿的最小平均信息率是R（D）。這個函數既依賴于信源的統計特性，也依賴于失真的度量，同時與編、解碼器的類型p（v/u）有關。R（D）是在失真不大于D的情況下，對信源信息率壓縮的理論極限。

可以證明，盡管在（3-21）式用min，而不用inf，R（D）是存在的；同時，R（D）在定義域內是單調遞減的下凸函數。關于R（D）的其他性質，可參閱文獻。對于離散信源，R（D）一般如圖3-4示，其中H（p）為熵函數。

3.3.3 限失真信源編碼定理

在實際的通信系統中，用來傳送信源信息的信息率遠大于R（D）函數所規定的值。那么，這個極限值是否能夠達到或接近呢？下面介紹的編碼定理將回答這個問題。

用G表示解碼還原的字集G＝｛v1，v，…，vM｝，稱G為長度N、字數為M的還原碼，G的元素稱為（還原）碼字。現在用G對信源[A，p]的輸出進行編、譯碼，即每個長度為N的信源符號組被映射為某一碼字v∈G，以使dN（u，v）為最小，記此最小值為

G的平均失真為

式中，〈〉p表示在p（u）上的平均。因此，d（G）是隨機產生的信源符號組u＝（u1，…，uN）以G中最近碼字為近似時所產生的失真的統計平均值。

字數為M、長為N的還原碼G的信息率通常定義為

這是顯而易見的，因為還原碼字v只有M種可能值，其最大可能信息率為log2M（bit/碼字）。如果d（G）≤D，稱G是D容許的。將字數最少的D容許碼記為M（N，D）。

有了這些預備知識，我們可以給出如下的信源編碼定理和它的逆定理，定理的證明可參考文獻。

正定理 對于給定平穩離散無記憶信源[A，p]和單符號逼真度準則Fd，設相對于Fd的[A，p]的率失真函數為R（·）。那么，給定任意ε＞0和D≥0，可以找到正整數N，以使一個長度為N的（D＋ε）容許碼存在，且其信息率R≤R（D）＋ε。也就是說，在N充分大時，以下不等式成立：

換句話說，失真接近于D、而信息率任意接近于R（D）的碼是存在的。

逆定理 不存在信息率小于R（D）的任何D－容許碼，即對于所有的N下式成立：

簡單地說，當失真為D時，信息率不能小于R（D）。

現在考慮信源編碼正、逆定理如何用于圖3-3所示的系統。假設對這個系統的要求是信宿相對于Fd以失真D＋ε還原平穩離散無記憶信源[A，p]。編碼器可以用（D＋ε）容許碼，將每個長度為N的信源輸出序列u映射為一個碼字v，以使dN（u，v）為最小。因為正定理保證R＜R（D）＋ε，所以只要信道容量（以每信源符號計）滿足

C＞R（D）＋ε（3-30）

編碼器的輸出就可以在譯碼器中以任意小的差錯概率還原。圖3-3中信道（可能包含信道編、譯碼器）輸入、輸出的符號則是無關緊要的，因為經過傳輸所增加的失真度為任意小，所以全系統仍以失真度D＋ε工作。另外，每個信源序列u映射為碼字v是確定性的，所以信源譯碼器放在信道輸出對上述結果并不產生影響。由此，可得下面的信息傳輸定理：

正定理 對于ε＞0，前述離散無記憶信源可以在容量C＞R（D）＋ε的任何離散無記憶信道的輸出端還原，而失真度為D＋ε。

逆定理 前述離散無記憶信源不可能在信道容量C＜R（D）的任何離散無記憶信道的輸出以失真D還原。

這兩個定理表明，信源和信宿間在限失真D下的通信，要求信道容量為R（D）既是必要的，也是充分的。若一個系統在信道容量C＝R（D）時可使平均失真等于D，則這個系統是理想的。在理想系統中，信源編碼和信道編碼可以完全分開處理。信源編碼在給定的信源和逼真度準則下謀求最佳碼，而不管信道結構，只要容量相等，任何信道都可以應用。信源編碼器的輸出的熵在碼字充分長時趨近于信道容量。根據信源的漸近等分性（AEP），在信源序列長度無限增大時，所有典型序列的概率和趨近于1，且每個序列的概率接近于相等，所以編碼器輸出的碼字也是接近于等概率的（可以舍棄那些總概率接近于零的非典型序列）。當然，這里已經應用了遍歷性，通常我們假設所討論的信源是遍歷的。這樣，就允許信道編碼器針對這些典型序列工作，而不管信源的細節；它只需建立信源碼字和信道碼字之間的一一對應關系。

以上的討論只涉及平穩離散無記憶信源。對于其他信源的率失真理論，有興趣的讀者請參閱文獻。