信息论与编码-曹雪虹-PPT-第4章..ppt

1、第4章信息率失真函数,本章主要讨论在信源允许一定失真情况下所需的最少信息率，从分析失真函数、平均失真出发，求出信息率失真函数R（D） 。 4.1 平均失真和信息率失真函数 4.2 离散信源和连续信源的R（D）计算,(1) “消息完全无失真传送”的可实现性 信道编码定理：无论何种信道，只要信息率R小于信道容量C，总能找到一种编码，使在信道上能以任意小的错误概率和任意接近于C的传输率来传送信息。反之，若RC，则传输总要失真。 完全无失真传送不可实现： 实际的信源常常是连续的，信息率无限大，要无失真传送要求信息率R为无穷大； 实际信道带宽是有限的，所以信道容量受限制。要想无失真传输，所需的信息率大大

2、超过信道容量RC。,4.1.1 引 言,4.1 基本概念,有失真信源编码的意义,(2) 实际中允许一定程度的失真 技术发展的需要 随着科学技术的发展，数字系统应用得越来越广泛，这就需要传送、存储和处理大量的数据。为了提高传输和处理效率，往往需要对数据压缩，这样也会带来一定的信息损失。 人类社会已进入信息时代，信息爆炸的结果要求人们解决如何对浩如烟海的数据有效的压缩，减少数据的存储容量(如各种数据库、电子出版物、多媒体娱乐)、传输时间(如数据通信和遥测)、或占有带宽(如多媒体通信、数字音频广播、高清晰度电视)，要想方设法压缩给定消息 集合占用的空间域、时间域和频率域资源。,4.1.1 引 言,4

3、.1 基本概念,实际生活中的需要 实际生活中，人们一般并不要求获得完全无失真的消息，通常只要求近似地再现原始消息，即允许一定的失真存在。 例如打电话：即使语音信号有一些失真，接电话的人也能听懂。人耳接收信号的带宽和分辨率是有限的。 放电影：理论上需要无穷多幅静态画面，由于人眼的“视觉暂留性”，实际上只要每秒放映24幅静态画面。 有些失真没有必要完全消除。,4.1.1 引 言,4.1 基本概念,限失真编码：信源编码经过译码后能保留应用要求的信息，允许信源有一定的失真。 那么在允许一定程度失真的条件下，能够把信源信息压缩到什么程度，也就是，允许一定程度失真的条件下，如何能快速的传输信息，这就是本章

4、所要讨论的问题。,4.1 平均失真和信息率失真函数,4.1.1 失真函数 4.1.2 平均失真 4.1.3 信息率失真函数R(D) 4.1.4 信息率失真函数的性质,4.1 平均失真和信息率失真函数,在实际问题中，信号有一定的失真是可以容忍的。但是当失真大于某一限度后，信息质量将被严重损伤，甚至丧失其实用价值。要规定失真限度，必须先有一个定量的失真测度。为此可引入失真函数。,1、失真函数,信源,信源编码,信道编码,信道,信道译码,信源译码,信宿,干扰,根据信道编码定理，我们可以把信道编码、信道和信道解码等价成是一个没有任何干扰的广义信道，这样收信者收到消息后，所产生的失真只是由信源编码带来的。

5、我们也可以把信源编码和信源译码等价成一个信道。,4.1.1 失真函数,我们称此信道为试验信道。,现在我们要研究在给定允许失真的条件下，是否可以设计一种信源编码使信息传输率为最低。为此，我们首先讨论失真的测度。,4.1.1 失真函数,失真函数定义 信源 经过信源编码后输出 对于每一对( xi , yj ) , 指定一个非负函数 d ( xi , yj ) 0 i = 1 , 2 , , n j = 1 , 2 , , m 称 d ( xi , yj ) 为单个符号的失真函数. 表示信源发出符号 xi , 接收端再现 yj 所引起的误差或失真. d越小表示失真越小： d ( xi , yj ) =

6、 0 无失真 , d ( xi , yj ) 0 有失真.,常用的失真函数 1平方误差失真函数 d ( xi , yj ) = (xi - yj )2 2绝对误差失真函数 d ( xi , yj ) = | xi - yj | 3相对误差失真函数 d ( xi , yj ) = | xi - yj |/ | xi | 4误码失真函数 失真函数1,2,3用于连续信源 , 失真函数4用 于离散信源 , 失真函数4也称Hanmming失真函数 失真矩阵d n m 矩阵,例1：,失真矩阵为：,这种失真成为汉明失真,在二元情况下：,例2：删除信源,对于二元删除信源n=2,m=3,失真函数的定义可以推广到

