信息率失真函数1课件

1、第四章 信息率失真函数 第四章 信息率失真函数 无失真信源编码和有噪信道编码（香农第一定理和香农第二定理）告诉我们：只要信道的信息传输速率小于信道容量，总能找到一种编码方法，使得在该信道上的信息传输的差错概率任意小；反之，若信道的信息传输速率大于信道容量，则不可能使信息传输差错概率任意小。但是，无失真的编码并非总是必要的。无失真信源编码和有噪信道编码（香农第一定理和香农第二定理）告原始图像红色图像绿色图像蓝色图像原始图像和限失真图像原始图像红色图像绿色图像蓝色图像原始图像和限失真图像香农首先定义了信息率失真函数R(D)，并论述了关于这个函数的基本定理。定理指出：在允许一定失真度D的情况下，信源

2、输出的信息传输率可压缩到R(D)值，这就从理论上给出了信息传输率与允许失真之间的关系，奠定了信息率失真理论的基础。信息率失真理论是进行量化、数模转换、频带压缩和数据压缩的理论基础。本章主要介绍信息率失真理论的基本内容，重点讨论离散无记忆信源。给出信源的失真度和信息率失真函数的定义与性质；讨论离散信源和连续信源的信息率失真函数计算；在此基础上论述保真度准则下的信源编码定理。香农首先定义了信息率失真函数R(D)，并论述了关于这个函数的 4.1 失真测度一、失真度从直观感觉可知，若允许失真越大，信息传输率就可越小；若允许失真越小，信息传输率需越大。所以信息传输率与（信源）编码所引起的失真(或误差)是

