限失真信源编码精选课件

2018/6/24,1/49,信息率失真 (Rate-Distortion)函数保真度准则下的信源编码定理,限失真信源编码,2018/6/24,2/49,理论上“消息完全无失真传送”的可实现性信道编码定理：无论何种信道，只要信息率R=(Klog2m)/L小于信道容量C，总能找到一种编码，使在信道上能以任意小的错误概率和任意接近于C的传输率来传送信息。反之，若RC，则传输总要失真。实际上“消息完全无失真传送”的不可实现性无失真传送的条件为RH(x)，而实际的信源常常是连续的，H(x)为无穷大，于是要求R为无穷大，而信道编码定理要求RC，必然会失真。,2018/6/24,3/49,有些失真没有必要完全消除（限失真信源编码）实际应用中，人们一般并不要求获得完全无失真的消息，通常只要求近似地再现原始消息，即允许一定的失真存在。打电话：即使语音信号有一些失真，接电话的人也能听懂。放电影：理论上需要无穷多幅静态画面，由于人眼的“视觉暂留性”，实际上只要每秒放映24幅静态画面。,信息率失真理论-信息率失真函数香农定义了信息率失真函数R(D)。定理指出：在允许一定失真度D的情况下，信源输出的信息率可压缩到的极限最小值为R(D)。,2018/6/24,4/49,在允许一定失真程度的条件下，怎样用尽可能少的信道符号来表达信源的信息，也就是信源熵所能压缩的极限或者说编码后信源输出的信息率压缩的极限值，这就是限失真信源编码要讨论的问题。限失真信源编码也称保真度准则下的信源编码、熵压缩编码或者称信息率失真理论，它是量化、数模转换、频带压缩和数据压缩的理论基础。无失真的冗余度压缩编码主要是针对离散信源。限失真的熵压缩编码主要是针对连续信源。,2018/6/24,5/49,信息率失真函数是I(X;Y)的极小值I(X;Y)是P(X)和P(Y/X)的二元函数；固定p(xi) ，变更p(yj /xi)来求平均互信息的值。由于I(X;Y)是p(yj /xi)的下凸函数，所求的极值一定是极小值。但若X和Y相互统计独立(p(yj /xi)= p(yj )， 求出的I(X;Y)极小值为0，因为I(X;Y)是非负的，0必为极小值，但是这样求出的极小值0毫无意义(对应完全失真)。引入一个失真函数，计算在一定失真的情况下I(X;Y)的极小值才有意义。,2018/6/24,6/49,失真度设离散无记忆信源为,对每一对(xi,yj)，指定一个非负函数d(xi,yj)0 i=1,2,n j=1,2,m称d(xi,yj)为单个符号的失真度/失真函数。它表示信源发出一个符号xi，在接收端再现yj所引起的误差或失真。,2018/6/24,7/49,均方失真： 绝对失真： 相对失真： 误码失真：,失真函数的表达,2018/6/24,8/49,常用的失真函数,失真函数是根据人们的实际需要，人为规定的。常用的失真函数有 (1)绝对失真：汉明失真汉明失真矩阵D通常为方阵，且对角线上的元素为0。即 (2)均方失真：平方误差失真函数如果信源符号代表信源输出信号的幅度值，则上式意味着较大的幅度差值要比较小的幅度差值引起的失真更为严重，严重程度用平方表示。,2018/6/24,9/49,失真矩阵失真度表示成矩阵的形式，称D为失真矩阵。它是nm阶矩阵。d(x,y)0,2018/6/24,10/49,平均失真度平均失真度：平均失真度为失真度的数学期望,2018/6/24,11/49,平均失真度意义 是信源统计特性p(xi) 、信道统计特性p(yj/xi )和失真度d(xi,yj)的函数 。当p(xi)，p(yj/xi )和d(xi,yj)给定后，平均失真度就是一个确定的量。如果p(xi)和d(xi,yj)一定， 就只是信道统计特性的函数。信道传递概率不同，平均失真度随之改变。保真度准则保真度准则：规定平均失真度 不能超过某一限定的上限值D，即 ，则D就是允许失真的上界。该式称为保真度准则。将保真度准则作为信道传递概率的约束条件，再求I(X;Y)的最小值就有实际意义。,2018/6/24,12/49,试验信道当固定信源（ P(X)已知），符号失真度也给定时，选择信道使 。凡满足要求的信道称为D失真许可的试验信道所有试验信道构成的集合用PD来表示，即,2018/6/24,13/49,信息率失真函数在信源和失真度给定以后，PD是满足保真度准则 的试验信道集合，由于I(X;Y)是信道传递概率p(yj /xi)的下凸函数，所以在PD中一定可以找到某个试验信道，使I(X;Y)达到最小，即 R(D)称为信息率失真函数。在信源给定以后，总希望在允许一定失真的情况下，传送信源所需要的信息率越小越好。从接收端来看，就是在满足保真度准则 的条件下，寻找再现信源消息必须的最低平均信息量，即平均互信息的最小值。,2018/6/24,14/49,研究率失真函数的意义是为了解决在已知信源和允许失真度D的条件下，使信源必须传送给信宿的信息率最小。即用尽可能少的码符号尽快地传送尽可能多的信源消息，以提高通信的有效性。这是信源编码问题。,2018/6/24,15/49,信息率失真函数的性质,率失真函数的定义域率失真函数的定义域问题就是在信源和失真函数已知的情况下，讨论允许平均失真度D的最小和最大值问题。D的选取必须根据固定信源X的统计特性P(X)和选定的失真函数d(xi , yj)，在平均失真度 的可能取值范围内。,2018/6/24,16/49,最小平均失真度Dmin 是非负函数d(xi , yj)的数学期望，也是一个非负函数，显然其下限为0。因此允许平均失真度D的下限也必然是0，这就是不允许有任何失真的情况。允许平均失真度D能否达到其下限值0，与单个符号的失真函数有关。信源最小平均失真度Dmin ：在失真矩阵的每一行找出一个最小的d(xi , yj) ，对所有这些不同的最小值求数学期望，就是信源的最小平均失真度。,2018/6/24,17/49,信源最大平均失真度Dmax信源最大平均失真度Dmax ：容忍的失真越大，所需的信息率就越小 。当R(D)等于0时，对应的平均失真D最大，也就是函数R(D)定义域的上界值Dmax 。信息率失真函数是平均互信息的极小值：当R(D) =0时，即平均互信息的极小值等于0；当DDmax时，在接收端收不到信源发送的任何信息，信源符号的信息率可以压缩至0。,2018/6/24,18/49,结 论：R(D)的定义域为(Dmin, Dmax)；一般情况Dmin =0， R(Dmin)=H(X)；当DDmax时，R(D)=0；当DminDDmax时，0R(D)H(X)。率失真函数函数R(D)具有凸状性，它在定义域DminDDmax时：在D=Dmax处，除某些特例外，S将从某一个负值跳到0，S在此点不连续。在D的定义域0, Dmax内，除某些特例外，S将是D的连续函数。,2018/6/24,31/49,(1) 二元离散信源的率失真函数 设二元信源 计算率失真函数R(D),例：二元离散信源的信息率失真函数,2018/6/24,32/49,先求出Dmax,2018/6/24,33/49,第一步：求i，由式(4.2.12)有,2018/6/24,34/49,第二步：求p(yj)，由式(4.2.11)有,2018/6/24,35/49,第三步：求p(yj/xi)，由式(4.2.10)有,2018/6/24,36/49,第四步：求D(S)，将上述结果代入式(4.2.14)有,2018/6/24,37/49,第五步：求率失真函数R(S)，将上述结果代入式(4.2.15)有,2018/6/24,38/49,对于这种简单信源，可从D(S)解出S与D的显式表达式为：,将S代入上面的i，p(yj)和p(yj/xi)和R(S)得：,2018/6/24,39/49,以及,2018/6/24,40/49,第六步：通过以上步骤计算出来的R(D)和S(D)如图4.2.2 。,(2) 说明：若=1，把d(xi , yj)当成了误码，即X和Y不一致时，认为错了一个码元，所以d(xi , yj)的数学期望就是平均误码率。能容忍的失真等效于能容忍的误码率。,2018/6/24,41/49,R(D)不仅与D有关，还与p有关。概率分布不同， R(D)曲线就不一样。当p=0.25时，如果能容忍的误码率也是0.25，不用传送信息便可达到R=0，这就是R(Dmax) =0的含义。,2018/6/24,42/49,当D相同时，信源越趋于等概率分布， R(D)就越大。由最大离散熵定理，信源越趋于等概率分布，其熵越大，即不确定性越大，要去除这不确定性所需的信息传输率就越大，而R(D)正是去除信源不确定性所必须的信息传输率。,2018/6/24,43/49,关于S(D)S(D)与p无直接关系，S(D)曲线只有一条，p=0.5和p=0.25都可以用，但它们的定义域不同；p=0.25时定义域是D=00.25，即到A点为止，此时 Smax