率失真理论

维基百科,自由的百科全书
跳转至: 导航搜索

資料率失真理论(Rate distortion theory)或稱信息率-失真理論(information rate-distortion theory)的基本问题可以归结如下:对于一个给定的信源(source, input signal)分布与失真度量,在特定的码率下能达到的最小期望失真;或者为了满足一定的失真限制,可允許的最小码率為何,D 定義為失真的符號。

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

率失真函數[编辑]

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

\inf_{Q_{Y|X}(y|x)} I_Q(Y;X)\ \mbox{subject to}\ D_Q \le D^*.

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

I(Y;X) = H(Y) - H(Y|X) \,

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

 H(Y) = - \int_{-\infty}^\infty P_Y (y) \log_{2} (P_Y (y))\,dy
 H(Y|X) = 
       - \int_{-\infty}^{\infty} \int_{-\infty}^\infty Q_{Y|X}(y|x) P_X (x) \log_{2} (Q_{Y|X} (y|x))\, dx\, dy.

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

\inf_{Q_{Y|X}(y|x)} E[D_Q[X,Y]] \mbox{subject to}\ I_Q(Y;X)\leq R.

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

無記憶(獨立) 高斯訊號來源[编辑]

如果我們假設 PX(x) 是常態分配並取變異數 σ2, 並且假設訊號 X 是連續 統計獨立性 (或等同於,來源是無記憶, 或訊號是 uncorrelated), 我們可以發現下列的率失真公式之「公式解」(analytical expression):

 R(D) = \left\{ \begin{matrix} 
  \frac{1}{2}\log_2(\sigma_x^2/D ), & \mbox{if } 0 \le D \le \sigma_x^2 \\  \\
              0,                             & \mbox{if } D > \sigma_x^2. 
                      \end{matrix} \right.

              [1]

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

Rate distortion function.png

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

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

注釋[编辑]

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