第五章_信源编码

1、1第五章信源编码5.1.1 码字唯一可译的条件码字唯一可译的条件5.1.2 香农编码香农编码5.1.3 费诺编码费诺编码5.1.4 赫夫曼编码赫夫曼编码5.1.5 游游程程编码编码5.1.6 冗余位编码冗余位编码2信源编码概述编码是为了优化通信系统，一般的通信系统的主要性编码是为了优化通信系统，一般的通信系统的主要性能指标：有效性、可靠性和安全性能指标：有效性、可靠性和安全性信源编码的目的：提高通信系统的有效性，通常通过信源编码的目的：提高通信系统的有效性，通常通过压缩信源的冗余度来实现，即压缩每个信源符号的信压缩信源的冗余度来实现，即压缩每个信源符号的信息量，使得同样多的信息用较少的信息传输

2、率来传送息量，使得同样多的信息用较少的信息传输率来传送信源编码的思路：根据信源输出符号序列的统计特性，信源编码的思路：根据信源输出符号序列的统计特性，寻找一定的把信源输出符号序列变换为最短码字序列寻找一定的把信源输出符号序列变换为最短码字序列的方法的方法信源编码的基本途径：使编码后的符号序列中的各个信源编码的基本途径：使编码后的符号序列中的各个符号尽可能地相互独立，即解除相关性；使编码后各符号尽可能地相互独立，即解除相关性；使编码后各个符号出现的概率尽可能的相等，即概率均匀化。个符号出现的概率尽可能的相等，即概率均匀化。信源编码的基础：无失真编码定理和限失真编码定理信源编码的基础：无失真编码定

3、理和限失真编码定理35.1 离散信源 5.1.1 码字唯一可译的条件码的分类码的分类 定定长长码码码码变变长长码码 奇奇异异码码非非唯唯一一可可译译码码码码非非奇奇异异码码非非即即时时码码唯唯一一可可译译码码即即时时码码按码长分类按码长分类定长码：码中所有码字的码长都相等定长码：码中所有码字的码长都相等奇异码：码中存在有相同的码字奇异码：码中存在有相同的码字( (对应不同的信源符号对应不同的信源符号) )唯一可译码：由码的码字组成任意有限长的码字序列只能被唯一可译码：由码的码字组成任意有限长的码字序列只能被唯一地译为对应的信源符号序列唯一地译为对应的信源符号序列即时码：译码器收到一个完整的唯一

4、可译码字以后，无需参即时码：译码器收到一个完整的唯一可译码字以后，无需参考后续的码字考后续的码字( (码元码元) )就能立即译码就能立即译码定长码定长码非奇异码非奇异码&唯一可译码唯一可译码45.1.1 码字唯一可译的条件1001001码码 C11100100码码 B11100000码码 A50.50概概 率率信信 源源码码 F码码 E码码 D00110011011001110011111110001x2x3x4x码码 A：奇异码、定长码、非唯一可译码：奇异码、定长码、非唯一可译码码码 B：非奇异码、定长码、唯一可译码：非奇异码、定长码、唯一可译码码码 C：非奇异码、非唯

5、一可译码：非奇异码、非唯一可译码码码 D：唯一可译码：唯一可译码码码 E：非即时码：非即时码码码 F：即时码：即时码1423112211, 10, 00, 0111000011, 1, 00, 00, 1x x x xx x x x x 01010001 已已译译码码2301xx 即时码中即时码中任何一个任何一个码字均不码字均不是其它码是其它码字的前缀字的前缀变长码变长码即时码即时码&唯一可译码唯一可译码5定义：如果一个码组中的任一个码字都不是另一个码字的延定义：如果一个码组中的任一个码字都不是另一个码字的延长或者找不到任何一个码字是另一个码字的前缀，或者说，长或者找不到任何一个码字是另一个码

6、字的前缀，或者说，任何一个码字后加上若干码元后都不是码组中另一个码字，任何一个码字后加上若干码元后都不是码组中另一个码字，则称为则称为即时码或非延长码即时码或非延长码。也叫前缀条件码。也叫前缀条件码/ /异前置码异前置码/ /异字异字头码头码/ /逗点码逗点码所有的码所有的码非奇异码非奇异码唯一可译码唯一可译码即时码即时码5.1.1 码字唯一可译的条件65.1.1 码字唯一可译的条件用树图法可以方便地构造即时码。从树根开始，树中每个中间用树图法可以方便地构造即时码。从树根开始，树中每个中间节点都伸出节点都伸出 1 至至 r 个树枝，不同的树枝标记不同的码元。个树枝，不同的树枝标记不同的码元。将

7、所有的码字都安排在将所有的码字都安排在终端节点上就可以得到即时码上就可以得到即时码每个中间节点都正好有每个中间节点都正好有 r 个分枝的树称为整树个分枝的树称为整树( (满树满树) )所有终端节点的阶数都相等的树为完全树，对应于定长码所有终端节点的阶数都相等的树为完全树，对应于定长码2r 75.1.1 码字唯一可译的条件二元满树二元满树二元非满树二元非满树三元非满树三元非满树三元满树三元满树8唯一可译定长码存在的条件对于定长码，非奇异码一定是唯一可译码对于定长码，非奇异码一定是唯一可译码lnr logloglnNr Nlnr loglognlr 1212, ,nrXx xxnCc ccl 单单

