第4章 信息率失真函数.ppt

《第4章 信息率失真函数.ppt》由会员分享，可在线阅读，更多相关《第4章 信息率失真函数.ppt（49页珍藏版）》请在三一文库上搜索。

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

2、息率失真理论是进行量化、数模转换、频带压缩和数据压缩的理论基础。 本章主要介绍信息率失真理论的基本内容，重点讨论离散无记忆信源。 给出信源的失真度和信息率失真函数的定义与性质； 讨论离散信源和连续信源的信息率失真函数计算； 在此基础上论述保真度准则下的信源编码定理。,4.1 失真测度,一、失真度 从直观感觉可知，若允许失真越大，信息传输率就可越小；若允许失真越小，信息传输率需越大。 所以信息传输率与（信源）编码所引起的失真(或误差)是有关的。,首先讨论失真的测度。 离散无记忆信源X，信源符号集Xa1,a2,ar，概率分布为p(x)p(a1),p(a2),p(ar) 。 信源符号通过信道传输到接

3、收端，接收端的接收符号集Y b1,b2,bs 。 对应于每一对(ai,bj)，我们指定一个非负的函数：,称为单个符号的失真度(或失真函数)。 通常较小的d值代表较小的失真，而d(ai,bj)0表示没有失真。,若信源变量X有r个符号，接收变量Y有s个符号，则d(ai,bj)就有rs个,它可以排列成矩阵形式，即：,该失真矩阵D，是 rs 阶矩阵。,实际这里X指的是原始的未失真信源，而Y是指失真以后的信源。如果假设X是信源，Y是信宿，那么X和Y之间必有信道。 从X到Y之间实际上是失真算法，所以这里的转移概率p(bj/ai)是指一种失真算法， 有时又把 p(bj/ai) 称为试验信道的转移概率，如图所

4、示。,例1 离散对称信源(r=s)，“0-1”失真。信源Xa1,a2,ar ，接收Y b1,b2,bs。定义单个符号失真度：,这种失真称为汉明失真。汉明失真矩阵是一方阵，对角线上的元素为零，即：,对二元对称信源(sr2)，信源X0,1，接收变量Y0,1。在汉明失真定义下，失真矩阵为：,例2 删除信源。信源Xa1,a2,ar ，接收Y b1,b2,bs (s = r+1) 。定义其单个符号失真度为：,其中接收符号bs作为一个删除符号。 此时，意味着若把信源符号再现为删除符号bs时，其失真程度要比再现为其他接收符号的失真程度少一半。 二元删除信源 r 2， s 3，X0,1，Y0,1 ,2 。 失

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

6、单个符号失真度d(ai,bj) 也是随机变量。 规定了单个符号失真度d(ai,bj) 后，传输一个符号引起的平均失真，即信源平均失真度：,在离散情况下，信源Xa1,a2,ar ，其概率分布p(x)p(a1),p(a2),p(ar) ，信宿Y b1,b2,bs 。 若已知试验信道的传递概率为p(bj/ai)时，则平均失其度为：,若平均失真度D不大于我们所允许的失真D0，即： D D0 称此为保真度准则。,4.2 信息率失真函数及其性质,一、信息率失真函数的定义,信源给定，且又具体定义了失真函数以后，总希望在满足一定失真的情况下，使信源传输给收信者的信息传输率R尽可能地小。-即在满足保真度准则下，

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

8、的最小平均信息量。即：,R(D)-信息率失真函数或简称率失真函数 单位是：比特信源符号,率失真函数给出了熵压缩编码可能达到的最小熵率与失真的关系; 其逆函数D(R)称为失真率函数, D(R)表示一定信息速率下所可能达到的最小的平均失真。,二、信息率失真函数的性质,允许失真度D的下限可以是零，这是不允许任何失真的情况。,1、 R(D)的定义域,R(D)的定义域为 且：,解：,例4 设试验信道输入符号集 ，各符号等概分布 ，失真矩阵如下所示，求 和 以及相应的试验信道的转移概率矩阵。,令对应最小失真度 的 ，其它为“0”，可得对应 的试验信道转移概率矩阵为：,上式中第二项最小，所以令 ， ，可得对