7、序列编码情况，如果假定离散信源输出符号序列X=(X1X2XlXL)，其中L长符号序列样值xi(xi1xi2xilxiL)，经信源编码后，输出符号序列Y=(Y 1Y 2Y lY L)，其中L长符号序列样值yj(yj1yj2yjlyjL)，则失真函数定义为：,其中d(xil，yjl)是信源输出L长符号样值xi中的第l个符号xil时，编码输出L长符号样值yj中的第l个符号yjl的失真函数。,4.1.2 平均失真,由于xi和yj都是随机变量，所以失真函数d(xi，yj)也是随机变量，限失真时的失真值，只能用它的数学期望或统计平均值，因此将失真函数的数学期望称为平均失真，记为,对于连续随机变量同样可以定

8、义平均失真,对于L长序列编码情况，平均失真为,受信道容量的限制 , 实际应用中必须对信源进行压缩 , 应 1使其压缩后的信息传输率小于信道容量; 2保证压缩所引入的平均失真 不超过预先给定的允许 失真度D; 3在满足 D的前提下 , 使编码后的信息率尽可能小. 不等式 D 称为保真度准则,4.1.3 信息率失真函数R(D),4.1.3 信息率失真函数R(D),给出一个失真的限制值D，在满足平均失真 D的条件下，选择一种编码方法使信息率R尽可能小。信息率R就是所需输出的有关信源X的信息量。,试验信道 1有失真的信源编码器视作有干扰的信道(假想信道) 2当信源已知 (即P(X)已知)时 , 单个符

9、号的失真度给定, 选择一类假想信道 , 使得 D ,这类假想信道称为 D 失真允许信道 , 或 D 失真允许试验信道. 记为 PD= p( yi | xj ): D ; i=1,2, ,n ; j=1,2,m p( yi | xj )为信道的传递概率。 凡满足保真度准则的这些试验信道称为D失真许可的试验信道。把所有D失真许可的试验信道组成一个集合PD。,（1）D允许试验信道,（2）信息率失真函数R(D),由于互信息取决于信源分布和信道转移概率分布，当p(xi)一定时，互信息I是关于p(yj/xi) 的U型凸函数，存在极小值。因而在上述允许信道PD中，可以寻找一种信道pij，使给定的信源p(xi

10、)经过此信道传输后，互信息I(X；Y)达到最小。该最小的互信息就称为信息率失真函数R(D)，即,对于离散无记忆信源，R(D)函数可写成,p(ai)，i1，2，n 是信源符号概率分布； p(bj/ai)，i1，2，n，j1，2，m 是转移概率分布 p(bj)，j1，2，m 是接收端收到符号概率分布。,例4-1-3 设信源的符号表为Aa1，a2，a2n，概率分布为p(ai)1/2n，i1，2，2n，失真函数规定为 即符号不发生差错时失真为0，一旦出错，失真为1，试研究在一定编码条件下信息压缩的程度。,4.1.4 信息率失真函数的性质,R(D)函数的定义域 Dmin和R(Dmin) Dmin0 对于

11、连续信源,(2) Dmax和R(Dmax),选择所有满足R(D)0中D的最小值，定义为R(D)定义域的上限Dmax，即,因此可以得到R(D)的定义域为,Dmax是这样来计算的。R(D)0就是I(X;Y)0，这时试验信道输入与输出是互相独立的，所以条件概率p(yj/xi)与xi无关。即,求出满足条件 的D中的最小值 ，即,此时平均失真为,从上式观察可得：在j=1，m中，可找到 值最小的j，当该j对应的pj1，而其余pj为零时，上式右边达到最小，这时上式可简化成,（ 4.3） 且 （ 4.4） （ 4.5） 证： 1） 定义域下界： 对x的每一取值 ，令对应最小的 条件概率p(bj|ai)为1 ,

12、 其余条件概率为零，就得到Dmin 。,1 R(D)的定义域为,2）定义域上界： R(D)为平均互信息，所以R(D)0。在较大范围内 求极小值一定不大于在所含小范围内求的极小值，所 以D1D2 = R(D1) R(D2)，即R(D)是D的非增函数。 当XY独立时，R(D) I(X;Y)=0，当D继续增加，R(D) 仍然为0。所以，Dmax是使R(D)=0的最小平均失真。当 x,y独立时，p(x,y)=p(x)p(y) ，有 由于 已给定，而且对不同y， 也可能有不同的值。所以，求 ，并使对 应的p(y)=1，其余为0。这样就可使平均失真最小。所 以得到（ 4.5）式。 证毕。,例4.3 设试验

13、信道输入符号 ，概率分别为1/3，1/3，1/3，失真矩阵如下所示，求Dmin和Dmax和相应的试验信道的转移 概率矩阵。 解 = 1 令对应最小 的 ,其它为0。可得对应Dmin 的转移概率矩阵为：,= 5/3 上式中第2项最小，所以令 ， 。可得对应Dmax 的转移概率矩阵为：,例4-1-4 设输入输出符号表为XY0，1，输入概率分布p(x)=1/3，2/3，失真矩阵为,解： 当Dmin0时，R(Dmin)H(X)H(1/3，2/3)0.91比特/符号，这时信源编码器无失真，所以该编码器的转移概率为,当R(Dmax)0时,此时输出符号概率p(b1)0，p(b2)1， 所以这时的编码器的转移

