《信息论与编码》课件1第8章.ppt

1、第第8章章 限失真信源编码限失真信源编码 第第8章章 限失真信源编码限失真信源编码 8.1 失真函数与平均失真失真函数与平均失真 8.2 信息率失真函数及其性质信息率失真函数及其性质 8.3 信息率失真函数的计算信息率失真函数的计算 8.4 保真度准则下的信源编码定理保真度准则下的信源编码定理 8.5 限失真信源编码的基本原理限失真信源编码的基本原理习题习题8第第8章章 限失真信源编码限失真信源编码 由第3章的讨论我们知道，在图8-1给出的简单信息传输系统中，系统的信息传输率为 R=I(X;Y)由于平均互信息I(X;Y)是信源概率分布P(x)和信道转移概率分布P(y|x)的函数，并且I（X;Y

2、）=IP(x);P(y|x)是信源概率分布P(x)的上凸函数，是信道转移概率分布P(y|x)的下凸函数，因此如果信息传输系统中的信源不同（P(x)不同）或者信道不同（P(y|x)不同），则该信息传输系统的信息传输率R不同。第第8章章 限失真信源编码限失真信源编码 图8-1 简单信息传输系统第第8章章 限失真信源编码限失真信源编码 第5章中我们讨论了使用固定信道传输不同信源信息的情况。由于此时信道转移概率分布P(y|x)固定不变，平均互信息I(X;Y)仅随着信源概率分布P(x)的改变而改变，且是信源概率分布P(x)的上凸函数,因此，对于给定的信道（P(y|x)固定），仅改变信源（P(x)可变）时

3、可以求出I(X;Y)的极大值，此极大值反映出了给定信道信息传输的能力，并被定义为给定信道的信道容量：()max(;)P xI X Y()max(;)P xCI X Y第第8章章 限失真信源编码限失真信源编码 与此类似，如果使用不同的信道传输同一信源（P(x)固定）输出的信息，则系统的信息传输率将随着信道转移概率P(y|x)的变化而改变。由于平均互信息I(X;Y)是信道转移概率分布P(y|x)的下凸函数，因此一定可以找到一个信道，当使用该信道传输给定信源输出的信息时，系统的信息传输率最小。此最小的平均互信息反映出了传输该给定信源信息时必须有的最小信息传输率。显然，与是一个成对偶关系的理论问题。(

4、/)min(;)P y xI X Y(/)min(;)P y xI X Y()max(;)P xI X Y第第8章章 限失真信源编码限失真信源编码 对于一个给定的信源，可以使用不同的信源编码方法表示其输出的信息。从信息传输系统的有效性考虑，我们希望找出一种信源编码方法（可以看做某种信道），采用该方法表示给定信源输出的符号时，信息传输率R最小，以构成一种最有效的信息传输系统。由平均互信息I（X;Y）的非负性可知：minI(X;Y)=0第第8章章 限失真信源编码限失真信源编码 但是当I(X;Y)=0即H(Y)H(Y|X)=0H(Y|X)=H(Y)时，信道的转移概率:P(y|x)=P(y)第第8章章

5、 限失真信源编码限失真信源编码 表明该信道的输出Y与其输入X相互独立，由Y根本得不到关于信源X的任何信息。由此可见，若使用R=I(X;Y)=0的信道传输给定信源输出信息，则信道的输出Y与信源的输出X相比面目全非，信息传输系统中产生了严重的失真，以至于完全丧失了传输信息的能力。因此，关于信息传输系统有效性的分析，应当将信息传输率R与系统产生的失真联系起来，对于给定的信源（P(x)固定），度量Y与X之间的失真，并在一定的失真限度内寻求信息传输率R,即平均互信息的最小值。(/)min(;)P y xI X Y第第8章章 限失真信源编码限失真信源编码 第7章我们讨论的无失真信源编码是一类在完全不允许失

6、真（即失真度为零）的条件下的信源编码问题。根据无失真信源编码定理，信源的信息熵是进行无失真编码时编码器信息传输率的理论下界。本章讨论的信息率失真函数表示在某一失真限度下，传输给定信源信息时需要的最小信息传输率。本课程主要针对离散无记忆信源，介绍信息率失真理论的基本概念，给出失真的度量、信息率失真函数R(D)的定义和性质。下面我们将在允许一定限度内的信息损失的条件下，分析平均互信息I（X；Y）的最小值问题，在最简单的条件下介绍信息率失真函数的计算，给出保真度准则下的限失真信源编码定理，初步讨论限失真信源编码的基本原理和主要方法。第第8章章 限失真信源编码限失真信源编码 8.1 失真函数与平均失真

