第5章 无失真信源编码定理.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第五章 无失真信源编码定理,5.1,编码器,5.2,等长码,5.3,渐近等分割性和,典型序列,5.4,等长信源编码定理,5.6,变长信源编码定理,5.5,变长码,信源编码,：以,提高通信有效性,为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。,信道编码,：是以,提高信息传输的可靠性,为目的的编码。通常通过增加信源的冗余度来实现。采用的一般方法是增大码率,/,带宽。与信源编码正好相反。,密码,：是以,提高通信系统的安全性,为目的的编码。通常通过加密和解密来实现。从信息论的观点出发，“加密”可视为增熵的过程，“解密”可视为减熵的过程。,5.1,编码器,信源编码理论是信息论的一个重要分支，其理论基础是信源编码的两个定理。,无失真信源编码定理,：是离散信源,/,数字信号编码的基础；,限失真信源编码定理,：是连续信源,/,模拟信号编码的基础。,信源编码的分类：离散信源编码、连续信源编码和相关信源编码三类。,离散信源编码,：独立信源编码，可做到无失真编码；,连续信源编码,：独立信源编码，只能做到限失真信源编码；,相关信源编码,：非独立信源编码。,5.1,编码器,编码器可以看作这样一个系统，它的输入端为原始信源,S,，,其符号集为 ；而信道所能传输的符号集,为,编码器的功能是用符号集,X,中的元素，将原始信源的符号 变换为相应的码字符号,，,所以编码器输出端的符号集为,称为,码字,，为码字 的码元个数，称为码字 的码字长度，简称,码长,。,编码器,5.1,编码器,1,、,二元码：,码符号集,X=0,1,，,如果要将信源通过二元信道传输，必须将信源编成二元码，这也是最常用的一种码。,2,、,等长码：,若一组码中所有码字的长度都相同，称为等长码。,3,、,变长码：,若一组码中所有码字的长度各不相同，称为变长码。,4,、,非奇异码：,若一组码中所有码字都不相同称为非奇异码。,5.1,编码器,5,、,奇异码：,若一组码中有相同的码字，称为奇异码。,6,、同价码,:,每个码字占相同的传输时间,7,、,码的,N,次扩展：,若码 ，码 则称码,B,为,码,C,的,N,次扩展码。,8,、,唯一可译码：,若码的任意一串有限长的码符号序列只能被唯一的译成所对应的信源符号序列，则称此码为,唯一可译码,。,5.1,编码器,例：如果有四个信源符号,s,1,，,s,2,，,s,3,，,s,4,，,采用二元编码，,l,=2,，,则可以编成,s,1,=00,，,s,2,=01,，,s,3,=10,，,s,4,=11,。,如果我们要对信源的,N,次扩展信源进行编码，也必须满足,，两边取对数得：,表示平均每个信源符号所需的码符号个数。,若对信源进行等长编码，则必须满足,其中，,l,是码长，,r,是码符号集中的码元数，,q,信源符号个数。,5.2,等长码,例：对英文电报得,32,个符号进行二元编码，根据上述关系：,我们继续讨论上面得例子，我们已经知道英文的极限熵是,1.4bit,远小于,5bit,，,也就是说，,5,个二元码符号只携带,1.4bit,的信息量，实际上，,5,个二元符号最多可以携带,5bit,信息量。我们可以做到让平均码长缩短，提高信息传输率,5.2,等长码,我们举例说明：,设信源,而其依赖关系为：,5.2,等长码,若不考虑符号间的依赖关系，可得码长,l,2,若考虑符号间的依赖关系，则对此信源作二次扩展,可见，由于符号间依赖关系的存在，扩展后许多符号出现的概率为,0,，此信源只有,4,个字符，可得码长 ，但平均每个信源符号所需码符号为,5.2,等长码,我们仍以英文电报为例，在考虑了英文字母间的相关性之后，我们对信源作,N,次扩展，在扩展后形成的信源（也就是句子）中，有些句子是有意义的，而有些句子是没有意义的，我们可以只对有意义的句子编码，而对那些没有意义的句子不进行编码，这样就可以缩短每个信源符号所需的码长。,等长信源编码定理给出了进行等长信源编码所需码长的极限值。,5.2,等长码,5.3,渐近等分割性和,典型序列,(,本节略,),本节的主要是为了证明信源编码定理，而引入了一种,渐近等分割性和,典型序列的重要概念。,定理,5.3,（等长信源编码定理）,一个熵为,H,(,S,),的离散无记忆信源，若对其,N,次扩展信源进行等长,r,元编码，码长为,l,，,对于任意 大于,0,，只要满足,当,N,无穷大时，则可以实现几乎无失真编码，反之，若：,则不可能实现无失真编码，当,N,趋向于无穷大时，译码错误率接近于,1,。,5.4,等长信源编码定理,定理,5.3,的条件式可写成：,左边表示长为 的码符号所能载荷的最大信息量，而右边代表长为,N,的序列平均携带的信息量。因此，只要码字传输的信息量大于信源序列携带的信息量，总可以实现无失真编码。定理,5.3,的条件式也可写成：,令：,称之为,编码信息率,。可见，编码信息率大于信源的熵，才能实现无失真编码。,5.4,等长信源编码定理,最佳编码效率为：,为了衡量编码效果，引进,称为,编码效率,。,5.4,等长信源编码定理,例：设离散无记忆信源：,若采用等长二元编码，要求编码效率 ，允许错误率,，则：,也就是长度要达到,4130,万以上。,5.4,等长信源编码定理,1,、唯一可译变长码与及时码,信源符号,出现概率,码1,码2,码3,码4,s,1,s,2,s,3,s,4,1/2,1/4,1/8,1/8,0,11,00,11,0,10,00,01,1,10,100,1000,1,01,0010001,5.5,变长码,码,1,是一个奇异码，不是唯一可译码；码,2,也不是唯一可译码，因为收到一串序列是，无法唯一译出对应的原符号序列，如,0100,，即可译作,s,4,s,3,s,1,也可译作,s,4,s,1,s,3,s,1,s,2,s,3,或,s,1,s,2,s,1,s,1,；码,3,和码,4,都是唯一可译的。,但码,3,和码,4,也不太一样，码,4,称作逗点码，只要收到,1,，就可以立即作出译码；而码,3,不同，当受到一个或几个码是，必须参考后面的码才能作出判断。,定义,，在唯一可译码中，有一类码，它在译码是无须参考后面的码字就可以作出判断，这种码称为,即时码,。,即时码也称为,非延长码,，,前缀条件码,。,5.5,变长码,定义,：如果一个码组中的任一个码字都不是另一个码字的续长，或者说，任何一个码字后加上若干码元后都不是码组中另一个码字，则称为,即时码,。,所有的码,非奇异码,唯一可译码,即时码,5.5,变长码,2,、即时码的树图构造法,我们可以用树图的形式构造即时码，如,0,1,0,0,1,1,1,1,01,001,0001,码,4,的树图,1,0,1,1,0,0,0,0,10,100,1000,码,3,的树图,树根,码字的起点,树枝数,码的数,节点数,码字的一部分,节数,码长,端点,码字,满树,等长码,非满树,变长码,5.5,变长码,在每个节点上都有,r,个分枝的树称为,整树,，否则称为,非整树,。,即时码的树图还可以用来译码,5.5,变长码,3,、克拉夫特（,Kraft,）,不等式,定理,5.5,对于码符号为 的任意即时码，所对应的码长为 ，则必定满足：,反之，若码长满足上式，则一定存在这样的即时码。,(,定理,5.4,可以根据即时码的树图构造法来证明，略,),B.McMillan,证明了对于唯一可译码也必须满足上面的不等式。,5.5,变长码,定理,5.6,若存在一个码长为 唯一可译码，则一定存在一个同样长度的即时码。,这说明，其他唯一可译码在码长方面并不比即时码占优。所以在讨论唯一可译码时，只需要讨论即时码就可以了。,5.5,变长码,设信源,编码后的码字为：,码长为：,则这个码的平均长度为：,平均每个码元携带的信息量即编码后的信息传输率为：,若有一个唯一可译码，它的平均码长小于其他唯一可译码的长度，则称此码为,紧致码,或,最佳码,，无失真信源编码的基本问题就是寻找紧致码。,5.6,变长信源编码定理,定理,5.7,若一个离散无记忆信源,S,具有熵为,H,(,s,),，并且编码符号集为,A,：,对信源进行编码，总可找到一种编码方法，构成单义可译码，使其平均码长满足,5.6,变长信源编码定理,定理,5.8,无失真变长信源编码定理（香农第一定理）,离散无记忆信源,S,的,N,次扩展信源 ，其熵为 ，并且编码器的码元符号集为,A,：,对信源 进行编码，总可以找到一种编码方法，构成单义可译码，使信源,S,中每个符号,s,i,所需要的平均码长满足,当 则得：,5.6,变长信源编码定理,这个定理是香农信息论中非常重要的一个定理，它指出，要做到无失真的信源编码，信源每个符号所需要的平均码元数就是信源的熵值，如果小于这个值，则唯一可译码不存在，可见，,熵是无失真信源编码的极限值,。定理还指出，通过对扩展信源进行编码，当,N,趋向于无穷时，平均码长可以趋进该极限值。,还可以证明，如果我们不确切知道信源的概率分布，我们用估计的概率分布去进行编码时，平均码长会加长，但是如果估计的偏差不大的话，平均码长也不会增加太多（定理,4.9,的内容）。,5.6,变长信源编码定理,由,得：,就是编码后每个信源符号所携带的平均信息量,第一定理可以表述如下：若 就存在唯一可译变长码，若 则不存在唯一可译变长码。,5.6,变长信源编码定理,定义：,若从信道角度讲，信道的信息传输率,因为：,所以,当平均码长达到极限值时，编码后信道的信息传输率为：,无噪信道编码定理,若信道的信息传输率,R,不大于信道容量,C,，,总能对信源的输出进行适当的编码，使得在无噪无损信道上能无差错的以最大信息传输率,C,传输信息，若,R,小于,C,，,则无差错传输是不可能的。,5.6,变长信源编码定理,编码效率：,码的剩余度：,在二元无噪无损信道中：,在二元无噪无损信道中信息传输率：,例：,其熵为：,H,(,S,)=0.811,我们令,s,1,=0,，,s,2,=1,，,这时平均码长 ，编码的效率为 。,5.6,变长信源编码定理,二次扩展信源进行编码：,即时码,s,1,s,1,9/16,0,s,1,s,2,3/16,10,s,2,s,1,3/16,110,s,2,s,2,1/16,111,作业,:5.1 5.2 5.4,5.6(,选做,),谢谢,