第5章 有失真信源编码.doc

第５章 有失真信源编码（信息率失真函数）
离散信源有失真编码
连续信源有失真编码

5.1信息率－失真函数的概念
在第２章我们证明了当输入随机变量的概率分布确定时，互信道是条件转移概率的下凸函数，即互信息必存在一个最小值。然而，在没有其它约束条件的情况下，这个最小值就是零。因为一方面互信息总是非负的，另一方面，当输入和输出随机变量相互独立时互信息等于零。所以研究一般情况下互信息的极小值问题没有什么意义。
无失真信源编码时，信源的熵是信息率所能达到的下限。在很多实际情况下，要做到完全没有失真是没有必要的，特别是对连续信源编码，由于信源的绝对熵无穷大，要达到无失真编码是不可能的。为此我们有必要研究在满足某种失真准则下互信息的极小值问题，即信息率－失真函数。
首先看离散信源的情况。
设Ｘ和Ｙ是定义在相同取值域上的离散型随机变量。失真函数d(x,y) 是定义在上的非负函数

例如，可定义
（５.１.１）
其物理意义是当输入和输出相等时没有失真，当输入和输出不相等时失真是相同的。显然失真函数d(x,y)是对Ｙ代表Ｘ所引起失真的量度。失真函数的定义由所研究的客观问题决定。（５.１.１）式的失真函数称为汉明失真准则。
失真函数只定义了若干具体失真的数值，为了反映随机变量之间的总体失真情况，我们定义平均失真
（５.１.２）
对离散型变量
（５.１.３）
如果Ｘ和Ｙ都是Ｌ维随机矢量，可定义矢量间的失真为
（５.１.４）
平均失真
（５.１.５）
其中是第个分量的平均失真。
如果我们要求平均失真不大于某个定值Ｄ。令表示所有满足平均失真不大于Ｄ的条件概率矩阵Ｐ的集合，我们定义
（５.１.６）
为信息率－失真函数，或简称率失真函数。它表示在给定失真限度Ｄ条件下互信息的极小值。
在率失真函数的定义中涉及条件转移概率矩阵，似乎它也是表征率失真函数的参量，然而，率失真函数是表征信源的量，它只与信源和失真Ｄ有关，而与转移概率矩阵无关。如果把转移概率矩阵看成信道，我们把这些不同的信道称为试验信道，对不同的试验信道，失真和互信息是不同的，只有当试验信道使互信息达到最小时，这个最小值就是率失真函数的值。
为了理解率失真函数的实际意义，我们看如下有失真信源编码问题。
设有一个有2n个符号的等概率信源，失真函数是

当（５。１。２）式的汉明失真准则。可允许的平均失真Ｄ＝１／２。在无失真情况下，传送每个符号的信息率至少log2n。在有失真条件下我们采用下述编码方案：

这时平均失真不大于１／２。编码后信息率

显然，Ｒ小于原来的log2n。信息率压缩了，所付出的代价是容忍了１／２的平均失真。
现在的问题是，（１）在失真为１／２时，信息率能否更小，最小值是多少；（２）采用何种编码方式使信息率尽可能小。第一个问题是率失真函数的计算问题，实际上是有失真信源编码问题；第二个问题是怎样进行信源编码问题，即信源编码方法问题。实际上，信息率可以更小些，但编码方法要复杂得多。

5.2率失真函数的性质
5.2.1 Ｒ（Ｄ）函数的定义域
（１） 失真函数的下限
失真函数d(i,j)组成一个失真矩阵

只要令对应于d(i,j)最小的p(j|i)=1，其它所有的都为零，可得
（５.２.１）
当且仅当失真矩阵中每行中至少有一个零时。通常情况下这是能够做到的。如果，只要改变单个符号的失真度，令就可以保证失真矩阵每行至少有一个零，使。对率失真函数来说它只是起了坐标平衡的作用。所以假设并不失一般性。Ｄ＝０对应于无失真情况，这时应该有

但是上式成立是有条件的，它与失真矩阵的形式有关。
只有当失真矩阵中每行至少有一个零，并且每列最多只有一个零时，。
否则Ｒ（０）小于Ｈ（Ｘ），这表示对信源符号集中有些符号进行压缩、合并，但没有引入失真（在具体的失真准则之下）。

（２） 失真函数的上限
定义域的上界定义为
（５.２.２）
必有。由于

所以

令，只要令对应于最小的q(j)等于1，那么
（５.２.３）

5.2.2 Ｒ（Ｄ）函数的下凸性
定理５.２.１ 率失真函数是定义域上的下凸函数
证明 （１）Ｒ（Ｄ）函数的定义域是凸域。令

由率失真函数的定义

