信息论基础第七章

信息论基础第七章第一页，共七十八页，2022年，8月28日1信息论与编码-限失真信源编码第五章我们讨论了无失真信源编码。但是，在很多场合，特别是对于连续信源，因为其绝对熵为无限大，若要求无失真地对其进行传输，则要求信道的信息传输率也为无限大，这是不现实的。因此也就不可能实现完全无失真传输。另一方面，从无失真信源编码定理来考虑，由于要求码字包含的信息量大于等于信源的熵，所以对于连续信源，要用无限多个比特才能完全无失真地来描述。第二页，共七十八页，2022年，8月28日2信息论与编码-限失真信源编码第16讲7.1失真测度第三页，共七十八页，2022年，8月28日3信息论与编码-限失真信源编码即使对于离散信源，由于处理的信息量越来越大，使得信息的存储和传输成本很高，而且在很多场合，过高的信息率也没有必要，例如：由于人耳能够接收的带宽和分辨率是有限的，因此对数字音频传输的时候，就允许有一定的失真，并且对欣赏没有影响。又如对于数字电视，由于人的视觉系统的分辨率有限，并且对低频比较敏感，对高频不太敏感，因此也可以损失部分高频分量，当然要在一定的限度内。等等这些，都决定了限失真信源编码的重要性。第四页，共七十八页，2022年，8月28日4信息论与编码-限失真信源编码在限失真信源编码里，一个重要的问题就是在一定程度的允许失真限度内，能把信源信息压缩到什么程度，即最少用多少比特数才能描述信源。这个问题已经被香农解决。香农在1948年的经典论文中已经提到了这个问题，在1959年，香农又在他的一篇论文“保真度准则下的离散信源编码定理”里讨论了这个问题。研究这个问题并做出较大贡献的还有前苏联的柯尔莫郭洛夫（Kolmogorov）以及伯格（T.Berger）等。第五页，共七十八页，2022年，8月28日5信息论与编码-限失真信源编码信息率失真理论是矢量化、数模转换、频带压缩和数据压缩的理论基础。本章主要介绍信息率失真理论的基本内容，包括信源的失真度和信息率失真函数的定义与性质，离散信源和连续信源的信息率失真函数计算，在此基础上论述保真度准则下的信源编码定理——即香农第三编码定理。第六页，共七十八页，2022年，8月28日6信息论与编码-限失真信源编码在实际中，信号有一定的失真是可以容忍的，但当失真大于某一限度后，信息质量将被严重损伤，甚至丧失其实用价值，因此，要规定失真限度，必须对其有一个定量的失真测度P(Yj/xi)XY信道的数学模型第七页，共七十八页，2022年，8月28日7信息论与编码-限失真信源编码转移矩阵描述P=(P(yj/xi))nxmP矩阵为一个n×m矩阵，其每行元素之和等于1。

从这个角度看编码器可以看作一个广义的信道，X为信道的输入，Y是信道的输出。与无失真编码不同，这是从输入到输出是一个多对一的映射，它是不可逆的，信源符号与码元符号之间的差异就是编码时引入的失真。第八页，共七十八页，2022年，8月28日8信息论与编码-限失真信源编码、失真函数（定量地描述信息失真程度）设某信源输出的随机变量为X，其值集合为，经过编码后输出为，设对应，如果则认为没有失真。当时，就产生了失真，失真的大小，用失真函数来衡量。单个符号的失真函数(失真度)的定义为第九页，共七十八页，2022年，8月28日9信息论与编码-限失真信源编码由于输入符号有n个，输出符号有m个，所以共有个，写成矩阵形式，就是d被称为失真矩阵。第十页，共七十八页，2022年，8月28日10信息论与编码-限失真信源编码例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.解：由失真矩阵定义：第十一页，共七十八页，2022年，8月28日11信息论与编码-限失真信源编码失真函数的函数形式可以根据需要适当选取，如平方代价函数、绝对代价函数、均匀代价函数等：平方失真：绝对失真：相对失真：误码(汉明)失真：第十二页，共七十八页，2022年，8月28日12信息论与编码-限失真信源编码也可以按其它的标准，如引起的损失、风险、主观感觉上的差别等来定义失真函数。二、平均失真由于信源X和信宿Y都是随机变量，所以符号失真度函数也是一个随机变量，传输时引起的平均失真应该是符号失真度函数在信源概率空间和信宿概率空间求平均，即：第十三页，共七十八页，2022年，8月28日13信息论与编码-限失真信源编码平均失真是符号失真函数在信源空间和信宿空间平均的结果，是描述某一信源在某一信道传输时失真的大小，是从整体上描述系统的失真情况。第十四页，共七十八页，2022年，8月28日14信息论与编码-限失真信源编码三、信源符号序列的失真从上面的单符号失真函数，可以得到信源符号序列的失真函数和平均失真度。由于序列时相当于是一个由单符号随机变量组成的随机矢量，仿照单符号时的情况，对单符号离散无记忆信源的L次扩展信源，在信道中的传递作用相当于单符号离散无记忆信道的L次扩展信道，输出也是一个随机变量序列，可得：第十五页，共七十八页，2022年，8月28日15信息论与编码-限失真信源编码定义7.1设发送序列xi=xi1xi2…xiN,,接收序列为yi=yj1yj2…yjN,

