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

1、 第第5章章 无失真信源编码定理无失真信源编码定理邹小林邹小林2015.11.u 通信的实质是信息的传输。通信的实质是信息的传输。u 高效率、高质量传送信息是信息传输的基本问题！高效率、高质量传送信息是信息传输的基本问题！u 需要解决两个问题：需要解决两个问题： 第一，在不失真或允许一定失真的条件下，如何第一，在不失真或允许一定失真的条件下，如何 用尽可能少的符号来传送信源信息；用尽可能少的符号来传送信源信息； 第二，在信道受干扰的情况下，如何增加信号的抗第二，在信道受干扰的情况下，如何增加信号的抗 干扰能力，同时又使得信息传输率最大。干扰能力，同时又使得信息传输率最大。u 为了解决这两个问题

2、，引入为了解决这两个问题，引入信源编码信源编码和和信道编码信道编码。了解了解 抗干扰能力与信息传输率二者相互矛盾。编码抗干扰能力与信息传输率二者相互矛盾。编码定理证明，至少存在某种最佳的编码能够解决上定理证明，至少存在某种最佳的编码能够解决上述矛盾，做到既可靠又有效地传输信息。述矛盾，做到既可靠又有效地传输信息。了解了解 由于信源符号之间存在分布不均匀和相关性，由于信源符号之间存在分布不均匀和相关性，使得信源存在冗余度，使得信源存在冗余度，信源编码的主要任务信源编码的主要任务就是减就是减少冗余，提高编码效率。少冗余，提高编码效率。 具体说，就是针对信源输出符号序列的统计特具体说，就是针对信源输

3、出符号序列的统计特性，寻找一定的方法把信源输出符号序列变换为性，寻找一定的方法把信源输出符号序列变换为最最短短的码字序列。的码字序列。了解了解 信源编码常分为信源编码常分为无失真信源编码无失真信源编码和和限失真信限失真信源编码源编码， 前者主要用于文字、数据信源的压缩前者主要用于文字、数据信源的压缩; 后者主要用于图像、语音信源的压缩。后者主要用于图像、语音信源的压缩。了解了解u 无失真编码无失真编码 无失真编码是无失真编码是可逆可逆编码的基础。编码的基础。 可逆可逆是指当信源符号转换成代码后，可从代是指当信源符号转换成代码后，可从代码无失真地恢复原信源符号。码无失真地恢复原信源符号。了解了解

4、5.1 5.1 编码器编码器 编码实质上是对信源的原始符号按一定编码实质上是对信源的原始符号按一定的数学规则进行的一种变换。的数学规则进行的一种变换。 了解了解 一、编码器模型一、编码器模型 由于信源编码可以不考虑抗干扰问题，所以由于信源编码可以不考虑抗干扰问题，所以它的数学模型比较简单。它的数学模型比较简单。了解了解 输入是信源符号集输入是信源符号集: x为编码器所用的编码符号集，包含为编码器所用的编码符号集，包含r个元素个元素 ，称为，称为码符号码符号(码元码元) 。 由码符号由码符号 组成的输出序列组成的输出序列 称为称为码字码字。 其长度其长度 称为称为码字长度码字长度或或码长码长，全

5、体码字，全体码字 的的集合集合C称为称为码码或或码书码书 。 编码器将信源符号集中的编码器将信源符号集中的信源符号信源符号 (或长为或长为N的信源符号序列的信源符号序列 )变成由变成由码符号码符号组成的长为的组成的长为的与信源符号一一对应的输出序列。即与信源符号一一对应的输出序列。即 :12 ,qSs ss ixrxxx,.,21iWiliWisi12(1,2, )(1,2, )(,), iiiiiilijs iqW iqxxxxX 理解理解 二、码的分类二、码的分类 根据码符号集合根据码符号集合X中码元个数的不同以及码中码元个数的不同以及码字长度是否一致，有以下一些常用的编码形式：字长度是否

