信息论第8章北理工

1、1第一节第一节 香农编码香农编码第八章第八章 无失真的信源编码无失真的信源编码2信源编码概述信源编码概述o 信源编码理论是信息论的一个重要分支，其理信源编码理论是信息论的一个重要分支，其理 论基础是信源编码的两个定理。论基础是信源编码的两个定理。n 无失真信源编码无失真信源编码：针对离散信源或数字信号：针对离散信源或数字信号n 限失真信源编码限失真信源编码：适用于波形信源或波形信号（模：适用于波形信源或波形信号（模拟信号）。拟信号）。信源编码的分类：离散信源编码、连续信源编码和相信源编码的分类：离散信源编码、连续信源编码和相关信源编码三类。关信源编码三类。n 离散信源编码离散信源编码：独立信源

2、编码，可做到无失真：独立信源编码，可做到无失真编码；编码；n 连续信源编码连续信源编码：独立信源编码，只能做到限失：独立信源编码，只能做到限失真信源编码；真信源编码；n 相关信源编码相关信源编码：非独立信源编码。：非独立信源编码。3o 有些编码原理和技术在通信原理和信号处理等有些编码原理和技术在通信原理和信号处理等相关课程中已经介绍过。例如：相关课程中已经介绍过。例如：n连续信源编码：脉冲编码调制连续信源编码：脉冲编码调制(PCM)(PCM)、矢量量、矢量量化技术；化技术；n相关信源编码：相关信源编码：o预测编码预测编码：增量编码、差分脉冲调制：增量编码、差分脉冲调制(DPCM)(DPCM)、

3、自适应差分脉冲调制自适应差分脉冲调制(ADPCM)(ADPCM)、线性预测声、线性预测声码器；码器；o变换编码变换编码：K KL L变换、离散变换、子带编码、变换、离散变换、子带编码、小波变换。小波变换。4定理定理5.8 5.8 无失真变长信源编码定理（香农第一定理）无失真变长信源编码定理（香农第一定理）离散无记忆信源离散无记忆信源S的的N次扩展信源次扩展信源 ，其熵为，其熵为 ，并且编，并且编码器的码元符号集为码器的码元符号集为A： 对信源对信源 进行编码，总进行编码，总可以找到一种编码方法，构成唯一可译码，使信源可以找到一种编码方法，构成唯一可译码，使信源S中每个符中每个符号所需要的平均码

4、长满足号所需要的平均码长满足 NS()NH S12,.,q NS()()1loglogNHSLHSrNrNlim( )rNLHS当 则得：N 回顾香农第一定理回顾香农第一定理5 这个定理是香农信息论中非常重要的一个定理，这个定理是香农信息论中非常重要的一个定理，它指出，要做到无失真的信源编码，信源每个符号它指出，要做到无失真的信源编码，信源每个符号所需要的平均码元数就是信源的熵值，如果小于这所需要的平均码元数就是信源的熵值，如果小于这个值，则唯一可译码不存在，可见，个值，则唯一可译码不存在，可见，熵是无失真信熵是无失真信源编码的极限值源编码的极限值。定理还指出，通过对扩展信源进。定理还指出，通

