信息论与编码理论--第三章.ppt

《信息论与编码理论--第三章.ppt》由会员分享，可在线阅读，更多相关《信息论与编码理论--第三章.ppt（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章第三章 信源编码（一）信源编码（一）离散信源无失真编码离散信源无失真编码3.1 信源及其分类信源及其分类3.2 离散无记忆信源的等长编码离散无记忆信源的等长编码3.3 离散无记忆信源的不等长编码离散无记忆信源的不等长编码3.4 最佳不等长编码最佳不等长编码3.1 信源及其分类信源及其分类信源及其分类信源及其分类离散信源离散信源 U-2,U-1,U0,U1,U2,，Ul取自字母表取自字母表A无记忆信源无记忆信源:Ul彼此独立彼此独立有记忆信源：有记忆信源：Ul彼此相关彼此相关简单信源：简单信源：Ul独立同分布独立同分布平稳信源，各态历经源平稳信源，各态历经源M阶记忆源（有限状态马尔可夫链）

2、阶记忆源（有限状态马尔可夫链）连续信源连续信源n时间离散连续源时间离散连续源n随机波形源随机波形源3.2 离散无记忆源的等长编码离散无记忆源的等长编码离散无记忆源离散无记忆源字母表字母表A=a1,aK,概率概率p1,pK,长为长为L的源输出序列的源输出序列uL=u1,uL，共有，共有KL种序种序列列码符号字母表码符号字母表B=b1,bD,以码符号表示以码符号表示源输出序列，源输出序列，D元码元码等长等长D元码，不等长元码，不等长D元码元码单义可译码，每个消息都至少有一个码字单义可译码，每个消息都至少有一个码字与之对应。与之对应。单义可译码存在充要条件单义可译码存在充要条件DNKL NLlogK

3、/logDDMS的等长编码的等长编码NlogDLH(U)H(U)是统计平均值，是统计平均值，L达到无限时，一个具达到无限时，一个具体的源输出序列的平均每符号的信息量才体的源输出序列的平均每符号的信息量才等于等于H(U)选选L足够长，使足够长，使 NlogDLH(U)+e eLDMS序列的自信息量序列的自信息量弱、强弱、强e e典型序列集典型序列集信源划分定理信源划分定理典型序列集典型序列集非典型序列集非典型序列集序列集合序列集合典型序列的比例编码速率和等长编码定理编码速率和等长编码定理R=(1/L)logM=(N/L)logD,M为码字总数为码字总数定义：对于给定信源和编码速率定义：对于给定信

4、源和编码速率R以及任意以及任意e0，若有，若有L0,以及编译码方法，使得以及编译码方法，使得LL0,错误概率小于错误概率小于e，R是可达的是可达的等长编码定理等长编码定理 RH(U),R是可达的，是可达的，RH(U)是不可达的是不可达的编码效率编码效率=H(U)/R3.3 DMS的不等长编码的不等长编码平均码长平均码长几个定义几个定义唯一可译码唯一可译码逗点码，无逗点码逗点码，无逗点码字头或前缀字头或前缀异字头码或异前缀码异字头码或异前缀码树码，满树，非满树，全树树码，满树，非满树，全树树码构造异字头码树码构造异字头码例子例子信源字信源字母集母集概率概率码码A A码码B B码码C C码码D D

5、a1a2a3a40.50.250.1250.125001100100110101101110010110111ShannonFano编码编码D D元码元码每次信源符号化为概率近似相等的每次信源符号化为概率近似相等的D D个子集个子集这样可以保证这样可以保证D D个码元近似等概，每个码字个码元近似等概，每个码字承载的信息量近似最大，码就近似最短。承载的信息量近似最大，码就近似最短。理想情况理想情况I(aI(ak k)=)=n nk klogDlogD,p(ap(ak k)=D)=D-n nk kKraft不等式不等式长度为长度为n1，n2，nK的的D-元异字头码存在的充分必元异字头码存在的充分必

