第五章 信息率失真函数.ppt

1、第五章离散信源的限失真信源编码,5.1 引言,5.3 信息率失真函数的性质,5.4 信息率失真函数的计算,5.2平均失真和信息率失真函数,5.1引言,冗余度压缩编码 对信源输出的信息进行有效的表示。 信道编码 增加信息的冗余度，以对抗信道中的传输错误。 以上两个方向的努力都是为了保证信息的可靠、 无误传输，是保熵的。 问题是： 是否所有的信源都要进行保熵的编码呢？,音频压缩,森林的鸟鸣： 原始音频：352Kps=44KHz8Bit 128kbps MP3格式压缩 一段著名的话： 原始音频：352Kps=44KHz8Bit 128kbps MP3格式压缩,图像压缩,文件大小： 232K,图像压缩

2、,文件大小： 138K,图像压缩,文件大小： 138K,图像压缩,文件大小： 24K,问题的提出,是否需要完全表示信源的信息？ 自然界中很多信源是不需要进行保熵的压缩和传输的 对于连续信源，需要使用无限大的码率才能够进行可靠的传输 因此，不可能也不必要完全表示信源信息 在给定的信息速率条件下，如何可以获得信息的最优表示？ 什么是最好？ 失真最小就是最好吗？ 定义失真的度量,本章讨论主要问题： 在允许一定失真存在的条件下，能够将信源信息压缩到什么程度，即最少需要多少比特信息才能够描述信源，如何能够快速的传输信息。 信息率失真理论的基本概念： 在允许传输消息出现一定的失真条件下，传输该消息所需的信

3、息率(最小值)将会比不允许失真时小，并且允许的失真度越大，则信息率(最小值)允许减小的程度就越大。,5.2平均失真和信息率失真函数,实际问题中，信号有一定的失真可以容忍。当失真大于某一限度后，信息质量将被严重损伤，丧失其实用价值。因此要规定失真限度，有一个定量的失真测度失真函数。,设信源输出样值：xi, xia1,an, 经过信源编码器，输出样值yj, yjb1,bm. 如果xi=yj，没有失真； 如果xiyj，产生失真。,失真函数（失真测度）,失真大小用失真函数d(xi,yj)表示 失真函数又称为失真度。为简化起见，d(xi,yj)简写成dij，,d(xi,yj)=,0,xi=yj,xiyj

4、,ij时，x和y的消息符号都是ai，收发之间没有失真，dij 0 ij时，发出符号ai，收到bj，传输时出现失真，dij 0 一般dij值的大小表示失真的程度， 表征了接收消息yj与发送消息xi之间的定量失真度。,失真函数（失真测度）,失真函数类型,均方失真,d(xi,yj)=(xi-yj)2,绝对失真,d(xi,yj)=|xi-yj|,相对失真,d(xi,yj)=|xi-yj|/|xi|,误码失真,d(xi,yj)=(xi-yj)=,0,1,xi=yj,其他,用于连续信源,失真函数（失真测度）,失真函数性质：,若X和Y集合都由N个不同符号构成的，那么可组成N2个不同的(i,j)对，相对应的失

5、真函数也有N2个 若X和Y集合分别由N个和M个不同符号构成的，那么可组成N*M个不同的(i,j)对，相对应的失真函数也有N*M个 dij表示方法有两种，一是失真矩阵D，二是消息传输图,失真函数（失真测度）,将所有失真函数排列起来，得到失真矩阵D,D,d(a1,b1),d(a1,b2),d(a1,bm),d(a2,b1),d(an,b1),d(an,b2),d(a2,b2),d(a2,bm),d(an,bm),失真矩阵,消息传输图,例：已知XYa1， a2，且有d11d220，d12d211，用两种方法表示失真函数 解：失真矩阵D为： 消息传输图为：,例：已知X=0,1,2,3,4,5，Y=0,

