信息论基础第七章PPT讲稿.ppt

《信息论基础第七章PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《信息论基础第七章PPT讲稿.ppt（78页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、信息论基础第七章1第1页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码 第五章我们讨论了无失真信源编码。但是，在很多场合，特别是对于连续信源，因为其绝对熵为无限大，若要求无失真地对其进行传输，则要求信道的信息传输率也为无限大，这是不现实的。因此也就不可能实现完全无失真传输。另一方面，从无失真信源编码定理来考虑，由于要求码字包含的信息量大于等于信源的熵，所以对于连续信源，要用无限多个比特才能完全无失真地来描述。2第2页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码n第16讲7.1 失真测度3第3页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码

2、 即使对于离散信源，由于处理的信息量越来越大，使得信息的存储和传输成本很高，而且在很多场合，过高的信息率也没有必要，例如：由于人耳能够接收的带宽和分辨率是有限的，因此对数字音频传输的时候，就允许有一定的失真，并且对欣赏没有影响。又如对于数字电视，由于人的视觉系统的分辨率有限，并且对低频比较敏感，对高频不太敏感，因此也可以损失部分高频分量，当然要在一定的限度内。等等这些，都决定了限失真信源编码的重要性。4第4页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码在限失真信源编码里，一个重要的问题就是在一定程度的允许一个重要的问题就是在一定程度的允许失真限度内，能把信源信息压缩到什么程

3、度，即最少用多少比失真限度内，能把信源信息压缩到什么程度，即最少用多少比特数才能描述信源特数才能描述信源。这个问题已经被香农解决。香农在1948年的经典论文中已经提到了这个问题，在1959年，香农又在他的一篇论文“保真度准则下的离散信源编码定理”里讨论了这个问题。研究这个问题并做出较大贡献的还有前苏联的柯尔莫郭洛夫（Kolmogorov）以及伯格（T.Berger）等。5第5页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码 信息率失真理论是矢量化、数模转换、频带压缩和数据压缩的理论基础。本章主要介绍信息率失真理论的基本内容，包括信源的失真度和信息率失真函数的定义与性质，离散信

