信息论与编码-第五章

1、信息论与编码-信源编码通信的实质是信息的传输。而高速度、高质量地传送信息是信息传输的基本问题。将信源信息通过信道传送给信宿，怎样才能做到尽可能不失真而又快速呢？这就需要解决两个问题：第一，在不失真或允许一定失真的条件下，如何用尽可能少的符号来传送信源信息；第二，在信道受干扰的情况下，如何增加信号的抗干扰能力，同时又使得信息传输率最大。为了解决这两个问题，就要引入信源编码和信道编码。信息论与编码-信源编码一般来说，提高抗干扰能力（降低失真或错误概率）往往是以降低信息传输率为代价的；反之，要提高信息传输率常常又会使抗干扰能力减弱。二者是有矛盾的。然而在信息论的编码定理中，已从理论上证明，至少存在某

2、种最佳的编码或信息处理方法，能够解决上述矛盾，做到既可靠又有效地传输信息。这些结论对各种通信系统的设计和估价具有重大的理论指导意义。信息论与编码-信源编码编码分为信源编码和信道编码信道编码，信源编码又分为无失真和限失真无失真和限失真。由于这些定理都要求符号数很大才能使它的值接近所规定的值，因而这些定理被称为极限定极限定理。理。一般称无失真信源编码定理为第一极限定理；信道编码定理（包括离散和连续信道）称为第二极限定理；限失真信编码定理称为第三极限定理。 信息论与编码-信源编码由于信源符号之间存在分布不均匀和相关性，使得信源存在冗余度，信源编码的主要任务就是减少冗余，提高编码效率。信息论与编码-信

3、源编码由于信源符号之间存在分布不均匀和相关性，使得信源存在冗余度，信源编码的主要任务就是减少冗余，提高编码效率。具体说，就是针对信源输出符号序列的统计特性，寻找一定的方法把信源输出符号序列变换为最短的码字序列。信息论与编码-信源编码由于信源符号之间存在分布不均匀和相关性，使得信源存在冗余度，信源编码的主要任务就是减少冗余，提高编码效率。具体说，就是针对信源输出符号序列的统计特性，寻找一定的方法把信源输出符号序列变换为最短的码字序列。信源编码的基本途径有两个，一是使序列中的各个符号尽可能地互相独立，即解除相关性；信息论与编码-信源编码由于信源符号之间存在分布不均匀和相关性，使得信源存在冗余度，信

4、源编码的主要任务就是减少冗余，提高编码效率。具体说，就是针对信源输出符号序列的统计特性，寻找一定的方法把信源输出符号序列变换为最短的码字序列。信源编码的基本途径有两个，一是使序列中的各个符号尽可能地互相独立，即解除相关性；二是使编码中各个符号出现的概率尽可能地相等，即概率均匀化。 信息论与编码-信源编码 编码的定义编码的定义 编码实质上是对信源的原始符号按一定的数学规则进行的一种变换。信息论与编码-信源编码 编码的定义编码的定义 编码实质上是对信源的原始符号按一定的数学规则进行的一种变换。讨论无失真信源编码，可以不考虑干扰问题，所以它的数学描述比较简单。信息论与编码-信源编码 编码的定义编码的

5、定义 编码实质上是对信源的原始符号按一定的数学规则进行的一种变换。讨论无失真信源编码，可以不考虑干扰问题，所以它的数学描述比较简单。图3.1是一个信源编码器，它的输入是信源符号 ，同时存在另一符号 ，一般来说，元素 是适合信道传输的，称为码符号（或者码元）。,21qsssS,21rxxxXjx信息论与编码-信源编码编码器的功能就是将信源符号集中的符号 （或者长为N的信源符号序列）变换成由 组成的长度为 的一一对应的序列。is),2, 1(rjxjil信息论与编码-信源编码编码器的功能就是将信源符号集中的符号 （或者长为N的信源符号序列）变换成由 组成的长度为 的一一对应的序列。is),2, 1

