第5章信源编码讲述.ppt

普通高等教育“十一五”国家级规划教材《信息论基础》 曹雪虹编著 第5章　信源编码 编码分为信源编码和信道编码，其中信源编码又分为无失真和限失真。 一般称 第一极限定理：无失真信源编码定理 第二极限定理：信道编码定理 第三极限定理：限失真信源编码定理 第5章　信源编码 信源存在冗余度 原因是信源符号之间存在概率分布不均匀和相关性 信源编码的主要任务就是减少冗余，提高编码效率。 第5章　信源编码 信源编码的基本途径有两个： 使序列中的各个符号尽可能地互相独立，即解除相关性； 使编码中各个符号出现的概率尽可能地相等，即概率均匀化。 第5章　信源编码 信源编码的作用可归纳为： (1) 符号变换：使信源的输出符号与信道的输入符号相匹配； (2) 冗余度压缩：使编码效率等于或接近100％。 第5章　信源编码 信源编码的基础是信息论中的两个编码定理： 无失真编码定理 限失真编码定理 无失真编码可精确复制信源输出的消息，只适用于离散信源 对于连续信源，只能在失真受限制的情况下进行限失真编码 第5章　信源编码 本章讨论离散信源编码，首先从无失真编码定理出发，重点讨论以香农码、费诺码和霍夫曼码为代表的最佳无失真码。然后介绍了限失真编码定理。最后简单介绍了一些其它常用的信源编码方法。 5.1 编码的定义 5.1 编码的定义 将信源消息分成若干组，即符号序列xi， xi＝(xi1xi2…xil…xiL)， xil?A={a1，a2，…，ai，…，an} 每个符号序列xi依照固定码表映射成一个码字yi， yi＝(yi1yi2…yil…yiL)， yil?B={b1，b2，…，bi，…，bm} 这样的码称为分组码，有时也叫块码。只有分组码才有对应的码表，而非分组码中则不存在码表。 5.1 编码的定义 如图5-1所示，如果信源输出符号序列长度L＝1，信源符号集A(a1，a2，…，an) 信源概率空间为 5.1 编码的定义 5.1 编码的定义 码可分为两类： 一、固定长度的码，码中所有码字的长度 都相同，如表5-1中的码1就是定长码 二、可变长度码，码中的码字长短不一，如表中其他码都是变长码。 5.1 编码的定义 （1）奇异码和非奇异码 若信源符号和码字是一一对应的，则该码为非奇异码。反之为奇异码。 如表5-1中的码2是奇异码，码3是非奇异码。 5.1 编码的定义 （2）唯一可译码 任意有限长的码元序列，只能被唯一地分割成一个个的码字，便称为唯一可译码 5.1 编码的定义 （3）非即时码和即时码 唯一可译码中又分为非即时码和即时码：如果接收端收到一个完整的码字后，不能立即译码，还需等下一个码字开始接收后才能判断是否可以译码，这样的码叫做非即时码。 5.1 编码的定义 即时码：只要收到符号就表示该码字已完整，可以立即译码。 即时码又称为非延长码，任意一个码字都不是其它码字的前缀部分，有时叫做异前缀码。 5.1 编码的定义 5.1 编码的定义 通常可用码树来表示各码字的构成 5.1 编码的定义 码树与码字对应关系图 5.1 编码的定义 唯一可译码存在的充分和必要条件 各码字的长度Ki 应符合克劳夫特不等式： 5.1 编码的定义 例：设二进制码树中X (a1， a2 ， a3 ， a4 )，K1＝1，K2＝2，K3＝2，K4＝3，应用上述判断定理： 5.1 编码的定义 5.1 编码的定义 克劳夫特不等式只是用来说明唯一可译码是否存在，并不能作为唯一可译码的判据。 5.2 无失真信源编码 用Y表示L长的信源序列X，则送出一个信源符号所需要的信息率平均为 编码目的：使 最小 5.2 无失真信源编码 无失真信源编码定理研究的内容: 最小信息率为多少时，才能得到无失真的译码？ 若小于这个信息率是否还能无失真地译码? 5.2 无失真信源编码 无失真的信源编码定理 定长编码定理 变长编码定理 5.2 无失真信源编码 定长编码定理： 无记忆平稳信源平均符号熵为HL(X)， 只要 则当L足够大时，必可使译码差错足够小； 反之，当 时，译码差 错一定是有限值，而L足够大时，译码几乎必定出错。 5.2 无失真信源编码 定长编码定理说明， 5.2 无失真信源编码 反之，当 时，不可能构成无失真的编