9、应 的试验信道转移概率矩阵为:,2、 R(D)是关于平均失真度D的下凸函数,设 为任意两个平均失真， ，则有：,3 、 R(D) 是 区间上的连续和严格单调递减函数。,信息率失真函数的一般形状,(),4.3 离散无记忆信源的信息率失真函数,已知信源的概率分布p(x)和失真函数d(x,y)，就可求得信源的R(D)函数。原则上它与信道容量一样，即在有约束条件下求极小值的问题。 也即选取适当的试验信道p(x/y)使平均互信息最小化：,其约束条件为:,一般取等号,一、 等概率、对称失真信源的R(D)计算,对于等概、对称失真的信源，存在一个与失真矩阵具有同样对称性的转移概率分布达到率失真R(D)。,解：

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

11、式，则比较困难，通常只能用参量形式来表达。 要保证约束条件式p(bj/ai) 0，应用拉格朗日乘子法解得的某些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),(

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

13、14)求,第二步：由式(4.3.13)求,第三步：由式(4.3.16)求D(s)，将上述结果代入式(4.3.16)有,第四步：由式(4.3.17)求R(s) ：,应用式(4.3.11)，还可求得此时的试验信道转移概率：,4.4 连续无记忆信源的信息率失真函数,研究连续信源的信息率失真函数比离散信源更有实际意义，因为连续随机变量不可能用有限比特加以精确描述，即连续信源信息量为无限大，传送无限大信息量既无必要，也不可能。 所以连续信源的讨论都属于限失真范畴。,一、连续无记忆信源的信息率失真函数的定义 连续信源的平均失真度定义为：,通过试验信道获得的平均互信息为：,同样，确定一允许失真度D，凡满足平

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

15、：,的极小值，满足约束条件为：,约束条件下的泛函求极值问题和约束条件下的函数求极值问题类似，即利用拉格朗日乘子将问题转化为无约束极值问题，并用变分代替微分，对本节讨论的问题，等价于使下式的一阶变分为零：,其中 为待定函数，s为待定常数，其求解顺序完全类似于离散情况。,在此我们仅给出最终结论： 在连续无记忆信源下，达到信息率失真函数的试验信道的转移概率密度函数必需满足：,其中,此时的率失真函数,从此意义上讲，连续信源的熵压缩编码是必不可少的。,四、差值失真度量下连续无记忆信源的信息率失真函数,一般情况下，连续无记忆信源下信息率失真函数的计算相当困难，绝大多数情况下无解析解。 但当连续信源的失真函

16、数D (x,y)为x和y的差值形式如： |x-y|，(x-y)2时，可以较容易地采用参量表述式来求得其上、下限。,(1) 差值失真度量下率失真函数的Shannon下限,上式是香农首先得到的，因此称其右端为差值失真度量时连续信源的香农下限。,(2) 平方误差(差方)失真度量下率失真函数的上限 对均值为零，方差为的任意连续无记忆信源，在差方失真度量下的率失真函数满足如下结论：,4.5 保真度准则下的信源编码定理,定理4.1 (保真度准则下的信源编码定理，香农第三定理) 设R(D)为一离散无记忆信源的信息率失真函数，并且有有限的失真测度D。对于任意 D ，以及任意长的码长k，一定存在一种信源编码C，

17、其码字个数为 使编码后码的平均失真度 。,定理的含义是：只要码长k足够长，总可以找到一种信源编码，使编码后的信息传输率略大于(直至无限逼近)率失真函数R(D)，而码的平均失真度不大于给定的允许失真度，即：,由于R(D)为给定D前提下信源编码可能达到的传信率的下限， 所以香农第三定理说明了： 达到此下限的最佳信源编码是存在的。,实际的信源编码(无失真编码或先进行限失真编码后再进行无失真编码)的最终目标是尽量接近最佳编码，使编码信息传输率接近最大值，或者对给定的信源用尽量少的编码符号进行传输，而同时又能保证译码后能无失真地恢复信源。 编码后信息传输率的提高使每个编码符号能携带尽可能多的信息量， -使得传输同样多的信源总信息量所需的码符号数减少； -使所需的单位时间传输信道单位时间信道容量Ct减少，或在Ct不变的前提下使传输时间缩短，从而提高通信的效率。,