8、符符号号离离散散信信源源信信源源符符号号集集中中共共有有个个符符号号码码元元集集定定长长码码码码长长为为12(,)NNNXXXn X次次扩扩展展得得到到的的多多符符号号离离散散信信源源信信源源符符号号集集共共有有个个符符号号注意注意：上述条件是：上述条件是，而而非充分条件非充分条件平均每个单信平均每个单信源符号所需要源符号所需要码元的个数码元的个数9maxmax()jijijjllllljilll 此此外外，对对应应于于码码长长的的阶阶节节点点，它它不不能能是是的的祖祖先先节节点点或或子子孙孙节节点点， 因因此此由由延延伸伸到到阶阶的的终终端端节节点点必必与与延延伸伸到到阶阶的的终终端端节节点

9、点不不同同；克拉夫特(Kraft)不等式12121,1innlninrY YYrl ll 对对符符号号数数为为的的信信源源进进行行进进制制变变长长编编码码，其其码码字字为为，相相应应的的码码长长分分别别为为，若若编编码码是是即即时时码码，必必有有：反反之之，若若码码长长满满足足上上述述不不等等式式，则则一一定定存存在在具具有有这这样样码码长长的的即即时时码码maxmaxmax12maxmax ,iinliilllll llrlrlllr ：记记，则则可可构构造造一一个个 元元阶阶满满树树其其终终端端节节点点数数为为。 即即时时码码中中码码长长为为 的的码码字字安安排排于于码码树树的的第第 阶阶

10、中中的的某某个个节节点点，由由即即时时码码的的条条件件可可知知，以以此此节节点点延延伸伸树树枝枝至至阶阶的的终终端端节节点点数数有有，它它们们不不能能安安排排码码字字。证证maxlr maxmax1illnilr 所所有有延延伸伸至至阶阶的的终终端端节节点点数数为为：KraftKraft？是是即即时时码码不不等等式式成成立立不不等等式式成成立立是是即即时时码码Kraft唯唯一一可可译译码码也也满满足足不不等等式式，且且任任何何唯唯一一可可译译码码可可用用具具有有相相同同码码长长的的某某个个即即时时码码替替代代反反向向如如何何证证明明？10唯一可译码判别准则01210jiij110n-01-01

11、n 1SS ,SSSWWW =W AASSAS ,1,WSSUS,SUSWSW=UASnnnnUWA为原始码字的集合。再构造一系列集合。为得到集合，首先考察中所有的码字。若码字是码字的前缀，即，则将其后缀列为中的元素，就是由所有具有这种性质的构成的集合。一般地则将比较。如有码字，且W是的前缀，即则取后缀为中的元素。同样，如有码字是的前缀，即与，120S ,SASSSnn一种码是唯一可译码的充要条则也是中的元素。如此便可件是： 中没有一个构成集合。则有下面命含有中题:的码字。11唯一可译码判别准则举例设信源消息集合设信源消息集合x1,x2, x3,x4, x5,x6,x7，它们分别被编码，它们分

12、别被编码为为a,c,ad,abb, bad,deb,bbcde，可构造出下表所示的，可构造出下表所示的吗符号集序列吗符号集序列S0S1S2S3S4S5S6S7adebdebaddebcbbcdebcdeadabbbaddebbbcde当n7时，sn是空集，而s5都包含s0中的元素，因此不是唯一可译码125.1.2香农编码香农编码是采用信源符号的累计概率分布函数来分配码字的香农编码是采用信源符号的累计概率分布函数来分配码字的设某离散无记忆信源设某离散无记忆信源 2 进制香农编码步骤：进制香农编码步骤：1212()()()()nnxxxXP Xp xp xp x 将信源符号以概率递减的次序排列起来

13、，为方便起见，令：将信源符号以概率递减的次序排列起来，为方便起见，令：12()()()np xp xp x 按下式求按下式求 x i 对应码字的码长对应码字的码长 l i ：log()log()1iiip xlp x 按下式逐步求信源符号按下式逐步求信源符号 x i 的概率累加和的概率累加和 P i ：1110,()2,3,iikkPPp xin 将所有的累加和概率将所有的累加和概率 P i 变换成变换成 2 进制数；取小数点后进制数；取小数点后 P i 位作位作为信源符号为信源符号 x i 的的 2 进制码字进制码字()iilI x 13编码所得的码字，没有相同的，所以是非奇异码，也没有一编

14、码所得的码字，没有相同的，所以是非奇异码，也没有一个码字是其它码字的前缀，所以是即时码。个码字是其它码字的前缀，所以是即时码。香农码的效率不高，其冗余度较大，不是最佳码，香农码的效率不高，其冗余度较大，不是最佳码，实用性受实用性受到较大限制到较大限制xip ( xi )Pi loglog p ( xi )li码字x10.3701.434200 x20.160.372.6443010 x30.140.582.8373100 x40.130.672.9433101x50.070.803.83741100 x60.060.874.059511011x70.040.934.644511101x80.0

15、30.975.059611111081()2.99 /iiilp x l ：码码元元 符符号号平均码长81()()log ()2.583bi /iiiH Xp xp xt ：符符号号信源熵()2.58386.4%log2.99H Xlr 编码效率：12345678()0.37 0.16 0.14 0.13 0.07 0.06 0.04 0.03xxxxxxxxXP X 14例：有一单符号离散无记忆信源例：有一单符号离散无记忆信源123456,()05XxxxxxxP X练习练习二进制香农编码二进制香农编码 xi p(xi) pa(xj) ki 码字码

