限失真信源与信息率失真函数R(D).doc

Chap 4
第四章 限失真信源与信息率失真函数R(D)
§4-1 引言
（一） 引入限失真的必要性：
1） 失真在传输中是不可避免的;
2） 接收者（信宿）无论是人还是机器设备，都有一定的分辨能力与灵敏度，超过分辨能力与灵敏度的信息传送过程是毫无意义的;
3） 即使信宿能分辨、能判别，但对通信质量的影响不大，也可以称它为允许范围内的失真；
4） 我们的目的就是研究不同的类型的客观信源与信宿，在给定的Qos要求下的最大允许（容忍）失真D，及其相应的信源最小信息率R(D).
5） 对限失真信源，应该传送的最小信息率是R(D)，而不是无失真情况下的信源熵H(U).
显然 H(U)≥R(D).
当且仅当 D=0时，等号成立；
6） 为了定量度量D，必须建立信源的客观失真度量，并与D建立定量关系；
7） R(D)函数是限失真信源信息处理的理论基础；
（二） R(D)函数的定义
1） 信源与信宿联合空间上失真测度的定义：:
其中： （单消息信源空间）
（单消息信宿空间）
则有

称为统计平均失真，它在信号空间中可以看作一类“距离”，它有性质
1〉, 当
2〉
3〉
对离散信源：i=j=1,2……..n,
则有：

若取 为汉明距离，则有：

对连续信源，失真可用二元函数d(uv)表示。
则有：
推而广之，d(u,v)可表示任何用v表达u时所引进的失真，误差，损失，风险，甚至是主观感觉上的差异等等。
进一步定义允许失真D为平均失真的上界：
--对离散
在讨论信息率失真函数时，考虑到信源与信宿之间有一个无失真信道，称它为试验信道，对离散信源可记为，对限失真信源这一试验信道集合可定义为：

根据前面在互信息中已讨论过的性质：

且互信息是的上凸函数，其极限值存在且为信道容量：
这里，我们给出其对偶定义：

即互信息是的下凸函数。其极限值存在且为信息率失真函数。
它还存在下列等效定义：

称D(R)为失真信息率函数，是R(D)的逆函数，它是求在允许最大速率情况下的最大失真D。
至此，我们已给定R(D)函数一个初步描述。

由定义，R(D)函数是在限定失真为最大允许失真为D时信源最小信息速率，它是通过改变试验信道特性（实际上是信源编码）来达到的。所以R(D)是表示不同D值时对应的理论上最小信息速率值。
然而对于不同的实际信源，存在着不同类型的信源编码，即不同的试验信道特性并可以求解出不同的信息率失真R’(D)函数，它与理论上最佳的R(D)之间存在着差异，它反映了不同方式信源编码性能的优劣，这也正是R(D)函数的理论价值所在。特别对于连续信源，无失真是毫无意义的，这时R(D)函数具有更大的价值。
例：若有一个离散、等概率单消息（或无记忆）二元信源： ,且采用汉明距离作为失真度量标准：即 若有一具体信源编码方案为：N个码元中允许错一个码元，实现时N个码元仅送N-1个，剩下一个不送，在接收端用随机方式决定（为掷硬币方式）。此时，速率R’及平均失真D相应为：

若已知这一类信源理论上的（后面将进一步给出计算），则有

阴影范围表示实际信源编码方案与理论值间的差距，我们完全可以找到更好，即更靠近理论值，缩小阴影范围的信源编码，这就是工程界寻找好的信源编码的方向和任务。
§4-2 R(D)函数的性质
讨论R(D)性质以前先简要介绍R(D)的定义域。
对离散：
对应R(D)值：
。
对连续：

R(D)函数性质可用下列定理总结：
定理4－2－1：对离散、单个消息限定失真信源，其R(D)函数满足下列性质：
（1）R(D)是D的下凸（）函数；
（2）R(D)是D的单调非增函数；
（3）R(D)是D的连续函数；
（4）；
证明：（1）证明思路：根据R(D)函数定义，与下凸函数定义，只需证明：