7、失真函数与平均失真由于人类生理、心理特性的影响，在实际的信息传递过程中，人们往往并不要求完全无失真地表示信源输出的信息，而是要求在一定保真度（失真限度）条件下，近似地还原信源输出的消息。为了讨论一定失真限度条件下的最小信息传输率，首先需要对信源、信道的输出给出一个定量的失真测度。考虑图8-2所示的信息传输系统。第第8章章 限失真信源编码限失真信源编码 图8-2 简单信息传输系统 第第8章章 限失真信源编码限失真信源编码 设离散无记忆信源:经信道P(vj|ui)传输后，接收符号集为V=v1,v2,vs 1212.,()()().()rruuuU P uP uP uP u第第8章章 限失真信源编码

8、限失真信源编码 1.单个符号的失真函数单个符号的失真函数对于信道的每一对输入ui和输出取值vj，指定一个非负数：d(ui,vj)0 i=1,2,r;j=1,2,s(8.1)表示ui与vj之间的误差或失真，被称为单个符号的失真函数。显然，若vj=ui，则用vj表示ui时便没有产生失真，于是，d(ui,vj)=0；若vjui，则d(ui,vj)0。失真函数定量地描述了用vj表示ui时引起的失真、损失、风险和主观感觉上的差异大小，其具体的度量方式应视应用场合而定。第第8章章 限失真信源编码限失真信源编码 常用的失真函数有以下几种。（1）均方失真：d(ui,vj)=(uivj)2 （2）绝对失真：d(

9、ui,vj)=|uivj|第第8章章 限失真信源编码限失真信源编码 (3)相对失真：(4)汉明失真：|-|(,)|ijijiuvd uvu0(,)(-)(0)ijijijijuvd uvuvaauv第第8章章 限失真信源编码限失真信源编码 2.失真函数的表示失真函数的表示由于信源U有r种可能取值，而接收符号集V有s种可能取值，因此，对于不同的i、j取值，U、V之间共有rs个失真函数d(ui,vj)。它们可以排列成一个rs的矩阵，即此矩阵称为失真函数矩阵。111212122212(,)(,)(,)(,)(,)(,)(,)(,)(,)ssrrrsd u vd u vd u vd u vd u vd

10、 u vd u vd u vd u vD第第8章章 限失真信源编码限失真信源编码 3.K维随机矢量的失真函数维随机矢量的失真函数若信道的输入与输出是K维随机矢量，则可以将单个符号的失真函数的定义加以推广。设信源输出的符号序列U=（U1，U2，UK），其中每一随机变量Ui(i=1,2,K)取自同一符号集u1,u2,ur，所以信源输出的符号序列U共有rK种可能的取值。接收端的符号序列为V=(V1,V2,VK)，其中每一个随机变量Vj(j=1,2,K)取自同一符号集v1,v2,vs，因此，V共有sK种可能的取值。第第8章章 限失真信源编码限失真信源编码 又设，分别是U、V的样矢量，则ul与vm之间的

11、失真函数为(8.2)对于不同的输入、输出符号序列，共有rKsK个失真函数，可写成矩阵形式DK，称之为信道输入、输出为K维随机矢量时的失真函数矩阵，它是一个rKsK阶矩阵。12(,)Klllluuuu12(,)Kllllvvvv11(,)(,)iiKKlmlmidd uvKu vKKsmrl,2,1;,2,1第第8章章 限失真信源编码限失真信源编码【例例8.1】已知U、V0,1，失真函数定义为。若作二次扩展，即U，V00，01，10，11，则二维随机矢量u、v之间的失真函数为0110D2221(00,00)02(0,0)(0,0)11(00,01)2(0,0)(0,1)21(11,11)02(1

12、,1)(1,1)ddddddddd第第8章章 限失真信源编码限失真信源编码 依次可写出u、v之间的失真函数矩阵:2110122011211011021122111201210222110111022D第第8章章 限失真信源编码限失真信源编码 4.平均失真平均失真由失真函数d(ui,vj)的定义可以看出，对于不同的ui、vj，d(ui,vj)的值可能不同。因此，失真函数d(ui,vj)是一个伴随着随机变量ui和vj的发生而发生的随机变量，发生的概率为P(ui,vj)。于是，在信息传输系统中产生的失真可以使用失真函数的统计平均值来表示。平均失真定义为(8.3)11(,)(,)(,)rsijijij