其中是使互信息达到极小值的信道转移概率，对应的平均失真。

其中是使互信息达到极小值的信道转移概率，对应的平均失真。
作，对应的平均失真

因此，即定义域是凸的。
（２） Ｒ（Ｄ）函数的下凸性。由率函数的定义和互信息的下凸性

证毕。

5.2.3 Ｒ（Ｄ）函数的单调递减性和连续性。
（１） Ｒ（Ｄ）函数的单调递减性
R(D)函数的递减性由定义直接得到，其单调递减性可以通过Ｒ（Ｄ）函数的下凸性来证明。
（２） Ｒ（Ｄ）函数的连续性
由互信息的连续性可以得到Ｒ（Ｄ）函数的连续性。

R(D)

H（X）

D
Dmax

Ｒ（Ｄ）函数示意图

5.3 离散信源R(D)函数的计算
5.3.1 Ｒ(D)函数的参量表达式
Ｒ（Ｄ）函数的计算是目标函数
（５.３.１）
在约束条件
（５.３.２）
（５.３.３）
下的极小值问题，其中。
用拉格朗日乘子法，引入n+1常数个s 和，求如下目标函数的极值。
－ （５.３４）
令

得

整理得
（５.３.５）
也就是
（５.３.６）
其中
（５.３.７）
（５．３．６）式是一个由nm个方程组成的方程组。两边对j求和得
（５.３.８）
（５.３.９）
（５．３．６）式两边乘以并对求和得
（５.３.１０）
即
（５.３.１１）
由把(5.3.9)式代入上式得
（５.３.１２）
(5.3.12)式是一个关于参量s的由m个方程组成的方程组, 可解得，代入（5.3.9）式可解得。
将所求得的代入（5.3.6）式得到解决nm个，再代入（5.3.1）和（5.3.2）式即得率失真函数和平均失真关于s的参量表达式。只要改变s的值（注意使q(j)非负）即右得到D(s)和R(s)的值，从而得到R（D）函数的曲线。
（５.３.１３）

（５.３.１４）
下面研究s 取值范围。事实上，参量s就是Ｒ（Ｄ）函数的一阶导数。因为

（５.３.１５）
再求，对（５.３.１１）式求关于s 导数得

两边乘以q(j)，并对j求和得

由（５.３.９）和（５.３.１３）式

代入（５.３.１５）式即得
（５.３.１６）
由Ｒ（Ｄ）函数的严格递减性和下凸性，必有s<0，而，即s随Ｄ的增加而增大。
当Ｄ＝０时，由（５.３.１３）式，必有。随着Ｄ的增加，s随之增大，并在时达到最大。当时，Ｒ，s均为零，在点除某些特例外，s将从某个负值跳到零，在该点不连续。

s
Dmax
D
smax

S(D) 函数示意图

由Ｒ（Ｄ）函数的参量表达式和s的取值范围，我们就可以得到Ｒ（Ｄ）函数的曲线。首先取s为一个绝对值比较大的负数，然后计算R(s)和D(s)的值；逐渐增加s，直到R(s)的值达到零，我们就可以得到一条完整的Ｒ（Ｄ）函数曲线了。

5.4离散信源在汉明准则下率失真函数的计算
把（５.３.１１）式写成矩阵形式

解得

或者

把（５.３.９）式写成矩阵形式

解得输出概率分布

条件概率分布

由（５.３.１３）式计算平均失真

或者

由（５.３.１４）式计算率失真函数

这就是Ｒ（Ｄ）函数的显式表达式，其中

对于二元信源，设。先求平均失真的上界和下界。
由于失真矩阵中每行都有一个零，所以。另外

所以，平均失真的上界。当n=2时

二元信源的率失真函数和s(D)函数下图所示。

R（D）

D

二元信源的率失真函数和s(D)函数示意图

在汉明失真准则下，当时，平均失真

就是误码率，能容忍的失真相当于能容忍的误码率。当p=1/4时，如果能容忍的误码率也是１／４，那就不用传输任何信息就可以达到。因为，不管信源发出什么符号，都把它编成，这时出错的概率就是信源发出的概率，即１／４。只送一种符号当然不用传送信息了，这时R=0，这就是的含义。如果能容忍的误码率小于１／４，就不能采用这样的编码方法，就是能容忍的失真而可能压缩的信息率，它与信道干扰所引起的信息损失相对应。
关于Ｓ（Ｄ），虽然其表达式与p无关，但其定义域与p有关。P=1/4时，定义域为［０，０.２５］，对应的；当p>1/4时，对应的s=0。因此，在Ｄ＝１／４点s(D)曲线是不连续的。当p=1/2时，s(D)曲线延伸至Ｄ＝１／２点，对应的，这时s(D)曲线是连续的。