16、字 x1 0.25 0.000 2 00(0.000)2 x2 0.25 0.250 2 01(0.010)2 x3 0.20 0.500 3 100(0.100)2 x4 0.15 0.700 3 101(0.101)2 x5 0.10 0.850 4 1101(0.1101)2 x6 0.05 0.950 5 11110(0.11110)2 对该信源编二进制香农码。其编码过程如下表所示。对该信源编二进制香农码。其编码过程如下表所示。155.1.3费诺编码费诺编码又称为子集分解法，通过将信源符号的概率分组，费诺编码又称为子集分解法，通过将信源符号的概率分组，对每个组分配相应的码元来实现编码，

17、其编码步骤如下：对每个组分配相应的码元来实现编码，其编码步骤如下：将信源符号以概率递减的次序排列起来，为方便起见，令将信源符号以概率递减的次序排列起来，为方便起见，令:12()()()np xp xp x 将依次排列的信源符号按概率分成将依次排列的信源符号按概率分成 r 组，使每个组的信源符组，使每个组的信源符号的概率和尽可能接近或相等，然后赋予每组一个号的概率和尽可能接近或相等，然后赋予每组一个 r 元码符元码符号；例如编号；例如编 2 进制费诺码，则每次分组均分成两组，每个组进制费诺码，则每次分组均分成两组，每个组分别赋予一个分别赋予一个 2 元码元码符号符号“0”或或“1”将每一大组的信

18、源符号按概率和递减的次序再分成将每一大组的信源符号按概率和递减的次序再分成 r 组，使组，使同一大组细分的同一大组细分的 r 个小组的信源符号的概率和尽可能接近或个小组的信源符号的概率和尽可能接近或相等，并分别赋予每小组一个相等，并分别赋予每小组一个 r 元码符号；元码符号；重复上述的分组，分配重复上述的分组，分配 r 元码符号的过程，直至最个分得的元码符号的过程，直至最个分得的每个小组只剩一个信源符号为止，最后每个信源符号所对应每个小组只剩一个信源符号为止，最后每个信源符号所对应的码元序列就是相应的码字的码元序列就是相应的码字16xip ( xi )费诺编码码字lix10.3700002x2

19、0.161012x30.141001003x40.1311013x50.0710011004x60.06111014x70.041011104x80.0311111481()2.67 /iiilp x l ：码码元元 符符号号平均码长()2.583bi /H Xt 信源熵：符符号号2.58396.7%2.67 编码效率：香香农农码码：2.99 /码码元元 符符号号86.4%12345678()0.37 0.16 0.14 0.13 0.07 0.06 0.04 0.03xxxxxxxxXP X 17费诺编码的码树图费诺编码的码树图实质上是一种构造码实质上是一种构造码树的方法，所以费诺树的方法，

20、所以费诺码是即时码码是即时码概率大，则分解的次概率大，则分解的次数小；概率小数小；概率小, 则分则分解的次数多解的次数多码字集合是唯一的码字集合是唯一的分解完后，码字与码分解完后，码字与码长便确定了长便确定了费诺码考虑了信源的统计特性，使经常出现的信源符号对应费诺码考虑了信源的统计特性，使经常出现的信源符号对应短码字，但是不一定能使短码得到充分利用，尤其当信源符短码字，但是不一定能使短码得到充分利用，尤其当信源符号较多时，若有一些符号概率分布很接近时，分两大组的组号较多时，若有一些符号概率分布很接近时，分两大组的组合方法就会很多。可能某种分大组的结果，会使后面小组的合方法就会很多。可能某种分大

21、组的结果，会使后面小组的“概率和概率和”相差较远，从而使平均码长增加。相差较远，从而使平均码长增加。费诺编码特点费诺编码特点12345678()0.37 0.16 0.14 0.13 0.07 0.06 0.04 0.03xxxxxxxxXP X 18xip ( xi )费诺编码码字lix10.2500002x20.251012x30.1251001003x40.12511013x50.062510011004x60.0625111014x70.06251011104x80.06251111141234567811111111()448816161616xxxxxxxxXP X ()2.75b

22、i /H Xt 信源熵：符符号号1114816222344l 平均码长：2.752.75100% 编码效率：费诺码适合于每次分组概率费诺码适合于每次分组概率都很接近的信源。特别是对都很接近的信源。特别是对每次分组概率都相等的信源每次分组概率都相等的信源进行编码时，可达到理想的进行编码时，可达到理想的编码效率编码效率费诺码考虑了信源的统计特性，使概率大的信源符号能对应码费诺码考虑了信源的统计特性，使概率大的信源符号能对应码长短的码字，从而有效地提高了编码效率长短的码字，从而有效地提高了编码效率。一般而言，费诺编码不是最佳编码，它的编码效率一般而言，费诺编码不是最佳编码，它的编码效率( (优于香农

23、码优于香农码) )要比赫夫曼编码效率稍低要比赫夫曼编码效率稍低2.75 / 码码元元 符符号号19例：设有一单符号离散信源 对该信源编二进制费诺码。123456,()0.360.080.04XxxxxxxP X练习练习205.1.4赫夫曼编码赫夫曼编码是一种最佳的逐个符号的编码方法，所得的码是即赫夫曼编码是一种最佳的逐个符号的编码方法，所得的码是即时码，其平均码长最短，因而是最佳编码时码，其平均码长最短，因而是最佳编码2 进制赫夫曼编码的步骤如下：进制赫夫曼编码的步骤如下：将信源符号以概率递减的次序排列起来，为方便起见，令将信源符号以概率递减的次序排列起来，为方便起见，

