第4章信源压缩编码基础

1、第第4 4章：信源编码基础章：信源编码基础l 信源编码的作用：信源编码的作用： 使信源适合于信道的传输，用信道能传输的符号来代使信源适合于信道的传输，用信道能传输的符号来代表信源发出的消息；表信源发出的消息； 在不失真或允许一定失真的条件下，用尽可能少的符在不失真或允许一定失真的条件下，用尽可能少的符号来传递信源消息，提高信息传输率。号来传递信源消息，提高信息传输率。 l 以提高通信以提高通信有效性有效性为目的为目的。通常通过。通常通过压缩信源的冗余压缩信源的冗余度度来实现。采用的一般方法是压缩每个信源符号的平来实现。采用的一般方法是压缩每个信源符号的平均码长。均码长。 信源编码概述l 信源编

2、码理论是信息论的一个重要分支，其理论基础信源编码理论是信息论的一个重要分支，其理论基础是信源编码的两个定理：是信源编码的两个定理：无失真信源编码定理无失真信源编码定理限失真信源编码定理限失真信源编码定理l 本章主要介绍本章主要介绍无失真信源编码无失真信源编码，它实质上是一种统，它实质上是一种统计匹配编码，根据信源的不同概率分布而选用与之相计匹配编码，根据信源的不同概率分布而选用与之相匹配的码。匹配的码。 信源编码概述信源编码概述l 信源的统计剩余度主要决定于以下两个因素信源的统计剩余度主要决定于以下两个因素 ：1）无记忆信源中，符号概率分布的非均匀性；）无记忆信源中，符号概率分布的非均匀性；2

3、）有记忆信源中，符号间的相关性及）有记忆信源中，符号间的相关性及符号概率分布符号概率分布的非均匀性的非均匀性。 信源编码概述信源编码概述l怎样压缩信源的冗余度？怎样压缩信源的冗余度？1) 去除码符号间的相关性。去除码符号间的相关性。2) 使码符号等概分布。使码符号等概分布。信源编码器模型信源编码器模型信宿信宿信道信道信源信源编码器编码器译码器译码器YXSSl 信源编码：将信源符号序列按一定的数学规律映射信源编码：将信源符号序列按一定的数学规律映射成码符号序列的过程。成码符号序列的过程。qsssS,2112 ,rXx xx 图图1 信源编码器模型信源编码器模型4.1 无失真可变长信源编码定理无失

4、真可变长信源编码定理l 将信源符号集中的符号将信源符号集中的符号 （或者长为（或者长为N的信源符号序的信源符号序列）映射成由码符号列）映射成由码符号 组成的长度为组成的长度为 的一一对应的的一一对应的码符号序列码符号序列 。编码器编码器,.,:21rxxxX码字码字qsssS,2112liiiiiwx xx信源编码器模型信源编码器模型ixisil12,qCw wwiw信源符号sip(si)码1码2s1p(s1)=1/2000s2p(s2)=1/40101s3p(s3)=1/810001s4p(s4)=1/811111例例: 4.112341234( )()()() ssssSp sp sp s

5、p sP信源编码器模型信源编码器模型l编码器输出的码符号序列编码器输出的码符号序列 称为称为码字码字；长度；长度 称为码称为码字长度，简称字长度，简称码长码长；全体码字的集合；全体码字的集合C称为称为码码。l若码符号集合为若码符号集合为X=0,1，则所得的码字都是二元序，则所得的码字都是二元序列，称为列，称为二元码二元码。关于编码的一些术语关于编码的一些术语iwisiwill将信源符号集中的每个信源符号将信源符号集中的每个信源符号 固定的映射成某固定的映射成某一个码字一个码字 ，这样的码称为，这样的码称为分组码分组码。 l若一个码中所有码字的码长都相等，则称为若一个码中所有码字的码长都相等，则