6、一致，有以下一些常用的编码形式： (1) 二元码和二元码和r元码元码 若码符号集若码符号集 ，编码所得码字为一些，编码所得码字为一些二元序列，则称二元序列，则称二元码二元码。二元码是数字通信与计。二元码是数字通信与计算机系统中最常用的一种码。算机系统中最常用的一种码。 若码符号集有若码符号集有 r 个元素，则称个元素，则称 r 元码元码。0,1X 理解理解 (2) 等长码等长码 若一组码中所有码字的长度都相同若一组码中所有码字的长度都相同-（即（即 ），则称为等长码。），则称为等长码。,1,ill iq 理解理解 (3) 变长码变长码 若一组码中码字的码长各不相同若一组码中码字的码长各不相同(

7、即码字长度即码字长度 不等不等)，则称为变长码，则称为变长码 。 如表中如表中“编码编码1”为等长码，为等长码，“编码编码2”为变长码。为变长码。il理解理解 (4)非奇异码非奇异码 若一组码中所有码字都不相同若一组码中所有码字都不相同(即所有信源符号即所有信源符号映射到不同的码符号序列映射到不同的码符号序列)，则称为非奇异码。，则称为非奇异码。 则称码则称码C为非奇异码。为非奇异码。CWWSssWWssjijijiji,理解理解 （5）奇异码奇异码 若一组码中有相同的码字，则为奇异码。若一组码中有相同的码字，则为奇异码。 则称码则称码C为奇异码。为奇异码。CWWSssWWssjijijiji

8、,理解理解()ip a1a2a3a4a概率如表中的如表中的“编码编码2”是奇异码，其他码是非奇异码。是奇异码，其他码是非奇异码。理解理解 （6）同价码同价码 若码符号集若码符号集X： 中每个码符号所占的传输中每个码符号所占的传输时间都相同，则所得的码为同价码。时间都相同，则所得的码为同价码。 我们一般讨论同价码，对同价码来说等长码中每个码我们一般讨论同价码，对同价码来说等长码中每个码字的传输时间相同，而变长码中每个码字的传输时间就字的传输时间相同，而变长码中每个码字的传输时间就不一定相同。不一定相同。 如如：电报中常用的莫尔斯码是非同价码，其码符号点：电报中常用的莫尔斯码是非同价码，其码符号点

9、（.）和划（）和划（-）所占的传输时间不相同。）所占的传输时间不相同。rxxx,.,21理解理解 （7）码的码的N次扩展码次扩展码 假定某码假定某码C，它把信源，它把信源 中的符中的符号号 一一变换成码一一变换成码C中的码字中的码字 ，则码，则码C的的N次扩次扩展码是所有展码是所有N个码字组成的码字序列的集合。个码字组成的码字序列的集合。12 ,qSs ss isiW理解理解 例如：若码例如：若码 满足：满足： 则码则码C的的N次扩展码集合次扩展码集合 ,其中：其中： 即码即码C的的N次扩展码中，每个码字次扩展码中，每个码字 与信源的与信源的N次扩次扩展信源展信源 中的每个信源符号中的每个信源

10、符号 是一一对应的：是一一对应的：12,qCW WW 12(,), ,iiiiiiliilsWxxxsS xX 12,NqBB BB 121,; ,1, ; 1,NNiiiiNBW WWiiqiqiBNS12,iiiiNsss 12(,), ,NlNiiiiiiiBW WWSWC理解理解例例求编码2的2次扩展掌握掌握 （8）惟一可译码惟一可译码 若任意一串有限长的码符号序列只能被惟一若任意一串有限长的码符号序列只能被惟一地译成所对应的信源符号序列，则此码称为地译成所对应的信源符号序列，则此码称为惟一惟一可译码可译码（或称（或称单义可译码单义可译码）。否则就称为非惟一）。否则就称为非惟一可译码或

