第5章-无失真信源编码定理 - 2005-9

第5章无失真信源编码定理邹小林2015.11.

通信的实质是信息的传输。高效率、高质量传送信息是信息传输的基本问题！需要解决两个问题：第一，在不失真或允许一定失真的条件下，如何

用尽可能少的符号来传送信源信息；第二，在信道受干扰的情况下，如何增加信号的抗干扰能力，同时又使得信息传输率最大。为了解决这两个问题，引入信源编码和信道编码。了解

抗干扰能力与信息传输率二者相互矛盾。编码定理证明，至少存在某种最佳的编码能够解决上述矛盾，做到既可靠又有效地传输信息。了解

由于信源符号之间存在分布不均匀和相关性，使得信源存在冗余度，信源编码的主要任务就是减少冗余，提高编码效率。具体说，就是针对信源输出符号序列的统计特性，寻找一定的方法把信源输出符号序列变换为最短的码字序列。了解

信源编码常分为无失真信源编码和限失真信源编码，前者主要用于文字、数据信源的压缩;

后者主要用于图像、语音信源的压缩。了解

无失真编码

无失真编码是可逆编码的基础。

可逆是指当信源符号转换成代码后，可从代码无失真地恢复原信源符号。了解5.1编码器

编码实质上是对信源的原始符号按一定的数学规则进行的一种变换。

了解

一、编码器模型由于信源编码可以不考虑抗干扰问题，所以它的数学模型比较简单。了解输入是信源符号集:x为编码器所用的编码符号集，包含r个元素{}，称为码符号(码元)。由码符号组成的输出序列称为码字。其长度称为码字长度或码长，全体码字的集合C称为码或码书。编码器将信源符号集中的信源符号

(或长为N的信源符号序列)变成由码符号组成的长为的与信源符号一一对应的输出序列。即:理解

二、码的分类根据码符号集合X中码元个数的不同以及码字长度是否一致，有以下一些常用的编码形式：

(1)

二元码和r元码若码符号集，编码所得码字为一些二元序列，则称二元码。二元码是数字通信与计算机系统中最常用的一种码。若码符号集有r个元素，则称r元码。理解

(2)等长码若一组码中所有码字的长度都相同----（即），则称为等长码。理解

(3)

变长码若一组码中码字的码长各不相同(即码字长度不等)，则称为变长码。如表中“编码1”为等长码，“编码2”为变长码。信源符号si符号出现概率p(si)编码1编码2s1p(s1)000s2p(s2)0101s3p(s3)10001s4p(s4)11101理解(4)非奇异码若一组码中所有码字都不相同(即所有信源符号映射到不同的码符号序列)，则称为非奇异码。则称码C为非奇异码。理解

（5）奇异码若一组码中有相同的码字，则为奇异码。则称码C为奇异码。理解概率信源符号

编码1编码2编码3编码4编码51/20000011/4010110011/8101001100011/81110111110001如表中的“编码2”是奇异码，其他码是非奇异码。理解

（6）同价码若码符号集X：{}中每个码符号所占的传输时间都相同，则所得的码为同价码。我们一般讨论同价码，对同价码来说等长码中每个码字的传输时间相同，而变长码中每个码字的传输时间就不一定相同。

如：电报中常用的莫尔斯码是非同价码，其码符号点（.）和划（-）所占的传输时间不相同。理解

（7）码的N次扩展码假定某码C，它把信源中的符号一一变换成码C中的码字，则码C的N次扩展码是所有N个码字组成的码字序列的集合。理解

例如：若码满足：则码C的N次扩展码集合,其中：

即码C的N次扩展码中，每个码字与信源的N次扩展信源中的每个信源符号是一一对应的：理解例信源符号ai码字信源符号ai码字a100a5010a2001a60101a30001……a40111a16111111信源符号si符号出现概率p(si)编码1编码2s1p(s1)000s2p(s2)0101s3p(s3)10001s4p(s4)11111求编码2的2次扩展掌握

（8）惟一可译码若任意一串有限长的码符号序列只能被惟一地译成所对应的信源符号序列，则此码称为惟一可译码（或称单义可译码）。否则就称为非惟一可译码或非单义可译码。若要使某一码为惟一可译码，则对于任意给定的有限长的码符号序列，只能被惟一地分割成一个个的码字。理解

例如：对于二元码，当任意给定一串码字序列，例如“10001101”，只可唯一地划分为1,00,01,1,01，因此是惟一可译码；而对另一个二元码，当码字序列为“01001”时，可划分为0,10,01或01,0,01，所以是非惟一可译的。理解

