限失真信源编码

from 信息论与编码/ 曹雪虹

本章主要讨论限失真信源编码，从分析失真函数、信息率失真函数出发，给出限失真编码定理。

1 平均失真和信息率失真函数

在实际问题中，信号有一定的失真是可以容忍的。但是当失真大于某一限度后，信息质量将被严重损伤。要规定失真限度，必须现有一个定量的失真测度，为此引入失真函数。

1.1 失真函数

某信源 $X$，经过有失真的信源编码器，输出 $Y$，产生的失真大小用一个量来表示，即失真函数 $d(x_i, y_j)$，以衡量用 $y_j$ 代替 $x_i$ 所引起的失真程度。一般失真函数定义为：

$d(x_i, y_j) = \begin{cases} 0 & &x_i = y_j \\ \alpha & \alpha > 0 & x_i \not= y_j \end{cases}$

单个符号的失真度的全体构成矩阵，称为失真矩阵

$\boldsymbol{d} = \begin{bmatrix} d(a_1, b_1) & \cdots & d(a_1, b_m) \\ \vdots & \ddots & \vdots \\ d(a_n, b_1) & \cdots & d(a_n, b_m) \end{bmatrix}$

失真函数 $d(x_i, y_j)$ 的函数形式可以根据需要任意选取，常用的失真函数有：

绝对失真：$d(x_i, y_j) = |x_i - y_j|$
均方失真：$d(x_i, y_j) = (x_i-y_j)^2$
相对失真：$d(x_i, y_j) = |x_i - y_j| / |x_i|$
误码失真：$d(x_i, y_j) = \delta(x_i, y_j) = \begin{cases}0 & x_1 = y_j \ 1 & 其他\end{cases}$

前三种失真函数适用于连续信源，后一种适用于离散信源。

将失真函数的定义推广到序列编码情况：如果假定离散信源输出符号序列 $X = (X_1X_2 \dots X_l \dots X_L)$，其中 $L$ 长符号序列样值 $x_i = (x_{i1}x_{i2} \dots x_{il} \dots x_{iL})$，经信源编码后，输出符号序列 $Y = (Y_1Y_2 \dots Y_l \dots Y_L)$，其中 $L$ 长符号序列样值 $y_j = (y_{j1}y_{j2} \dots y_{jl} \dots y_{jL})$，则失真函数定义为：

$d_L(\boldsymbol{x_i},\boldsymbol{y_j}) = \frac{1}{L}\sum_{l=1}^L{d(x_{il}, y_{jl})}$

其中 $d(x_{il}, y_{jl})$ 是信源输出 $L$ 长符号样值 $x_i$ 中的第 $l$ 个符号 $x_{il}$ 时，编码输出 $L$ 长符号样值 $y_j$ 中的第 $l$ 个符号 $y_{jl}$ 的失真函数。

1.2 平均失真

由于 $x_i$ 和 $y_j$ 都是随机变量，所以失真函数 $d(x_i, y_j)$ 也是随机变量，限失真时的失真值只能用它的数学期望或统计平均值。因此将失真函数的数学期望称为平均失真，记为

$\begin{align} \bar{D} & = \sum_{i=1}^{n}{\sum_{j=1}^{m}{p(a_ib_j)d(a_i,b_j)}} \\ & = \sum_{i=1}^{n}{\sum_{j=1}^{m}{p(a_i)p(b_j|a_i)d(a_i,b_j)}}\\ \end{align}$

1.3 信息率失真函数 $R(D)$

如果信源输出的信息率大于信道的传输能力，就必须对信源进行压缩，使其压缩后的信息传输率小于信道传输能力，但同时要保证压缩所引入的失真不超过预先规定的限度 $D$。

因此信息压缩问题就是对于给定的信源，在满足平均失真

$\bar{D} \leq D$

的前提下，使编码后的信息率尽可能小。

我们将有失真的信源编码器视作有干扰的信道，用分析信道传输的方法来研究限失真编码问题。所有满足上式的转移概率分布 $p_{ij}$ 构成了类假想的信道，称为 $D$ 允许信道，记为：

$P_D = \{p(y|x): \bar{D} \leq D\}$

对于离散无记忆信道，相应有：

$P_D = \begin{cases}\{p(y_j|x_i): \bar{D} \leq D & i = 1, 2, \dots n; j = 1, 2, \dots, m \}\end{cases}$

在上述允许信道 $P_D$ 中，可以寻找一个信道 $p(Y|X)$，使给定的信源经过此信道传输后，互信息 $I(X;Y)$ 达到最小。该最小的互信息就称为信息率失真函数 $R(D)$，即：

$R(D) = \min_{P_D}{I(X;Y)}$

对于离散无记忆信源，$R(D)$ 函数可写成：

$R(D) = \min_{p_{ij}\in P_D}{\sum_{i=1}^{n}{\sum_{j=1}^{m}{p(x_i)p(y_j|x_i) \log {\frac{p(y_j|x_i)}{p(y_j)}}}}} \\$

1.4 信息率失真函数的性质

1. $R(D)$ 函数的定义域

由于 $D$ 是非负实数 $d(x,y)$ 的数学期望，因此 $D$ 也是非负的实数，非负实数的下界是零。对应于无失真情况，相当于无噪声信道，此时信道传输的信息量等于信源熵，即：

$R(D) = R(0) = H(X)$

由于 $I(X;Y)$ 是非负函数，而 $R(D)$ 是在约束条件下的 $I(X;Y)$ 的最小值，所以 $R(D)$ 也是一个非负函数，它的下限值是零。取满足 $R(D) = 0$ 的所有 $D$ 中最小的，定义为 $R(D)$ 定义域的上限 $D_{max}$ 。因此 $D \in [0, D_{max}]$。其中：

$\begin{align} D_{max} = &\min \sum_{j=1}^m{p_j} \sum_{i=1}^n{p_i d_{ij}}\\ = & \min_{j = 1, 2, \dots, m}\sum_{i =1}^n{p_id_{ij}} \end{align}$

例：设输入输出符号表为 $X = Y = \{0, 1\}$，输入概率分布为 $p(x) = \{\frac{1}{3}, \frac{1}{3}\}$，失真矩阵为：

$\boldsymbol{d} = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$

求 $D_{max}$

解：

$\begin{align} D_{max} = & \min_{j = 1, 2, \dots, m}\sum_{i =1}^n{p_id_{ij}} \\ = & \min_{j =1 , 2}(p_1d_{11}+p_2d_{21}, p_1d_{12}+p_2d_{22}) \\ = & \frac{1}{3} \end{align}$

此时输出符号的概率：$p(y_1) = 0$, $p(y_2) = 1$

2. $R(D)$ 函数的下凸性和连续性

3. $R(D)$ 函数的单调递减性

由上述三点可以得到以下结论：

$R(D)$ 是非负的实数，即 $R(D) \geq 0$。其定义域为 $[0, D_{max}]$，其值为$[0, H(X)]$。当 $D \geq D_{max}$ 时，$R(D) = 0$。
$R(D)$ 是关于 $D$ 的连续函数、下凸函数、严格递减函数