14、概率为,2R(D) 是关于D的下凸函数 设D1,D2为任意两个平均失真， ，那么 （ 4.6） 证 当信源分布给定后， 可以看成试验信道转移概率 的函数，即 ， ，且有,令 ， ，那么 ， = 证毕。,3、R(D)函数的单调递减性 容许的失真度越大，所要求的信息率越小。反之亦然。,综上所述，可以得出如下结论： R(D)是非负的实数，即R(D) 0。其定义域为0Dmax，其值为0H(X)。当DDmax时， R(D) 0。 R(D)是关于D的下凸函数，因而也是关于D的连续函数。 R(D)是关于D的严格递减函数。,由以上三点结论，对一般R(D)曲线的形态可以画出来,由以上分析可见，当规定了允许的失真

15、D，又找到了适当的失真函数di j ，就可以找到该失真条件下的最小信息率R (D)，这个最小信息率是一个极限值。在满足保真度准则的前提下，用不同方法进行数据压缩时，R(D)函数就是压缩程度的衡量，由R (D)可知是否还有压缩的潜力，潜力有多大，因此对它的研究很有实际意义。,例：二元信源和离散对称信源的R(D)函数,1、二元对称信源的R(D)函数,设二元信源U=0,1，其分布概率 ，,而接收变量v=0,1，设汉明失真矩阵为：,因而最小失真度 。并能找到满足该最小失真的试验信道，且是一个无噪无损信道，其信道矩阵为：,要达到最大允许失真，唯一确定,此时，可计算得信息传输率,一般情况下，当 时，,可以

16、计算得：二元信源得信息率失真函数为,例：,在汉明失真条件下，,对于离散对称信源，在汉明失真条件下：,R(D)与C的比较 信道容量定义为。它表示信道的最大传输能力，反映的是信道本身的特性，应该与信源无关。但平均互信息量与信源的特性有关，为排除信源特性对信道容量的影响，在所有的信源中以那个能够使平均互信息量达到最大的信源为参考，从而使信道容量仅与信道特性有关，信道不同，C亦不同。 信息率失真函数。它也应该与信道无关。为此在所有信道中以能够使平均互信息量达到最小的信道为参考，从而使信息率失真函数仅与信源特性有关，信源不同，R(D)亦不同。,引入C和R(D)的目的 引入C, 是为了解决在所用信道中传送

17、的最大信息量到底有多大的问题，它给出了信道可能传输的最大信息量，是无差错传输的上限。引入C能够为信道编码服务，或者说为提高通信的可靠性服务。 引入R(D)，是为了解决在允许失真度D条件下，信源编码到底能压缩到什么程度的问题，它给出了保真度条件下信源信息率可被压缩的最低限度，可见引入它能够为信源的压缩编码服务，或者说是为提高通信的有效性服务,4.2 离散信源和连续信源的R（D）计算,某些特殊情况下R（D）的表示式为： （1）当d(x,y)=(x-y)2， 时，,(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

18、)H(D),这些R（D）可画成图4-5的三条曲线,0 Dmax D,R(D) H,(3),(1),(2),图4-5 信息率失真函数R(D),信息率失真函数R(D)的计算 已给定信源概率P(X)和失真函数d ( xi , yj ) ,求信息率失真函数R(D)的问题 , 可以归结为在约束条件保真度准则 D 下, 求极小值的问题 .,离散信源信息率失真函数的计算,设试验信道的输入X，符号集A=a1,an，对应的概率分布为p1,pn；信道的输出 Y，符号集B=b1,bm，对应的概率分布为q1,qm，失真矩阵为 试验信道转移概率矩阵为 。 并且， 。,求解R(D)，实际上是求有约束极值 （4.2.1） 由于，使R最小的pij总是在PD的边界上，所以在求极值时，平均失真约束条件的不等式取等号，即 （4.2.2） 从（4.2.1）式可知，约束条件有n+1个，未知数 pij有mn个。下面用拉格朗日乘子法求有约束极值。,设s, i (i=1,n)为常数，求下式极值（以e为底）： （ ） 令 ，得 （4.2.3） 其中 ，,所以 （4.2.4） 当 时，有 （4.2.5） 结合（4.2.4）与（4.2.5）式，得 ， j=1,m （4.2.6） （4.2.6）式含m个方程，m个未知数qj (j=1,m)，而s为参 量，一般能解。,将（4.2.3）代入（4.2.2）（4.2.