24、令:12()()()np xp xp x 将两个概率最小的信源符号将两个概率最小的信源符号 x n 1, x n 各分配一个码元各分配一个码元“0”和和“1”，并将这两个符号合并成一个新符号，合并后新符号，并将这两个符号合并成一个新符号，合并后新符号概率为原来两个符号概率之和，从而得到包含概率为原来两个符号概率之和，从而得到包含 n 1 个符号个符号的缩减信源的缩减信源 S1 把缩减信源把缩减信源 S1 的符号仍按概率递减次序排列，重复步骤的符号仍按概率递减次序排列，重复步骤 2 得得到只含有到只含有 n 2 个信源符号的缩减信源个信源符号的缩减信源 S2 重复上述步骤，直至缩减信源只剩重复上

25、述步骤，直至缩减信源只剩 1 个信源符号为止；然后个信源符号为止；然后从最后一级缩减信源开始，依编码路径向前返回，就得到各从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码元序列，即对应的码字信源符号所对应的码元序列，即对应的码字21xip(xi)缩减信源码字liS1S2S3S4S5S6S7x10.37x20.16x30.14x40.13x50.07x60.06x70.04x80.030.0701070.360.631.00101010101000110001001110110000001000115544433112345678()0.37 0.1

26、6 0.14 0.13 0.07 0.06 0.04 0.03xxxxxxxxXP X 22赫夫曼编码的码树赫夫曼编码的码树12345678()0.37 0.16 0.14 0.13 0.07 0.06 0.04 0.03xxxxxxxxXP X ()2.583 bi /H Xt 符符号号81()2.66 /iiilp x l ：码码元元 符符号号平均码长2.5832.6697.1% ：编码效率2.99 /香香农农码码：码码元元 符符号号2.67 /费费诺诺码码：码码元元 符符号号86.4%香香农农码码：96.7%费费诺诺码码：赫夫曼编码的特点赫夫曼编码的特点概率大的符号安排在离概率大的符号安

27、排在离根节点较近的终端节点根节点较近的终端节点保证了概率大的符号对保证了概率大的符号对应于短码，概率小的符应于短码，概率小的符号对应于长码号对应于长码每次缩减信源的最长两每次缩减信源的最长两个码字具有相同码长个码字具有相同码长每次缩减信源的最后两每次缩减信源的最后两个码字总是最后一位码个码字总是最后一位码元不同，前面各位码元元不同，前面各位码元相同相同( (2 元码情况元码情况) )编码不具有惟一性编码不具有惟一性赫夫曼编码是最佳码赫夫曼编码是最佳码23方差越小，各码字长度方差越小，各码字长度就越接近平均码长，设就越接近平均码长，设计的编码器也就越简单计的编码器也就越简单赫夫曼编码的非唯一性每

28、次对缩减信源两个概率最小的符号分配每次对缩减信源两个概率最小的符号分配“0”或或“1”码元码元是任意的，所以可得到不同的码字。只要在各次缩减信源中是任意的，所以可得到不同的码字。只要在各次缩减信源中保持码元分配的一致性，即能得到可分离码字，即能得到可分离码字不同的码元分配，得到的具体码字不同，但码长不同的码元分配，得到的具体码字不同，但码长 li 不变，平均不变，平均码长也不变，所以没有本质区别码长也不变，所以没有本质区别缩减信源时，若合并后新符号的概率与其它符号概率相等，缩减信源时，若合并后新符号的概率与其它符号概率相等，从编码方法上来说，这几个符号的次序可任意排列，编出的从编码方法上来说，

29、这几个符号的次序可任意排列，编出的码都是正确的，但得到的码字不相同。不同的编法得到的码码都是正确的，但得到的码字不相同。不同的编法得到的码字长度字长度 li 也不尽相同，但平均码长仍不变也不尽相同，但平均码长仍不变对同一信源的多种赫夫曼编码，除了用平均码长来衡量外，对同一信源的多种赫夫曼编码，除了用平均码长来衡量外，当平均码长相同时，可以码长当平均码长相同时，可以码长 li 偏离平均码长的方差来判断：偏离平均码长的方差来判断：22() iE ll 22() ( )iiE lE l 21()()niiillp x 22()iE ll 24xip(xi)编码过程码字lix10.37x20.16x3

30、0.14x40.13x50.07x60.06x70.04x80.030.070.370.160.1 0.130.070.060.130.330.070.200.330.270.360.370.270.630.370101010101011.00011001010000001110110000100001113344455方案一12345678()0.37 0.16 0.14 0.13 0.07 0.06 0.04 0.03xxxxxxxxXP X 25xip(xi)缩码过程码字lix10.37x20.16x30.14x40