5、过对扩展信源进行编码，当行编码，当N N趋向于无穷时，平均码长可以趋近该趋向于无穷时，平均码长可以趋近该极限值。极限值。 6第一节第一节 香农编码香农编码qiiqqxpxpxpxpxxx121211)(,)(.)()(.设有离散无记忆信源设有离散无记忆信源7)(log)(logiiixplxp221的的码码字字位位作作为为点点后后的的用用二二进进制制表表示示，用用小小数数把把iijaxlxp)(1234香农编码方法的步骤香农编码方法的步骤按信源符号的概率从大到小的顺序排队)(.)()(qxpxpxp21设设个码字的累加概率表示第，用令iijxpxpja1),(0)(0111)()(jiijax

6、pxp8 例例 有一单符号离散无记忆信源有一单符号离散无记忆信源o 对该信源编二进制香农码。其编码过程如下表所示。对该信源编二进制香农码。其编码过程如下表所示。05.010.015.020.025.025.0,)(654321xxxxxxXPX表表5.1.1 二进制香农编码二进制香农编码xip(xi)pa(xj)li码字码字x10.250200(0.000)2x20.250.25201(0.010)2x30.20.53100(0.100)2x40.150.73101(0.101)2x50.10.8541101(0.1101)2x60.050.955111110(0.11110)29o计算出给定

7、信源香农码的平均码长计算出给定信源香农码的平均码长o若对上述信源采用等长编码，要做到无失真译码，每若对上述信源采用等长编码，要做到无失真译码，每个符号至少要用个符号至少要用3 3个比特表示。相比较，香农编码对信个比特表示。相比较，香农编码对信源进行了压缩。源进行了压缩。)/(.).(.)(符号符号比特比特7250504100315020222501qiiilxpL10o 由离散无记忆信源熵定义，可计算出：由离散无记忆信源熵定义，可计算出：o 对上述信源采用香农编码的信息率为对上述信源采用香农编码的信息率为o 编码效率为信源熵和信息率之比。则编码效率为信源熵和信息率之比。则可以看出，编码效率并不

8、是很高。可以看出，编码效率并不是很高。)/(42. 2)x(plog)x(p)X(H61ii2i符号符号比特比特2172217222rNrNLR,.log.log这里这里%63.897 . 242. 2)(RXH11第二节第二节 费诺编码费诺编码 费诺编码也是一种常见的信源编码方法。编码步骤费诺编码也是一种常见的信源编码方法。编码步骤如下：如下：o 将概率按从大到小的顺序排列，令将概率按从大到小的顺序排列，令p p( (x x1 1) ) p p( (x x2 2) p p( (x xq q) )o 按编码进制数将概率分组，使每组概率和尽可能按编码进制数将概率分组，使每组概率和尽可能接近或相等

9、。如编二进制码就分成两组，编接近或相等。如编二进制码就分成两组，编r r进进制码就分成制码就分成r r组。组。o 给每一组分配一位码元。给每一组分配一位码元。o 将每一分组再按同样原则划分，重复步骤将每一分组再按同样原则划分，重复步骤2 2和和3 3，直至概率不再可分为止。直至概率不再可分为止。12 例例 设有一单符号离散信源设有一单符号离散信源o 对该信源编二进制费诺码。编码过程如下表。对该信源编二进制费诺码。编码过程如下表。05. 010. 015. 020. 025. 025. 0 x,x,x,x,x,x)X(PX654321表5.3.1 二进制费诺编码信源符号信源符号概率概率编码编码码

10、字码字码长码长x10.2500002x20.251012x30.2010102x40.15101103x50.101011104x60.0511111413o 上述码字还可用码树来表示，如图下所示。14o 该信源的熵为该信源的熵为o 平均码长为平均码长为o 编码效率为编码效率为o 本例中费诺编码有较高的编码效率。费诺码比较适合本例中费诺编码有较高的编码效率。费诺码比较适合于于每次分组概率都很接近每次分组概率都很接近的信源。特别是对每次的信源。特别是对每次分组分组概率都相等概率都相等的信源进行编码时，可达到理想的编码效的信源进行编码时，可达到理想的编码效率。率。)/(42325. 2)x(plo

11、g)x(p)X(H61ii2i符号符号比特比特)/(.)(符号符号比特比特61452iiilxpL219198452423224232214522rNrXHNL,%.log.log)(.这里这里15 例例 有一单符号离散无记忆信源有一单符号离散无记忆信源o对该信源编二进制费诺码，编码过程如表。对该信源编二进制费诺码，编码过程如表。16/116/116/116/18/18/14/14/1,)(87654321xxxxxxxxXPX16o 码树图如图。码树图如图。o 信源熵为信源熵为 H H( (X X)=2.75()=2.75(比特比特/ /符号符号) )o 平均码长为平均码长为o 编码效率为编

12、码效率为=1=1。之所以如此，因为每次所分两组的概率恰。之所以如此，因为每次所分两组的概率恰好相等。好相等。)/(.).(符号符号比特比特7524406250321202250250L17第三节第三节 霍夫曼编码霍夫曼编码 霍夫曼霍夫曼(Huffman)编码是一种效率比较高的变长编码是一种效率比较高的变长无失真信源编码方法。无失真信源编码方法。o编码步骤编码步骤o二进制霍夫曼编码二进制霍夫曼编码or进制霍夫曼编码进制霍夫曼编码18o 将信源符号按概率从大到小的顺序排列，令将信源符号按概率从大到小的顺序排列，令p(x1) p(x2) p(xq)o 给两个概率最小的信源符号给两个概率最小的信源符号

13、p(xn-1)和和p(xn)各分配一个码位各分配一个码位“0”和和“1”，将这两个信源符号合并成一个新符号，并用这两个，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含最小的概率之和作为新符号的概率，结果得到一个只包含(q1)个信源符号的新信源。称为个信源符号的新信源。称为信源的第一次缩减信源信源的第一次缩减信源，用，用S1表示。表示。o 将缩减信源将缩减信源S1的符号仍按概率从大到小顺序排列，重复步骤的符号仍按概率从大到小顺序排列，重复步骤2，得到只含得到只含(q2)个符号的缩减信源个符号的缩减信源S2。o 重复上述步骤，直至缩减信源只剩两个符号

14、为止，此时所剩重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为两个符号的概率之和必为1。然后从最后一级缩减信源开始，。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。依编码路径向前返回，就得到各信源符号所对应的码字。19例例 设单符号离散无记忆信源如下，要求对信源编二进制设单符号离散无记忆信源如下，要求对信源编二进制 霍夫曼码。编码过程如下图（后页）。霍夫曼码。编码过程如下图（后页）。12345678,()0.40.180.10.10.070.060.050.04XxxxxxxxxP Xn在图中读取码字的时候，一定要从后向前读，此时编出在

15、图中读取码字的时候，一定要从后向前读，此时编出来的码字才是可分离的异前置码。若从前向后读取码字，来的码字才是可分离的异前置码。若从前向后读取码字，则码字不可分离。则码字不可分离。2021o 将上图左右颠倒过来重画一下，即可得到二进制哈夫将上图左右颠倒过来重画一下，即可得到二进制哈夫曼码的码树。曼码的码树。22o 信源熵为：信源熵为：o 平均码长为平均码长为o 编码效率为编码效率为o 若采用定长编码，码长若采用定长编码，码长L=3，则编码效率，则编码效率o 可见哈夫曼的编码效率提高了可见哈夫曼的编码效率提高了12.7%。821( )( )log( )2.55(/)iiiH Xp xp x比特 符

16、号()()2.552.6197.7%HXHXRK2.55385%)/(.)(符号符号比特比特81612iiilxpL23注意：注意：哈夫曼的编法并不惟一哈夫曼的编法并不惟一。o每次对缩减信源两个概率最小的符号分配每次对缩减信源两个概率最小的符号分配“0 0”和和“1 1”码元是任意的，所以可得到不同的码字。只码元是任意的，所以可得到不同的码字。只要要在各次缩减信源中保持码元分配的一致性在各次缩减信源中保持码元分配的一致性，即即能得到可分离码字。能得到可分离码字。o不同的码元分配，得到的具体码字不同，但码长不同的码元分配，得到的具体码字不同，但码长L Li i不变，平均码长也不变，所以没有本质区

17、别；不变，平均码长也不变，所以没有本质区别；o缩减信源时，若合并后的新符号概率与其他符号缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方法上来说，概率相等，从编码方法上来说，这几个符号的次这几个符号的次序可任意排列，编出的码都是正确的，但得到的序可任意排列，编出的码都是正确的，但得到的码字不相同码字不相同。不同的编法得到的不同的编法得到的码字长度码字长度L Li i也不也不尽相同尽相同。24例例 设有离散无记忆信源设有离散无记忆信源1 . 01 . 02 . 02 . 04 . 0)(54321xxxxxXPX用两种不同的方法对其编二进制用两种不同的方法对其编二进制huffmanh

18、uffman码码25方法一方法一方法二方法二26 27信源符号信源符号xi概率概率p(xi) 码字码字Wi1码长码长Li1码字码字Wi2码长码长Li2x10.411002x20.2012102x30.20003112x40.1001040103x50.1001140113两种不同的编码方法得到的码字和码长的对比两种不同的编码方法得到的码字和码长的对比28两种编码的平均码长是一样的，都是两种编码的平均码长是一样的，都是2.2，那一种更好，那一种更好呢，我们可以计算一下平均码长的方差。呢，我们可以计算一下平均码长的方差。511( )0.4 1 0.2 20.2 30.1 40.1 42.2iiiL

19、P s l 521( )0.4 20.2 20.2 20.1 30.1 32.2iiiLP s l 2221() ( )()qiiiiE lLP slL522111( )()1.36iiiP slL522221( )()0.16iiiP slL定义码字长度的方差定义码字长度的方差2：29n可见：第二种编码方法的码长方差要小许多。意味着可见：第二种编码方法的码长方差要小许多。意味着第二种编码方法的码长变化较小，比较接近于平均码第二种编码方法的码长变化较小，比较接近于平均码长。长。l第一种方法编出的第一种方法编出的5 5个码字有个码字有4 4种不同的码长；种不同的码长；l第二种方法编出的码长只有两

20、种不同的码长；第二种方法编出的码长只有两种不同的码长；l显然，显然，第二种编码方法更简单、更容易实现，所以第二种编码方法更简单、更容易实现，所以更好更好。结论：结论：在哈夫曼编码过程中，对缩减信源符号按概率由大在哈夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应到小的顺序重新排列时，应使合并后的新符号尽可能使合并后的新符号尽可能排在靠前的位置排在靠前的位置，这样可使合并后的新符号重复编码，这样可使合并后的新符号重复编码次数减少，使短码得到充分利用。次数减少，使短码得到充分利用。30“全树全树”概念概念o 定义：码树图中每个中间节点后续的枝数为定义：码树图中每个中间节点后续的枝数

21、为r时称为时称为全树全树；若有些节点的后续枝数不足若有些节点的后续枝数不足r，就称为，就称为非全树非全树。o 二进制码不存在非全树的情况，因为后续枝数是二进制码不存在非全树的情况，因为后续枝数是1时，这个时，这个枝就可以去掉使码字长度缩短。枝就可以去掉使码字长度缩短。o 对对r进制编码：若所有码字构成全树，可分离的码字数（信进制编码：若所有码字构成全树，可分离的码字数（信源个数）必为源个数）必为 r+k(r1)。k为信源缩减次数。为信源缩减次数。o 若信源所含的符号数若信源所含的符号数q不能构成不能构成r进制全树，必须增加进制全树，必须增加s个不个不用的码字形成全树。用的码字形成全树。31o

22、在编在编r进制哈夫曼码时为了使平均码长最短，必须使最进制哈夫曼码时为了使平均码长最短，必须使最后一步缩减信源有后一步缩减信源有r个信源符号。非全树时，有个信源符号。非全树时，有s个码字个码字不用不用.n 第一次对最小概率符号分配码元时就只取第一次对最小概率符号分配码元时就只取(rs)个，个，分别配以分别配以0,1,rs1，把这些符号的概率相加作，把这些符号的概率相加作为一个新符号的概率，与其它符号一起重新排列。为一个新符号的概率，与其它符号一起重新排列。n 以后每次就可以取以后每次就可以取r个符号，分别配以个符号，分别配以0,1,r1；如此下去，直至所有概率相加得如此下去，直至所有概率相加得1

23、为止，即得到各符为止，即得到各符号的号的r进制码字。进制码字。32例：对如下单符号离散无记忆信源编三进制哈夫曼码。例：对如下单符号离散无记忆信源编三进制哈夫曼码。这里：这里：r=3，q=8o 令令k=3，r+k(r1)=9，则，则 s=9q=98=1o 所以第一次取所以第一次取rs=2个符号进行编码。个符号进行编码。12345678,()0.40.180.10.10.070.060.050.04XxxxxxxxxP X333435o 平均码长为平均码长为o 信息率为信息率为o 编码效率为编码效率为o 可见：哈夫曼的编码效率相当高，对编码器的要求可见：哈夫曼的编码效率相当高，对编码器的要求也简单

24、得多。也简单得多。)/(.).().(.)(符号符号比特比特6913040050206007010180140511iiilxpL)/(.log.log符号符号比特比特68231691322NLR%2 .9568. 255. 2)(RXH36(3) (3) 结论结论o 香农码、费诺码、赫夫曼码都考虑了信源的统计特性，使香农码、费诺码、赫夫曼码都考虑了信源的统计特性，使经常出现的信源符号对应较短的码字，使信源的平均码长经常出现的信源符号对应较短的码字，使信源的平均码长缩短，从而实现了对信源的压缩；缩短，从而实现了对信源的压缩；o 香农码有系统的、惟一的编码方法，但在很多情况下编码香农码有系统的、

25、惟一的编码方法，但在很多情况下编码效率不是很高；效率不是很高；o 费诺码和赫夫曼码的编码方法都不惟一；费诺码和赫夫曼码的编码方法都不惟一；o 费诺码比较适合于对分组概率相等或接近的信源编码，费费诺码比较适合于对分组概率相等或接近的信源编码，费诺码也可以编诺码也可以编r r进制码，但进制码，但r r越大，信源的符号数越多，可越大，信源的符号数越多，可能的编码方案就越多，编码过程就越复杂，有时短码未必能的编码方案就越多，编码过程就越复杂，有时短码未必能得到充分利用；能得到充分利用；o 赫夫曼码对信源的统计特性没有特殊要求，编码效率比较赫夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对编码设备

26、的要求也比较简单，因此综合性能优于香高，对编码设备的要求也比较简单，因此综合性能优于香农码和费诺码农码和费诺码。37实际使用中注意的问题实际使用中注意的问题o 误差扩散问题：误差扩散问题： 实际信道中有噪声存在，必然要破坏变长码的实际信道中有噪声存在，必然要破坏变长码的结构。同时由于变长码是不加同步的码，无法自结构。同时由于变长码是不加同步的码，无法自动清洗产生的错误使得产生的错误扩散。动清洗产生的错误使得产生的错误扩散。 在工程上哈夫曼码只能适合于高信噪比的优在工程上哈夫曼码只能适合于高信噪比的优质信道，如：误码率低于质信道，如：误码率低于1010-6-6以下。以下。 工程上还常常采用定期清

27、洗的方法，如在文件工程上还常常采用定期清洗的方法，如在文件或报纸中采用按行清洗的方式，以牺牲编码效率或报纸中采用按行清洗的方式，以牺牲编码效率达到限制误差扩散的目的。达到限制误差扩散的目的。38o 速率匹配问题速率匹配问题 由于信源消息是不等概率的，因而编成的变长由于信源消息是不等概率的，因而编成的变长码长度也是不相同的，这必然导致信源输出速率是码长度也是不相同的，这必然导致信源输出速率是变化的，然而在实际信道中传送的信息率是变化的，然而在实际信道中传送的信息率是固定不固定不变化变化的。的。 一般在工程中采用缓冲存储器的方法，变速输一般在工程中采用缓冲存储器的方法，变速输入恒速输出，存储器容量

28、的选取与信源统计特性和入恒速输出，存储器容量的选取与信源统计特性和编码方法，以及输出速率密切相关。容量选大了浪编码方法，以及输出速率密切相关。容量选大了浪费设备，容量小了会产生溢出或取空现象。费设备，容量小了会产生溢出或取空现象。实际使用中注意的问题39o 与信源统计特性相匹配的问题与信源统计特性相匹配的问题 一般变长码更适合于大的消息集，而不大一般变长码更适合于大的消息集，而不大适合消息集小且概率分布相差很大的集合。小适合消息集小且概率分布相差很大的集合。小集合只有在很特殊情况下才能实现统计匹配。集合只有在很特殊情况下才能实现统计匹配。 如果信源的统计特性不完全知道，则无如果信源的统计特性不

29、完全知道，则无法实现变长编码。法实现变长编码。实际使用中注意的问题40第四节第四节 游程编码游程编码一一. .游程编码对象和性质游程编码对象和性质二二. . 游程编码的定义游程编码的定义三三. . 二元独立序列二元独立序列四四. . 游程编码的效率游程编码的效率五五. . 长码的截断处理方法长码的截断处理方法41一一. . 游程编码对象和性质游程编码对象和性质o香农编码、费诺编码、哈夫曼编码主要是针对无记忆香农编码、费诺编码、哈夫曼编码主要是针对无记忆信源。当信源有记忆时上述编码效率不高；信源。当信源有记忆时上述编码效率不高；o游程编码对游程编码对相关信源相关信源编码更有效；编码更有效；o香农

30、编码、费诺编码、哈夫曼编码属于香农编码、费诺编码、哈夫曼编码属于无失真信源编无失真信源编码码；o游程编码属于游程编码属于限失真信源编码限失真信源编码。42二二. . 游程编码的定义游程编码的定义o游程游程：数字序列中连续出现相同符号的一段。：数字序列中连续出现相同符号的一段。o二元序列的游程：只有二元序列的游程：只有“0 0”和和“1 1”两种符号。两种符号。n连连“0 0”这一段称为这一段称为“0 0”游程，它的长度称为游程，它的长度称为游程游程长度长度L L(0)(0)；n连连“1 1”这一段称为这一段称为“1 1”游程，它的游程长度用游程，它的游程长度用L L(1)(1)表示。表示。43

31、三三. . 二元独立序列二元独立序列 二元独立序列游程长度概率二元独立序列游程长度概率o若规定二元序列总是从若规定二元序列总是从“0 0”开始，第一个游程是开始，第一个游程是“0 0”游程，则第二个游程必为游程，则第二个游程必为“1 1”游程，第三个又游程，第三个又是是“0 0”游程游程。o对于随机序列，游程长度是随机的其取值可为对于随机序列，游程长度是随机的其取值可为1,2,3,1,2,3,，直至无穷。，直至无穷。44o游程长度序列游程长度序列/ /游程序列：用交替出现的游程序列：用交替出现的“0 0”游程和游程和“1 1”游程长度表示任意二元序列。游程长度表示任意二元序列。o游程变换游程变

32、换：是一种一一对应的变换，也是可逆变换。：是一种一一对应的变换，也是可逆变换。 例如：二元序列例如：二元序列 000101110010001000101110010001 可变换成如下游程序列可变换成如下游程序列 3113213131132131o游程变换减弱了原序列符号间的相关性。游程变换减弱了原序列符号间的相关性。o游程变换游程变换将二元序列变换成了多元序列将二元序列变换成了多元序列；这样就适；这样就适合于用其他方法，如哈夫曼编码，进一步压缩信源，合于用其他方法，如哈夫曼编码，进一步压缩信源，提高通信效率。提高通信效率。45编码方法编码方法n 首先测定首先测定“0 0”游程长度和游程长度和

33、“1 1”游程长度的概率分布，游程长度的概率分布，即即以游程长度为元素，构造一个新的信源以游程长度为元素，构造一个新的信源；n 对新的信源（游程序列）进行哈夫曼编码。对新的信源（游程序列）进行哈夫曼编码。 多元序列也可以变换成游程序列，如多元序列也可以变换成游程序列，如r r元序列可元序列可有有r r种游程。但是变换成游程序列时，需要增加标志位种游程。但是变换成游程序列时，需要增加标志位才能区分游程序列中的才能区分游程序列中的“长度长度”是是r r种游程中的哪一个种游程中的哪一个的长度，否则，变换就不可逆。这样，增加的标志位的长度，否则，变换就不可逆。这样，增加的标志位可能会抵消压缩编码得到的

34、好处。所以，可能会抵消压缩编码得到的好处。所以，对多元序列对多元序列进行游程变换的意义不大进行游程变换的意义不大。46 二元独立序列游程长度的熵二元独立序列游程长度的熵o若二元序列的概率特性已知，由于二元序列与游程若二元序列的概率特性已知，由于二元序列与游程变换序列的一一对应性，可计算出游程序列的概率变换序列的一一对应性，可计算出游程序列的概率特性。特性。o令令“0 0”和和“1 1”的概率分别为的概率分别为p p0 0和和p p1 1，则，则“0 0”游程长度游程长度L L(0)(0)的概率为的概率为 p p L L(0)=(0)=p p0 0L L(0)(0)1 1p p1 1 式中式中L

35、 L(0)=1,2,(0)=1,2, ,o在计算在计算p p L L(0)(0)时必然已有时必然已有“0 0”出现，否则就不是出现，否则就不是“0 0”游程，若下一个符号是游程，若下一个符号是“1 1”，则游程长度为，则游程长度为1 1，其概率是其概率是p p1 1 =1 =1p p0 0；若下一个符号为；若下一个符号为“0 0”、再下一、再下一个符号为个符号为“1 1”，则游程长度为，则游程长度为2 2，其概率将为，其概率将为p p0 0p p1 1 ；依此类推。依此类推。47o游程长度至少是游程长度至少是1 1，理论上，游程长度可以是无穷，理论上，游程长度可以是无穷，但很长的游程实际出现的

36、概率非常小。但很长的游程实际出现的概率非常小。o同理可得同理可得“1 1”游程长度游程长度L L(1)(1)的概率为的概率为P P L L(1)=(1)=p p1 1L L(1)-1(1)-1p p0 0(0) 1(0) 10110(0) 1(0) 1(0) 12110001234 (0)(1)11(1)1LLLLLp Lpppppppppxxxxx 11)1 (101) 1 (ppLpL48121)0(001)0(0201121)0(021)0(011)0(1211)0(01)0(1)0(0211)0(01)0(11)0(0211)0(01)0(2log)log(loglog 1)0(log

37、loglog)0(log)0()0(ppdpdpppppLppppppppppppLpLpLHLLLLLLLLLLLLL2(0) 1(0) 1(0) 101201(0) 1(0) 1(0) 1(0) 101200121(0) 1(0) 1(0) 1(0) 1110100(0) 1(0) 1 (0) (0)log (0)log log logloglog (0) 1LLLLLLLLLLLLLH Lp Lp LpppppppppppppppLp 根011102000010111 (0)loglog11()logpH LpppppppH ppppp 据无穷等比级数和的公式得：o“0”游程长度的熵游程

38、长度的熵49 二元独立序列的平均游程长度二元独立序列的平均游程长度o“0 0”游程序列的平均游程长度游程序列的平均游程长度o同理可得同理可得“1 1”游程长度的熵和平均游程长度游程长度的熵和平均游程长度(0) 1001(0) 1(0) 112011234 (0)(0) (0)(0)11(1)(1)1LLLlE LLp LLpppppxxxxx 01001)1 ()()1 (pLElppHLH50 二元独立序列的熵二元独立序列的熵o“0 0”游程序列的熵与游程序列的熵与“1 1”游程长度的熵之和除以游程长度的熵之和除以它们的平均游程长度之和，即为对应原二元序列它们的平均游程长度之和，即为对应原二

39、元序列的熵的熵H H( (X X) )o游程变换后符号熵没有变。因为游程变换是一一游程变换后符号熵没有变。因为游程变换是一一对应的可逆变换，所以变换后熵值不变，这也说对应的可逆变换，所以变换后熵值不变，这也说明变换后的游程序列是独立序列。明变换后的游程序列是独立序列。0101 (0) (1)()()()(8.30)H LH LH XH pH pll51o对于有相关性的二元序列，也可以证明变换后的游对于有相关性的二元序列，也可以证明变换后的游程序列是独立序列，并且也有程序列是独立序列，并且也有 的结论，只是此时的结论，只是此时H H L L(0)(0)，H H L L(1)(1)，l l0 0和

40、和l l1 1的具体的具体表达形式不同，它们是相关符号的联合概率和条件表达形式不同，它们是相关符号的联合概率和条件概率的函数。概率的函数。01 (0) (1)()H LH LH Xll52五. 长码的截断处理方法o理论上，游程长度可从理论上，游程长度可从1 1到无穷，要建立游程长度和到无穷，要建立游程长度和码字之间的一一对应的码表是困难的。码字之间的一一对应的码表是困难的。o一般情况下，游程越长，出现的概率越小；当游程长一般情况下，游程越长，出现的概率越小；当游程长度趋向于无穷时，出现的概率也趋于度趋向于无穷时，出现的概率也趋于0 0。o按照哈夫曼编码规则，概率越小，码字越长。但小概按照哈夫曼

41、编码规则，概率越小，码字越长。但小概率的码字对平均码长影响较小。所以在实际应用时，率的码字对平均码长影响较小。所以在实际应用时，常对长码采用截断处理的方法。常对长码采用截断处理的方法。8.5.1 算术编码特点及应用8.5.2 信源符号序列的累积分布函数F(s)及对应的区间8.5.3 信源序列累积分布函数的递推公式8.5.4 算术编码方法8.5.5 算术编码的译码538.5 8.5 算术编码算术编码o 算术编码不同于哈夫曼码，它是非分组（非块）码。它从全序列出发，考虑符号之间的关系来进行编码。o 算术编码利用了累积概率的概念。o 算术码主要的编码方法是计算输入信源符号序列所对应的区间。o 因为在

42、编码过程中，每输入一个符号要进行乘法和加法运算，所以称此编码方法为算术编码。o 二元序列的算术编码可用于黑白图像的编码，例如传真。548.5.1 8.5.1 算术编码的码特点及应用算术编码的码特点及应用o 设信源符号集A=a1,a2,an，其相应概率分布为P(ai)，P(ai) 0(i=1,2, ,n)o 信源符号的累积分布函数为 所得累积分布函数为每台级的下界值，则其区间为0,1)左闭右开区间。 F(a1)=0 F(a2)=P(a1) F(a3)=P(a1)+P(a2) o 当A=0,1二元信源二元信源时： F(0)=0 F(1)=P(0),()()(11AaaaPaFkikiik558.5

43、.2 信源符号序列的累积分布函数信源符号序列的累积分布函数F(s s)及对应的区间及对应的区间o 计算二元无记忆信源序列二元无记忆信源序列的累积分布函数n 初始时：在0,1)区间内由F(1)划分成二个子区间0,F(1)和F(1),1)， F(1)= P(0)。o 子区间0,F(1)的宽度为A(0)= P(0)，对应于信源符号“0”；o 子区间F(1),1)的宽度为A(1)= P(1)，对应于信源符号“1”；o 若输入符号序列的第一个符号为s=“0”，落入0,F(1)区间，得 累积分布函数F(s=“0”)= F(0)=0； 56n 输入第二个符号为“1”，s=“01”os=“01”所对应的区间是

