信息论与编码技术：第四章 信息率失真函数

1、 第四章 信息率失真函数 4.1 失真测度 4.2 信息率失真函数及其性质 4.3 离散无记忆信源的信息率失真函数 4.4 连续无记忆信源的信息率失真函数 4.5 保真度准则下的信源编码定理 1 在前面几章的讨论中，其基本出发点都是如何保证信息的无失真传输。 但在许多实际应用中，人们并不要求完全无失真地恢复消息，而是只要满足一定的条件，近似地恢复信源发出的消息就可以了。 什么是允许的失真？如何对失真进行描述？ 信源输出信息率被压缩的最大程度是多少？信息率失真理论回答了这些问题，其中香农的限失真编码定理定量地描述了失真，研究 了信息率与失真的关系，讨论了在限失真范围内的信源编码问题，已成为量化、

2、数据转化、频带压缩和数据压缩等现代通信技术的理论基础。 2 本章主要讨论： 在允许一定失真存在的条件下，能够将信源压缩到什么程度，即最少需要多少比特信息才能描述信源，如何能够快速的传输信息。 本章主要介绍信息率失真理论的基本内容，侧重讨论离散无记忆信源。 给出信源的失真度和信息率失真函数的定义与性质； 讨论离散信源和连续信源的信息率失真函数计算； 论述保真度准则下的信源编码定理(限失真信源编码定理 香农第三定理)。 3 引入限失真的必要性(1) 信宿的灵敏度和分辨率都是有限的，不必要求信息传输过程中绝对无失真。 如人耳对语音信号接收的带宽和分辨率都有限，而语音信号的带宽高达20KHz，可以把频

3、谱范围20Hz20KHz的语音信号去掉高低端部分，只保留3003400Hz间的部分，这样，即使传输的语音信号存在一些失真，人耳也不易分辨或感觉出来，并可减少语音传输的开销，因而允许这种失真。 4 又如，由于人眼在接收视觉信号时的主观视觉特征，允许信息有某些失真，可由此降低信息传输速率，从而降低信息传输成本。(2) 无失真编码并非总是可能的。由于信源的输出通常是取值连续的消息，即信源输出的信息熵H无穷大，同时要求信道的信息传输率R也无穷大。但任何一个信道的实际带宽总是有限的，即信道容量总要受到一定的限制，不可能达到无穷大，故不可能实现完全无失真的信源信息传输。(3) 由于信道噪声的影响，即使信源

4、消息的编码是无失真的，消息在传输过程中也会产生失真。 5结论： 实际信息传输系统中的失真是不可避免的，有时甚至是必要的。问题： 在允许一定失真度的条件下，能够多大程度地压缩信息(最少需要多少比特数才能描述信源)。 香农论述了限定失真范围内的信源编码问题，定义了信息率失真函数R(D)，并论述了关于这个函数的基本性质，指出在允许一定失真度D的情况下，信源输出的信息传输率最低可压缩到R(D)值(即R(D)值是信源信息传输率的下限值)，从理论上给出了信息传输率与允许失真之间的关系，奠定了信息率失真理论的基础。 64.1 失真测度74.1 失真测度4.1.1 系统模型 限失真信源编码的系统模型如下图所示

5、。信源发出的消息X通过有失真信源编码器，编码后的输出通过理想无噪信道传输，经信源译码器译码后输出Y 。 8 由于信源编码为有失真编码，故输出的Y不是信源发出的消息X的精确重现。 为了定量描述信息传输率与失真之间的关系，已假定传输信道为理想无噪信道。 可以将信源编码引起的失真视为由于信道不理想所造成的(将有失真信源编码器与信源译码器之间的过程一并看作有噪信道该假想信道称为试验信道)。 由此，把有失真信源编码问题转化为无失真信源编码通过有噪信道传输的问题，进而可通过研究试验信道输入|输出间的互信息来研究限失真信源编码。 9在实际问题中，信号有一定的失真是可以容忍的。但是当失真大于某一限度后，信息质

6、量将被严重损伤，甚至丧失其实用价值。要规定 失真限度，必须先有一个定量地失真测度。为此可引入失真函数。4.1.2 失真度和平均失真度1.单符号失真度 试验信道的输入为X，取值于符号集Aa1,a2,an，试验信道的输出为Y，取值于符号集Bb1,b2,bm。设 分别为试验信道的输入与输出，若 ，则没有失真；否则就产生了失真。对每一对(xi,yj)，定义非负函数d(xi,yj)为单符号失真度(单符号失真函数)。 一般有 11 单符号失真度d(xi,yj)用来度量信源发出一个符号xi (i=1,n)时，信源译码器输出符号yj(j=1,m)所引起信息失真的大小。 规定d(xi,yj)的值越小代表失真越小