定义序列失真度为：d(xi,yj)=d(xi1xi2…xiN,

yj1yj2…yjN)=d(xi1,yj1)+d(xi2,yj2)+…+d(xiN,yjN)=∑d(xik,yjk)(k=1toN)也就是说信源序列的失真度等于序列对应单个符号失真度之和，写成矩阵形式rNxsN第十六页，共七十八页，2022年，8月28日16信息论与编码-限失真信源编码故对L长的信源序列，其平均失真度为第十七页，共七十八页，2022年，8月28日17信息论与编码-限失真信源编码第十八页，共七十八页，2022年，8月28日18信息论与编码-限失真信源编码平均每个符号的平均失真度为当信源与信道无记忆时，，而第十九页，共七十八页，2022年，8月28日19信息论与编码-限失真信源编码如果满足平稳条件：若平均失真度不大于我们所允许的失真D，即我们称此为保真度准则。第二十页，共七十八页，2022年，8月28日20信息论与编码-限失真信源编码7.2信息率失真函数在信源给定，并且也定义了具体的失真函数之后，我们总是希望在满足一定的失真限度要求的情况下，使信源最后输出的信息率R尽可能地小。也就是说，要在满足保真度准则下（），寻找信源输出信息率R的下限值。1)信息压缩问题对于给定的信源，在满足给定失真的前提下使编码后的信息率（I(X；Y)）最小。第二十一页，共七十八页，2022年，8月28日212）限失真编码的研究方法将有失真信源编码器视作有干扰的信道，用分析信道传输的方法来研究限失真编码问题。3）D允许信道满足的所有转移概率Pij构成了一类假想信道，称为D允许信道（或D失真许可的试验信道），对于模拟信道记为信息论与编码-限失真信源编码第二十二页，共七十八页，2022年，8月28日22信息论与编码-限失真信源编码对于离散无记忆信道，有我们的目的，就是要在上述允许信道中，寻找到一个信道P(Y/X)，使得从输入端传送过来的信息量最少，即I(X;Y)最小。对于离散无记忆信源的N次扩展信源和离散无记忆N次扩展信道，相应的D失真许可信道为：4）信息率失真函数R(D)这个最小的互信息就称为信息率失真函数R(D)，简称为率失真函数。第二十三页，共七十八页，2022年，8月28日23信息论与编码-限失真信源编码。应当注意，在研究R(D)时，我们引用的条件概率并没有实际信道的含义，只是为了求平均互信息的最小值而引用的、假想的可变试验信道。实际上这些信道反应的仅是不同的有失真信源编码，或称信源压缩。所以改变试验信道求最小值，实质上是选择一种编码方式式信息第二十四页，共七十八页，2022年，8月28日24信息论与编码-限失真信源编码传输率为最小，也就是在保真度准则下，使信源的压缩率最高。R(D)是在信源和允许失真固定情况下，接收端用户收到的满足失真要求而再现信源消息所必须获得的最少平均信息量。R(D)反映了信源可以压缩的程度，是在满足一定失真条件下，信源可压缩的最低值。第二十五页，共七十八页，2022年，8月28日25信息论与编码-限失真信源编码[例4-1-2]已知编码器输入的概率分布是信道转移矩阵分别为：解：因为，用代入因为：所以：第二十六页，共七十八页，2022年，8月28日26信息论与编码-限失真信源编码又因为，所以：代入互信息公式可得：用代入同样可得第二十七页，共七十八页，2022年，8月28日27信息论与编码-限失真信源编码可见，当p(x)一定时，I(X;Y)随Pij而变。可以证明，当p(x)一定时，I(X;Y)是关于Pij的下凸函数。因此当Pij

