《信息论与编码(第二版)》第5章-2

信源编码

第5章15.1

编码的定义5.2

无失真信源编码5.3限失真信源编码5.4常用信源编码方法简介内容2编码的目的香农编码定理虽然指出了理想编码器的存在性,但是并没有给出实用码的结构及构造方法；编码理论正是为了解决这一问题而发展起来的科学理论；编码的目的是为了优化通信系统,就是使这些指标达到最佳；通信系统的性能指标主要是有效性、可靠性、安全性和经济性,除了经济性外,这些指标正是信息论研究的对象。按不同的编码目的,编码分为三类：信源编码信道编码安全编码/密码。3信源编码：以提高通信有效性为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送,使单位时间内传送的平均信息量增加,从而提高通信的有效性。信道编码：是以提高信息传输的可靠性为目的的编码。通常通过增加信源的冗余度来实现。采用的一般方法是增大码率/带宽。与信源编码正好相反。密码：是以提高通信系统的安全性为目的的编码。通常通过加密和解密来实现。从信息论的观点出发“加密”可视为增熵的过程,“解密”可视为减熵的过程。4信源编码理论是信息论的一个重要分支,其理论基础是信源编码的两个定理。无失真信源编码定理：是离散信源/数字信号编码的基础；限失真信源编码定理：是连续信源/模拟信号编码的基础。信源编码的分类：离散信源编码：独立信源编码,可做到无失真编码；连续信源编码：独立信源编码,只能做到限失真信源编码；相关信源编码：非独立信源编码。55.2无失真信源编码6信源符号信源符号出现概率C1C2A0.600

0B0.2501

10C0.110

110D0.0511

1110信源{A,B,C,D}信源编码器信道Error:10-4解码信宿无失真信源编码7C2

的效率比C1高码字平均长度C1

和C2平均长度C2的区分

：0

表示码字的结束011100110100…ADACBA…码字平均长度8编码效率信息率与编码效率信息率95.2.3最佳变长编码最佳码：对于某一信源和某一码符号集来说,若有一唯一可译码,其平均码长小于所有其他唯一可译码的平均长度。紧致码香农（Shannon）费诺（Fano）哈夫曼（Huffma）10香农编码香农第一定理指出了平均码长与信源之间的关系,同时也指出了可以通过编码使平均码长达到极限值,这是一个很重要的极限定理。香农第一定理指出,选择每个码字的长度Ki满足下式：或:－log2

p(xi)≤Ki

<1－log2

p(xi)就可以得到这种码。这种编码方法称为香农编码

取整11二进制香农码的编码步骤如下：⑴将信源符号按概率从大到小的顺序排列,

p(a1)≥p(a2)≥…≥p(an)⑵确定满足下列不等式的整数Ki

,－log2

p(ai)≤Ki

<1－log2

p(ai)⑶令p(a1)=0,用Pi表示第i个码字的累加概率，香农编码⑷将Pi用二进制表示,并取小数点后Ki位作为符号ai的编码。12例有一单符号离散无记忆信源对该信源编二进制香农码。其编码过程如表所示以i=3为例:码字长度：K4=[－log0.2]=3累加概率

Pi=0.70→0.10110…00011011110011101这些码字没有占满所有树叶,所以是非最佳码信源符号xi

符号概率p(xi)累加概率Pi-logp(xi)码长码字x10.401.32200x20.30.41.73201x30.20.72.323101x40.050.94.3

511100x50.050.954.351110113香农码的平均码长熵编码效率为提高编码效率,首先应达到满树;如把x4x5换成前面的节点,可减小平均码长。不应先规定码长,而是由码树来规定码字,可得更好的结果。x1x2x5x3x414费诺编码费诺编码属于概率匹配编码

。编码步骤如下：将概率按从大到小的顺序排列,令p(x1)≥p(x2)≥…≥p(xn)按编码进制数将概率分组,使每组概率尽可能接近或相等。如编二进制码就分成两组,编m进制码就分成m组。给每一组分配一位码元。将每一分组再按同样原则划分,重复步骤2和3,直至概率不再可分为止。15信源符号xi

符号概率p(xi)第1次分组第2次分组第3次分组码字码长x10.400002x40.05100103x50.0510113x20.310102x30.21112例设有一单符号离散信源对该信源编二进制费诺码。信源符号xi

符号概率p(xi)第1分组第2分组第3分组第4分组码字码长x10.4001x20.310102x30.2101103x40.051011104x50.05111114平均码长：K=2.1编码效率:η=93%平均码长：K=2.0编码效率:η=97.5%16平均码长编码效率费诺码比较适合于每次分组概率都很接近的信源特别是对每次分组概率都相等的信源进行编码时,可达到理想的编码效率。17例有一单符号离散无记忆信源对该信源编二进制费诺码,编码过程如表:18信源熵为H(X)=2.75(比特/符号)平均码长为编码效率为

