《信息论与编码-第五章.》由会员分享，可在线阅读，更多相关《信息论与编码-第五章.（171页珍藏版）》请在金锄头文库上搜索。
1、信息论与编码-信源编码 通信的实质是信息的传输。而高速度、高质量 地传送信息是信息传输的基本问题。 将信源信息通过信道传送给信宿，怎样才能做 到尽可能不失真而又快速呢？这就需要解决两 个问题： 第一，在不失真或允许一定失真的条件下，如 何用尽可能少的符号来传送信源信息； 第二，在信道受干扰的情况下，如何增加信号 的抗干扰能力，同时又使得信息传输率最大。 为了解决这两个问题，就要引入信源编码和信 道编码。 信息论与编码-信源编码 一般来说，提高抗干扰能力（降低失真或错误 概率）往往是以降低信息传输率为代价的；反 之，要提高信息传输率常常又会使抗干扰能力 减弱。二者是有矛盾的。 然而在信息论的编码
2、定理中，已从理论上证明 ，至少存在某种最佳的编码或信息处理方法， 能够解决上述矛盾，做到既可靠又有效地传输 信息。这些结论对各种通信系统的设计和估价 具有重大的理论指导意义。 信息论与编码-信源编码 编码分为信源编码和信道编码， 信源编码又分为无失真和限失真。 由于这些定理都要求符号数很大才能使它的值 接近所规定的值，因而这些定理被称为极限定 理。 一般称无失真信源编码定理为第一极限定理； 信道编码定理（包括离散和连续信道）称为第 二极限定理； 限失真信编码定理称为第三极限定理。 信息论与编码-信源编码 由于信源符号之间存在分布不均匀和相关 性，使得信源存在冗余度，信源编码的主 要任务就是减少
3、冗余，提高编码效率。 信息论与编码-信源编码 由于信源符号之间存在分布不均匀和相关 性，使得信源存在冗余度，信源编码的主 要任务就是减少冗余，提高编码效率。 具体说，就是针对信源输出符号序列的统 计特性，寻找一定的方法把信源输出符号 序列变换为最短的码字序列。 信息论与编码-信源编码 由于信源符号之间存在分布不均匀和相关 性，使得信源存在冗余度，信源编码的主 要任务就是减少冗余，提高编码效率。 具体说，就是针对信源输出符号序列的统 计特性，寻找一定的方法把信源输出符号 序列变换为最短的码字序列。 信源编码的基本途径有两个，一是使序列 中的各个符号尽可能地互相独立，即解除 相关性； 信息论与编码
4、-信源编码 由于信源符号之间存在分布不均匀和相关性 ，使得信源存在冗余度，信源编码的主要任 务就是减少冗余，提高编码效率。 具体说，就是针对信源输出符号序列的统计 特性，寻找一定的方法把信源输出符号序列 变换为最短的码字序列。 信源编码的基本途径有两个，一是使序列中 的各个符号尽可能地互相独立，即解除相关 性；二是使编码中各个符号出现的概率尽可 能地相等，即概率均匀化。 信息论与编码-信源编码 编码的定义 编码实质上是对信源的原始符号按一定的数学 规则进行的一种变换。 信息论与编码-信源编码 编码的定义 编码实质上是对信源的原始符号按一定的数学 规则进行的一种变换。 讨论无失真信源编码，可以不
5、考虑干扰问题， 所以它的数学描述比较简单。 信息论与编码-信源编码 编码的定义 编码实质上是对信源的原始符号按一定的数学 规则进行的一种变换。 讨论无失真信源编码，可以不考虑干扰问题， 所以它的数学描述比较简单。图3.1是一个信源 编码器，它的输入是信源符号 ， 同时存在另一符号 ，一般来说， 元素 是适合信道传输的，称为码符号（或者 码元）。 信息论与编码-信源编码 编码器的功能就是将信源符号集中的符号 （或者 长为N的信源符号序列）变换成由 组成的长度为 的一一对应的 序列。 信息论与编码-信源编码 编码器的功能就是将信源符号集中的符号 （或者 长为N的信源符号序列）变换成由 组成的长度为
6、 的一一对应的 序列。 编 码 器 输出 图3.1 无失真信源编码器 码表 信源 信息论与编码-信源编码 输出的码符号序列称为码字，长度 称为码 字长度或简称码长。 信息论与编码-信源编码 输出的码符号序列称为码字，长度 称为码 字长度或简称码长。 编码就是从信源符号到码符号的一种映射。 信息论与编码-信源编码 输出的码符号序列称为码字，长度 称为码 字长度或简称码长。 编码就是从信源符号到码符号的一种映射。 若要实现无失真编码，则这种映射必须是一 一对应的，并且是可逆的。 信息论与编码-信源编码 输出的码符号序列称为码字，长度 称为码 字长度或简称码长。 编码就是从信源符号到码符号的一种映射
7、。 若要实现无失真编码，则这种映射必须是一 一对应的，并且是可逆的。 码字长度有无限长（卷积码）、定长和变长 （分组码）。 信息论与编码-信源编码 输出的码符号序列称为码字，长度 称为码 字长度或简称码长。 编码就是从信源符号到码符号的一种映射。 若要实现无失真编码，则这种映射必须是一 一对应的，并且是可逆的。 码字长度有无限长（卷积码）、定长和变长 （分组码）。 码元符号通常使用二进制来表示 信息论与编码-信源编码 信源符号取值概率 码 表 码1码2 a1 a2 a3 a4 p(a1 ) p(a2 ) p(a3 ) p(a4 ) 00 01 10 11 0 01 001 111 变长码与定长
8、码 信息论与编码-信源编码 信源符号信源符号概率 码1码2 a1 a2 a3 a4 1/2 1/4 1/8 1/8 0 11 00 11 0 10 00 01 码3码4 1 10 100 1000 1 01 001 0001 信息论与编码-信源编码 码符号的分类： 下图是一个码分类图 分组码 非分组码 码 信息论与编码-信源编码 码符号的分类： 下图是一个码分类图 非奇异码 奇异码 分组码 非分组码 码 信息论与编码-信源编码 码符号的分类： 下图是一个码分类图 唯一可译码 非唯一可译码 非奇异码 奇异码 分组码 非分组码 码 信息论与编码-信源编码 码符号的分类： 下图是一个码分类图 信息论
9、与编码-信源编码 下面，我们给出这些码的定义。 1. 二元码 若码符号集为 ，所有码字都是一些二元 序列，则称为二元码。二元码是数字通信和计 算机系统中最常用的一种码。 信息论与编码-信源编码 下面，我们给出这些码的定义。 1. 二元码 若码符号集为 ，所有码字都是一些二元 序列，则称为二元码。二元码是数字通信和计 算机系统中最常用的一种码。 2. 等长码： 若一组码中所有码字的码长都相同，即 ，则称为等长码。 信息论与编码-信源编码 下面，我们给出这些码的定义。 1. 二元码 若码符号集为 ，所有码字都是一些二元序列， 则称为二元码。二元码是数字通信和计算机系统中最 常用的一种码。 2. 等
10、长码： 若一组码中所有码字的码长都相同，即 ，则称为等长码。 3. 变长码： 若一组码组中所有码字的码长各不相同，则称为变长码 。 信息论与编码-信源编码 4. 非奇异码： 若一组码中所有码字都不相同，则称为非奇异码 。 信息论与编码-信源编码 4. 非奇异码： 若一组码中所有码字都不相同，则称为非奇异码 。 5. 奇异码： 若一组码中有相同的码字，则称为奇异码。 信息论与编码-信源编码 4. 非奇异码： 若一组码中所有码字都不相同，则称为非奇异码 。 5. 奇异码： 若一组码中有相同的码字，则称为奇异码。 6. 唯一可译码： 若码的任意一串有限长的码符号序列只能唯一地 被译成所对应的信源符号
11、序列，则此码称为唯 一可译码，否则就称为非唯一可译码。 信息论与编码-信源编码 例如0,10,11是一种唯一可译码。因为任 意一串有限长码序列，如100111000，只能 被分割成 10，0，11，0，0。任何其他分割 法都会产生一些非定义的码字。 信息论与编码-信源编码 例如0,10,11是一种唯一可译码。因为任 意一串有限长码序列，如100111000，只能 被分割成 10，0，11，0，0。任何其他分割 法都会产生一些非定义的码字。 显然，奇异码不是唯一可译码，而非奇异 码中有非唯一可译码和唯一可译码。 信息论与编码-信源编码 信源符号 信源符号概率码1码2 a1 a2 a3 a4 1/
12、2 1/4 1/8 1/8 0 11 00 11 0 10 00 01 码3码4 1 10 100 1000 1 01 001 0001 上表中码3是唯一可译码，但码2不是唯一可译码。 例如10000100是由码2的（10，0，0，01，00 ）产生的序列，译码时可有多种分法，如10，0， 00，10，0，此时产生歧义。 信息论与编码-信源编码 7. 非即时码和即时码： 如果接收端收到一个完整的码字后，不能立即 译码，还要等下一个码字开始接收后才能判断 是否可以译码，这样的码叫做非即时码。 信息论与编码-信源编码 7. 非即时码和即时码： 如果接收端收到一个完整的码字后，不能立即 译码，还要等
13、下一个码字开始接收后才能判断 是否可以译码，这样的码叫做非即时码。 如果收到一个完整的码字以后，就可以立即译 码，则叫做即时码。 信息论与编码-信源编码 7. 非即时码和即时码： 如果接收端收到一个完整的码字后，不能立即 译码，还要等下一个码字开始接收后才能判断 是否可以译码，这样的码叫做非即时码。 如果收到一个完整的码字以后，就可以立即译 码，则叫做即时码。即时码要求任何一个码字 都不是其他码字的前缀部分，也叫做异前缀码 信息论与编码-信源编码 信源符号 信源符号概率码1码2 a1 a2 a3 a4 1/2 1/4 1/8 1/8 0 11 00 11 0 10 00 01 码3码4 1 1
14、0 100 1000 1 01 001 0001 上表中码3是非即时码，而码4是即时码。 码4中只要收到符号1就表示该码字已完整，可以立 即译码。 信息论与编码-信源编码 信源符号 信源符号概率码1码2 a1 a2 a3 a4 1/2 1/4 1/8 1/8 0 11 00 11 0 10 00 01 码3码4 1 10 100 1000 1 01 001 0001 上表中码3是非即时码，而码4是即时码。 码4中只要收到符号1就表示该码字已完整，可以立即译码 。 即时码又称为非延长码，任意一个码字都不是其他码字的前 缀部分，有时叫做异前缀码。 信息论与编码-信源编码 信源符号 信源符号概率码1
15、码2 a1 a2 a3 a4 1/2 1/4 1/8 1/8 0 11 00 11 0 10 00 01 码3码4 1 10 100 1000 1 01 001 0001 上表中码3是非即时码，而码4是即时码。 在延长码中，有的码是唯一可译的，主要取决于 码的总体结构，如表中码3的延长码就是唯一可译 的。 信息论与编码-信源编码 码树： 信息论与编码-信源编码 码树： 即时码的一种简单构造方法是树图法。 信息论与编码-信源编码 码树： 即时码的一种简单构造方法是树图法。 对给定码字的全体集合 可以用码树来描述它。 信息论与编码-信源编码 码树： 即时码的一种简单构造方法是树图法。 对给定码字的
16、全体集合 可以用码树来描述它。 所谓树，就是既有根、枝， 又有节点， 信息论与编码-信源编码 码树： 即时码的一种简单构造方法是树图法。 对给定码字的全体集合 可以用码树来描述它。 所谓树，就是既有根、枝， 又有节点，如图所示。 A B C D 0 0 0 E 1 1 1 1 1 01 001 0001 信息论与编码-信源编码 码树： 即时码的一种简单构造方法是树图法。 对给定码字的全体集合 可以用码树来描述它。 所谓树，就是既有根、枝，又 有节点，如图所示。图中，最上端 A为根节点， A B C D 0 0 0 E 1 1 1 1 1 01 001 0001 信息论与编码-信源编码 码树：