５．２ 离散信源率失真函数计算的迭代公式
把互信息Ｉ（Ｘ，Ｙ）看成条件转移概率分布和输出概率分布q(j)的函数。求目标函数

（５.４.１）
的极值问题。可以证明，上式是的下凸函数。
先固定，在的条件下求Ｆ的极值，即

两边对j求和得，故
（５.４.２）
这就是求普通的边缘概率分布。
现固定q(j)，在的限制下求极值：

上式两边对j求和得

所以
（５.４.３）
公式（５.４.２）和（５.４.３）就是Ｒ（Ｄ）函数迭代计算的基础。条件转移概率的初值可选。可以证明，迭代计算的收敛性和收敛速度。
Ｒ（Ｄ）函数的迭代计算方法与离散信道容量的迭代计算方法类似。所不同的是计算信道容量只需要得到一个数值即可计算Ｒ（Ｄ）函数需要得到一条曲线。我们先取s 的值为一个绝对值较大的负数，得到Ｒ（Ｄ）函数的一个点，然后增加s，依次计算各点，直到Ｒ（Ｄ）＝０时为止。

5.５ 连续信源的率失真函数
5.5.1连续信源的平均失真函数
设连续信源的输出为Ｘ，其概率密度函数为p(x)。信源编码器的输出为Ｙ，其概率密度函数为q(y)。编码器的条件概率密度函数为p(y|x)。在第２章已经证明，当信源的概率密度函数一定时，互信息Ｉ（Ｘ，Ｙ）是条件概率密度函数p(y|x)的下凸函数。所以互信息的极小值必为最小值。由互信息的非负性，它的最小值为零，而当Ｘ和Ｙ相互独立时达到这个最小值。所以一般意义下互信息的极小值问题没有什么实际意义。
连续信源是实际中最常见的信源，如话音信号和图像信号都是典型的连续信源。对连续信源进行不失真编码既是不可能的，也是不必要的。研究在某种失真度准则下的连续信源编码问题有非常重要的实际意义。
连续信源的失真函数d(x,y)是定义在二维实数域上的二元非负函数，它表示用y代表x所引起的失真。如
（５.５.１）
和
（５.５.２）
平均失真
（５.５.３）
互信息
（５.５.４）
其中
（５.５.５）
定义是所有平均失真的条件概率密度函数p(y|x)的集合，即
（５.５.６）
我们定义信息率－失真函数（简称率失真函数）为
（５.５.７）
式中inf表示下确界，相当于离散集合中的极小。严格也说，连续集合中可能不存在极小值，但下确界是存在的。由率失真函数的定义，率失真函数是（５.５.４）式目标函数在约束条件（５.５.３）和
（５.５.８）
之下的下确界问题。求下确界仍然是求极值问题，方法是用拉格朗日乘子法和变分法。
与离散情况的推导类似，用变分法我们可以得到率失真函数的参量表达式：
（５.５.９）
（５.５.１０）
其中、和满足
（５.５.１１）
（５.５.１２）
（５.５.１３）
并且可以证明，参量s是Ｒ（Ｄ）函数的斜率。
（５.５.１４）
率失真函数的一般求解是困难的。但是在
（５.５.１５）
的条件下，解是存在的。我们可以用数值计算方法求解。

5.5.2 d(x,y)只与x-y有关情况下率失真函数的求解
在许多实际情况下失真函数d(x,y)只与x-y有关，比如均方失真准则就属于这种情况。这时我们可以用解析方法求解率失真函数。 令，，那么
（５.５.１６）
其中
（５.５.１７）
是方程（５.５.１１）的解。因为将（５.５.１６）和（５.５.１７）式代入（５.５.１１）式得

由（５.５.１２）式

令
（５.５.１８）
注意，满足，因此它也是一种概率密度函数。这时
（５.５.１９）
上式表明，p(x) 是q(x)和的卷积。因此，我们可以用特征函数法（即付里叶变换法）求解。令是对应的特征函数（特征函数与付氏变换相差一个负号），即

那么

由此可得

解得和后即可得到R（D）函数的参量表达式。
5.5.3 高斯信源的率失真函数
设高斯信源的概率密度函数为

在均方失真准则下

这是均值为零，方差为的正态概率密度函数，其特征函数是

而p(x)的特征函数是

则q(x)的特征函数为

这也是正态分布，均值为m，方差为，即

所以

（５.５.１０）

用代入上式即得高斯信源在均方准则下的率失真函数Ｒ（Ｄ）的表达式