3、有关的。 4.1 失真测度一、失真度 首先讨论失真的测度。 离散无记忆信源X，信源符号集Xa1,a2,ar，概率分布为p(x)p(a1),p(a2),p(ar) 。 信源符号通过信道传输到接收端，接收端的接收符号集Y b1,b2,bs 。 对应于每一对(ai,bj)，我们指定一个非负的函数：称为单个符号的失真度(或失真函数)。 通常较小的d值代表较小的失真，而d(ai,bj)0表示没有失真。 首先讨论失真的测度。称为单个符号的失真度(或失真函数若信源变量X有r个符号，接收变量Y有s个符号，则d(ai,bj)就有rs个,它可以排列成矩阵形式，即：该失真矩阵D，是 rs 阶矩阵。若信源变量X有r个

4、符号，接收变量Y有s个符号，则d(ai,b实际这里X指的是原始的未失真信源，而Y是指失真以后的信源。如果假设X是信源，Y是信宿，那么X和Y之间必有信道。从X到Y之间实际上是失真算法，所以这里的转移概率p(bj/ai)是指一种失真算法，有时又把 p(bj/ai) 称为试验信道的转移概率，如图所示。原始信源失真信源试验信道信道XYp (bj/ai)实际这里X指的是原始的未失真信源，而Y是指失真以后的信源。如 例1 离散对称信源(r=s)，“0-1”失真。信源Xa1,a2,ar ，接收Y b1,b2,bs。定义单个符号失真度：这种失真称为汉明失真。汉明失真矩阵是一方阵，对角线上的元素为零，即： 对二

5、元对称信源(sr2)，信源X0,1，接收变量Y0,1。在汉明失真定义下，失真矩阵为： 例1 离散对称信源(r=s)，“0-1”失真。信源X 例2 删除信源。信源Xa1,a2,ar ，接收Y b1,b2,bs (s = r+1) 。定义其单个符号失真度为：其中接收符号bs作为一个删除符号。此时，意味着若把信源符号再现为删除符号bs时，其失真程度要比再现为其他接收符号的失真程度少一半。二元删除信源 r 2， s 3，X0,1，Y0,1 ,2 。失真度为： 则d(0,0)=d(1,1)=0 d(0,1)=d(1,0)=1d(0,2)=d(1,2)=1/2除j=s以外所有的j和i所有i 例2 删除信源

6、。信源Xa1,a2,ar ，接收 例 对称信源(s = r) 。信源Xa1,a2,ar ，接收Y b1,b2,bs 。若失真度定义为：如果信源符号代表信源输出信号的幅度值，这就是一种平方误差失真度。它意味着幅度差值大的要比幅度差值小的所引起的失真更为严重，其严重的程度用平方来表示。 当 r3时， 0,1,2，0,1,2 ，则失真矩阵为：上述例子说明了失真度的具体定义。一般情况下根据实际信源的失真，可以定义不同的失真和误差的度量。另外还可以按其他标准，如引起的损失、风险、主观感觉上的差别大小等来定义失真度d(a,b)。 例 对称信源(s = r) 。信源Xa1,a2,二、序列失真度设 ，其中取自

7、信源符号集A； 其中取自信宿符号集B。则序列失真度定义为： 二、序列失真度设 三、 平均失真度信源 X 和信宿 Y 都是随机变量，故单个符号失真度d(ai,bj) 也是随机变量。规定了单个符号失真度d(ai,bj) 后，传输一个符号引起的平均失真，即信源平均失真度： 在离散情况下，信源Xa1,a2,ar ，其概率分布p(x)p(a1),p(a2),p(ar) ，信宿Y b1,b2,bs 。若已知试验信道的传递概率为p(bj/ai)时，则平均失其度为：三、 平均失真度信源 X 和信宿 Y 都是随机变量，故单个 若平均失真度D不大于我们所允许的失真D0，即： D D0 称此为保真度准则。信源固定（

8、即给定了p(x)），单个符号失真度固定时（即给定了d(ai,bj)） ，选择不同试验信道，相当于不同的编码方法，所得的平均失真度是不同的。有些试验信道满足D D0，而有些试验信道DD0。凡满足保真度准则-平均失真度D D0的试验信通称为 -D失真许可的试验信道。把所有D失真许可的试验信道组成一个集合，用符号PD表示，则： PD=p (bj / ai)： D D0 若平均失真度D不大于我们所允许的失真D0，即：信源固定（即4.2 信息率失真函数及其性质一、信息率失真函数的定义 信源给定，且又具体定义了失真函数以后，总希望在满足一定失真的情况下，使信源传输给收信者的信息传输率R尽可能地小。-即在满

9、足保真度准则下，寻找信源必须传输给信宿的信息率R的下限值-这个下限值与D有关。从接收端来看，就是在满足保真度准则下，寻找再现信源消息所必须获得的最低平均信息量。而接收端获得的平均信息量可用平均互信息I(X;Y)来表示，这就变成了在满足保真度准则的条件下，寻找平均互信息I(X;Y)的最小值。4.2 信息率失真函数及其性质一、信息率失真函数的定义 信寻找平均互信息I(X;Y)的最小值。而PD是所有满足保真度准则的试验信道集合，因而可以在D失真许可的试验信道集合PD中寻找一个信道p(bj / ai) ，使I(X;Y) 取极小值。由于平均互信息I(X;Y)是p(bj / ai)的U型凸函数，所以在PD

10、集合中，极小值存在。这个最小值就是在D D0的条件下，信源进行传输的最小平均信息量。即：R(D)-信息率失真函数或简称率失真函数 单位是：比特信源符号寻找平均互信息I(X;Y)的最小值。而PD是所有满足保真度准率失真函数给出了熵压缩编码可能达到的最小熵率与失真的关系;其逆函数D(R)称为失真率函数, D(R)表示一定信息速率下所可能达到的最小的平均失真。 率失真函数给出了熵压缩编码可能达到的最小熵率与失真的关系;二、信息率失真函数的性质允许失真度D的下限可以是零，这是不允许任何失真的情况。 1、 R(D)的定义域R(D)的定义域为 且：二、信息率失真函数的性质允许失真度D的下限可以是零，这是不

11、允解：例4 设试验信道输入符号集 ，各符号等概分布 ，失真矩阵如下所示，求 和 以及相应的试验信道的转移概率矩阵。 令对应最小失真度 的 ，其它为“0”，可得对应 的试验信道转移概率矩阵为： 解：例4 设试验信道输入符号集 上式中第二项最小，所以令 ， ，可得对应 的试验信道转移概率矩阵为:上式中第二项最小，所以令 2、 R(D)是关于平均失真度D的下凸函数 设 为任意两个平均失真， ，则有： 3 、 R(D) 是 区间上的连续和严格单调递减函数。 信息率失真函数的一般形状 () 2、 R(D)是关于平均失真度D的下凸函数 设 4.3 离散无记忆信源的信息率失真函数 已知信源的概率分布p(x)

12、和失真函数d(x,y)，就可求得信源的R(D)函数。原则上它与信道容量一样，即在有约束条件下求极小值的问题。 也即选取适当的试验信道p(x/y)使平均互信息最小化：其约束条件为: 一般取等号4.3 离散无记忆信源的信息率失真函数 已知一、 等概率、对称失真信源的R(D)计算 对于等概、对称失真的信源，存在一个与失真矩阵具有同样对称性的转移概率分布达到率失真R(D)。一、 等概率、对称失真信源的R(D)计算 对于解：例5有一个二元等概平稳无记忆信源 ，接收符号集为 且失真矩阵为 ： 求率失真函数R(D) 。由于信源等概分布，失真函数具有对称性，因此，存在着与失真矩阵具有同样对称性的转移概率分布达

13、到率失真R(D) ，该转移概率矩阵可写为：由于 ，因此对于任何有限平均失真，必须 ,于是转移概率矩阵为：解：例5有一个二元等概平稳无记忆信源 对应此转移概率矩阵的平均失真：因此: 可求得此时的互信息为：对应此转移概率矩阵的平均失真：二、 信息率失真函数的参量表述 求信源的R(D)函数，原则上与求信道容量一样，是在有约束条件下求极小值的问题。 也就是适当选取试验信道p(y/x)使平均互信息最小化， 应用拉格朗日乘子法，原则上可以求出解来。二、 信息率失真函数的参量表述 求信源的R(D困难在于：要得到显式的解析表达式，则比较困难，通常只能用参量形式来表达。要保证约束条件式p(bj/ai) 0，应用

14、拉格朗日乘子法解得的某些p(bj/ai)很可能是负的。在这情况下，必须假设其p(bj/ai) =0，然后重新计算，这就使得计算复杂化了。下面介绍用拉格朗日乘子法求解R(D)函数，并用s作为参量来表述率失真函数R(s)和失真函数D(s)。困难在于： 由 (1)式知，当信源的概率分布p(x)固定，平均互信息仅仅是试验信道p(bj/ai)的函数。若先不考虑 (2)式的约束，约束条件 (3)式包含n个等式，取拉格朗日乘子i(i1,2, n)分别与之对应；并取拉氏乘子s与 (4)式对应。由此构成辅助函数：(2)(3)(4)(1) 由 (1)式知，当信源的概率分布p(x)固定，平均互信息仅求极值，即为求(

15、5) 式一阶导数等于零的方程组的解。已知平均互信息I(X;Y)是信道P的U型凸函数，所以，若极值存在，它一定是极小值。即求：得：-(6)求极值，即为求(5) 式一阶导数等于零的方程组的解。得：-(6)(1)(3)(4)-(6)(1)(3)(4)经整理得结论：经整理得结论：注：这时所得的结果是以s为参量的表达式，而不是显式表达式，因而所得到的R(D)的表达式也是以s为参量的表达式。参量s对应的限制条件为(4)式，它与允许的失真度D有关，所以，以s为参量就相当于以D为参量。(4)注：这时所得的结果是以s为参量的表达式，而不是显式表达式，因 例6 设离散信源和接收变量：并设失真矩阵为:求该信源的信息

16、率失真函数R(D)。 解：根据(4.2.4)式计算可得 ，由题已知，根据参量表达式按如下步骤进行。第一步：由式(4.3.14)求 例6 设离散信源和接收变量：求该信源的信息率失真函数第二步：由式(4.3.13)求第二步：由式(4.3.13)求第三步：由式(4.3.16)求D(s)，将上述结果代入式(4.3.16)有第三步：由式(4.3.16)求D(s)，将上述结果代入式(4第四步：由式(4.3.17)求R(s) ：应用式(4.3.11)，还可求得此时的试验信道转移概率：第四步：由式(4.3.17)求R(s) ：应用式(4.3.14.4 连续无记忆信源的信息率失真函数研究连续信源的信息率失真函数

17、比离散信源更有实际意义，因为连续随机变量不可能用有限比特加以精确描述，即连续信源信息量为无限大，传送无限大信息量既无必要，也不可能。所以连续信源的讨论都属于限失真范畴。4.4 连续无记忆信源的信息率失真函数研究连续信源的信息率失一、连续无记忆信源的信息率失真函数的定义 连续信源的平均失真度定义为： 通过试验信道获得的平均互信息为：同样，确定一允许失真度D，凡满足平均失真小于D的所有试验信道的集合记为PD，则连续信源的信息率失真函数定义为：一、连续无记忆信源的信息率失真函数的定义通过试验信道获得的平 二、高斯信源的信息率失真函数 对高斯信源，在一般失真函数下，其率失真函数是很难求得的，但在平方误

18、差失真度量下，其率失真函数有简单的封闭表达式。 对平方误差失真，试验信道输入符号和输出符号之间失真为： 对应的平均失真度为： 二、高斯信源的信息率失真函数 对应的平均失真度为：在平方误差失真下，设允许失真为D，则高斯信源 的率失真函数为：下图表示当 时， 的曲线。在平方误差失真下，设允许失真为D，则高斯信源 三、连续无记忆信源信息率失真函数的参量表述类似于离散信源，连续信源的率失真函数的计算也归结为求有约束极值的问题，不过在连续信源情况下试验信道的条件概率也是函数，所以，率失真函数的计算就变成求泛函的极值，即求： 的极小值，满足约束条件为： 三、连续无记忆信源信息率失真函数的参量表述的极小值，

19、满足约 约束条件下的泛函求极值问题和约束条件下的函数求极值问题类似，即利用拉格朗日乘子将问题转化为无约束极值问题，并用变分代替微分，对本节讨论的问题，等价于使下式的一阶变分为零： 其中 为待定函数，s为待定常数，其求解顺序完全类似于离散情况。 约束条件下的泛函求极值问题和约束条件下的函数在此我们仅给出最终结论：在连续无记忆信源下，达到信息率失真函数的试验信道的转移概率密度函数必需满足：其中在此我们仅给出最终结论：其中此时的率失真函数和失真D满足参量方程： 需要说明的是，连续情况下的信息率失真函数与离散情况下信息率失真函数的一个主要差别在于当时，由于连续信源的差熵而使从此意义上讲，连续信源的熵压缩编码是必不可少的。此时的率失真函数和失真D满足参量方程： 需要说明的是， 四、差值失真度量下连续无记忆信源的信息率失真函数 一般情况下，连续无记忆信源下信息率失真函数的计算相当困难，绝大多数情况下无解析解。 但当连续信源的失真函数D (x,y)为x和y的差值形式如： |x-y|，(x-y)2时，可以较容易地采用参量表述式来求得其上、下限。 四、差值失真度量下连续无记忆信源的信息率失真函数 (1) 差值失真度量下率失真函数的Shannon下限 上式是香农首先得到的，因此称其右端为差值失真度量时连续信源的香农下限。 (2) 平方误差(差方)失真度量下率失真