第五章无失真编码2

1、无失真信源编码无失真信源编码n无失真编码概述n定长信源编码n变长信源编码n实用的无失真信源编码方法举例5.1无失真编码器1离散、无失真、无记忆信源编码的一般模型：总码组合数：1()qSSS1()CCCr总组合数：qNlr入出信源编码有q个源字母有r个码字母5.1无失真编码器2n问题问题：能否进行无失真编码，怎样进行无失真编码若：不考虑信源统计特性：n应满足条件应满足条件： 相互矛盾！ NlNlrr无失真：q有效：qloglogNllqqrNr由结论结论：当q=r时，lN不有效。当l=N时，rq，亦不满足有效性解决办法解决办法：引入信源统计特性。l l5.1无失真编码器3n考察无失真条件考察无失

2、真条件： 分别表示等概条件下的消息熵 与码字熵 之比， 考虑信源的实际统计特性（非等概），实际消息熵为： 代入无失真条件得： 此时：即使q=r,只要 就有可能实现l0,0，只要满足： (l/N)log rH(S)+ 则：当N足够大时，可使译码差错小于， 反之，当 (l/N)logrH(S)-2 时，译码一定出错。解释：定长编码定理给出了信源进行等长编码所需码长的理论极限值。 5.3定长编码定理2-进一步理解n若要求变得的等长码是唯一可译的，则必须：n若N1，则：n结论结论：对于唯一可译码，每个信源符号至少需要用 个码符号来变换。n当采用二元码编码时，r2，则：n结论结论：对信源进行二元等长编码

3、时，每个信源符号所需码长的极限值为 loglogqrloglogqNr1loglog ()Nlqlq bitN log ()q bitloglogNllqqrNr例1：英文电报有32个符号（266），即q=32， 若r=2，N1（即对信源的逐个符号进行二元编码）， 则：解释：每个英文电报符号至少需要用5位二元符号编码问题：第三章：在考虑符号出现的概率和符号间相关性前提下,每个英文符 号平均携带的信息量是1.4bit/符号（ ），5bit/符号， 等长编码效率极低，如何提高效率？如何体现有效性？loglog325lqBit/符号bitH4 . 1解决方法：考察：字母个数为n，字母出现非等概，且字

4、母之间相关长度为L的英文信源，其可能的字母序列总数为 ；但其中大部分字母序列是无意义的字母组合，而且随着N的增加，这种无意义序列的总数越来越大。方法：进行联合编码，即对字母序列编码，且只对哪些有意义的字母序列编码，即需编码的字母序列的总数 ,则平均每个信源符号所需的码符号个数可以大大减少，从而提高了传输效率。问题：会引入一定的误差，当N足够长后，误差可以任意小。NqNq5.3定长编码定理3证明n考察离散、随机序列信源的统计特性 渐进等分割性（AEP）nAEP描述： 渐进等分割定理：渐进等分割定理： （熵定理，遍历性定理） 设 是离散无记忆信源输出的一个特定序列，则任给 和 ，总可以找到一个整数

