资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,单击此处编辑母版标题样式,第四章无失真信源编码,第四章 无失真信源编码,第一节 引言,第二节 码的分类,第三节 等长信源编码定理,第四节 变长信源编码定理,第五节 费诺编码,引言,通信的根本任务:有效、可靠地传输信息。,要把信源发出的消息所携带的信息,高速度、高质量的通过信道传送给接受者,存在,3,个问题:,第一,信源发出的符号有可能不适合信道的传输。,用信道能传输的符号作为码符号集,对信源发出的每一种符号进行一一对应的无失真编码。(无失真信源编码),第二,信道能够尽快地传输信源发出的符号,即要求编码有效,用尽量少的信道符号代表信源发出的每一个消息。,第三,在有扰有噪的信道中传输,码字应该具有抗干扰功能,具有一定的自动发现错误和纠错能力。(有噪离散信道编码),信源编码,:以,提高通信有效性,为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送,使单位时间内传送的平均信息量增加,从而提高通信的有效性。,信道编码,:是以,提高信息传输的可靠性,为目的的编码。通常通过增加信源的冗余度来实现。采用的一般方法是增大码率,/,带宽。与信源编码正好相反。,密码,:是以,提高通信系统的安全性,为目的的编码。通常通过加密和解密来实现。,第一节 引言,信源编码理论是信息论的一个重要分支,其理论基础是信源编码的两个定理。,无失真信源编码定理,:是离散信源,/,数字信号编码的基础;,限失真信源编码定理,:是连续信源,/,模拟信号编码的基础。,信源编码的分类:离散信源编码、连续信源编码和相关信源编码三类。,离散信源编码,:独立信源编码,可做到无失真编码;,连续信源编码,:独立信源编码,只能做到限失真信源编码;,相关信源编码,:非独立信源编码。,第一节 引言,第二节 码的分类,编码器可以看作这样一个系统,它的输入端为原始信源,S,,其符号集为 ;而信道所能传输的符号集,为 。编码器的功能是用符号集,X,中的元素,将原始信源的符号 变换为相应的码字符号 ,所以编码器输出端的符号集为,称为,码字,,为码字 的码元个数,称为码字 的码字长度,简称,码长,。,编码器,例,:,用,u,1,,,u,2,,,u,3,,u,4,表示信源的四个消息,码符号集为0,1,表3-1列出了该信源的几种不同编码。表,4-1,同一信源的几种不同编码,信源消息,各消息概率,码1,码2,码3,码4,u,1,q,(,u,1,),00,00,0,1,u,2,q,(,u,2,),11,01,1,10,u,3,q,(,u,3,),10,10,00,100,u,4,q,(,u,4,),11,11,11,1000,1,、,二元码:,码符号集,X=0,1,,如果要将信源通过二元信道传输,必须将信源编成二元码,这也是最常用的一种码。,2,、,等长码:,若一组码中所有码字的长度都相同,称为等长码。,3,、,变长码:,若一组码中所有码字的长度各不相同,称为变长码。,4,、,非奇异码:,若一组码中所有码字都不相同,称为非奇异码。,第二节 码的分类,5,、,奇异码:,若一组码中有相同的码字,称为奇异码。,6,、,码的,N,次扩展:,若码 ,码 则称码,B,为,码,C,的,N,次扩展码。,7,、,唯一可译码:,若码的任意一串有限长的码符号序列只能被唯一的译成所对应的信源符号序列,则称此码为,唯一可译码,或单义可译码,第二节 码的分类,例:如果有四个信源符号,s1,,,s2,,,s3,,,s4,,采用二元编码,,l=2,,则可以编成,s1=00,,,s2=01,,,s3=10,,,s4=11,。,第三节 等长信源编码定理,若对信源进行无失真等长编码,则必须满足,其中,,l,是码长,,r,是码符号集中的码元数,,q,是信源符号个数。,如果我们要对信源的,N,次扩展信源进行编码,也必须满足,两边取对数得:,表示平均每个信源符号所需的码符号个数。,例:对英文电报,的,32,个符号进行二元编码,根据上述关系:,我们已经知道英文的极限熵是,1.4bit,,远小于,5bit,,也就是说,,5,个二元码符号只携带,1.4bit,的信息量,实际上,,5,个二元符号最多可以携带,5bit,信息量。我们可以做到让平均码长缩短,提高信息传输率。,-,香农的信源编码,第三节 等长信源编码定理,定理,4.3,(等长信源编码定理),一个熵为,H(S),的离散无记忆信源,若对其,N,次扩展信源进行等长,r,元编码,码长为,l,,对于任意,大于,0,,只要满足,当,N,无穷大时,则可以实现几乎无失真编码,反之,若:,则不可能实现无失真编码,当,N,趋向于无穷大时,译码错误率接近于,1,。,第三节 等长信源编码定理,定理,4.3,的条件式可写成:,左边表示长为 的码符号所能载荷的最大信息量,而右边代表长为,N,的序列平均携带的信息量。因此,只要码字传输的信息量大于信源序列携带的信息量,总可以实现无失真编码。,定理,4.3,的条件式也可写成:,令 称之为,编码信息率或编码速率,。可见,编码信息率大于信源的熵,才能实现无失真编码。,第三节 等长信源编码定理,最佳编码效率为:,为了,衡量编码效果,,引进 称为,编码效率,。,当方差 和,均给定,且当允许错误概率小于,时,信源序列长度必须满足,或:,第三节 等长信源编码定理,只有,N,足够大时,编码效率才接近,1,例:设离散无记忆信源:,若采用等长二元编码,要求编码效率 ,允许错误率,,则:,也就是长度要达到,4130,万以上。,第三节 等长信源编码定理,由此可见,在差错率和效率要求都不苛刻的情况下,就必须有,4000,多万个信源符号一起编码,技术实现非常困难。,第四节 变长信源编码定理,不等长编码允许把等长的消息变换成不等长的码序列。,通常把经常出现的消息编成短码,,,不常出现的消息编成长码,。这样可使平均码长最短,从而提高通信效率,代价是增加了编译码设备的复杂度。,例如,在不等长码字组成的序列中要正确识别每个长度不同的码字的起点就比等长码复杂得多。,译码延时,/,译码同步,:接收到一个不等长码序列后,有时不能马上断定码字是否真正结束,因而不能立即译出该码,要等到后面的符号收到后才能正确译出。,信源符号,出现概率,码,1,码,2,码,3,码,4,s1,s2,s3,s4,1/2,1/4,1/8,1/8,0,11,00,11,0,10,00,01,1,10,100,1000,1,01,001,0001,第四节 变长信源编码定理,码,1,:显然不是惟一可译码。,码,2,:是非奇异码,不是惟一可译码。这种码从单个码字来看虽然不是奇异的,但从有限长的码序列来看,它仍然是一个奇异码。,码,3,:虽然是惟一可译码,但它要等到下一个“,1”,收到后才能确定码字的结束,译码有延时。,码,4,:既是惟一可译码,又没有译码延时。码字中的符号,“,1”,起了逗点的作用,故称为,逗点码,。,定义:如果一个码组中的任一个码字都不是另一个码字的延长或者找不到任何一个码字是另一个码字的前缀,或者说,任何一个码字后加上若干码元后都不是码组中另一个码字,则称为,即时码或非延长码,。也叫前缀条件码,/,异前置码,/,异字头码,/,逗点码,所有的码,非奇异码,唯一可译码,即时码,第四节 变长信源编码定理,图 码的分类结构图,下图是码的分类结构图,由上面的结构图可看出,将码分为奇异码和非奇异码两大类,我们只讨论非奇异码。非奇异码又分为惟一可译码和非惟一可译码两大类,我们只讨论惟一可译码,。,2,、即时码的树图构造法,我们可以用树图的形式构造即时码,如,0,1,0,0,1,1,1,1,01,001,0001,码,4,的树图,1,0,1,1,0,0,0,0,10,110,1110,码,3,的树图,树根,码字的起点,树枝数,码符号数,节点,树枝的尽头,阶数,码长,端点,码字,满树,等长码,非满树,变长码,第四节 变长信源编码定理,树根到每一阶节点路径树枝上的码符号作为一阶节点的各自的码符号序列,例,一个码,C,包含,4,个码字,码字集合为,1,01,000,001,试用码树来表示。,解:码树采用二进码树,如图,所示。,(,000,),0,0 1 (001),0 1,(01),R 1,(1),图码的二进码树表示,3,、克拉夫特(,Kraft,)不等式,定理,4.4,对于码符号为 的任意即时码,所对应的码长为 ,则必定满足:,反之,若码长满足上式,则一定存在这样的即时码。可以证明对于,唯一可译码也必须满足上面的不等式,。,定理,4.6,若存在一个码长为 唯一可译码,则一定存在一个同样长度的即时码。,第四节 变长信源编码定理,唯一可译码判别准则,唯一可译码判别准则,举例,设信源消息集合,x,1,x,2,x,3,x,4,x,5,x,6,x,7,,它们分别被编码为,a,c,ad,abb,bad,deb,bbcde,,可构造出下表所示的码符号集序列,S,0,S,1,S,2,S,3,S,4,S,5,S,6,S,7,a,d,eb,de,b,a,d,d,eb,c,bb,c,de,bcde,ad,abb,bad,deb,bbcde,当,n,7,时,,s,n,是空集,根据定义,因此,不,是唯一可译码,设信源,编码后的码字为:,,码长为:,则这个码的,平均码长,为:,平均每个码元携带的信息量即编码后的信息传输率为:,若有一个唯一可译码,它的平均码长小于其他唯一可译码的长度,则称此码为,紧致码,或,最佳码,,,无失真信源编码的基本问题就是寻找,紧致码,。,第四节 变长信源编码定理,平均码长和有效性的关系,待编码信源,S,是给定的,信源,S,每一个信源符号,s,i,所含有的平均信息量,等于信源,S,的熵,H(S),,其值不变的。而每一个码符号所携带的平均信息量,即码,W,的信息传输率为,,,它的高低取决于平均码长,。,因此平均码长 是衡量即时码的有效性高低的标准。,编码时不仅要考虑满足,Kraft,不等式,还要考虑码长和信源空间的合理搭配,充分挖掘信源的统计特性的潜力,使平均码长尽量小。,例如:信源空间为,设码符号集,0,1,,设码字长度分别为,l,1,=1,l,2,=2,l,3,=3,l,4,=3,1.,寻找唯一可译码存在的可能性,因为满足,Kraft,不等式,因此一定能构成至少一种即时码:,如,W(1):w,1,=0;w,2,=10;w,3,=110;w,4,=111;,W(2):w,1,=1;w,2,=01;w,3,=000;w,4,=001;,W(3):w,1,=0;w,2,=11;w,3,=100;w,4,=101;,这三个即时码的四个码字与信源符号集中的符号可以有不同搭配,所编出的码都,符合唯一可译码的条件,都是无失真信源编码,因此,即时码的形式不是唯一的。,不同的搭配得到的平均码长不同,从而效率也不同,如概率大的符号对应码长小的码字则,W(1):s,1,-w,1,=0;s,2,-w,2,=10;s,3,-w,3,=110;s,4,-w,4,=111,平均码长,如概率大的符号对应码长大的码字则,W(1):s,1,-w,1,=111;s,2,-w,2,=110;s,3,-w,3,=10;s,4,-w,4,=0,表明:要提高编码效率,就要使即时码的平均码长尽量小,就必须遵守概率大的信源符号尽量赋于短码;概率小的信源符号尽量赋于长码,2.,考虑编码的有效性,寻找最佳码,第四节 变长信源编码定理,平均码长决定了编码的信息传输率,问题:平均码长能否无限制地小?,平均码长的界限定理,平均码长的下界定理意义,采用正确的原则,合理搭配码字长度与信源符号的概率分布,可以使平均码长减小,但平均码长的,下降是有限度的,,,其下界值是,H(S)/,logr,。,在保持即时码所必须的结构条件,Kraft,不等式的条件下,平均码长绝对不会小于其下界值。,当且仅当信源符号,s,i,的概率分布,p(s,i,)=(1/r),li,时,且,l,i,均是正整数时,即时码的平均码长才能达到下界值,,此时的编码就是最佳码。,思考:,如果平均码长小于下界值,会怎样?,实际上,把下界值用换底公式变换,将对数的底变为码符号数,r,:,上界定理结论,:,平均码长不超过其上界值,H,r,(S)+1,的情况下,就可以构成即时码,但这并不意味着,超过这个上界就不能构成即时码,只是因为我们总是希望平均码长能够尽量小。,按照不等式 来确定码字长度,实际上也是一种即时码的构造方法,称之为,香农码,。,香农码,并不是最有效的,但可以直接根据信源符号的概率分布得到对应的码字应具有的长度的确切数字,给编码带来了一定的方便。,平均码长界限定理的思考?,若以,一个码字对应单个信源符号,来构造即时码,其平均码长的下界值就由给定的信源的熵值确定为,H(S)/,logr,,如果想进一步降低平均码长,提高通信的有效性,就要设法改变编码对象本身的信息特征。,若信源,S,发出的消息由,N,个符号组成,则,一条消息,可看做信源,S,的,N,次,扩展信源,S,的某一个符号,。编码时,只是一个完整的码字不再对应单个信源符号,而是对应扩展信源的符号,能否使平均码长有所下降?,也就是说能否用,扩展信源,的手段,达到数据压缩的目的,定理,4.8,无失真变长信源编码定理(香农第一定理),离散无记忆信源,S,的,N,次扩展信源 ,其熵为 ,并且编码器的码元符号集为,A,:,对信源 进行编码,总可以找到一种编码方法,构成唯一可译码,使信源,S,中每个符号,s,i,所需要的平均码长满足,当 则得:,第四节 变长信源编码定理,由,得:,就是编码后每个信源符号所携带的平均信息量,第一定理可以表述如下:,若 就,存在,唯一可译变长码,,若 则,不存在,唯一可译变长码。,定义:,对应,离散平稳有记忆信源,上述结论仍然成立,,H(S)=,H,;,M,阶马尔可夫信源,:,H(S)=,H,m+1,结论:,当平均码长达到极限值时,编码后信道的信息传输率为,logr,,也即是信道达到信道容量,无失真信源编码定理是香农信息论中非常重要,的,一个定理,也叫香农第一定理。,要做到无失真,的,信源编码,信源每个符号所需要的平均码元数就是信源的熵值,如果小于这个值,则唯一可译码不存在,可见,,熵,是无失真信源编码的极限值,。,通过对扩展信源进行编码,当,N,趋向于无穷时,平均码长可以趋进该极限值。,(可以通过扩展信源的方式 ),又因为要进行无失真传输,在无失真信源编码后,必须接入无噪信道,所以,,无失真信源编码定理,也可以称为无噪信道编码定理。,无失真信源编码定理小结,变长编码效率,:,码的剩余度,:,在二元无噪无损信道中:,在二元无噪无损信道中信息传输率:,编码效率与码的剩余度,为了,衡量编码效果,,引进,编码效率,。,例:,其熵为:,H(S)=0.811,。我们令,s,1,=0,,,s,2,=1,,这时平均码长 ,编码的效率为 。,二次扩展信源进行编码:,即时码,s1s1,9/16,0,s1s2,3/16,10,s2s1,3/16,110,s2s2,1/16,111,可见编码效率是提高的,小结,克拉夫特不等式和唯一可译码的判别准则告诉我们寻找的码是满足唯一可译性的。,树图法,-,构造唯一可译码,平均码长界限定理和变长编码定理,-,最佳码的界定,第五节 费诺编码,费诺编码,也是一种常见的概率匹配编码方法。,编码步骤如下:,将信源符号按其概率大小依次排列,令,p,(,x,1,),p,(,x,2,),p,(,x,n,),将依次排列的信源符号按概率值分组,使每组概率尽可能接近或相等。如编二进制码就分成两组,编,m,进制码就分成,m,组。,给每一组分配一位码元。,将每一分组再按同样原则划分,重复步骤,2,和,3,,直至每个组中只剩下一个信源符号为止。,例:设有一单符号离散信源,对该信源编二进制费诺码。编码过程如下表。,第六节 费诺编码,该信源的熵为:,平均码长为,:,编码效率为:,本例中费诺编码有较高的编码效率。费诺码比较适合于,每次分组概率都很接近,的信源。特别是对每次,分组概率都相等,的信源进行编码时,可达到理想的编码效率。,第六节 费诺编码,题中码字还可用码树来表示,如图所示。,第六节 费诺编码,
展开阅读全文