第4章信源压缩编码基础

第4章：信源编码基础

信源编码的作用：

使信源适合于信道的传输，用信道能传输的符号来代表信源发出的消息；在不失真或允许一定失真的条件下，用尽可能少的符号来传递信源消息，提高信息传输率。

以提高通信有效性为目的。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均码长。

信源编码概述

信源编码理论是信息论的一个重要分支，其理论基础是信源编码的两个定理：无失真信源编码定理限失真信源编码定理

本章主要介绍无失真信源编码，它实质上是一种统计匹配编码，根据信源的不同概率分布而选用与之相匹配的码。信源编码概述

信源的统计剩余度主要决定于以下两个因素：1）无记忆信源中，符号概率分布的非均匀性；2）有记忆信源中，符号间的相关性及符号概率分布的非均匀性。信源编码概述怎样压缩信源的冗余度？1)去除码符号间的相关性。2)使码符号等概分布。信源编码器模型信宿信道信源编码器译码器YXSS’

信源编码：将信源符号序列按一定的数学规律映射成码符号序列的过程。

图1信源编码器模型4.1无失真可变长信源编码定理

将信源符号集中的符号

（或者长为N的信源符号序列）映射成由码符号

组成的长度为

的一一对应的码符号序列

。编码器码字信源编码器模型信源符号sip(si)码1码2s1p(s1)=1/2000s2p(s2)=1/40101s3p(s3)=1/810001s4p(s4)=1/811111例:4.1信源编码器模型编码器输出的码符号序列称为码字；长度

称为码字长度，简称码长；全体码字的集合C称为码。若码符号集合为X={0,1}，则所得的码字都是二元序列，称为二元码。关于编码的一些术语将信源符号集中的每个信源符号固定的映射成某一个码字

，这样的码称为分组码。若一个码中所有码字的码长都相等，则称为定长码；否则为变长码。1.奇异性若一个码中所有码字互不相同，则称为非奇异码；否则为奇异码。信源符号si码1码2s1s2s3s401100110100001一、信源编码的相关概念2.唯一可译性

若任意一串有限长的码符号序列只能被唯一地译为对应的信源符号序列，则称此码为唯一可译码。信源符号si码1码2码3s1s2s3s401100110100001010110111一、信源编码的相关概念

唯一可译码应当满足的条件码字与信源符号一一对应2)不同的信源符号序列对应不同的码字序列1)2.唯一可译性一、信源编码的相关概念2.唯一可译性例：1)奇异码11译码奇异码一定不是唯一可译码一、信源编码的相关概念2.唯一可译性2)非奇异码0100001001000010译码译码一、信源编码的相关概念2.唯一可译性3)等长码非奇异码00011011唯一可译码译码一、信源编码的相关概念

唯一可译定长码存在的条件对于定长码，非奇异码一定是唯一可译码。所谓非奇异码，即信源符号集中的每一个信源符号与码中的某一个码字一一对应。设信源符号集中共有个符号，，码符号集中共有种码元，，定长码码长为,则要满足非奇异性必然有该条件是必要条件，而不是充分条件。二、定长码及定长信源编码定理唯一可译定长码存在的条件例：英文字母表中，每一字母用定长编码转换成二进制表示，码字的最短长度是多少？解：信源符号数码符号数二、定长码及定长信源编码定理若用r元码对信源SN进行编码，设S中每个符号所需的平均码长为则定义：为该码的编码效率18要做到无失真的信源编码，平均每个信源符号所需最少的r元码元数为信源的熵。即它是无失真信源压缩的极限值。若编码的平均码长小于信源的熵值，则惟一可译码不存在，在译码或反变换时必然要带来失真或差错。通过对扩展信源进行变长编码，当N

时，平均码长