5、 ，使当 时，有：Nssss.21000N0NN 1| )(|)(logSHPNsP引入：渐进等分割性（引入：渐进等分割性（AEP）5.3定长编码定理4 AEP物理意义任何一个离散随机序列信源当序列长度时,信源序列会产生两极分化.大概率事件集合 与小概率事件集合 n对于 有性质: (信源熵) (大概率事件熵) (等概率) n对于 有性质: 由此可见，信源编码只需对信源中少数少数落入典型大概率事件的集合的符号进行编码即可 。 而 对大 多 数大 多 数属 于 非 典 型 小 概 率 事 件 集 合 中 的 信 源 符 号 无 需 编 码 ,且 。 AAA1)A(pLimL121(,)()kMnH

6、 PPPH PPM/1PPM1A0)A(pLimL0)(AP信源序列集合AALS5.3定长编码定理5 AEP证明n集合 和 中的序列分别称为 典型序列和 非典型序列n可以证明：对于任意小的正数 ， ，当N足够大时，n 表示 中所有 典型序列的集合n 表示 集合中序列的个数个数n还可以证明：对于任意小的正数 ， ，当N足够大时，n 表示序列 出现的概率n由切比雪夫不等式可得：n 表示S中每个符号携带的信息量的n 方差 AA00( )( )(1)2| 2N H SN H SAA|ANSA0Ai ( ) ( )2( ) 2N H SN H SiP)(iPi2( ) 1NP A 2nAEP结论：当L足

7、够大时，n所有 典型序列出现的概率近似相等，即 典型序列为渐进等概序列n可粗略认为 典型序列出现的概率为n所有 典型序列的概率和接近为1，即nAEP应用：n提出、证明都是基于离散无记忆序列信源 n平稳遍历信源有类似结果n体现信源统计特性n用以证明定长编码定理1)(Ap( )2NH S5.3定长编码定理5 证明n定长编码定理证明思路：n将取自S，长为N的信源符号序列分为集合 和n只对集合 中的序列进行一一对应的等长编码n此时的误差为 ，计算误差n可见当 ，且 (K/L)log mH(S)+ 时，n几个概念：n编码信息率： （编码后后平均每个信源符号能载荷的最大信息率）n编码效率： （编码前后前后

8、平均每个信源符号能载荷的最大信息率之比）AAA)(APPE0EPNloglNRrRSH)(22P eN5.3定长编码定理6（物理意义）n结论：n可推广至离散、非平稳无记忆信源和有记忆信源情况n只要码字传输的信息量大于信源序列携带的信息量，总可以实现几乎无失真编码(l/N)logrH(S)+( )logH SlNr二元码时，r2：( )( )( )( )llNNH SlNH SH SH SRl最佳等长码时：5.3定长编码定理7（实际应用问题）n编译码同步问题n问题：如何使译码端知道码字起点n解决办法：1、每个码字加短同步前缀 2、每若干码字加较长同步前缀n分组长度与编译码复杂性、编译码延时等等关

9、系n问题：要实现有效，源序列分组很长，使得编译码 复杂性和延时增加n解决办法：目前没有理想到解决办法n定长信源编码的理论意义远大于其实用价值5.3定长编码定理8（举例)例2：设有一简单离散信源：q=2对其进行近似于无失真的等长编码，若要求其编码效率为96%，差错率低于10-5，试求符号联合编码长度N=？解： 由编码效率：即： 再由:可见,信源序列长度需要4100万个符号,才能达到上述要求,这显然是不现实的.一般来说：当一般来说：当N有限时，高传输效率的等长码往往要引入一定的失真和错误，它不有限时，高传输效率的等长码往往要引入一定的失真和错误，它不能象变长编码那样可以实现真正的无失真编码能象变长