13、ijdE d u vP u v d u v第第8章章 限失真信源编码限失真信源编码 若已知信道转移概率P(vj|ui)，则平均失真可进一步表示为(8.4)可见，单个符号的失真函数d(ui,vj)描述了某个信源符号经过信道传输后的失真大小，对于不同的信源符号和不同的接收符号，其值是不同的，而平均失真则是从总体上描述整个系统失真情况的一个量。d11()(|)(,)rsijiijijdP u P vu d u v第第8章章 限失真信源编码限失真信源编码 若信道的输入、输出为K维随机矢量U、V，则系统的平均失真定义为(8.5)11(,)(,)(,)(,)(|)(,)KKrmKKKKlmKlmlmlmm

14、lKlmdE dPdPPduvu vu vu vvuu v第第8章章 限失真信源编码限失真信源编码 也可写成：(8.6)11111()(|)(,)1()(|)(,)KKKKiirsKlmlKlmijrsKlmlKlmijldPPdPPduvKuvuu vuvu第第8章章 限失真信源编码限失真信源编码 当信源与信道都是无记忆时，可进一步简化为(8.7)其中，是K维随机矢量的第i个分量的平均失真。如果离散信源是平稳的，则有和，即通过离散无记忆信道传输离散无记忆平稳信源输出的符号序列时，系统的平均失真等于信源输出单个符号的平均失真。1111(,)iiKKKlmiiidE d uvdKKidKddid

15、dd第第8章章 限失真信源编码限失真信源编码 8.2 信息率失真函数及其性质信息率失真函数及其性质8.2.1 D失真许可准则与失真许可准则与D失真许可信道失真许可信道在实际的通信过程中，人们对于通信质量的要求一般是从统计平均的意义上进行考查和度量的。为了满足一定的通信质量要求，需要对系统中产生的失真加以限制，要求信息传输系统所产生的平均失真不能够大于某一给定的常数D，即满足：D(8.8)dd第第8章章 限失真信源编码限失真信源编码 由于常数D为信息传输系统中所允许的失真限度，因此式(8.8)称为信息传输系统的D失真许可准则。考虑一个使用不同信道P(vj|ui)传输给定的信源U输出符号的信息传输

16、过程，信道的输出符号为随机变量V。显然，使用不同信道传输该给定信源信息时，系统的信息传输率R=I(U;V)不同，产生的失真也不同。在定义了失真函数d(ui,vj)之后，我们总是希望在允许一定失真限度D的条件下，使得传输信源信息的信息传输率R=I(U;V)尽可能地小。也就是说,在D失真许可准则(D)下，寻找传输该给定信源信息的信息传输率R=I(U;V)的最小值。d第第8章章 限失真信源编码限失真信源编码 由平均失真的定义式(8.4)可以看出，系统的平均失真不仅与失真函数d(ui,vj)有关，而且与信源的统计特性P(ui)和信道的转移概率P(vj|ui)有关。应当注意，在给定信源U，并且定义了U、

17、V之间的失真函数d(ui,vj)之后，系统的平均失真仅由信道转移概率P(vj|ui)决定，即 =P(vj|ui)。如果要求信息传输系统所产生的平均失真 不能够大于某一给定的常数D，则可以使用的信道受到了限制。于是，传输该给定信源信息的信道可以划分为两类:一类信道能够满足D失真许可准则的要求，即满足 D;另一类信道中所产生的平均失真 D。因此，我们将信道P(vj|ui)划分为两个集合：ddddddd第第8章章 限失真信源编码限失真信源编码(8.9)(8.10)显然，如果信道P(vj|ui)PD，则使用该信道传输给定信源输出信息时，传输系统的平均失真将满足D失真许可准则。因此，集合PD中的信道称为

18、D失真许可信道。说明：为了求出信道可变条件下信息传输率R=I(U;V)的最小值，此处引用的信道P(vj|ui)为一种假想的可变信道，称为试验信道。在实际问题的分析中，这些不同的试验信道可以看做不同的信源编码方法。(|);jiDPP vudD(|);DjiPP vudD第第8章章 限失真信源编码限失真信源编码 8.2.2 信息率失真函数信息率失真函数平均互信息的凸性表明，对于给定的信源，信息传输系统的信息传输率：R=I(U;V)=IP(vj|ui)是信道转移概率P(vj|ui)的下凸函数。因此，若改变信道参数，则一定存在一个平均互信息的最小值，使得传输给定信源信息时系统的信息传输率最小。但是，此