首先证，再利用互信息对的下凸性。即：若用与表示达到与时的条件分布，且
则有：

这里，
由
可得
再利用互信息对的下凸性，有

（2）设 则

即R(D)是D的单调非增函数。
（3）设。
由定义，有。
同时，由于是连续函数。
即当 有
即，R(D)是D的连续函数。
（4）当，即无失真时，，一一对应

§4-3 离散信源R(D)函数计算：

可见，求解R(D)实质上是求解互信息的条件极值，可采用拉氏乘子法求解。但是，在一般情况下只能求得用参量（R(D)的斜率S）来描述的参量表达式，并借助计算机进行迭代运算。
由信道容量C与R(D)数学上对偶关系：

其迭代运算与求信道容量迭代运算相仿的。在正式讨论R(D)迭代运算前，这里，我们先介绍特殊情况下的R(D)计算。

具有等概率、对称失真信源的R(D)计算：
例1：有一个二元等概率平稳无记忆信源U，且失真函数为

试求其R(D)=?
解：由：
为了运算方便，取
上式中，已知：，D（允许失真）给定。
则一一对应。
这时，由概率归一性，可进一步假设：

可见：
代入上述公式，有
再将它代入转移概率公式中：

由：，得：
则：

例2：若有一个元等概率、平稳无记忆信源，且规定失真函数为：

试求R(D)=?
解：
由，求得

取，4，8，有

由上图可见
无失真时
，
，
，
有失真，比如时

显然 ① ，进制越小，压缩比越大；
② ，但相对关系不变，
允许失真越大，压缩比亦越大。

R(D)的参量表达式：
要讨论R(D)的计算，由R(D)函数定义，需要求下列约束条件下的互信息极值。
①
②
③
求解这类极值有好几种方法：
变分法、拉氏乘子法、凸规划方法等等。这里引用最简单的拉氏乘子法。但是它不能处理不等式约束关系，因此需对上述条件进行必要的修改，这时上述问题可归纳为在下列组约束条件下：

求互信息的极小值。
引用拉氏乘子法，并设与分别表示个约束条件的待定参数，则有：

求得 —— ①
由归一化条件有
求得 —— ②
再将①式两边同乘并对i求和，且设qj>0，则有

—— ③
代②入③，得：
—— ④
当信源给定，选定与以后，它是一个求解个的方程组，则可按下列顺序求解：

最后求得参量方程如下：

—— ⑥
这就是用参量[的斜率]表达的函数形式，又称为参量方程。
定理4-3-1：，即R(D)斜率为参量S。证明从略。
例：引用上述参量方程求解一个二进不等概率离散信源：，且其中，试求
解：首先求参量与
由公式③，有：

求得
将它带入式②，有

求得

再将带入⑤式中：

再将它带入，有：

取，的曲线：

由图可见：
无失真：

限失真，比如时

结论：1) 信源概率分布越不均匀，压缩比越大；
2) 越大，压缩比也越大。

R(D)函数的迭代算法
首先让我们从信道容量与函数定义与数学上的对偶性来分析：

显然，我们可以利用求解信道容量的计算迭代公式的方法与思路求解函数。其关键步骤为：
1)寻求两个决定互信息的互为因果关系的自变量对，这里选，且通过求极值；
2)对互信息求条件极值（极小值），引用拉氏乘子法；

具体求解步骤如下：
1) 两个自变量中首先固定值，则在满足和的约束条件下求的极小值。引用拉氏乘子法，有：
即 ， 求得：
，再由归一化条件
，
再代入原式得： —— ①
2) 再固定值，在满足（对所有值）和的约束条件下求极值：

由归一化条件，有

求出：
再将它带入表达式，求得
——②
① 式与②式是两个基本迭代公式
若假设一个值，比如，通过①②逐次迭代，求得，代入互信息公式中，求得