10、编码那样可以实现真正的无失真编码信源符号）/(811. 0log)(21bitppSHiii%96)()(SHSH034.096.096.0811.0811.022722520.47154.1 10(0.034)10PNNP4715. 0)(log221)(22SHppiii412431sspS5.4变长信源编码n几个码类的概念(4)n非奇异码（奇异码、单义码）n唯一可译码n前缀码（即时码、非延长码、异前置码）n最佳码（紧致码）nKraft定理n唯一可译码存在定理n变长编码定理（香农第一定理）5.4变长信源编码-1(Kraft定理)n引出n码树nKraft定理描述nKraft定理证明略5.4变

11、长信源编码-2(Kraft定理引出)n问题：寻求实时唯一可译码n方法：研究实时唯一可译码的码字可分离条件n引入：“码树”概念（直观）n结论：通过Kraft定理给出实时唯一可译码（前缀码）存在 的条件码树变长码的树图表示将变长码与码树建立“一一对应”关系：树根码字起点树枝数码的进制数节点码字或码字的一部分终止节点码字节数码长非满树变长码满树等长码 5.4变长信源编码-3(Kraft定理)n问题：n比较简单信源，码树方法可直接且直观构造前缀码n较复杂信源，直接画码树复杂且困难n解决方法：n为分析起来特别对含有很多符号种类的复杂信源更方便寻找一种与上述“树图”等效的解析式表达式-Kraft不等式不等

12、式。n结论： nKraft定理给出码字可分离或前缀码存在的充要条件5.4变长信源编码-4(Kraft定理)n定理：长度为li（i=1,2,n）的r （码字母表长度）进制前缀码存在的充要条件为：n证明：略n物理意义：n给定信源个数q和码字数r，只要允许码字长度可以足够长，就总可以满足Kraft不等式，从而得到前缀码11inlir5.4变长信源编码-5(唯一可译码定理)nKraft不等式给出的限制也是所有唯一可译码都必须满足的。n定理描述：n任何唯一可译码均满足Kraft不等式。n结论：n对任何唯一可译码均可在不改变码字长度的条件下得到相应的前缀码5.4变长编码定理6n问题：n对于已知信源S可用码

13、符号X进行变长编码，而且对同一信源编成同一码符号的前缀码或惟一可译码可有许多种。究竟哪一种最好呢?从高速度传输信息的观点来考虑，当然希望选择由短的码符号组成的码字，就是用码长作为选择准则。n引入：码的平均长度。 离散无记忆平稳信源 信源熵率为 码字母表个数为r， 则前缀码平均码长： ninipppsSsSsSPS11)(SH1( )riiill p a5.4变长编码定理7n无失真变长信源编码定理(即香农第一定理) ：n 离散无记忆平稳信源S，其熵率为 ，并有码符号X=x1,xr。对信源S进行编码,总可以找到一种编码方法，构成惟一可译码，使信源S中每个信源符号所需的平均码长满足: 另一方面,必可

14、以找到前缀码，使其平均码长满足 )(SH( )logHSrl( )log1HSrl5.4变长编码定理8n定理证明略n物理意义：n又称无噪信道编码定理n编码后的码符号信源尽可能为等概分布，使每个码符号平均所含的信息量达到最大n要做到无失真编码，变换每个信源符号平均所需最少的r元码元数就是信源的熵率（以r进制信息量单位测度）n信源的熵率是描述信源每个符号平均所需最少的比特数n定理说明：n是存在性定理具有理论指导意义n是构造性定理设计出多种具体编码方法5.4变长编码定理9编码效率n变长码编码效率：衡量各种编码方法的优略，判断是否最佳码。 编码前平均每个信源符号携带的信息量为： 编码后平均每个信源符号

15、携带的最大的信息量为： 定义变长码编码效率为：n另一种理解： 最佳码（极限时）每个信源符号的平均码长为： 某一方法得到的每个信源符号的平均码长为： 定义变长码编码效率为：loglr( )( )logrHSHSlrl)(SH( )log( )HSrrlHSl( )rHSlll比较：n定长编码的编码效率：n变长编码的编码效率：注意到： 是指每个信源符号所需的平均码长，而 也是平均到每个信源符号的码长，所以它们是一致的，均表示无失真信源编码的效率。( )( )( )logrlNNHSH SH SRlr( )( )logrHSHSlrlllNn例4：p160例4.4一离散无记忆信源412431sspS

16、其熵为：信源符号）比特/(811.0log4log)(344341SH用二元符号（0，1；r=2）构造一个前缀码：1,021ss此时每个信源符号平均码长为：1l ()0 .8 1 1HSl编码效率为：为提高编码效率，对S的2次扩展信源进行2维联合编码：构造一个扩展信源S2的前缀码：前缀码 s1s2 9/16 0 s1s23/16 10 s1s2 3/16110 s1s2 1/16111i)(iP此时平均码长为：2 721 6l此时信源S中每个符号对应的平均码长为：2 72 71 63 22l 编码效率为：()20 .9 6 1HSl同样可得：()30 .9 8 5HSl()40 .9 9 1H

17、Sl定长编码与变长编码效率比较：例4与例2相比： 同一个信源，当要求编码效率达到96时， 等长码需要4100万个信源符号联合编码； 变长码只需2个符号（二次扩展信源）联合编码；结论：采用变长编码，N不需要很大就可以达到相当高的编码效率，而且可以实现无失真编码。且随着N的增大，编码效率越来越接近于1。5.5实用的无失真信源编码方法举例1（huffman编码）nHuffman编码n编码方法n特点n应用n问题5.5实用的无失真信源编码方法举例2（huffman编码）n编码方法：例 ： =消息U 概率pi 编码C U1 1/2 0 0 1 U2 1/4 0 10 1/2 1 U3 1/8 0 110

18、1/4 1 U4 1/8 1 111pis8/18/14/12/14321ssss5.5实用的无失真信源编码方法举例3（huffman编码）编码规则： 1)将信源消息U按概率大小排序（由大至小）。 2)从最小两个概率开始编码，并赋予一定规则，如下支路小概率为“1”，上支路大概率为“0”。若两支路概率相等，仍为下支为“1”上支为“0”。 3) 将已编码两支路概率合并，重新排队，编码。 4) 重复步骤3）直至合并概率归一时为止。 5) 从概率归一端沿树图路线逆行至对应消息编码，如U3为“110”。5.5实用的无失真信源编码方法举例4（huffman编码）n例2：5.5实用的无失真信源编码方法举例5（huffman编码）n特点：n编码不是唯一的n保证了概率大的符号对应于短码，概率小的符号对应于长码，而且短码得到充分利用n每次缩减信源的最后二个码字总是最后一位码元不同，前面各位码元相同（二元码情况）n每次缩减信源的最长两个码字具有相同码长这三个特点保证了所得到这三个特点保证了所得到huffman码一定是最佳码码一定是最佳码5.5实用的无失真信源编码方法举例6（huffman编码）n应用应用: : n在不同领域得到广泛应用。 n例：International dig