19、时讨论的问题是在满足D失真许可要求下寻找重建给定信源信息时所必须有的最小平均信息量。虽然由平均互信息的下凸性知道此时R=I（U；V）的最小值一定存在，但是由于规定了失真限度D，因此传输给定信源信息所能够使用的信道受到了限制，即P(vj|ui)PD。第第8章章 限失真信源编码限失真信源编码 于是，我们可以在D失真许可信道集合PD中选出一组信道转移概率P(vj|ui)，使得信息传输率R=I(U;V)达到最小值。此平均互信息的最小值表示在满足D失真许可要求（D）时传输给定信源信息的信息传输率R的最小值。定义满足D失真许可要求的平均互信息的最小值为信息率失真函数,即(8.11)简称率失真函数，单位是比

20、特/符号或奈特/符号。d(|)()min (;)min(;);DP v uPR DI U VI U VdD第第8章章 限失真信源编码限失真信源编码 信息率失真函数R(D)的定义表明，R(D)为给定信源和定义失真函数的前提下，在失真限度为D（试验信道满足一定约束条件）时平均互信息I(U;V)的最小值。因此信息率失真函数R(D)具有明确的物理含义和实际指导意义。第第8章章 限失真信源编码限失真信源编码 信息率失真函数R(D)与信道容量C具有对偶性。R(D)是在给定信源P(u)和失真限度D时平均互信息I(U;V)的最小值。这个最小值R(D)是在给定信源的情况下，接收端以满足失真限度D的要求而重建信源

21、信息时所必须获得的最小平均信息量。因此，R（D）反映了在满足一定失真限度D的要求下，给定信源输出的信息率可以压缩的程度，即最有效地表达信源输出信息时可以压缩到的最低信息率。显然，R（D）所表示的最低信息率是反映信源特性的参量，与试验信道无关。对于不同的信源，其R（D）不同。第第8章章 限失真信源编码限失真信源编码 信道容量C则是在给定信道P(v|u)时平均互信息I(U;V)的最大值。信道容量C反映了信道传输信息的能力，是在信道中实现可靠传输时该给定信道的最大信息传输率。信道容量C与信源无关，是反映信道特性的参量。对于不同的信道，其信道容量不同。信息率失真函数R(D)与信道容量C这两个概念在实际

22、应用中有明显区别。信道容量C的研究目的是掌握给定信道传输信息的能力，即该信道能够可靠传送的最大信息量。在充分利用给定信道传输能力的条件下，使信息传输系统的信息传输率最大而错误概率任意小，这就是一般的信道编码问题。第第8章章 限失真信源编码限失真信源编码 信息率失真函数R（D）的研究目的是掌握给定信源输出信息的特性。在满足D失真许可要求的条件下，人们希望使用尽可能少的码符号表达（传送）给定信源输出的信息。由于R(D)恰为失真限度D之内传输给定信源输出信息时所必需的最小信息传输率，因此信息率失真函数R(D)反映了信息传输系统的有效性研究，即信源编码和数据压缩应用中所面临的一个基本问题。第第8章章

23、限失真信源编码限失真信源编码 8.2.3 R(D)的基本函数关系的基本函数关系由上面的讨论可以看出，传输给定信源输出的符号时，如果信息传输系统中允许产生的平均失真限度为D，则由D失真许可信道集合PD中找出的平均互信息的最小值便为信息率失真函数R（D）。显然，如果要求的平均失真限度D不同，则D失真许可信道集合PD不同，所得到的最小信息传输率也不同。因此，信息率失真函数R(D)是失真限度D的函数。设已给定离散无记忆信源:第第8章章 限失真信源编码限失真信源编码 对于试验信道:已定义U、V之间的rs个失真函数d(ui,vj)0。失真函数矩阵为(8.12)(8.13)1212.,()()().()rr

24、uuuU P uP uP uP u(|)1,2,.,;1,2,.,jiP vuir js第第8章章 限失真信源编码限失真信源编码(8.14)下面首先讨论信息率失真函数：所具有的基本函数关系,即考察R(D)的值域和使得R(D)有定义的失真限度D的取值范围。111212122212(,)(,)(,)(,)(,)(,)(,)(,)(,)Dssrrrsd u vd u vd u vd u vd u vd u vd u vd u vd u v(|)()min (;)min(;);DP v uPR DI U VI U VdD第第8章章 限失真信源编码限失真信源编码 1 R(D)的值域的值域信息率失真函数R