改变时I(X;Y)有一极小值。信息率失真函数的物理意义：对于给定的信源，在平均失真限度D条件下()，信息率容许压缩的最小值。是衡量一种具体信源压缩方法的尺子。此时的Pij实际上指的是一种限失真信源编码方法。下面通过对一个信源处理的例子，进一步明确信息率失真函数的物理意义。第二十八页，共七十八页，2022年，8月28日28信息论与编码-限失真信源编码[例4-1-3]设信源的符号表A={a1,a2,a3,…,a2n},概率分布为p(ai)=1/2n,i=1,2,…2n,失真函数规定为由信源的概率分布可求出信源的熵为第二十九页，共七十八页，2022年，8月28日29信息论与编码-限失真信源编码如果对信源进行不失真编码，平均每个符号至少需要log2n个二进制码元。现在假定允许有一定失真，假设失真限度D=1/2。也就是说，当收到100个符号时，允许其中有50个以下的差错。这时信源的信息能够少到多少呢？每个符号平均码长能够压缩到什么程度呢？设想采用以下编码方案。第三十页，共七十八页，2022年，8月28日30信息论与编码-限失真信源编码等效试验信道图：第三十一页，共七十八页，2022年，8月28日31信息论与编码-限失真信源编码按照上述关于失真函数的规定，求平均失真D由于上述编码相当于下图所示的试验信道，它是一个确定信道，所以第三十二页，共七十八页，2022年，8月28日32信息论与编码-限失真信源编码由互信息量公式：信道输出概率分布为：则输出熵H（Y）为：第三十三页，共七十八页，2022年，8月28日33信息论与编码-限失真信源编码由以上结果可知道，经压缩编码以后，信源需要传送的信息率由原来的log2n，压缩到也就是说信息率压缩了所付出的代价是容忍1/2的平均失真。注意：一旦达到最小互信息量这个极限值，就是R(D)的数值（此处D=1/2）。如果超过这个极限值，那么，失真就要超过失真限度。如果需要压缩的信息率更大，则容忍的失真就更大第三十四页，共七十八页，2022年，8月28日34信息论与编码-限失真信源编码五、信息率失真函数的性质

1.R(D)的定义域R(D)的定义域，即D的取值范围。（1）因为D是非负函数d(x,y)的数学期望，因此D也是非负函数，其下界为0。此时，意味着不允许失真，所以信道的信息率等于信源的熵，即但是平均失真度D,是否能达到下限值0，与单符号失真函数的定义有关第三十五页，共七十八页，2022年，8月28日35信息论与编码-限失真信源编码第三十六页，共七十八页，2022年，8月28日36信息论与编码-限失真信源编码第三十七页，共七十八页，2022年，8月28日37信息论与编码-限失真信源编码第三十八页，共七十八页，2022年，8月28日38信息论与编码-限失真信源编码（2）平均失真D也有一上界值。根据R(D)的定义，R(D)是在一定的约束条件下，平均互信息量I(X;Y)的最小值，其下界为0。R(D)和D的关系曲线一般如下图所示。当D大到一定程度，R(D)就达到其下界0，我们定义这时的D为。第三十九页，共七十八页，2022年，8月28日39信息论与编码-限失真信源编码

的计算：设当平均失真时，R(D)以达到其下界0。当允许更大失真时，即时，R(D)仍只能继续是0。因为当X和Y统计独立时，平均互信息I(X;Y)=0，可见当时，信源X和接收符号Y已经统计独立了，因此，与x无关。R(D)DR(D)>0R(D)=0第四十页，共七十八页，2022年，8月28日40信息论与编码-限失真信源编码因此，就是在R(D)=0的条件下，看在什么分布下(P(xi)一定)，能够得到的平均失真D的最小值，即也可以改写成第四十一页，共七十八页，2022年，8月28日41信息论与编码-限失真信源编码也就是说，要求的数学期望的最小值。这个最小值是一定存在的。比如这样分布：当某一个使得为最小时，就取，而其余的，此时求得的的数学期望一定是最小的。此时，有例题：设输入输出符号表为X=Y={0,1}，输入概率分布为，失真矩阵为第四十二页，共七十八页，2022年，8月28日42信息论与编码-限失真信源编码求解：第四十三页，共七十八页，2022年，8月28日43信息论与编码-限失真信源编码而输出符号概率为例题2：输入输出符号表同上题，失真矩阵为求解：此时第四十四页，共七十八页，2022年，8月28日44信息论与编码-限失真信源编码(3)R(D)函数的连续性现在证明R(D)在定义域0~Dmax之间的连续性（1）（2）由于是的连续函数，即当（3）则第四十五页，共七十八页，2022年，8月28日45信息论与编码-限失真信源编码(4)R(D)函数的下凸性第四十六页，共七十八页，2022年，8月28日46信息论与编码-限失真信源编码

第四十七页，共七十八页，2022年，8月28日47信息论与编码-限失真信源编码

第四十八页，共七十八页，2022年，8月28日48信息论与编码-限失真信源编码（5）R(D)函数的单调性证明：非递增性证明由定义可以证明，当则于是上式表明因为后，在一个较大范围内求得的极小值不会大于一个小范围的极小值。所以R(D)是非递增函数。第四十九页，共七十八页，2022年，8月28日49信息论与编码-限失真信源编码单调性证明即证明不等式中的等号不成立。用反证法：设第五十页，共七十八页，2022年，8月28日50信息论与编码-限失真信源编码