31、.13x50.07x60.06x70.04x80.030.030.270.360.370.270.630.370101010101011.000110010100110000100010000000000011333546612345678()0.37 0.16 0.14 0.13 0.07 0.06 0.04 0.03xxxxxxxxXP X 0.070.370.160.1 0.130.060.130.37方案二26赫夫曼编码的非唯一性（续）xip(xi)码长 li方案一方案二x10.3711x2

32、0.1633x30.1433x40.1343x50.0744x60.0645x70.0456x80.0356平均码长2.66 /码码元元 符符号号20.37 1(3)30.0740.065(0.040.03) 62.66 /l 码码元元 符符号号222122()0.37 1(0.160.14) 3(0.130.070.06) 4(0.040.03) 58.98iE l 2229.382.662.304 2222222()0.37 1(3)30.0740.06 5(0.040.03) 69.38iE l 2218.982.661.904 方案一较好，其

33、方案一较好，其码长变化较小码长变化较小在赫夫曼编码过程中，当缩减信源符号按概率大小，以递减次序自上而下在赫夫曼编码过程中，当缩减信源符号按概率大小，以递减次序自上而下重新排列时，应把合并后的新符号重新排列时，应把合并后的新符号尽量置于缩减信源中具有相同概率的其它符号之上，减少合并后的新符号被重复赋予码元的次数，进而减小码字，减少合并后的新符号被重复赋予码元的次数，进而减小码字长度相对于平均码长的摆动长度相对于平均码长的摆动上述方法不会引起平均码长的变化，可以使短码得到充分利用上述方法不会引起平均码长的变化，可以使短码得到充分利用27r 进制赫夫曼编码r 进制赫夫曼编码是进制赫夫曼编码是 2 进

34、制编码的推广；求缩减信源时需要求进制编码的推广；求缩减信源时需要求 r 个信源符号使其概率和最小，并对个信源符号使其概率和最小，并对 r 个信源符号分别分配码元个信源符号分别分配码元0,1, r 1，然后将它们缩减为一个新符号，重复上述缩减和，然后将它们缩减为一个新符号，重复上述缩减和分配码元的步骤直至缩减信源中只剩下一个符号为止分配码元的步骤直至缩减信源中只剩下一个符号为止 r 进制霍夫曼编码，如果从一始就每进制霍夫曼编码，如果从一始就每 r 个符号缩减为一个新符个符号缩减为一个新符号，则缩减到最后时剩下的信源符号可能不到号，则缩减到最后时剩下的信源符号可能不到 r 个，为了使平个，为了使平

35、均码长最短，必须使最后一步缩减信源有均码长最短，必须使最后一步缩减信源有 r 个信源符号个信源符号全树全树非全树非全树码树图中至少有一个中间节码树图中至少有一个中间节点的后续枝数不足点的后续枝数不足 r码树图中每个中间节码树图中每个中间节点后续枝数为点后续枝数为 r2 进制码不进制码不存在非全树存在非全树的情况，因的情况，因为后续枝数为后续枝数是是 1 时，这时，这个枝就可以个枝就可以去掉使码字去掉使码字长 度 缩 短长 度 缩 短28r 进制赫夫曼编码(续)对对 r 进制编码，若所有码字构成全树，可分离的码字数必为：进制编码，若所有码字构成全树，可分离的码字数必为：k 为信源缩减次数为信源缩

36、减次数 1(1)rk r 若信源所含的符号数若信源所含的符号数 n 不能构成不能构成 r 进制全树，必须增加进制全树，必须增加 s 个不个不用的码字形成全树，且用的码字形成全树，且 s r 1若若 s r 1，意味着某个中间节点之后只有一个分枝，为了，意味着某个中间节点之后只有一个分枝，为了节约码长，这一分枝可以省略节约码长，这一分枝可以省略为了使平均码长最短，当码树为非全树时，有为了使平均码长最短，当码树为非全树时，有 s 个码字不用：个码字不用：第一次对最小概率和的符号分配码元时只取第一次对最小概率和的符号分配码元时只取 r s 个，分别赋个，分别赋予码元予码元 0,1, r s 1，把这

37、些符号的概率相加作为一个新符，把这些符号的概率相加作为一个新符号的概率，与其它符号一起重新排列号的概率，与其它符号一起重新排列 以后每次就可以取以后每次就可以取 r 个符号，分别赋予码元个符号，分别赋予码元 0,1, r 1；如；如此下去直至缩减至此下去直至缩减至 1 个信源符号，得到各符号的个信源符号，得到各符号的 r 进制码字进制码字29可见，要发挥赫夫曼编码的优势，一般情况下，信源符号集的符可见，要发挥赫夫曼编码的优势，一般情况下，信源符号集的符号数应远大于码元数号数应远大于码元数8n 信信源源符符号号数数：xip(xi)3 进制赫夫曼缩码过程码字 lix10.37x20.16x30.1

38、4x40.13x50.07x60.06x70.04x80.030.43xip(xi) 4 进制赫夫曼缩码过程 码字 lix10.37x20.16x30.14x40.13x50.07x60.06x70.04x80.030.070.201.0021100012220120002212223320.070.331.00120231311111010211123320.370.160.1 0.070.060.130.340.370.200.370.160.1 0.070.060.130.370.160.140132103210210210102103, 3(31)8,rks 4

