限失真信源与信息率失真函数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, 当 23对离散信源：i=j=1,2.n,则有： 若取 为汉明距离，则有：对连续信源，失真可用二元函数d(u,v)表示。则有：推而广之，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)函数性质可用下列定理总结：定理421：对离散、单个消息限定失真信源，其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求和，且设qj0，则有 代入，得： 当信源给定，选定与以后，它是一个求解个的方程组，则可按下列顺序求解：最后求得参量方程如下： 这就是用参量的斜率表达的函数形式，又称为参量方程。定理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