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

1、25.1 编码的定义5.2 无失真信源编码5.3 限失真信源编码5.4 常用信源编码方法简介3 香农编码定理虽然指出了理想编码器的存在性,但是并没有给出实用码的结构及构造方法； 编码理论正是为了解决这一问题而发展起来的科学理论； 编码的目的是为了优化通信系统,就是使这些指标达到最佳； 通信系统的性能指标主要是有效性、可靠性、安全性和经济性,除了经济性外,这些指标正是信息论研究的对象。 按不同的编码目的,编码分为三类： 信源编码 信道编码 安全编码/密码。4 信源编码： 以提高通信为目的的编码。 通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的

2、信息用较少的码率传送,使单位时间内传送的平均信息量增加,从而提高通信的有效性。 信道编码： 是以提高信息传输的为目的的编码。 通常通过增加信源的冗余度来实现。采用的一般方法是增大码率/带宽。与信源编码正好相反。 密码： 是以提高通信系统的为目的的编码。 通常通过加密和解密来实现。从信息论的观点出发 “加密”可视为增熵的过程,“解密”可视为减熵的过程。5 信源编码理论是信息论的一个重要分支,其理论基础是信源编码的两个定理。无失真信源编码定理：是离散信源/数字信号编码的基础；限失真信源编码定理：是连续信源/模拟信号编码的基础。 信源编码的分类：离散信源编码：独立信源编码,可做到无失真编码；连续信源