25、(D)的定义式(8.11)表明，R(D)本质上反映的是信息传输系统中信源U与信道输出V之间的平均互信息I(U;V)。依据平均互信息I(U;V)的基本性质，可以确定信息率失真函数R(D)取值大小满足的关系。由于平均互信息I(U;V)具有非负性,即I(U;V)0第第8章章 限失真信源编码限失真信源编码 因此信息率失真函数的取值不会小于0，即R（D）0由平均互信息I(U;V)的极值性，即I(U;V)H(U)可以看出，信息率失真函数R(D)的取值有界:R(D)H(U)即信息率失真函数R(D)的数值不会超过信源U的输出的平均信息量H(U)。于是，信息率失真函数R(D)的取值范围为0R(D)H(U)第第8

26、章章 限失真信源编码限失真信源编码 2 R(D)的定义域的下界的定义域的下界Dmin对于给定的信源（P(u)固定）和定义的失真函数d(ui,vj)，使得信息率失真函数R(D)有定义的失真限度D中的最小值Dmin便为R(D)的定义域的下界。由前面关于失真函数的讨论可知，失真函数大于或等于零，即d(ui,vj)0 i=1,2,r;j=1,2,s作为失真函数d(ui,vj)的统计平均值，平均失真也是一个非负的实数，即0。因此，使得信息率失真函数R(D)有意义的失真限度D的取值不可能小于零。由此可知，信息率失真函数R(D)的定义域的下界满足Dmin0。dd第第8章章 限失真信源编码限失真信源编码 在实

27、际应用中，由于不同信源具有不同的统计关系，在不同的应用场合用vj表示ui时所产生的差异、损失与风险的大小也各不相同，因此，信息率失真函数R（D）的定义域需要根据具体问题和应用要求加以确定。对于以给定的信源U（见式(8.12)）和失真函数矩阵D（见式(8.14)），可以求出U与V之间的平均失真：(8.15)11()(|)(,)rsijiijijdP u P vu d u v第第8章章 限失真信源编码限失真信源编码 由于信源概率分布P(ui)和失真函数d(ui,vj)已确定，因此此时的平均失真是信道参数P(vj|ui)的函数。于是，改变试验信道参数时所取得的平均失真的最小值即为R(D)定义域的下界

28、,即(8.16)dmin(|)(|)11minmin()(|)(,)DDrsijiijP v uPP v uPijDdP u P vu d u v第第8章章 限失真信源编码限失真信源编码 对于信源输出符号集合中的某一符号ui（i=1,2,r，且为固定的参变量），不同试验信道P(vj|ui)的输出vj（j=1,2,s）不同，则该试验信道传输某一信源符号ui所产生的平均失真为(8.17)显然，使用的试验信道P(vj|ui)不同，则平均失真的大小不同，并且一定存在一种试验信道P(vj|ui)，使得式(8.17)所表示的平均失真达到其可能的最小值。1(|)(,)sjiijjP vu d u v第第8章

29、章 限失真信源编码限失真信源编码 进一步分析可知，对于给定的信源和已定义的失真函数，如果可以找到一种试验信道，对于ui（i=1,2,r）都能够使式(8.16)达到其可能的最小值，则U、V之间的平均失真一定达到其最小值，且为信息率失真函数R(D)的定义域的下界Dmin。于是，式(8.16)可以表示为(8.18)min(|)11()min(|)(,)DrSijiijP v uPijDP uP vu d u v第第8章章 限失真信源编码限失真信源编码 由此可以看出，我们可以通过选择一种试验信道，使每一种信源符号所产生的平均失真最小（即式(8.18)中的内和式达到其最小值），从而得到R(D)的定义域的

30、下界Dmin。使用不同的vj(j=1,2,s)表示固定的ui时，由于失真函数矩阵D中第i行的元素d(ui,vj)互不相同，因此在失真函数矩阵D的第i行元素中一定可以找出一个最小值（也可能有若干个相同的最小值）。不妨设失真函数矩阵D的第i行中第J列失真函数的取值（此处记做Ji）最小，便有：min(,)(,)1,2,.,iijiJjd u vd u vir第第8章章 限失真信源编码限失真信源编码 可以选择一种试验信道，使其满足：(8.19)那么，第i行的平均失真达到其最小值：(|)1 1,2,.,(|)0jiijiiP vujJjsP vujJ1(|)(,)(,)min(,)1,2,.,isjii

31、jiJijjjP vu d u vd u vd u vir第第8章章 限失真信源编码限失真信源编码 由于失真函数矩阵D中每一行的平均失真都是最小的，因此系统总体的平均失真一定为其可能取值的最小值。于是，对于给定的信源和定义的失真函数，信息率失真函数R（D）的定义域的下界为(8.20)若失真函数矩阵D的每一行中至少有一个失真函数为零，则有Dmin=0，否则，Dmin0。若给定失真限度为D=Dmin=0min1()min(,)riijiDP ud u v第第8章章 限失真信源编码限失真信源编码 则表示该信息传输系统必须无失真传输给定信源输出的符号。于是，信息传输率至少应等于信源的信息熵，即R(0)