4、源和连续信源的信息率失真函数计算，在此基础上论述保真度准则下的信源编码定理即香农第三编码定理。6第6页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码在实际中，信号有一定的失真是可以容忍的，但当失真大于某一限度后，信息质量将被严重损伤，甚至丧失其实用价值，因此，要规定失真限度，必须对其有一个定量的失真测度P(Yj/xi)XY信道的数学模型信道的数学模型7第7页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码n转移矩阵描述P=(P(yj/xi)nxmP矩阵为一个nm矩阵，其每行元素之和等于1。从这个角度看编码器可以看作一个广义的信道编码器可以看作一个广义的信道，X

5、为信道的输入，Y是信道的输出。与无失真编码不同，这是从输入到输出是一个多对一的映射，它是不可逆的，信源符号与码元符号之间的差异就是编码时引入的失真。8第8页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码7.1.1、失真函数（定量地描述信息失真程度）设某信源输出的随机变量为X，其值集合为 ，经过编码后输出为 ，设 对应 ，如果则认为没有失真。当 时，就产生了失真，失真的大小，用失真函数来衡量。单个符号的失真函数(失真度)的定义为9第9页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码由于输入符号有n个，输出符号有m个，所以共有 个，写成矩阵形式，就是d被称为失真

6、矩阵。10第10页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码例4-1-1 设信源符号 ,编码器的输出符号 ，规定失真函数为：d(0,0)=d(1,1)=0;d(0,1)=d(1,0)=1;d(0,2)=d(1,2)=0.5求失真矩阵d.解：由失真矩阵定义：11第11页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码失真函数 的函数形式可以根据需要适当选取，如平方代价函数、绝对代价函数、均匀代价函数等：平方失真：绝对失真：相对失真：误码(汉明)失真：12第12页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码也可以按其它的标准，如引起的损失、

7、风险、主观感觉上的差别等来定义失真函数。二、平均失真 由于信源X和信宿Y都是随机变量，所以符号失真度函数也是一个随机变量，传输时引起的平均失真应该是符号失真度函数 在信源概率空间和信宿概率空间求平均，即：13第13页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码平均失真是符号失真函数在信源空间和信宿空间平均的结果，是描述某一信源在某一信道传输时失真的大小，是从整体上描述系统的失真情况。14第14页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码三、信源符号序列的失真从上面的单符号失真函数，可以得到信源符号序列的失真函数和平均失真度。由于序列时相当于是一个由单符

8、号随机变量组成的随机矢量，仿照单符号时的情况，对单符号离散无记忆信源的L次扩展信源，在信道中的传递作用相当于单符号离散无记忆信道的L次扩展信道，输出也是一个随机变量序列，可得：15第15页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码定义7.1 设发送序列xi=xi1xi2xiN,接收序列为yi=yj1yj2yjN,定义序列失真度为：d(xi,yj)=d(xi1xi2xiN,yj1yj2yjN)=d(xi1,yj1)+d(xi2,yj2)+d(xiN,yjN)=d(xik,yjk)(k=1 to N)也就是说信源序列的失真度等于序列对应单个符号失真度之和，写成矩阵形式rNxs

9、N16第16页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码故对L长的信源序列，其平均失真度为17第17页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码18第18页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码平均每个符号的平均失真度为当信源与信道无记忆时，而19第19页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码如果满足平稳条件：若平均失真度不大于我们所允许的失真D，即 我们称此为保真度准则。20第20页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码7.2信息率失真函数信息率失真函数在信源给定，并且也

10、定义了具体的失真函数之后，我们总是希望在满足一定的失真限度要求的情况下，使信源最后输出的信息率R尽可能地小。也就是说，要在满足保真度准则下（），寻找信源输出信息率R的下限值。1)信息压缩问题对于给定的信源，在满足给定失真 的前提下使编码后的信息率（I(X；Y)）最小。21第21页，共78页，编辑于2022年，星期四2）限失真编码的研究方法将有失真信源编码器视作有干扰的信道，用分析信道传输的方法来研究限失真编码问题。3）D允许信道满足 的所有转移概率Pij构成了一类假想信道，称为D允许信道（或D失真许可的试验信道），对于模拟信道记为信息论与编码-限失真信源编码22第22页，共78页，编辑于202

11、2年，星期四信息论与编码-限失真信源编码对于离散无记忆信道，有我们的目的，就是要在上述允许信道 中，寻找到一个信道P(Y/X)，使得从输入端传送过来的信息量最少，即I(X;Y)最小。对于离散无记忆信源的N次扩展信源和离散无记忆N次扩展信道，相应的D失真许可信道为：4）信息率失真函数R(D)这个最小的互信息就称为信息率失真函数R(D)，简称为率失真函数。23第23页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码。应当注意，在研究R(D)时，我们引用的条件概率 并没有实际信道的含义，只是为了求平均互信息的最小值而引用的、假想的可变试验信道。实际上这些信道反应的仅是不同的有失真信源

12、编码，或称信源压缩。所以改变试验信道求最小值，实质上是选择一种编码方式式信息24第24页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码传输率为最小，也就是在保真度准则下，使信源的压缩率最高。R(D)是在信源和允许失真固定情况下，接收端用户收到的满足失真要求而再现信源消息所必须获得的最少平均信息量。R(D)反映了信源可以压缩的程度，是在满足一定失真条件下，信源可压缩的最低值。25第25页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码例 4-1-2已知编码器输入的概率分布是信道转移矩阵分别为：解：因为 ，用 代入因为：所以：26第26页，共78页，编辑于2022

13、年，星期四信息论与编码-限失真信源编码又因为 ，所以：代入互信息公式可得：用 代入同样可得27第27页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码可见，当p(x)一定时，I(X;Y)随Pij而变。可以证明，可以证明，当当p(x)一定时，一定时，I(X;Y)是关于是关于Pij的下凸函数的下凸函数。因此当Pij 改变时I(X;Y)有一极小值。信息率失真函数的物理意义：对于给定的信源，在平对于给定的信源，在平均失真限度均失真限度D条件下条件下()，信息率容许压缩的最，信息率容许压缩的最小值小值。是衡量一种具体信源压缩方法的尺子。此时的Pij实际上指的是一种限失真信源编码方法。下面

