1、2023/2/11/49l理论上理论上“消息完全无失真传送消息完全无失真传送”的可实现性的可实现性l信道编码定理信道编码定理：无论何种信道，只要信息率：无论何种信道，只要信息率R=(Klog2m)/L小于信道容量小于信道容量C，总能找到一种编码，使在信道上能以任，总能找到一种编码，使在信道上能以任意小的错误概率和任意接近于意小的错误概率和任意接近于C的传输率来传送信息。反的传输率来传送信息。反之，若之，若RC，则传输总要失真。，则传输总要失真。l实际上实际上“消息完全无失真传送消息完全无失真传送”的不可实现性的不可实现性l实际的信源常常是连续的，信息率无限大，要无失真传送实际的信源常常是连续的
2、，信息率无限大，要无失真传送要求信道容量要求信道容量C为无穷大；为无穷大；l实际信道带宽是有限的，所以信道容量受限制。要想无失实际信道带宽是有限的，所以信道容量受限制。要想无失真传输，所需的信息率大大超过信道容量真传输，所需的信息率大大超过信道容量RC。2023/2/12/49l有些失真没有必要完全消除（有些失真没有必要完全消除（限失真信源编码）限失真信源编码）l实际生活中，人们一般并不要求获得完全无失真的消息，实际生活中，人们一般并不要求获得完全无失真的消息，通常只要求近似地再现原始消息，即允许一定的失真存通常只要求近似地再现原始消息，即允许一定的失真存在。在。l打电话：即使语音信号有一些失
3、真，接电话的人也能听打电话：即使语音信号有一些失真，接电话的人也能听懂。懂。l放电影：理论上需要无穷多幅静态画面，由于人眼的放电影：理论上需要无穷多幅静态画面，由于人眼的“视觉暂留性视觉暂留性”，实际上只要每秒放映，实际上只要每秒放映24幅静态画面。幅静态画面。l信息率失真理论信息率失真理论-信息率失真函数信息率失真函数l香农定义了信息率失真函数香农定义了信息率失真函数R(D)。l定理指出定理指出：在允许一定失真度：在允许一定失真度D的情况下，信源输出的的情况下，信源输出的信息率可压缩到信息率可压缩到R(D)。2023/2/13/49l在允许一定失真程度的条件下，怎样用尽可能少的信道符在允许一
4、定失真程度的条件下，怎样用尽可能少的信道符号来表达信源的信息，也就是信源熵所能压缩的极限或者号来表达信源的信息，也就是信源熵所能压缩的极限或者说编码后信源输出的信息率压缩的极限值，这就是限失真说编码后信源输出的信息率压缩的极限值，这就是限失真信源编码要讨论的问题。信源编码要讨论的问题。l限失真信源编码也称保真度准则下的信源编码、熵压缩编限失真信源编码也称保真度准则下的信源编码、熵压缩编码或者称信息率失真理论，它是量化、数模转换、频带压码或者称信息率失真理论，它是量化、数模转换、频带压缩和数据压缩的理论基础。缩和数据压缩的理论基础。l如果无失真的冗余度压缩编码主要是针对离散信源的，那如果无失真的
5、冗余度压缩编码主要是针对离散信源的，那么，限失真的熵压缩编码主要是针对连续信源。么，限失真的熵压缩编码主要是针对连续信源。2023/2/14/49l信息率失真函数极小值问题信息率失真函数极小值问题lI(X;Y)是是P(X)和和P(Y/X)的二元函数；的二元函数；l在讨论信道容量时：固定在讨论信道容量时：固定P(Y/X)，I(X;Y)变成变成P(X)的函数。的函数。在离散情况下，因为在离散情况下，因为I(X;Y)对对p(xi)是上凸函数，所以变更是上凸函数，所以变更p(xi)所求极值一定是所求极值一定是I(X;Y)的极大值；的极大值；l在讨论率失真时：固定在讨论率失真时：固定p(xi)，变更，变
6、更p(yj/xi)来求平均互信息来求平均互信息的极小值。的极小值。由于由于I(X;Y)是是p(yj/xi)的下凸函数，所求的极值的下凸函数，所求的极值一定是极小值一定是极小值。但若。但若X和和Y相互统计独立相互统计独立(p(yj/xi)=p(yj)，这个极小值就是这个极小值就是0，因为，因为I(X;Y)是非负的，是非负的，0必为极小值，必为极小值，这样求极小值就没意义了。这样求极小值就没意义了。l引入一个失真函数，计算在失真度一定的情况下信息率的引入一个失真函数，计算在失真度一定的情况下信息率的极小值就变成有意义了。极小值就变成有意义了。2023/2/15/49信息率与失真的关系信息率与失真的
7、关系l信道中固有的噪声和不可避免的干扰，使信源的消息通信道中固有的噪声和不可避免的干扰，使信源的消息通过信道传输后造成误差和失真过信道传输后造成误差和失真l误差或失真越大，接收者收到消息后对信源存在的不确误差或失真越大，接收者收到消息后对信源存在的不确定性就越大，获得的信息量就越小，信道传输消息所需定性就越大，获得的信息量就越小，信道传输消息所需的信息率也越小。的信息率也越小。2023/2/16/49l失真度失真度l设离散无记忆信源为设离散无记忆信源为)(,),(),(,)(2121mmjypypypyyyypYY到接收端信源符号通过信道传送)(,),(),(,)(2121nnixpxpxpx
8、xxxpX)/()/()/()/()/()/()/()/()/()/(212222111211nmnnmmxypxypxypxypxypxypxypxypxypXYp信道的传递概率矩阵l对每一对对每一对(xi,yj)，指定一个非负函数，指定一个非负函数d(xi,yj)0 i=1,2,n j=1,2,m称称d(xi,yj)为为单个符号的失真度单个符号的失真度/失真函数。它表示信源发出一个符号失真函数。它表示信源发出一个符号xi，在接收端再现在接收端再现yj所引起的误差或失真。所引起的误差或失真。2023/2/17/49l 均方失真：均方失真：l 绝对失真：绝对失真：l 相对失真：相对失真：l 误
9、码失真：误码失真：2(,)()(,)|(,)|/|ijiiijiiijiiid x yx yd x yx yd x yx yx11(,)(,)Lijikjkkd x yd x yL失真函数的表达失真函数的表达2023/2/18/49常用的失真函数常用的失真函数 失真函数是根据人们的实际需要和失真引起的损失、风险大小等人为失真函数是根据人们的实际需要和失真引起的损失、风险大小等人为规定的。常用的失真函数有规定的。常用的失真函数有 (1)绝对失真：汉明失真绝对失真：汉明失真l在离散对称信道中，定义单个符号失真度为汉明失真。在离散对称信道中，定义单个符号失真度为汉明失真。l汉明失真矩阵汉明失真矩阵D
10、通常为方阵，且对角线上的元素为通常为方阵，且对角线上的元素为0。即。即 (2)均方失真：平方误差失真函数均方失真：平方误差失真函数l如果信源符号代表信源输出信号的幅度值，则上式意味着较大的幅如果信源符号代表信源输出信号的幅度值，则上式意味着较大的幅度差值要比较小的幅度差值引起的失真更为严重，严重程度用平方度差值要比较小的幅度差值引起的失真更为严重，严重程度用平方表示。表示。0(,)1ijijijxyd x yxy01 1110111 1 10D 2(,)(),ijijd x yxyij 2023/2/19/49l失真矩阵失真矩阵l失真度还可表示成矩阵的形式失真度还可表示成矩阵的形式l称称D为失
11、真矩阵。它是为失真矩阵。它是nm阶矩阵。阶矩阵。d(x,y)0),(),(),(),(),(),(),(),(),(212221212111mnnnmmyxdyxdyxdyxdyxdyxdyxdyxdyxdD2023/2/110/49l平均失真度平均失真度ld(xi,yj)只能表示两个特定的具体符号只能表示两个特定的具体符号xi和和yj之间的失真。之间的失真。l平均失真度平均失真度：平均失真度为失真度的数学期望：平均失真度为失真度的数学期望nimjjiijijijiyxdxypxpDyxdEDXYPYXyxd11),()/()(),()(),(由数学期望的定义中的统计平均值的联合概率空间和在即
12、，2023/2/111/49l平均失真度意义平均失真度意义l 是在平均意义上，从总体上对整个系统失真情况的描述。它是信源是在平均意义上，从总体上对整个系统失真情况的描述。它是信源统计特性统计特性p(xi)、信道统计特性、信道统计特性p(yj/xi)和失真度和失真度d(xi,yj)的函数的函数。当。当p(xi)，p(yj/xi)和和d(xi,yj)给定后，平均失真度就不是一个随机变量了，而是一给定后，平均失真度就不是一个随机变量了，而是一个确定的量。个确定的量。l如果信源和失真度一定，如果信源和失真度一定，就只是信道统计特性的函数。信道传递就只是信道统计特性的函数。信道传递概率不同，平均失真度随
13、之改变。概率不同，平均失真度随之改变。l保真度准则保真度准则l人们所允许的失真指的都是平均意义上的失真。人们所允许的失真指的都是平均意义上的失真。l保真度准则保真度准则：规定平均失真度：规定平均失真度 不能超过某一限定的值不能超过某一限定的值D，即即 ，则，则D就是允许失真的上界。该式称为保真度准则。就是允许失真的上界。该式称为保真度准则。l将保真度准则作为信道传递概率的约束条件，再求信道的信息率将保真度准则作为信道传递概率的约束条件，再求信道的信息率R=I(X;Y)的最小值就有实际意义。的最小值就有实际意义。DDDDD2023/2/112/49试验信道试验信道l单符号信源和单符号信道的试验信
14、道单符号信源和单符号信道的试验信道l当固定信源（当固定信源（P(X)已知），单个符号失真度也给定时，选择信道已知），单个符号失真度也给定时，选择信道使使 。凡满足要求的信道称为。凡满足要求的信道称为D失真许可的试验信道失真许可的试验信道，l所有试验信道构成的集合用所有试验信道构成的集合用PD来表示，即来表示，即DDmjniDDxypPijD,2,1,2,1:)/(2023/2/113/49信息率失真函数信息率失真函数l在信源和失真度给定以后，在信源和失真度给定以后，PD是满足保真度准则是满足保真度准则 的试验信的试验信道集合，平均互信息道集合，平均互信息I(X;Y)是信道传递概率是信道传递概率
15、p(yj/xi)的下凸函数，所以的下凸函数，所以在在PD中一定可以找到某个试验信道，使中一定可以找到某个试验信道，使I(X;Y)达到最小，即达到最小，即 这个最小值这个最小值R(D)称为信息率失真函数称为信息率失真函数，简称，简称率失真函数率失真函数。l在信源给定以后，总希望在允许一定失真的情况下，传送信源所必在信源给定以后，总希望在允许一定失真的情况下，传送信源所必须的信息率越小越好。须的信息率越小越好。从接收端来看，就是在满足保真度准则从接收端来看，就是在满足保真度准则 的条件下，寻找再现信源消息必须的最低平均信息量，即平均互信的条件下，寻找再现信源消息必须的最低平均信息量，即平均互信息的
16、最小值息的最小值。);(min)()/(YXIDRDijPxypDDDD 2023/2/114/49信息率失真函数与信道容量的对偶问题信息率失真函数与信道容量的对偶问题 平均互信息平均互信息I(X;Y)既是信源概率分布既是信源概率分布p(xi)的上凸函数，的上凸函数，又是信道传递概率又是信道传递概率p(yj/xi)的下凸函数。的下凸函数。l率失真函数率失真函数R(D)是在允许失真是在允许失真D和信源概率分布和信源概率分布p(xi)已给已给的条件下，求平均互信息的极小值问题。的条件下，求平均互信息的极小值问题。l而信道容量而信道容量C是在信道特性是在信道特性p(yj/xi)已知的条件下求平均互已
17、知的条件下求平均互信息的极大值问题。信息的极大值问题。2023/2/115/49研究率失真函数和信道容量的意义研究率失真函数和信道容量的意义l研究信息率失真函数的意义：是为了解决在已知信源和允研究信息率失真函数的意义：是为了解决在已知信源和允许失真度许失真度D的条件下，使信源必须传送给信宿的信息率最的条件下，使信源必须传送给信宿的信息率最小。即用尽可能少的码符号尽快地传送尽可能多的信源消小。即用尽可能少的码符号尽快地传送尽可能多的信源消息，以息，以提高通信的有效性提高通信的有效性。这是。这是信源编码信源编码问题。问题。l研究信道容量的意义：是为了解决在已知信道中传送最大研究信道容量的意义：是为
18、了解决在已知信道中传送最大信息率问题。目的是充分利用已给信道，使传输的信息量信息率问题。目的是充分利用已给信道，使传输的信息量最大而发生错误的概率任意小，以最大而发生错误的概率任意小，以提高通信的可靠性提高通信的可靠性。这。这就是就是信道编码信道编码问题。问题。2023/2/116/49信息率失真函数的性质信息率失真函数的性质l率失真函数的定义域率失真函数的定义域l允许平均失真度允许平均失真度：率失真函数中的自变量率失真函数中的自变量D，也就是，也就是人们规定的平均失真度人们规定的平均失真度 的上限值。的上限值。l率失真函数的定义域率失真函数的定义域问题就是在信源和失真函数已知问题就是在信源和
19、失真函数已知的情况下，讨论的情况下，讨论允许平均失真度允许平均失真度D的最小和最大值问的最小和最大值问题题。lD的选取必须根据固定信源的选取必须根据固定信源X的统计特性的统计特性P(X)和选定的和选定的失真函数失真函数d(xi,yj)，在平均失真度，在平均失真度 的可能取值范围的可能取值范围内。内。DD2023/2/117/49l信源最小平均失真度信源最小平均失真度Dminl 是非负函数是非负函数d(xi,yj)的数学期望，也是一个非负函的数学期望，也是一个非负函数，显然其下限为数，显然其下限为0。因此。因此允许平均失真度允许平均失真度D的下限也的下限也必然是必然是0，这就是不允许有任何失真的
20、情况。，这就是不允许有任何失真的情况。l允许平均失真度允许平均失真度D能否达到其下限值能否达到其下限值0，与单个符号的，与单个符号的失真函数有关。失真函数有关。l信源最小平均失真度信源最小平均失真度Dmin：对于每一个：对于每一个xi，找出一个，找出一个yj与之对应，使与之对应，使d(xi,yj)最小，不同的最小，不同的xi对应的最小对应的最小d(xi,yj)也不同。这相当于在失真矩阵的每一行找出一个最小也不同。这相当于在失真矩阵的每一行找出一个最小的的d(xi,yj)，各行的最小，各行的最小d(xi,yj)值都不同。对所有这些值都不同。对所有这些不同的最小值求数学期望，就是信源的最小平均失真
21、不同的最小值求数学期望，就是信源的最小平均失真度。度。DnijijiyxdxpD1min),(min)(2023/2/118/49l信源最大平均失真度信源最大平均失真度Dmaxl信源最大平均失真度信源最大平均失真度Dmax：所需的信息率越小，容忍：所需的信息率越小，容忍的失真就越大。当的失真就越大。当R(D)等于等于0时，对应的平均失真最大，时，对应的平均失真最大，也就是也就是函数函数R(D)定义域的上界值定义域的上界值Dmax。l信息率失真函数是平均互信息的极小值：信息率失真函数是平均互信息的极小值：l当当R(D)=0时，即平均互信息的极小值等于时，即平均互信息的极小值等于0；l当当DDma
22、x时，从数学意义上讲，因为时，从数学意义上讲，因为R(D)是非负函数，所以是非负函数，所以它仍只能等于它仍只能等于0。这相当于输入。这相当于输入X和输出和输出Y统计独立。意味着统计独立。意味着在接收端收不到信源发送的任何信息在接收端收不到信源发送的任何信息，与，与信源不发送任何信信源不发送任何信息息等效。或者说等效。或者说传送信源符号的信息率可以压缩至传送信源符号的信息率可以压缩至0。2023/2/119/49结结 论：论：lR(D)的定义域为的定义域为 (Dmin,Dmax)；l一般情况下一般情况下Dmin=0，R(Dmin)=H(X)；l当当DDmax时，时，R(D)=0；l当当DminD
23、Dmax时，时，0R(D)H(X)。l率失真函数对允许平均失真度的下凸性：率失真函数对允许平均失真度的下凸性：对任一对任一01和任意平均失真度和任意平均失真度D和和DDmax，有，有RD+(1 )DR(D)+(1)R(D)l由于函数由于函数R(D)具有凸状性，保证了它在定具有凸状性，保证了它在定义域内是连续的。义域内是连续的。l在在DminDDmax时：在时：在D=Dmax处，除某些特处，除某些特例外，例外，S将从某一个负将从某一个负值跳到值跳到0，S在此点不在此点不连续。在连续。在D的定义域的定义域0,Dmax内，除某些特例内，除某些特例外，外，S将是将是D的连续函的连续函数。数。2023/
24、2/133/49(1)二元离散信源的率失真函数二元离散信源的率失真函数 设二元信源设二元信源 计算率失真函数计算率失真函数R(D)二元离散信源的信息率失真函数二元离散信源的信息率失真函数 1,01,0000211211)(212121yyYxxXDppppxxxpXi输出符号集输入符号集失真矩阵为，所以，其中2023/2/134/49 先求出先求出DmaxpDDDDDpppppDDDDDDypDyxdxpDjjjjjjmjjypjiniijj2max2121max1)(max1min21)1(001min)(min),()(，故有已知2023/2/135/49第一步第一步：求：求i，由式由式(
25、4.2.12)有有)1)(1(1)1(11)1(1)1(1)()(1)()(212121),(22),(11),(22),(1122211211SSSSyxSdyxSdyxSdyxSdepepppeeppexpexpexpexp)12.2.4(),2,1,0)(,1)(1),(mjypexpjniyxSdiiji2023/2/136/49第二步第二步：求：求p(yj)，由式由式(4.2.11)有有SSSSSSSSyxSdyxSdyxSdyxSdmjyxSdjiepepypeeppypepypeypepeypypeypeypeypeypeypji1)1()(1)1()(1)1()()(1)()(
26、1)()(1)()()11.2.4()(12121212),(2),(11),(2),(11),(221221112023/2/137/49第三步第三步：求：求p(yj/xi)，由式由式(4.2.10)有有)1)(1()1()/()1()1()/()1)(1()1()/()1()1()/()()/()()/()()/()()/()10.2.4(,2,1;,2,1)()/(222212221211),(2222),(1212),(2121),(1111),(22211211SSSSSSSSSSyxSdyxSdyxSdyxSdyxSdijijeppepxypeeppepxypeepeppxypep
27、eppxypeypxypeypxypeypxypeypxypmjnieypxypji2023/2/138/49第四步第四步：求：求D(S)，将上述结果代入式将上述结果代入式(4.2.14)有有SSSSSSSSyxSdyxSdyxSdyxSdyxSdinimjjijieeeppeppepeeepppeyxdypxpeyxdypxpeyxdypxpeyxdypxpSDeyxdypxpSDji1)1()1()1)(1(1)1()1(),()()(),()()(),()()(),()()()()14.2.4(),()()()(),(12222),(22121),(11212),(11111),(112
28、21112112023/2/139/49第五步第五步：求率失真函数：求率失真函数R(S)，将上述结果代入式将上述结果代入式(4.2.15)有有)1ln()1ln()1(ln1ln)1(ln1)()15.2.4(ln)()()(211SSSSSiniieppppeeSppeeSSRxpSSDSR2023/2/140/49对于这种简单信源，可从对于这种简单信源，可从D(S)解出解出S与与D的显式表达式。的显式表达式。DDDDDDDDDDppxypppDxypppDxypppxypDDpypDDpyppDpDDDS212212221211212111111)/(11)/(11)/(11)/(21)1
29、()(21)(1111ln将将S S代入上面的代入上面的ii，p p(yjyj)和和p p(yjyj/xixi)和和R(S)R(S)得：得：2023/2/141/49ppSpDDDRDDpHRDDHpHppppDDDDDR1ln1,0)(,)()0(,0)()1ln()1(ln1ln)1(ln)(maxmaxmaxmax压缩的信息率。定失真而可能熵，第二项是因容忍一上式右边第一项是信源以及以及2023/2/142/49第六步第六步：通过以上步骤计算出来的：通过以上步骤计算出来的R(D)和和S(D)如图如图4.2.2。2023/2/143/49(2)信息率失真函数曲信息率失真函数曲线图说明线图说
30、明l若若=1，把，把d(xi,yj)当成当成了误码个数，即了误码个数，即X和和Y不一致时，认为误了一不一致时，认为误了一个码元，所以个码元，所以d(xi,yj)的数学期望就是平均误码率。能容忍的失真等。能容忍的失真等效于能容忍的误码率。效于能容忍的误码率。2023/2/144/49lR(D)不仅与不仅与D有关，还有关，还与与p有关。概率分布不有关。概率分布不同，同，R(D)曲线就不一曲线就不一样。当样。当p=0.25时，如果时，如果能容忍的误码率也是能容忍的误码率也是0.25，不用传送信息便，不用传送信息便可达到可达到R=0，这就是，这就是R(Dmax)=0的含义。的含义。2023/2/145
31、/49l当当D相同时，信源越趋相同时，信源越趋于等概率分布，于等概率分布，R(D)就越大。由最大离散熵就越大。由最大离散熵定理，信源越趋于等概定理，信源越趋于等概率分布，其熵越大，即率分布，其熵越大，即不确定性越大，要去除不确定性越大，要去除这不确定性所需的信息这不确定性所需的信息传输率就越大，而传输率就越大，而R(D)正是去除信源不确定性正是去除信源不确定性所必须的信息传输率。所必须的信息传输率。2023/2/146/49l关于关于S(D)lS(D)与与p无直接关系，无直接关系，S(D)曲曲线只有一条，线只有一条，p=0.5和和p=0.25都可以用，但它们的定义域都可以用，但它们的定义域不同
32、；不同；lp=0.25时定义域是时定义域是D=00.25，即到即到A点为止，此时点为止，此时 Smax=1.59。D0.25时，时，S(D)就恒为就恒为0了。所以在了。所以在A点点S(D)是不连续的；是不连续的；l当当p=0.5时，曲线延伸至时，曲线延伸至D=0.5处，此时处，此时Smax=0，故，故S(D)是连续曲线，定义域为是连续曲线，定义域为D=00.5。DDS1ln12023/2/147/49(3)二元等概率离散信源的率失真函数二元等概率离散信源的率失真函数l当上述二元信源呈等概率分布时，上面式子分别退化当上述二元信源呈等概率分布时，上面式子分别退化为为)(21)(212121)()1
33、(22111)1(221121min1211212maxypypDDypDDDDDDDj2023年2月1日星期三电信学院 汪汉新48精品课件精品课件！2023年2月1日星期三电信学院 汪汉新49精品课件精品课件！2023/2/150/49l这个结论很容易推广到这个结论很容易推广到n元等概率信源的情况。元等概率信源的情况。)/(1111)/()/(11)/(11)/(11)/(112212112212212112221212122111xypDxypxypDDxypDDxypDpxypDDDDDDDDDD)1ln()1(1lnln)(DDnDDnDRDHDDDDppppDR2ln1ln)1(ln)1ln()1(ln)(