11、非单义可译码。可译码或非单义可译码。 若要使某一码为惟一可译码，则对于任意给若要使某一码为惟一可译码，则对于任意给定的有限长的码符号序列，只能被惟一地分割成定的有限长的码符号序列，只能被惟一地分割成一个个的码字。一个个的码字。理解理解 例如例如：对于二元码：对于二元码 ，当任意给定一，当任意给定一串码字序列，例如串码字序列，例如“10001101”，只可唯一地划，只可唯一地划分为分为1,00,01,1,01，因此是惟一可译码；而对另，因此是惟一可译码；而对另一个二元码一个二元码 ，当码字序列为，当码字序列为“01001”时，可划分为时，可划分为0,10,01或或01,0,01，所以，所以是非惟

12、一可译的。是非惟一可译的。11,01,00C 20,10,01C 理解理解 对惟一可译码又分为对惟一可译码又分为即时码即时码和和非即时码非即时码：l 如果在接收端收到一个完整的码字后，就能立即进行如果在接收端收到一个完整的码字后，就能立即进行译码，这样的码叫做译码，这样的码叫做即时码即时码；l 而在接收端收到一个完整的码字后，还需等下一个码而在接收端收到一个完整的码字后，还需等下一个码字接收后才能判断是否可以译码，这样的码叫做字接收后才能判断是否可以译码，这样的码叫做非即非即时码时码。 即时码又称为非延长码，对即时码而言，在码本中即时码又称为非延长码，对即时码而言，在码本中任意一个码字都不是其

13、它码字的前缀部分。对非即时任意一个码字都不是其它码字的前缀部分。对非即时码来说，有的码是惟一可译的，有的码是非惟一可译码来说，有的码是惟一可译的，有的码是非惟一可译的，主要取决于码的总体结构。的，主要取决于码的总体结构。理解理解u 码码1是奇异码，码是奇异码，码2是非奇异码。是非奇异码。u 码码2不是唯一可译码，码不是唯一可译码，码3是。是。又如，码字又如，码字0，10，11是一种唯一可译码。因为任意一串有是一种唯一可译码。因为任意一串有限长码序列，例如限长码序列，例如100111000，只能被分割成，只能被分割成10，0，11，10，0，0。任何其他分割法都会产生一些非定义的码字。任何其他分

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

15、2 等长码等长码 一般说来，若要实现无失真的编码，这不但要一般说来，若要实现无失真的编码，这不但要求信源符号与码字是一一对应的，而且要求所编的求信源符号与码字是一一对应的，而且要求所编的码必须是唯一可译码。否则，所编的码不具有唯一码必须是唯一可译码。否则，所编的码不具有唯一可译码性，就会引起译码带来的错误与失真。可译码性，就会引起译码带来的错误与失真。 对于等长码来说，若等长码是非奇异码，对于等长码来说，若等长码是非奇异码，则它的任意有限长则它的任意有限长N次扩展码一定也是非奇次扩展码一定也是非奇异码。因此等长非奇异码一定是唯一可译码。异码。因此等长非奇异码一定是唯一可译码。理解理解 此式表明

16、，只有当此式表明，只有当 长的长的码符号序列数大于或等于码符号序列数大于或等于N次扩展信源的符号数时，才次扩展信源的符号数时，才可能存在等长非奇异码。可能存在等长非奇异码。l理解理解52log/32loglog/logrqNlqrNl5l即：理解理解例：对英文电报得32个符号进行二元编码，根据上述关系：log325log2l P60页知道英文的极限熵是1.4bit,远小于5bit，也就是说，5个二元码符号只携带1.4bit的信息量，实际上，5个二元符号最多可以携带5bit信息量。 可以做到让平均码长缩短，提高信息传输率理解理解 举例说明为什么每个信源符号平均所需的码长可以减少：举例说明为什么每