6、(rjxjil 编 码 器,:21qsssS,:21rxxxX输出图3.1 无失真信源编码器 码表信源信息论与编码-信源编码输出的码符号序列称为码字，长度 称为码字长度或简称码长。il信息论与编码-信源编码输出的码符号序列称为码字，长度 称为码字长度或简称码长。编码就是从信源符号到码符号的一种映射。il信息论与编码-信源编码输出的码符号序列称为码字，长度 称为码字长度或简称码长。编码就是从信源符号到码符号的一种映射。若要实现无失真编码，则这种映射必须是一一对应的，并且是可逆的。il信息论与编码-信源编码输出的码符号序列称为码字，长度 称为码字长度或简称码长。编码就是从信源符号到码符号的一种映射

7、。若要实现无失真编码，则这种映射必须是一一对应的，并且是可逆的。码字长度有无限长（卷积码）、定长和变长（分组码）。il信息论与编码-信源编码输出的码符号序列称为码字，长度 称为码字长度或简称码长。编码就是从信源符号到码符号的一种映射。若要实现无失真编码，则这种映射必须是一一对应的，并且是可逆的。码字长度有无限长（卷积码）、定长和变长（分组码）。码元符号通常使用二进制来表示il信息论与编码-信源编码 信源符号取值概率码 表码1码2a1a2a3a4p(a1)p(a2)p(a3)p(a4)00011011001001111变长码与定长码信息论与编码-信源编码 信源符号信源符号概率码1码2a1a2a3

8、a41/21/41/81/801100110100001码3码411010010001010010001信息论与编码-信源编码码符号的分类码符号的分类：下图是一个码分类图分组码非分组码码信息论与编码-信源编码码符号的分类码符号的分类：下图是一个码分类图非奇异码奇异码分组码非分组码码信息论与编码-信源编码码符号的分类码符号的分类：下图是一个码分类图唯一可译码非唯一可译码非奇异码奇异码分组码非分组码码信息论与编码-信源编码即时码（非延长码）非即时码唯一可译码非唯一可译码非奇异码奇异码分组码非分组码码码符号的分类码符号的分类：下图是一个码分类图信息论与编码-信源编码下面，我们给出这些码的定义。1.

9、二元码若码符号集为 ，所有码字都是一些二元序列，则称为二元码。二元码是数字通信和计算机系统中最常用的一种码。1 , 0X信息论与编码-信源编码下面，我们给出这些码的定义。1. 二元码若码符号集为 ，所有码字都是一些二元序列，则称为二元码。二元码是数字通信和计算机系统中最常用的一种码。2. 等长码：若一组码中所有码字的码长都相同，即 ，则称为等长码。1 , 0X),2, 1(qilli信息论与编码-信源编码下面，我们给出这些码的定义。1. 二元码若码符号集为 ，所有码字都是一些二元序列，则称为二元码。二元码是数字通信和计算机系统中最常用的一种码。2. 等长码：若一组码中所有码字的码长都相同，即

10、，则称为等长码。3. 变长码：若一组码组中所有码字的码长各不相同，则称为变长码。1 , 0X),2, 1(qilli信息论与编码-信源编码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码2a1a2a3a41/21/41/81/801100110100001码3码4110100100010100100

12、01上表中码3是唯一可译码，但码2不是唯一可译码。例如10000100是由码2的（10，0，0，01，00）产生的序列，译码时可有多种分法，如10，0，00，10，0，此时产生歧义。信息论与编码-信源编码7. 非即时码和即时码：如果接收端收到一个完整的码字后，不能立即译码，还要等下一个码字开始接收后才能判断是否可以译码，这样的码叫做非即时码。信息论与编码-信源编码7. 非即时码和即时码：如果接收端收到一个完整的码字后，不能立即译码，还要等下一个码字开始接收后才能判断是否可以译码，这样的码叫做非即时码。如果收到一个完整的码字以后，就可以立即译码，则叫做即时码。信息论与编码-信源编码7. 非即时码

13、和即时码：如果接收端收到一个完整的码字后，不能立即译码，还要等下一个码字开始接收后才能判断是否可以译码，这样的码叫做非即时码。如果收到一个完整的码字以后，就可以立即译码，则叫做即时码。即时码要求任何一个码字都不是其他码字的前缀部分，也叫做异前缀码信息论与编码-信源编码 信源符号信源符号概率码1码2a1a2a3a41/21/41/81/801100110100001码3码411010010001010010001上表中码3是非即时码，而码4是即时码。码4中只要收到符号1就表示该码字已完整，可以立即译码。信息论与编码-信源编码 信源符号信源符号概率码1码2a1a2a3a41/21/41/81/80

14、1100110100001码3码411010010001010010001上表中码3是非即时码，而码4是即时码。码4中只要收到符号1就表示该码字已完整，可以立即译码。即时码又称为非延长码，任意一个码字都不是其他码字的前缀部分，有时叫做异前缀码异前缀码。信息论与编码-信源编码 信源符号信源符号概率码1码2a1a2a3a41/21/41/81/801100110100001码3码411010010001010010001上表中码3是非即时码，而码4是即时码。在延长码中，有的码是唯一可译的，主要取决于码的总体结构，如表中码3的延长码就是唯一可译的。信息论与编码-信源编码码树码树：信息论与编码-信源编

15、码码树码树：即时码即时码的一种简单构造方法是的一种简单构造方法是树图法树图法。信息论与编码-信源编码码树码树：即时码即时码的一种简单构造方法是树图法。的一种简单构造方法是树图法。对给定码字的全体集合对给定码字的全体集合可以用码树来描述它。可以用码树来描述它。,21qWWWC信息论与编码-信源编码码树码树：即时码即时码的一种简单构造方法是树图法。的一种简单构造方法是树图法。对给定码字的全体集合对给定码字的全体集合可以用码树来描述它。可以用码树来描述它。,21qWWWC所谓树，就是既有根、枝，所谓树，就是既有根、枝，又有节点，又有节点，信息论与编码-信源编码码树码树：即时码的一种简单构造方法是树图

16、法。对给定码字的全体集合可以用码树来描述它。所谓树，就是既有根、枝，所谓树，就是既有根、枝，又有节点，如图所示。又有节点，如图所示。,21qWWWCABCD000E11111010010001信息论与编码-信源编码码树码树：即时码的一种简单构造方法是树图法。对给定码字的全体集合可以用码树来描述它。所谓树，就是既有根、枝，又所谓树，就是既有根、枝，又有节点，如图所示。图中，最上端有节点，如图所示。图中，最上端A为为根节点根节点，,21qWWWCABCD000E11111010010001信息论与编码-信源编码码树码树：即时码即时码的一种简单构造方法是树图法。的一种简单构造方法是树图法。对给定码字

17、的全体集合对给定码字的全体集合可以用码树来描述它。可以用码树来描述它。所谓树，就是既有根、枝，又所谓树，就是既有根、枝，又有节点，如图所示。图中，最上端有节点，如图所示。图中，最上端A为为根节点根节点，A、B、 C、D、E皆皆为节点，为节点，E为为终端节点终端节点。,21qWWWCABCD000E11111010010001信息论与编码-信源编码码树码树：即时码的一种简单构造方法是树图法。对给定码字的全体集合可以用码树来描述它。所谓树，就是既有根、枝，又有节点，如图所示。图中，最上端图中，最上端A为为根节点根节点，A、B、 C、D、E皆皆为节点，为节点，E为为终端节点终端节点。 A、B、C、D

18、为为中间节点中间节点，中间节点不安排码字，而只在终端节点安排码字中间节点不安排码字，而只在终端节点安排码字.,21qWWWCABCD000E11111010010001信息论与编码-信源编码每个终端节点所对应的每个终端节点所对应的码字码字就是从根节点出发到终就是从根节点出发到终端节点走过的路径上所对应的符号组成。端节点走过的路径上所对应的符号组成。信息论与编码-信源编码每个终端节点所对应的码字就是从根节点出发到终端节点走过的路径上所对应的符号组成。如图如图3.2中的终端节点中的终端节点E，走过的路径为，走过的路径为ABCDE，所对应的码符号分别为所对应的码符号分别为0、0、0、1，则，则E对应

19、的码对应的码字为字为0001。信息论与编码-信源编码每个终端节点所对应的码字就是从根节点出发到终端节点走过的路径上所对应的符号组成。如图3.2中的终端节点E，走过的路径为ABCDE，所对应的码符号分别为0、0、0、1，则E对应的码字为0001。可以看出，按树图法构成的码一定满足可以看出，按树图法构成的码一定满足即时码即时码的定义（一一对应，非前缀码）。的定义（一一对应，非前缀码）。信息论与编码-信源编码每个终端节点所对应的码字就是从根节点出发到终端节点走过的路径上所对应的符号组成。如图3.2中的终端节点E，走过的路径为ABCDE，所对应的码符号分别为0、0、0、1，则E对应的码字为0001。可

20、以看出，按树图法构成的码一定满足即时码的定义（一一对应，非前缀码）。从码树上可以得知，当第从码树上可以得知，当第i阶的节点作为终端节阶的节点作为终端节点，且分配码字，则码字的码长为点，且分配码字，则码字的码长为i。信息论与编码-信源编码任一即时码都可以用树图法来表示。信息论与编码-信源编码任一即时码都可以用树图法来表示。当码字长度给定后，用树图法安排的即时码不是唯一的。信息论与编码-信源编码任一即时码都可以用树图法来表示。当码字长度给定后，用树图法安排的即时码不是唯一的。如图中，如果把左树枝安排为1，右树枝安排为0，则得到不同的结果。信息论与编码-信源编码任一即时码都可以用树图法来表示。当码字

21、长度给定后，用树图法安排的即时码不是唯一的。如图中，如果把左树枝安排为1，右树枝安排为0，则得到不同的结果。对一个给定的码，画出其对应的树，如果有中对一个给定的码，画出其对应的树，如果有中间节点安排了码字，则该码一定不是即时码。间节点安排了码字，则该码一定不是即时码。信息论与编码-信源编码任一即时码都可以用树图法来表示。当码字长度给定后，用树图法安排的即时码不是唯一的。如图中，如果把左树枝安排为1，右树枝安排为0，则得到不同的结果。对一个给定的码，画出其对应的树，如果有中间节点安排了码字，则该码一定不是即时码。每个节点上都有每个节点上都有 个分支的树称为个分支的树称为满树满树，否则，否则为为非

22、满树非满树。r信息论与编码-信源编码000000000000001111111111111110满树信息论与编码-信源编码012非满树信息论与编码-信源编码即时码的码树图还可以用来译码。 信息论与编码-信源编码即时码的码树图还可以用来译码。 当收到一串码符号序列后，首先从根节点出发，当收到一串码符号序列后，首先从根节点出发，根据接收到的第一个码符号来选择应走的第一根据接收到的第一个码符号来选择应走的第一条路径，条路径，信息论与编码-信源编码即时码的码树图还可以用来译码。 当收到一串码符号序列后，首先从根节点出发，根据接收到的第一个码符号来选择应走的第一条路径，再根据收到的第二个符号来选择应走再

23、根据收到的第二个符号来选择应走的第二条路径，的第二条路径，信息论与编码-信源编码即时码的码树图还可以用来译码。 当收到一串码符号序列后，首先从根节点出发，根据接收到的第一个码符号来选择应走的第一条路径，再根据收到的第二个符号来选择应走的第二条路径，直到走到终端节点为止，就可直到走到终端节点为止，就可以根据终端节点，立即判断出所接收的码字。以根据终端节点，立即判断出所接收的码字。信息论与编码-信源编码即时码的码树图还可以用来译码。 当收到一串码符号序列后，首先从根节点出发，根据接收到的第一个码符号来选择应走的第一条路径，再根据收到的第二个符号来选择应走的第二条路径，直到走到终端节点为止，就可以根

24、据终端节点，立即判断出所接收的码字。然后从树根继续下一个码字的判断。这样，就然后从树根继续下一个码字的判断。这样，就可以将接收到的一串码符号序列译成对应的信可以将接收到的一串码符号序列译成对应的信源符号序列。源符号序列。信息论与编码-信源编码克拉夫特（克拉夫特（Kraft）不等式）不等式 信息论与编码-信源编码克拉夫特（克拉夫特（Kraft）不等式）不等式 对于码符号为对于码符号为 的任意唯一可译的任意唯一可译码，其码字为码，其码字为 ，所对应的码长，所对应的码长为为 ，则必定满足克拉夫特不等式，则必定满足克拉夫特不等式 ,21rxxxXqWWW,21qlll,2111qilir信息论与编码-

25、信源编码克拉夫特（Kraft）不等式 对于码符号为 的任意唯一可译码，其码字为 ，所对应的码长为 ，则必定满足克拉夫特不等式 反之，若码长满足上面的不等式，则一定存在反之，若码长满足上面的不等式，则一定存在具有这样码长的即时码。具有这样码长的即时码。,21rxxxXqWWW,21qlll,2111qilir信息论与编码-信源编码注意注意：克拉夫特不等式只是说明唯一可译码是否：克拉夫特不等式只是说明唯一可译码是否存在，并不能作为唯一可译码的判据（可以排除，存在，并不能作为唯一可译码的判据（可以排除，不能肯定）。不能肯定）。信息论与编码-信源编码注意：克拉夫特不等式只是说明唯一可译码是否存在，并不

26、能作为唯一可译码的判据（可以排除，不能肯定）。如如0，10，010，111满足克拉夫特满足克拉夫特不等式，但却不是唯一可译码。不等式，但却不是唯一可译码。信息论与编码-信源编码例题：设二进制码树中 ，对应的 ，),(4321xxxxX 3, 2, 2, 14321llll信息论与编码-信源编码例题：设二进制码树中 ，对应的 ，由上述定理，可得 ),(4321xxxxX 3, 2, 2, 14321llll18922222322141ili信息论与编码-信源编码例题：设二进制码树中 ，对应的 ，由上述定理，可得 因此不存在满足这种码长的唯一可译码。因此不存在满足这种码长的唯一可译码。 ),(43

27、21xxxxX 3, 2, 2, 14321llll18922222322141ili信息论与编码-信源编码例题：设二进制码树中 ，对应的 ，由上述定理，可得 因此不存在满足这种码长的唯一可译码。 可以用树码进行检查。可以用树码进行检查。),(4321xxxxX 3, 2, 2, 14321llll18922222322141ili例题：将各码字长度改为 由上述定理，可得 因此存在满足这种码长的唯一可译码。如（0，10，110，111）。可以用树码进行检查。 但但0，10，010，111满足克拉夫特不等式，却不满足克拉夫特不等式，却不是唯一可译码。是唯一可译码。信息论与编码-信源编码12222

28、2332141ili3, 3, 2, 14321llll信息论与编码-信源编码集合F的构成方法：首先，观察码C中最短的码字是否是其它码字的前缀，若是，将其所有可能的尾随后缀排列出。而这些尾随后缀又有可能是某些码字的前缀，再将这些尾随后缀产生的新的尾随后缀列出，然后再观察这些新的尾随后缀是否是某些码字的前缀，再将产生的尾随后缀列出，依此下去，直到没有一个尾随后缀是码字的前缀为止。信息论与编码-信源编码这样，首先获得了由最短的码字能引起的所有尾随后缀，接着，按照上述步骤将次短码字、等等所有码字可能产生的尾随后缀全部列出。由此得到由码C的所有可能的尾随后缀的集合F。信息论与编码-信源编码这样，首先获

29、得了由最短的码字能引起的所有尾随后缀，接着，按照上述步骤将次短码字、等等所有码字可能产生的尾随后缀全部列出。由此得到由码C的所有可能的尾随后缀的集合F。例题：设码C=0,10,1100,1110,1011,1101，根据上述测试方法，判断是否是唯一可译码。信息论与编码-信源编码码C=0,10,1100,1110,1011,1101解：解：1. 先看最短的码字：先看最短的码字：“0”，它不是其他码字，它不是其他码字 前缀，所以没有尾随后缀。前缀，所以没有尾随后缀。 信息论与编码-信源编码码C=0,10,1100,1110,1011,1101解：1. 先看最短的码字：“0”，它不是其他码字 前缀，

30、所以没有尾随后缀。 2. 再观察码字再观察码字“10”，它是码字，它是码字“1011”的前的前缀，缀，因此有尾随后缀：因此有尾随后缀：101100100111信息论与编码-信源编码所以，集合所以，集合F=11，00，10，01，其中，其中“10”为码为码字，故码字，故码C不是唯一可译码。不是唯一可译码。码C=0,10,1100,1110,1011,1101信息论与编码-信源编码所以，集合F=11，00，10，01，其中“10”为码字，故码C不是唯一可译码。如若收到如若收到101110,可译为可译为10，1110，也可译为，也可译为1011,10码C=0,10,1100,1110,1011,11

31、01信息论与编码-信源编码定长编码定理定长编码定理 信息论与编码-信源编码定长编码定理定长编码定理 前面已经说过，所谓前面已经说过，所谓信源编码信源编码，就是将信源符，就是将信源符号序列变换成另一个序列（码字）。号序列变换成另一个序列（码字）。 信息论与编码-信源编码定长编码定理定长编码定理 前面已经说过，所谓信源编码，就是将信源符号序列变换成另一个序列（码字）。 设信源输出符号序列长度为设信源输出符号序列长度为L，码字的长度，码字的长度为为 ，编码的目的，就是要是信源的信息率，编码的目的，就是要是信源的信息率最小，也就是说，要用最少的符号来代表信源。最小，也就是说，要用最少的符号来代表信源。

32、LK信息论与编码-信源编码在定长编码中，对每一个信源序列，在定长编码中，对每一个信源序列， 都都是定值，设等于是定值，设等于K，我们的目的是寻找，我们的目的是寻找最小最小K值。值。LK信息论与编码-信源编码在定长编码中，对每一个信源序列， 都是定值，设等于K，我们的目的是寻找最小K值。要实现无失真的信源编码，要实现无失真的信源编码，要求信源符号要求信源符号 与码字是一一对应的，并求由码字组与码字是一一对应的，并求由码字组成的符号序列的逆变换也是唯一的成的符号序列的逆变换也是唯一的（唯一可译码）。（唯一可译码）。LK), 2 , 1(qiiX信息论与编码-信源编码定长编码定理定长编码定理：由由L

33、个符号组成的、每个符号熵为个符号组成的、每个符号熵为 的无记的无记忆平稳信源符号序列忆平稳信源符号序列 ，可用，可用 个符号个符号 （每个符号有（每个符号有m中可能值）中可能值）进行定长编码。对任意进行定长编码。对任意 ，只要，只要则当则当L足够大时，必可使译码差错小于足够大时，必可使译码差错小于)(XHLLXXX,21LKLKYYY,210, 0)(logXHmLKLL信息论与编码-信源编码反之，当反之，当2)(logXHmLKLL信息论与编码-信源编码反之，当时，译码差错一定是有限值，当时，译码差错一定是有限值，当L足够大时，译足够大时，译码几乎必定出错。码几乎必定出错。2)(logXHm

34、LKLL信息论与编码-信源编码反之，当时，译码差错一定是有限值，当L足够大时，译码几乎必定出错。式中，左边是输出码字每符号所能载荷的最大信式中，左边是输出码字每符号所能载荷的最大信息量息量2)(logXHmLKLLmLKLlog信息论与编码-信源编码上述定理的条件可改写成 XHXLHmKLLlog信息论与编码-信源编码上述定理的条件可改写成上式大于号左边为上式大于号左边为KL 长码字所能携带的最大长码字所能携带的最大信息量，右边为信息量，右边为L长长信源序列携带的信息量。信源序列携带的信息量。 XHXLHmKLLlog信息论与编码-信源编码上述定理的条件可改写成上式大于号左边为KL 长码字所能

35、携带的最大信息量，右边为L长信源序列携带的信息量。所以等长编码定理告诉我们，只要码字传输的所以等长编码定理告诉我们，只要码字传输的信息量大于信源序列携带的信息量，总可以信息量大于信源序列携带的信息量，总可以实现几乎无失真的编码。条件是所取得符号实现几乎无失真的编码。条件是所取得符号数数L足够大。足够大。 XHXLHmKLLlog信息论与编码-信源编码例如，某信源有例如，某信源有8种等概率符号，种等概率符号，L1，信源，信源序列熵达到最大值：序列熵达到最大值： H1(X)=log8=3bit/符号符号 信息论与编码-信源编码例如，某信源有8种等概率符号，L1，信源序列熵达到最大值： H1(X)=

36、log8=3bit/符号 即该信源符号肯定可以用即该信源符号肯定可以用3比特的信息率进行比特的信息率进行无失真的编码。无失真的编码。信息论与编码-信源编码例如，某信源有8种等概率符号，L1，信源序列熵达到最大值： H1(X)=log8=3bit/符号 即该信源符号肯定可以用3比特的信息率进行无失真的编码。这就是说，如果采用二进制这就是说，如果采用二进制符号作为码字输出符号，则用符号作为码字输出符号，则用3个比特就可以个比特就可以表示一个符号。表示一个符号。信息论与编码-信源编码当信源符号输出概率不相等时，如， p(xi)=.4,.18,.1,.1,.07,.06,.05,.04 则此时，H1(

37、X)=2.55bit/符号信息论与编码-信源编码当信源符号输出概率不相等时，如， p(xi)=.4,.18,.1,.1,.07,.06,.05,.04 则此时，H1(X)=2.55bit/符号因22.55=5.856，即若用2.55bit来表示，只有5.856种可能码字，还有部分符号没有对应的码字，信息论与编码-信源编码当信源符号输出概率不相等时，如， p(xi)=.4,.18,.1,.1,.07,.06,.05,.04 则此时，H1(X)=2.55bit/符号因22.55=5.856，即若用2.55bit来表示，只有5.856种可能码字，还有部分符号没有对应的码字，这些符号一旦出现，被传输至

38、接受端，就没有对这些符号一旦出现，被传输至接受端，就没有对应的码字译码，因而引起译码差错。所以定长应的码字译码，因而引起译码差错。所以定长编码一般都存在译码差错，只是差错大小不同。编码一般都存在译码差错，只是差错大小不同。信息论与编码-信源编码当信源符号输出概率不相等时，如， p(xi)=.4,.18,.1,.1,.07,.06,.05,.04 则此时，H1(X)=2.55bit/符号因22.55=5.856，即若用2.55bit来表示，只有5.856种可能码字，还有部分符号没有对应的码字，这些符号一旦出现，被传输至接受端，就没有对应的码字译码，因而引起译码差错。所以定长编码一般都存在译码差错

39、，只是差错大小不同。当当L足够大时，译码差错可以达到足够小。足够大时，译码差错可以达到足够小。设 是信源序列的样本矢量， ，则共有 种样本，信息论与编码-信源编码),(21LlixxxxX nilaaaax,21 Ln设 是信源序列的样本矢量， ，则共有 种样本，我们把它分成两个互补的集 和 信息论与编码-信源编码),(21LlixxxxX nilaaaax,21 LnACA设 是信源序列的样本矢量， ，则共有 种样本，我们把它分成两个互补的集 和 集中的元素（样本矢量）有与之对应的不同码字，信息论与编码-信源编码),(21LlixxxxX nilaaaax,21 LnACAA设 是信源序列的

40、样本矢量， ，则共有 种样本，我们把它分成两个互补的集 和 集中的元素（样本矢量）有与之对应的不同码字，而集 中的元素没有对应的输出码字，因而会在译码时发生差错。信息论与编码-信源编码),(21LlixxxxX nilaaaax,21 LnACAACA信息论与编码-信源编码如果允许一定的差错 ，则编码时只需对属于 中的 个样本矢量赋予相应的不同字码，即输出码字的总个数 只要大于 就可以了。AMKmM信息论与编码-信源编码如果允许一定的差错 ，则编码时只需对属于 中的 个样本矢量赋予相应的不同字码，即输出码字的总个数 只要大于 就可以了。在这种编码方式下，差错概率 即为集 中元素发生的概率 ,

41、此时要求 ， 因而 集中的样本都应是小概率事件。AMKmMePCACAPCAPCA信息论与编码-信源编码如果允许一定的差错 ，则编码时只需对属于 中的 个样本矢量赋予相应的不同字码，即输出码字的总个数 只要大于 就可以了。在这种编码方式下，差错概率 即为集 中元素发生的概率 , 此时要求 ， 因而 集中的样本都应是小概率事件。当当L则增大时虽然样本数也随着增多，但小则增大时虽然样本数也随着增多，但小概率事件的概率将更小，有望使概率事件的概率将更小，有望使 更小。更小。AMKmMePCACAPCAPCACAP设差错概率为 ，信源序列的自方差为则有：信息论与编码-信源编码P22)()()(XxIE

42、Xi22)(LXP 设差错概率为 ，信源序列的自方差为则有：当当 和和 均为定值时，只要均为定值时，只要L足够大，足够大， 可以可以小于任一整数小于任一整数 ，即，即信息论与编码-信源编码)(2XP22)()()(XxIEXi22)(LXP 2P22)(LX信息论与编码-信源编码此时要求： 22)(XL 信息论与编码-信源编码此时要求： 只要只要 足够小，就可以几乎无差错地译足够小，就可以几乎无差错地译码，当然代价是码，当然代价是L变得更大。变得更大。22)(XL 信息论与编码-信源编码令为为码字最大平均符号信息量码字最大平均符号信息量。mLKKLlog信息论与编码-信源编码令为码字最大平均符

43、号信息量。定义定义编码效率编码效率为为：mLKKLlogKXHL)(信息论与编码-信源编码令为码字最大平均符号信息量。定义编码效率为：最佳编码效率最佳编码效率为为mLKKLlogKXHL)()()(XHXHLL信息论与编码-信源编码 无失真信源编码定理从理论上阐明了编码无失真信源编码定理从理论上阐明了编码效率接近于效率接近于1的理想编码器的存在性，它使的理想编码器的存在性，它使输出符号的信息率与信源熵之比接近于输出符号的信息率与信源熵之比接近于1，信息论与编码-信源编码 无失真信源编码定理从理论上阐明了编码效率接近于1的理想编码器的存在性，它使输出符号的信息率与信源熵之比接近于1，但要在实际中

44、实现，则要求信源符号序列但要在实际中实现，则要求信源符号序列的的L非常大进行统一编码才行，这往往是非常大进行统一编码才行，这往往是不现实不现实的。的。信息论与编码-信源编码例题：设离散无记忆信源概率空间为信源熵为自信息方差为自信息方差为04. 005. 006. 007. 01 . 01 . 018. 04 . 087654321xxxxxxxxPX符号/55. 2log)(812bitppXHiii信息论与编码-信源编码82. 7)()(log)(log)(2)(log)(log)(2)(log)(log)()()(812228181812222812222812222iiiiiiiiiii

45、iiiiiiiiXHpppXHppXHppXHpXHppXHppXHxIEX信息论与编码-信源编码对信源符号采用定长二元编码，要求编码效率 ，无记忆信源有 ，因此可以得到%90)()(XHXHL%90)()(XHXH28. 0信息论与编码-信源编码对信源符号采用定长二元编码，要求编码效率 ，无记忆信源有 ，因此可以得到如果要求译码错误概率如果要求译码错误概率 ，则，则%90)()(XHXHL%90)()(XHXH28. 0610872210108 . 9(）XL信息论与编码-信源编码由此可见，在对编码效率和译码错误概率的要由此可见，在对编码效率和译码错误概率的要求不是十分苛刻的情况下，就需要求

46、不是十分苛刻的情况下，就需要 个信源个信源符号一起进行编码，这对存储和处理技术的要符号一起进行编码，这对存储和处理技术的要求太高，目前还无法实现。求太高，目前还无法实现。810L信息论与编码-信源编码由此可见，在对编码效率和译码错误概率的要求不是十分苛刻的情况下，就需要 个信源符号一起进行编码，这对存储和处理技术的要求太高，目前还无法实现。如果用如果用3比特来对上述信源的比特来对上述信源的8个符号进行定长个符号进行定长二元编码，二元编码，L=1，此时可实现译码无差错，但，此时可实现译码无差错，但编码效率只有编码效率只有2.55/3=85%。810L信息论与编码-信源编码由此可见，在对编码效率和

47、译码错误概率的要求不是十分苛刻的情况下，就需要 个信源符号一起进行编码，这对存储和处理技术的要求太高，目前还无法实现。如果用3比特来对上述信源的8个符号进行定长二元编码，L=1，此时可实现译码无差错，但编码效率只有2.55/3=85%。因此，一般说来，当因此，一般说来，当L有限时，高传输效率的定有限时，高传输效率的定长码往往要引入一定的失真和译码错误。解决长码往往要引入一定的失真和译码错误。解决的办法是可以采用的办法是可以采用变长编码变长编码。810L信息论与编码-信源编码变长编码定理变长编码定理在变长编码中，码长是变化的。对同一信源，其即时码或唯一可译码可以有许多种。信息论与编码-信源编码变

48、长编码定理变长编码定理在变长编码中，码长是变化的。对同一信源，其即时码或唯一可译码可以有许多种。究竟哪一种好究竟哪一种好呢？从高速传输信息的观点来考虑，当然希望选呢？从高速传输信息的观点来考虑，当然希望选择由短的码符号组成的码字，就是用码长来作为择由短的码符号组成的码字，就是用码长来作为选择准则，为此我们引入选择准则，为此我们引入码的平均长度码的平均长度。信息论与编码-信源编码变长编码定理变长编码定理在变长编码中，码长是变化的。对同一信源，其即时码或唯一可译码可以有许多种。究竟哪一种好呢？从高速传输信息的观点来考虑，当然希望选择由短的码符号组成的码字，就是用码长来作为选择准则，为此我们引入码的

49、平均长度。设信源为)(,),(,),(,2211qqxpxxpxxpxPX信息论与编码-信源编码编码后的码字为其码长分别为qWWW,21qlll,21信息论与编码-信源编码编码后的码字为其码长分别为因为对唯一可译码来说，信源符号与码字是一因为对唯一可译码来说，信源符号与码字是一一对应的，所以有一对应的，所以有qWWW,21qlll,21), 2 , 1)()(qixpWpii信息论与编码-信源编码编码后的码字为其码长分别为因为对唯一可译码来说，信源符号与码字是一一对应的，所以有则这个码的平均长度为则这个码的平均长度为qWWW,21qlll,21), 2 , 1)()(qixpWpiiqiiil

50、xpK1)(信息论与编码-信源编码编码后的码字为其码长分别为因为对唯一可译码来说，信源符号与码字是一一对应的，所以有则这个码的平均长度为它是每个信源符号平均需用的码元数。它是每个信源符号平均需用的码元数。qWWW,21qlll,21), 2 , 1)()(qixpWpiiqiiilxpK1)(信息论与编码-信源编码对某一信源来说，若有一个唯一可译码，其对某一信源来说，若有一个唯一可译码，其平均长度小于所有其它的唯一可译码的平平均长度小于所有其它的唯一可译码的平均长度，则该码称为均长度，则该码称为紧致码紧致码，或称，或称最佳码最佳码。信息论与编码-信源编码对某一信源来说，若有一个唯一可译码，其平

51、均长度小于所有其它的唯一可译码的平均长度，则该码称为紧致码，或称最佳码。无失真变长信源编码的基本问题就是要找无失真变长信源编码的基本问题就是要找最佳码。最佳码。信息论与编码-信源编码单个符号变长编码定理单个符号变长编码定理：信息论与编码-信源编码单个符号变长编码定理单个符号变长编码定理：若一离散无记忆信源的符号熵为若一离散无记忆信源的符号熵为H(X)，每个信源每个信源符号用符号用m进制码元进行变长编码，一定存在一进制码元进行变长编码，一定存在一种无失真编码方法，其码字平均长度种无失真编码方法，其码字平均长度 满足满足下面的不等式下面的不等式K1log)(log)(mXHKmXH信息论与编码-信

52、源编码离散平稳无记忆序列变长编码定理离散平稳无记忆序列变长编码定理（香农第一香农第一定理定理）：信息论与编码-信源编码离散平稳无记忆序列变长编码定理离散平稳无记忆序列变长编码定理（香农第一香农第一定理定理）：对于平均符号熵为 的离散平稳无记忆信源，必存在一种无失真信源编码方法，使平均信息率 满足下面的不等式其中， 为任意小正数。)(XHLRLLHRXH）(信息论与编码-信源编码上面的两个定理实际上是一样的，可以由第一个推导出第二个。信息论与编码-信源编码上面的两个定理实际上是一样的，可以由第一个推导出第二个。设用设用m进制码元做变长编码，进制码元做变长编码，序列长度为序列长度为L个信源符号，则

53、该序列所对应的个信源符号，则该序列所对应的码字的平均长度码字的平均长度 满足下面的不等式满足下面的不等式LK1log)(log)(mXLHKmXLHLLL信息论与编码-信源编码上面的两个定理实际上是一样的，可以由第一个推导出第二个。设用m进制码元做变长编码，序列长度为L个信源符号，则该序列所对应的码字的平均长度 满足下面的不等式而平均输出信息率为而平均输出信息率为LK1log)(log)(mXLHKmXLHLLLmLKRLlog信息论与编码-信源编码故有LmXHRXHLLlog)()(信息论与编码-信源编码故有当L足够大时，可使LmXHRXHLLlog)()(Lmlog信息论与编码-信源编码故

54、有当L足够大时，可使因此LmXHRXHLLlog)()(Lmlog)()(XHRXHLL信息论与编码-信源编码编码效率为LmXHXHKXHLLLlog)()()(信息论与编码-信源编码编码效率为剩余度（剩余度（冗余度冗余度）为）为KXHL)(11LmXHXHKXHLLLlog)()()(信息论与编码-信源编码用变长编码来达到相当高的编码效率，一般所用变长编码来达到相当高的编码效率，一般所要求的符号长度要求的符号长度L可以比定长编码小得多。可以比定长编码小得多。信息论与编码-信源编码用变长编码来达到相当高的编码效率，一般所要求的符号长度L可以比定长编码小得多。编码效率编码效率的下界：的下界：Lm

55、XHXHKXHLLLlog)()()(信息论与编码-信源编码用变长编码来达到相当高的编码效率，一般所要求的符号长度L可以比定长编码小得多。编码效率的下界：例如用二进制，例如用二进制，m=2，logm=1，仍用前面的例子，仍用前面的例子，LmXHXHKXHLLLlog)()()(信息论与编码-信源编码用变长编码来达到相当高的编码效率，一般所要求的符号长度L可以比定长编码小得多。编码效率的下界：例如用二进制，例如用二进制，m=2，logm=1，仍用前面的例子，仍用前面的例子，H（X）=2.55比特比特/符号，若要求符号，若要求 90%，则，则，LmXHXHKXHLLLlog)()()(信息论与编码

56、-信源编码用变长编码来达到相当高的编码效率，一般所要求的符号长度L可以比定长编码小得多。编码效率的下界：例如用二进制，例如用二进制，m=2，logm=1，仍用前面的例子，仍用前面的例子，H（X）=2.55比特比特/符号，若要求符号，若要求 90%，则，则，LmXHXHKXHLLLlog)()()(428. 01, 9 . 0155. 255. 2LL信息论与编码-信源编码香农第一编码定理给出了码字的平均长度的下界和上界。但并不是说大于这上界不能构成唯一可译码，而是因为我们总是希望 尽可能短。LK信息论与编码-信源编码香农第一编码定理给出了码字的平均长度的下界和上界。但并不是说大于这上界不能构成

57、唯一可译码，而是因为我们总是希望 尽可能短。定理说明当平均码长小于上界时，唯一可译码也存在。也就是说，定理给出的是最佳码的最短平均码长，并指出这个最短的平均码长与信源熵是有关的。LK信息论与编码-信源编码例5-3：设离散无记忆信源的概率空间为414321xxPX信息论与编码-信源编码其信源熵为符号/811. 034log434log41)(22bitXH信息论与编码-信源编码其信源熵为若用二元定长编码（0，1）来构造一个即时码： ，这时平均码长为符号/811. 034log434log41)(22bitXH1, 021xx信源符号二元码符号/1K信息论与编码-信源编码其信源熵为若用二元定长编码（0