复旦 周小林 信息论 5.信源编码

1、普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著1第第5章信源编码章信源编码 编码分为信源编码和信道编码，其中信源编码分为信源编码和信道编码，其中信源编码又分为编码又分为无失真和限失真无失真和限失真。一般称一般称u无失真信源编码定理无失真信源编码定理为第一极限定理；为第一极限定理；u信道编码定理信道编码定理（包括离散和连续信道）称为第（包括离散和连续信道）称为第 二极限定理；二极限定理；u限失真信源编码定理限失真信源编码定理称为第三极限定理。称为第三极限定理。 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著2第第5章信源编码章信源编码由于信源符号之间存在分布由于信源符

2、号之间存在分布不均匀和相关不均匀和相关性性，使得信源存在，使得信源存在冗余度冗余度，信源编码的主，信源编码的主要任务就是减少冗余，提高编码效率。要任务就是减少冗余，提高编码效率。 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著3第第5章信源编码章信源编码信源编码的基本途径有两个：信源编码的基本途径有两个：n使序列中的各个符号尽可能地互相独立，使序列中的各个符号尽可能地互相独立，即解除相关性；即解除相关性；n使编码中各个符号出现的概率尽可能地使编码中各个符号出现的概率尽可能地相等，即概率均匀化。相等，即概率均匀化。 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著4第第

3、5章信源编码章信源编码信源编码的基础是信息论中的两个编码定理：信源编码的基础是信息论中的两个编码定理：n无失真编码定理无失真编码定理n限失真编码定理限失真编码定理 无失真编码无失真编码只适用于离散信源只适用于离散信源 对于连续信源，只能在失真受限制的情况下进对于连续信源，只能在失真受限制的情况下进行行限失真编码限失真编码 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5第第5章信源编码章信源编码本章讨论本章讨论离散信源编码离散信源编码，首先从，首先从无失真编无失真编码定理码定理出发，重点讨论以出发，重点讨论以香农码香农码、费诺码费诺码和和霍夫曼码霍夫曼码为代表的最佳无失真码。然后

4、为代表的最佳无失真码。然后介绍了介绍了限失真编码定理限失真编码定理。最后简单介绍了。最后简单介绍了一些其它常用的信源编码方法。一些其它常用的信源编码方法。 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著65.1 编码的定义编码的定义信源信源编码器编码器信道信道码表码表图图5-1 信源编码器示意图信源编码器示意图普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著75.1 编码的定义编码的定义信源编码信源编码是指信源输出符号经信源编码器是指信源输出符号经信源编码器编码后转换成另外的压缩符号编码后转换成另外的压缩符号无失真信源编码无失真信源编码：可精确无失真地复制信：可精确无

5、失真地复制信源输出地消息源输出地消息普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著85.1 编码的定义编码的定义将信源消息分成若干组，即符号序列将信源消息分成若干组，即符号序列xi， xi(xi1xi2xilxiL)， xil A=a1，a2，ai，an每个符号序列每个符号序列xi依照固定码表映射成一个码字依照固定码表映射成一个码字yi， yi(yi1yi2yilyiL)， yil B=b1，b2，bi，bm这样的码称为这样的码称为分组码分组码，有时也叫块码。只有，有时也叫块码。只有分组码才有对分组码才有对应的码表应的码表，而非分组码中则不存在码表。，而非分组码中则不存在码表。