17、个信源符号平均所需的码长可以减少： 设信源设信源31241234( )( )()()()ssssSP sP sP sP sP s41( )1iiP s而其依赖关系为：而其依赖关系为：21124334(/)(/)(/)(/)1,(/)0jiP ssP ssP ssP ssP ss其余理解理解31241234( )( )()()()ssssSP sP sP sP sP s41( )1iiP s而其依赖关系为：而其依赖关系为：21124334(/)(/)(/)(/)1,(/)0jiP ssP ssP ssP ssP ss其余0100100000010010P1234ssss1234ssss传递矩阵理

18、解理解若不考虑符号间的依赖关系，可得码长l2若考虑符号间的依赖关系，则对此信源作二次扩展23 44 31 22 121 22 13 44 3()()()()()s ss ss ss sSP s sP s sP s sP s sP s()1ijijP s s 可见，由于符号间依赖关系的存在，扩展后许多符号出现的概率为0，此信源只有4个字符，可得码长 ，平均每个信源符号所需码符号为2l 12llN理解理解 考虑到英文字母间的相关性，对信源作考虑到英文字母间的相关性，对信源作N次扩展，在次扩展，在扩展后的信源扩展后的信源(也就是句子）中，有些句子是有意义的，而也就是句子）中，有些句子是有意义的，而有

19、些句子是没有意义的，可以只对有意义的句子编码，而有些句子是没有意义的，可以只对有意义的句子编码，而对那些没有意义的句子不进行编码，这样就可以缩短每个对那些没有意义的句子不进行编码，这样就可以缩短每个信源符号所需的码长。信源符号所需的码长。 等长信源编码定理给出了进行等长信源编码所需码长的等长信源编码定理给出了进行等长信源编码所需码长的极限值。极限值。例：英文电报例：英文电报了解了解5.4 5.4 等长信源编码定理等长信源编码定理信源编码有信源编码有等长等长和和变长变长两种方法。两种方法。等长编码等长编码：码字长度是固定的，相应的编码定理称为：码字长度是固定的，相应的编码定理称为 定长信源编码定

20、理，是寻求最小码字长度定长信源编码定理，是寻求最小码字长度 的编码方法。的编码方法。变长编码变长编码：码字长度是变值，相应的编码定理称为变：码字长度是变值，相应的编码定理称为变 长编码定理。这里的码字长度最小意味着长编码定理。这里的码字长度最小意味着 数学期望最小。数学期望最小。理解理解了解了解 定理中的公式改写成定理中的公式改写成l 不等式左边表示长为不等式左边表示长为L的码符号序列能载荷的最的码符号序列能载荷的最大信息量，大信息量，l 右边代表长为右边代表长为N的信源序列平均携带的信息量。的信源序列平均携带的信息量。 所以定长编码定理告诉我们：只要码字传输所以定长编码定理告诉我们：只要码字

21、传输的信息量大于信源携带的信息量，总可实现几乎的信息量大于信源携带的信息量，总可实现几乎无失真编码。无失真编码。)(log2SNHrl了解了解最佳编码效率为：( )( )( )H SH SRH S1( )H S( )( )logH SH SlRrN编码效率：rSHNllog)(log( )lrH SNloglRrN编码后信源的信息传输率：了解了解2iSIDN 2221SHSIDNiiSID为自信息的方差为自信息的方差如果为最佳编码，如果为最佳编码，则则由式5.32了解了解414321SSPS96. 0510求求信源序列的长度信源序列的长度。允许错误概率允许错误概率722221222222222

22、2221013. 4)1 ()()(4715. 0)()(log )(2)()( )()(2)()( )()(2)()( )()(2)()()()()(/811. 0)(NSHSIDNSHppSHSHSIESIESHSHSIESHSIESHSIESHSISHSIESHSIESIDSHiiiiiiiiiiiii则根据符号比特解：了解了解5.5 5.5 变长码变长码5.5.1 5.5.1 唯一可译变长码与即时码唯一可译变长码与即时码 优点：优点： 变长码往往在变长码往往在N不很大时就可编出效率很高不很大时就可编出效率很高而且无失真的码。而且无失真的码。 5.5 5.5 变长码变长码5.5.1 5.

23、5.1 唯一可译变长码与即时码唯一可译变长码与即时码 变长码的要求：变长码的要求： 变长码必须是唯一可译码，才能实现无失真编码。变长码必须是唯一可译码，才能实现无失真编码。1. 变长码不但码本身必须是非奇异的，而且其任意变长码不但码本身必须是非奇异的，而且其任意有限长有限长N次扩展码也都必须是非奇异的。所以唯一次扩展码也都必须是非奇异的。所以唯一可译变长码的任意有限长可译变长码的任意有限长N次扩展码都是非奇异的。次扩展码都是非奇异的。了解了解 观察表中的各个码。观察表中的各个码。表表5.4掌握掌握码2二次扩展掌握掌握掌握掌握掌握掌握5.5.2 5.5.2 即时码的树图构造法即时码的树图构造法即

24、时码的一种简单构造方法是即时码的一种简单构造方法是树图法树图法。对于给定码字的全体集合对于给定码字的全体集合C，可用，可用码树码树来描述它。来描述它。所谓所谓树树，既有根、枝，又有节点。，既有根、枝，又有节点。n图中最上端图中最上端A点为点为根根，从根出发，从根出发向下伸出树枝，树枝的数目等于向下伸出树枝，树枝的数目等于码符号的总数码符号的总数r。n树枝的尽头为树枝的尽头为节点节点，从节点出发，从节点出发再伸出树枝，每次每个节点伸出再伸出树枝，每次每个节点伸出r枝，依次下去构成一棵树。枝，依次下去构成一棵树。了解了解n在下图中，当某一个节点在下图中，当某一个节点被安排为码字后，就不再被安排为码

25、字后，就不再继续伸枝，此节点称为继续伸枝，此节点称为终终端节点端节点(用粗黑点表示用粗黑点表示)。n其他节点称为其他节点称为中间节点中间节点，不安排为码字不安排为码字(用空心圈表用空心圈表示示)，给每个节点所伸出的，给每个节点所伸出的树枝分别从左向右标上码树枝分别从左向右标上码符号符号0，1，r。了解了解任一即时码都可用任一即时码都可用树图法树图法来表示。来表示。当码字长度给定时，即时码不是唯一的。当码字长度给定时，即时码不是唯一的。在每个节点上都有在每个节点上都有r个分枝的树称为个分枝的树称为整树整树（满树满树），），否则称为否则称为非整树非整树（非满树非满树）。）。了解了解了解了解5.5.

26、3 5.5.3 克拉夫特（克拉夫特（Kraft)Kraft)不等式不等式掌握掌握 例例：设二进制码树中：设二进制码树中X= ， ， ， ，对应，对应的的 ， ， ， ，由上述定理，可得，由上述定理，可得因此不存在满足这种码长的唯一可译码。因此不存在满足这种码长的唯一可译码。18922222322141ili22l11l34l23l4a3a1a2a掌握掌握a1=1 0 1 0 1 0 1a2=01a3=001a4=000 1，01，001，001 惟一可译码；惟一可译码； 1，01，010，000 不是惟一可译码；不是惟一可译码； 均满足克劳夫特不等式均满足克劳夫特不等式122222332141