44、在区间0,F(1)中进行分割；o 符号序列“00”对应的区间宽度为A(00)=A(0)P(0)=P(0)P(0)=P(00)；o 对应的区间为0,F(s=“01”)。o 符号序列“01”对应的区间宽度为A(01)=A(0)P(1)=P(0)P(1)=P(01)= A(0)A(00)；o 对应的区间为F(s=“01”),F(1)。o 累积分布函数F(s=“01”)=P(00)= P(0)P(0)57n输入第三个符号为“1”：o 输入序列可记做s1=“011”（若第三个符号输入为“0”，可记做s0=“010”）；o 现在，输入序列s1=“011”对应的区间是对区间F(s),F(1)进行分割；o 序

45、列s0=“010”对应的区间宽度为 A(s=“010”)=A(s=“01”)P(0)=A(s)P(0) 其对应的区间为F(s), F(s)+ A(s)P(0)；o 序列s1=“011”对应的区间宽度为 A(s=“011”)=A(s)P(1)=A(s=“01”)A(s=“010”)= A(s )A(s0) 其对应的区间为F(s)+A(s)P(0),F(1)；o 符号序列s1=“011”的累积分布函数为F(s1)=F(s)+A(s)P(0)；o 若第三个符号输入为“0”，符号序列s0=“010”的区间下界值仍为F(s)，得符号序列s0=“010”的累积分布函数为F(s0)=F(s)。58n 归纳o