当时的Ｒ（Ｄ）和s(D)曲线如图所示。当Ｄ＝１时Ｒ（Ｄ）＝０。即，如果可容忍的失真等于１，那么不用传输任何信息。这是显然的，因为不管信源的输出是多少，都将它编码为均值，均方误差也是１。而一个常数是不需要传输的。对应的Ｒ（Ｄ）曲线的斜率s=-0.5，在这一点s是不连续的。
当，表明可容许的失真趋于零时，率失真函数趋于信源的熵，而连续信源的绝对熵趋于无穷大。
除一面两种极端情况外，比如Ｄ＝１／４时，Ｒ（Ｄ）＝１。也就是说，至少需要１比特的信息率才能使平均误差达到１／４。编码定理证明，在极限情况下这是可能的，但实际编码是困难的。我们看用一个比特编码所能达到的平均失真（均方误差）。为简单起见，设信源输出的均值为零，编码方案如下：

由此引入的平均失真为

当时，上式的平均失真Ｄ达到最小值0.36。这比理论上的最小值１／４大了很多。
上例实际上是信源的二值量化问题。由于均方误差准则下的平均失真等于量化噪声功率，所以代表量化引起的信噪比ＳＮＲ。就是量化信噪比为ＳＮＲ时信源编码所能达到的最小信息率。以ＰＣＭ电话为例，一般要求ＳＮＲ＝２６dB（４００倍），这时比特。现有ＰＣＭ方式所能达到的信息率为７～８比特，尚有潜力可挖。
由高斯信源的率失真函数可以得到如下失真率函数

这里对数的底取２，信息率的单位为比特。失真率函数表示在给定信息率条件下信源编码所引起的理论上的最大失真度。用分贝数表示为

上式表明，信息率每增加１bit，失真度减少６dB。如果从量化的角度解释，信息率每增加１bit，量化噪声功率将减少６dB。这与模数变换器的精度每提高一位，量化误差可减少６dB是一致的。
实际电话信号并不服从正态分布，但用正态分布代替所需的信息率要高一些。因为在确定功率下信源的熵以正态分布时最大。

一般信源率失真函数的上限和下限
设无记忆平稳信源的均值为零，方差为，那么，在均方误差准则下，其率失真函数满足上限

即，在所有限平均功率信源中，当信源的概率密度函数服从高斯分布时率失真函数达到最大。这个结论可以看成连续信源限平均功率最大熵定理的推广。该上限是１９７１年由Berger给出的。
率失真函数的下限也存在，下面给出了Shannon下限。
设无记忆平稳信源的均值为零，方差为，那么，在均方误差准则下，其率失真函数满足下限

这里h（Ｘ）是信源的微分熵。
当信源的概率密度函数服从高斯分布时，这个下限就是高斯信源的失真函数。

白色高斯信源的率失真函数
设白色高斯信源的双边功率谱密度函数为

信号的平均功率。在持续时间Ｔ内，以Nyquist采样速率２Ｆ对信源进行采样，得到的２ＦＴ个样值之间互不相关，由于这些样值都服从高斯分布，因此，它们是相互独立的，并且是同分布的。时间Ｔ内的率失真函数

单位时间内的率失真函数

5.6限失真信源编码定理
5.6.1 离散无记忆信源限失真编码定理
设有一离散无记忆平稳信源，其率失真函数为Ｒ（Ｄ），当信息速率时，只要信源序列足够长，一定存在一种编码方式Ｃ，其译码失真小于或等于，为任意小的正数。反之，当时，不论用何种编码方式，其译码失真均大于Ｄ。
５．６．２ 连续无记忆信源限失真编码定理
设有一连续无记忆平稳信源，其率失真函数为Ｒ（Ｄ），当信息速率时，只要信源序列足够长，一定存在一种编码方式Ｃ，其译码失真小于或等于，为任意小的正数。反之，当时，不论用何种编码方式，其译码失真均大于Ｄ。
编码定理的重要意义：
（１） 率失真函数在限失真信源编码中占有非常重要的地位，它是实际信源编码所能逼近的下限，为信源编码指明了目标。
（２） 这是一个存在性定理，而非构造性定理。如何进行信源编码是一个广阔的研究领域。
（３） 指明了获得好的信源编码的途径，即构造长码。
（４） 信源编码的平均失真随码长以指数规律趋于Ｄ。

信源编码方法：
（１） 波形编码
脉冲编码调制（ＰＣＭ）
增量调制（差分编码）
预测编码（线性预测编码ＬＰＣ）
矢量量化编码
（２） 变换编码
离散正交变换
离散余弦变换
（３） 分析综合编码
子带编码 利用人的听觉和视觉感知与激励信号的频率有关
小波变换编码
分形图像编码
模型基编码