信息论与编码第5章

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,信源编码,第,5,章,5.1,编码的定义,5.2,无失真信源编码,5.3,限,失真信源编码,5.4,常用,信源编码方法简介,内容,2,5.1,编码的定义,3,信源编码：,无失真信源编码,第一极限定理 离散信源,限失真信源编码,第三极限定理 连续信源,信道编码,第二极限定理,信源编码,在不失真或允许一定失真条件下,如何用尽可能少的符号来传送信源信息,以便,提高信息传输率,信道编码,在信道受干扰的情况下如何增加信号的,抗干扰能力,同时又使得信息传输率最大。,编码,4,编码的定义,信源,编码器,码表,信源,信道,信源编码,:,将信源输出符号,经信源编码器后变换成另外的,压缩符号,然后将压缩后信息经信道传送给信宿,信源符号之间存在,分布不均匀,和,相关性,使得信源存在冗余度,信源编码,的主要任务就是,减少冗余,提高编码效率。,针对信源输出符号序列的,统计特性,寻找一定的方法把信源输出符号序列变换为,最短,的码字序列。,X,Y,5,编码的定义,编码定理证明,:,必存在一种编码方法,使,代码的平均长度,可任意接近但,不能低于符号熵,;,达到这目标的途径就是使,概率与码长匹配,。,统计匹配编码,：,根据信源的不同概率分布而选用与之匹配的编码,以达到在系统中传信速率最小。,6,编码的定义,信源符号,信源符号,出现概率,码 表,码,0,码,1,码,2,码,3,码,4,a,1,p,(,a,1,)=1/2,00,0,0,1,1,a,2,p,(,a,2,)=1/4,01,11,10,10,01,a,3,p,(,a,3,)=1/8,10,00,00,100,001,a,4,p,(,a,4,)=1/8,11,11,01,1000,0001,等长码,：码中所有码字的长度都相同,变长码,：码中的码字长短不一,非奇异码,：信源符号与码字是一一对应的,奇异码,：码,1,若码集为,0,1,所得码字为二元序列,称为二元码,例如,信源符号,X,a,1,a,2,a,3,a,4,对应不同码字如表,7,编码的定义,唯一可译码：,任意有限长的码元序列,只能被唯一地分割成一个个的码字。,例：,0,10,11,是一种唯一可译码。,任意一串有限长码序列,如,100111000,只能被分割成,10,0,11,10,0,0,。任何其他分割法都会产生一些非定义的码字。,奇异码不是唯一可译码,非奇异码,唯一可译码,码,3,非唯一可译码,码,2,8,编码的定义,唯一可译码,非即时码,：,如果接收端收到一个完整的码字后不能立即译码,还需等下一个码字开始接收后才能判断是否可以译码,即时码,：,(,非延长码,) (,异前缀码,),在,译码,时无需参考后续的码符号就能,立即,作出判断,译成对应的信源符号。,任意一个码字都,不是,其它码字的,前缀,部分,在延长码中,有的码是唯一可译的,取决于码的总体结构,9,编码的定义,码,非分组码,分组码,奇异码,非奇异码,非唯一可译码,唯一可译码,非即时码,即时码,(,非延长码,),10,码树,表示各码字的构成,A,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,1,1,1,1,1,二进制码树,2,0,0,0,0,0,1,1,1,1,1,2,2,2,2,2,三进制码树,树根,码字的起点,分成,r,个,树枝,码的进制数,终端,节点,码字,1101,中间,节点,码字的一部分,节数,码长,11,码,4,1,1,1,1,0,0,0,1,0,1,001,0001,码,4,0,0,0,0,1,1,1,0,10,110,1110,树码,如果有,n,个信源符号,那么在码树上就要选择,n,个,终端节点,用相应的,r,元基本符号表示这些码字。,码,0,0,1,0,0,1,11,1,10,01,00,任一,即时码,都可用树图法来表示。,当码字长度给定,即时码不是唯一的。,12,1,10,1000,100,1,0,0,0,码,3,对应的树如下图,:,编码的定义,该码树从根到终端节点所经路径上每一个,中间节点皆为码字,因此不满足前缀条件。,虽然码,3,不是即时码,但它是唯一可译码。,13,编码的定义,满树：,每个节点上都有,r,个分枝的树,等长码,非满树,：,变长码,用树的概念可导出,唯一可译码,存在的,充分和必要条件,即各码字的长度,Ki,应符合,Kraft,不等式,式中,:,m,是进制数,n,是信源符号数,14,例,：,设二进制码树中,X=(,a,1,a,2,a,3,a,4,), K,1,=1,K,2,=2,K,3,=2,K,4,=3,应用,Kraft,不等式,得：,不存在满足这种,K,i,的唯一可译码,0,0,0,1,1,0,10,110,11,中间,节,点,如果将各码字长度改成,K,1,=1,K,2,=2,K,3,=3,K,4,=3,则,这样的码字就存在唯一可译码,111,15,编码的定义,必须注意：,Kraft,不等式只是用来说明唯一可译码是否存在,并不能作为唯一可译码的判据。,如码字,0,，,10,，,010,，,111,虽然满足,Kraft,不等式,但它不是唯一可译码。,16,5.2,无失真信源编码,17,无失真信源编码,信源编码器,码表,信源,信道,信源编码器输入的消息序列,:,X,=(X,1,X,2,X,l,X,L,),X,l,a,1,a,n,输入的消息总共有,n,L,种可能的组合,输出的码字为,:,Y,=(Y,1,Y,2,Y,k,Y,K,) ,Y,k,b,1,b,m,输出的码字总共有,m,K,种可能的组合。,X,Y,L,长序列,K,长码字,18,无失真信源编码,实现,无失真,的信源编码,要求,:,信源符号,X,1,X,2,X,l,X,L,是一一对应的,码字,Y,1,Y,2,Y,k,Y,K,能够无失真或,无差错地从,Y,恢复,X,也就是能正确地进行反变换或译码,;,传送,Y,时所需要的,信息率最小,信息率最小,就是找到一种编码方式使,最小,19,5.2.1,定长编码定理,信源,编码器,码表,信源,信道,在,定长,编码中,K,是,定值,。,我们的目的是寻找,最小,K,值,。,编码器输入,X,=(X,1,X,2,X,l,X,L,),X,l,a,1,a,n,输入的消息总共有,n,L,种可能的组合,输出的码字,Y,=(Y,1,Y,2,Y,k,Y,K,) , Y,k,b,1,b,m,输出的码字总共有,m,K,种可能的组合。,若对信源进行,定长,编码,必须满足,:,n,L,m,K,X,Y,L,长序列,K,长码字,20,定长编码,若对信源进行,定长,编码,必须满足,:,只有当,K,长的码符号序列数,m,K,大于或等于信源的符号数,n,L,时,才可能存在,定长,非奇异码。,例如英文电报有,27,个符号,n=27,L=1,m=2(,二元编码,),每个英文电报符号至少要用,5,位二元符号编码,21,定长编码,实际英文电报符号信源,在考虑了符号出现的概率以及符号之间的依赖性后,平均每个英文电报符号所提供的信息量约等于,1.4,比特,大大小于,5,比特。,编码后,5,个二元符号只携带约,1.4,比特信息量。,定长编码的信息传输效率极低。,22,定长编码定理,定长编码定理,：,由,L,个符号组成的、每个符号的熵为,H,L,(X),的无记忆平稳信源符号序列,X,1,X,l,X,L,可用,K,个符号,Y,1,Y,k,Y,K,(,每个符号有,m,种可能值,),进行定长编码。对任意,0,0,只要,则当,L,足够大时,必可使译码差错小于,;,反之,当,时,译码差错一定是有限值,而当,L,足够大时,译码几乎必定出错,23,定长编码定理,当编码器容许的输出信息率,也就是当每个信源符号所必须输出的码长是,时,只要,这种编码器一定可以做到几,乎,无失真,也就是收端的译码差错概率接近于零,条件是所取的符号数,L,足够大,。,24,将定理的条件改写成,其中：,左边：,K,L,长码字所能携带的最大信息，,右边：,L,长信源序列携带的信息量。,上述定理表明,:,只要码字所能携带的信息量大于信源序列输出的信息量,则可以使传输几乎无失真,当然条件是,L,足够大。,反之,当 时,不可能构成无失真的编码,也就是不可能做一种编码器,能使收端译码时差错概率趋于零。,时,则为,临界状态,可能无失真,也可能有失真。,25,定长编码定理,为了衡量编码效果,定义,编码效率,：,对定长编码,若要实现几乎无失真编码,则信源长度必须满足,:,信源序列的自信息方差,26,例,5-2,设离散无记忆信源概率空间,信源熵：,方差：,若取差错率,10,6,编码效率为,90%,则,L,应满足,在差错率和编码效率要求并不十分苛刻的条件下,就需要,L=10,8,个信源符号进行联合编码,这显然是很难实现的。,27,5.2.2,变长编码定理,在,变长,编码中,码长,K,是变化,的。,我们可根据信源各个符号的,统计特性,如概率大的符号用短码,概率小的用较长的码,这样在大量信源符号编成码后平均每个信源符号所需的输出符号数就可以降低,从而提高编码效率,28,变长编码定理,单个符号变长编码定理：,若一离散无记忆信源的符号熵为,H(X),每个信源符号用,m,进制码元进行变长编码,一定存在一种无失真编码方法,其码字平均长度满足下列不等式,:,29,变长编码定理,离散平稳无记忆序列变长编码定理,对于平均符号熵为,H,L,(,X,),的离散平稳无记忆信源,必存在一种无失真编码方法,使平均信息率 满足不等式,其中,为任意小正数,30,A,B,C,D,E,F,G,H,I,J, , , , , , , , , ,K,L,M,N,O,P,Q,R,S,T, , , , , , , , , ,U,V,W,X,Y,Z,，,., , , , , , , , ,1,2,3,4,5,6,7,8,9,0, , , , , , , , , , ,Morse,电报字符,31,变长编码定理,用变长编码来达到相当高的编码效率,一般所要求的符号长度,L,可以比定长编码小得多。,编码效率的,下界,：,32,由,若对,例,5-2,用变长码实现,要求,90%,用二进制,m,2,log,2,m=l,。,得,L= 4,33,例,5-3,设离散无记忆信源概率空间,信源熵：,若用二元定长编码,(0,1),来构造一个,即时码,:,a,1,0,a,2,1,平均码长为,编码效率为,输出的信息效率为,34,再对长度为,L =2,的信源序列进行变长编码,其即时码如表,平均码长为,编码效率为,输出的信息效率,a,i,p,(,a,i,),即时码,a,1,a,1,a,1,a,2,a,2,a,1,a,2,a,2,9/16,3/16,3/16,1/16,0,10,110,111,单个符号的平均码长,35,将信源序列的长度增加,L,3,或,L=4,对这些信源序列,X,进行编码,并求出其编码效率为,信息传输率分别为,如果对这一信源采用定长二元码编码,要求编码效率达到,96,时,允许译码错误概率,10,-5,自信息的方差,所需要的信源序列长度,36,习题,5-1,37,