6、1,2，X和Y集合符号之间的失真函数值分别为d00=d11=d22=0，d30=d31=d41=d42=d50=d52=1，d01= d02 = d10 =d12=d20=d21=2，d32=d40=d51=3。这些失真函数值的由来可形象化地用正六角形表示，其中每条条边相当于失真函数值为1。,X,Y,0,2,0,1,2,3,4,5,0,0,0,1,3,2,2,2,2,2,2,1,1,1,1,1,1,3,3,汉明失真,平方误差失真函数,为了估计全体信源发出的消息符号与接收符号之间的失真程度,需要计算各个失真函数的统计平均值(数学期望)。平均失真函数定义为：,平均失真函数,若X和Y都是n维矢量消息

7、的集合，也可以定义两个矢量消息之间的失真函数为： 其平均失真函数为： 该式中 是n维矢量的第r个分量上的平均失真函数,平均失真函数,当给定信源的各符号概率分布时，若要求平均失真函数不超过某个给定的值D(即D为允许失真度)，这就需要对假想的试验信道的传输概率P(yj|xi)施加一定的限制 先把P(yj|xi)集合的各种可能值代入式,信源概率,转移概率,失真函数,求出各个 ，再根据 ，把P(yj|xi)分成两类: 的一类用PD表示，PD是能使实际失真在允许失真度范围内的那些假想试验信道的P(yj|xi) 的一类称为禁用集合,保真度（失真度）准则： 若平均失真函数不大于所允许的失真度D，即 称为保真

8、度准则。,信息率失真函数R(D),把有失真的信源编码器看作有干扰的假想信道，用分析信道传输的方法研究限失真信源编码问题,平均失真由信源分布，转移概率，失真函数决定，如果信源分布和失真函数一定，则满足失真条件的所有转移概率分布构成一个信道集合：,PD为假想信道，允许试验信道,信息率失真函数R(D)定义： 在给定信源消息的概率分布P(xi)及平均失真函数允许值D的条件下，传输这些信源消息，并使失真程度在允许范围内时，所需要的信息率的最小值，其定义式为： R(D)又称作率失真函数,PD满足保真度准则的试验信道的集合。,平均互信息量的凸函数性 (1) I(X;Y) 是信源概率分布P(X) 的上凸函数

9、（最大值）信道容量 (2) I(X;Y) 是信道转移概率P(Y/X) 的下凸函数 （最小值）率失真函数,回顾：,二进制对称信道 q不变时, I(X;Y)为上凸曲线。p=0.5时有最大值 p不变时, I(X;Y)为下凸曲线。q=0.5时有最小值,回顾：,由于平均互信息量I(X;Y)是p(yj|xi)的下凸函数，所以 在PD集合内，极小值存在。该极小值就是在保真度 准则的条件下，信源必须传输的最小平均互信息量.,离散无记忆信源,N维信源矢量的信息率失真函数RN(D)为,X信源的一个输出序列； Y信宿的一个接收序列； N维信源矢量的平均失真度。,信息率失真函数R(D) 的等效定义,称D(R)为失真信

10、息率函数，是R(D)的逆函数，它是求在允许最大速率情况下的最小失真D,给定速率,由定义，R(D)函数是在限定失真为最大允许失真D时信源最小信息传输速率，它是通过改变试验信道特性来达到的。所以R(D)是表示不同D值时对应的理论上最小信息速率值。,说明： （1）在研究信息率失真函数R(D)时，引用的信道传输概率 p(yj|xi)并没有实际信道的含义，是为了求平均互信息量极小值而引用的假想可变试验信道。即不同的试验信道特性，并求解出不同的信息率失真R(D)函数，它与理论上最佳的R(D)之间存在着差异，它反映了不同方式信源编码性能的优劣，这也正是R(D)函数的理论价值所在。,（2）连续信源，无失真是毫