6、称为定长码定长码； 否则为否则为变长码变长码。1. 奇异性奇异性若一个码中所有码字互不相同，则称为若一个码中所有码字互不相同，则称为非奇异码非奇异码；否则为否则为奇异码奇异码。信源符号信源符号si码码1码码2s1s2s3s401100110100001一、信源编码的相关概念一、信源编码的相关概念2. 唯一可译性唯一可译性l 若任意一串有限长的码符号序列只能被唯一地译为若任意一串有限长的码符号序列只能被唯一地译为对应的信源符号序列，则称此码为对应的信源符号序列，则称此码为唯一可译码唯一可译码。信源符号信源符号si码码1码码2码码3s1s2s3s401100110100001010110111一、

7、信源编码的相关概念一、信源编码的相关概念l 唯一可译码应当满足的条件唯一可译码应当满足的条件(1,2,., )(1,2,., )iiw iqs iq码字与信源符号一一对应码字与信源符号一一对应2) 不同的信源符号序列对应不同的码字序列不同的信源符号序列对应不同的码字序列1) 2. 唯一可译性唯一可译性一、信源编码的相关概念一、信源编码的相关概念2. 唯一可译性唯一可译性例：例：1)11001104321ssss2s4s奇异码奇异码11译码译码奇异码一定不是唯一可译码奇异码一定不是唯一可译码一、信源编码的相关概念一、信源编码的相关概念2. 唯一可译性唯一可译性2)01001004321ssss非

8、奇异码非奇异码14321sssss2334ssss0 1 00 00 1 00 10 00 0 1 0译码译码译码译码一、信源编码的相关概念一、信源编码的相关概念2. 唯一可译性唯一可译性3)111001004321ssss等长码等长码非奇异码非奇异码0 0 0 1 1 0 1 14321ssss唯一可译码唯一可译码译码译码一、信源编码的相关概念一、信源编码的相关概念唯一可译定长码存在的条件唯一可译定长码存在的条件l对于定长码，非奇异码一定是唯一可译码。对于定长码，非奇异码一定是唯一可译码。l所谓非奇异码，即信源符号集中的每一个信源符号所谓非奇异码，即信源符号集中的每一个信源符号与码中的某一个

9、码字与码中的某一个码字 一一对应。一一对应。l设信源符号集中共有设信源符号集中共有 个符号，个符号， ， 码符号集中共有码符号集中共有 种码元，种码元， ， 定长码码长为定长码码长为 , 则要满足非奇异性必然有则要满足非奇异性必然有lrq 12,qSs ss,.,:21rxxxXiwislrq该条件是必要条件，而不是充分条件。该条件是必要条件，而不是充分条件。二、定长码及定长信源编码定理二、定长码及定长信源编码定理例：英文字母表中，每一字母用定长编码转换成二进制例：英文字母表中，每一字母用定长编码转换成二进制表示，码字的最短长度是多少？表示，码字的最短长度是多少？26q 解：解：2r 信源符号

