-信息论与编码.ppt

5.2.3 最佳变长编码• 最佳码： – 对于某一信源和某一码符号集来说,若有一唯 一可译码,其平均码长小于所有其他唯一可译码 的平均长度 • 最佳变长编码 :凡是能载荷一定的信息量，且码字的平均长度最 短，可分离的变长码的码字集合称为最佳变长码 • 紧致码 – 香农（Shannon） – 费诺（Fano） – 哈夫曼（Huffman ）1香农编码• 香农第一定理指出了平均码长与信源之间的关系, 同时也指出了可以通过编码使平均码长达到极限 值,这是一个很重要的极限定理 • 香农第一定理指出,选择每个码字的长度Ki满足下 式： 或: －log2 p(xi)≤ Ki <1－log2 p(xi) • 就可以得到这种码 • 这种编码方法称为香农编码香农编码 取整2• 二进制香农码的编码步骤如下： ⑴将信源符号按概率从大到小的顺序排列, p(a1)≥ p(a2)≥…≥ p(an) ⑵确定满足下列不等式的整数Ki , －log2 p(ai)≤ Ki <1－log2 p(ai) ⑶令P(a1)=0,用Pi表示第i个码字的累加概率，香农编码⑷将Pi用二进制表示,并取小数点后Ki位作为 符号ai的编码。

3例有一单符号离散无记忆信源• 对该信源编二进制香农码其编码过程如表所示以i = 3为例: 码字长度： K3 = [－log0.2] = 3 累加概率 Pi=0.70 → 0.10110… 00011011110011101 这些码字没有占满所有 树叶,所以是非最佳码 信源 符号xi 符号 概率 p(xi)累加 概率 Pi-log p(xi) 码 长码字 x10.4 01.32 200 x20.30.41.73 201 x30.20.72.32 3101 x40.050.94.3 511100 x50.050.954.35111014• 香农码的平均码长• 熵• 编码效率为提高编码效率,首先应达到满树;如把 x4x5换成前面的节点,可减小平均码长不应先规定码长,而是由码树来规定码 字,可得更好的结果 x1x2x5x3 x45费诺编码• 费诺编码属于概率匹配编码 • 编码步骤如下： • 将概率按从大到小的顺序排列,令 p(x1)≥ p(x2)≥…≥ p(xn) • 按编码进制数将概率分组,使每组概率尽可能接近 或相等如编二进制码就分成两组,编m进制码就 分成m组 • 给每一组分配一位码元。

• 将每一分组再按同样原则划分,重复步骤2和3,直 至概率不再可分为止6信源 符号 xi 符号 概率 p(xi)第1次 分组 第2次 分组第3次 分组码 字 码 长x10.4 00002x40.05100103x50.0510113x20.310102 x30.21112• 例设有一单符号离散信源• 对该信源编二进制费诺码信源 符号 xi 符号 概率 p(xi)第1 分 组 第2 分 组第3 分 组第4 分 组码 字 码 长x10.4 001 x20.3 10102 x30.210110 3 x40.0510111 04x50.051111 14平均码长：K= 2.1 编码效率: η=93% 平均码长：K= 2.0 编码效率: η=97.5% 7• 平均码长• 编码效率• 费诺码比较适合于每次分组概率都很接近的信源 • 特别是对每次分组概率都相等的信源进行编码时, 可达到理想的编码效率8例有一单符号离散无记忆信源• 对该信源编二进制费诺码,编码过程如表:9• 信源熵为 H(X)=2.75(比特/符号) • 平均码长为• 编码效率为η=1 • 之所以如此,因为 每次所分两组的 概率恰好相等。

10哈夫曼编码• 哈夫曼编码也是用码树来分配各符号的码字• 费诺码是从树根开始,把各节点分给某子集,若子 集已是单点集,它就是一片树叶而作为码字• 哈夫曼编码是先给每一符号一片树叶,逐步合并 成节点直到树根• 哈夫曼(Huffman)编码是一种效率比较高的变 长无失真信源编码方法11• 哈夫曼编码的步骤如下： ⑴ 将信源消息符号按其出现的概率大小依次排列p(x1)≥p(x2)≥…≥ p(xn) ⑵取两个概率最小的字母分别配以0和1两码元,并 将这两个概率相加作为一个新字母的概率,与未 分配的二进符号的字母重新排队 ⑶ 对重排后的两个概率最小符号重复步骤⑵的过 程 ⑷不断继续上述过程,直到最后两个符号配以0和1 为止 ⑸ 从最后一级开始,向前返回得到各个信源符号 所对应的码元序列,即相应的码字 12例5-7 设单符号离散无记忆信源如下,要求对信 源编二进制哈夫曼码编码过程如下表信源符 号xi 符号概 率p(xi)编码过 程x10.20 x20.19 x30.18 x40.17 x50.15 x60.10 x70.01010.200.190.180.170.150.11010.260.200.190.180.17010.350.260.200.19010.390.350.26010.610.3901码字10 11 000 001 010 0110 0111在图中读取码字的时候,要 从后向前读,此时编出来的 码字是可分离的异前置码。