7、，显然，d(xi,yj)=0表示没有失真。 若信源符号集有n个符号，信源译码器的输出符号集有m个符号，则单符号失真度d(ui,vj)就有nm个，它可以排列成nm阶矩阵d称为(nm 阶)失真矩阵。 12说明： 这里假设X是信源，Y是信宿，那么X和Y之间必有信道。 实际上X指的是原始未失真信源，Y是失真信源。因此，从X到Y之间实际上包含了失真算法。所以这里的转移概率p(yj|xi)是指一种失真算法。也把p(yj|xi) 称为试验信道的转移概率，如图所示。 单符号失真度d(xi,yj)可根据实际信源的的失真情况来定义，方法各异。 13例1 设离散对称信源(r=s)，信源变量Xa1,a2,ar ，接收

8、变量Y b1,b2,br。定义单符号失真度这种失真称为汉明失真。汉明失真矩阵是一方阵，主对角线上的元素为零，其余全为1 对二元对称信源(s=r=2)，信源X=0,1，接收变量Y=0,1，则汉明失真矩阵为 14例2 设有删除信源，其信源变量X=a1,a2,ar，接收变量Y=b1,b2,bs (s=r+1) 。定义其单个符号失真度为 其中接收符号bs作为一个删除符号。 在这种情况下，意味着若把信源符号再现为删除符号bs时，其失真程度要比再现为其他接收符号的失真程度少一半。 若二元删除信源r=2，s=3，X=0,1, Y=0,1,2。失真度为 d(0,0)=d(1,1)=0 d(0,1)=d(1,0

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

10、小等来定义失真度d(xi,yj)。 173. 平均失真度 信源X和信宿Y都是随机变量，故单个符号失真度d(xi,yj) 也是随机变量。 单个符号失真函数d(xi,yj)和序列失真函数 仅表示两个具体符号或符号序列之间的失真大小，有必要在规定了d(xi,yj)后，定义一个能在平均意义上衡量信道每传输一个符号所引起的平均失真大小的量，即定义平均失真度： 设在离散情况下，信源X=a1,a2,ar，其概率分布P(x)=P(a1),P(a2),P(ar) ，信宿Y= b1,b2,bs 。若已知试验信道的传递概率为P(yj|xi)时，则平均失真度为： 18 称为单符号平均失真度，表示由信源X和试验信道X,

11、P(Y|X),Y组成的通信系统的平均失真度。 单符号平均失真度D不再像失真函数那样只是表示某两个具体符号或序列之间的失真大小，而是从总体平均意义上度量整个通信系统失真的大小。 单符号平均失真度D是信源统计特性p(ai)(i=1,2,r)，试验信道传递特性p(bj|ai)(i=1,2,r; j=1,2,s)和定义的失真函数(失真度)d(ai,bj) (i=1,2, ,r; j=1,2, ,s)的函数，即 D=f(p(ai), p(bj|ai), d(ai,bj) (i=1,2, ,r; j=1,2, ,s) 19 当d(ai,bj)被确定，信源的统计特性p(ai)给定以后，平均失真度D仅是试验信

12、道传递概率p(bj|ai)的函数，故改变信道传递概率，就可改变平均失真度D。 或者说，在信源固定(给定P(x)，单符号失真度固定时(给定d(ui,vj) ，选择不同的试验信道，相当于采用不同的编码方法，所得的平均失真度不同。 同理，序列平均失真度定义为 20保真度准则：若规定系统的平均失真度D不超过某一限定值D0，即 D D0作为“允许的失真” 。 有些试验信道满足DD0，而有些试验信道DD0，凡满足保真度准则平均失真度DD0的试验信道称为D失真许可的试验信道。 把所有D失真许可的试验信道组成一个集合，用符号PD表示，即 PD=P (yj |xi): D D0 引入D0使我们有可能把允许的平均

13、失真度D0作为对信道传递概率p(bj|ai)的一种约束条件，在此约束条件下，求解试验信道的信息传输速率的最小值，并赋予该最小值某种使用价值。 214.2 信息率失真函数及其性质224.2.1 信息率失真函数的定义 从直观感觉可知，若允许失真越大，信息传输率可越小；若允许失真越小，信息传输率越大，所以信息传输率与信源编码所引起的失真是有关的信源给定，且又具体定义了失真函数以后，总希望在满足一定失真的情况下，使信源传输给收信者的信息传输率R尽可能地小。即在满足保真度准则下，寻找信源必须传输给收信者的信息率R的下限值这个下限值与D有关。 从接收端来看，就是在满足保真度准则下，寻找再现信源消息所必须获

14、得的最低平均信息量。 23 从接收端来看，就是在满足保真度准则下，寻找再现信源消息所必须获得的最低平均信息量。 而接收端获得的平均信息量可用平均互信息I(X;Y)来表示，问题变成了在满足保真度准则的条件下，寻找平均互信息I(X;Y)的最小值。 24 寻找平均互信息I(U;V)的最小值 许可试验信道集合PD=P(yj|xi):DD0是所有满足保真度准则的试验信道集合，由任一试验信道的的传递概率所得的平均失真度D都满足保真度准则DD0，即平均失真度D都不超过给定的允许值D0，因而可以在D失真许可的试验信道集合PD中寻找一个信道P(yj|xi)，使I(X;Y) 取极小值。 25信息率失真函数定义 平

15、均互信息I(X;Y)是P(yj|xi)的型凸函数，在PD集合中, I(X;Y)极小值存在。这个最小值就是在DD0的条件下，信源必须传输的最小平均信息量，即R(D)称为信源的信息速率失真函数，简称信息率失真函数或率失真函数。 R(D) 的单位：比特/信源符号(奈特|哈特/信源符号) 说明 率失真函数R(D)给出了熵压缩编码可能达到的最小熵率与失真的关系。 率失真函数R(D)的逆函数称为失真率函数D(R)，表示一定信息速率下所可能达到的最小的平均失真。 261. R(D)的定义域证 先证明下界4.2.2 信息率失真函数的性质 27 对x的每一取值ai，令对应最小的d(ai,bj)条件概率p(bj|

16、ai)为1，其余条件概率为0，得Dmin，即取 因为R(D)为满足保真度准则的平均互信息I(X;Y)的最小值。 I(X;Y)是非负的，其最小值为0，因此把I(X;Y)=0的最小平均失真度定义为最大允许失真度Dmax，它也是R(D)=0中所有D中的最小值。 28因为I(X;Y)非负，所以R(D)0。在较大范围内求极小值一定不大于在所含的小范围内求极小值，所以 D1D2 R(D1) R(D2)表明R(D)是D的非增函数。D继续增加时，R(D)仍然为0，所以Dmax是使R(D)=0的最小平均失真度。 I(X;Y)=0时，输入随机变量X和输出随机变量Y统计独立，p(x,y)=p(x)p(y)，有 29

17、由于信源概率分布p(xi)和失真函数d(xi,yj)已经给定，故求Dmax相当于寻找分布p(yj)，使 最小。如果选取 最小时的分布p(yj)=1，而对其他的 选取p(yj)=0，则有 综上所述，信息率失真函数R(D)的定义域为(Dmin,Dmax)， 30说明： 允许失真度D的下限可以是零，当Dmin=0时，即信源不允许任何失真，此时，信息传输率应不大于信源熵，即 R(0)H(X)。 当允许失真度大于上限值(DDmax)时，R(D)=0。 而当DminDDmax时， 0R(D)H(X) 。 31例 设试验信道输入概率空间和失真矩阵如下所示，求Dmin和 Dmax以及相应的试验信道的转移概率矩

18、阵。解令对应最小失真度d(ai,bj) 的 p(bj|ai)=1，其它为“0”，可得对应Dmin 的试验信道转移概率矩阵为 (显然p(y|x)与d同阶。) 32上式中第二项最小，所以令 p(b2)=1，p(b1)=p(b3)=0，可得对应 Dmax的试验信道转移概率矩阵为 332. R(D)是关于平均失真度D的下凸函数 设 D1，D2 为任意两个平均失真度，取0a1 ，则有： R(a D1+(1-a)D2)a R( D1)+(1-a)R(D2)证 信源分布给定后，信息率失真函数R(D)可以看作试验信道转移概率p(y|x)的函数，即 34令D0=aD1+(1-a)D2, p0(y|x)=ap1(

19、y|x)+(1-a)p2(y|x), 显然0p0(y|x)1，p0(y|x)可视为一个新的试验信道，该试验信道的平均失真度D为 353 . R(D) 是 (Dmin,Dmax)区间上的连续和严格单调递减函数。 由信息率失真函数的下凸性可知，R(D)在(Dmin,Dmax)上连续。又由R(D)函数的非增性且不为常数知，R(D)是区间(Dmin,Dmax) 上的严格单调递减函数。 信息率失真函数的一般形状如下图所示 36说明 Dmin和Dmax的取值取决于失真矩阵。 若对任一ai，都至少存在一个bj使得d(ai,bj)=0，则有 Dmin=0； 若失真矩阵中存在无穷大值，则Dmax可取到无穷大，

20、此时R(Dmax)=0。 如果失真矩阵的每行和每列有且仅有一个元素为0， 则此时Dmin=0，且有R(0)=H(X)-H(X|Y)=H(X)，当信 源为连续信源时，H(X)=，此时R(0)=。 37R(D）的物理意义：对于给定的信源，在满足保真度准则下，必须传送的最小信息量，它既反映了用户容忍程度，也反映了信息率允许压缩的最小值，R(D)越大，越难压缩，反之可压缩率就大。4.3离散无记忆信源的信息率失真函数394.3 离散无记忆信源的信息率失真函数 已知信源的概率分布p(x)和失真函数d(x,y)，就可求得信源的信息率失真函数R(D) 。原则上它与信道容量一样，即在有约束条件下求极小值的问题(

21、即适当选取试验信道P(y|x)使平均互信息最小化)。即求 40 使用变分法或拉格朗日乘子法等方法求解约束条件下函数极值问题时，通常得到参数形式表述，且很难计算。 若信道具有某种对称性，则可简化信道容量的计算。同样在计算率失真函数时，利用信源和失真矩阵的对称性也可大大简化率失真函数的计算。 以下先说明特殊情况下R(D)的计算，然后讨论R(D)一般的参数表述。 414.3.1 等概率、对称失真信源的R(D)计算 对于等概、对称失真的信源，存在一个与失真矩阵具有同样对称性的转移概率分布达到率失真R(D)(证明略)。例4.3.1一个二元等概平稳无记忆信源X=0,1，接收符号集为Y=0,1,2，失真矩阵

22、为 求率失真函数R(D) 。解 由于信源等概分布，失真函数具有对称性，故存在着与失真矩阵同样具有对称性的转移概率分布达到率失真R(D) 。 42该转移概率矩阵可写为由于d(0,1)=d(1,0)=，因此对于任何有限平均失真，必须有=0。于是转移概率矩阵变为 因此，=1-D 43 44可求出此时的互信息为相应的率失真函数R(D)如图所示。 45例4.3.2 设有n元等概平稳无记忆信源X=1,n，接收符号集Y =1,n，若规定失真矩阵为求率失真函数。解 由于信源等概分布，失真函数具有对称性，存在着与失真矩阵同样具有对称性的转移概率分布达到率失真函数R(D)。 46该转移概率矩阵可写为 47分别取n

23、=2，则 R(D)=1-H(D,1-D) 取n=4，则 R(D)=2-H(D,1-D)Dlog3 取n=8，则 R(D)=3-H(D,1-D)Dlog7 48得到率失真函数曲线如下图所示。当D=0，即无失真时，n=2, R(0)=1-H(1)=1 (bit/sym) n=4, R(0)=2-H(1)=2 (bit/sym) n=8, R(0)=3-H(1)=3 (bit/sym) 49有失真时，如D=0.2时 50R(D）的物理意义：对于给定的信源，在满足保真度准则下，必须传送的最小信息量，它既反映了用户容忍程度，也反映了信息率允许压缩的最小值，R(D)越大，越难压缩，反之可压缩率就大。 4.

24、3.2 离散无记忆信源的信息率失真函数的参量 表述 求信源的R(D)函数，原则上与求信道容量一样，是在有约束条件下求极小值的问题，也就是适当选取试验信道P(y|x)使平均互信息最小化，应用拉格朗日乘子法，原则上可以求出解来。 在没有不等式约束(P(Y|X)非负)条件下，互信息I(X;Y)是信道转移概率P(Y|X)的下凸函数，故必有唯一的极小值(最小值)。 在不等式约束下，互信息I(X;Y)的最小值有可能发生在某几个条件概率为0的边界上，进而可能涉及多组等式约束的极值求解问题，故一般无显式解析解，可求得其参量表述。 52 设试验信道的输入为X，输入符号集A=a1,a2,an，对应的p(x)=(p

25、1,p2, ,pn)；设试验信道的输出为Y，输出符号集B=b1,b2,bm，对应的q(y)=(q1,q2, ,qm)，失真矩阵为 53 由于应用拉格朗日乘子法解得的一个或某几个P(yj|xi)很可能是负的。在这情况下，必须假设某些P(yj|xi) =0，然后重新计算，这就使得计算复杂化了。 一般可采用收敛的迭代算法在计算机上求解R(D)函数。 以下用拉格朗日乘子法求解R(D)函数，并用S作为参量来表述率失真函数R(D)和失真函数D(S)。 54 问题表述：求解信息率失真函数R(D)就是寻找达到R(D)的转移概率分布，即求解有约束的极值问题 由于使R(D)最小的Pj|i总是在许可试验信道集合PD

26、的边界上，所以求极值时，平均失真度约束条件的不等式取等号，即 55 由式(1)知，当信源的概率分布pi固定时，平均互信息仅仅是试验信道Pj|i的函数。 考虑问题描述方程组中的约束条件(3)和(5)可知，约束条件有r+1个；未知数为转移概率Pj|i，有rs个。 若先不考虑式(2)的约束，约束条件式(3)包含r个等式，取拉格朗日乘子i(i1,2,r)分别与之对应；并取拉氏乘子S与式(5)对应。则S、i (i1,2,r)分别表示r+1个约束条件的待定常数。构造目标函数 56 (6)表示的目标函数右边第一项为互信息，后两项都是转移概率Pj|i的线性函数，所以(Pj|i)仍是Pj|i的下凸函数，因此局部

27、极小也就是全局极小。 求极值，就是求目标函数一阶导数等于零的方程组的解，即求该式共有rs个方程，加上式(3) r 个方程和式(4) 1 个方程，共有(r+1+ rs)个方程。 而未知数i(i=1,2,r)、S和P(yj|xi )(i=1,2,r，j=1,2,s)也正好对应(r+1+rs)个，所以原则上只需求解式(6)、(3)和(4)的方程组，即可求出I(X;Y)在约束条件下的极小值。 57 58 59 (*)含有s个方程，s个未知数qj(j=1,2,s)，S为参数，可解。整个问题的求解顺序为 先求qj(j=1,2,s) = i(i=1,2,r) = pj|i = D(S) = R(S) 60注

28、意： 这时所得的D(S)是以S为参量的表达式，而不是显式表达式，因而所得到的R(D)的表达式也是以S为参量的表达式。 参量S对应的限制条件为 ，它与允许的失真度D有关，所以以S为参量就相当于以D为参量。 61信息率失真函数R(D)的求解过程： 参数S给定时，由 求出i (i=1,2,r)； 由 求出qj (j=1,2,s) ； 再由 62参数S的几何意义(信息率失真函数R(D)与参数S关系分析)： 63 64例 设离散信源 和接收变量：Y=0,1 并设失真矩阵为:求该信源的信息率失真函数R(D)。解 根据计算可得 Dmin=0，Dmax=1/2 ，由题设知 p1=p2=1/2，d11=0，d1

29、2=2，d21=1，d22=0根据参量表达式按如下步骤进行求解。 65第一步：由 (j=1,2)，求i。第二步：由 (j=1,2)，求qj。 66第三步：由式 求D(s)。 将前两步的结果代入上式，有第四步：由 求R(s)。 将前三步结果代入上式，有 67由 ，还可求得此时的试验信道转移概率为 68例 设有二进制非等概信源，试验信道输入符号集A=0,1，p(0)=p1=p，p(1)=p2=1-p，试验信道输出符号集B=0,1 ，失真函数为汉明失真。求该信源的信息率失真函数R(D)。解 由题知，d11=0, d22=0, d12=d21=1，按前述参数方程的求解步骤求解。第一步：由 (j=1,2

30、)，求i。第二步：由 (j=1,2)，求qj。 69第三步：由式 (i,j=1,2)，求D(s) 将前两步的结果代入上式，有第四步：将S、1和2的结果代入R(s)，有 70 由图可见，当D=0(无失真时)，R0.5(0)=1bit/sym， R0.25(0)=0.8bit/sym, R0.125(0)=0.6bit/sym；限失真时，如D=0.1， R0.5(0.1)=0.67bit/sym,R0.25(0.1)=0.45bit/sym, R0.125(0.1)=0.17bit/sym压缩比分别为K0.5=1/0.67K0.250.8/0.450 ，以及任意长的码长k，一定存在一种信源编码C，其码字个数为M2kR(D) +，使编码后码的平均失真度DD0。 106定理解释 对于任何失真度D，只要码长k足够长，总可以找到一种信源编码，使编码后每个信源符号的信息传输率略大于(直至无限逼近)率失真函数R(D)而码的平均失真度不大于给定的允许失真度，即DD0。 由于R(D)为给定D前提下信源编码可能达到的信息传输率下限， 所以香农第三定理说明了： 达到信息传输率下限的最佳信源编码是存在的。 107实际的信源编码(无失真编码或先限失真编码后无失真编码)的最终目标是尽量接近最佳编码，使编码信息传输率接近最大值logr，而同