10、数信源符号数码符号数码符号数lrqloglog264.7loglog2qlrmin5l二、定长码及定长信源编码定理二、定长码及定长信源编码定理若用若用r元码对信源元码对信源SN进行编码，设进行编码，设S中每个符号所需中每个符号所需的平均码长为的平均码长为 则定义：则定义：为该码的编码效率为该码的编码效率NLNrNLsHNlog)(18 要做到无失真的信源编码，平均每个信源符号要做到无失真的信源编码，平均每个信源符号所需最少的所需最少的r元码元数为信源的熵元码元数为信源的熵 。 即即 它是无失真信源压缩的极限值。它是无失真信源压缩的极限值。 若编码的平均码长小于信源的熵值若编码的平均码长小于信源

11、的熵值 ，则惟，则惟一可译码不存在，在译码或反变换时必然要带一可译码不存在，在译码或反变换时必然要带来失真或差错。来失真或差错。 通过对扩展信源进行变长编码，当通过对扩展信源进行变长编码，当N时，时，平均码长平均码长( )rHS( )rHS( )rHS19 无失真信源编码的实质：无失真信源编码的实质： 对离散信源进行适当的变换，使变换后形对离散信源进行适当的变换，使变换后形成的新的码符号信源成的新的码符号信源(即信道的输入信源即信道的输入信源)尽可尽可能为等概率分布，以使新信源的每个码符号平能为等概率分布，以使新信源的每个码符号平均所含的信息量达到最大，使信道的信息传输均所含的信息量达到最大，

12、使信道的信息传输率达到信道容量，实现信源与信道理想的统计率达到信道容量，实现信源与信道理想的统计匹配。这实际上就是香农第一定理的物理意义。匹配。这实际上就是香农第一定理的物理意义。20 为了衡量各种编码是否达到极限情况，定义变长为了衡量各种编码是否达到极限情况，定义变长码的编码效率为：码的编码效率为： 常通过编码效率来衡量各种编码的优劣常通过编码效率来衡量各种编码的优劣. 为了衡量各种编码与最佳码的差距，定义码的剩为了衡量各种编码与最佳码的差距，定义码的剩余度为：余度为： 信息传输率定义为：信息传输率定义为： 注意注意:虽然与在数值上相同，但它们的单位不同，编码虽然与在数值上相同，但它们的单位

13、不同，编码效率没有单位，而信息传输率的单位是比特效率没有单位，而信息传输率的单位是比特/码符号。码符号。LSHr)(LSHr)(11LSHR)(23:5321 为了使得平均编码长度为最小，必须将概率大为了使得平均编码长度为最小，必须将概率大的信息符号编以短的码字，概率小的符号编以的信息符号编以短的码字，概率小的符号编以长的码字。能获得最佳码（或次最佳码）的编长的码字。能获得最佳码（或次最佳码）的编码方法有很多。码方法有很多。 香农香农(shannon) 编码、费诺编码、费诺(Fano) 编码、霍夫编码、霍夫曼曼(Huffman)编码等就是代表。编码等就是代表。221 1 香农码香农码 香农第一

14、定理指出，可选择每个码字的长度满香农第一定理指出，可选择每个码字的长度满足关系式：足关系式： 或：或： x 表示不小于表示不小于 x 的整数。按不等式选择的的整数。按不等式选择的码长所构成的码称香农码。香农码满足克拉夫码长所构成的码称香农码。香农码满足克拉夫特不等式，所以一定存在对应码字的长度的惟特不等式，所以一定存在对应码字的长度的惟一可译码。一可译码。log()log()1(1, )iiip slp siq 1lo g(1,)()iiliqps 23:5323 一般情况下，按照香农编码方法编出来的码，一般情况下，按照香农编码方法编出来的码，其平均码长不是最短的，也即不是紧致码其平均码长不是

15、最短的，也即不是紧致码(最最佳码佳码)。只有当信源符号的概率分布使不等式。只有当信源符号的概率分布使不等式左边的等号成立时，编码效率才达到最高。左边的等号成立时，编码效率才达到最高。 香农码的编码步骤如下：香农码的编码步骤如下： 1）将个信源符号按概率递减的方式进行排列：）将个信源符号按概率递减的方式进行排列： 2）按香农不等式计算出每个信源符号的码长）按香农不等式计算出每个信源符号的码长 ； 3）为了编成惟一可译码，计算第）为了编成惟一可译码，计算第i个信源符号的个信源符号的累加概率累加概率 4）将累加概率）将累加概率 用二进制数表示。用二进制数表示。 5）取）取 对应二进制数的小数点后位构

16、成该信源符对应二进制数的小数点后位构成该信源符号的二进制码字。号的二进制码字。12qppp il11iikkPp iPiP23:5325()ip aiP1log( )ip sil1a2a3a4a5a6a7a概率累加概率码长信源符号对应的二进制数码字0.2000.0002.3430000.190.20.00112.4130010.180.390.01102.4830110.170.570.10012.5631000.150.740.10112.7431010.100.890.11103.34411100.010.990.11111106.6671111110例例:设信源共有七个信源符号，其概率分

17、布如表所设信源共有七个信源符号，其概率分布如表所示，试对该信源进行香农编码。示，试对该信源进行香农编码。 解解: 码的性能分析：码的性能分析： 通过计算可得此信源的熵通过计算可得此信源的熵: (比特符号比特符号) 而码的平均长度而码的平均长度: (二元码符号符二元码符号符号号) 编码效率：编码效率：71()()log()2.61iiiH Xp ap a 71()3 .1 4iiiLp al 0.831 23:53272 2 费诺码费诺码 费诺编码属于概率匹配编码，但它一般也不是最费诺编码属于概率匹配编码，但它一般也不是最佳的编码方法，只有当信源的概率分布呈现佳的编码方法，只有当信源的概率分布呈

18、现 分布形式的条件下，才能达到最佳码的性能。分布形式的条件下，才能达到最佳码的性能。( )ilip sr 23:5328 费诺码的编码步骤如下：费诺码的编码步骤如下： 1）信源符号以概率递减的次序排列起来；）信源符号以概率递减的次序排列起来； 2）将排列好的信源符号按概率值划分成两大组，使每组）将排列好的信源符号按概率值划分成两大组，使每组的概率之和接近于相等，并对每组各赋予一个二元码符号的概率之和接近于相等，并对每组各赋予一个二元码符号“0”和和“1”； 3）将每一大组的信源符号再分成两组，使划分后的两个）将每一大组的信源符号再分成两组，使划分后的两个组的概率之和接近于相等，再分别赋予一个二

19、元码符号；组的概率之和接近于相等，再分别赋予一个二元码符号； 4）依次下去，直至每个小组只剩一个信源符号为止；）依次下去，直至每个小组只剩一个信源符号为止； 5）信源符号所对应的码字即为费诺码。）信源符号所对应的码字即为费诺码。23:5329例例:将下列消息按二元费诺码方法进行编码。将下列消息按二元费诺码方法进行编码。23:5330 此信源的熵此信源的熵 (比特符号比特符号)， 而码的平均长度而码的平均长度 (二元码符号符号二元码符号符号) 显然，该码是紧致码，编码效率：显然，该码是紧致码，编码效率： 该码之所以能达到最佳，是因为信源符号的概率分布该码之所以能达到最佳，是因为信源符号的概率分布

20、正好满足式，否则，在一般情况下是无法达到编码效正好满足式，否则，在一般情况下是无法达到编码效率等于率等于“1”的。的。 ()2.75H X 2.75L 1 码的性能分析：码的性能分析：23:5331费诺码具有如下的性质：费诺码具有如下的性质： 费诺码的编码方法实际上是一种构造码树的方法，所以费诺码是即时码。费诺码的编码方法实际上是一种构造码树的方法，所以费诺码是即时码。 费诺码考虑了信源的统计特性，使概率大的信源符号能对应码长较短的费诺码考虑了信源的统计特性，使概率大的信源符号能对应码长较短的码字，从而有效地提高了编码效率。码字，从而有效地提高了编码效率。 费诺码不一定是最佳码。因为费诺码编码

21、方法不一定能使短码得到充分费诺码不一定是最佳码。因为费诺码编码方法不一定能使短码得到充分利用利用:当信源符号较多时，若有一些符号概率分布很接近时，分两大组的组当信源符号较多时，若有一些符号概率分布很接近时，分两大组的组合方法就会很多。可能某种分大组的结果，会使后面小组的合方法就会很多。可能某种分大组的结果，会使后面小组的“概率和概率和”相相差较远，从而使平均码长增加。差较远，从而使平均码长增加。23:53323 3 霍夫曼码霍夫曼码 1952年，霍夫曼（年，霍夫曼（Huffman）提出了一种构造）提出了一种构造最佳码的方法，这是一种最佳的逐个符号的编最佳码的方法，这是一种最佳的逐个符号的编码方

22、法，一般就称作霍夫曼码。码方法，一般就称作霍夫曼码。 设信源设信源 ，其对应的概率分布为，其对应的概率分布为 ，则对二元霍夫曼码而言，则对二元霍夫曼码而言，其编码步骤如下：其编码步骤如下： 12 ,.,qSs ss 12(),.,iqp sppp 23:5333 1）将）将q个信源符号按概率递减的方式排列起来；个信源符号按概率递减的方式排列起来； 2）用）用“0”、“1”码符号分别表示概率最小的两个信源符码符号分别表示概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个新的符号，号，并将这两个概率最小的信源符号合并成一个新的符号，从而得到只包含从而得到只包含q-1个符号的新信源，称之

23、为个符号的新信源，称之为S信源的信源的S1缩缩减信源；减信源； 3）将缩减信源中的符号仍按概率大小以递减次序排列，）将缩减信源中的符号仍按概率大小以递减次序排列，再将其最后两个概率最小的符号合并成一个符号，并分别再将其最后两个概率最小的符号合并成一个符号，并分别用用“0”、“1”码符号表示，这样又形成了由码符号表示，这样又形成了由q-2个符号构个符号构成的缩减信源成的缩减信源S2； 4）依次继续下去，直到缩减信源只剩下两个符号为止，）依次继续下去，直到缩减信源只剩下两个符号为止，将这最后两个符号分别用将这最后两个符号分别用“0”、“1”码符号表示；码符号表示； 5）从最后一级缩减信源开始，向前

24、返回，沿信源缩减方）从最后一级缩减信源开始，向前返回，沿信源缩减方向的反方向取出所编的码元，得出各信源符号所对应的码向的反方向取出所编的码元，得出各信源符号所对应的码符号序列，即为对应信源符号的码字。符号序列，即为对应信源符号的码字。23:5334 例例:对离散无记忆信源对离散无记忆信源 进行霍夫曼编码。进行霍夫曼编码。 解解:编码过程如表所示：编码过程如表所示： 1)将信源符号按概率大小由大至小排序。将信源符号按概率大小由大至小排序。 2)从概率最小的两个信源符号和开始编码，并按一定的从概率最小的两个信源符号和开始编码，并按一定的规则赋予码符号，如下面的信源符号（小概率）为规则赋予码符号，如