η=1之所以如此,因为每次所分两组的概率恰好相等。19哈夫曼编码哈夫曼编码也是用码树来分配各符号的码字。费诺码是从树根开始,把各节点分给某子集,若子集已是单点集,它就是一片树叶而作为码字。哈夫曼编码是先给每一符号一片树叶,逐步合并成节点直到树根。哈夫曼(Huffman)编码是一种效率比较高的变长无失真信源编码方法。20哈夫曼编码的步骤如下：⑴将信源消息符号按其出现的概率大小依次排列

p(x1)≥p(x2)≥…≥p(xn)⑵取两个概率最小的字母分别配以0和1两码元,并将这两个概率相加作为一个新字母的概率,与未分配的二进符号的字母重新排队。⑶对重排后的两个概率最小符号重复步骤⑵的过程。⑷不断继续上述过程,直到最后两个符号配以0和1为止。⑸从最后一级开始,向前返回得到各个信源符号所对应的码元序列,即相应的码字。21例5-7

设单符号离散无记忆信源如下,要求对信源编二进制哈夫曼码。编码过程如下表信源符号xi

符号概率p(xi)编码过程x10.20x20.19x30.18x40.17x50.15x60.10x70.01010.200.190.180.170.150.11010.260.200.190.180.17010.350.260.200.19010.390.350.26010.610.3901码字101100000101001100111在图中读取码字的时候,要从后向前读,此时编出来的码字是可分离的异前置码。22熵平均码长为编码效率23哈夫曼的编法并不惟一。每次对缩减信源两个概率最小的符号分配“0”和“1”码元是任意的,所以可得到不同的码字。只要在各次缩减信源中保持码元分配的一致性,即能得到可分离码字。不同的码元分配,得到的具体码字不同,但码长Ki不变,平均码长也不变,所以没有本质区别；缩减信源时,若合并后的新符号概率与其他符号概率相等,从编码方法上来说,这几个符号的次序可任意排列,编出的码都是正确的,但得到的码字不相同。不同的编法得到的码字长度Ki也不尽相同。哈夫曼编码24例5-8

单符号离散无记忆信源信源符号xi

符号概率p(xi)编码过程x10.4x20.2x30.2x40.1x50.1010.40.20.20.2010.40.40.2010.60.401码字10100000100011码字00101101001125

26单符号信源编二进制哈夫曼码,编码效率主要决定于信源熵和平均码长之比。对相同的信源编码,其熵是一样的,采用不同的编法,得到的平均码长可能不同。平均码长越短,编码效率就越高。编法一的平均码长为编法二的平均码长为两种编法的平均码长相同,所以编码效率相同。27讨论：哪种方法更好？定义码字长度的方差σ2：第二种编码方法的码长方差要小许多。第二种编码方法的码长变化较小,比较接近于平均码长。哈夫曼编码28哈夫曼编码第一种方法编出的5个码字有4种不同的码长；第二种方法编出的码长只有两种不同的码长；第二种编码方法更简单、更容易实现,所以更好。结论：在哈夫曼编码过程中,对缩减信源符号按概率由大到小的顺序重新排列时,应使合并后的新符号尽可能排在靠前的位置,这样可使合并后的新符号重复编码次数减少,使短码得到充分利用。29m进制哈夫曼编码在编m进制哈夫曼码时为了使平均码长最短,必须使最后一步缩减信源有m个信源符号。对于m进制编码,若所有码字构成全树,可分离的码字数必为:

m＋k(m－l)非全树时,有s个码字不用：第一次对最小概率符号分配码元时只取(m－s)个,分别配以0,1,…,m-s-1,把这些符号的概率相加作为一个新符号的概率,与其它符号一起重新排列以后每次取m个符号,分别配以0,1,…,m-1；如此下去,直至所有概率相加得1为止,即得到各符号的m进制码字。30例:对如下单符号离散无记忆信源编三进制哈夫曼码这里：m=3，n=8令k=3，m+k(m－1)=9，则s=9－n=9－8=1所以第一次取m－s=2个符号进行编码。313进制哈夫曼编码信源符号xi

符号概率p(xi)编码过程x10.40x20.18x30.10x40.10x50.07x60.06x70.05x80.04010120.400.180.100.100.090.070.060.400.220.180.100.100120.400.380.22012码字010111221222002013233平均码长为信息率为编码效率为哈夫曼的编码效率相当高,对编码器的要求也简单得多。34

结论香农码、费诺码、哈夫曼码都考虑了信源的统计特性,使经常出现的信源符号对应较短的码字,使信源的平均码长缩短,从而实现了对信源的压缩；香农码有系统的、惟一的编码方法,但在很多情况下编码效率不是很高；费诺码和哈夫曼码的编码方法都不惟一；费诺码比较适合于对分组概率相等或接近的信源编码,费诺码也可以编m进制码,但m越大,信源的符号数越多,可能的编码方案就越多,编码过程就越复杂,有时短码未必能得到充分利