查看“︁率失真理论”︁的源代码

{{NoteTA
|G1 = Communication
|G2 = IT
|G3 = Math
|1 = zh-tw:資料; zh-hk:數據; zh-cn:数据;
|2 = zh-tw:失真; zh-hk:失真; zh-cn:失真;
|3 = zh-tw:訊號來源; zh-cn:信源;

|4 = zh-tw:信號源; zh-cn:信源;
}}

'''数据率失真理论'''（Rate distortion theory）或稱'''信息率-失真理論'''（information rate-distortion theory）是[[信息论]]的主要分支，其的基本问题可以归结如下：对于一个给定的信源（source, input signal）分布与[[失真]]度量，在特定的[[码率]]下能达到的最小期望失真；或者为了满足一定的失真限制，可允許的最大码率為何，D 定義為失真的符號。

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

== 失真函數 ==
失真函數能量化輸入與輸出的差異，以便進行數學分析。令輸入信號為<math>\chi</math>，輸出信號為<math>\hat{\chi}
</math>，定義失真函數為<math>d(\chi,\hat{\chi})
</math>，失真函數可以有多種定義，其與[[到达域|對應域]]為非負實數：

<math>d:\chi \times \hat{\chi}\rightarrow R_+
</math>。

=== 漢明失真 ===
漢明失真函數能描述錯誤率，定義為：

<math>d(x,\hat{x}) = \begin{cases} 0, & \text{if }x=\hat{x} \\ 1, & \text{if }x\neq\hat{x} \end{cases}
</math>，

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

=== 平方誤差失真 ===
最常用於量測連續字符傳輸的失真，定義為：

<math>d(x,\hat{x}) = (x-\hat{x})^2
</math>，

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

== 率失真函數 ==
下列是率與失真（rate and distortion）的最小化關係函數:

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

這裡 ''Q''<sub>''Y'' | ''X''</sub>(''y'' | ''x''), 有時被稱為一個測試頻道 （test channel）, 係一種[[條件機率]]之[[機率密度函數]] (PDF)，其中頻道輸出 (compressed signal) ''Y'' 相對於來源 (original signal) ''X'', 以及 ''I''<sub>''Q''</sub>(''Y'' ; ''X'') 是一種'''[[互信息]]'''（Mutual Information），在 ''Y'' 與 ''X'' 之間被定義為

:<math>I(Y;X) = H(Y) - H(Y|X) \, </math>

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

:<math> H(Y) = - \int_{-\infty}^\infty P_Y (y) \log_{2} (P_Y (y))\,dy </math>

:<math> 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. </math>

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

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

這兩個公式之間互為可逆推。
=== 無記憶（獨立）高斯訊號來源 ===
如果我們假設 ''P''<sub>''X''</sub>(''x'') 服从[[正态分布]]且[[方差]]为σ<sup>2</sup>, 並且假設 ''X'' 是連續时间[[統計獨立性|独立]]訊號（或等同於來源無記憶或訊號不相關），我們可以發現下列的率失真公式的「公式解」（analytical expression）:

:<math> 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.

              </math><ref name="auto">{{cite book| author = Thomas M. Cover, Joy A. Thomas | title = Elements of Information Theory | publisher = John Wiley & Sons, New York |year=2006}}</ref>

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

[[File:Rate distortion function.png]]

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

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

=== 二元信號源 ===
[[伯努利分布|伯努利]]信號源<math>X
</math>，<math>X\thicksim Bernoulli(p)
</math>，以漢明失真描述的率失真函數為：

<math>R(D) = \begin{cases} H(p)-H(D), & 0\leq D\leq min\{ p,1-p\} \\ 0, & D\geq min\{p,1-p\} \end{cases}
</math>

=== 平行高斯信號源 ===
平行高斯信號源的率失真函數為一經典的反注水算法(Reverse water-filling algorithm)，我們可以找出一閾值<math>\lambda
</math>，只有[[方差]]大於<math>\lambda
</math>的信號源才有必要配置位元來描述，其他信號源則可直接傳送與接收，不會超過最大可容許的失真範圍。

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

<math>X_1,X_2...,X_m
</math>且<math> X_i\thicksim N(0,\sigma^2_i)
</math>，此時率失真函數為，

<math>R(D)=\sum_{i=1}^m {1\over2}log{{\sigma^2_i}\over{D_i}}
</math>

其中，

<math>D_i = \begin{cases} \lambda, & \text{if }{\lambda}<{{\sigma^2_i} } \\ \sigma^2_i, & \text{if }{\lambda}\geq{{\sigma^2_i} } \end{cases}
</math>

且<math>\lambda
</math>必須滿足限制：

<math>\sum_{i=1}^m D_i=D
</math>。

==注釋==
{{reflist}}
[[Category:信號處理]]