第五十一页，共七十八页，2022年，8月28日51信息论与编码-限失真信源编码所以，R(D)有如下基本性质：，定义域为，当时，R(D)=0。R(D)是关于D的连续函数。R(D)是关于D的严格递减函数。第五十二页，共七十八页，2022年，8月28日52信息论与编码-限失真信源编码

第五十三页，共七十八页，2022年，8月28日53信息论与编码-限失真信源编码因此，当规定了允许失真，又找到了适当的失真函数，就可以找到该失真条件下的最小信息率R(D)，用不同的方法进行数据压缩时（在允许的失真限度D内），其压缩的程度如何，可以用R(D)来衡量。由它可知是否还有压缩潜力，有多大的压缩潜力。因此，有关R(D)的研究也是信息论领域的一个研究热点。第五十四页，共七十八页，2022年，8月28日54信息论与编码-限失真信源编码§7.3R(D)的计算[信息论基础教程,李亦农,北邮出版社]已知信源的概率分布和失真函数，就可以求得信源的R(D)函数。求R(D)函数，实际上是一个求有约束问题的最小值问题。即适当选取试验信道的使平均互信息第五十五页，共七十八页，2022年，8月28日55信息论与编码-限失真信源编码最小化，并使满足以下约束条件应用拉格朗日乘子法，原则上总是可以求出上述问题的界。第五十六页，共七十八页，2022年，8月28日56信息论与编码-限失真信源编码（1）R(D)函数的参量表达式：已知第五十七页，共七十八页，2022年，8月28日57信息论与编码-限失真信源编码为了在（2）式的n+1个条件下求（1）式的极值，引入拉格郎日乘子s和ui(i=1,2,…,n),然后对p(yj/xi)进行求导，并令其为零，即得：第五十八页，共七十八页，2022年，8月28日58信息论与编码-限失真信源编码得：第五十九页，共七十八页，2022年，8月28日59信息论与编码-限失真信源编码由此可解出s为参量的P(yj).为了保证P(yj)均为非负值，对s有限制。用这些P(yj)得到n个第六十页，共七十八页，2022年，8月28日60信息论与编码-限失真信源编码所以有：第六十一页，共七十八页，2022年，8月28日61信息论与编码-限失真信源编码一般情况下，参量s无法消去，因此得不到R(D)函数的闭式解。若无法消去参量s就需要进行逐点计算。将R(D)看成D(s)和s的隐函数，而又是s的函数，即R(D)=f(D,S,)利用全微分公式对R(D)函数求导，得

第六十二页，共七十八页，2022年，8月28日62信息论与编码-限失真信源编码为求出将（7）式对s求导得到第六十三页，共七十八页，2022年，8月28日63信息论与编码-限失真信源编码此式表明：参量s是信息率失真函数R(D)的斜率。由R(D)函数在0<D<Dmax之间是严格单调递减函数可知，s是负值，且s将随D的增加而增加。又R(D)的性质可知，在D=0处R(D)的斜率可能为负无穷大；当D>Dmax时，R(D)=0,其斜率为0，所以参量s的取值范围是第六十四页，共七十八页，2022年，8月28日64信息论与编码-限失真信源编码下面将简单介绍参量表达式方法求解失真函数R(D)。这里结合例子给出计算步骤：[例4-2-1]设输入输出符号表为X=Y={0，1}，输入概率分布p(x)={p,1-p},0<p<=1/2,失真矩阵为求信息率失真函数R(D)第六十五页，共七十八页，2022年，8月28日65信息论与编码-限失真信源编码

第六十六页，共七十八页，2022年，8月28日66信息论与编码-限失真信源编码

第六十七页，共七十八页，2022年，8月28日67信息论与编码-限失真信源编码

第六十八页，共七十八页，2022年，8月28日68信息论与编码-限失真信源编码

第六十九页，共七十八页，2022年，8月28日69信息论与编码-限失真信源编码结果得到如下图所示曲线：第七十页，共七十八页，2022年，8月28日70信息论与编码-限失真信源编码但一般来说，求解会是非常复杂的。这里不准备做复杂的推导过程，只给出几个结果。（1）当，时，第七十一页，共七十八页，2022年，8月28日71信息论与编码-限失真信源编码，（2）当，时，，（3）当，时，，第七十二页，共七十八页，2022年，8月28日72信息论与编码-限失真信源编码7.4限失真信源编码定理（香农第三编码定理-信息率与失真之间关系的一个极限定律）定理7.1设R(D)是离散无记忆信源的信息率失真函数并且失真函数为有限值，对于任意的允许失真D≥0和任意小的正数ε>0，当信源长度N足够长时，一定存在一种编码CK,其码字个数M≤exp{N[R(D)+ε]},而编码