信息论课件第五章_无失真信源编码

无失真信源编码定理™通信的实质是信息的传输,而高效率、高质量地传送信息却又是信息传输的基本问题™将信源信息通过信道传输给信宿，怎样才能做到尽可能不失真而又快速呢？这就要解决两个问题：\第一：在不失真或允许一定失真条件下，如何尽可能少的符号来表示信源信息，以便提高信息传输率。\第二：在信道受干扰的情况下，如何增加信号的抗干扰能力，提高信息传输的可靠性，同时又使得信息传输率最大。™为此，我们引入信源编码和信道编码™一般来说，提高抗干扰的能力（降低失真或错误概率）往往是增加冗余度以降低信息传输率为代价的；反之，要提高信息传输率往往通过压缩信源的冗余度来实现而常常又会使抗干扰能力减弱。二者是有矛盾的。™然而在信息论的编码定理中，已从理论上证明，至少存在某种最佳的编码或信息处理方法，能够解决上述矛盾，做到既可靠又有效地传输信息。™这些结论对各种通信系统的设计个估价具有重大的理论指导意义。™本章将重点讨论对离散信源进行无失真信源编码的要求、方法以及理论极限，并得出一个极为重要的极限定理香农第一定理目录™5.1编码器™5.2等长码™5.3渐进等分割性和ε典型序列™5.4等长信源编码定理™5.4变长码™5.６变长信源编码定理5.1编码器™编码实质上是对信源的原始符号按照一定的数学规则进行一种变换。™为了分析方便和突出问题的重点，当研究信源编码时，我们将信道编码和译码看成是信道的一部分，而突出信源编码。同样，研究信道编码时，将信源编码和译码看成是信源和信宿的一部分，突出信道编码。图5.1无失真信源编码器编码器S:{s1,s2,…,sq}C:{W1,W2,…Wq}X:{x1,x2,…,xr}Wi是由li个xj（xj∈X）组成的序列，并与si一一对应™上述模型中，输入符号集S={s1,s2,…,sq}。同时存在另一符号集X={x1,x2,…,xr},一般元素xj是适合信道传输的，称为码符号（或者码元）。™编码器是将信源符号集中的符号si（或者长为N的信源符号序列αi)变换成由xj（j=1,2,…,r)组成的长度为li的一一对应序列。即),...,1()...(),...,1(21lkXxxxxWqiskiliiiiii=∈=↔=),...,2,1(),...,2,1(),...,2,1()...()...(2121iiiNiiiiiiiilkXxNkSsqixxxWssskkilN=∈=∈==↔=α或者™这种码符号序列Wi，称为码字。长度li称为码字长度或简称码长。所有这些码字的集合C称为码（或称码书）此码为r元码或称r进制码。™编码就是从信源符号到码符号的一种映射™若要实现无失真编码，必须这种映射是一一对应的、可逆的。二元码™若码符号集为X=｛０,１｝（即r=2）,所得码字就是一些二元序列，则称为二元码（或称二进制码）™若将信源通过一个二元信道进行传输，为使信源适合信道传输，就必须把信源符号变换成0,1符号组成的码符号序列（二元序列）这种编码所得的码为二元码。™二元码是数字通信和计算机系统中最常用的一种码。等长码™若一组码中所有的码字的码长都相同，即li=l(i=1,2,…,q),则称为等长码。变长码™若一组码中所有的码字的码长各不相同，即任意码字由不同长度li的码符号序列组成，则称为变长码。非奇异码™若一组码中所有的码字都不相同，即所有信源符号映射到不同的码符号序列),,(CWWSssWWssjijijiji∈∈≠⇒≠),,(CWWSssWWssjijijiji∈∈=⇒≠则称码C为非奇异码。™若一组码中有相同的码字，即奇异码则称码C为奇异码。同价码™若码符号集X:{x1,x2,…,xr}中每个码符号xi所占的传输时间相同，则所得的码C为同价码。™一般二元码是同价码。本章讨论的都是同价码。对同价码来说，等长码中每个码字的传输速度都相同；而变长码中每个码字的传输时间就不一定相同。电报中用的莫尔斯码是非同价码，其码符号点（.）和划（－）所占的传输时间不相同。码的N次扩展码™假定某码C，它把信源S中的符号si一一变换成码C中的码字Wi，则称码C的N次扩展码是所有N个码字组成的码字序列的集合。XxxxxWSsililiiiiii∈=↔∈)...(21™若码C={W1,W2,…,Wq}其中则N次扩展码⎭⎬⎫⎩⎨⎧====NNiiiiqiqiii)...(2121可见，码C的N次扩展码B中，每个码字Bi（i=1,2,…,qN)与N次扩展信源SN中每个信源序列符号αi一一对应，而)...(21Niiiisss=α举例：™设信源S的概率空间为1)()(...,),(),(...,,,)(12121=⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡∑=qiiqqsPsPsPsPssssPS™若把它通过一个二元信道进行传输，为使信源适合信道传输，就必须把信源符号si变换成0,1符号组成的码符号序列（二元序列）。我们可以采用不同的二元序列使其与信源符号si一一对应，这样就得到不同的二元码。表５.１信源符号si符号概率P(si)码１码２s1P(s1)000s2P(s2)0101s3P(s3)10001s4P(s4)11111™码１是等长非奇异码，码２是变长非奇异码。N次扩展码™我们可以求得表5.1中码１和码２的任意N次扩展码。例如求码２的二次扩展码。™因为信源S的二次扩展信源S2=[α1=s1s1,α2=s1s2,α3=s1s3,…,α16=s4s4]所以码２的二次扩展码为信源符号码字信源符号码字信源符号码字α１00=W1W1=B1α5010=W2W1=B5……α２001=W1W2=B2…………α３0001=W1W3=B3…………α４0111=W1W4=B4……α16111111=W4W4=B16惟一可译码™若码的任意一串有限长的码符号序列只能被惟一地译成所对应的信源符号序列，则此码称为惟一可译码，或单义可译码。否则称为非惟一可译码或非单义可译码。™若要所编的码是惟一可译码，不但要求编码时不同的信源符号变换成不同的码字，而且还要求任意有限长的信源序列所对应的码符号序列各不相同，即要求码的任意长N次扩展码都是非奇异码。因为只有任意有限长的信源序列所对应的码符号序列各不相同，才能把该码符号序列唯一地分割成一个个对应的信源符号，从而实现惟一地译码。™所以，某码的任意有限长N次扩展码都是非奇异码，则该码为唯一可译码。™例如，表5.1中码１是惟一可译码，而码２是非惟一可译码。™因为对于码２，其有限长的码符号序列能译成不同的信源符号序列。如：0010,可译成s1s2s1或s3s1,显然不是惟一的。™下面，我们分别讨论等长码和变长码的最佳编码问题，也就是是否存在一种惟一可译编码方法，使平均每个信源符号所需的码符号最短。也就是无失真信源压缩的极限值。5.2等长码™一般来说,若要实现无失真的编码,这不但要求信源符号si(i=1,2,…,q)与码字Wi(i=1,2,…,q)是一一对应的,而且要求码符号序列的反变换也是惟一的.™所编的码必须是惟一可译码.否则,所编的码不具有惟一可译码性,就会引起译码带来的错误与失真.™对于等长码来说,若等长码是非奇异码,则它的任意有限长N次扩展码一定也是非奇异码.™因此等长非奇异码一定是惟一可译码.表5.2等长码信源符号码1码2s1s2s3s40001101100111011™在上表中,码2不是惟一可译码,比如11™码1是等长非奇异码,所以是惟一可译码.™若对信源进行等长编码,则必须满足)1.5(lrq≤式中,l是等长码的码长,r是码符号集中码元数.™例如表5.2中,信源S共有q=4个信源符号,现进行二元等长编码,其中码符号个数为r=2.根据式(5.1)可知,信源S存在惟一可译等长码的条件是码长l必须不小于2.™如果我们对信源S的N次扩展信源进行等长编码.设信源,有q个符号,那么它的N次扩展信源共有qN个符号.其中是长度为N的信源符号序列},...,,{21qsssS=},...,,{21NqNSααα=),...,2,1}(,...,,{21NkSsssskNiiiii=∈=α™设码符号集为.],...,,[21rxxxX=™现在需要把这些长为N的信源符号序列变换成长度为l的码符号序列),...,1(Niqi=α),...,(),...(121XxxxxxWlliiiiii∈=™根据前面的分析,若要求得编得的等长码是惟一可译码则必须满足)2.5(lNrq≤此式表明,只有当l长的码符号序列数(rl)大于或等于N次扩展信源的符号数(qN)时,才可能存在等长非奇异码.™对式(5.2)两边取对数,则有rqNlloglog≥™是平均每个信源符号所需要的码符号个数.Nl™对于等长惟一可译码,每个信源符号至少需要用个码符号来变换.rqloglog™当r=2,logr=1,则qNllog≥™这结果表明:对于二元等长惟一可译码,每个信源符号至少需要logq个二元符号来变换.™这也表明:对信源进行二元等长不失真编码时,每个信源符号所需要码长的极限值为logq个.™英文符号至少需要5个二元符号编码才行.™是不是可以用更少的符号表示?是™接下来的例子说明为什么每个信源符号平均所需的码符号个数可以减少.™设信源∑==⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡41432143211)(,)(),(),(),(,,,)(iisPsPsPsPsPsssssPS而其依赖关系为P(s1|s2)=P(s2|s1)=P(s3|s4)=P(s4|s3)=1,其余P(sj|si)=0.™若不考虑符号之间依赖关系,此信源q=4,那么,进行等长二元编码,由前面可知,l=2.™若考虑符号之间依赖关系,此特殊信源的二次扩展信源为)4,3,2,1,()|()()(1)()(),(),(),(,,,)(34431221344312212=⋅==⎥⎦⎤⎢⎣⎡=⎥⎥⎦⎤⎢⎢⎣⎡∑jissPsPssPssPssPssPssPssPssssssssssPSijijiijjiji又™由上述依赖关系可以知道,除了P(s1|s2),P(s2|s1),P(s3|s4),P(s4|s3)不等于0,其余sisj出现的概率皆为0.™因此二次扩展信源S2由16个符号缩减到4个符号.因此对它进行等长编码,所需码长仍为l’=2.™由此可见,当考虑信源符号之间依赖关系后,有些信源符号序列不会出现,这样信源符号序列个数会减少,再进行编码时,所需平均码长就可以缩短.™英文™等长编码定理给出了信源进行等长编码所需码长的理论极限值.5.3渐进等分割性和ε典型序列™渐近等分割性指出：随机变量S1,S2,…,SN独立同分布，联合概率为P(S1S2…SN),只要N足够大，N个变量自信息的平均值接近于信息熵H(S)(自信息的数学期望)∑=niiXn11)(log121NSSSPN−)(2SNH−)(log1)SSlogP(SN1-1N21∑=−=…niiSPN注意：™渐进等分割性AEP是弱大数定理的直接推论™大数定理：若X1,X2,…，Xn是独立同分布的随机变量，只要n足够大，接近于数学期望E(X)。™即：P(S1S2…SN)接近于定理5.1渐近等分割性：若随机序列S1S2…SN相互独立并且都服从同一概率分布P(s),则：⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡qqPPPsssPS2121对离散无记忆信源：11=∑=qiiPSN=(S1S2…SN)为其N次扩展信源.表示扩展信源)(21Niiiisss=α)(log1)(log121NiiiisssPNPN−=−α依概率收敛于H(S)也就是N足够大时，N个变量自信息的平均值接近于信息熵H(S)(自信息的数学期望))(121NiiisssPN−即：对任意ε0,有：的输出。1}|)()(log1{|lim=−−∞→εαSHPNPiNε典型序列™定义：N长的序列，对于任意小的正数ε，满足NiiiiSsssN∈=)(21αεα−−|)()(log1|SHPNi则称为ε典型序列。iα反之。若满足则称为ε非典型序列。εα≥−−|)()(log1|SHPNiiα记：}|)()(log1:|{εααε