再继续假设、、、等。求得相应的、、、。最后再将其值连成一个曲线，即为函数曲线。
下面，为了迭代方便，可将①②改写为：

假设，则可按下列顺序迭代：（当信源给定，选一初始分布）

上述迭代至前后两值间误差小于给定值为止。可求得
重新假设、、、 ，分别求得、、、。最后连接各值为一条曲线，即为所求的函数曲线。

§4-4 连续信源R(D)函数
⒈连续信源比离散信源更需要R(D)函数。因为连续信源信息量为无限大（取值无限），传送信息量既无必要，也不可能。所以连续信源都是属于限失真范畴；
⒉连续信源R(D)与离散信源R(D)类似：
只需将概率换为概率密度
求和换为积分

则当已知信源概率分布密度为、条件密度为、失真函数为、
信源平均失真
而
则有：
同样，可以求出类似于离散的参量表达式：
即在下述限制条件下：

求互信息

的下确界。
引用变分，并引入待定常数和任意函数，再对取变分，并置之为0。
所谓变分是指求泛函的极值。即

其求解顺序完全类似于离散情况，但需求解一个积分方程。最后结果为：

连续信源能否有类似于离散信源的一些特殊情况，不需求解繁琐的积分方程呢？的确存在，在某些情况下，比如时，求解可大大减化。即
若二元函数仅与与差值有关，比如

这时令参量，设，其中，且，这时可求得：
可见，由上述卷积表达式，无需求解积分方程就可以求得分布密度。
进一步，若令、和分别表示、和的特征函数，则由以上时域的卷积关系，求得下列特征函数间的关系如下：

则
再由类似于离散信源的下列求解顺序：

例：若
当时，求
则

即
∴　
而信源p(u)的特征函数为

再由最后求得：

定理2-4-1：对任一连续非正态信源，若已知其方差为，熵为，并规定失真函数为，则其R(D)满足下列不等式：
（正态） （上限）
可见，在平均功率受限条件下，正态分布R(D)函数值最大，它是其他一切分布的上限值，也是信源压缩比中最小的。所以人们往往将它作为连续信源压缩比中最保守的估计值。

例：对连续有记忆信源R(D)函数计算相当复杂，下面考虑一个简单的特例：对一个广义平稳遍历马氏链信源，且有，其中。现求其R(D)函数。
下面我们仅给出结果：

而

结论：
1）（越大）， （越小）， 压缩比
2） ， ， 压缩比K

下面利用连续信源的R(D)函数，进一步分析语音的波形编码：
为了分析方便，假设语音遵从平稳正态分布：
例1：分析PCM编码及其压缩潜力：
现有PCM编码是8KHz采样率，8位编码，8*8=64Kb/s，它认为样点间独立，且每个样点8bit，这时信噪比可达到入公用网26dB的要求，在语音编码中信噪比是，其中D为噪声（允许失真）功率，由正态分布的信息率失真函数的公式：

实际语音的R(D)值要小于4.3bit，因为语音不遵从正态分布，而是近似遵从Laplace分布（一级近似）、Gamma分布（二级近似）。它们的R(D)函数值均小于正态分布的R(D)值，。可见，4.3bit至PCM 8bit，大约有一倍差距。

例2：若对语音编码进一步计入相关性，则其R(D)函数为：，则可算出其R(D)值，即对应压缩比（相对于PCM编码64Kb/s）
信噪比（dB）
35
32
28
25
23
20
17
R(D)(bit)
4
3.5
2.5
2.34
2
1.5
1
压缩倍数
2
2.28
3.2
3.42
4
5.3
8
若计入语音分布R(D)值小于正态分布值，以及R(D)的主观特征，在25-26dB要求下，实际R(D)值大约等于2左右，可以获得大约4倍的压缩比。

例3：参量编码：
以英语为例，其音素大约为128~256个，按照通常讲话速率，每秒大约平均发出10 个音素，这时语音信源给出的信息率为：

- 29 -