3、编码：独立信源编码,只能做到限失真信源编码；相关信源编码：非独立信源编码。67信源符号信源符号出现概率C1C2A0.60 0 0B0.250 1 1 0C0.11 0 1 1 0D0.051 1 1 1 1 0信源A, B, C, D信源编码器信道Error: 10-4解码信宿8C2 的效率比 C1高 C1 和C2平均长度 C2的区分 ：0 表示码字的结束011100110100ADACBA205.021.0225.026.021K6 . 105. 041 . 0325. 026 . 012KniiiKapK1)( 码字平均长度9 编码效率RXH)( 信息率mLKRLlog10 最佳码： 对于

4、某一信源和某一码符号集来说,若有一唯一可译码,其平均码长小于所有其他唯一可译码的平均长度。 紧致码 香农（Shannon） 费诺（Fano） 哈夫曼（Huffma ）11 香农第一定理指出了平均码长与信源之间的关系,同时也指出了可以通过编码使平均码长达到极限值,这是一个很重要的极限定理。 香农第一定理指出,选择每个码字的长度Ki满足下式： )(1logiixpK或: log2 p(xi) Ki 1log2 p(xi) 就可以得到这种码。 这种编码方法称为 取整12 二进制香农码的编码步骤如下：将信源符号按概率从大到小的顺序排列, p(a1) p(a2) p(an)确定满足下列不等式的整数Ki

5、, log2 p(ai) Ki 1log2 p(ai)令p(a1)=0,用Pi表示第i个码字的累加概率，11)(ikkiapP将Pi用二进制表示,并取小数点后Ki位作为符号ai的编码。例有一单符号离散无记忆信源 对该信源编二进制香农码。其编码过程如表所示以i = 3为例:码字长度：K4 = 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 201x30.20.72.32 31

6、01x40.050.94.3 511100 x50.050.954.351110105. 005. 02 . 03 . 04 . 0)(54321xxxxxxpX 香农码的平均码长5 . 22505. 032 . 023 . 024 . 0)(51iiiKxpK 熵95. 105. 0log05. 022 . 0log2 . 03 . 0log3 . 04 . 0log4 . 0)(XH 编码效率%785 . 295. 1)(KXH 为提高编码效率,首先应达到满树;如把x4x5换成前面的节点,可减小平均码长。 不应先规定码长,而是由码树来规定码字,可得更好的结果。 x1x2x5x3x415 费

7、诺编码属于概率匹配编码 。 编码步骤如下： 将概率按从大到小的顺序排列,令p(x1) p(x2) p(xn) 按编码进制数将概率分组,使每组概率尽可能接近或相等。如编二进制码就分成两组,编m进制码就分成m组。 给每一组分配一位码元。 将每一分组再按同样原则划分,重复步骤2和3,直至概率不再可分为止。16信源符号xi 符号概率p(xi)第1次分组 第2次分组第3次分组码字 码长x10.4 00002x40.05100103x50.0510113x20.310102x30.21112 例设有一单符号离散信源 对该信源编二进制费诺码。05. 005. 02 . 03 . 04 . 0)(54321x

8、xxxxxpX信源符号xi 符号概率p(xi)第1分组 第2分组第3分组第4分组码字 码长x10.4 001x20.310102x30.2101103x40.0510 1110 4x50.051 1111 4平均码长：K= 2.1编码效率: =93% 平均码长：K= 2.0编码效率: =97.5% 17%931 . 295. 1)(11KXH 平均码长 编码效率 费诺码比较适合于每次分组概率都很接近的信源 特别是对每次分组概率都相等的信源进行编码时,可达到理想的编码效率。1 . 2) 305. 0 (222 . 023 . 024 . 0)(511iiiKxpK0 . 2) 405. 0 (2

9、32 . 023 . 014 . 0)(512iiiKxpK%5 .970 . 295. 1)(22KXH18例有一单符号离散无记忆信源 对该信源编二进制费诺码,编码过程如表:16/116/116/116/18/18/14/14/1,)(87654321xxxxxxxxXPX19 信源熵为 H(X)=2.75(比特/符号) 平均码长为)/(75. 2440625. 03212. 02)25. 025. 0(符号比特K 编码效率为 =1 之所以如此,因为每次所分两组的概率恰好相等。20 哈夫曼编码也是用码树来分配各符号的码字。 费诺码是从树根开始,把各节点分给某子集,若子集已是单点集,它就是一片

10、树叶而作为码字。 哈夫曼编码是先给每一符号一片树叶,逐步合并成节点直到树根。 哈夫曼(Huffman)编码是一种效率比较高的变长无失真信源编码方法。21 哈夫曼编码的步骤如下： 将信源消息符号按其出现的概率大小依次排列 p(x1)p(x2) p(xn)取两个概率最小的字母分别配以0和1两码元,并将这两个概率相加作为一个新字母的概率,与未分配的二进符号的字母重新排队。 对重排后的两个概率最小符号重复步骤的过程。不断继续上述过程,直到最后两个符号配以0和1为止。 从最后一级开始,向前返回得到各个信源符号所对应的码元序列,即相应的码字。22例5-7 设单符号离散无记忆信源如下,要求对信源编二进制哈夫

11、曼码。编码过程如下表01. 010. 015. 017. 018. 019. 020. 0)(7654321xxxxxxxxpX信源符号xi 符号概率p(xi)编码过程x10.20 x20.19x30.18x40.17x50.15x60.10 x70.01010.200.190.180.170.150.11010.260.200.190.180.17010.350.260.200.19010.390.350.26010.610.3901码字101100000101001100111在图中读取码字的时候,要从后向前读,此时编出来的码字是可分离的异前置码。23 熵61. 201. 0log01.

12、010. 0log10. 015. 0log15. 017. 0log17. 018. 0log18. 019. 0log19. 02 . 0log2 . 0)(XH 平均码长为72. 2401. 0410. 0315. 0317. 0318. 0219. 022 . 0)(71iiiKxpK 编码效率()()2.6196%2.72H XH XRK24 哈夫曼的编法并不惟一。 每次对缩减信源两个概率最小的符号分配“0”和“1”码元是任意的,所以可得到不同的码字。只要在各次缩减信源中保持码元分配的一致性,即能得到可分离码字。 不同的码元分配,得到的具体码字不同,但码长Ki不变,平均码长也不变,所

13、以没有本质区别； 缩减信源时,若合并后的新符号概率与其他符号概率相等,从编码方法上来说,这几个符号的次序可任意排列,编出的码都是正确的,但得到的码字不相同。 不同的编法得到的码字长度Ki也不尽相同。25 例5-8 单符号离散无记忆信源1 . 01 . 02 . 02 . 04 . 0,)(54321xxxxxXPX信源符号xi 符号概率p(xi)编码过程x10.4 x20.2x30.2x40.1x50.1010.40.20.20.2010.40.40.2010.60.401码字10100000100011码字00101101001126 27 单符号信源编二进制哈夫曼码,编码效率主要决定于信源

14、熵和平均码长之比。 对相同的信源编码,其熵是一样的,采用不同的编法,得到的平均码长可能不同。 平均码长越短,编码效率就越高。 编法一的平均码长为2 . 2231 . 0222 . 024 . 0)(512iiiKxpK2 . 2241 . 032 . 022 . 014 . 0)(511iiiKxpK 编法二的平均码长为 两种编法的平均码长相同,所以编码效率相同。28 讨论：哪种方法更好？ 定义码字长度的方差2：51222)()(iiiiKKxpKKE36. 12) 2 . 24 ( 1 . 0) 2 . 23 ( 2 . 0) 2 . 22 ( 2 . 0) 2 . 21 ( 4 . 022

15、222116. 02) 2 . 23 ( 1 . 02) 2 . 22 ( 2 . 0) 2 . 22 ( 4 . 022222 第二种编码方法的码长方差要小许多。 第二种编码方法的码长变化较小,比较接近于平均码长。29 第一种方法编出的5个码字有4种不同的码长； 第二种方法编出的码长只有两种不同的码长； 第二种编码方法更简单、更容易实现,所以更好。 在哈夫曼编码过程中,对缩减信源符号按概率由大到小的顺序重新排列时,应使合并后的新符号尽可能排在靠前的位置,这样可使合并后的新符号重复编码次数减少,使短码得到充分利用。30 在编m进制哈夫曼码时为了使平均码长最短,必须使最后一步缩减信源有m个信源符

16、号。 对于m进制编码,若所有码字构成全树,可分离的码字数必为: mk(ml) 非全树时,有s个码字不用： 第一次对最小概率符号分配码元时只取(ms)个,分别配以0,1, ,m-s-1,把这些符号的概率相加作为一个新符号的概率,与其它符号一起重新排列 以后每次取m个符号,分别配以0,1,m-1；如此下去,直至所有概率相加得1为止,即得到各符号的m进制码字。31 例:对如下单符号离散无记忆信源编三进制哈夫曼码04. 005. 006. 007. 01 . 01 . 018. 04 . 0,)(87654321xxxxxxxxXPX这里：m =3，n =8 令k=3，m+k(m1)=9，则 s =

17、9n = 98 =1 所以第一次取ms=2个符号进行编码。32信源符号xi 符号概率p(xi)编码过程x10.40 x20.18x30.10 x40.10 x50.07x60.06x70.05x80.04010120.400.180.100.100.090.070.060.400.220.180.100.100120.400.380.22012码字010111221222002013334 平均码长为)/(69. 13)04. 005. 0(2)06. 007. 01 . 018. 0(14 . 0)(51符号比特iiiKxpK)/(68. 23log169. 13log22符号比特LKR%2

18、 .9568. 255. 2)(RXH 信息率为 编码效率为 哈夫曼的编码效率相当高,对编码器的要求也简单得多。35 香农码、费诺码、哈夫曼码都考虑了信源的统计特性,使经常出现的信源符号对应较短的码字,使信源的平均码长缩短,从而实现了对信源的压缩； 香农码有系统的、惟一的编码方法,但在很多情况下编码效率不是很高； 费诺码和哈夫曼码的编码方法都不惟一； 费诺码比较适合于对分组概率相等或接近的信源编码,费诺码也可以编m进制码,但m越大,信源的符号数越多,可能的编码方案就越多,编码过程就越复杂,有时短码未必能得到充分利用；对信源的统计特性没有特殊要求,编码效率比较高,对编码设备的要求也比较简单,因此综合性能优于香农码和费诺码。36 5-1137 香农编码、费诺编码、哈夫曼编码主要是针对无记忆信源。 当信源有记忆时上述编码效率不高； 游程编码对编码更有效； 香农编码、费诺编码、哈夫曼编码属于无失真信源编码； 游程编码属于限失真信源编码。38： 数字序列中连续出现相同符号的一段。 二元序