单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章 信息率失真函数,第四章 信息率失真函数,1,无失真信源编码和有噪信道编码（香农第一定理和香农第二定理）告诉我们：,只要信道的信息传输速率小于信道容量，总能找到一种编码方法，使得在该信道上的信息传输的差错概率任意小；反之，若信道的信息传输速率大于信道容量，则不可能使信息传输差错概率任意小。,但是，无失真的编码,并非,总是必要的,。,无失真信源编码和有噪信道编码（香农第一定理和香农第二定理）告,2,原始图像,红色图像,绿色图像,蓝色图像,原始图像和限失真图像,原始图像红色图像绿色图像蓝色图像原始图像和限失真图像,3,香农首先定义了信息率失真函数R(D)，并论述了关于这个函数的基本定理。,定理指出：在允许一定失真度D的情况下，信源输出的信息传输率可压缩到R(D)值，这就从理论上给出了信息传输率与允许失真之间的关系，奠定了信息率失真理论的基础。,信息率失真理论是进行量化、数模转换、频带压缩和数据压缩的理论基础。,本章,主要介绍,信息率失真理论的基本内容，重点讨论离散无记忆信源。,给出信源的失真度和信息率失真函数的定义与性质；,讨论离散信源和连续信源的信息率失真函数计算；,在此基础上论述保真度准则下的信源编码定理。,香农首先定义了信息率失真函数R(D)，并论述了关于这个函数的,4,4.1 失真测度,一、失真度,从直观感觉可知，若允许失真越大，信息传输率就可越小；若允许失真越小，信息传输率需越大。,所以信息传输率与（信源）编码所引起的失真(或误差)是有关的。,4.1 失真测度一、失真度,5,首先讨论,失真的测度,。,离散无记忆信源X，信源符号集X,a,1,a,2,a,r,，概率分布为,p,(,x,)p(,a,1,),p(,a,2,),p(,a,r,)。,信源符号通过信道传输到接收端，接收端的接收符号集Y b,1,b,2,b,s,。,对应于每一对(,a,i,b,j,)，我们指定一个非负的函数：,称为单个符号的,失真度,(或失真函数)。,通常较小的d值代表较小的失真，而d(,a,i,b,j,)0表示没有失真。,首先讨论失真的测度。称为单个符号的失真度(或失真函数,6,若信源变量X有r个符号，接收变量Y有s个符号，则d(,a,i,b,j,)就有rs个,它可以排列成矩阵形式，即：,该失真矩阵D，是,rs,阶矩阵。,若信源变量X有r个符号，接收变量Y有s个符号，则d(ai,b,7,实际,这里X指的是原始的未失真信源，而Y是指失真以后的信源。如果,假设,X是信源，Y是信宿，那么X和Y之间必有信道。,从X到Y之间实际上是失真算法，所以这里的转移概率,p,(b,j,/,a,i,)是指一种失真算法，,有时又把,p,(b,j,/,a,i,)称为,试验信道,的转移概率，如图所示。,原始信源,失真信源,试验信道,信道,X,Y,p,(b,j,/,a,i,),实际这里X指的是原始的未失真信源，而Y是指失真以后的信源。如,8,例1,离散对称信源(r=s)，“0-1”失真,。信源X,a,1,a,2,a,r,，接收Y b,1,b,2,b,s,。定义单个符号失真度：,这种失真称为汉明失真。汉明失真矩阵是一方阵，对角线上的元素为零，即：,对二元对称信源(sr2)，信源X0,1，接收变量Y0,1。在汉明失真定义下，失真矩阵为：,例1 离散对称信源(r=s)，“0-1”失真。信源X,9,例2,删除信源,。信源X,a,1,a,2,a,r,，接收Y b,1,b,2,b,s,(s=r+1)。定义其单个符号失真度为：,其中接收符号b,s,作为一个删除符号。,此时，意味着若把信源符号再现为删除符号b,s,时，其失真程度要比再现为其他接收符号的失真程度少一半。,二元删除信源 r 2，s 3，X0,1，Y0,1,2。,失真度为：,则,d(0,0)=d(1,1)=0,d(0,1)=d(1,0)=1,d(0,2)=d(1,2)=1/2,除j=s以外所有的j和i,所有i,例2 删除信源。信源Xa1,a2,ar，接收,10,例,对称信源,(s=r)。信源X,a,1,a,2,a,r,，接收Y b,1,b,2,b,s,。,若,失真度定义为：,如果信源符号代表信源输出信号的幅度值，这就是一种,平方误差失真度,。它意味着幅度差值大的要比幅度差值小的所引起的失真更为严重，其严重的程度用平方来表示。,当 r3时，0,1,2，0,1,2，则失真矩阵为：,上述例子说明了失真度的具体定义。,一般情况下根据实际信源的失真，可以定义不同的失真和误差的度量。另外还可以按其他标准，如引起的损失、风险、主观感觉上的差别大小等来定义失真度d(,a,b)。,例 对称信源(s=r)。信源Xa1,a2,11,二、序列失真度,设,，其中,取自信源符号集,A,；,其中,取自,信宿,符号集B。,则序列失真度定义为：,二、序列失真度设,12,三、平均失真度,信源 X 和信宿 Y 都是随机变量，故单个符号失真度d(,a,i,b,j,)也是随机变量。,规定了单个符号失真度d(,a,i,b,j,)后，,传输一个符号引起的平均失真，即信源平均失真度,：,在,离散情况下,，信源X,a,1,a,2,a,r,，其概率分布p(,x,)p(,a,1,),p(,a,2,),p(,a,r,)，信宿Y,b,1,b,2,b,s,。,若已知试验信道的传递概率为p(,b,j,/,a,i,)时，则平均失其度为：,三、平均失真度信源 X 和信宿 Y 都是随机变量，故单个,13,若平均失真度D不大于我们所允许的失真D,0,，即：,D,D,0,称此为,保真度准则,。,信源固定（即给定了p(x)），单个符号失真度固定时（即给定了d(,a,i,b,j,)），选择不同试验信道，相当于不同的编码方法，所得的平均失真度是不同的。,有些试验信道满足D,D,0,，而有些试验信道DD,0,。,凡满足保真度准则-平均失真度D,D,0,的试验信通称为-,D失真许可的试验信道,。,把所有D失真许可的试验信道组成一个集合，用符号P,D,表示，则：,P,D,=p(b,j,/,a,i,)：D,D,0,若平均失真度D不大于我们所允许的失真D0，即：信源固定（即,14,4.2 信息率失真函数及其性质,一、信息率失真函数的定义,信源给定，且又具体定义了失真函数以后，总希望在满足一定失真的情况下，使信源传输给收信者的信息传输率R尽可能地小。-,即在满足保真度准则下，寻找,信源必须传输给信宿的信息率R,的下限值,-这个下限值与D有关。,从接收端来看，就是在满足保真度准则下，寻找再现信源消息所必须获得的最低平均信息量。,而接收端获得的平均信息量可用平均互信息I(X;Y)来表示，这就变成了在满足保真度准则的条件下，,寻找平均互信息I(X;Y)的最小值,。,4.2 信息率失真函数及其性质一、信息率失真函数的定义 信,15,寻找平均互信息I(X;Y)的最小值。而P,D,是所有满足保真度准则的试验信道集合，因而可以在D失真许可的试验信道集合P,D,中寻找一个信道,p(b,j,/,a,i,),，使I(X;Y)取极小值。,由于平均互信息I(X;Y)是,p(b,j,/,a,i,),的,U型凸函数,，所以在P,D,集合中，极小值存在。这个最小值就是在D,D,0,的条件下，,信源进行传输的最小平均信息量,。即：,R(D)-信息率失真函数或简称,率失真函数,单位是：比特信源符号,寻找平均互信息I(X;Y)的最小值。而PD是所有满足保真度准,16,率失真函数给出了熵压缩编码可能达到的最小熵率与失真的关系;,其逆函数D(R)称为失真率函数,D(R)表示一定信息速率下所可能达到的最小的平均失真。,率失真函数给出了熵压缩编码可能达到的最小熵率与失真的关系;,17,二、信息率失真函数的性质,允许失真度D的下限可以是零，这是不允许任何失真的情况。,1、R(D)的定义域,R(D),的定义域为,且：,二、信息率失真函数的性质允许失真度D的下限可以是零，这是不允,18,解：,例4,设,试验信道输入符号集,，,各符号等概分布，失真矩阵如下所示，求 和 以及相应的试验信道的转移概率矩阵。,令对应最小失真度 的 ，其它为“0”，可得对应 的试验信道转移概率矩阵为：,解：例4 设试验信道输入符号集,19,上式中第二项最小，所以令 ，可得对应 的试验信道转移概率矩阵为:,上式中第二项最小，所以令,20,2,、R(D),是关于平均失真度D的下凸函数,设 为任意两个平均失真，则有：,3,、R(D),是 区间上的连续和严格单调递减函数。,信息率失真函数的一般形状,(),2、R(D)是关于平均失真度D的下凸函数 设,21,4.3 离散无记忆信源的信息率失真函数,已知信源的概率分布p(,x,)和失真函数d(,x,y,)，就可求得信源的R(D)函数。原则上它与信道容量一样，即在有约束条件下求极小值的问题。,也即选取适当的试验信道p(,x,/,y,)使平均互信息最小化：,其约束条件为:,一般取等号,4.3 离散无记忆信源的信息率失真函数 已知,22,一、等概率、对称失真信源的R(D)计算,对于等概、对称失真的信源，存在一个与失真矩阵具有同样对称性的转移概率分布达到率失真,R(D)。,一、等概率、对称失真信源的R(D)计算 对于,23,解：,例5,有一个二元等概平稳无记忆信源,，,接收符号集为,且失真矩阵为,：,求率失真函数R(D)。,由于信源等概分布，失真函数具有对称性，因此，存在着与失真矩阵,具有同样对称性的转移概率分布,达到率失真R(D)，该转移概率矩阵可写为：,由于 ，因此对于任何有限平均失真，必须 ,于是转移概率矩阵为：,解：例5有一个二元等概平稳无记忆信源,24,对应此转移概率矩阵的平均失真：,因此:,可求得此时的互信息为：,对应此转移概率矩阵的平均失真：,25,二、信息率失真函数的参量表述,求信源的R(D)函数，原则上与求信道容量一样，是在有约束条件下求极小值的问题。,也就是适当选取试验信道p(,y,/,x,)使平均互信息最小化，,应用拉格朗日乘子法，原则上可以求出解来。,二、信息率失真函数的参量表述 求信源的R(D,26,困难在于：,要得到显式的解析表达式，则比较困难，通常只能用参量形式来表达。,要保证约束条件式,p(b,j,/,a,i,),0,，应用拉格朗日乘子法解得的某些,p(b,j,/,a,i,),很可能是负的。在这情况下，必须假设其,p(b,j,/,a,i,),=0,，然后重新计算，这就使得计算复杂化了。,下面介绍用拉格朗日乘子法求解R(D)函数，并用s作为参量来表述率失真函数R(s)和失真函数D(s)。,困难在于：,27,由(1)式知，当信源的概率分布,p(,x,),固定，平均互信息仅仅是试验信道,p(b,j,/,a,i,),的函数。,若,先不考虑(2)式的约束,，约束条件(3)式包含n个等式，取拉格朗日乘子,i,(i1,2,n)分别与之对应；并取拉氏乘子s与(4)式对应。由此构成辅助函数：,(2),(3),(4),(1),由(1)式知，当信源的概率分布p(x)固定，平均互信息仅,28,求极值，即为求(5)式一阶导数等于零的方程组的解。,已知平均互信息I(X;Y)是信道P的U型凸函数，所以，若极值存在，它一定是极小值。即求：,得：,-(6),求极值，即为求(5)式一阶导数等于零的方程组的解。得：-,29,-(6),(1),(3),(4),-(6)(1)(3)(4),30,经整理得结论：,经整理得结论：,31,注：,这时所得的结果是以s为参量的表达式，而不是显式表达式，因而所得到的R(D)的表达式也是以s为参量的表达式。,参量s对应的限制条件为(4)式，它与允许的失真度D有关，所以，以s为参量就相当于以D为参量。,(4),注：这时所得的结果是以s为参量的表达式，而不是显式表达式，因,32,例6,设离散信源,和接收变量：,并设失真矩阵为:,求该信源的信息率失真函数R(D)。,解,：根据(4.2.4)式计算可得 ，由题已知，,根据参量表达式按如下步骤进