第五章信源编码(编码定义及定长编码).

1、第五章第五章 信源编码信源编码5.1编码的定义编码的定义5.2无失真信源编码无失真信源编码 5.2.1定长编码定理定长编码定理31456002张安然张安然回顾：为什么进行信源编码？回顾：为什么进行信源编码？理论上，信源传送信息所需要的信息率：极限熵理论上，信源传送信息所需要的信息率：极限熵H（X）或信息率失真函数或信息率失真函数R（D）.极限熵极限熵H（X） ：多符号离散平稳信源实际上就多符号离散平稳信源实际上就是原始信源在不断地发出符号，随着信源之间的是原始信源在不断地发出符号，随着信源之间的依赖关系（即信源的相关性）变多，信源的实际依赖关系（即信源的相关性）变多，信源的实际熵越小（第二章熵

2、越小（第二章P32-33证明），越趋于证明），越趋于H（X）。）。所以所以H（X）是离散平稳有记忆信源平均每发一）是离散平稳有记忆信源平均每发一个符号提供的信息量的个符号提供的信息量的最小值最小值。信息率失真函数信息率失真函数R（D）：从允许一定失真的条件）：从允许一定失真的条件下，我们去寻找可以用较小的信息率来传送信息，下，我们去寻找可以用较小的信息率来传送信息，即去掉某些不必要的成分，这时得到的信息率的即去掉某些不必要的成分，这时得到的信息率的最小值最小值是是R（D）。）。由此可见，极限熵由此可见，极限熵H（X）或信息率失真函数或信息率失真函数R（D）是理论上传送信息的）是理论上传送信息的

3、最小值最小值。而实际上，。而实际上，信源发出消息时包含了信源发出消息时包含了多余信息多余信息，即存在冗余度，即存在冗余度，冗余度体现了信源输出信号的信息携带效率。冗余度体现了信源输出信号的信息携带效率。冗余度冗余度定义：衡量信源发出消息时包含了多余信息的物定义：衡量信源发出消息时包含了多余信息的物理量理量来源：来源：1.信源符号的相关性。相关程度越大，信源的实信源符号的相关性。相关程度越大，信源的实际上越小，越趋向于际上越小，越趋向于H（X） 。2.信源符号分布的不均匀性。等概率分布时信源信源符号分布的不均匀性。等概率分布时信源熵最大，不均匀分布时，信源熵减小。当各符号熵最大，不均匀分布时，信

4、源熵减小。当各符号之间不存在依赖关系且为等概率分布时，信源实之间不存在依赖关系且为等概率分布时，信源实际熵趋于最大熵际熵趋于最大熵H0（X） 下面，以英文为例，计算文字信源的冗余度：下面，以英文为例，计算文字信源的冗余度：首先给出英文字母（含空档）出现概率如下：首先给出英文字母（含空档）出现概率如下：下面，首先求得独立等概率情况，即下面，首先求得独立等概率情况，即其次，计算独立不等概率情况，其次，计算独立不等概率情况，再次，若仅考虑字母有一维相关性，求再次，若仅考虑字母有一维相关性，求H2最后，利用统计推断方法求出，由于采用的逼近的方法和最后，利用统计推断方法求出，由于采用的逼近的方法和所取的

5、样本的不同，推算值也有不同，这里采用所取的样本的不同，推算值也有不同，这里采用Shannon的推断值。的推断值。bitH76. 427log20bitppHiii03. 4log2711bitH32. 32bitH4 . 1采用等概率下传送方式，计算得采用等概率下传送方式，计算得这样，可以计算出这样，可以计算出R=0.71。这一结论说明，英文。这一结论说明，英文信源，从理论上看信源，从理论上看71是多余成分。直观地说是多余成分。直观地说100页英文书，理论上看仅有页英文书，理论上看仅有29页是有效的，其页是有效的，其余余71页是多余的。正是由于这一多余量的存在，页是多余的。正是由于这一多余量的

