率失真理论

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

要完全避免失真几乎不可能。处理信号时必须允许有限度的失真﹐可减小所必需的信息率。1959年﹐Claude Shannon 首先发表《逼真度准则下的离散信源编码定理》一文，提出了率失真函数的概念。

失真函数

失真函数能量化输入与输出的差异，以便进行数学分析。令输入信号为$\chi$，输出信号为${\hat {\chi }}$，定义失真函数为$d(\chi ,{\hat {\chi }})$，失真函数可以有多种定义，其与到达域为非负实数：

$d:\chi \times {\hat {\chi }}\rightarrow R_{+}$。

汉明失真

汉明失真函数能描述错误率，定义为：

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

对汉明失真函数取期望即为传输错误率。

平方误差失真

最常用于量测连续字符传输的失真，定义为：

$d(x,{\hat {x}})=(x-{\hat {x}})^{2}$，

平方误差失真函数不适用于语音或影像方面，因为人类感官对于语音或影像的平方误差失真并不敏感。

率失真函数

下列是率与失真（rate and distortion）的最小化关系函数:

$\inf _{Q_{Y|X}(y|x)}I_{Q}(Y;X)\ {\mbox{subject to}}\ D_{Q}\leq D^{*}.$

这里 Q_{Y | X}(y | x), 有时被称为一个测试频道 （test channel）, 系一种条件概率之概率密度函数 (PDF)，其中频道输出 (compressed signal) Y 相对于来源 (original signal) X, 以及 I_Q(Y ; X) 是一种互信息（Mutual Information），在 Y 与 X 之间被定义为

$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.$

这两个公式之间互为可逆推。

无记忆（独立）高斯信源

如果我们假设 P_X(x) 服从正态分布且方差为σ², 并且假设 X 是连续时间独立信号（或等同于来源无记忆或信号不相关），我们可以发现下列的率失真公式的“公式解”（analytical expression）:

$R(D)=\left\{{\begin{matrix}{\frac {1}{2}}\log _{2}(\sigma _{x}^{2}/D),&{\mbox{if }}0\leq D\leq \sigma _{x}^{2}\\\\0,&{\mbox{if }}D>\sigma _{x}^{2}.\end{matrix}}\right.$

下图是本公式的几何面貌:

率失真理论告诉我们“没有压缩系统存在于灰色区块之外”。可以说越是接近红色边界，执行效率越好。一般而言，想要接近边界就必须透过增加码块（coding block）的长度参数。然而，块长度（blocklengths）的获取则来自率失真公式的量化（quantizers）有关。

这样的率失真理论（rate–distortion function）仅适用于高斯无记忆信源（Gaussian memoryless sources）。

二元信源

伯努利信源$X$，$X\thicksim Bernoulli(p)$，以汉明失真描述的率失真函数为：

$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}}$

平行高斯信源

平行高斯信源的率失真函数为一经典的反注水算法(Reverse water-filling algorithm)，我们可以找出一阈值$\lambda$，只有方差大于$\lambda$的信源才有必要配置比特来描述，其他信源则可直接发送与接收，不会超过最大可容许的失真范围。

我们可以使用平方误差失真函数，计算平行高斯信源的率失真函数。注意，此处信源不一定同分布：

$X_{1},X_{2}...,X_{m}$且$X_{i}\thicksim N(0,\sigma _{i}^{2})$，此时率失真函数为，

$R(D)=\sum _{i=1}^{m}{1 \over 2}log{{\sigma _{i}^{2}} \over {D_{i}}}$

其中，

$D_{i}={\begin{cases}\lambda ,&{\text{if }}{\lambda }<{\sigma _{i}^{2}}\\\sigma _{i}^{2},&{\text{if }}{\lambda }\geq {\sigma _{i}^{2}}\end{cases}}$

且$\lambda$必须满足限制：

$\sum _{i=1}^{m}D_{i}=D$。