46、 当已知前面输入符号序列为s，若接着再输入一个符号“0”，序列s0的累积分布函数为： F(s0)=F(s)o 对应区间宽度为： A(s0)=A(s)P(0)o 若接着输入的一个符号是“1”，序列的累积分布函数为：F(s1)=F(s)+A(s)P(0)o 对应区间宽度为： A(s1)=A(s)P(1)=A(s)A(s0)59n 符号序列对应的区间宽度A(s=“0”)=P(0)A(s=“1”)=1A(s=“0”)=P(1)A(s=“00”)=P(00)=A(0)P(0)=P(0)P(0)A(s=“01”)=A(s=“0”)A(s=“00”)=P(01)=A(0)P(1)=P(0)P(1)A(s=“

47、10”)=P(10)=A(1)P(0)=P(1)P(0)A(s=“11”)=A(s=“1”)A(s=“10”)=P(11)= A(s=“1”)P(1)=P(1)P(1)A(s=“010”)=A(s=“01”)P(0)=P(01)P(0)P(010)A(s=“011”)=A(s=“01”)A(s=“010”)=A(s=“01”)P(1)=P(01)P(1)=P(011) 信源符号序列信源符号序列s s所对应区间的宽度所对应区间的宽度A(s)等于符号序列等于符号序列s s的概率的概率P(s s)。60o 二元信源符号序列的累积分布函数的递推公式nF(sr)=F(s)+P(s)F(r) (r=0,1

48、) (8.51)sr表示已知前面信源符号序列为s，接着再输入符号为rF(0)=0， F(1)=P(0)F(s0)=F(s)F(s1)=F(s)+P(s)F(1)= F(s)+P(s)P(0)nA(sr)=P(sr)=P(s)P(r) (r=0,1) (8.52) A(s0)=P(s0)=P(s)P(0) A(s1)=P(s1)=P(s)P(1)618.58.5.3 信源序列累积分布函数的递推公式o 举例：已输入二元符号序列为s=“011”，接着再输入符号为“1”，得序列累积分布函数为： F(s1)=F(0111)=F(s=“011”)+P(011)P(0) =F(s=“01”)+P(01)P(

49、0)+P(011)P(0) =F(s=“0”)+P(0)P(0) +P(01)P(0)+P(011)P(0) =0+P(00)+P(010)+P(0110) 对应的区间宽度为 A(s1)=P(s=“011”)P(1)=P(011)P(1)=P(0111)62o 上述整个分析过程可用图8.9描述o 式(8.51)和(8.52)是可递推运算，在实际中，只需两个存储器，把P(s)和F(s)存下来，然后，根据输入符号和式(8.51)、(8.52)更新两个存储器中的数值。因此在编码过程中，每输入一个符号要进行乘法和加法运算，所以称为算算术编码术编码。63) 1 ()() 1() 1()0()()0()0