对惟一可译码又分为即时码和非即时码：如果在接收端收到一个完整的码字后，就能立即进行译码，这样的码叫做即时码；而在接收端收到一个完整的码字后，还需等下一个码字接收后才能判断是否可以译码，这样的码叫做非即时码。即时码又称为非延长码，对即时码而言，在码本中任意一个码字都不是其它码字的前缀部分。对非即时码来说，有的码是惟一可译的，有的码是非惟一可译的，主要取决于码的总体结构。信源符号si符号出现概率p(si)编码1编码2s1p(s1)11s2p(s2)1001s3p(s3)100001s4p(s4)10000001理解信源符号ai符号出现概率p(ai)码1码2码3码4a11/20011a21/411101001a31/80000100001a41/8110110000001

码1是奇异码，码2是非奇异码。码2不是唯一可译码，码3是。又如，码字{0，10，11}是一种唯一可译码。因为任意一串有限长码序列，例如100

111

000，只能被分割成10，0，11，10，0，0。任何其他分割法都会产生一些非定义的码字。理解信源符号ai符号出现概率p(ai)码1码2码3码4a11/20011a21/411101001a31/80000100001a41/8110110000001

即时码要求任何一个码字都不是其他码字的前缀部分，所以也叫做异前缀码/非延长码。如上表中的码4。如果接收端收到一个完整的码字后，不能立即译码，必须结合后续的码元序列才能进行译码，称为非即时码。如码3。可见，唯一可译码不一定是即时码，因为非即时码(延长码)也具有唯一可译性。理解了解5.2等长码

一般说来，若要实现无失真的编码，这不但要求信源符号与码字是一一对应的，而且要求所编的码必须是唯一可译码。否则，所编的码不具有唯一可译码性，就会引起译码带来的错误与失真。

对于等长码来说，若等长码是非奇异码，则它的任意有限长N次扩展码一定也是非奇异码。因此等长非奇异码一定是唯一可译码。理解

此式表明，只有当长的码符号序列数大于或等于N次扩展信源的符号数时，才可能存在等长非奇异码。理解例：

英文电报有32个符号(26个字母加上6个字符),请问对信源符号进行二进制编码，要想有唯一可译码，码长至少为多少？解：

r=2,q=32,N=1，要想有唯一可译码，则理解例：对英文电报得32个符号进行二元编码，根据上述关系：P60页知道英文的极限熵是1.4bit,远小于5bit，也就是说，5个二元码符号只携带1.4bit的信息量，实际上，5个二元符号最多可以携带5bit信息量。可以做到让平均码长缩短，提高信息传输率理解

举例说明为什么每个信源符号平均所需的码长可以减少：

设信源而其依赖关系为：理解而其依赖关系为：传递矩阵理解若不考虑符号间的依赖关系，可得码长l＝2若考虑符号间的依赖关系，则对此信源作二次扩展

可见，由于符号间依赖关系的存在，扩展后许多符号出现的概率为0，此信源只有4个字符，可得码长，平均每个信源符号所需码符号为理解

