信息论编码教材.ppt

信源编码,第5章,2,5.1 编码的定义 5.2 无失真信源编码 5.3 限失真信源编码 5.4 常用信源编码方法简介,内容,3,5.2 无失真信源编码,4,5.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…)2,,,,,,,,,,,101,11100,11101,,00,01,8,,,,,,,,,,,,香农码的平均码长,熵,编码效率,为提高编码效率, 把x4, x5换成前面的节点,可减小平均码长 不应先规定码长,而是由码树来规定码字,可得更好的结果x1,x2,x5,x3,x4,,9,费诺编码,费诺编码属于概率匹配编码 编码步骤如下： 将概率按从大到小的顺序排列,令 p(x1)≥ p(x2)≥…≥ p(xn) 按编码进制数将依次排列的概率分组,使每组概率和尽可能接近或相等如编二进制码就分成两组,编m进制码就分成m组 给每一组分配一位码元 将每一分组再按同样原则划分,重复步骤2和3,直至概率不再可分为止 信源符号所对应的码字就是费诺码10,例设有一单符号离散信源,对该信源编二进制费诺码平均码长： 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 设单符号离散无记忆信源如下,要求对信源编二进制哈夫曼码编码过程如下表,0 1,0.20 0.19 0.18 0.17 0.15 0.11,,,0 1,,,0.26 0.20 0.19 0.18 0.17,0 1,,,0.35 0.26 0.20 0.19,0 1,,,0.39 0.35 0.26,0 1,,,0.61 0.39,0 1,,,,,,,,,,在图中读取码字的时候,要从后向前读。

17,熵,平均码长为,编码效率,18,哈夫曼的编法并不惟一 每次对缩减信源两个概率最小的符号分配“0”和“1”码元是任意的,所以可得到不同的码字 不同的码元分配,得到的具体码字不同,但码长Ki不变,平均码长也不变,所以没有本质区别； 缩减信源时,若合并后的新符号概率与其他符号概率相等,从编码方法上来说,这几个符号的次序可任意排列,编出的码都是正确的,但得到的码字不相同此时，不同的编法得到的码字长度Ki也不尽相同哈夫曼编码,19,例5-8 单符号离散无记忆信源,0 1,,,0.4 0.2 0.2 0.2,0 1,,0.4 0.4 0.2,0 1,,,,0.6 0.4,0 1,,,,20,单符号信源编二进制哈夫曼码,编码效率主要决定于信源熵和平均码长之比 对相同的信源编码,其熵是一样的,采用不同的编法,得到的平均码长可能不同 平均码长越短,编码效率就越高编法一的平均码长为,编法二的平均码长为,两种编法的平均码长相同,所以编码效率相同21,讨论：哪种方法更好？ 定义码字长度的方差σ2：,第二种编码方法的码长方差要小许多 第二种编码方法的码长变化较小,比较接近于平均码长哈夫曼编码,22,哈夫曼编码,第一种方法编出的5个码字有4种不同的码长； 第二种方法编出的码长只有两种不同的码长； 第二种编码方法更简单、更容易实现,所以更好。

结论： 在哈夫曼编码过程中,对缩减信源符号按概率由大到小的顺序重新排列时,应使合并后的新符号尽可能排在靠前的位置,这样可使合并后的新符号重复编码次数减少,使短码得到充分利用23,哈夫曼编码的特点,哈夫曼码是用概率匹配方法进行信源编码 哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码； 缩减信源的最后二个码字总是最后一位不同，从而保证了哈夫曼码是即时码,24,比较 香农码、费诺码、哈夫曼码都考虑了信源的统计特性,使经常出现的信源符号对应较短的码字,使信源的平均码长缩短,从而实现了对信源的压缩； 香农码有系统的、惟一的编码方法,但在很多情况下编码效率不是很高； 费诺码和哈夫曼码的编码方法都不惟一； 费诺码比较适合于对分组概率相等或接近的信源编码,费诺码也可以编m进制码,但m越大,信源的符号数越多,可能的编码方案就越多,编码过程就越复杂,有时短码未必能得到充分利用； 哈夫曼码对信源的统计特性没有特殊要求,编码效率比较高,对编码设备的要求也比较简单,因此综合性能优于香农码和费诺码25,练习题,5-11 (1)-(4),。