11、无意义的，这时R(D)函数具有更大的价值。实际上，这些信道仅仅反映不同的有失真信源编码或信源压缩编码。因此，改变试验信道求平均互信息量的极小值，实质上是选择一种信源编码方法使信息传输速率最小。,（3）研究信息率失真函数是为了解决在已知信源和允许失真度的条件下，如何使信源传送给信宿的信息量最小的问题，也就是说在一定失真度D条件下，尽可能用最少的码符号来传送信源消息，使信源消息尽快地传送出去，以提高通信的有效性。,（4）信息率失真函数的物理意义：,对于给定信源，在平均失真不超过失真限度D的条件下，信息率容许压缩的最小值为R(D)。,限失真信源编码定理(香农第三定理),限失真信源的信息率用R(D)描

12、述，所采用的信道的信道容量为C时，若CR(D)时，则限失真信源的有效性编码存在；反之，若CR(D)时，则限失真信源的有效性编码就不存在,信源编码器的目的： 使编码后所需的信息传输率R尽量小,给出一个失真的限制值D，在满足保真度准则条件下，选择一种编码方法，使信息率R尽可能小,例：若有一个离散、等概率单消息（或无记忆）二元信源：,且采用汉明距离作为失真度量标准：即,有一具体信源编码方案为：N个码元中允许错一个码元，实现时N个码元仅送N-1个，剩下一个不送，在接收端用随机方式决定（为掷硬币方式）。,阴影范围表示实际信源编码方案与理论值间的差距，我们完全可以找到更好，即更靠近理论值，缩小阴影范围的信

13、源编码，这就是工程界寻找好的信源编码的方向和任务。,二元信源的理论信息率失真函数,二元信源的实际信息率失真函数,例：设信源具有一百个以等概率出现的符号a1， a2， a99，a100，并以每秒发出一个符号的速率从信源输出。试求在允许失真度D0.1条件下，传输这些消息所需要的最小信息率。,除a1， a2， a89，a90对应位置上的元素为0外，其余元素为1或（假想试验信道传输概率P(yj|xi)为零时，所对应的dij为无限大）,该失真信源的组合方案的平均失真函数为：,上式中： X1Y1a1， a2， a89，a90，属于不失真的符号集合，对应dij0，其中i,j1，2，90 X2a91， a10

14、0，Y2a90，属于失真集合，对应dij1，其中i91，91，100，j90,据题意，P(xi)1/100（i1，2，100） 所以得平均失真函数： 可见，这样设想的失真信源的组合方案能满足对失真度的要求。,该试验信道为无噪有损信道，即H(Y|X)=0,所以 R=I(X;Y)=H(Y)-H(Y|X)=H(Y) 在试验信道的输出端Y，a1， a2， a89的出现概率仍为1/100,而a90的出现概率P(a90)11/100，可知相应的信息传输速率为：,比较 R与无失真传输条件下的信息率R ,可知在D0.1的条件下，所需信息率减小了6.6446.2640.38 bit/s。 同理，在D0.5的条件

15、下(假定后50个符号均产生失真，这后50个符号均用a50来代替)信息率R”为：,与无失真传输条件下的信息率R想比较减小 6.6443.7512.893 bit/s。,信道容量与信息率失真函数的比较,(1) 求极值问题 平均互信息I(X;Y)是信源概率分布p(xi)(i=1,2,n)或概率密度函数p(x)的上凸函数。根据上凸函数定义，如果I(X;Y)在定义域内对p(xi)或p(x)的极值存在，则该极值一定是极大值。信道容量就是在固定信道情况下，求平均互信息极大值的问题，即 I(X;Y)又是信道转移概率分布p(yj/xi)(i=1,2,n;j=1,2,m)或条件概率密度函数p(y/x)的下凸函数，

16、因此在满足保真度准则条件下，I(X;Y)对p(yj/xi)或p(y/x)的条件极值若存在，则一定是极小值。信息率失真函数就是在试验信道（满足保真度准则的信道）中寻找平均互信息极小值的问题，即,信道容量与信息率失真函数的比较,信道容量与信息率失真函数的比较,(2)特性 信道容量C一旦求出后，就只与信道转移概率p(yj/xi)或条件概率密度p(y/x)有关，反映信道特性，与信源特性无关；由于平均互信息与信源的特性有关，为了排除信源特性对信道容量的影响，采用的做法是在所有的信源中以那个能够使平均互信息达到最大的信源为参考，从而使信道容量仅与信道特性有关，信道不同，C亦不同。,信息率失真函数R(D)一

