第5章 无失真信源编码定理精选文档.ppt
第5章 无失真信源编码定理本讲稿第一页，共三十一页n信源编码：以提高通信有效性为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。n信道编码：是以提高信息传输的可靠性为目的的编码。通常通过增加信源的冗余度来实现。采用的一般方法是增大码率/带宽。与信源编码正好相反。n密码：是以提高通信系统的安全性为目的的编码。通常通过加密和解密来实现。从信息论的观点出发，“加密”可视为增熵的过程，“解密”可视为减熵的过程。5.1 编码器编码器本讲稿第二页，共三十一页n信源编码理论是信息论的一个重要分支，其理论基础是信源编码的两个定理。n无失真信源编码定理：是离散信源/数字信号编码的基础；n限失真信源编码定理：是连续信源/模拟信号编码的基础。n信源编码的分类：离散信源编码、连续信源编码和相关信源编码三类。n离散信源编码：独立信源编码，可做到无失真编码；n连续信源编码：独立信源编码，只能做到限失真信源编码；n相关信源编码：非独立信源编码。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 编码器编码器本讲稿第六页，共三十一页例：如果有四个信源符号s1，s2，s3，s4，采用二元编码，l=2，则可以编成s1=00，s2=01，s3=10，s4=11。如果我们要对信源的N次扩展信源进行编码，也必须满足 ，两边取对数得：表示平均每个信源符号所需的码符号个数。若对信源进行等长编码，则必须满足其中，l是码长，r是码符号集中的码元数，q信源符号个数。5.2 等长码等长码本讲稿第七页，共三十一页例：对英文电报得32个符号进行二元编码，根据上述关系：我们继续讨论上面得例子，我们已经知道英文的极限熵是1.4bit,远小于5bit，也就是说，5个二元码符号只携带1.4bit的信息量，实际上，5个二元符号最多可以携带5bit信息量。我们可以做到让平均码长缩短，提高信息传输率5.2 等长码等长码本讲稿第八页，共三十一页 我们举例说明：设信源而其依赖关系为：5.2 等长码等长码本讲稿第九页，共三十一页若不考虑符号间的依赖关系，可得码长l2若考虑符号间的依赖关系，则对此信源作二次扩展 可见，由于符号间依赖关系的存在，扩展后许多符号出现的概率为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码4s1s2s3s41/21/41/81/801100110100001110100100010100100015.5 变长码变长码本讲稿第十七页，共三十一页 码1是一个奇异码，不是唯一可译码；码2也不是唯一可译码，因为收到一串序列是，无法唯一译出对应的原符号序列，如0100，即可译作s4s3s1,也可译作s4s1s3,s1s2s3或s1s2s1s1；码3和码4都是唯一可译的。但码3和码4也不太一样，码4称作逗点码，只要收到1，就可以立即作出译码；而码3不同，当受到一个或几个码是，必须参考后面的码才能作出判断。定义定义，在唯一可译码中，有一类码，它在译码是无须参考后面的码字就可以作出判断，这种码称为即时码。即时码也称为非延长码，前缀条件码。5.5 变长码变长码本讲稿第十八页，共三十一页定义定义：如果一个码组中的任一个码字都不是另一个码字的续长，或者说，任何一个码字后加上若干码元后都不是码组中另一个码字，则称为即时码。所有的码非奇异码唯一可译码即时码5.5 变长码变长码本讲稿第十九页，共三十一页2、即时码的树图构造法我们可以用树图的形式构造即时码，如01001111010010001码4的树图10110000101001000码3的树图树根码字的起点树枝数码的数节点数码字的一部分节数码长端点码字满树等长码非满树变长码5.5 变长码变长码本讲稿第二十页，共三十一页 在每个节点上都有r个分枝的树称为整树，否则称为非整树。即时码的树图还可以用来译码5.5 变长码变长码本讲稿第二十一页，共三十一页3、克拉夫特（Kraft）不等式定理定理5.55.5 对于码符号为 的任意即时码，所对应的码长为 ，则必定满足：反之，若码长满足上式，则一定存在这样的即时码。(定理5.4可以根据即时码的树图构造法来证明，略)B.McMillan证明了对于唯一可译码也必须满足上面的不等式。5.5 变长码变长码本讲稿第二十二页，共三十一页定理定理5.65.6 若存在一个码长为 唯一可译码，则一定存在一个同样长度的即时码。这说明，其他唯一可译码在码长方面并不比即时码占优。所以在讨论唯一可译码时，只需要讨论即时码就可以了。5.5 变长码变长码本讲稿第二十三页，共三十一页设信源编码后的码字为：码长为：则这个码的平均长度为：平均每个码元携带的信息量即编码后的信息传输率为：若有一个唯一可译码，它的平均码长小于其他唯一可译码的长度，则称此码为紧致码或最佳码，无失真信源编码的基本问题就是寻找紧致码。5.6 变长信源编码定理变长信源编码定理本讲稿第二十四页，共三十一页定理定理5.7 5.7 若一个离散无记忆信源S具有熵为H(s)，并且编码符号集为A：对信源进行编码，总可找到一种编码方法，构成单义可译码，使其平均码长满足 5.6 变长信源编码定理变长信源编码定理本讲稿第二十五页，共三十一页定理定理5.8 无失真变长信源编码定理（香农第一定理）无失真变长信源编码定理（香农第一定理）离散无记忆信源S的N次扩展信源 ，其熵为 ，并且编码器的码元符号集为A：对信源 进行编码，总可以找到一种编码方法，构成单义可译码，使信源S中每个符号si所需要的平均码长满足 当 则得：5.6 变长信源编码定理变长信源编码定理本讲稿第二十六页，共三十一页 这个定理是香农信息论中非常重要的一个定理，它指出，要做到无失真的信源编码，信源每个符号所需要的平均码元数就是信源的熵值，如果小于这个值，则唯一可译码不存在，可见，熵是无失真信源编码的极限值。定理还指出，通过对扩展信源进行编码，当N趋向于无穷时，平均码长可以趋进该极限值。还可以证明，如果我们不确切知道信源的概率分布，我们用估计的概率分布去进行编码时，平均码长会加长，但是如果估计的偏差不大的话，平均码长也不会增加太多（定理4.9的内容）。5.6 变长信源编码定理变长信源编码定理本讲稿第二十七页，共三十一页由得：就是编码后每个信源符号所携带的平均信息量第一定理可以表述如下：若 就存在唯一可译变长码，若 则不存在唯一可译变长码。5.6 变长信源编码定理变长信源编码定理定义：若从信道角度讲，信道的信息传输率因为：所以当平均码长达到极限值时，编码后信道的信息传输率为：本讲稿第二十八页，共三十一页无噪信道编码定理无噪信道编码定理 若信道的信息传输率R不大于信道容量C，总能对信源的输出进行适当的编码，使得在无噪无损信道上能无差错的以最大信息传输率C传输信息，若R小于C，则无差错传输是不可能的。5.6 变长信源编码定理变长信源编码定理 编码效率：码的剩余度：在二元无噪无损信道中：在二元无噪无损信道中信息传输率：本讲稿第二十九页，共三十一页例：其熵为：H(S)=0.811我们令s1=0，s2=1，这时平均码长 ，编码的效率为 。5.6 变长信源编码定理变长信源编码定理二次扩展信源进行编码：即时码s1s19/160s1s23/1610s2s13/16110s2s21/16111本讲稿第三十页，共三十一页n作业:5.1 5.2 5.4 n 5.6(选做)n谢谢本讲稿第三十一页，共三十一页