32、=H(U)如果失真函数矩阵D中某些列中包含了至少两个取值为零的元素，则表明给定信源符号集中的某些符号可以压缩、合并。此时，一般满足:R(0)H(U)若失真函数矩阵D中至少有一行全部为非零元素，则有Dmin0。此时R(Dmin)H(U)第第8章章 限失真信源编码限失真信源编码【例例8.2】设信源(0p1)，Vv1,v2,v3，定义失真函数矩阵为 由式(8.20)可以求出信息率失真函数R(D)的定义域的下界为12,1uuU Ppp10121103 D2min1()min(,)11min0,1,(1)min1,0,023iijjiDP ud u vpp第第8章章 限失真信源编码限失真信源编码 由前面

33、的分析和式(8.19)所示的关系可以看出，达到此最小允许失真限度的试验信道为 由于此试验信道是一个无噪无损信道，在信道的输出端观测到输出V之后，便可以消除关于信源U的不确定性，因此信道疑义度H(U|V)=0,则有：I(U;V)=H(U)H(U|V)=H(U)于是100(|)010jiP vumin()(0)min(;)()ijDPPR DRI U VH U第第8章章 限失真信源编码限失真信源编码 【例例8.3】设信源，Vv1,v2，定义失真函数矩阵为由式(8.20)计算得：123,111333uuuU P01112210D第第8章章 限失真信源编码限失真信源编码 所以，对于此信源U和定义的失真

34、函数，R(D)的定义域的下界为。根据式(8.19)，达到此最小允许失真限度的试验信道必须满足：3min111 111()min(,)0033 236iijjiDP ud u vmin16D11122223(|)1(|)(|)1(|)1P vuP vuP vuP vu第第8章章 限失真信源编码限失真信源编码 由于满足约束条件P(v1|u2)+P(v2|u2)=1的P(v1|u2)和P(v2|u2)可以有无穷多种组合，因此可以使得系统平均失真的试验信道有无数多个。这些试验信道的信道矩阵中每一列都有不止一个非零元素，所以H(U|V)0,于是min16dDmin1()()min(;)()6jiDpPR

35、 DRI U VH U第第8章章 限失真信源编码限失真信源编码 若将失真函数矩阵改成：则同理，达到此最小允许失真限度的试验信道必须满足：010010d3min1()min(,)0iijjiDP ud u v11122223(|)1(|)(|)1(|)1P vuP vuP vuP vu第第8章章 限失真信源编码限失真信源编码 满足上述条件的试验信道的共同特点就是信道矩阵中每列有不止一个非零元素，所以，H(U|V)0，因此，。从失真函数矩阵d也可以看出，信源符号u1传递到符号v1无失真，而信源符号u2传递到v1也无失真，因此，完全可以将信源的符号u1和u2合并成一个符号，使信源符号集由三个符号压缩

36、成两个符号，并不引起任何失真。显然，压缩后信息传输率必然减小，所以得R(0)0；当 时，R=I(U;V)0。于是，作为在D失真许可条件下传输给定信源信息时的平均互信息的最小值(即使得I(U;V)由非零变为零所对应的平均失真取值)，对于考察信息率失真函数R(D)的基本函数关系有重要意义。minddminddmind第第8章章 限失真信源编码限失真信源编码 因此，设给定信源的信息率失真函数为R(D)，对于失真限度D0，一定存在一个自变量的取值D=Dmax,使得DDmax时，有0R(D)H(U)当DDmax时，有R（D）0则Dmax表示R(D)定义域的上界值。第第8章章 限失真信源编码限失真信源编码

37、 下面我们讨论和给出R(D)定义域的上界Dmax的确定方法。由前面关于系统平均失真与系统信息传输率R=I(U;V)的讨论可以看出，当时，R=I(U;V)0。由于与此对应的试验信道的输入U与输出V相互独立，因此为了得到，构造试验信道转移概率：P(vj|ui)=P(vj)i=1,2,r;j=1,2,s(8.21)ddmindmind第第8章章 限失真信源编码限失真信源编码 于是可以求出信道输入U与输出V之间的平均失真：显然，在满足U与V相互独立（见式(8.21)）的条件下，不同的试验信道中产生的平均失真不同，而恰为此类信道中平均失真的下界(最小值),于是dmind11(,)()(|)(,)rsij