6、普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著95.1 编码的定义编码的定义如图如图5-1所示，如果信源输出符号序列长度所示，如果信源输出符号序列长度L1，信源符号集信源符号集A(a1，a2，an)信源概率空间为信源概率空间为 )()()(2121nnapapapaaaPX若将信源若将信源X通过二元信道传输，就必须把信源符通过二元信道传输，就必须把信源符号号ai变换成由变换成由0，1符号组成的码符号序列，这个符号组成的码符号序列，这个过程就是信源编码过程就是信源编码 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著105.1 编码的定义编码的定义码可分为两类：码可分为

7、两类：一、固定长度的码，码中所有码字的长度一、固定长度的码，码中所有码字的长度 都相同，如表都相同，如表5-1中的码中的码1就是就是定长码定长码二、可变长度码，码中的码字长短不一，二、可变长度码，码中的码字长短不一，如表中码如表中码2就是就是变长码变长码。 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著115.1 编码的定义编码的定义不同的码符号序列，如表不同的码符号序列，如表5-1所示。所示。 表表5-1 变长码与定长码变长码与定长码信源信源符号符号ai信源符号出信源符号出现概率现概率p(ai)码表码表码码1码码2a1p(a1)000a2p(a2)0101a3p(a3)1000

8、1a4p(a4)11111普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著125.1 编码的定义编码的定义（1）奇异码和非奇异码）奇异码和非奇异码 若信源符号和码字是若信源符号和码字是一一对应一一对应的，则该的，则该码为码为非奇异码非奇异码。反之为奇异码。反之为奇异码。 如表如表5-2中的码中的码1是奇异码，码是奇异码，码2是非奇异是非奇异码。码。 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著135.1 编码的定义编码的定义表表5-2 码的不同属性码的不同属性信源符号信源符号ai符号出现概率符号出现概率p(ai)码码1码码2码码3码码4a11/20011a21/41

9、1101001a31/80000100001a41/8110110000001普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著145.1 编码的定义编码的定义（2）唯一可译码唯一可译码 任意有限长的码元序列，只能被唯一地任意有限长的码元序列，只能被唯一地分割成一个个的码字，便称为唯一可译分割成一个个的码字，便称为唯一可译码码 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著155.1 编码的定义编码的定义唯一可译码中又分为唯一可译码中又分为非即时码非即时码和和即时码即时码：如果接收端收到一个完整的码字后，不能如果接收端收到一个完整的码字后，不能立即译码，还需等下一个码字

10、开始接收后立即译码，还需等下一个码字开始接收后才能判断是否可以译码，这样的码叫做才能判断是否可以译码，这样的码叫做非非即时码。即时码。普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著165.1 编码的定义编码的定义即时码即时码：只要收到符号就表示该码字已完：只要收到符号就表示该码字已完整，可以立即译码。整，可以立即译码。即时码又称为即时码又称为非延长码非延长码，任意一个码字都，任意一个码字都不是其它码字的前缀部分，有时叫做不是其它码字的前缀部分，有时叫做异前异前缀码缀码。 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著175.1 编码的定义编码的定义码码奇异码奇异码非

11、分组码非分组码分组码分组码非奇异码非奇异码非唯一可译码非唯一可译码非即时码非即时码即时码即时码(非延长码非延长码)唯一可译码唯一可译码普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著185.1 编码的定义编码的定义通常可用通常可用码树码树来表示各码字的构成来表示各码字的构成 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1二进制码树二进制码树普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著195.1 编码的定义编码的定义 0 1 2 0 1 2 0 1 2 0 1 20 1 20 1 2三进制码树三进

12、制码树普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著205.1 编码的定义编码的定义唯一可译码唯一可译码存在存在的充分和必要条件的充分和必要条件 各码字的长度各码字的长度Ki 应符合应符合克劳夫特不等式克劳夫特不等式： 11niKim普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著215.1 编码的定义编码的定义例例：设二进制码树中设二进制码树中X (a1， a2 ， a3 ， a4 )，K11，K22，K32，K43，应用上述判断定理：应用上述判断定理： 18922222322141iKi因此不存在满足这种因此不存在满足这种Ki的唯一可译码的唯一可译码。 普通高等教

13、育“十五”国家级规划教材信息论与编码 曹雪虹等编著225.1 编码的定义编码的定义a1=1 0 1 0 1 0 1a2=01a3=011a4=0001，01，001，000 惟一可译码；惟一可译码；1，01，101，000 不是惟一可译码；不是惟一可译码；均满足克劳夫特不等式均满足克劳夫特不等式122222332141iKi普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著235.1 编码的定义编码的定义克劳夫特不等式克劳夫特不等式只是用来说明唯一可译码只是用来说明唯一可译码是否是否存存在，并不能作为唯一可译码的判据。在，并不能作为唯一可译码的判据。 普通高等教育“十五”国家级规划教

14、材信息论与编码 曹雪虹等编著245.2 5.2 无失真信源编码无失真信源编码信源输出信源输出X(X1X2XlXL)，Xl a1，a2，ai，an编码为编码为Y(Y1Y2Yk YkL)，Yk b1，b2，bj，bm。要求能够要求能够无失真或无差错无失真或无差错地译码，同时传地译码，同时传送送Y时所需要的时所需要的信息率最小信息率最小 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著255.2 5.2 无失真信源编码无失真信源编码Yk平均每个符号平均每个符号的最大信息量为的最大信息量为log mKL长码字的最大信息量为长码字的最大信息量为KLlog m则传送一个信源符号需要的信息率平均

15、为则传送一个信源符号需要的信息率平均为 MLmLKKLlog1logLKmM 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著265.2 5.2 无失真信源编码无失真信源编码所谓所谓信息率最小信息率最小，就是找到一种编码方，就是找到一种编码方式使式使 最小。最小。无失真信源编码无失真信源编码定理研究的内容定理研究的内容: :最小信息率为多少时，才能得到无失真最小信息率为多少时，才能得到无失真的译码？若小于这个信息率是否还能无的译码？若小于这个信息率是否还能无失真地译码失真地译码 K普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著275.2 5.2 无失真信源编码无失真信

16、源编码无失真的信源编码定理无失真的信源编码定理n定长定长编码定理编码定理n变长变长编码定理编码定理 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著285.2 5.2 无失真信源编码无失真信源编码n定长定长编码定理编码定理K是定值是定值 且惟一可译码且惟一可译码普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著295.2 5.2 无失真信源编码无失真信源编码由由L个符号组成的、每个符号的熵为个符号组成的、每个符号的熵为HL(X)的无记的无记忆平稳信源符号序列忆平稳信源符号序列X1X2XlXL，可用，可用KL个符个符号号Y1，Y2，Yk，（每个符号有，（每个符号有m种可能种

17、可能值）进行值）进行定长编码定长编码。对任意。对任意 0， 0，只要，只要则当则当L足够大时，必可使译码差错小于足够大时，必可使译码差错小于 ；反之，当反之，当 时，译码差错一时，译码差错一定是有限值，而定是有限值，而L足够大时，译码几乎必定出错足够大时，译码几乎必定出错 )(logXLLHmLK2)(logXLLHmLK普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著305.2 5.2 无失真信源编码无失真信源编码定长编码定理说明，定长编码定理说明，)()(logXXHLHmKLL码字所能携带的信息量码字所能携带的信息量大于大于信源序列输出信源序列输出的信息量，则可以使传输几乎无

18、失真，当的信息量，则可以使传输几乎无失真，当然条件是然条件是L L足够大足够大。 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著315.2 5.2 无失真信源编码无失真信源编码反之，当反之，当 时，不可能构成无失时，不可能构成无失真的编码，也就是不可能做一种编码器，真的编码，也就是不可能做一种编码器，能使收端译码时差错概率趋于零。能使收端译码时差错概率趋于零。 时，则为临界状态，可能无失真，时，则为临界状态，可能无失真，也可能有失真。也可能有失真。)(XLHK )(XLHK 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著325.2 5.2 无失真信源编码无失真信源编

19、码式中式中 为自信息方差为自信息方差 为一正数。当为一正数。当 和和 均为定值时，只要均为定值时，只要L足够大，足够大，Pe可以小于任一正数可以小于任一正数 。即，。即， 22)(LPeX)()()(22XxXHIEi)(2X222)(LX普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著335.2 5.2 无失真信源编码无失真信源编码当信源序列长度当信源序列长度L满足满足 时，时，能达到差错率要求能达到差错率要求 22)(XL22)(LPeX普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著345.2 5.2 无失真信源编码无失真信源编码在在连续信源连续信源的情况下，由于

20、信源的的情况下，由于信源的信息量信息量趋于无限趋于无限，显然不能用离散符号序列，显然不能用离散符号序列Y来来完成无失真编码，而只能进行完成无失真编码，而只能进行限失真编码限失真编码。普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著355.2 5.2 无失真信源编码无失真信源编码定义定义为为编码效率编码效率，即信源的平均符号熵为，即信源的平均符号熵为H(X)，采用平均符号码长为采用平均符号码长为 来编码，所得的效来编码，所得的效率。率。编码效率总是小于编码效率总是小于1，且最佳编码效率为，且最佳编码效率为 KHL)(XK0,)()(XXLLHH普通高等教育“十五”国家级规划教材信息论

21、与编码 曹雪虹等编著365.2 5.2 无失真信源编码无失真信源编码编码定理从理论上阐明了编码效率接近编码定理从理论上阐明了编码效率接近1的理想编码器的存在性，它使输出符号的的理想编码器的存在性，它使输出符号的信息率与信源熵之比接近于信息率与信源熵之比接近于1，即，即 L取无限长取无限长1log)(mLKHLLX普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著375.2 5.2 无失真信源编码无失真信源编码例例设离散无记忆信源概率空间为设离散无记忆信源概率空间为 比特比特/符号符号 04. 005. 006. 007. 01 . 01 . 018. 04 . 087654321aa

22、aaaaaaPX55. 2log)(81iiippXH普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著385.2 5.2 无失真信源编码无失真信源编码对信源符号采用对信源符号采用定长定长二元编码，要求编码二元编码，要求编码效率为效率为 90，若取，若取L1，则可算出，则可算出2.55 90%=2.8比特比特/符号符号Pe0.04 太大太大K普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著395.2 5.2 无失真信源编码无失真信源编码28. 0,90. 0)()(XHXH228122)(82. 7)()(log)()(bitXHppxIDXiiii若要求译码错误概率若要

23、求译码错误概率 61087622210108 . 91028. 082. 7)(XL普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著405.2 5.2 无失真信源编码无失真信源编码变长变长编码定理编码定理在变长编码中，码长在变长编码中，码长K是变化的是变化的根据信源各个符号的统计特性，如根据信源各个符号的统计特性，如概率大概率大的符号用短码，概率小的用较长的码的符号用短码，概率小的用较长的码，使，使得编码后平均码长降低，从而提高编码效得编码后平均码长降低，从而提高编码效率。（统计匹配）率。（统计匹配）普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著415.2 5.2 无

24、失真信源编码无失真信源编码单个符号单个符号变长编码定理：若离散无记忆信变长编码定理：若离散无记忆信源的符号熵为源的符号熵为H(X)，每个信源符号用，每个信源符号用m进进制码元进行变长编码，一定存在一种无失制码元进行变长编码，一定存在一种无失真编码方法，其码字平均长度满足下列不真编码方法，其码字平均长度满足下列不等式等式1log)(log)(mXHKmXH普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著425.2 5.2 无失真信源编码无失真信源编码 离散平稳无记忆序列离散平稳无记忆序列变长编码定理：对于变长编码定理：对于平均符号熵为平均符号熵为HL(X)的离散平稳无记忆信源，的离散

25、平稳无记忆信源，必存在一种无失真编码方法，使平均信息必存在一种无失真编码方法，使平均信息率满足不等式率满足不等式其中其中 为任意小正数。为任意小正数。)()(XXLLHKH普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著435.2 5.2 无失真信源编码无失真信源编码用变长编码来达到相当高的编码效率，一用变长编码来达到相当高的编码效率，一般所要求的符号长度般所要求的符号长度L可以比定长编码小可以比定长编码小得多。得多。 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著445.2 5.2 无失真信源编码无失真信源编码编码效率总是小于编码效率总是小于1 1，可以用它来衡量各

26、种，可以用它来衡量各种编码方法的优劣。编码方法的优劣。为了衡量各种编码方法与为了衡量各种编码方法与最佳码最佳码的差距，的差距，定义码的剩余度为定义码的剩余度为 KXHmLKXHLLL)(1log)(11普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著455.2 5.2 无失真信源编码无失真信源编码例例设离散无记忆信源的概率空间为设离散无记忆信源的概率空间为414321aaPX普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著465.2 5.2 无失真信源编码无失真信源编码符号/811. 034log434log41)(bitXH若用二元定长编码若用二元定长编码(0，1)来

27、构造一个即来构造一个即时码：时码： 。平均码长平均码长 1二元码符号二元码符号/信源符号信源符号1,021aaK普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著475.2 5.2 无失真信源编码无失真信源编码编码效率为编码效率为811. 0)(KXH输出的信息效率为输出的信息效率为R0.811比特比特/二元码符号二元码符号普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著485.2 5.2 无失真信源编码无失真信源编码长度为长度为2的信源序列进行的信源序列进行变长编码变长编码（编码方（编码方法后面介绍），其即时码如下表法后面介绍），其即时码如下表 aip(ai)即时码a1

28、a19/160a1a23/1610a2a13/16110a2a21/16111普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著495.2 5.2 无失真信源编码无失真信源编码322722KK162731613163216311692K二元码符号二元码符号/信源序列信源序列二元码符号二元码符号/信源符号信源符号普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著505.2 5.2 无失真信源编码无失真信源编码961. 027811. 0322编码效率编码效率信息效率信息效率R20.961比特比特/二元码符号二元码符号 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编

29、著515.2 5.2 无失真信源编码无失真信源编码L3 R30.985比特比特/二元码符号二元码符号 L4 R40.991比特比特/二元码符号二元码符号 985. 03991. 04普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著525.2 5.2 无失真信源编码无失真信源编码定长二元码编码，要求编码效率达到定长二元码编码，要求编码效率达到96时，允许译码错误概率时，允许译码错误概率 510222122)(4715. 0)()(log)(bitXHppXiii752221013. 41004. 0)96. 0()811. 0(4715. 0L普通高等教育“十五”国家级规划教材信息论

30、与编码 曹雪虹等编著535.2 5.2 无失真信源编码无失真信源编码最佳变长编码最佳变长编码 凡是能载荷一定的信息量，且码字的平均凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合称长度最短，可分离的变长码的码字集合称为为最佳变长码最佳变长码。 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著545.2 5.2 无失真信源编码无失真信源编码能能获得最佳码的编码方法主要有：获得最佳码的编码方法主要有：n香农（香农（Shannon）n费诺（费诺（Fano）n哈夫曼（哈夫曼（Huffman）等）等 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著555.2

31、 5.2 无失真信源编码无失真信源编码香农香农（Shannon）编码）编码n将信源消息符号按其出现的概率大小依将信源消息符号按其出现的概率大小依次排列次排列n确定满足下列不等式的整数码长确定满足下列不等式的整数码长Ki。nppp211loglog22iiipKp普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著565.2 5.2 无失真信源编码无失真信源编码3.为了编成唯一可译码，计算第为了编成唯一可译码，计算第i个消息个消息的累加概率的累加概率4.将累加概率将累加概率Pi变换成二进制数。变换成二进制数。5.取取Pi二进数的小数点后二进数的小数点后Ki位即为该消息位即为该消息符号的二

32、进制码字。符号的二进制码字。 11ikkiapP普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著575.2 5.2 无失真信源编码无失真信源编码例例 设信源共设信源共7个符号消息，其概率和累加个符号消息，其概率和累加概率如下表所示。概率如下表所示。 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著585.2 5.2 无失真信源编码无失真信源编码信源消息信源消息符号符号ai符号概符号概率率(ai)累加概累加概率率Pi-log p(ai)码字长码字长度度Ki码字码字a10.2002.323000a20.190.22.393001a30.180.392.473011a40.1

33、70.572.563100a50.150.742.743101a60.100.893.3241110a70.010.996.6471111110普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著59十进制小数二进制小数 方法：“乘2取整”对十进制小数乘2得到的整数部分和小数部分,整数部分既是相应的二进制数码,再用2乘小数部分(之前乘后得到新的小数部分),又得到整数和小数部分.如此不断重复,直到小数部分为0或达到精度要求为止.第一次所得到为最高位,最后一次得到为最低位如:0.25的二进制0.25*2=0.5 取整是00.5*2=1.0 取整是1即0.25的二进制为 0.01 ( 第一次

34、所得到为最高位,最后一次得到为最低位)0.8125的二进制0.8125*2=1.625 取整是10.625*2=1.25 取整是10.25*2=0.5 取整是00.5*2=1.0 取整是1即0.8125的二进制是0.1101（第一次所得到为最高位,最后一次得到为最低位）普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著605.2 5.2 无失真信源编码无失真信源编码14. 3)(71iiiKapK码元码元/符号符号831. 014. 361. 2)(KXHR比特比特/码元码元 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著615.2 5.2 无失真信源编码无失真信源编码

35、费诺费诺编码方法编码方法费诺编码属于概率匹配编码费诺编码属于概率匹配编码(1)将信源消息符号按其出现的概率大小依将信源消息符号按其出现的概率大小依次排列：次排列： 。(2)将依次排列的信源符号按概率值分为两将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近于相同，大组，使两个组的概率之和近于相同，并对各组赋予一个二进制码元并对各组赋予一个二进制码元“0”和和“1”。nppp21普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著625.2 5.2 无失真信源编码无失真信源编码(3)将每一大组的信源符号进一步再分成两将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率之

36、和近于组，使划分后的两个组的概率之和近于相同，并又赋予两个组一个二进制符号相同，并又赋予两个组一个二进制符号“0”和和“1”。(4)如此重复，直至每个组只剩下一个信源如此重复，直至每个组只剩下一个信源符号为止。符号为止。(5)信源符号所对应的码字即为费诺码。信源符号所对应的码字即为费诺码。普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著635.2 5.2 无失真信源编码无失真信源编码例例 对以下信源进行费诺编码对以下信源进行费诺编码。 消息符消息符号号ai各 个 消各 个 消息概率息概率 p(ai)第一次第一次分组分组第二次第二次分组分组第三次第三次分组分组第四次第四次分组分组二元

37、二元码字码字码长码长Kia10.2000002a20.19100103a30.1810113a40.1710102a50.15101103a60.101011104a70.01111114普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著645.2 5.2 无失真信源编码无失真信源编码74. 2)(71iiiKapK953. 074. 261. 2)(KXHR 码元码元/符号符号 bit/符号符号 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著655.2 5.2 无失真信源编码无失真信源编码 哈夫曼哈夫曼编码方法编码方法(1)将信源消息符号按其出现的概率大小依将信源消息

38、符号按其出现的概率大小依次排列，次排列，(2)取两个概率最小的字母分别配以取两个概率最小的字母分别配以0和和1两两个码元，并将这两个概率相加作为一个个码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进符号的新字母的概率，与未分配的二进符号的字母重新排队。字母重新排队。nppp21普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著665.2 5.2 无失真信源编码无失真信源编码(3)对重排后的两个概率最小符号重复步骤对重排后的两个概率最小符号重复步骤(2)的过程。的过程。(4)不断继续上述过程，直到最后两个符号不断继续上述过程，直到最后两个符号配以配以0和和1为止。为止。(5

39、)从最后一级开始，向前返回得到各个信从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码源符号所对应的码元序列，即相应的码字。字。2022年4月18日星期一67例 1-3-1考虑离散信源DMS具有发生的概率如图(1-3-4)说明的七个可能的符号x1,x2,x7我们安排信源符号的次序以符号发生概率递降为序 p(x1)p(x2),p(x7)2022年4月18日星期一68从最后二个可能符号x6、x7开始讨论他的编码过程这二个符号如图所示索搏在一起，上边支路为“0”，下边支路为“1”。 字符概率自信息码x10.351.514600 x20.301.737001x30.202.32191

40、0 x40.103.3219110 x50.044.64391110 x60.0057.643911110 x70.0057.643911111H(x)=2.11 R 221.普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著695.2 5.2 无失真信源编码无失真信源编码例例 对以下信源进行哈夫曼编码对以下信源进行哈夫曼编码 信源符号信源符号ai概率概率p(ai) 码字码字Wi码长码长Kia10.20102a20.19112a30.180003a40.170013a50.150103a60.1001104a70.0101114普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等

41、编著705.2 5.2 无失真信源编码无失真信源编码0.20 0.20 0.26 0.35 0.39 0.61 1.00.19 0.19 0.20 0.26 0.35 0.390.18 0.18 0.19 0.20 0.260.17 0.17 0.18 0.190.15 0.15 0.170.10 0.110.01010101010101普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著715.2 5.2 无失真信源编码无失真信源编码 码元码元/符号符号 bit/符号符号 72. 2)(71iiiKapK96. 072. 261. 2)(KXHR普通高等教育“十五”国家级规划教材信息

42、论与编码 曹雪虹等编著725.2 5.2 无失真信源编码无失真信源编码哈夫曼编码方法得到的码并非唯一的哈夫曼编码方法得到的码并非唯一的n每次对信源缩减时，赋予信源最后两个每次对信源缩减时，赋予信源最后两个概率最小的符号，用概率最小的符号，用0和和1是可以任意的，是可以任意的，所以可以得到不同的哈夫曼码，但不会所以可以得到不同的哈夫曼码，但不会影响码字的长度。影响码字的长度。普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著735.2 5.2 无失真信源编码无失真信源编码n对信源进行缩减时，两个概率最小的符对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率号合并后的概

43、率与其它信源符号的概率相同时，这两者在缩减信源中进行概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响故会得到不同的哈夫曼码。此时将影响码字的长度，一般将码字的长度，一般将合并的概率放在上合并的概率放在上面面，这样可获得，这样可获得较小的码方差较小的码方差。普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著745.2 5.2 无失真信源编码无失真信源编码例例 设有离散无记忆信源设有离散无记忆信源1 . 01 . 02 . 02 . 04 . 054321aaaaaPX普通高等教育“十五”国家级规

44、划教材信息论与编码 曹雪虹等编著755.2 5.2 无失真信源编码无失真信源编码信源符号信源符号ai概率概率p(ai)码字码字Wi1码长码长Ki1码字码字Wi2码长码长Ki2a10.411002a20.2012102a30.20003112a40.1001040103a50.1001140113普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著765.2 5.2 无失真信源编码无失真信源编码0.4 0.4 0.4 0.6 1.0 0.2 0.2 0.4 0.40.2 0.2 0.20.1 0.2 0.10.4 0.4 0.4 0.6 1.0 0.2 0.2 0.4 0.40.2 0.

45、2 0.20.1 0.20.10101010101010101普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著775.2 5.2 无失真信源编码无失真信源编码2 . 2)(71iiiKapK 码元码元/符号符号 965. 0)(KXH普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著785.2 5.2 无失真信源编码无失真信源编码qiiiilKkapKkE1222)(36. 121l16. 022l普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著795.2 5.2 无失真信源编码无失真信源编码 进行哈夫曼编码时，为得到进行哈夫曼编码时，为得到码方差码方差最小的

46、最小的码，应使合并的信源符号位于缩减信源序码，应使合并的信源符号位于缩减信源序列列尽可能高的位置尽可能高的位置上，以减少再次合并的上，以减少再次合并的次数，充分利用短码。次数，充分利用短码。 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著805.2 5.2 无失真信源编码无失真信源编码哈夫曼码是用哈夫曼码是用概率匹配概率匹配方法进行信源编码。方法进行信源编码。n哈夫曼码的编码方法保证了概率大的符哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长号对应于短码，概率小的符号对应于长码，充分利用了短码；码，充分利用了短码；n缩减信源的最后二个码字总是最后一位缩减信源的

47、最后二个码字总是最后一位不同，从而保证了不同，从而保证了哈夫曼码是即时码哈夫曼码是即时码。普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著815.3 限失真信源编码定理限失真信源编码定理 信息率失真函数给出了失真小于D时所必须具有的最小信息率R(D)；只要信息率大于R(D)，一定可以找到一种编码，使译码后的失真小于D。 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著825.3 限失真信源编码定理限失真信源编码定理限失真信源编码定理：设离散无记忆信源X的信息率失真函数R(D)，则当信息率RR(D)，只要信源序列长度L足够长，一定存在一种编码方法，其译码失真小于或等于D，

48、为任意小的正数。反之，若RR(D)，则无论采用什么样的编码方法，其译码失真必大于D。普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著835.3 限失真信源编码定理限失真信源编码定理如果是二元信源，对于任意小的，每一个信源符号的平均码长满足如下公式 )()(DRKDR普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著845.3 限失真信源编码定理限失真信源编码定理在失真限度内使信息率任意接近R(D)的编码方法存在。然而，要使信息率小于R(D)，平均失真一定会超过失真限度D。对于连续平稳无记忆信源，无法进行无失真编码，在限失真情况下，有与上述定理一样的编码定理。普通高等教育“

49、十五”国家级规划教材信息论与编码 曹雪虹等编著855.3 限失真信源编码定理限失真信源编码定理限失真信源编码定理只能说明最佳编码是存在的，而具体构造编码方法却一无所知。因而就不能象无损编码那样从证明过程中引出概率匹配的编码方法。一般只能从优化的思路去求最佳编码。实际上迄今尚无合适的可实现的编码方法可接近R(D)这个界。 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著865.4 常用信源编码方法简介常用信源编码方法简介n游程编码 在二元序列中，连0段称为0游程 连1段称为1游程000101110010001 可变换成下列游程序列：3113213 普通高等教育“十五”国家级规划教材信

50、息论与编码 曹雪虹等编著875.4 常用信源编码方法简介常用信源编码方法简介若已知二元序列以0起始，从游程序列很容易恢复成原来的二元序列 游程序列是多元序列，各长度可按霍夫曼编码或其它方法处理以达到压缩码率的目的。 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著885.4 常用信源编码方法简介常用信源编码方法简介n多元序列也存在相应的游程序列 n多元序列变换成游程序列再进行压缩编码没有多大意义 n游程编码只适用于二元序列，对于多元信源，一般不能直接利用游程编码 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著895.4 常用信源编码方法简介常用信源编码方法简介n冗余位

51、编码，游程编码在多元信源的应用普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著905.4 常用信源编码方法简介常用信源编码方法简介如下多元序列x1，x2，xm1，y，y，y，x m1+1，xm1+2，x m2，y，y， 可以用下面序列表示 111，100，000111，111000 x1，x2，xm1，x m1+1，x m1+2x 2， 1表示信息位，0表示冗余位 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著915.4 常用信源编码方法简介常用信源编码方法简介n算术编码 非分组码的编码方法之一算术码普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著925.

52、4 常用信源编码方法简介常用信源编码方法简介符号概率与积累概率的递推关系0)()() 1 ,()()0 ,(1 , 0,)()(),(PSpSPSPSPSPrPSpSPrSPr普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著935.4 常用信源编码方法简介常用信源编码方法简介采用累积概率P(S)表示码字C(S)，符号概率p(S)表示状态区间A(S) rrpSASrAPSASCSrC)()()()()(普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著945.4 常用信源编码方法简介常用信源编码方法简介P(S)把区间0，1)分割成许多小区间，每个小区间的长度等于各序列的概率p(S)，小区间内的任一点可用来代表这序列 0(P1) P2 P3 P4 P5 1 p1 p2 p3 p4 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著955.4 常用信源编码方法简介常用信源编码方法简介 0(P1) P2 P3 P4 P5 1 p1 p2 p3 p4 )