信息论编码教材

信源编码

第5章25.1

编码的定义5.2

无失真信源编码5.3限失真信源编码5.4常用信源编码方法简介内容35.2无失真信源编码45.2.3最佳变长编码最佳码(紧致码)：对于某一信源和某一码符号集来说,若有一唯一可译码,其平均码长小于所有其他唯一可译码的平均长度。紧致码香农（Shannon）费诺（Fano）哈夫曼（Huffman）

——均为匹配编码（统计编码），都是通过使用较短的码字来给出现概率较高的信源符号编码，而出现概率较小的信源符号用较长的码字来编码，从而使得平均码长最短，达到最佳编码的目的。5香农编码无失真信源编码定理(香农第一定理)给出了平均码长和信源之间的关系，并指出可通过编码使平均码长达到极限值。根据定理，先决定码长，再用合适的方法构造码字，这就是香农编码。香农码选择每个码字的长度Ki满足下式：－log2

p(xi)≤Ki

<1－log2

p(xi)取整或:

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

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

－log2

p(ai)≤Ki

<1－log2

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

(0.7)10=(0.10110…)21011110011101信源符号xi

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

511100x50.050.954.351110100018香农码的平均码长熵编码效率

为提高编码效率,把x4,x5换成前面的节点,可减小平均码长。不应先规定码长,而是由码树来规定码字,可得更好的结果。x1x2x5x3x49费诺编码费诺编码属于概率匹配编码

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

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

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

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

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

符号概率p(xi)编码过程x10.4x20.2x30.2x40.1x50.1010.40.20.20.2010.40.40.2010.60.401码110100000100011码200101101001120单符号信源编二进制哈夫曼码,编码效率主要决定于信源熵和平均码长之比。对相同的信源编码,其熵是一样的,采用不同的编法,得到的平均码长可能不同。平均码长越短,编码效率就越高。编法一的平均码长为编法二的平均码长为两种编法的平均码长相同,所以编码效率相同。21讨论：哪种方法更好？定义码字长度的方差σ2：第二种编码方法的码长方差要小许多。第二种编码方法的码长变化较小,比较接近于平均码长。哈夫曼编码22哈夫曼编码第一种方法编出的5个码字有4种不同的码长；第二种方法编出的码长只有两种不同的码长；第二种编码方法更简单、更容易实现,所以更好。结论：在哈夫曼编码过程中,对缩减信源符号按概率由大到小的顺序重新排列时,应使合并后的新符号尽可能排在靠前的位置,这样可使合并后的新符号重复编码次数减少,使短码得到充分利用。23哈夫曼编码的特点哈夫曼码是用概率匹配方法进行信源编码。哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码；缩减信源的最后二个码字总是最后一位不同，从而保证了哈夫曼码是即时码24比较香农码、费诺码、哈夫曼码都考虑了信源的统计特性,使经常出现的信源符号对应较短的码字,使信源的平均码长缩短,从而实现了对信源的压缩；香农码有系统的、惟一的编码方法,但在很多情况下编码效率不是很高；费诺码和哈夫曼码的编码方法都不惟一