39、, 4(41)8,rks 25,ks1,3,sk 2rs34ks ，2,2,sk2rs()2.583 bi /H Xt 符符号号81()1.7 /iiilp x l ：三三元元码码元元 符符号号平均码长2.58395.9%1.7log3 ：编码效率81()1.4 /iiilp x l ：四四元元码码元元 符符号号平均码长2.58392.3%1.4log4 ：编码效率30练习练习设单符号离散无记忆信源如下，要求对信源编二进设单符号离散无记忆信源如下，要求对信源编二进制霍夫曼码。制霍夫曼码。12345678,( )0.4 0.18 0.1 0.1 0.07 0.06 0.05 0.04Xxxxxx

40、xxxP Xn在图中读取码字的时候，一定要从后向前读，此时编出来的码字才是可分离的异前置码。若从前向后读取码字，则码字不可分离。31香农码、费诺码和赫夫曼码总结香农码、费诺码、赫夫曼码都考虑了信源的统计特性，香农码、费诺码、赫夫曼码都考虑了信源的统计特性，使经常出现的信源符号对应较短的码字，使信源的平使经常出现的信源符号对应较短的码字，使信源的平均码长缩短，从而实现了对信源的压缩。均码长缩短，从而实现了对信源的压缩。香农码编码结果唯一，但在很多情况下编码效率不是香农码编码结果唯一，但在很多情况下编码效率不是很高很高费诺码和赫夫曼码的编码方法都不唯一费诺码和赫夫曼码的编码方法都不唯一费诺码比较适

41、合于对分组概率相等或接近的信源编码费诺码比较适合于对分组概率相等或接近的信源编码赫夫曼码对信源的统计特性没有特殊要求，编码效率赫夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对编码设备的要求也比较简单，因此综合性比较高，对编码设备的要求也比较简单，因此综合性能优于香农码和费诺码能优于香农码和费诺码赫夫曼码通常适用于多元信源，对于二元信源，必须赫夫曼码通常适用于多元信源，对于二元信源，必须采用合并符号的方法，才能得到较高的编码效率采用合并符号的方法，才能得到较高的编码效率325.1.5 游程编码概述香农码、费诺码、赫夫曼码主要是针对无记忆信源；当信源香农码、费诺码、赫夫曼码主要是针对无记忆

42、信源；当信源有记忆时上述编码的效率不高有记忆时上述编码的效率不高游程编游程编码是一种对相关信源较为有效的扩展符号集的编码方码是一种对相关信源较为有效的扩展符号集的编码方法，是赫夫曼编码的改进和应用，主要用于只有黑、白二值法，是赫夫曼编码的改进和应用，主要用于只有黑、白二值灰度的文灰度的文件传真，如文件、报纸、表格、手写体字、图纸等件传真，如文件、报纸、表格、手写体字、图纸等文件传真是把一页文件扫描为文件传真是把一页文件扫描为 n m 个像素。由于黑、白个像素。由于黑、白二值文件只有两个灰度值，因此采用二值文件只有两个灰度值，因此采用 2 进制编码。进制编码。如果每一个像素用一位二进制码如果每一

43、个像素用一位二进制码( (0：白色，：白色，1：黑色：黑色) )表示，表示，显然一页文件的码元数就等于该页文件的像素数显然一页文件的码元数就等于该页文件的像素数例如，参照国际标准，一张例如，参照国际标准，一张 A4 幅面幅面( (210 mm 297 mm) )的的二值文件扫描的辨率为：二值文件扫描的辨率为：1728像素像素/ /行行，4行行/ /mm即一幅即一幅 A4 页面共可分为页面共可分为 1188 行，每行行，每行 1728 像素。整幅共像素。整幅共有有 2.05 M 个像素，若用个像素，若用 4800 bit/s 的信息传输率进行传输的信息传输率进行传输约需约需 7.2 分钟，直接传

44、真将需耗费大量的通信时间分钟，直接传真将需耗费大量的通信时间33游程编码概述(续)统计表明，此类传真文件黑白两个灰度值出现的概率为：统计表明，此类传真文件黑白两个灰度值出现的概率为：()93.3%()6.7%pp 白白，黑黑()()log()()log()0.933log0.9330.067log0.0670.3546 bit / H Xpppp 像像素素熵熵：白白白白黑黑黑黑像像素素()log2110.354664.54%H X 冗冗余余度度：显然一个像素用一位二进制编码，会有很大冗余度，要提高显然一个像素用一位二进制编码，会有很大冗余度，要提高传真效率，必须去除冗余传真效率，必须去除冗余对

45、于二值灰度的文件，每一扫描行均是由若干个连白对于二值灰度的文件，每一扫描行均是由若干个连白( (0) )像素像素序列及若干个连黑序列及若干个连黑( (1) )像素序列组合而成，且同类像素连续出像素序列组合而成，且同类像素连续出现的概率很大，因此可通过像素类别现的概率很大，因此可通过像素类别( (黑或白黑或白) )加重复次数来加重复次数来表示，由此思想构成的编码称为游程编码表示，由此思想构成的编码称为游程编码重复出现的同类像素的长度称为重复出现的同类像素的长度称为游程长度；白白( (0) )像素序列称像素序列称为白为白( (0) )游程，游程， 黑黑( (1) )像素序列称为黑像素序列称为黑(

46、(1) )游程游程34游程编码概述(续)游程编码的基本结构是编码单元：游程编码的基本结构是编码单元：符号码标识码游程长度像素序列：白白黑黑黑黑白白白白白白黑黑黑像素序列：白白黑黑黑黑白白白白白白黑黑黑游程编码：白游程编码：白#2黑黑#4白白#6黑黑#3实际上，每一扫描行的白像素序列和黑像素序列是交替出现实际上，每一扫描行的白像素序列和黑像素序列是交替出现的，若规定第一游程为白游程的，若规定第一游程为白游程( (若第一游程为黑游程，则在黑游若第一游程为黑游程，则在黑游程前插入一个游程长度为程前插入一个游程长度为 0 的白游程的白游程) )，则可将编码中的，则可将编码中的“符号符号码码”和和“标识