6、要条件是要条件是二元异字头码二元异字头码Kraft不等式等号成立不等式等号成立定理定理:任意唯一可译码必满足任意唯一可译码必满足Kraft不等式不等式不等长编码定理不等长编码定理编码速率编码速率3.4最佳不等长编码最佳不等长编码HuffmanHuffman编码的最佳性编码的最佳性所谓最佳：是指在所有可能的编码方法中，其所谓最佳：是指在所有可能的编码方法中，其编码得到的平均码长最短。编码得到的平均码长最短。定理定理3.4.1：对于给定信源，存在有最佳惟一可对于给定信源，存在有最佳惟一可译二元码，其最小概率的两个码字译二元码，其最小概率的两个码字C CK-1K-1和和C CK K的的长度最长且相等

7、，它们之间仅最后一位码元取长度最长且相等，它们之间仅最后一位码元取值不同值不同(一个为一个为0 0，另一个为，另一个为1)1)。HuffmanHuffman编码的最佳性编码的最佳性对信源对信源可对可对aK-1和和aK的码字的最后一位分别指定为的码字的最后一位分别指定为1 1和和0 0，然后作一辅助集然后作一辅助集HuffmanHuffman编码的最佳性编码的最佳性定理定理3.4.2 3.4.2 对辅助集对辅助集U 为最佳的码，对原为最佳的码，对原始消息集始消息集U也是最佳的。也是最佳的。若若C1，C2，CK-1是对辅助集是对辅助集U 的最佳的最佳码，相应码长为码，相应码长为n1，n2，nK-1

8、，则对则对U的码字的码字C1，C2,CK的码长为的码长为nk=nk kK2nk=nK-1+1 k=K,K1HuffmanHuffman编码的最佳性编码的最佳性 例：例：HuffmanHuffman编码过程编码过程例：例：HuffmanHuffman编码过程编码过程Shannon-Shannon-FanoFano编码例子编码例子cabcedeacacdeddaaabaababaaabbacdebaceadacabcedeacacdeddaaabaababaaabbacdebaceada 共共4040个字母个字母频度频度na-16a-16，b-7b-7，c-6c-6，d-6d-6，e-5 e-5

9、1)1)将给定符号按照其频率从大到小排序。将给定符号按照其频率从大到小排序。na-16 b-7 c-6 d-6 e a-16 b-7 c-6 d-6 e 5 52)2)将序列分成左右两部分，使得左部频率总和尽可将序列分成左右两部分，使得左部频率总和尽可能接近右部频率总和。有：能接近右部频率总和。有：n(a,b),(c,d,e)(a,b),(c,d,e)Shannon-Shannon-FanoFano编码例子编码例子3)3)我们把第二步中划分出的上部作为二叉树的左子树，记我们把第二步中划分出的上部作为二叉树的左子树，记 0 0，下部作为二叉树的右子树，记，下部作为二叉树的右子树，记 1 1。4)

10、4)分别对左右子树重复分别对左右子树重复 2 3 2 3 两步，直到所有的符号都成为两步，直到所有的符号都成为二叉树的树叶为止。二叉树的树叶为止。bacde00101011a 00b 01c 10d 110e 111Shannon-Shannon-FanoFano编码例子编码例子编码结果编码结果nCabcedeacacdeddaaabaababaaabbacdebaceadan10 00 01 10 111 110 111 00 10 00 10.n长长91bit采用采用3bit等长编码需等长编码需120bit采用采用ASCII码需要码需要320bit采用采用Huffman编码a 16b 7c

11、 6d 6e 511132401010101a 0b 100c 101d 110e 111总比特数总比特数88，信源熵为，信源熵为86.601bitHuffmanHuffman编码编码Shannon-Shannon-FanoFano编码构造二叉树是自树根到编码构造二叉树是自树根到树叶，很难保证最佳性。树叶，很难保证最佳性。HuffmanHuffman编码则是从树叶到树根，是最佳的编码则是从树叶到树根，是最佳的总结总结HuffmanHuffman需要知道信源的概率分布，这在实需要知道信源的概率分布，这在实际中有时是比较困难的。际中有时是比较困难的。采用半静态模型、自适应模型、采用半静态模型、自适

