zyw7保真度准则下的信源编码课件.ppt
普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,1,第7章保真度准则下的信源编码,本章主要讨论在信源允许一定失真D情况下所需的最少信息率，从分析失真函数、平均失真出发，求出信息率失真函数R（D） 。 7.1 D平均失真和信息率失真函数7.2信息率失真函数及其性质7.2 离散信源和连续信源的R（D）计算7.6保真度准则下的信源编码定理,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,2,平均失真和信息率失真函数,失真函数平均失真信息率失真函数R(D)信息率失真函数的性质,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,3,7.1 平均失真和信息率失真函数,在实际问题中，信号有一定的失真是可以容忍的。但是当失真大于某一限度后，信息质量将被严重损伤，甚至丧失其实用价值。要规定失真限度，必须先有一个定量的失真测度。为此可引入失真函数。,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,4,失真函数,假如某一信源U，输出样值为ui，uiu1,ur，经过有失真的信源编码器，输出V，样值为vj，vj v1,vs。如果uivj，则认为没有失真d=0；如果ui vj，那么就产生了失真。失真的大小，用一个量来表示，即失真函数d(ui， vj)，以衡量用vj代替ui所引起的失真程度。一般失真函数定义为,试验信道编码方法,U,V,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,5,失真矩阵,单个符号的失真度的全体构成的矩阵 ，称为失真矩阵,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6,均方失真：,相对失真：,误码失真：,绝对失真：,前三种失真函数适用于连续信源，后一种适用于离散信源。,最常用的失真函数,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,7,举例：常见的失真矩阵定义,7.1,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,8,失真函数的定义可以推广到序列编码情况，如果假定离散信源输出符号序列U=(U1U2UlUN)，其中N长符号序列样值ui(ui1ui2uiluiN)，经信源编码后，输出符号序列V=(V 1V 2V lVN)，其中N长符号序列样值vj(vj1vj2vjlvjN)，则失真函数定义为：,其中d(uil，vjl)是信源输出N长符号样值ui中的第l个符号uil时，编码输出N长符号样值vj中的第l个符号vjl的失真函数。,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,9,平均失真,由于ui和vj都是随机变量，所以失真函数d(ui，vj)也是随机变量，限失真时的失真值，只能用它的数学期望或统计平均值，因此将失真函数的数学期望称为平均失真，记为,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,10,对于连续随机变量同样可以定义平均失真,对于L长序列编码情况，平均失真为,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,11,信息率失真函数R(D),普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,12,信息率失真函数R(D),信源编码器的目的是使编码后所需的信息传输率R尽量小，然而R越小，引起的平均失真就越大。给出一个失真的限制值D，在满足平均失真 D的条件下，选择一种编码方法使信息率R尽可能小。信息率R就是所需输出的有关信源U的信息量。将此问题对应到信道，即为接收端V需要获得的有关U的信息量，也就是互信息I(U;V)。这样，选择信源编码方法的问题就变成了选择假想信道的问题，符号转移概率P(vj/ui)就对应信道转移概率。,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,13,信息率失真函数R(D)物理意义 1R(D)是信源给定的情况下, 在可容忍的失真度内再现 信源消息所必须获得的最小平均信息量 。 2R(D)是反映给定信源可压缩的程度。 3R(D)求出后 , 就与选择的试验信道无关 , 而只是信源 特性的参量 , 不同的信源 , 其R(D)是不同的。,此时的信道转移概率pij实际上指的是一种限失真信源编码方法。,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,14,下面的例子，进一步说明了信息率失真函数的物理意义。,信源符号表为Aa1,a2.a2n,概率分布为p(ai)=1/2n, i=1,2.,2n。失真函数定义为为：,符号不出差错，失真为0；符号一处差错，失真为1。分析在一定编码条件下的信息压缩度。,由信源概率分布可得：信息熵H(X)=H(1/2n,1/2n,.1/2n )=log 2n bit/符号,一般不失真编码的话，每一个信源符号要用log2n个二进制码元进行编码。,假设我们允许的失真限度D1/2，则允许有一半的符号出错。这时信息率应该会减少。,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,15,如果采用上面的编码方式，则平均失真,右边的信道是个确定信道， pij=0或1，H(Y/X)=0 I(X；Y)=H(Y)-H(X/Y)=H(Y),普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,16,信道输出概率分布为：p1=p2=.pn-1=1/2nan之后编码完全相同，他们共同的概率为：pn=(1+n)/2n，,经压缩编码以后，信源需要传输的信息率由原来的 log2n，压缩到也就是说，信息率压缩了所付出的代价是容忍了1/2的平均失真。,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,17,如果选取压缩更为有利的编码方案，压缩的效果可能更好。但一旦达到最小互信息这个极限值，就是R(D）的数值(此处D12)。 如果超过这个极限值，那么失真就要超过失真限度。 如果需要压缩的信息率更大，则可容忍的平均失真就要更大。,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,18,1、D允许试验信道,平均失真由信源分布P(ui)、假想信道的转移概率P(vj/ui)和失真函数d(ui，vj)决定，若P(ui)和d(ui，vj)已定，则可给出满足U下式条件的所有转移概率分布Pij，它们构成了一个信道集合BD称为D允许试验信道。,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,19,2、信息率失真函数R(D),由于互信息取决于信源分布和信道转移概率分布,当P(ui)一定时，互信息I是关于P(vj/ui) 的U型凸函数，存在极小值。因而在上述允许信道PD中，可以寻找一种信道Pij，使给定的信源P(ui)经过此信道传输后，互信息I(U；V)达到最小。该最小的互信息就称为信息率失真函数R(D)，即,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,20,对于离散无记忆信源，R(D)函数可写成,P(ui)，i1，2，r 是信源符号概率分布； P(vj/ui)，i1，2，r，j1，2，s 是转移概率分布； P(vj)，j1，2，s 是接收端收到符号概率分布。,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,21,例 设信源的符号表为Aa1，a2，a2n，概率分布为p(ai)1/2n，i1，2，2n，失真函数规定为 即符号不发生差错时失真为0，一旦出错，失真为1，试研究在一定编码条件下信息压缩的程度。,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,22,两种理论的对比,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,23,信息率失真理论：条件概率不是实际的信道，是为了求R的最小值而引入的假想的可变试验信道。这些试验信道代表的是不同的有失真信源编码或者信源压缩的方式。3.改变试验信道，求平均互信息的最小值，实际上选择一种合适的编码方式，使得信息传输率R最小。4.这个极小值R（D）是在信源给定的条件下，接收端以满足失真要求而在现信源消息所需要的最少的平均信息量；是信息压缩的最小值。备注：平均互信息是信道传递概率P(v|u)的U形函数，具有最小值。,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,24,1.信道固定: 输入信号平均功率受限的条件下，选择一种试验信源，使得信息传输率R最大。2. 研究信道容量C:是为了解决在已知信道中传送的最大信息量。3.信道编码涉及的问题：为了充分利用已给信道，使传输的信息传输率最大而错误概率任意小. 4。研究信息率失真函数：解决在已知信源和允许失真度D的条件下，使用户需要传输的信息传输率最小。即:在D一定的前提下，用尽可能少的符号来传输信息，使得信源的消息尽可能快的传输出去。提高通信的有效性。,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,25,信息率失真函数的性质,R(D)函数的定义域 Dmin和R(Dmin) Dmin0 对于离散信源： 对于连续信源 ：,减函数,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,26,Dmin的推导： 平均失真度 是一个非负的实数，因此，它的下限应该是0。,当ui固定，对于不同的vj，其失真不同。但是每一行必定有一个最小值，或者若干个最小值。 选择试验信道，,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,27,带入最小失真的函数：,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,28,最小失真Dmin能否达到零？,只有当失真矩阵中，每行至少有一个0存在时，Dmin才可能为0。此时，表示不允许失真存在，要求无失真传输，R（Dmin=0）=H（U）,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,29,R（Dmin=0）=H（U）？如何保证,只有当失真矩阵每行至少有一个0，且每列最多有一个0时，上式才成立。否则， R（Dmin=0）H（U）,表示信源中有些符号可以压缩，合并，并且不引入失真。,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,30,举例7.4：U:0,1, V:0,1,2,满足最小允许失真的试验信道矩阵为：,此时，为无损无躁试验信道，I（X；Y）=H（U） R（Dmin=0）=H（U）,集合BD中只有这一个试验信道。,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,31,举例：7.5,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,32,说明信源符号集合可以压缩，将u1和u2压缩成一个信源符号，并不引入失真。压缩有的信息传输率R减小。所以，R（0）H(U),普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,33,(2) Dmax和R(Dmax),选择所有满足R(D)0中D的最小值，定义为R(D)定义域的上限Dmax，即,因此可以得到R(D)的定义域为,减函数,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,34,Dmax的推导：R(D)0就是I(U;V)0，这时试验信道输入与输出是互相独立的，所以条件概率p(vj/ui)与ui无关。即,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,35,求出满足条件 的D中的最小值 ，即,此时平均失真为,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,36,从上式观察可得：在j=1，s中，可找到 值最小的j，当该j对应的P(vj)1，而其余P(vj)为零时，上式右边达到最小，这时上式可简化成,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,37,解：当Dmin0时，R(Dmin)H(U)H(1/3，2/3)0.91比特/符号，这时信源编码器无失真，所以该编码器的转移概率为,例 设输入输出符号表为UV0，1，输入概率分布P(u)=1/3，2/3，失真矩阵为,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,38,当R(Dmax)0时,此时输出符号概率P(v1)0，P(v2)1， 所以这时的编码器的转移概率为,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,39,2、R(D)函数的下凸性和连续性,3、R(D)函数的单调递减性 容许的失真度越大，所要求的信息率越小。反之亦然。,信息率失真曲线,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,40,综上所述，可以得出如下结论：R(D)是非负的实数，即R(D) 0。其定义域为0Dmax，其值为0H(U)。当DDmax时， R(D) 0。R(D)是关于D的下凸函数，也是关于D的连续函数。R(D)是关于D的严格递减函数。,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,41,由以上三点结论，对一般R(D)曲线的形态可以画出来：,离散信源,连续信源,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,42,离散信源和连续信源的R（D）计算,某些特殊情况下R（D）的表示式为： （1）当d(x,y)=(x-y)2， 时，,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,43,(2)当d(x,y)=|x-y|， 时，,(3)当d(x,y)=(x,y)，p(x=0)=p，p(x=1)=1-p时，R(D)=H(p)H(D),普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,44,这些R（D）可画成三条曲线,图4-5 信息率失真函数R(D),普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,45,例 设输入输出符号表为XY0，1，输入概率分布p(x)=(p，1-p)，0p1/2，失真矩阵为,求信息率失真函数R(D)。,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,46,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,47,保真度准则下的信源编码定理,定理：7.1设R（D）是离散无记忆信源的信息率失真函数，且有有限的失真测度，对于任意的D0或D=0， 以及任意足够长的码长n，则一定存在一种编码C，其码字的个数为：,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,48,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,49,逆定理：,不存在平均失真度为D，而平均信息传输率RR(D)的任何信源编码。对于任意码长为n的信源码C，若码字的个数即：编码后平均每个信源符号的信息传输率R小于信息率失真函数R（D），就不能在保真度准则下在现信源的消息。,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,50,信息一传输定理,若无记忆信源S的信息率失真函数为R（D），离散无记忆信道的信道容量为C，若满足CR(D)，则信源输出的信源序列能在此信道输出段端重现，其失真小于等于D。,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,51,7.8 限失真信源编码定理的实际意义,R(D)是允许失真D的情况下的信息压缩的下限值。当信源给定后，无失真信源压缩的极限值是H（S）；有失真信源压缩的极限值市信息率失真函数R（D）。在给定D以后，一般R（D）小于H（S）。,
