第4章 信息率失真函数
前言
对于失真的合理与可行性分析
- 实际信息处理过程允许一定程度的失真
- 连续信源编码必定存在失真
- 一定范围内的失真可以大幅提高编码效率
本章的研究对象
- 允许一定失真的离散信源编码和连续信源编码
失真函数
定义
- 设某一信源$X$,输出样值为$x_i$,经过有失真的信源编码器,输出$Y$,样值为$y_j$,满足以下关系
$$ x_i\in \{a_1,\cdots,a_n\},y_j\in \{b_1,\cdots,b_m\} $$
- 如果$x_i$=$y_j$,则认为没有失真,反之认为产生失真
- 失真函数表示为$d(x_i,y_i)$,是用来表示失真的大小的量,能衡量用$y_i$代替$x_i$所引起的失真程度,一般的失真函数可定义为
$$ d(x_i,y_j)=\left \{ \begin {matrix} 0,&x_i=y_j\\ \alpha,&\alpha>0,x_i\neq y_j \end {matrix} \right. $$
- 如果把所有的失真函数值排列起来,则可以用矩阵表示,构成失真矩阵
$$ \mathbf d=\begin {bmatrix} d(a_1,b_1) & d(a_1,b_2) & \cdots & d(a_1,b_m)\\ d(a_2,b_1) & d(a_2,b_2) & \cdots & d(a_2,b_m)\\ \vdots & \vdots & \ddots & \vdots\\ d(a_n,b_1) & d(a_n,b_2) & \cdots & d(a_n,b_m)\\ \end {bmatrix} $$
常见失真函数
- 均方失真
$$ d(x_i,y_j)=(x_i-y_j)^2 $$
- 绝对失真
$$ d(x_i,y_j)=|x_i-y_j| $$
- 相对失真
$$ d(x_i,y_j)=\frac {|x_i-y_j|} {|x_i|} $$
- 误码失真
$$ d(x_i,y_j)=\delta(x_i,y_j)=\left \{ \begin {matrix} 0,&x_i=y_j\\ 1,&\mathrm others \end {matrix} \right. $$
推广
- 将一般情况推广到序列编码情况,离散信源输出$L$长符号序列,经过信源编码后输出$L$长编码序列
$$ \begin {matrix} \mathbf X=(X_1,X_2,\cdots,X_L),\mathbf x_i=(x_{i_1},x_{i_2},\cdots,x_{i_l},\cdots,x_{i_L})\\ \mathbf Y=(Y_1,Y_2,\cdots,Y_L),\mathbf y_j=(y_{i_1},y_{i_2},\cdots,y_{i_l},\cdots,y_{i_L}) \end {matrix} $$
- 此时的失真函数可定义为
$$ d_L(\mathbf x_i,\mathbf y_i)=\frac 1 L \sum_{l=1}^Ld(x_{i_l},y_{j_l}) $$
平均失真
定义
- 由于$x_i$,$y_j$都是随机变量,因此失真函数也是一个随机变量,要分析整个信源的失真大小,就需要使用一个整体的值来表示
- 定义失真函数的数学期望称为平均失真
- 离散情况下
$$ \begin {align} \overline D &=\sum_{i=1}^n\sum_{j=1}^mp(a_i,b_j)d(a_i,b_j)\\ &=\sum_{i=1}^n\sum_{j=1}^mp(a_i)p(b_j|a_i)d(a_i,b_j) \end {align} $$
理解
- 根据定义式可以将平均失真理解为给定信源分布$p(a_i)$在经过某一转移概率分布为$p(b_j|a_i)$的有失真信源编码器后产生的失真的总体量度
- 将信源编码器看成一个假想信道,从而可以利用信道转移概率的思想来进行讨论
推广
- 对于连续随机变量有
$$ \overline D =\int_{-\infty}^\infty\int_{-\infty}^\infty p_{X,Y}(x,y)d(x,y)\mathrm d x\mathrm d y $$
- 对于$L$长序列编码情况有
$$ \overline D_L=\frac 1 L \sum_{l=1}^LE[d(x_{i_l},y_{j_l})]=\frac 1 L\sum_{l=1}^L\overline D_l $$
信息率失真函数
前置知识
回顾:信息率
信息率函数是信道中平均每个符号能传送的信息量,单位为$bit/sig$
$$ R=I(X;Y)=H(X)-H(X|Y) $$
- 信息率就是所需输出的有关信源$X$的信息量,从信道的角度来考虑就是接收端$Y$需要获得的有关$X$的信息量,也就是互信息
- 当$p(x_i)$一定时,$I$是关于$p(y_j|x_i)$的$\cup$型函数,有极小值
- 信源编码器目的是使编码后所需要的信息传输率$R$尽可能小,然而$R$越小,所引起的平均失真越大
信源压缩的必要性
- 当信源输出的信息量大于信道的传输能力时,必须对信源进行压缩
- 即使信源输出的信息量小于信道的传输能力,压缩编码也能够大幅度提高传输效率
失真限度
- 信源编码的过程其实是引入失真的过程
- 要根据实际情况定义最大失真限度,保证压缩引入的失真必须在失真限度之内
信息压缩原理
- 对于给定的信源,在满足失真限度(平均失真小于某一值)的前提下,应该使编码后的信息量尽可能小,称为保真度准则
定义
D允许试验信道
- 将失真编码器看作有干扰信道,用分析信道传输的方法探究失真编码
- 将满足失真限度的所有转移概率分布构成一个假想信道,称为D允许试验信道,离散无记忆的情况下可写作
$$ P_D=\{p(y_j|x_i);\overline D\leqslant D,i=1,2,\cdots,n,j=1,2,\cdots,m\} $$
信息率失真函数R(D)
在所有D允许信道中,寻找某一个信道,使得给定的信源经过此信道传输后,互信息达到最小,该最小的互信息即称为信息率失真函数
$$ R(D)=\min_{P_D}I(X;Y) $$
通常信源分布是给定的,于是互信息就取决于概率转移分布,也对应了不同D允许信道的选择
$$ I(X;Y)=\sum_{ij}p(x_i,y_j)\log\frac {p(x_i|y_j)} {p(x_i)} $$
数学模型
- 离散无记忆信源的信息率失真函数可写作
$$ R(D)=\min_{p_{ij}\in P_D}I(X;Y)=\sum_{p_{ij}\in P_D}p(a_i)p(b_j|a_i)\log\frac {p(b_j|a_i)}{p(b_j)} $$
- 失真编码
$$ I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X) $$
理解
- 互信息是信源熵和噪声产生的疑义度之差,也可以理解为接收端应收到的信息量与信道噪声产生的噪声熵之差,是信道传输最终有价值的信息量
- 对于信源编码,$Y$是$X$的编码结果,不考虑信道噪声的影响。将信道噪声造成的损失(如疑义度)看作是信息存储或传输时需要去掉的冗余(可以忽略的次要成分),从而完成对信源的原始信息在允许的失真限度内进行了压缩
- 从物理意义上来看,信息率是真函数是对于给定信源,在平均失真不超过失真限度$D$的条件下,信息率所允许压缩到的最小值$R(D)$
- 因为互信息是在信源分布确定下的关于$p_{ij}$的下凸函数,存在极小值,因此存在合适的$p_{ij}$,使得互信息最小,也就意味着可以选择某种编码方式,使得在满足保真度的条件下,信源可以压缩到最小信息量
信息率失真函数的性质
$R(D)$的定义域和值域
定义域和值域
- 定义域为$[D_{min},D_{max}]$
- 值域为$[H(X),0]$
理解
- 当平均失真取到最小值时,对应失真最小,信源的信息大部分都被传输,信息传输率(互信息)非常接近$H(X)$,当通过合理构造试验信道使得$D_{min}=0$时,信息能够被无失真传输,信息传输率就是信源熵$H(X)$
- 当平均失真取到最大值时,相当于失真达到最大,信息都被损失掉了,信息传输率会达到0,相当于没有任何信息传输
$D_{min}$的讨论
构造式子
$$ \begin {align} D_{min}&=\min \left [\sum_{i=1}^n \sum_{j=1}^mp(a_i)p(b_j|a_i)d(a_i,b_j) \right ]\\ &=\sum_{i=1}^n\left \{p(a_i)\min[\sum_{j=1}^mp(b_j|a_i)d(a_i,b_j)] \right \} \end {align} $$
理解
- 因为信源分别是给定的,我们能调整的只是假想信道的转移概率分布(即调整不同的编码方式)使得平均失真最小,因此可以将$min$移到后面那部分中,问题转换为求后面那部分式子的最小值
- 由失真函数的性质可知,当信源输入$a_i$是固定的情况下,对于不同的$b_j$,失真矩阵中每行总有一个或多个相同的最小值在不同位置,因此可以由此构造试验信道使得平均失真最小化
构造方法
- 固定$a_i$,看失真矩阵中第$i$行的所有元素,让$d_{ij}$最小值对应的$p_{ij}$定为1,不为最小值的元素对应$p_{ij}$定为0,从而就能够构造出整体的最小值
- 在实际求解过程中,求失真矩阵中每一行的最小元素乘以对应的$p(a_i)$值(如第一行的最小值就乘$p(a_1)$,第二行的最小值就乘$p(a_2)$,再把所有的值加起来),求和即可得出$D_{min}$值,然后再令每一行中最小元素所在位置的值为1,其他位置值为0,构建转移概率矩阵
讨论
- 当失真矩阵每一行至少有一个0时,才有可能通过构造一个合适的编码使得平均失真为0
在每行至少一个0的基础上,若每列至多有一个0,有该等式成立
$$ R(D_{min})=R(0)=H(X) $$
$D_{max}$的讨论
构造式子
$$ \begin {align} D_{max}&=\min R(D)\\ &=\min \left [\sum_{i=1}^n\sum_{j=1}^mp(a_i)p(b_j|a_i)d(a_i,b_j)\right]\\ &=\min\left[\sum_{i=1,j=1}^{n,m}p(b_j|a_i)\sum_{i=1}^np(a_i)d(a_i,b_j)\right] \end {align} $$
理解
- $D_{max}$虽然是一个最大值,但它其实是相对的,它对应了使得$R(D)=0$的最小失真,即对于任意大于$D_{max}$的失真,信息传输率都满足$R(D)=0$
$R(D)=0$意味着没有信息被传输,$I(X;Y)=0$,说明$X$和$Y$是统计独立的,互相没有关系,转移概率和信源概率分布无关,有
$$ p_{ij}=p(y_j|x_i)=p(y_j)=p_j $$
- 问题转换为通过构造一个试验信道使得整个式子的值最小化
构造方法
- 固定$a_i$,若$\sum_{i=1}^np(a_i)d(a_i,b_j)$取到最小,则令$p(b_j|a_i)=p_j=1$,否则令其为0
根据以上方法就有
$$ D_{max}=\min\sum_{i=1}^np(a_i)d(a_i,b_j) $$
- 也就是说,在求解过程中,先计算失真矩阵各列元素乘以其对应$p(a_i)$的值的和(例如某列中的第一个元素乘$p(a_1)$,第二个元素乘$p(a_2)$,再把所有值加起来),然后看哪一列的这一和值最小,令转移概率矩阵中的此列为1,其他列为0
例题
- 设信道输入为$X=\{a_1,a_2,a_3\}$,且为等概率分布,已知失真矩阵为$$D=\begin{bmatrix}1 & 2 & 3\\2 & 1 & 3\\3 & 2 & 1\end {bmatrix}$$求$D_{min}$和$D_{max}$及相应的试验信道转移概率矩阵
- 首先求$D_{min}$
$$ D_{min}=\frac 1 3min[1,2,3]+\frac 1 3min[2,1,3]+\frac 1 3min[3,2,1]=\frac 1 3\times 3=1 $$
- 各行最小值均为1,分别在(1,1)(2,2)(3,3)处,于是此时试验信道的转移概率矩阵中这些位置的值记为1,其他位置均为0,得到转移概率矩阵$$P_{(Y|X)}= \begin {bmatrix}1 & 0 & 0 \\0 & 1 & 0 \\0 & 0 & 1\end {bmatrix}$$
- 接着求$D_{max}$
$$ \begin {align} D_{max}&=\min\left [ \sum_{i=1}^np(a_i)d(a_i,b_j)\right ]\\ &=\min \begin {bmatrix} p(a_1)\times1+p(a_2)\times2+p(a_3)\times3\\ p(a_1)\times2+p(a_2)\times1+p(a_3)\times2\\ p(a_1)\times3+p(a_2)\times3+p(a_3)\times1 \end {bmatrix}\\ &=\min\begin {bmatrix} \frac 6 3\\ \frac 5 3\\ \frac 6 3 \end {bmatrix}=\frac 5 3 \end {align} $$
- 发现使得该式子取到最小值的列为第二列,于是此时试验信道的转移概率矩阵中第二列的元素值记为1,其他位置均为0,得到转移概率矩阵$$P_{(Y|X)}=\begin {bmatrix} 0 & 1 & 0\\0 & 1 & 0\\0 & 1 & 0\end {bmatrix}$$
$R(D)$是关于$D$的下凸函数(证明略)
$R(D)$在定义域内是严格递减函数(证明略)
信息率失真函数与信道容量
从定义上来看
信道容量为$C=\max_{p(a_i)}I(X;Y)$
- 表示信道的最大传输能力,反映的是信道本身的特性,和信源无关
- 为了排除信源特性对信道容量的影响,通常采用在所有信源中那个能够使平均互信息量达到最大的信源作为参考,从而使得信道容量仅与信道本身的特性有关
- 信道不同,$C$也不同
信息率失真函数为$R=\min_{p_D}I(X;Y)$
- 表示保真度条件下信源信息率可以被压缩的最低限度,反映的是信源本身的特性,和信道无关
- 为了排除信道特性对信息率失真函数的影响,通常采用所有的编码其中那个能够使得平均互信息量达到最小的编码器作为参考,从而使得信息率失真函数仅与信源本身的特性有关
- 信源不同,$R$也不同
从引入目的来看
引入信道容量$C$
- 是为了解决在所用信道中传送的最大信息量到底有多大的问题,其给出了可能传输的最大信息量
- 为信道编码服务,提高通信的可靠性
引入信息率失真函数$R$
- 是为了解决在允许失真度$D$的条件下,信源编码能够压缩到什么程度的问题,其给出了保真度条件下信源信息率可以被压缩道的最低信度
- 为信源的压缩编码服务,提高通信的有效性