38、ijiijijdE d u vP u P vu d u v11()()(,)rsijijijP u P v d u v第第8章章 限失真信源编码限失真信源编码 其中，内和式表示了U、V统计独立时，失真函数矩阵D的每一列元素d(ui,vj)对P(ui)的均值。为使上式总和最小，我们可以按下述方法来选择试验信道。min1111min()()(,)min()()(,)rsijijijsrjiijjidP u P v d u vP vP u d u v第第8章章 限失真信源编码限失真信源编码 首先计算失真函数矩阵D中每一列元素d(ui,vj)的统计平均值:而后在各列均值中找出最小者。此处不妨设第k列最

39、小，即j1()(,v)1,2,.,riiiP u d ujs11min()(,)()(,)rriijiikjiiP u d u vP u d u v第第8章章 限失真信源编码限失真信源编码 相应地，取试验信道的转移概率为于是，得到了U、V统计独立条件下的最小平均失真，即1(|)()1,2,.,;1,2,.,0jijjkP vuP vir jsjkmin11111min()()(,)()min()(,)min()(,)srjiijjisrjiijjjiriijjidP vP u d u vP vP u d u vP u d u v第第8章章 限失真信源编码限失真信源编码 显然，由这样的U、V相互

40、独立的试验信道所得到的平均失真的最小值即为信息率失真函数R(D)定义域的上界值Dmax，即(8.22)并且当DDmax时，有R（D）0max,11min()()(,)min()()(,)U VsrjiijjiDP u P v d u vP vP u d u v第第8章章 限失真信源编码限失真信源编码 【例例8.4】设输入随机变量的概率空间为，输出符号集，定义失真函数矩阵为101,111333U P1 1,2 2 V131231D第第8章章 限失真信源编码限失真信源编码 则由式(8.22)可知：3max1min()(,)111111min113,321333333565min,=333 iijj

