信息论与编码课件第5章-2

信源编码

第5章15.2无失真信源编码25.2.3最佳变长编码1、最佳码定义：对于某一信源和某一码符号集来说,若有可分离的变长码，且其平均码长最短。2、最佳码分类香农（Shannon）费诺（Fano）哈夫曼（Huffma）3

香农编码香农第一定理指出,选择每个码字的长度Ki满足下式：或:－log2

p(xi)≤Ki

<1－log2

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

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

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

p(ai)≤Ki

<1－log2

p(ai)⑶令P1=0,用Pi表示第i个码字的累加概率，⑷将Pi用二进制表示,并取小数点后Ki位作为符号ai的编码。香农编码5例1有一单符号离散无记忆信源对该信源编二进制香农码。其编码过程如表所示以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.35111016香农码的平均码长熵编码效率为提高编码效率,首先应达到满树;如把x4x5换成前面的节点,可减小平均码长。不应先规定码长,而是由码树来规定码字,可得更好的结果。x1x2x5x3x47费诺编码费诺编码属于概率匹配编码

。编码步骤如下：（1）将概率按从大到小的顺序排列,令p(x1)≥p(x2)≥…≥p(xn)（2）按编码进制数将概率分组,使每组概率尽可能接近或相等。如编二进制码就分成两组,编m进制码就分成m组。（3）给每一组分配一位码元。（4）将每一分组再按同样原则划分,重复步骤2和3,直至概率不再可分为止。8信源符号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%9平均码长编码效率费诺码比较适合于每次分组概率都很接近的信源特别是对每次分组概率都相等的信源进行编码时,可达到理想的编码效率。10例有一单符号离散无记忆信源对该信源编二进制费诺码,编码过程如表:11信源熵为H(X)=2.75(比特/符号)平均码长为编码效率为η=1之所以如此,因为每次所分两组的概率恰好相等。12哈夫曼编码哈夫曼编码也是用码树来分配各符号的码字。费诺码是从树根开始,把各节点分给某子集,若子集已是单点集,它就是一片树叶而作为码字。哈夫曼编码是先给每一符号一片树叶,逐步合并成节点直到树根。哈夫曼(Huffman)编码是一种效率比较高的变长无失真信源编码方法。13哈夫曼编码的步骤如下：⑴将信源消息符号按其出现的概率大小依次排列

p(x1)≥p(x2)≥…≥p(xn)⑵取两个概率最小的字母分别配以0和1两码元,并将这两个概率相加作为一个新字母的概率,与未分配的二进符号的字母重新排队。⑶对重排后的两个概率最小符号重复步骤⑵的过程。⑷不断继续上述过程,直到最后两个符号配以0和1为止。⑸从最后一级开始,向前返回得到各个信源符号所对应的码元序列,即相应的码字。14例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在图中读取码字的时候,要从后向前读,此时编出来的码字是可分离的异前置码。15熵平均码长为编码效率16哈夫曼的编法并不惟一。每次对缩减信源两个概率最小的符号分配“0”和“1”码元是任意的,所以可得到不同的码字。只要在各次缩减信源中保持码元分配的一致性,即能得到可分离码字。不同的码元分配,得到的具体码字不同,但码长Ki不变,平均码长也不变,所以没有本质区别；缩减信源时,若合并后的新符号概率与其他符号概率相等,从编码方法上来说,这几个符号的次序可任意排列,编出的码都是正确的,但得到的码字不相同。不同的编法得到的码字长度Ki也不尽相同。哈夫曼编码17例5-8单符号离散无记忆信源信源符号xi

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

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

m＋k(m－l)非全树时,有s个码字不用：第一次对最小概率符号分配码元时只取(m－s)个,分别配以0,1,…,m-s-1,把这些符号的概率相加作为一个新符号的概率,与其它符号一起重新排列以后每次取m个符号,分别配以0,1,…,m-1；如此下去,直至所有概率相加得1为止,即得到各符号的m进制码字。23例:对如下单符号离散无记忆信源编三进制哈夫曼码这里：m=3，n=8令k=3，m+k(m－1)=9，则s=9－n=9－8=1所以第一次取m－s=2个符号进行编码。243进制哈夫曼编码信源符号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码字010111221222002012526平均码长为信息率为编码效率为哈夫曼的编码效率相当高,对编码器的要求也简单得多。27

结论香农码、费诺码、哈夫曼码都考虑了信源的统计特性,使经常出现的信源符号对应较短的码字,使信源的平均码长缩短,从而实现了对信源的压缩；香农码有系统的、