14、通过对一个信源处理的例子，进一步明确信息率失真函数的物理意义。28第28页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码例4-1-3设信源的符号表A=a1,a2,a3,a2n,概率分布为p(ai)=1/2n,i=1,2,2n,失真函数规定为由信源的概率分布可求出信源的熵为29第29页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码n如果对信源进行不失真编码，平均每个符号至少需要log2n个二进制码元。现在假定允许有一定失真，假设失真限度D=1/2。也就是说，当收到100个符号时，允许其中有50个以下的差错。这时信源的信息能够少到多少呢？每个符号平均码长能够压缩

15、到什么程度呢？设想采用以下编码方案。30第30页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码等效试验信道图：31第31页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码n按照上述关于失真函数的规定，求平均失真Dn由于上述编码相当于下图所示的试验信道，它是一个确定信道，所以32第32页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码由互信息量公式：信道输出概率分布为：则输出熵H（Y）为：33第33页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码由以上结果可知道，经压缩编码以后，信源需要传送的信息率由原来的log2n，压缩到也就

16、是说信息率压缩了所付出的代价是容忍1/2的平均失真。n注意：一旦达到最小互信息量这个极限值，就是一旦达到最小互信息量这个极限值，就是R(D)的的数值（此处数值（此处D=1/2）。如果超过这个极限值，那么，失真）。如果超过这个极限值，那么，失真就要超过失真限度。如果需要压缩的信息率更大，则容忍的就要超过失真限度。如果需要压缩的信息率更大，则容忍的失真就更大失真就更大34第34页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码五、信息率失真函数的性质 1.R(D)的定义域R(D)的定义域，即D的取值范围。（1）因为D是非负函数d(x,y)的数学期望，因此D也是非负函数，其下界为0。

17、此时，意味着不允许失真，所以信道的信息率等于信源的熵，即 但是平均失真度D,是否能达到下限值0，与单符号失真函数的定义有关35第35页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码36第36页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码37第37页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码38第38页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码（2）平均失真D也有一上界值 。根据R(D)的定义，R(D)是在一定的约束条件下，平均互信息量I(X;Y)的最小值，其下界为0。R(D)和D的关系曲线一般如下图所示。当D大到

18、一定程度，R(D)就达到其下界0，我们定义这时的D为 。39第39页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码n 的计算：设当平均失真 时，R(D)以达到其下界0。当允许更大失真时，即 时，R(D)仍只能继续是0。因为当X和Y统计独立时，平均互信息I(X;Y)=0，可见当 时，信源X和接收符号Y已经统计独立了，因此 ，与x无关。R(D)DR(D)0R(D)=040第40页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码因此，就是在R(D)=0的条件下，看在什么分布下(P(xi)一定)，能够得到的平均失真D的最小值，即也可以改写成41第41页，共78页，编辑

19、于2022年，星期四信息论与编码-限失真信源编码也就是说，要求 的数学期望的最小值。这个最小值是一定存在的。比如 这样分布：当某一个 使得 为最小时，就取 ，而其余的 ，此时求得的 的数学期望一定是最小的。此时，有例题：设输入输出符号表为X=Y=0,1，输入概率分布为 ，失真矩阵为42第42页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码求解：43第43页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码而输出符号概率为例题2：输入输出符号表同上题，失真矩阵为求解：此时44第44页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码(3)R(D)函数

20、的连续性现在证明R(D)在定义域0Dmax之间的连续性（1）（2）由于 是 的连续函数，即当（3）则45第45页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码(4)R(D)函数的下凸性46第46页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码 47第47页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码 48第48页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码（5）R(D)函数的单调性证明：非递增性证明非递增性证明由定义可以证明，当 则于是上式表明因为 后，在一个较大范围内求得的极小值不会大于一个小范围的极小值。所以R(D

21、)是非递增函数。49第49页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码单调性证明单调性证明即证明不等式中的等号不成立。用反证法：设50第50页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码 51第51页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码所以，R(D)有如下基本性质：n ，定义域为 ，当 时，R(D)=0。nR(D)是关于D的连续函数。nR(D)是关于D的严格递减函数。52第52页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码 53第53页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码因此，