19无失真信源编码的实质：对离散信源进行适当的变换，使变换后形成的新的码符号信源(即信道的输入信源)尽可能为等概率分布，以使新信源的每个码符号平均所含的信息量达到最大，使信道的信息传输率达到信道容量，实现信源与信道理想的统计匹配。这实际上就是香农第一定理的物理意义。20为了衡量各种编码是否达到极限情况，定义变长码的编码效率为：

常通过编码效率来衡量各种编码的优劣.为了衡量各种编码与最佳码的差距，定义码的剩余度为：信息传输率定义为：注意:虽然与在数值上相同，但它们的单位不同，编码效率没有单位，而信息传输率的单位是比特/码符号。11:1221为了使得平均编码长度为最小，必须将概率大的信息符号编以短的码字，概率小的符号编以长的码字。能获得最佳码（或次最佳码）的编码方法有很多。香农(shannon)编码、费诺(Fano)编码、霍夫曼(Huffman)编码等就是代表。221香农码香农第一定理指出，可选择每个码字的长度满足关系式：或：

x

表示不小于x的整数。按不等式选择的码长所构成的码称香农码。香农码满足克拉夫特不等式，所以一定存在对应码字的长度的惟一可译码。11:1223一般情况下，按照香农编码方法编出来的码，其平均码长不是最短的，也即不是紧致码(最佳码)。只有当信源符号的概率分布使不等式左边的等号成立时，编码效率才达到最高。香农码的编码步骤如下：

1）将个信源符号按概率递减的方式进行排列：

2）按香农不等式计算出每个信源符号的码长；

3）为了编成惟一可译码，计算第i个信源符号的累加概率

4）将累加概率用二进制数表示。

5）取对应二进制数的小数点后位构成该信源符号的二进制码字。11:1225概率累加概率码长信源符号对应的二进制数码字0.2000.0002.3430000.190.20.0011…2.4130010.180.390.0110…2.4830110.170.570.1001…2.5631000.150.740.1011…2.7431010.100.890.1110…3.34411100.010.990.1111110…6.6671111110例:设信源共有七个信源符号，其概率分布如表所示，试对该信源进行香农编码。解:码的性能分析：通过计算可得此信源的熵:

(比特／符号)

而码的平均长度:

(二元码符号／符号)

编码效率：11:12272费诺码费诺编码属于概率匹配编码，但它一般也不是最佳的编码方法，只有当信源的概率分布呈现

分布形式的条件下，才能达到最佳码的性能。11:1228

费诺码的编码步骤如下：

1）信源符号以概率递减的次序排列起来；

2）将排列好的信源符号按概率值划分成两大组，使每组的概率之和接近于相等，并对每组各赋予一个二元码符号“0”和“1”；

3）将每一大组的信源符号再分成两组，使划分后的两个组的概率之和接近于相等，再分别赋予一个二元码符号；

4）依次下去，直至每个小组只剩一个信源符号为止；

5）信源符号所对应的码字即为费诺码。11:1229例:将下列消息按二元费诺码方法进行编码。11:1230此信源的熵(比特／符号)，而码的平均长度

(二元码符号／符号)

显然，该码是紧致码，编码效率：该码之所以能达到最佳，是因为信源符号的概率分布正好满足式，否则，在一般情况下是无法达到编码效率等于“1”的。码的性能分析：11:1231费诺码具有如下的性质：①费诺码的编码方法实际上是一种构造码树的方法，所以费诺码是即时码。②费诺码考虑了信源的统计特性，使概率大的信源符号能对应码长较短的码字，从而有效地提高了编码效率。③费诺码不一定是最佳码。因为费诺码编码方法不一定能使短码得到充分利用:当信源符号较多时，若有一些符号概率分布很接近时，分两大组的组合方法就会很多。可能某种分大组的结果，会使后面小组的“概率和”相差较远，从而使平均码长增加。11:12323霍夫曼码1952年，霍夫曼（Huffman）提出了一种构造最佳码的方法，这是一种最佳的逐个符号的编码方法，一般就称作霍夫曼码。设信源，其对应的概率分布为，则对二元霍夫曼码而言，其编码步骤如下：11:12331）将q个信源符号按概率递减的方式排列起来；2）用“0”、“1”码符号分别表示概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个新的符号，从而得到只包含q-1个符号的新信源，称之为S信源的S1缩减信源；3）将缩减信源中的符号仍按概率大小以递减次序排列，再将其最后两个概率最小的符号合并成一个符号，并分别用“0”、“1”码符号表示，这样又形成了由q-2个符号构成的缩减信源S2；4）依次继续下去，直到缩减信源只剩下两个符号为止，将这最后两个符号分别用“0”、“1”码符号表示；5）从最后一级缩减信源开始，向前返回，沿信源缩减方向的反方向取出所编的码元，得出各信源符号所对应的码符号序列，即为对应信源符号的码字。11:1234例:对离散无记忆信源