17、旦求出后，就只与信源概率分布p(xi)或概率密度函数p(x)有关，反映信源特性，与信道特性无关。由于平均互信息与信道的特性有关，为了排除信道特性对信息率失真函数的影响，采用的做法是在所有的信道中以那个能使平均互信息达到最小的信道为参考，从而使信息率失真函数仅仅与信源特性有关，信源不同，R(D)亦不同。,(3) 解决的问题 信道容量是为了解决通信的可靠性问题，是信息传输的理论基础，通过信道编码增加信息的冗余度来实现； 信息率失真函数是为了解决通信的有效性问题，是信源压缩的理论基础，通过信源编码减少信息的冗余度来实现。,5.3 信息率失真函数的性质,1.R(D)函数的定义域,(1) Dmin和R(

18、Dmin),R(Dmin)R(0)=H(X),通常最小允许失真度Dmin为零，在D0条件下，因为不允许失真，所以X和Y集合的各个消息符号都一一对应，这相当于假想的试验信道是无扰离散信道的情况。在这种信道上，有： I(X;Y) H(X) H(Y) 所以，R(0)=H(X)，且R(0)是R(D)的上限值,当给定信源，以及失真矩阵D，信源的最小平均失真度,由上式可以知道，若选择试验信道 ，使对每一个 的求和式 为最小，则总和值达到最小。当 固定某个 ，那么对于不同的 其 不同（即在 失真矩阵D中第i行的元素不同），其中必有最小值 也可能有若干个相同的最小值。于是，可以选择这样的试验 信道，它满足,可

19、见，允许失真度D是否能为零，这与单个符号的失真函数有关， 只有当失真矩阵中每行至少有一个零元素时，信源的平均失真度 才能达到零值，否则，最小平均失真度不等于零。 如果Dmin0，可以适当改变单个符号的失真度，令 使Dmin=0。而对信息率失真函数来说，它只是起了坐标平移作用。 所以可以假设Dmin=0而不失其普遍性。 可见，只有当失真矩阵中每行至少有一个零，并且每一列最多只有 一个零时， 才等于 ；否则小于 。这时表示信源符号集 中有些符号可以压缩、合并，但是没有任何失真。,则可以得信源的最小平均失真度为,例：删除信源X取值【0，1】，Y取值【0，1，2】。而失真矩阵为,求Dmin。,满足最小

20、失真度的试验信道是个无噪无损信道，转移矩阵为,在这个无噪无损信道中，可得,例：,(2) Dmax和R(Dmax),最大允许失真度Dmax的含义是使平均互信息量等于零时所允许的 失真度，即R(Dmax)0 在Dmax条件下，R(Dmax)I(X;Y)0，这意味着X和Y集合之间没有任何信息量的关连，X和Y相互独立 当D Dmax 也有R(D)0,X和Y相互独立的条件下，对各个xi，有P(yj|xi) P(yj)，这时平均失真函数可写成： 因为当 D Dmax时，有R(D)0 所以， Dmax应在满足I(X；Y)0的条件下，取Y集合中所有 值中的最小值，故定义Dmax为：,例：已知信源的消息集合X中包含x0和x1两个消息，并设它们的概率为P(X1)p 1/2，P(X2)1p，而信宿符号集合Y也包含两个符号y0和y1 ，失真矩阵为 ，试求Dmax,解：接收符号y0的平均失真函数 为： 接收符号y1的平均失真函数 为： 因为 p 1/2 所以,满足这个失真度的试验信道为：,2.R(D)函数的下凸性和连续性,3.R(D)函数的单调递减性,物理意义： 容许的失真度越大，所要求的信息率越小。,5.4 信息率失真函数的计算,可见，求解R(D)实质上是求解互信息的条件极值，可采用拉氏乘子