6、存在，才有可能对英文信源进行压缩编码。才有可能对英文信源进行压缩编码。消息的冗余，特别是大量的冗余，为我们提高通消息的冗余，特别是大量的冗余，为我们提高通信效率，压缩信号容量提供了基础。为了提高传信效率，压缩信号容量提供了基础。为了提高传输效率，对大量冗余进行压缩，即信源编码。输效率，对大量冗余进行压缩，即信源编码。000/11HHHHHR信源编码信源编码 信源编码是以提高通信的有效性为目的信源编码是以提高通信的有效性为目的编码。编码。 采用的一般方法是压缩每个信源符号的采用的一般方法是压缩每个信源符号的平均比特数。同样多的信息用较少的信平均比特数。同样多的信息用较少的信息率来传送，使单位时间

7、内传送的平均息率来传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。信息量增加，从而提高通信的有效性。 信源编码的目的就是要减少冗余，提高编信源编码的目的就是要减少冗余，提高编码效率码效率。信源编码的基本途径（即消除冗余度信源编码的基本途径（即消除冗余度来源的途径）有两个：来源的途径）有两个：使序列中的各个符号尽可能地互相独使序列中的各个符号尽可能地互相独立，即解除相关性；立，即解除相关性；使编码中各个符号出现的概率尽可能使编码中各个符号出现的概率尽可能地相等，即概率均匀化。地相等，即概率均匀化。 根据能否在解码后完全准确的恢复出原始消息根据能否在解码后完全准确的恢复出原始消息（可

8、逆）分为：（可逆）分为： 无失真信源编码无失真信源编码 限失真信源编码限失真信源编码 无失真编码只适用于离散信源；对于连续信源，无失真编码只适用于离散信源；对于连续信源，只能在失真受限制的情况下进行限失真编码。前只能在失真受限制的情况下进行限失真编码。前者主要用于文字、数据信源的压缩者主要用于文字、数据信源的压缩;后者主要用于后者主要用于图像、语音信源的压缩。图像、语音信源的压缩。 一般地：由于这些定理都要求符号数很大（参考一般地：由于这些定理都要求符号数很大（参考极限熵极限熵H（X）序列长趋向于序列长趋向于 ）才能使它的值接）才能使它的值接近所规定的值，因而这些定理被称为近所规定的值，因而这

9、些定理被称为极限定理。极限定理。1.无失真信源编码定理称为无失真信源编码定理称为第一极限定理第一极限定理； 2.信道编码定理信道编码定理(包括离散和连续信道包括离散和连续信道)称为称为第二极第二极限定理；限定理； 3.限失真信源编码定理称为限失真信源编码定理称为第三极限定理第三极限定理。 这些定理的完善化，是这些定理的完善化，是香农信息论香农信息论的主要内容。的主要内容。编码定理不但证明了必然存在一种编码方法，使编码定理不但证明了必然存在一种编码方法，使代码的平均长度可任意接近但不能低于符号熵，代码的平均长度可任意接近但不能低于符号熵，而且还阐明了达到这目标的途径，就是使概率与而且还阐明了达到

10、这目标的途径，就是使概率与码长匹配。码长匹配。例如之后学习的变长编码，使出现概率小的信源例如之后学习的变长编码，使出现概率小的信源符号用短码编，出现概率大的用长的码编，这样符号用短码编，出现概率大的用长的码编，这样就可以使平均每个信源符号的输出符号降低。以就可以使平均每个信源符号的输出符号降低。以哈夫曼编码为例：哈夫曼编码为例：哈夫曼编码的编码结果可以看出，信源出现符号小的哈夫曼编码的编码结果可以看出，信源出现符号小的a7编编码长度是码长度是4位，信源出现符号小的位，信源出现符号小的a1编码长度是编码长度是2位，平均位，平均码长计算得码长计算得2.72码元码元/符号，输出符号码长减小。符号，输