47、码标识码”均省略，均省略，这样就可把像素序列变换为游程长度这样就可把像素序列变换为游程长度序列，且二者是可逆的。例如：序列，且二者是可逆的。例如：像素类别：像素类别：“白白”( (0) )“黑黑”( (1) )符号码和游符号码和游程长度之间程长度之间的 分 割 符的 分 割 符游程长度序列：游程长度序列：45287613321黑白像素序列：黑白像素序列：0000111110011111111000000011111101110001104528761 33 2 1游程长度是随机的，取值为游程长度是随机的，取值为1,2,直直至无穷至无穷一一对应的可逆变换35游程：数字序列中连续出现相同符号的一段

48、游程：数字序列中连续出现相同符号的一段二元序列的游程：只有二元序列的游程：只有“0”和和“1”两两种符号种符号连连“0”这一段称为这一段称为“0”游程，游程长度：游程，游程长度：L(0)连连“1”这一段称为这一段称为“1”游程，游程长度：游程，游程长度：L(1) 在二元序列中，在二元序列中，“0”游程和游程和“1”游程总是交替出现的游程总是交替出现的游程变换将二元序列变换成了多元序列，减弱了原序列符号间的相关游程变换将二元序列变换成了多元序列，减弱了原序列符号间的相关性，这样就适合于用其它方法，如赫夫曼编码，进一步压缩信源，提性，这样就适合于用其它方法，如赫夫曼编码，进一步压缩信源，提高通信效

49、率高通信效率r 元序列同样也可以变换游程长度序列，但是元序列同样也可以变换游程长度序列，但是 r 元序列，总共有元序列，总共有 r 种游程，种游程，为能保证一一对应的可逆变换性，必须再加一些分隔标志符号，才能区分为能保证一一对应的可逆变换性，必须再加一些分隔标志符号，才能区分游程长度序列中的某一个长度是游程长度序列中的某一个长度是 r 种游程中的哪一个长度；增加分隔标志种游程中的哪一个长度；增加分隔标志符号可能会抵消压缩编码得到的好处，故一般不对多元序列进行游程编码符号可能会抵消压缩编码得到的好处，故一般不对多元序列进行游程编码游程编码的方法：游程编码的方法：首先测定首先测定“0”游程长度和游

50、程长度和“1”游程长度的概率分布，即以游程长度游程长度的概率分布，即以游程长度为元素，构造一个新的信源为元素，构造一个新的信源对新的信源对新的信源( (游程长度序列游程长度序列) )进行赫夫曼编码进行赫夫曼编码游程编码一般规定二元序列一般规定二元序列总是从总是从“0”开始开始36二元独立序列的游程长度序列(0) 101 (0)(0)1,2,3,Lp LppL 注：在计算注：在计算 p L( 0 ) 时第一个信源符号必然是时第一个信源符号必然是“0”，否则就不，否则就不是是“0”游程，若下一个符号是游程，若下一个符号是“1”，则游程长度为，则游程长度为 1，其，其概率是概率是 p1 1 1 p0

51、；若下一个符号为；若下一个符号为“0”、再下一个符号、再下一个符号为为“1”，则游程长度为，则游程长度为 2，其概率为，其概率为 p0 p1；依此类推；依此类推(1) 110 (1)Lp Lpp 同理可得：同理可得：(0) 101(0) 1(0) 1 (0)LLLp Lpp 1 10010(1)1pppp 101pp 1 0(1) 11 (1)11Lpp Lp 若二元独立序列的概率特性已知，由于二元独立序列与游程若二元独立序列的概率特性已知，由于二元独立序列与游程长度序列的一一对应性，可计算出游程长度序列的概率特性长度序列的一一对应性，可计算出游程长度序列的概率特性设二元独立序列中符号设二元独

52、立序列中符号“0”和和“1”出现的概率分别为出现的概率分别为 p0 和和 p1 ，则则“0”游程长度游程长度 L(0) 的概率为：的概率为：37“0”游程长度序列的熵：游程长度序列的熵：(0) 101(0) 1(1) 110(1) 1 (0)(0)1,2,3, (0)1 (1)(1)1,2,3, (1)1LLLLp LppLp Lp LppLp L (0) 1 (0) (0)log (0)LH Lp Lp L “1”游程长度序列的熵：游程长度序列的熵：10 (1)()HH pLp 同理可得：同理可得： (0) 1(0) 1(0) 1010(0) 1011 (0)1loglogLLLLLpppp