考虑到英文字母间的相关性，对信源作N次扩展，在扩展后的信源(也就是句子）中，有些句子是有意义的，而有些句子是没有意义的，可以只对有意义的句子编码，而对那些没有意义的句子不进行编码，这样就可以缩短每个信源符号所需的码长。

等长信源编码定理给出了进行等长信源编码所需码长的极限值。例：英文电报了解5.4等长信源编码定理信源编码有等长和变长两种方法。等长编码：码字长度是固定的，相应的编码定理称为定长信源编码定理，是寻求最小码字长度的编码方法。变长编码：码字长度是变值，相应的编码定理称为变长编码定理。这里的码字长度最小意味着数学期望最小。理解了解

定理中的公式改写成不等式左边表示长为L的码符号序列能载荷的最大信息量，右边代表长为N的信源序列平均携带的信息量。所以定长编码定理告诉我们：只要码字传输的信息量大于信源携带的信息量，总可实现几乎无失真编码。了解最佳编码效率为：编码效率：编码后信源的信息传输率：了解当允许错误概率小于δ时，信源符号序列的长度N：为自信息的方差如果为最佳编码，则由式5.32了解例5-1：设离散无记忆信源求信源序列的长度。对S采取等长二元编码，要求编码效率允许错误概率了解5.5变长码5.5.1唯一可译变长码与即时码

优点：变长码往往在N不很大时就可编出效率很高而且无失真的码。

5.5变长码5.5.1唯一可译变长码与即时码

变长码的要求：变长码必须是唯一可译码，才能实现无失真编码。变长码不但码本身必须是非奇异的，而且其任意有限长N次扩展码也都必须是非奇异的。所以唯一可译变长码的任意有限长N次扩展码都是非奇异的。了解信源符号ai符号出现概率p(ai)码1码2码3码4a11/20011a21/411101001a31/80000100001a41/8110110000001

观察表中的各个码。表5.4掌握码2二次扩展掌握掌握掌握5.5.2即时码的树图构造法即时码的一种简单构造方法是树图法。对于给定码字的全体集合C，可用码树来描述它。所谓树，既有根、枝，又有节点。图中最上端A点为根，从根出发向下伸出树枝，树枝的数目等于码符号的总数r。树枝的尽头为节点，从节点出发再伸出树枝，每次每个节点伸出r枝，依次下去构成一棵树。了解在下图中，当某一个节点被安排为码字后，就不再继续伸枝，此节点称为终端节点(用粗黑点表示)。其他节点称为中间节点，不安排为码字(用空心圈表示)，给每个节点所伸出的树枝分别从左向右标上码符号0，1，…，r。了解任一即时码都可用树图法来表示。当码字长度给定时，即时码不是唯一的。在每个节点上都有r个分枝的树称为整树（满树），否则称为非整树（非满树）。了解了解5.5.3克拉夫特（Kraft)不等式掌握

例：设二进制码树中X={，，，}，对应的，，，，由上述定理，可得因此不存在满足这种码长的唯一可译码。掌握a1=1

01

01

01a2=01a3=001a4=000{1，01，001，001}惟一可译码；

{1，01，010，000}

不是惟一可译码；均满足克劳夫特不等式掌握

注意：不满足克拉夫特不等式的码，一定不是唯一可译码。码长满足克拉夫特不等式的码，也不一定是唯一可译码。克拉夫特不等式只是说明唯一可译码是否存在，并不能作为一种码制是否是唯一可译码的判断依据。了解5.5.4唯一可译变长码的判断法

有限长的码符号序列能译成两种不同的码字序列，此码一定不是唯一可译变长码。如下图：

唯一可译码的判断方法将码C中所有可能的尾随后缀组成一个集合F，当且仅当集合F中没有包含任一码字，则可判断此码C为唯一可译码。

掌握

集合F的构成方法：首先，观察码C中最短的码字是否是其它码字的前缀，若是，将其所有可能的尾随后缀排列出。这些尾随后缀又有可能是某些码字的前缀或者最短码字是这些尾随后缀的前缀，再将这些尾随后缀产生的新的尾随后缀列出.C={0，10，1100，1110，1011，1101}掌握然后再观察这些新的尾随后缀是否是某些码字的前缀，再将产生的尾随后缀列出，依此下去，直到没有一个尾随后缀是码字的前缀为止。

这样获得了由最短的码字引起的所有尾随后缀，列出上述步骤将所有码字可能产生的尾随后缀。由此得到由码C的所有可能的尾随后缀的集合F。C={0，10，1100，1110，1011，1101}

例5.2：设码C={0，10，1100，1110，1011，1101}，根据上述测试方法，判断是否是唯一可译码。

解：1.先看最短的码字：“0”，它不是其他码字前缀，所以没有尾随后缀。

2.再观察码字“10”，它是码字“1011”的前缀，因此有尾随后缀：掌握

所以，集合F={11，00，10，01}，其中“10”为码字，故码C不是唯一可译码。C={0，10，1100，1110，1011，1101}掌握掌握练习：设消息集合中共有7个消息，分别为被编码成对应的码字，判断是否是唯一可译码。掌握S0S1S2S3S4S5S6S7S8adebdebaddeb0cbbcdebcdeadabbbaddebbbcde结论：当N>7时，Sn为空集，而在S5中包含S0中的码字，故而S0不是唯一可译码。例5-5：设消息集合中共有7个消息，分别为被编码成对应的码字，判断是否是唯一可译码。5.6变长信源编码定理

对同一信源编成即时码有许多种。究竟哪一种最好呢？从高效率传输信息的观点来考虑，选择由短的码符号组成的码字，即用码长作为选择准则。如概率大的符号用短码，概率小的用较长的码，使得编码后平均码长降低，从而提高编码效率。

因此准则：码的平均长度。

理解

设信源为编码后的码字为

对应的码长分布为