进行霍夫曼编码。解:编码过程如表所示：

1)将信源符号按概率大小由大至小排序。

2)从概率最小的两个信源符号和开始编码，并按一定的规则赋予码符号，如下面的信源符号（小概率）为“1”，上面的信源符号（大概率）为“0”。若两支路概率相等，仍为下面的信源符号为“1”上面的信源符号为“0”。

3)将已编码两个信源符号概率合并，重新排队，编码。

4)重复步骤3）直至合并概率等于“1.0”为止。

5)从概率等于“1.0”端沿合并路线逆行至对应消息编码.11:123511:1236码的性能分析：信源的熵为：H(s)=2.12

(比特／符号)

从，可得平均码长为：编码效率为：11:1237按霍夫曼码的编码方法，可知这种码有如下特征：①它是一种分组码：各个信源符号都被映射成一组固定次序的码符号；②它是一种惟一可解的码：任何码符号序列只能以一种方式译码；③它是一种即时码：由于代表信源符号的节点都是终端节点，因此其编码不可能是其它终端节点对应的编码的前缀，霍夫曼编码所得的码字一定是即时码。所以一串码符号中的每个码字都可不考虑其后的符号直接解码出来。霍夫曼码的译码：对接收到的霍夫曼码序列可通过从左到右检查各个符号进行译码。11:1238说明：①霍夫曼码是一种即时码，可用码树形式来表示。②每次对缩减信源最后两个概率最小的符号，用“0”和“1”码是可以任意的，所以可得到不同的码，但码长不变，平均码长也不变。③当缩减信源中缩减合并后得到的新符号的概率与其他信源符号概率相同时，从编码方法上来说，它们概率的排序是没有限制的，因此也可得到不同的码。即对给定信源，用霍夫曼编码方法得到的码并非是惟一，但平均码长不变。三种编码的比较Huffman:不唯一，但对信源没有特殊要求，且编码效率较高，设备要求简单，综合性能优于另外两种。相同点：三种编码都考虑了信源的统计特性，使经常出现的信源符号对应较短的码字，使平均码长缩短，实现了信源压缩。不同点：shnnon：有唯一的编码，但编码效率不是很高；Fano:编码方法不唯一，适合与分组概率相等或相近的信源；11:12394.5.3MH编码（游程编码）游程是指符号序列中各个符号连续重复出现而形成符号串的长度，又称游程长度或游长。游程编码（就是将这种符号序列映射成游程长度和对应符号序列的位置的标志序列。如果知道了游程长度和对应符号序列的位置的标志序列，就可以完全恢复出原来的符号序列。游程长度编码举例说明：

aaaa

bbb

cc

d

eeeee

fffffff(共22×8=176bit)

4a3b2c1d5e7f(共12×8=96bit)43215711:124111:1242游程编码特别适用于对相关信源的编码。对二元相关信源，其输出序列往往会出现多个连续的“0”或连续的“1”。在信源输出的二元序列中，连续出现的“0”符号称为“0游程”，连续出现的“1”符号称为“1游程”，对应连续同一符号的个数分别称为“0”游程长度和“1游程”长度，