41、iDP u d u v第第8章章 限失真信源编码限失真信源编码 可以看出，达到最大失真限度Dmax所对应的试验信道矩阵为并且当时，有R（D）011(|)()02jijjP vuP vj53D 第第8章章 限失真信源编码限失真信源编码 8.2.4 信息率失真函数的性质信息率失真函数的性质性质性质1 在定义域Dmin,Dmax内，R(D)是D的下凸函数，即已知D1，D2Dmin,Dmax,对于任意给定的01，有：R(D1+(1)D2)R(D1)+(1)R(D2)(8.23)第第8章章 限失真信源编码限失真信源编码 证明证明：在R（D）的定义域内任取两点，并有：其中，P1(vj|ui)是恰使I(U;

42、V1)达到最小值的试验信道。同理有：其中，P2(vj|ui)是恰使I(U;V2)达到最小值的试验信道。11111()min(;)(;,(|)jiDjipPR DI U VI U V P vu22222()min (;)(;,(|)jiDjipPR DI U VI U V P vu第第8章章 限失真信源编码限失真信源编码 令01，并令D=D1+(1)D2且P(vj|ui)=P1(vj|ui)+(1)P2(vj|ui)首先证明P(vj|ui)是D失真许可信道集合PD内的信道,即使用信道P(vj|ui)PD传输信源信息时，系统中产生的平均失真D。d第第8章章 限失真信源编码限失真信源编码 因为121

43、2()()(|)(,)()(|)(1)(|)(,)()(|)(,)(1)()(|)(,)jiijiijijijijiijijijiijijijiijijd P v uP u P vu d u vP uP vuP vud u vP u P vu d u vP u P vu d u v第第8章章 限失真信源编码限失真信源编码 可记成因为所以12(1)ddd11(|)jiDP vuP22(|)jiDP vuP11dD22dD第第8章章 限失真信源编码限失真信源编码 于是因此P(vj|ui)PD即P(vj|ui)是D失真许可信道集合PD内的一个信道。因此有：R(D)=R(D1+(1)D2)I(U;V,

44、P(vj|ui)(8.24)1212(|)(1)(1)jid P vuddDDD第第8章章 限失真信源编码限失真信源编码 另外，由于平均互信息I(U;V,P(vj|ui)是信道转移概率的下凸函数，因此有：由式(8.24)和式(8.25)可得：R（D1+(1)D2）R(D1)+(1)R(D2)因此信息率失真函数R(D)在定义域内是下凸的。112212(;,()(;,(|)(1)(;,(|)()(1-)()jijijiI U V P v uI U V P vuI U V P vuR DR D(8.25)第第8章章 限失真信源编码限失真信源编码 性质性质2 R(D)在定义域Dmin,Dmax内是单调

45、递减函数。由上面的讨论可以看出，当传输给定信源输出的信息时，允许的失真限度D愈大，则传输该信源必须有的最小信息传输率将愈小。因此，依信息率失真函数的定义可知，在定义域Dmin,Dmax内，R(D)是单调递减函数。R(D)在定义域内的单调递减性可以由R(D)的下凸性加以证明。第第8章章 限失真信源编码限失真信源编码 证明：证明：设D1为定义域内的任意一点。在(D1,Dmax)中任取一点D，使D=(1)D1+Dmax其中,是任意小的正数。由于R(D)在定义域内是下凸的，因此有：R(D)=R(1)D1+Dmax)(1)R(D1)+R(Dmax)第第8章章 限失真信源编码限失真信源编码 已知R(Dma

46、x)=0，则R(D)(1)R(D1)由于011，于是R(D)D1，则一定满足R(D)0则系统的信息传输率改变为111(;)(|)(|)()(|)log()(|)jirsjiijirijijiiI U VI P vuP vuP uP vuP uP vu第第8章章 限失真信源编码限失真信源编码 令0，则P(vj)0 因此，平均互信息I(U;V)是信道转移概率P(vj|ui)的连续函数。对于给定信源U，如果失真限度为D，则D失真许可信道集合为PD=P(vj|ui);Dd第第8章章 限失真信源编码限失真信源编码 1(|)(|)min (;)()DjiP v uPI P vuI U VR D由信息率失真

47、函数R(D)的定义可知，一定存在一组信道参数P1(vj|ui)PD，使得：若将失真限度调整为D=D+0则满足D失真许可的信道集合为PD=P(vj|ui);D+d第第8章章 限失真信源编码限失真信源编码 同理,一定可以找到一组信道参数:P2(vj|ui)PD使得:显然，当0时，PDPD，且有：P2(vj|ui)=P1(vj|ui)02(|)(|)min (;)()DjiP v uPI P vuI U VR D第第8章章 限失真信源编码限失真信源编码 由于平均互信息I(U;V)是信道转移概率P(vj|ui)的连续函数，因此有：此式等价于：110lim(|)(|)jijiI P vuI P vu00

48、(|)(|)lim()limmin (;)min (;)DDP v uPP v uPR DI U VI U V第第8章章 限失真信源编码限失真信源编码 于是 因此，信息率失真函数R(D)在其定义域Dmin,Dmax内是失真限度D的连续函数。根据R(D)的上述性质，可以做出R(D)的大致函数曲线。00(|)(|)lim()limmin (;)min (;)()DDP v uPP v uPR DI U VI U VR D第第8章章 限失真信源编码限失真信源编码 设给定信源U，其信息熵为H（U），并且已定义信道输入U与输出V之间的失真函数矩阵D。如果失真函数矩阵D的每一行元素中的最小值为0，且只有一

49、个元素为0，则由前面关于信息率失真函数R(D)的基本函数关系的讨论可知，系统中允许的失真限度D的下限值为Dmin=0，且有：R(Dmin)=R(0)=H(U)第第8章章 限失真信源编码限失真信源编码 并且一定存在一个失真限度Dmax，当DDmax时，R(Dmax)0。于是，在失真限度D和信息率失真函数R(D)分别为横、纵坐标构成的坐标系中，可以标出信息失真函数的定义域0,Dmax与函数中的两个点：(0,H(U)和(Dmax,0)。由于信息失真函数R(D)在其定义域0,Dmax内是下凸、单调递减的连续函数，因此可以做出R(D)在其定义域内的函数曲线，并且当DDmax时，有R(Dmax）0，如图8

50、-3(a)所示。第第8章章 限失真信源编码限失真信源编码 如果对于给定的失真函数矩阵D，系统中允许的失真限度D0，则可计算得到信息失真函数R(D)的定义域的下界Dmin和上界Dmax，求出相应的信息率失真函数取值R(Dmin)和R(Dmax)0，依据信息失真函数R(D)在其定义域Dmin,Dmax内的下凸性、单调递减性和连续性，做出R(D)的函数曲线，如图8-3(b)所示。（注意：当DDmax时，R(Dmax)0。）第第8章章 限失真信源编码限失真信源编码 图8-3 R(D)函数的曲线 第第8章章 限失真信源编码限失真信源编码 8.3 信息率失真函数的计算信息率失真函数的计算8.3.1 信息率