11、出符号码长减小。信源编码（主要内容）信源编码定理信源编码定理v 信源编码基本概念信源编码基本概念v 定长信源编码定长信源编码v 变长信源编码变长信源编码信源编码方法信源编码方法 离散信源编码离散信源编码 连续信源编码连续信源编码 相关信源编码相关信源编码 变换编码变换编码5.1编码的定义编码的定义分组码定义：分组码定义：将信源消息分成若干组，即符号序将信源消息分成若干组，即符号序列列Xi=xi1,xi2,.,xiL,序列中的每一个符号取自于符序列中的每一个符号取自于符号集号集A，xil属于属于a1 ， a2 ， ， ai ， ， an，而，而每个符号序列每个符号序列Xi依照固定的码表映射成一个

12、码字依照固定的码表映射成一个码字Yi，这样的码称为分组码，有时也叫块码。这样的码称为分组码，有时也叫块码。分组码百科定义：分组码百科定义：它把信源待发的信息序列按固它把信源待发的信息序列按固定的定的位一组划分成消息组位一组划分成消息组,再将每一消息组独立再将每一消息组独立变换成长为变换成长为n(n)的二进制数字组的二进制数字组,称为码字。称为码字。如果消息组的数目为如果消息组的数目为M(显然显然M2),由此所获得的由此所获得的M个码字的全体便称为码长为个码字的全体便称为码长为n、信息数目为、信息数目为M的的分组码分组码,记为记为【n，M】。 只有分组码才有对应的码表，而非分组码中不存在码表。只

13、有分组码才有对应的码表，而非分组码中不存在码表。编码定义：编码定义：二元信道（基本符号二元信道（基本符号0,1）中，若将信源）中，若将信源X通过通过这样的二元信道传输，就必须把信源符号这样的二元信道传输，就必须把信源符号ai 变换成有变换成有1.0符符号组成的码符号序列，这个过程就是信源编码。号组成的码符号序列，这个过程就是信源编码。编码的广泛定义：编码的广泛定义：编码是编码是信息信息从一种形式或格式转换为另从一种形式或格式转换为另一种形式的过程也称为计算机编程语言的代码简称编码。一种形式的过程也称为计算机编程语言的代码简称编码。用预先规定的方法将文字、数字或其它对象编成数码，或用预先规定的方

14、法将文字、数字或其它对象编成数码，或将信息、数据转换成规定的电脉冲信号。将信息、数据转换成规定的电脉冲信号。 我们之后介绍的是二元信道中的编码。我们之后介绍的是二元信道中的编码。信源编码器示意图信源符号集信源符号集X Xaa1 1,a,a2 2,a,an n ： 代表信源发出的消息，共有代表信源发出的消息，共有n n个信源符号。个信源符号。码表（码符号集）码表（码符号集） 码符号集中的元素称为码元或者码符号，适合信道传输。码符号集中的元素称为码元或者码符号，适合信道传输。码字集合码字集合Y=WY=W1 1,W,W2 2,W,Wn n ： 与信源符号一一对应，码字由码符号序列组成。与信源符号一一

15、对应，码字由码符号序列组成。一个简单的编码实例一个简单的编码实例【例例】对学生的成绩等级进行编码，分为优、良、对学生的成绩等级进行编码，分为优、良、中、差中、差4 4个个 等级。等级。信源符号集信源符号集X Xaa1 1,a,a2 2,a,an n =优、良、中、差优、良、中、差 用二元码，码符号集合为用二元码，码符号集合为0,10,1码字集合为码字集合为 Y=WY=W1 1,W,W2 2,W,Wn n=00,01,10,1100,01,10,11编码过程：编码过程：0000代表优，代表优，0101代表良，代表良，1010代表中，代表中，1111代代表差。每一个码字都是表差。每一个码字都是2

16、2个码符号组成的序列。个码符号组成的序列。信源符号信源符号符号出现概符号出现概率率p(ai)码码1码码2码码3码码4a11/20011a21/411101001a31/80000100001a41/8110110000001(1)奇异码与非奇异码书中定义：书中定义：若信源符号和码字是一一对应的，则若信源符号和码字是一一对应的，则该码是非奇异码；反之，是奇异码。这个定义可该码是非奇异码；反之，是奇异码。这个定义可以理解为数学意义上的映射，每一个符号均可以以理解为数学意义上的映射，每一个符号均可以在码字集合中找到唯一对应的码。在码字集合中找到唯一对应的码。华中科技大学书中定义：华中科技大学书中定义