50、()0()()() 1()()0(PPPAPPPAPPFFFFsssssssssss64 通过关于信源符号序列的累积分布函数的计算，把区间分割成许多小区间，不同的信源符号序列对应不同的区间为F(s),F(s)+P(s) 。可取小区间内的一点来代表这序列。o 编码方法：将符号序列的累积分布函数写成二进位的小数，取小数点后k位，若后面有尾数，就进位到第k位，这样得到的一个数C，并使k满足o 举例 。的码字为得符号序列设整数代表大于或等于的最小kkkzzzzzzzCPk21212s,1 , 0. 0) s (1log658.58.5.4 算术编码方法。的码字为，得则110s110. 0371) s

51、(10110001. 0) s (CkPFo 编码效率n 这样选取的数值C，一般根据二进位小数截去尾数的影响，得 CF(s)Cn 而P(s)1/2kn 信源符号序列对应区间的上界为 F(s)+P(s)F(s)+1/2kCn 可见，数值在区间F(s),F(s)+P(s)内。而信源符号序列对应的不同区间（左封右开）是不重叠的，所以编得的码是即时码。66o 算术编码的编码效率很高。当信源符号序列很长时，L很大时，平均码长接近信源的熵。mLKRLSHRLKSH2log1)()(67)()(1)()(1)(log)()()()(log)()(1log222SLHSHLLSHLKLSHpPkPKPPPkL

52、LL若信源是无记忆，平均每个符号的码长为得由于ssssssssss例：设二元无记忆信源S=0,1，其P(0)=1/4，P(1)=3/4。对二元序列11111100做算术编码。解：P(s=11111100)=P2(0)P6(1)=(3/4)6(1/4)2F(sr)=F(s)+P(s)F(r)F(s0)=F(s) F(s1)=F(s)+P(s)F(1)= F(s)+P(s)P(0)F(s)=P(0)+P(1)P(0)+P(1)2P(0)+P(1)3P(0)+P(1)4P(0)+P(1)5P(0) =0.82202=0.110100100111得C0.1101010 得s的码字为1101010。编码

53、效率 7)(1log2sPk68举 例%928/7811. 0/)()(LKsHRsH) 1 () s () 1s () 1s ()0() s ()0s ()0s ()0() s () s () 1s () s ()0s (PPPAPPPAPPFFFF69举 例70一一. . 冗余编码特点及应用冗余编码特点及应用二二. . 冗余编码方法冗余编码方法三三. . L LD D编码方法编码方法四四. . L LD D译码方法译码方法五五. . 举例举例第六节第六节 冗余编码冗余编码71o 冗余位冗余位：在信源序列中，常有许多符号不携带信息，：在信源序列中，常有许多符号不携带信息，除了符号的数目或所占时长外，完全可以不传送。这除了符号的数目或所占时长外，完全可以不传送。这些符号称为冗余位。些符号称为冗余位。如语音通信中讲话的间歇；图像如语音通信中讲话的间歇；图像通信中，图像的背景基本不变，并在图像中占相当大通信中