25、下面的信源符号（小概率）为“1”，上面的信源符号（大概率）为上面的信源符号（大概率）为“0”。若两支路概率相等，。若两支路概率相等，仍为下面的信源符号为仍为下面的信源符号为“1” 上面的信源符号为上面的信源符号为“0”。 3)将已编码两个信源符号概率合并，重新排队，编码。将已编码两个信源符号概率合并，重新排队，编码。 4)重复步骤重复步骤3）直至合并概率等于）直至合并概率等于“1.0”为止。为止。 5)从概率等于从概率等于“1.0”端沿合并路线逆行至对应消息编码端沿合并路线逆行至对应消息编码.12345()0.40.20.20.10.1iSsssssp s 23:533523:5336 码的性

26、能分析：码的性能分析： 信源的熵为：信源的熵为：H(s)=2.12 (比特符号比特符号) 从从 ，可得平均码长为：，可得平均码长为： 编码效率为：编码效率为：4 , 4 , 3 , 2 , 1:il2 . 241 . 041 . 032 . 022 . 014 . 051iiilpL9636. 02 . 212. 2)(LsH23:5337 按霍夫曼码的编码方法，可知这种码有如下特征：按霍夫曼码的编码方法，可知这种码有如下特征： 它是一种分组码：各个信源符号都被映射成一组固定次它是一种分组码：各个信源符号都被映射成一组固定次序的码符号；序的码符号； 它是一种惟一可解的码：任何码符号序列只能以一

27、种方它是一种惟一可解的码：任何码符号序列只能以一种方式译码；式译码； 它是一种即时码：由于代表信源符号的节点都是终端节它是一种即时码：由于代表信源符号的节点都是终端节点，因此其编码不可能是其它终端节点对应的编码的前缀，点，因此其编码不可能是其它终端节点对应的编码的前缀，霍夫曼编码所得的码字一定是即时码。所以一串码符号中霍夫曼编码所得的码字一定是即时码。所以一串码符号中的每个码字都可不考虑其后的符号直接解码出来。的每个码字都可不考虑其后的符号直接解码出来。 霍夫曼码的译码：对接收到的霍夫曼码序列可通过从左到霍夫曼码的译码：对接收到的霍夫曼码序列可通过从左到右检查各个符号进行译码。右检查各个符号进

28、行译码。23:5338 说明：说明： 霍夫曼码是一种即时码，可用码树形式来表示。霍夫曼码是一种即时码，可用码树形式来表示。 每次对缩减信源最后两个概率最小的符号，用每次对缩减信源最后两个概率最小的符号，用“0”和和“1”码是可以任意的，所以可得到不同的码是可以任意的，所以可得到不同的码，但码长不变，平均码长也不变。码，但码长不变，平均码长也不变。当缩减信源中缩减合并后得到的新符号的概率当缩减信源中缩减合并后得到的新符号的概率与其他信源符号概率相同时，从编码方法上来说，与其他信源符号概率相同时，从编码方法上来说，它们概率的排序是没有限制的，因此也可得到不它们概率的排序是没有限制的，因此也可得到不

29、同的码。同的码。 即对给定信源，用霍夫曼编码方法得到的码并非是惟即对给定信源，用霍夫曼编码方法得到的码并非是惟一，但平均码长不变。一，但平均码长不变。三种编码的比较三种编码的比较Huffman:不唯一，但对信源没有特殊要求，且编码效率较不唯一，但对信源没有特殊要求，且编码效率较高，设备要求简单，综合性能优于另外两种。高，设备要求简单，综合性能优于另外两种。相同点：相同点：三种编码都考虑了信源的统计特性，使经常出三种编码都考虑了信源的统计特性，使经常出现的信源符号对应较短的码字，使平均码长缩短，实现现的信源符号对应较短的码字，使平均码长缩短，实现了信源压缩。了信源压缩。不同点：不同点：shnno

30、n：有唯一的编码，但编码效率不是很高；：有唯一的编码，但编码效率不是很高；Fano:编码方法不唯一，适合与分组概率相等或相近的信源；编码方法不唯一，适合与分组概率相等或相近的信源；23:53394.5.3 MH编码（游程编码）编码（游程编码） 游程游程是指符号序列中各个符号连续重复出现而形成符号串是指符号序列中各个符号连续重复出现而形成符号串的长度，又称游程长度或游长。的长度，又称游程长度或游长。 游程编码游程编码（就是将这种符号序列映射成游程长度和对应符（就是将这种符号序列映射成游程长度和对应符号序列的位置的标志序列。如果知道了游程长度和对应符号序列的位置的标志序列。如果知道了游程长度和对应

31、符号序列的位置的标志序列，就可以完全恢复出原来的符号号序列的位置的标志序列，就可以完全恢复出原来的符号序列。序列。游程长度编码游程长度编码 举例说明：举例说明：aaaa bbb cc d eeeee fffffff (共共22228=176 bit)8=176 bit) 4a3b2c1d5e7f (共共128=96 bit)43215723:534123:5342 游程编码特别适用于对相关信源的编码。对二元相关信源，游程编码特别适用于对相关信源的编码。对二元相关信源，其输出序列往往会出现多个连续的其输出序列往往会出现多个连续的“0”或连续的或连续的“1”。在。在信源输出的二元序列中，连续出现的信源输出的二元序列中，连续出现的“0”符号称为