17、：若一种码中的所有码字若一种码中的所有码字都互不相同，则称此分组码为非奇异码，否则称都互不相同，则称此分组码为非奇异码，否则称为奇异码。为奇异码。 可以看出，表中码可以看出，表中码1是奇异码，有两个是奇异码，有两个11码。其他码。其他是非奇异码是非奇异码（2）唯一可译码书中定义：书中定义：任意有限长序列，只能被分割成一个个的码字，便可以称任意有限长序列，只能被分割成一个个的码字，便可以称为唯一可译码。为唯一可译码。例如给定一个信源例如给定一个信源,编码后的码字有编码后的码字有0,，10，11，就是说信源只能变，就是说信源只能变出这三种码字。任意给定一个序列出这三种码字。任意给定一个序列1001

18、11000，按照分割成信源定义，按照分割成信源定义的三种码字可以分成的三种码字可以分成10,0,11,10,0,0唯一一种方式。任何其他分割法都唯一一种方式。任何其他分割法都会产生信源不能发出的码字。这种码字就是唯一可译码会产生信源不能发出的码字。这种码字就是唯一可译码码码1是奇异码，必定不能唯一可译，因为如果分到是奇异码，必定不能唯一可译，因为如果分到11码，就不确定是码，就不确定是信源发的信源发的a2还是还是a4码码2也不是唯一可译码，看码也不是唯一可译码，看码2的码字特点，若是序列中有一段码是的码字特点，若是序列中有一段码是00，我们即可以分成我们即可以分成00对应对应a3，也可以分成，

19、也可以分成0,0对应发两次对应发两次a1.码码3是唯一可译码。因为分解时只要遇到是唯一可译码。因为分解时只要遇到1就看后面有几个就看后面有几个0，确定唯，确定唯一译码一译码（3）非即时码和即时码）非即时码和即时码书中定义：如果接受端收到一个完整的码字后，书中定义：如果接受端收到一个完整的码字后，不能立即译码，还需要等下一个码字开始接受后不能立即译码，还需要等下一个码字开始接受后才能判断是否可以译码，这样的码叫做非即时码。才能判断是否可以译码，这样的码叫做非即时码。一个唯一可译码成为即时码的充要条件是其中任一个唯一可译码成为即时码的充要条件是其中任何一个码字都不是其它码字的前缀（前缀问题）何一个

20、码字都不是其它码字的前缀（前缀问题）这里这里是建立在唯一可译码基础上的，表中码是建立在唯一可译码基础上的，表中码3码码4是唯一可译码。是唯一可译码。码码3，接到，接到0后不能确定到某个码，码后不能确定到某个码，码4只要接到只要接到1就确认是哪个码了。就确认是哪个码了。消息消息概率概率C1C2C3C4C5C6u11/2000000101u21/4001011010000001u31/160100111101101001100u41/16011011111101100010101u51/1610001111111101001110110u61/161010111111111101111110111

21、(1)哪些是唯一可译码（2）哪些是即时码（3）计算平均码长和编码效率树图法树图法对于对于m进制树图，有树根、树枝和节点。进制树图，有树根、树枝和节点。p树图最顶部的节点称为树根；树图最顶部的节点称为树根；p每一个分支称为树枝；每一个分支称为树枝；p树枝的尽头称为节点，每个节点生出的树枝数目树枝的尽头称为节点，每个节点生出的树枝数目等于码符号数等于码符号数m；p从树根到终端节点各树枝代表的码符号顺次连接，从树根到终端节点各树枝代表的码符号顺次连接，就得到了编码码字。就得到了编码码字。m2的二进制树图A0101010101 0101000001010011100101110111一阶节点二阶节点三

