信息论第4章 无失真信源编码1.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第4,章 无失真信源编码,重庆交通大学信息科学与工程学院,通信工程系,李益才,2012年,8,月,第4,章 无失真信源编码,4.1,信源编码的相关概念,4.2,定长码及定长编码定理,4.3,变长码及变长编码定理,4.4,变长码的编码方法,4.5,实用的无失真信源码方法,4.1,信源编码的相关概念,4.1.1,编码器,信源输出的符号序列，需要变换成适合信道传输的符号序列，一般称为,码序列,，,对信源输出的原始符号按照一定的数学规则进行的这种变换称为,编码,，,完成编码功能的器件，称为,编码器,。,接收端有一个,译码器,完成相反的功能。,信源编码器的输入是信源符号集,，,共有,q,个信源符号。同时存在另一个符号集,，,称为码符号集，共有,r,个码符号，码符号集中的元素称为,码元,或,码符号,，,编码器的作用就是将信源符号集,S,中的符号 变换成由 个码符号组成的一一对应的码符号序列。编码器输出的码符号序列称为,码字,，,并用 来表示，它与信源符号 之间是一一对应的关系，如图,4.1,所示。,4.1.1,编码器,码字的集合,C,称为,码,，,即 。信源符号 对应的码字 包含 个码符号，称为,码字长度,，,简称,码长,。,所以，信源编码就是把信源符号序列变换到码符号序列的一种映射。若要实现,无失真编码,，,那么这种映射必须是一一对应的、可逆的。一般来说，人们总是希望把信源所有的信息毫无保留地传递到接收端，即实现无失真传递，所以首先要对信源实现无失真编码。,图4.1,信源编码器,4.1.1,编码器,信源编码有以下,3,种主要方法：,匹配编码,根据信源符号的概率不同，编码的码长不同：概率大的信源符号，所编的代码短；概率小的信源符号所编的代码长，这样使平均码长最短。这类编码主要有香农编码、哈夫曼编码、费诺码都是概率匹配编码，都是无失真信源编码。,变换编码,先对信号进行变换，从一种信号空间变换为另一种信号空间，然后针对变换后的信号进行编码。包括,DCT、DFT、DWT。,识别编码,识别编码主要用于印刷或打字机等有标准形状的文字符号和数据的编码，比如文字和语音的识别。,后两种信源编码均为有失真的信源编码。,无失真信源编码针对离散信源，连续信源在量化编码的过程中必然会有量化失真，连续信源只能近似地再现信源的消息。,4.1.2,码的分类,分组码和非分组码,定义,4.1,将信源符号集中的每个信源符号固定地映射成一个码字，这样的码称为,分组码,。,用分组码对信源符号进行编码时，为了使接收端能够迅速准确地将码译出，分组码必须具有一些直观属性。与分组码对应的是,非分组码,，,又称为,树码,、,树码编码器输出的码符号通常与编码器的所有信源符号都有关。,奇异码与非奇异码,定义,4.2,若一种分组码中的所有码字都不相同，则称此分组码为,非奇异码,，,否则称为,奇异码,。,4.1.2,码的分类,唯一可译码与非唯一可译码,定义,4.3,任意有限长的码元序列，如果只能唯一地分割成一个个码字，便称为唯一可译码。,唯一可译码的物理含义是指不仅要求不同的码字表示不同的信源符号，而且还要求对由信源符号构成的符号序列进行编码时，在接收端仍能正确译码而不发生混淆。唯一可译码首先是非奇异码，且任意有限长的码字序列不会雷同。,即时码与非即时码,定义,4.4,无需考虑后续的码符号就可以从码符号序列中译出码字，这样的唯一可译码称为即时码。,4.1.2,码的分类,下面讨论唯一可译码成为即时码的条件。,定义,4.5,设 为一码字，对于任意的 ，称码符号序列的前,j,个元素 为码字的前缀。,按照上述的前缀的定义，有下述结论：,定理,4.1,一个唯一可译码成为即时码,的充要条件是其中任何一个码字都不是,其他码字的前缀。,即时码可以用树图来构造图,5.2,是一个,二元即时码的树图,图5.2,二元即时码的树图,4.1.2,码的分类,树是没有回路的图，所以它也是由节点和弧构成的树中最顶部的节点称为,根节点,，,没有子节点的节点称为,叶子节点,。,所有根节点的子节点称为,一阶节点,，,所有一阶节点的子节点称为,二阶节点,，,依此类推。阶节点最多有 个。节点的阶次又称为节点的,深度,。,综上所述，可将信源编码作如下分类：,码,非分组码（树码）,分组码（块码）,奇异码,非奇异码,非唯一可译码,唯一可译码,即时码,非即时码,4.2,定长码及定长编码定理,若对一个有,q,个信源符号的信源,S,进行定长编码，那么信源,S,存在唯一可译定长码的条件是,(4.1),其中，,r,是码符号集中的码元数，,l,是定长码的码长。,如果对信源,S,的,N,次扩展信源 进行定长编码，若要编得的定长码是唯一可译码，则必须满足,(4.2),其中，,q,是信源,S,的符号个数，是信源,S,的,N,次扩展信源 的符号个数，,r,是码符号集,X,的码符号数。,4.2,定长码及定长编码定理,定长编码的信息传输效率是很低的。提高信息传输效率的方法有：,方法,1,考虑符号之间的依赖关系，对信源,S,的扩展信源进行编码。,方法,2,对于概率等于,0,或非常小的符号序列不予编码。,定理,4.2,离散无记忆信源的熵为,H(S),，,若对信源长为,N,的序列进行定长编码，码符号集,X,中有,r,个码符号，码长为,l,，,则对于任意,，,只要满足,则当,N,足够大时，可实现几乎无失真编码，即译码错误概率,任小；反之，如果,则不可能实现几乎无失真编码，即当,N,足够大时，译码错误概率为,1,。,4.2,定长码及定长编码定理,定理,5.2,可以在离散平稳无记忆信源的条件下得到证明的，但它同样适合于平稳有记忆信源，只要将式中,H(S),改为极限熵 即可，条件是有记忆信源的极限熵 和方差 存在。,定长信源编码定理给出了定长编码时每个信源符号最少所需的码符号的理论极限，该极限值由,H(S),决定。,定义,4.6,设熵为,H(S),的离散无记忆信源，若对信源的长为,N,的符号序列进行定长编码，码符号集中码符号个数为,r,，,设码字长为,l,，,定义 比特,/,信源符号为,编码速,率,，,它表示平均每个信源符号编码后能载荷的最大信息量。,这时，定理,4.2,的条件可表述为,R,H(S)+,，,即编码速率大于信源的熵才能实现几乎无失真编码。为了衡量编码效果，引进编码效率。,4.2,定长码及定长编码定理,定义,4.7,定义 为,编码效率,。,由定理,4.2,可得最佳编码效率为 ，所以在已知方差和信源熵的条件下，信源符号序列长度,N,与最佳编码效率,和允许错误概率 的关系为：,当允许错误概率越小，编码效率又要高，那么信源符号序列长度,N,必须越长在实际情况下，要实现几乎无失真的定长编码，,N,需要的长度将会大到难以实现。,4.3,变长码及变长编码定理,4.3.1,Kraft,不等式和,McMillan,不等式,定理,4.3,设信源符号集为,，,码符号集为 ，对信源进行编码，得到的码为 ，码长分别为 。即时码存在的充要条件是,这称为,Kraft,不等式,。,由,Kraft,不等式可知，给定,r,和,q,，,只要允许码字长度可以足够长，则码长总可以满足,Kraft,不等式而得到即时码，,Kraft,不等式指出了即时码的码长必须满足的条件,对于唯一可译码，该不等式又称为,McMillan,不等式。,(4.11),4.3.1,Kraft,不等式和,McMillan,不等式,定理,4.4,唯一可译码存在的充要条件是,r,为码符号个数，,li,为码字长度，,q,为信源符号个数。,定理,4.4,指出了唯一可译码中,r、q,、,之间的关系，如果满足这个不等式的条件，则一定能够构成至少一种唯一可译码，否则，无法构成唯一可译码它给出了唯一可译变长码的存在性。,另外，从定理,4.3,和定理,4.4,可以得到一个重要的结论，即任何一个唯一可译码均可用一个相同码长的即时码来代替，因为即时码很容易用树图法构造，因此要构造唯一可译码，只要构造即时码就可以了。,(4.12),4.3.2,唯一可译码的判别准则,A.A.,Sardinas,和,G.W.Patterson,于1957,年提出下述算法用于判断码,C,的唯一可译性此算法的原理如下所示：,其中 都是码字。可知，当且仅当某个有限长的码符号序列能译成两种不同的码字序列时，此码不是唯一可译码，此时 一定是 的前缀，而 的尾随后缀一定是另一码字 的前缀；而 的尾随后缀又是其他码字的前缀最后，码符号序列的尾部一定是一个码字。,4.3.2,唯一可译码的判别准则,设,C,为码字集合，按以下步骤构造此码的尾随后缀集合,F,：,考查,C,中所有的码字，若 是 的前缀，则将相应的后缀作为一个尾随后缀码放入集合 中；,考查,C,和 两个集合，若 是 的前缀或 是 的前缀，则将相应的后缀作为尾随后缀码放入集合 中；,即为码,C,的尾随后缀集合；,若,F,中出现了,C,中的元素，则算法终止，返回假,(,C,不是唯一可译码,),；否则若,F,中没有出现新的元素，则返回真。,定理,4.5,一个码是唯一可译码的充要条件是的 并集中没有,C,中的码字。,4.3.3,无失真变长编码定理,定义,4.8,设有信源,编码后的码字分别为,，,各码字相应的码长分别为,li,因为是唯一可译码，信源符号 和码字 一一对应，则定义此码的,平均码长,为,其中，表示每个信源符号平均需用的码元数。,当信源给定时，信源熵,H(S),就确定了，而编码后每个信源符号平均用 个码元来变换，故平均每个码元载荷的信息量即编码后信源的信息传输率。,码符号,/,信源符号,(4.20),4.3.3,无失真变长编码定理,定义,4.9,编码后信源的信息传输率为,如果传输一个码符号平均需要,t,秒时间，则编码后信源每秒钟提供的信息量为,可以看出，越小，则 越大，信息传输率就越高，因此我们感兴趣的码是使平均码长 最短的码。,定义,4.10,对于给定的信源和码符号集，若有一个唯一可译码，其平均码长 小于所有其他唯一可译码，则称这种码为,紧致码,或,最佳码,。,无失真信源编码的核心问题就是寻找紧致码,比特,/,码符号,(4.21),(4.22),4.3.3,无失真变长编码定理,下面的定理给出了紧致码的平均码长可能达到的理论极限,定理,4.6,若一个离散无记忆信源,S,，,熵为,H(S),，,用拥有,r,个码符号的码符号集 对,S,进行无失真编码，则总可以找到一种唯一可译码，其平均码长满足,若熵以,r,进制为单位，则式,(4.23),可写成,另外还可以看到平均码长的极限值与无失真定长信源编码定理中的极限值是一致的。,(4.23),(4.33),4.3.4,香农第一编码定理,定理,4.7,设离散无记忆信源,S,的信源熵,H(S),，,它的,N,次扩展信源 ，其熵 。并用码符号 对信源 进行编码，总可以找到一种唯一可译码，使信源,S,中每个信源符号所需的平均码长满足,或者写成,定理,4.6,可以看作定理,5.7在,N,=1,时的特殊情况。,定理,4.7,是香农信息论的主要定理之一。,(4.34),(4.35),4.3.4,香农第一编码定理,定义,4.11,编码后信道的,信息传输率,为,这里，,，,所以,无失真信源编码的实质就是对离散信源进行适当的变换，使变换后新的码符号信源,(,信道的输入,),尽可能为等概率分布，使新信源的每个码符号平均所含的信息量达到最大，从而使信道的信息传输率,R,达到信道容量，实现信源与信道理想的统计匹配。这就是香农第一定理的物理意义。,比特,/,码符号,(4.43),比特,/,信源符号,码符号,/,信源符号,4.3.4,香农第一编码定理,为了衡量各种编码是否已达到极限情况，我们定义变长码的编码效率。,定义,4.12,设对信源,S,进行无失真编码所得到的平均码长为,，,则 ，定义,为,编码效率,，,对同一信源来说，码的平均码长 越短，越接近极限,，,信道的信息传输率越高，越接近无噪无损信道的信道容量，这时,也越接近于,1,，所以用码的效率,来衡量各种编码的优劣。,(5.44),4.3.4,香农第一编码定理,另外，为了衡量各种编码与最佳码的差距，引入码的剩余度的概念。,定义,4.13,定义,为码的,剩余度,。,在二元无噪无损信道中,r,=2，,所以在二元无噪无损信道中信息传输率,注意它们数值相同，单位不同,是个无单位的比值，而,R,的单位是比特,/,码符号。,(4.45),4.4,变长码的编码方法,本章介绍的变长码的常见编码方法，如香农编码、香农,-,费诺,-,埃利斯编码、霍夫曼编码、费诺编码均为匹配编码，也称,统计编码,，,都是通过使用较短的码字来给出现概率较高的信源符号编码。而出现概率较小的信源符号用较长的码字来编码，从而使平均码长最短，达到最佳编码的目的。下面介绍这几种方法：,4.4.1,香农编码,香农码的方法是选择每个码字长度 满足,按照香农编码方法构造的码，其平均码长 不超过上界，即,4,.4.1 香农,编码,其具体方法如下：,(1),将信源发出的,q,个消息符号按其概率的递减次序排列,(2),计算出各个信源符号的累加概率,(3),按下式计算第,i,个消息的二元代码组的码长,(4),将累加概率,(,十进制小数,),变换成二进制小数。根据码长 取小数点后 个二进制符号作为第,i,个消息的码字。,4.4.3,霍夫曼编码,霍夫曼于,1952,年提出的一种构造紧致码的方法具体方法如下：,(1),q,将个信源符号按概率大小递减排列,(2),用“,0，1”,码符号分别代表概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个，从而得到只包含,q,-1,个符号的新信源，称为缩减信源,；,(3),把缩减信源 的符号仍按概率大小递减次序排列，再将其最后两个概率最小的信源符号分别用“,0”,和“,1”,码符号表示，并且合并成一个符号，这样又形成了,q,-2,个信源符号的缩减信源,；,(4),依次继续下去，直至信源最后只剩下两个信源符号为止，将这最后两个信源符号分别用二元码符号“,0”,和“,1”,表示；,(5),然后从最后一级缩减信源开始，进行回溯，就得到各信源符号所对应的码符号序列，即相应的码字。,4.4.3,霍夫曼编码,霍夫曼编码方法得到的码并非是唯一的。,(1),每次对信源缩减时，赋予最后两个概率最小的信源符号的码符号“,0”,和“,1”,是可以互换的，所以可得到不同的霍夫曼码；,(2),对信源进行缩减时，如果两个概率最小的信源符号合并后的概率与其他信源符号的概率相同，则在进行概率排序时的次序是任意的，因此会得到不同的霍夫曼码。,霍夫曼码是用概率匹配的方法进行信源编码：,(1),霍夫曼码的编码方法保证了概率大的信源符号对应的码长小，概率小的信源符号对应的码长大，充分利用了短码；,(2),每次缩减信源的最长两个码字有相同的码长，并且仅仅只有最后一位码符号不同。,定理,4.8,霍夫曼码是紧致码。,4.4.5,费诺编码,费诺码编码过程如下：,(1),将信源符号 以概率递减次序排列，即,(2),将依次排列的信源符号以概率分为两组，使两个组的概率和基本相等，并对各组赋予二元码符号“,0”,和“,1”,；,(3),将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率和近于相等，又分别赋予各组二元码符号“,0”,和“,1”,；,(4),如此重复，直至每组只剩下一个信源符号为止；,(5),信源符号所对应的码符号序列即为费诺码,编码,平均码长,信息传输率,R,香农码,霍夫曼,费诺码,3.14,2.72,2.74,0.831,0.959,0.953,以上讨论了霍夫曼码和其他一些编码方法，并且证明了霍夫曼码是最佳码，当,N,不很大时，它能使无失真编码的效率接近于,1,，但是在实际使用时设备较复杂。,首先，每个信源符号所对应的码,长不同，一般情况下，信源符号,以匀速输出，信道也是匀速传输,的。,其次，差错扩散的问题变长码,的一个码元的差错可能造成译码,错误，并且还会造成同步错误，,结果后面一系列码字也会译错。,最后，霍夫曼码的编译码需要用,查表的方法来进行。,表4.15,三种编码方法的比较,