信息论部分课件第四章率失真编码

第四章 率失真编码,主 讲： 易 波 老 师 博一工作室2010年V.1版,在允许一定程度失真的条件下，能够把信源信息压缩到什么程度，即最少需要多少比特数才能描述信源。也就是，在允许一定程度失真的条件下，如何能快速地传输信息。这就是本章将讨论的问题。 信息率失真理论是量化、数模转换、频带压缩和数据压缩的理论基础。 本章主要介绍信息率失真理论的基本内容，侧重讨论离散无记忆信源。首先给出信源的失真度和信息率失真函数的定义与性质，在这基础上论述率失真准则下的信源编码定理。,主要内容,1、有失真编码的目的 2、采用限失真编码的原因 3、失真测度 4、信息率失真函数及其性质 5、限失真信源编码定理,1、有失真编码的目的 在允许的失真范围内把编码后的信息率压缩到最小。如果限定失真范围，又称为限失真编码，编码后的信息率得到压缩。 2、采用限失真编码的原因 1）保熵编码并非总是必需的。 2）保熵编码并非总是可能的。 3）可降低信息率有利于传输和处理。,一般通信系统框图,根据信道编码定理，我们可以把信道编码、信道、信道译码（C点到F点）这三部分看成没有干扰的广义信道，这样收信者收到消息后所产生的失真（误差）只是由信源编码带来的。,从直观感觉可知，若允许的失真越大，信息传输率可以越小；若允许的失真越小，信息传输率需越大。所以信息传输率与信源编码所引起的失真是有关的。,在限失真信源编码的情况下，信源的编译码会引起接收信息的错误，这一点与信道干扰引起的错误可作类比。为了便于讨论，我们将图中B点至G点全部略去，将信源的限失真编译码的效果等同于一个 “试验信道”。,4.1 失真度和平均失真度,对应于每一对(u,v),我们指定一个非负的函数,(4.1),称为单个符号的失真度(或称失真函数).用它来测度信源发出一个符号ui,而在接收端再现成接收符号集中一个符号vi,所引起的误差或失真。通常较小的d值代表较小的失真，而d(ui,vj)=0表示没有失真。 由于信源变量U有r个符号，而接收变量V有S个符号,所以d(ui,vj)就有r×s个。这r×s个非负的函数要吧排列成矩阵形式，即,(4.2),我们称它为失真矩阵D,它是r ×s阶矩阵.,例4.1 离散对称信源(r=s).信源变量U=u1,u2, ,us, 接收变量V=v1, v2, vs. 定义单个符号失真度,(4.3),它表示当再现的接收符号与发送的信源符号相同时,就不存在失真和错误,所以失真度d(ui,vj)=0。,汉明失真矩阵D是一方阵，并且对角线上的元素为零,即,(4.4),对于二元对称信源(s=r=2),信源U=0,1,而接收变量V=0,1.在汉明失真定义下,失真矩阵为,即 d(0,0)=d(1,1)=0 d(0,1)=d(1,0)=1 它表示当发送信源符号0(或符号1)而接收后再的仍是符号0(或符号1)时,则认为无失真或无错误存在,例4.2 删除信源.信源U= u1,u2, ,ur,接收变量V= v1,v2, ,vs,s=r+1.定义它的单个符号失真度为,(4.5),其中二元删除信源r=2,s=3,U=0,1,V=0,1,2.失真度为,则得,例4.3 对称信源(r=s),信源U= u1,u2, ,ur,接收变量V= v1,v2, ,vs。失真度定义 d(ui,vj)=(vj- ui)2 (对所有i,j) (4.6) 当r=3时,U=0,1,2,V=0,1,2,则失真矩阵为,平均失真度,规定了单个符号失真度d(ui,vj)后,传输一个符号引起的平均失真,即信源平均失真度,其中E · 是对U和V的联合空间求平均.若已知试验信道的传递概率为P(vj|ui)时,则平失真度为,(4.7 ),设发送的信源序列为ai=(ui1, ui2, uiN),而再现的接收序列为j=(vj1, vj2, vjN),因此序列的失真度,(4.8 ),而对于N维信源符号序列的平均失真度,(4.9),也可以写成,(4.10),由此所得的信源平均失真度(单个符号的平均失真度),(4.11),当信源与信道都是无记忆时,N维信源序列的平均 失真度,(4.12),而信源的平均失真度,(4.13),其中/DL是信源序列第L个分量的平均失真度。如果离散信源是平稳信源，即有,则,即离散无记忆平稳信源通过无记忆的试验信道其信源序列的平均失真度等单个符号平均失真度的N倍。 若平均失真度/D不大于我们所允许的失真D，即 /D D (4.14) 我们称此为保真度准则.同理,N维信源序列的保真度准则应是平均失真度/D(N)不大于允许的失真ND,即 /D(N) ND (4.15) 凡满足保真度准则平均失真度/D D的这些实验信道称为D失真许可的试验信道。把所有D失真许可的试验信道组成一个集合，用符号BD表示，即 BD=P(vj|ui):/D D BD=P(j|ai):/D(N) ND (4.16),4.2 信息率失真函数及其性质,函数R(D)的一些基本性质: 1. R(D)的定义域(0,Dmax) 1)Dmin和R(Dmin) 当给定信源U,P(u),及给定失真矩阵D,信源的最小平均失真度为,(4.23),(4.24),当固定某个ui,那么对于不同的vj其d(ui,vj)不同(即在失真矩阵D中第i行的元素不同).其中必有最小值,也可能有若干个相同的最小值。选择这样试验信道,它满足,(4.25),允许失真度D是否能达到零,这与单个符号的失真函数有关,只有当失真矩阵中每行至少有一个零元素时,信源的平均失真度才能达到零值。 若信源要求无失真地传输，则信息传输率至少应等于信源输出的信息量信息熵，即 R(0)=H(U) (4.27),但是,式(4.25)能否成立是有条件的,它与失真矩阵形式有关,只有当失真矩阵中每行至少有一个零,并每一列最多只有一个零时,式(4.25)才成立.否则R(0)可以小于H(U),它表示这时信源符号集中有些符号可以压缩,合并,而不带来任何失真。 例4.4 删除信源U取值于0,1,V取值于0,1,2,而失真矩阵为,由式(5.26)可知最小允许失真度为,满足最小允许失真度的试验信道是一个噪声无损的试验信道,信道矩阵为,由前知，在这个无噪无损的试验信道中，有 I(U;V)=H(U) 因此,由式(4.26)计算得,由式(4.25)可知,使平均失真度达到最小值(D=1/6)的信道必须满足,这些信道的共同特征是信道矩阵中每列有不止一个非零元素,所以其信道疑义度H(U|V) 0,则得,若失真矩阵改成,可得,同理,这些信道的信道矩阵中每列有不止一个非零元素,得,表示在失真矩阵D下信源本身可实现无失真的压缩编码,如图4.3所示.,2)Dmax和R(Dmax) 已知I(U;V)是非负的,其下限值为零.由此可得,R(D)也是非负的,它的下限值也为零.所以当R(D)等于零时,所对应的平均失真度/D的下界就是上界值Dmax如图4.4。,在P(u) 0的前提下,P(v|u)只是v的函数,而与u无关, 即,根据平均失真度定义,R(D)=0的平均失真度为,所在Dmax就是在R(D)的条件下,取/D的最小值,即,这就是求d/(v)的数学期望的最小值因为d/(v)0,随v的选取总有珍上最小值.所以,对Q(v)求d/(v)的数学期望的最小值,就等于在vjV中求最小值d/(v).由此得,(4.29),2.R(D)是允许失真度D的U型凸函数 根据凸函数的定义只需证明对于任意, /0, +/ =1,和任意失真度D/,D/Dmax,有 R(D/+/ D/) R(D/)+/ R(D/) (4.30) 3.R(D)函数的单调递减速性和连续性。 R(D)的非增性是容易理解的。因为允许的失真越大,所要求的信息率可以越小。 利用R(D)的下凸型来证明递减。即在DminDDmax范围内R(D)不可能为常数。,一般信源(有记忆,无记忆)R(D)函数的典型曲线图,如图4.5所示。,图4.5 R(D)函数的典型图形,4.3信息率失真函数的参量表述及其计算,适当选取试验信道P(v|u)使平均互信息,(4.31),最小化,并使P(vj|ui)满足以下约束条件:,和,(4.32),(4.33),(4.34),辅助函数,(4.35),求极值,就是求辅助函数一阶导数等于零的方程组的解.因为已知平均互信息I(U;V)是信道P的U型凸函数,所以若极值存在,它一定是极小值.即求,(4.36),为此,又因为,求解式(4.35),(4.33)和(4.34)的方程组,即可求出I(U;V)在约束条件下的极小值. 为了求解方便,令,整理式(5.35)得,(4.38),求解上式,可得r×s个传递概率,(4.39),将上式对j求和,得,(4.40),再将式(5.39)乘以P(ui),再对i求和,得,若P(vj) 0,即得,(4.41),将式(5.40)代入上式,由此得到用参量S表达的P(vj),(4.42),从上式方程就可求解出S个输出符号的概率P(vj)。但应强调指出，当P(vj)=0时Cj不必等于1,可以证明它必须小于等于1.,将所求的P(vj)代入式(5.40)可求出i。若将式(5.40)代入式(5.39)则得,(i=1,2,r) (j=1,2,s) (4.43),由式(4.42)解得的概率分布P(vj),代入上式就可求解出极小值的试验信道的传递P(vj|uj)。这时所得的结果是以S为参量的表达式，而不是显示表达式。将式(4.39)代入式(4.34)和(4.31),得到以S为参量的信息率函数R(S)和失真函数D(S)。,(4.44),(4.45),将R(S)对D求导数,则得,(4.46),其次,将式(4.41)对S取导,则得,将上式两边乘以P(vj),并对j求和,得,即,由式(4.48)表明,参量S是信息率失真函数R(D)的斜率。,4.4 二元信源和离散对称信源的R(D)函数,二元对称信源的R(D)函数,设二元对称信源U=0,1,其概率分布P(u)=w,1- w, w1/2,而接收变量V=0,1,设汉明失真矩阵的,(4.65),因而最小允许失真度Dmin=0。并能找到满足该最小失真的试验信道,且是一个无噪无损信道,其信道矩阵为,计算得,在式(5.65)失真函数定义下,又计算出最大允许失真度为,要达到最大允许失真度的试验信道,惟一确定为,即这个试验信道能正确传送信源符号u=1,而传送信源符号u=0,而传送信源符号u=0时,接收符号一定为v=1.那么,凡发送符号u=0时,一定都错了。而u=0出现的概率为w,所以信道的平均失真度为w.在这种试验信道条件下,可计算得 R(Dmax)=R(w)=I(U;V)=0,一般情况下当0DDmax=w时,平均失真度为,PE是信道传输的平均错误概率,如式(5.10).这就是说在汉明失真度的情况下,平均失真度等于平均错误概率。 此时，选取任一信道使/D=D,得平均互信息 I(U;V)=H(U)-H(U|V)=H(w)-H(U|V) 根据费诺不等式(5.15),当r=2时有 H(U|V) H(PE)=H(D) 所以得 I(U;V) H(w)-H(D) 这是平均互信息的下限值。,根据信息率失真函数的定义，当0DDmax时,下限值就是R(D)的数值.为了证实这一点,必须找到一个试验信道,使其平均失真度Ed D,而平均互信息达到这个下限值。即 I(U;V)=R(D)=H(w)-H(D) 寻找这个试验信道最好的方法是引进一个“反向”的试验信道,现设这个反向信道为,如图4.5所示.可计算得,因为0Dw=1/2,0P(v)1,所以,所设的反向试验信道是存在的。在该试验信道的条件下，平均失真度,又,图4.7 反向试验信道,在该