22、阶节点整树与非整树考虑一个树有r阶节点p整树：码树的各个分支都延伸到最后一级端点，此时，将共有mr个码字；p非整树：码树中存在分支，没有延伸到最后一级端点，此时，将少于mr个码字。整树图例A0101010101 0101000001010011100101110111一阶节点二阶节点三阶节点非整树图例ABC11110001010010001=W4E即时码的构造树图法即时码的构造树图法编码：用树图法构造即时码，只要将信源符号全部对应于终端节点，而不编码：用树图法构造即时码，只要将信源符号全部对应于终端节点，而不是中间节点即可。这样就可以保证任何一个码字都不是其它码字的前缀是中间节点即可。这样就可

23、以保证任何一个码字都不是其它码字的前缀解码：按照码符号的顺序，从根节点依次查询到终端节点，就得到对应的解码：按照码符号的顺序，从根节点依次查询到终端节点，就得到对应的信源符号。再从根节点对剩下的码符号序列做相同的处理，直到处理完码信源符号。再从根节点对剩下的码符号序列做相同的处理，直到处理完码符号序列中所有的码符号符号序列中所有的码符号对应表中的码对应表中的码4 4分析分析A0101010101 0101000001010011100101110111一阶节点二阶节点三阶节点唯一可译码唯一可译码存在存在的充要条件的充要条件克劳夫特不等式：克劳夫特不等式：m是进制数，是进制数，n是信源符号数是信

24、源符号数1.唯一可译码必定满足不等式唯一可译码必定满足不等式2.满足不等式的码存在唯一可译码，但不一定是满足不等式的码存在唯一可译码，但不一定是唯一可译码唯一可译码此定理只证明存在性此定理只证明存在性11inKim例题p88无失真信源编码概念无失真信源编码无失真信源编码：o要求精确地复现信源的输出o保证信源的全部信息无损的送给信宿研究方法研究方法：o只考虑有效性，不考虑可靠性o将信道编解码看成一个无噪无损信道输入序列输入序列X长度长度L，每一位，每一位n种可能。编码后种可能。编码后Y的长度是的长度是KL，每一位每一位m种种可能。可能。北京邮电大学周炯槃的书北京邮电大学周炯槃的书中解释无失真条件

25、：中解释无失真条件： 无失真：无失真：nL mK(每个消息序列有对应的编码码组每个消息序列有对应的编码码组) 信源输出有效：信源输出有效： nL 大于等于大于等于mK（编码输出的码组数小于信源消息序（编码输出的码组数小于信源消息序列总数）列总数）信源编码输入输出XX1,X2,XLYY1,Y2,YKL2logloglogloglogLKmnmLnKmKnnLm两边取以 为底的对数，有或由无失真条件可得：编码的目的：希望传送编码的目的：希望传送Y时所需的信息率（信息率是通过时所需的信息率（信息率是通过接收到的信息可获得的发送信息的信息量接收到的信息可获得的发送信息的信息量,即互信息。单即互信息。单

26、位位:bit/符号）最小。符号）最小。 序列序列Y的最大信息量是的最大信息量是Klogm(序列长乘以每个符号的最序列长乘以每个符号的最大信息熵大信息熵)所以送一个信源符号所以送一个信源符号x需要的平均信息率为：需要的平均信息率为： 信息率最小就是找到一种编码方式使信息率最小就是找到一种编码方式使 最小。最小。mLKKLlogmLKLlog5.2.1定长编码定理定长编码定理n定义：各个码字码长都相等的码定义：各个码字码长都相等的码 n定长码中每个码字长度相等，所以只要定长码是非奇异定长码中每个码字长度相等，所以只要定长码是非奇异码，则必为唯一可译码码，则必为唯一可译码非奇异码唯一可译码即时码变长

27、码非奇异码唯一可译码即时码等长码消息消息概率概率C1C2C3C4C5C6u11/2000000101u21/4001011010000001u31/160100111101101001100u41/16011011111101100010101u51/1610001111111101001110110u61/161010111111111101111110111唯一可译定长码的存在条件唯一可译定长码的存在条件o对一个简单信源X进行定长编码，信源X存在唯一可译定长码的条件是： nmKn 其中，n是信源X的符号个数，m是信道基本码符号数，K 是定长码的码长。n 此为华中科技大学书中给出的定理。 o