12、应模型、markovmarkov模模型，部分匹配预测模型等等解决这一问题。型，部分匹配预测模型等等解决这一问题。D元元Huffman编码编码共有共有K个符号，概率最小的个符号，概率最小的R个符号码长最长个符号码长最长K+B=D+m(D-1)注意注意BD-1 K-2=m(D-1)+D-2-B B B个个R个个B=D-2-(K-2)mod(D-1)R=2+(K-2)mod(D-1)Shannon-Fano-Elias编码编码累计分布函数修正累计分布函数Shannon-Fano-Elias编码编码采用采用 的数值作为的数值作为ak的码字的码字码长码长Shannon-Fano-Elias编码Shann

13、on-Fano-Elias编码编码信源信源符号符号P(aP(ak k)F(aF(ak k)修正值修正值 二进制二进制 码长码长码字码字a10.250.250.1250.0013001a20.50.750.50.10210a30.1250.8750.81250.110141101a40.1251.00.93750.111141111算术码算术码应用于应用于JPEG2000,H.263等图像压缩标准等图像压缩标准算术码算术码信源序列信源序列(u1u2un)的累计分布的累计分布算术编码是计算序列的累计分布，用累计算术编码是计算序列的累计分布，用累计分布值表示序列，所以称为算术编码分布值表示序列，所以

14、称为算术编码以二元信源输出序列的编码为例以二元信源输出序列的编码为例01110P(0)P(1)F(0)F(1)01算术码算术码P(00)P(01)F(0)F(01)F(1)P(010)P(011)F(011)P(0110)P(0111)F(0111)P(01110)P(01111)F(01111)算术码算术码信源符号序列信源符号序列u u对应区间的宽度等于符号序列的对应区间的宽度等于符号序列的概率概率算术编码算术编码F(u)将将0,1)分割成许多小区间，分割成许多小区间，取小区间内的一个点代表该序列，取小区间内的一个点代表该序列，以该点数值的二进制小数表示该以该点数值的二进制小数表示该序列，码

15、字长度为序列，码字长度为算术编码算术编码例例：P(0)=0.25,P(1)=0.75,u=11111100 P(u=11111100)=0.7560.252L=7F(s)=0.110100100111C=1101010编码效率编码效率92.7%LZ编码编码利用字典编码方法利用字典编码方法信源符号信源符号A=(a1aK)将序列分为不同的段将序列分为不同的段n取最短长度的连续符号构成段，保证互不相同。取最短长度的连续符号构成段，保证互不相同。n先取一个符号分段，若与前面段相同，就再取先取一个符号分段，若与前面段相同，就再取一个符号，直至序列结束一个符号，直至序列结束n得到字典表，码字由段号加后一个

16、符号组成。得到字典表，码字由段号加后一个符号组成。n单符号的码字，段号为单符号的码字，段号为0LZ编码编码符号符号码字字a0a1a2a300011011LZ编码编码00000 00110 00011 00001 10000 00100 01110 1 2 3 4 5 6 7LZ编码编码设长为设长为L的信源序列的信源序列u分为分为M(u)个码段，每个码段，每段短语的二元码符号长度为段短语的二元码符号长度为总码长总码长平均平均+LZ编码编码设长度为设长度为l段有段有Kl种。若把长为种。若把长为L的信源序列的信源序列u分为分为M(u)个码段后，设最长的段长为个码段后，设最长的段长为lmax，而且所有小于等于，而且所有小于等于lmax 的段型全部都有，的段型全部都有，则则LZ编码编码典型段，典型段，ak出现出现的次数为的次数为lmaxp(ak)LZ编码设较短的段型忽略不计设较短的段型忽略不计