53、pp (0) 2(0) 1010(0) 101(0) 101(log) (0)1(log)LLLLp ppLpppp (0) 1010(0) 101(log)logLLp pppp (0) 1010(0) 101(log)logLLp pppp 010100d1(log)logd1p ppppp 1001111(log)logpppppp (0) 1(0) 1(0) 10101logLLLpppp 0101201(log)log(1)p pppp 001111(log)(log)ppppp 01()H pp 38“0”游程的平均长度：游程的平均长度：(0) 101(0) 101(1) 110(

54、1) 110 (0) (0)1 (0)() (1) (1)1 (1)()LLLLp Lppp LH LH ppp Lppp LH LH pp “1”游程的平均长度：同理可得游程的平均长度：同理可得011lp 二元独立序列的熵：二元独立序列的熵：“0”游程长度序列的熵与游程长度序列的熵与“1”游程长度序列的熵之和除以它们的平均游程长度序列的熵之和除以它们的平均游程长度之和，即为对应的原二元独立序列的熵游程长度之和，即为对应的原二元独立序列的熵 H ( X )01 (0) (1)()H LH LH Xll 游程变换后符号熵保持不变。因为游程变换是一一对应的可逆变换游程变换后符号熵保持不变。因为游程

55、变换是一一对应的可逆变换000111()(log)(log)()H pppppH p 0(0) 1 (0)(0) (0)LlE LLp L (0) 1(0) 101(0)LLLpp (0)1(0) 100ddLLppp 100d11d1ppp (0)1(0) 100ddLLppp 0100dd1pppp 100d1d1ppp 1201(1)pp 11p 011010()()11H pH ppppp 001101()()p H pp H ppp 0()H p 1()H p 39游程编码的编码效率根据编码效率的定义和前述分析可得二元序列的编码效率：根据编码效率的定义和前述分析可得二元序列的编码效率

56、：01 (0) (1) (0) (1)H LH LH LH L 假设假设 0 1，易知：，易知： 0 1当当“0”游程和游程和“1”游程的编码效率都很高时，采用游程编码游程的编码效率都很高时，采用游程编码的整体编码效率也很高，至少不会低于较小的那个游程的编的整体编码效率也很高，至少不会低于较小的那个游程的编码效率码效率要想游程的整体编码效率尽可能高，应尽可能提高熵值较大要想游程的整体编码效率尽可能高，应尽可能提高熵值较大的游程的编码效率的游程的编码效率0101 (0) (1),H LH LRR 假设假设“0”游程长度和游程长度和“1”游游程长度的赫夫曼编码效率分程长度的赫夫曼编码效率分别为别为

57、 1, 2，即：，即：40游程编码的截断处理尽管游程长度可以从尽管游程长度可以从 1 一直到无穷长，但建立游程长度与赫夫一直到无穷长，但建立游程长度与赫夫曼码字之间的一一对应码表将是非常困难曼码字之间的一一对应码表将是非常困难游程越长，其出现的概率就越小，所以：游程越长，其出现的概率就越小，所以： (0 1) (0,1)0Lp L ，由赫夫曼码的编码规则，概率越小，码字越长；但小概率对由赫夫曼码的编码规则，概率越小，码字越长；但小概率对应的长码字对平均码长影响很小，故对较长的二元序列，游应的长码字对平均码长影响很小，故对较长的二元序列，游程编码一般需采用截断处理，以下为一种截断处理方法程编码一

58、般需采用截断处理，以下为一种截断处理方法选取适当的选取适当的 n 值，将游程长度分别为值，将游程长度分别为 的游程进的游程进行赫夫曼编码，得到相应的码表行赫夫曼编码，得到相应的码表 1,2,3,21n 所有游程长度大于等于所有游程长度大于等于 的游程，将其编码为多个固定的码的游程，将其编码为多个固定的码字字 C 串接游程长度减去串接游程长度减去 所得余数的二进制表示，具体为：所得余数的二进制表示，具体为：2n2n游程长度：游程长度： ，则游程编码为，则游程编码为 CA，其中，其中 A 为游程为游程长度减去长度减去 所得余数补足为所得余数补足为 n 位的二进制表示，位的二进制表示，12 21nn

59、 2n游程长度：游程长度： ，则游程编码为，则游程编码为 C000CA，其，其中中 A 为游程长度减去为游程长度减去 所得余数的二进制表示，依此类推所得余数的二进制表示，依此类推112 221nnn12n n 个个41游程编码的截断处理(续)例如：如选择例如：如选择 n 8，则可用，则可用 255 个码字构成的赫夫曼码表对应个码字构成的赫夫曼码表对应于游程长度不超过于游程长度不超过 255 的游程；如用的游程；如用 C 表示所有游程长度超过表示所有游程长度超过 255 的游程对应的码字的前半部分，则：的游程对应的码字的前半部分，则：游程长度编码260C00000100516C00000000C

60、00000100772C00000000C000000000C00000100“0”游程和游程和“1”游程当分别编码，建立各自的码表游程当分别编码，建立各自的码表两个码表中的码字可以有重复，但两个码表中的码字可以有重复，但 C 码必须不同，即分别用码必须不同，即分别用 C0 , C1 编码编码“0”游程和游程和“1”游程游程译码器要根据后面的码字来判断当前游程的长度译码器要根据后面的码字来判断当前游程的长度000000101nC 个个(0)25nL 0C(0)25nL 继续考察更后面的码字继续考察更后面的码字 1C后面码后面码字为：字为： 42MH 码MH 码是黑白二值文件、传真类数据压缩编码