27、iKi掌握掌握 注意注意：不满足克拉夫特不等式的码，一定不是唯一：不满足克拉夫特不等式的码，一定不是唯一可译码。码长满足克拉夫特不等式的码，也不一可译码。码长满足克拉夫特不等式的码，也不一定是唯一可译码。定是唯一可译码。 克拉夫特不等式只是说明唯一可译码是否克拉夫特不等式只是说明唯一可译码是否存存在在，并不能作为一种码制是否是唯一可译码的判，并不能作为一种码制是否是唯一可译码的判断依据。断依据。了解了解5.5.4 5.5.4 唯一可译变长码的判断法唯一可译变长码的判断法 有限长的码符号序列能译成两种不同的码字序列，有限长的码符号序列能译成两种不同的码字序列，此码一定不是唯一可译变长码。如下图：

28、此码一定不是唯一可译变长码。如下图： 唯一可译码的唯一可译码的判断方法判断方法 将码将码C中所有中所有可能的尾随后缀可能的尾随后缀组成一个集合组成一个集合F，当，当且仅当集合且仅当集合F中没有包含任一码字，则可判断此中没有包含任一码字，则可判断此码码C为唯一可译码。为唯一可译码。 掌握掌握 集合集合F的构成方法的构成方法：首先，观察码首先，观察码C中最短的码字是否是其它码字的中最短的码字是否是其它码字的前缀，若是，将其所有可能的尾随后缀排列出。前缀，若是，将其所有可能的尾随后缀排列出。这些尾随后缀又有可能是某些码字的前缀或者最这些尾随后缀又有可能是某些码字的前缀或者最短码字是这些尾随后缀的前缀