22、当规定了允许失真，又找到了适当的失真函数 ，就可以找到该失真条件下的最小信息率R(D)，用不同的方法进行数据压缩时（在允许的失真限度D内），其压缩的程度如何，可以用R(D)来衡量。由它可知是否还有压缩潜力，有多大的压缩潜力。因此，有关R(D)的研究也是信息论领域的一个研究热点。54第54页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码7.3 R(D)的计算的计算信息论基础教程信息论基础教程,李亦农李亦农,北邮出版社北邮出版社已知信源的概率分布和失真函数 ，就可以求得信源的R(D)函数。求R(D)函数，实际上是一个求有约束问题的最小值问题。即适当选取试验信道的 使平均互信息55

23、第55页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码最小化，并使 满足以下约束条件应用拉格朗日乘子法，原则上总是可以求出上述问题的界。56第56页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码（1）R(D)函数的参量表达式：已知57第57页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码为了在（2）式的n+1个条件下求（1）式的极值，引入拉格郎日乘子s和ui(i=1,2,n),然后对p(yj/xi)进行求导，并令其为零，即得：58第58页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码得：59第59页，共78页，编辑于202

24、2年，星期四信息论与编码-限失真信源编码由此可解出s为参量的P(yj).为了保证P(yj)均为非负值，对s有限制。用这些P(yj)得到n个60第60页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码所以有：61第61页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码一般情况下，参量s无法消去，因此得不到R(D)函数的闭式解。若无法消去参量s就需要进行逐点计算。将R(D)看成D(s)和s的隐函数，而 又是s的函数，即R(D)=f(D,S,)利用全微分公式对R(D)函数求导，得 62第62页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码为求出 将（

25、7）式对s求导得到63第63页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码此式表明：参量s是信息率失真函数R(D)的斜率。由R(D)函数在0DDmax时，R(D)=0,其斜率为0，所以参量s的取值范围是64第64页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码n下面将简单介绍参量表达式方法求解失真函数R(D)。这里结合例子给出计算步骤：例4-2-1设输入输出符号表为X=Y=0，1，输入概率分布p(x)=p,1-p,0p0，当信源长度N足够长时，一定存在一种编码CK,其码字个数MexpNR(D)+,而编码后的平均失真73第73页，共78页，编辑于2022年，

26、星期四信息论与编码-限失真信源编码定理7.2（限失真编码定理逆定理）不存在平均失真度D而信息传输率RR(D)的任何信源编码，即对任意码长为N的信源码C,若码字个数MR(D)，只要信源序列L足够长，一定存在一种编码方法，其译码失真小于或等于D+.为任意小正数；反之，若RR(D),则无论采用什么样的编码方法，其译码失真必大于D75第75页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码定理说明，在允许失真为D的条件下，信源最小可达的信息传输率是信源的R(D)。保真度准则下的信源编码定理（限失真信源编码定理）是有失真信源压缩的理论基础。定理说明了在允许失真D确定后，总存在一种编码方法

27、，使编码的信息传输率大于R(D)且可以任意接近R(D)，而平均失真度小于允许失真D。而当信息传输率小于R(D)时，编码的平均失真将大于D。可见，R(D)是允许失真度为D的情况下信源信息压缩的下限值。76第76页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码 比较香农第一定理和香农第三定理可知，当信源给定后，无失真信源压缩的极限值是信源熵H(X)，而限失真信源压缩的极限值是信息率失真函数R(D)。在给定D后，一般R(D)H(X)。R(D)可以作为衡量各种压缩编码方法性能优劣的一种尺度。但香农第三定理同样是一个指出存在性的定理，至于如何寻找这种最佳压缩编码方法，定理中没有给出。在实际应用中，该理论主要存在以下两类问题：（1）符合实际信源的R(D)函数的计算相当困难。77第77页，共78页，编辑于2022年，星期四信息论与编码-限失真信源编码 首先，对需要对实际信源的统计特性有确切的数学描述，其次，需要符合主客观实际的失真度量。这些都不是很容易的事情。即使有了这些，率失真函数的计算也是相当困难的。（2）即使求得了符合实际的信息率失真函数，还需要研究采用何种编码方法，才能达到或接近极限值R(D)。78第78页，共78页，编辑于2022年，星期四