13• 熵• 平均码长为• 编码效率14• 哈夫曼的编法并不唯一 • 每次对缩减信源两个概率最小的符号分配“0”和 “1”码元是任意的,所以可得到不同的码字只要在 各次缩减信源中保持码元分配的一致性,即能得到 可分离码字 • 不同的码元分配,得到的具体码字不同,但码长Ki不 变,平均码长也不变,所以没有本质区别； • 缩减信源时,若合并后的新符号概率与其他符号概 率相等,从编码方法上来说,这几个符号的次序可任 意排列,编出的码都是正确的,但得到的码字不相同 • 不同的编法得到的码字长度Ki也不尽相同哈夫曼编码15• 例5-8 单符号离散无记忆信源信源 符号 xi 符号 概率 p(xi)编码过 程x10.4 x20.2x30.2 x40.1 x50.1010.40.20.20.2010.40.40.2010.60.401码字1 01 000 0010 0011码字00 10 11 010 0111617• 单符号信源编二进制哈夫曼码,编码效率主要 决定于信源熵和平均码长之比 • 对相同的信源编码,其熵是一样的,采用不同的 编法,得到的平均码长可能不同 • 平均码长越短,编码效率就越高。

• 编法一的平均码长为• 编法二的平均码长为• 两种编法的平均码长相同,所以编码效率相同18• 讨论：哪种方法更好？ • 定义码字长度的方差σ2：• 第二种编码方法的码长方差要小许多 • 第二种编码方法的码长变化较小,比较接近于平 均码长哈夫曼编码19哈夫曼编码• 第一种方法编出的5个码字有4种不同的码长； • 第二种方法编出的码长只有两种不同的码长； • 第二种编码方法更简单、更容易实现,所以更 好 • • 结论：结论： • 在哈夫曼编码过程中,对缩减信源符号按概率由大 到小的顺序重新排列时,应使合并后的新符号尽可 能排在靠前的位置,这样可使合并后的新符号重复 编码次数减少,使短码得到充分利用20哈夫曼码是用概率匹配方法进行信源编码 • 哈夫曼码的编码方法保证了概率大的符 号对应于短码，概率小的符号对应于长码 ，充分利用了短码； • 缩减信源的最后二个码字总是最后一位 不同，从而保证了哈夫曼码是即时码21r进制哈夫曼编码• 在编r进制哈夫曼码时为了使平均码长最短,必须 使最后一步缩减信源有r个信源符号 • 对于r进制编码,若所有码字构成全树,可分离的 码字数必为: m= r＋k(r－l) • 非全树时,有s个码字不用： s=m-n • 第一次对最小概率符号分配码元时只取(r－s)个 ,分别配以0,1, …,r-s-1,把这些符号的概率相加 作为一个新符号的概率,与其它符号一起重新排 列 • 以后每次取r个符号,分别配以0,1,…,r-1；如此 下去,直至所有概率相加得1为止,即得到各符号 的r进制码字。

22• 例:对如下单符号离散无记忆信源编三进制哈 夫曼码这里：r =3，n =8 • 令k=3，r+k(r－1)=9，则 s = 9－n = 9－8 =1 • 所以第一次取r－s=2个符号进行编码233进制哈夫曼编码信源符 号xi 符号概率 p(xi)编码过 程x10.40x20.18x30.10x40.10 x50.07 x60.06 x70.05 x80.04010120.400.180.100.100.090.070.060.400.220.180.100.100120.400.380.22012码字01011122122200201 2425结论结论• 香农码、费诺码、哈夫曼码都考虑了信源的统计特 性,使经常出现的信源符号对应较短的码字,使信源 的平均码长缩短,从而实现了对信源的压缩； • 香农码有系统的、唯一的编码方法,但在很多情况 下编码效率不是很高； • 费诺码和哈夫曼码的编码方法都不唯一； • 费诺码比较适合于对分组概率相等或接近的信源编 码,费诺码也可以编r进制码,但r越大,信源的符号数 越多,可能的编码方案就越多,编码过程就越复杂,有 时短码未必能得到充分利用； • • 哈夫曼码哈夫曼码对信源的统计特性没有特殊要求,编码效 率比较高,对编码设备的要求也比较简单,因此综合 性能优于香农码和费诺码。