信息论基础与编码 教学课件 作者 王军选 田小平 曹红梅 05章.ppt

信源编码：以提高通信有效性为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。 信道编码：是以提高信息传输的可靠性为目的的编码。通常通过增加信源的冗余度来实现。采用的一般方法是增大码率/带宽。与信源编码正好相反。 密码：是以提高通信系统的安全性为目的的编码。通常通过加密和解密来实现。从信息论的观点出发，“加密”可视为增熵的过程，“解密”可视为减熵的过程。 信源编码理论是信息论的一个重要分支，其理论基础是信源编码的两个定理。 无失真信源编码定理：是离散信源/数字信号编码的基础； 限失真信源编码定理：是连续信源/模拟信号编码的基础。 信源编码的分类：离散信源编码、连续信源编码和相关信源编码三类。 离散信源编码：独立信源编码，可做到无失真编码； 连续信源编码：独立信源编码，只能做到限失真信源编码； 相关信源编码：非独立信源编码。 Kraft不等式是惟一可译码存在的充要条件，其必要性表现在如果码是惟一可译码，则必定满足Kraft不等式;充分性表现在如果满足Kraft不等式，则这种码长的惟一可译码一定存在，但并不表示所有满足Kraft不等式的码一定是惟一可译码。 因此，克拉夫特不等式是惟一可译码存在的必要条件，而不是惟一可译码的充要条件。 唯一可译变长码的判断方法 根据上面的定理可知，不满足Kraft不等式的肯定不是唯一可译码，满足Kraft不等式的不一定是唯一可译码 根据定义的判断法：将码C中所有码字可能的尾随后缀组成一个集合F，当且仅当集合F中没有包含任何码字的时候，则码C为唯一可译码 唯一可译码的判断步骤 观察最短的码字是否是其它码字的前缀，如果是将所有可能的尾随后缀列出 观察上面的尾随后缀是否是其它码字的前缀，或者其它码字是这些尾随后缀的前缀，若是将由这些尾随后缀产生新的尾随后缀列出 ┇ 直到没有一个尾随后缀是其它码字的前缀或其它码字是它的前缀 由所有的尾随后缀构成集合F 判断F中是否有码字存在 例：判断C＝{0,10,1100,1110,1011,1101}是否为唯一可译码？ 解：首先判断是否满足Kraft不等式 最短的码字是0，不是其它码字的前缀，故没有尾随后缀 次短的码字是10，是码字1011的前缀，故产生一个尾随后缀11 第二步的尾随后缀11又是码字1100，1110以及1101的前缀，故可产生3各新的尾随后缀：00，10，01 此时码字0又是上面尾随后缀00，01的前缀，故产生新的尾随后缀0，1 同时上一步尾随后缀1，又是码字1100，1110，1011，1101的前缀，产生了新的尾随后缀：110，011，101 此时的F集合为：F＝{11，00，10，01，0，1，110，011，101} F集合了包含了码字0，10，所以C不是唯一可译码 例：判断码字C＝{110,11,100,00,10}是否为唯一可译码 解：首先判断是否满足Kraft不等式 最短的码字为11，00，10 首先看11，是码字110的前缀，故产生尾随后缀0 尾随后缀0不是任何码字的前缀，任何码字也不是它的前缀 再看00，不是任何码字的前缀，故没有尾随后缀产生 最后看10，是码字100的前缀，故产生尾随后缀0 尾随后缀0分析同上 集合F＝{0}，不包含任何码字 故码C是一个唯一可译码 5.2.1 定长编码定理 定理：由L个符号组成的、每个符号的熵为 的离散无记忆平稳信源符号序列X= ，可用K个符号 进行定长编码，且 香农第一定理指出，可选择每个码字的长度满足关系式： 或： ? x ? 表示不小于 x 的整数。按不等式选择的码长所构成的码称香农码。香农码满足克拉夫特不等式，所以一定存在对应码字的长度的惟一可译码。 一般情况下，按照香农编码方法编出来的码，其平均码长不是最短的，也即不是紧致码(最佳码)。只有当信源符号的概率分布使不等式左边的等号成立时，编码效率才达到最高。 例:设信源共有七个信源符号，其概率分布如下表所示，试对该信源进行香农编码。 解:计算过程见下页 码的性能分析： 通过计算可得此信源的熵: (比特／符号) 而码的平均长度: (二元码符号／符号