率失真理論

資料率失真理論(Rate distortion theory)或稱資訊率-失真理論(information rate-distortion theory)是資訊理論的主要分支,其的基本問題可以歸結如下:對於一個給定的信號源(source, input signal)分布與失真度量,在特定的位元速率下能達到的最小期望值失真;或者為了滿足一定的失真限制,可允許的最大位元速率為何,D 定義為失真的符號。

要完全避免失真幾乎不可能。處理訊號時必須允許有限度的失真﹐可減小所必需的資訊率。1959年﹐Claude Shannon 首先發表《逼真度準則下的離散信號源編碼定理》一文,提出了率失真函數的概念。

失真函數

失真函數能量化輸入與輸出的差異,以便進行數學分析。令輸入訊號為 ,輸出訊號為 ,定義失真函數為 ,失真函數可以有多種定義,其與對應域為非負實數:

 

漢明失真

漢明失真函數能描述錯誤率,定義為:

 

對漢明失真函數取期望值即為傳輸錯誤率。

平方誤差失真

最常用於量測連續字元傳輸的失真,定義為:

 

平方誤差失真函數不適用於語音或影像方面,因為人類感官對於語音或影像的平方誤差失真並不敏感。

率失真函數

下列是率與失真(rate and distortion)的最小化關係函數:

 

這裡 QY | X(y | x), 有時被稱為一個測試頻道 (test channel), 係一種條件機率機率密度函數 (PDF),其中頻道輸出 (compressed signal) Y 相對於來源 (original signal) X, 以及 IQ(Y ; X) 是一種相互資訊(Mutual Information),在 YX 之間被定義為

 

此處的 H(Y) 與 H(Y | X) 是指信宿(output signal) Y(entropy)以及基於信號源(source signal)和信宿(output signal)相關的條件熵(conditional entropy), 分別為:

 
 

這一樣來便可推導出率失真的公式, 相關表示如下:

 

這兩個公式之間互為可逆推。

無記憶(獨立)高斯訊號來源

如果我們假設 PX(x) 服從常態分布變異數為σ2, 並且假設 X 是連續時間獨立訊號(或等同於來源無記憶或訊號不相關),我們可以發現下列的率失真公式的「公式解」(analytical expression):

 [1]

下圖是本公式的幾何面貌:

 

率失真理論告訴我們「沒有壓縮系統存在於灰色區塊之外」。可以說越是接近紅色邊界,執行效率越好。一般而言,想要接近邊界就必須透過增加碼塊(coding block)的長度參數。然而,塊長度(blocklengths)的取得則來自率失真公式的量化(quantizers)有關。[1]

這樣的率失真理論(rate–distortion function)僅適用於高斯無記憶信號源(Gaussian memoryless sources)。

二元信號源

伯努利信號源  ,以漢明失真描述的率失真函數為:

 

平行高斯信號源

平行高斯信號源的率失真函數為一經典的反注水演算法(Reverse water-filling algorithm),我們可以找出一閾值 ,只有變異數大於 的信號源才有必要組態位元來描述,其他信號源則可直接傳送與接收,不會超過最大可容許的失真範圍。

我們可以使用平方誤差失真函數,計算平行高斯信號源的率失真函數。注意,此處信號源不一定同分布:

  ,此時率失真函數為,

 

其中,

 

 必須滿足限制:

 

注釋

  1. ^ 1.0 1.1 Thomas M. Cover, Joy A. Thomas. Elements of Information Theory. John Wiley & Sons, New York. 2006.