第五章：无失真编码2.ppt

无失真信源编码 无失真信源编码 无失真编码概述 定长信源编码 变长信源编码 实用的无失真信源编码方法举例 §5.1无失真编码器－1 离散、无失真、无记忆信源编码的一般模型： §5.1无失真编码器－2 问题：能否进行无失真编码，怎样进行无失真编码 若：不考虑信源统计特性： 应满足条件： 相互矛盾！ §5.1无失真编码器－3 考察无失真条件： 分别表示等概条件下的消息熵 与码字熵 之比， 考虑信源的实际统计特性（非等概），实际消息熵为： 代入无失真条件得： 此时：即使q=r,只要 就有可能实现lN。 即无失真与有效性同时满足。 具体实现时：定长与变长编码 §5.2分组码(几个码类的概念) 非奇异码： 每一个码字仅对应信源中的一个信源符号（序列）。 编码是单义的。编码Ⅱ 反之为奇异码或非单义码。编码Ⅰ §5.2分组码(几个码类的概念) 唯一可译码 编码单义、译码单义 对任何一个有限长度的信源字母序列，如果编码得到的码字母序列不与其他任何信源字母序列所对应的码字母序列相同。编码Ⅰ 编码Ⅱ §5.2分组码(几个码类的概念) 即时码(前缀码) 是一类唯一可译码 在一个变长码中，没有任何一个码字是其他码字的前缀。 译码时无需参考后续的码符号就能立即作出判断，进行无延时译码。 又称前缀码、非延时码 §5.2分组码(几个码类的概念) 最佳码 唯一可译码的一类 其平均码长小于其他唯一可译码的平均长度 §5.2分组码(几个码类的概念)例3： §5.3定长编码定理－1 定长编码定理 描述 证明 物理意义 实际应用中的问题 §5.3定长编码定理－2-描述 定长（等长）码信源编码定理： 对离散，无记忆、平稳、遍历信源其符号序列：S =(S1,S2 …..Sq)， 可用r个符号C =(C1,C2….Cr) 进行等长编码，对任意ε0,δ0， 只要满足： (l/N)log r≥H(S)+ε 则：当N足够大时，可使译码差错小于δ， 反之，当 (l/N)logr≤H(S)-2ε 时，译码一定出错。 解释：定长编码定理给出了信源进行等长编码所需码长的理论极限值。 § 5.3定长编码定理－2-进一步理解 若要求变得的等长码是唯一可译的，则必须： 若N＝1，则： 结论：对于唯一可译码，每个信源符号至少需要用 个码符号来变换。 当采用二元码编码时，r＝2，则： 结论：对信源进行二元等长编码时，每个信源符号所需码长的极限值为 例1：英文电报有32个符号（26＋6），即q=32， 若r=2，N＝1（即对信源的逐个符号进行二元编码）， 则： 解释：每个英文电报符号至少需要用5位二元符号编码 问题：第三章：在考虑符号出现的概率和符号间相关性前提下,每个英文符 号平均携带的信息量是1.4bit/符号（ ），5bit/符号， 等长编码效率极低，如何提高效率？如何体现有效性？ 解决方法： 考察：字母个数为n，字母出现非等概，且字母之间相关长度为L的英文信源，其可能的字母序列总数为 ；但其中大部分字母序列是无意义的字母组合，而且随着N的增加，这种无意义序列的总数越来越大。 方法：进行联合编码，即对字母序列编码，且只对哪些有意义的字母序列编码，即需编码的字母序列的总数 ,则平均每个信源符号所需的码符号个数可以大大减少，从而提高了传输效率。 问题：会引入一定的误差，当N足够长后，误差可以任意小。 § 5.3定长编码定理－3－证明 考察离散、随机序列信源的统计特性 －－渐进等分割性（AEP） AEP描述： 渐进等分割定理： （熵定理，遍历性定理） 设 是离散无记忆信源输出的一个特定序列，则任给 和 ，总可以找到一个整数 ，使当 时，有： § 5.3定长编码定理－4－ AEP物理意义 任何一个离散随机序列信源当序列长度Ｌ→∝时,信源序列会产 生两极分化.