28、英文电报有32个符号，即n32，n 26个英文字母加上6个标点符号o采用二元码时，则m2。o对信源X的逐个符号xi,i1,2,32进行二元编码，则 322Ko这就是说，每个英文电报符号至少要用5位二元符号进行编码才能得到唯一可译码定长信源编码定理（香农第一等长编码公式）定长信源编码定理（香农第一等长编码公式）o 定理内容：由L个符号组成的，每个符号的熵为HL（X）的无记忆平稳信源符号XX1,X2,XL，编码K个符号YY1,Y2,YKL（每个符号m种可能）对任意0,0，只要满足n 则当L足够大时，必可使译码差错小于。o 反之，若n 则当L足够大时，可以实现几乎无失真编码，译码错误概率趋于1，几乎

29、必定出错。logKmXL log2KmXL 定长信源编码定理的意义：o信源经过定长编码后，所能携带的信息量，一定要大于信源所携带的平均信息量(熵)。o若是小于，肯定不能无失真o若是等于，是临界状态。可能失真，也可能不失真。例如某信源有例如某信源有8种符号，种符号，L=1，信源序列熵，信源序列熵=log8=3bit/符符号。说明可以用号。说明可以用3bit的信息屡进行无失真编码。的信息屡进行无失真编码。采用二进制，采用二进制，0,1，等概时，等概时lb8=3 bit/符号（这是等概信符号（这是等概信源的）源的）若信源非等概，若信源非等概，p(ai)=0.4,0.18,0.1,0.1,0.07,0

30、.06,0.05,0.04,则则 H(X)=2.55 bit/符号的信息率在二进制中可以表示符号的信息率在二进制中可以表示22.55=5.856种码字，还有部分符号没有编码，当出现没编种码字，还有部分符号没有编码，当出现没编码的符号只能用其他符号代替，这就是失真。当码的符号只能用其他符号代替，这就是失真。当L足够大足够大时，有些符号的发生概率变得很小，差错率就变得很小。时，有些符号的发生概率变得很小，差错率就变得很小。典型序列及非典型序列的说明典型序列及非典型序列的说明引入信源的不等概统计特性后，无需将信源所有符号序列编码，仅对大概率典型序列编码，小的不编码（会失真），下面介绍北京邮电大学周炯

31、槃北京邮电大学周炯槃书中的对典型序列及非典型序列的说明：当L足够大时，根据大数定理，其中一些序列的集合会以趋向概率1出现，如果每一个序列等概率出现，这个概率为2 - L H （ X ）（这个计算是先确定等概率的信息上是 log 2 -LH（X）这个计算=LH(X),就是是平均每个序列的信息量，L长序列，序列中每个符号信息量是H(X)。）所以证明这个集合就是典型序列集合，共有2 LH（X）个典型序列，只需要对这些序列编码即可。这一概念对应本书中的互补这一概念对应本书中的互补集合。集合。L增大时，典型序列数目增多，小概率事件概率更小。根据切比雪夫不等式式中， 为信源序列的自信息方差， 为一正数。当

32、 和 均为定值时，P可以小于任一正数 。信源序列长度L必满足可以看出，L无穷大时，误码概率趋向于0.22)(LXPeH(X)-)I(x2i2EX ）（）（X222( )xL 信源编码效率信源编码效率对于等长编码， 编码效率一定是小于或等于1的数。对同一信源来说，若码的平均码长越短，信息传输率就越高，这时也越接近1。所以编码效率可以用来衡量各种编码方法在有效性方面的优劣。 编码后的实际码长最小可能码长载荷的最大信息量编码后每个信源符号能信息量信源的每个符号载荷的编码效率)()()(XHXHKXHLLL上面介绍到了，L无限长时，实际编码长变小，越接近最小可能码长。看下面的例子：设离散无记忆信源概率空间为信源熵为对信源符号采用定长二元编码，要求编码效率为若取L=1，则可以算出：