29、，再将这些尾随后短码字是这些尾随后缀的前缀，再将这些尾随后缀产生的新的尾随后缀列出缀产生的新的尾随后缀列出.C=0，10，1100，1110，1011，1101掌握掌握然后再观察这些新的尾随后缀是否是某些码字的前然后再观察这些新的尾随后缀是否是某些码字的前缀，再将产生的尾随后缀列出，依此下去，直到没缀，再将产生的尾随后缀列出，依此下去，直到没有一个尾随后缀是码字的前缀为止。有一个尾随后缀是码字的前缀为止。 这样获得了由最短的码字引起的所有尾随后缀，这样获得了由最短的码字引起的所有尾随后缀，列出上述步骤将所有码字可能产生的尾随后缀。由列出上述步骤将所有码字可能产生的尾随后缀。由此得到由码此得到由

30、码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”为码

31、字，故码为码字，故码C不是唯一可译码。不是唯一可译码。C=0，10，1100，1110，1011，1101掌握掌握掌握掌握,7654321aaaaaaa,bbcdedebbadabbadca掌握掌握 S0 S1 S2 S3 S4 S5 S6 S7 S8 S0 S1 S2 S3 S4 S5 S6 S7 S8 a d eb de b a d eb de b ad ad d eb 0 d eb 0 c bb cde bcde c bb cde bcde ad ad abb abb bad bad deb deb bbcde bbcde,7654321aaaaaaa,bbcdedebbadabbadc

32、a5.6 5.6 变长信源编码定理变长信源编码定理 对同一信源编成即时码有许多种。对同一信源编成即时码有许多种。 究竟哪一种最好呢？究竟哪一种最好呢？ 从高效率传输信息的观点来考虑，选择由短的从高效率传输信息的观点来考虑，选择由短的码符号组成的码字，即用码符号组成的码字，即用码长码长作为选择准则。作为选择准则。 如概率大的符号用短码，概率小的用较长的码，如概率大的符号用短码，概率小的用较长的码，使得编码后平均码长降低，从而提高编码效率使得编码后平均码长降低，从而提高编码效率。 因此准则：因此准则：码的平均长度码的平均长度。 理解理解 设信源为设信源为 编码后的码字为编码后的码字为 对应的码长分布为对应的码长分布为 因为对唯一可译码来说，信源符号与码字是一一因为对唯一可译码来说，信源符号与码字是一一对应的，所以有对应的，所以有 则码的则码的平均长度平均长度为为它是每个信源符号平均需用的码元数。它是每个信源符号平均需用的码元数。qWWW,.,21qiiilspL1)()(,),(,),(,2211qqspsspsspsPSLLqlll,.,21),.,