信息论与编码理论第三章PPT讲稿.ppt

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

1、信息论与编码理论第三章第1页，共51页，编辑于2022年，星期四3.1 信源及其分类信源及其分类3.2 离散无记忆信源的等长编码离散无记忆信源的等长编码3.3 离散无记忆信源的不等长编码离散无记忆信源的不等长编码3.4 最佳不等长编码最佳不等长编码第2页，共51页，编辑于2022年，星期四3.1 信源及其分类信源及其分类第3页，共51页，编辑于2022年，星期四信源及其分类信源及其分类离散信源离散信源 U-2,U-1,U0,U1,U2,，Ul取自字母表取自字母表A无记忆信源无记忆信源:Ul彼此独立彼此独立有记忆信源：有记忆信源：Ul彼此相关彼此相关简单信源：简单信源：Ul独立同分布独立同分布平

2、稳信源，各态历经源平稳信源，各态历经源M阶记忆源（有限状态马尔可夫链）阶记忆源（有限状态马尔可夫链）连续信源连续信源n时间离散连续源时间离散连续源n随机波形源随机波形源第4页，共51页，编辑于2022年，星期四3.2 离散无记忆源的等长编码离散无记忆源的等长编码第5页，共51页，编辑于2022年，星期四离散无记忆源离散无记忆源字母表字母表A=a1,aK,概率概率p1,pK,长为长为L的的源输出序列源输出序列uL=u1,uL，共有，共有KL种序列种序列码符号字母表码符号字母表B=b1,bD,以码符号表示源以码符号表示源输出序列，输出序列，D元码元码等长等长D元码，不等长元码，不等长D元码元码单义

3、可译码，每个消息都至少有一个码字与单义可译码，每个消息都至少有一个码字与之对应。之对应。单义可译码存在充要条件单义可译码存在充要条件DNKL NLlogK/logD第6页，共51页，编辑于2022年，星期四DMS的等长编码的等长编码NlogDLH(U)H(U)是统计平均值，是统计平均值，L达到无限时，一个具达到无限时，一个具体的源输出序列的平均每符号的信息量才等体的源输出序列的平均每符号的信息量才等于于H(U)选选L足够长，使足够长，使 NlogDLH(U)+e eL第7页，共51页，编辑于2022年，星期四DMS序列的自信息量序列的自信息量第8页，共51页，编辑于2022年，星期四弱、强弱、

4、强e e典型序列集典型序列集第9页，共51页，编辑于2022年，星期四信源划分定理信源划分定理典型序列集典型序列集非典型序列集非典型序列集序列集合序列集合第10页，共51页，编辑于2022年，星期四典型序列的比例第11页，共51页，编辑于2022年，星期四编码速率和等长编码定理编码速率和等长编码定理R=(1/L)logM=(N/L)logD,M为码字总数为码字总数定义：对于给定信源和编码速率定义：对于给定信源和编码速率R以及任意以及任意e0，若有，若有L0,以及编译码方法，使得以及编译码方法，使得LL0,错误概率小于错误概率小于e，R是可达的是可达的等长编码定理等长编码定理 RH(U),R是可

5、达的，是可达的，RH(U)是不可达的是不可达的编码效率编码效率=H(U)/R第12页，共51页，编辑于2022年，星期四3.3 DMS的不等长编码的不等长编码第13页，共51页，编辑于2022年，星期四平均码长平均码长第14页，共51页，编辑于2022年，星期四几个定义几个定义唯一可译码唯一可译码逗点码，无逗点码逗点码，无逗点码字头或前缀字头或前缀异字头码或异前缀码异字头码或异前缀码树码，满树，非满树，全树树码，满树，非满树，全树树码构造异字头码树码构造异字头码第15页，共51页，编辑于2022年，星期四例子例子信源字信源字母集母集概率概率码码A A码码B B码码C C码码D Da1a2a3a

6、40.50.250.1250.125001100100110101101110010110111第16页，共51页，编辑于2022年，星期四ShannonFano编码编码D D元码元码每次信源符号化为概率近似相等的每次信源符号化为概率近似相等的D D个子集个子集这样可以保证这样可以保证D D个码元近似等概，每个码字个码元近似等概，每个码字承载的信息量近似最大，码就近似最短。承载的信息量近似最大，码就近似最短。理想情况理想情况I(aI(ak k)=n)=nk klogD,p(alogD,p(ak k)=D)=D-n-nk k第17页，共51页，编辑于2022年，星期四Kraft不等式不等式长度为

7、长度为n1，n2，nK的的D-元异字头码存在的充分必要条件元异字头码存在的充分必要条件是是二元异字头码二元异字头码Kraft不等式等号成立不等式等号成立定理定理:任意唯一可译码必满足任意唯一可译码必满足Kraft不等式不等式第18页，共51页，编辑于2022年，星期四不等长编码定理不等长编码定理编码速率编码速率第19页，共51页，编辑于2022年，星期四3.4最佳不等长编码最佳不等长编码第20页，共51页，编辑于2022年，星期四HuffmanHuffman编码的最佳性编码的最佳性所谓最佳：是指在所有可能的编码方法中，其所谓最佳：是指在所有可能的编码方法中，其编码得到的平均码长最短。编码得到的

8、平均码长最短。定理定理3.4.1：对于给定信源，存在有最佳惟一可对于给定信源，存在有最佳惟一可译二元码，其最小概率的两个码字译二元码，其最小概率的两个码字C CK-1K-1和和C CK K的的长度最长且相等，它们之间仅最后一位码元取长度最长且相等，它们之间仅最后一位码元取值不同值不同(一个为一个为0 0，另一个为，另一个为1)1)。第21页，共51页，编辑于2022年，星期四HuffmanHuffman编码的最佳性编码的最佳性对信源对信源可对可对aK-1和和aK的码字的最后一位分别指定为的码字的最后一位分别指定为1 1和和0 0，然，然后作一辅助集后作一辅助集第22页，共51页，编辑于2022

9、年，星期四HuffmanHuffman编码的最佳性编码的最佳性定理定理3.4.2 3.4.2 对辅助集对辅助集U 为最佳的码，对原为最佳的码，对原始消息集始消息集U也是最佳的。也是最佳的。若若C1，C2，CK-1是对辅助集是对辅助集U 的最佳的最佳码，相应码长为码，相应码长为n1，n2，nK-1，则对则对U的码字的码字C1，C2,CK的码长为的码长为nk=nk kK2nk=nK-1+1 k=K,K1第23页，共51页，编辑于2022年，星期四HuffmanHuffman编码的最佳性编码的最佳性 第24页，共51页，编辑于2022年，星期四例：例：HuffmanHuffman编码过程编码过程第2

10、5页，共51页，编辑于2022年，星期四例：例：HuffmanHuffman编码过程编码过程第26页，共51页，编辑于2022年，星期四Shannon-FanoShannon-Fano编码例子编码例子cabcedeacacdeddaaabaababaaabbacdebaceada cabcedeacacdeddaaabaababaaabbacdebaceada 共共4040个个字母字母频度频度na-16a-16，b-7b-7，c-6c-6，d-6d-6，e-5 e-5 1)1)将给定符号按照其频率从大到小排序。将给定符号按照其频率从大到小排序。na-16 b-7 c-6 d-6 e a-16

11、b-7 c-6 d-6 e 5 52)2)将序列分成左右两部分，使得左部频率总和尽可能将序列分成左右两部分，使得左部频率总和尽可能接近右部频率总和。有：接近右部频率总和。有：n(a,b),(c,d,e)(a,b),(c,d,e)第27页，共51页，编辑于2022年，星期四Shannon-FanoShannon-Fano编码例子编码例子3)3)我们把第二步中划分出的上部作为二叉树的左子树，记我们把第二步中划分出的上部作为二叉树的左子树，记 0 0，下部作为二叉树的右子树，记下部作为二叉树的右子树，记 1 1。4)4)分别对左右子树重复分别对左右子树重复 2 3 2 3 两步，直到所有的符号都成为

12、二叉树的两步，直到所有的符号都成为二叉树的树叶为止。树叶为止。bacde00101011a 00b 01c 10d 110e 111第28页，共51页，编辑于2022年，星期四Shannon-FanoShannon-Fano编码例子编码例子编码结果编码结果nCabcedeacacdeddaaabaababaaabbacdebaceadan10 00 01 10 111 110 111 00 10 00 10.n长长91bit采用采用3bit等长编码需等长编码需120bit采用采用ASCII码需要码需要320bit第29页，共51页，编辑于2022年，星期四采用采用Huffman编码编码a 16

13、b 7c 6d 6e 511132401010101a 0b 100c 101d 110e 111总比特数总比特数88，信源熵为，信源熵为86.601bit第30页，共51页，编辑于2022年，星期四HuffmanHuffman编码编码Shannon-FanoShannon-Fano编码构造二叉树是自树根到编码构造二叉树是自树根到树叶，很难保证最佳性。树叶，很难保证最佳性。HuffmanHuffman编码则是从树叶到树根，是最佳的编码则是从树叶到树根，是最佳的第31页，共51页，编辑于2022年，星期四总结总结HuffmanHuffman需要知道信源的概率分布，这在实需要知道信源的概率分布，这

14、在实际中有时是比较困难的。际中有时是比较困难的。采用半静态模型、自适应模型、采用半静态模型、自适应模型、markovmarkov模模型，部分匹配预测模型等等解决这一问题。型，部分匹配预测模型等等解决这一问题。第32页，共51页，编辑于2022年，星期四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)第33页，共51页，编辑于2022年，星期四Shannon-Fano-Elias

15、编码编码累计分布函数修正累计分布函数第34页，共51页，编辑于2022年，星期四Shannon-Fano-Elias编码编码采用采用 的数值作为的数值作为ak的码字的码字码长码长第35页，共51页，编辑于2022年，星期四Shannon-Fano-Elias编码第36页，共51页，编辑于2022年，星期四Shannon-Fano-Elias编码编码信源信源符号符号P(aP(ak k)F(aF(ak k)修正值修正值 二进制二进制 码长码长码字码字a10.250.250.1250.0013001a20.50.750.50.10210a30.1250.8750.81250.110141101a40

16、.1251.00.93750.111141111第37页，共51页，编辑于2022年，星期四算术码算术码应用于应用于JPEG2000,H.263等图像压缩标准等图像压缩标准第38页，共51页，编辑于2022年，星期四算术码算术码信源序列信源序列(u1u2un)的累计分布的累计分布算术编码是计算序列的累计分布，用累计分算术编码是计算序列的累计分布，用累计分布值表示序列，所以称为算术编码布值表示序列，所以称为算术编码以二元信源输出序列的编码为例以二元信源输出序列的编码为例01110P(0)P(1)F(0)F(1)01第39页，共51页，编辑于2022年，星期四算术码算术码P(00)P(01)F(0

17、)F(01)F(1)P(010)P(011)F(011)P(0110)P(0111)F(0111)P(01110)P(01111)F(01111)第40页，共51页，编辑于2022年，星期四算术码算术码信源符号序列信源符号序列u u对应区间的宽度等于符号序列的概对应区间的宽度等于符号序列的概率率第41页，共51页，编辑于2022年，星期四算术编码算术编码F(u)将将0,1)分割成许多小区间，取分割成许多小区间，取小区间内的一个点代表该序列，以小区间内的一个点代表该序列，以该点数值的二进制小数表示该序列，该点数值的二进制小数表示该序列，码字长度为码字长度为第42页，共51页，编辑于2022年，星

18、期四算术编码算术编码第43页，共51页，编辑于2022年，星期四例例：P(0)=0.25,P(1)=0.75,u=11111100 P(u=11111100)=0.7560.252L=7F(s)=0.110100100111C=1101010编码效率编码效率92.7%第44页，共51页，编辑于2022年，星期四LZ编码编码利用字典编码方法利用字典编码方法信源符号信源符号A=(a1aK)将序列分为不同的段将序列分为不同的段n取最短长度的连续符号构成段，保证互不相同。取最短长度的连续符号构成段，保证互不相同。n先取一个符号分段，若与前面段相同，就再取先取一个符号分段，若与前面段相同，就再取一个符号

19、，直至序列结束一个符号，直至序列结束n得到字典表，码字由段号加后一个符号组成。得到字典表，码字由段号加后一个符号组成。n单符号的码字，段号为单符号的码字，段号为0第45页，共51页，编辑于2022年，星期四LZ编码编码符号符号码字码字a0a1a2a300011011第46页，共51页，编辑于2022年，星期四LZ编码编码00000 00110 00011 00001 10000 00100 01110 1 2 3 4 5 6 7第47页，共51页，编辑于2022年，星期四LZ编码编码设长为设长为L的信源序列的信源序列u分为分为M(u)个码段，每个码段，每段短语的二元码符号长度为段短语的二元码符号长度为总码长总码长平均平均+第48页，共51页，编辑于2022年，星期四LZ编码编码设长度为设长度为l段有段有Kl种。若把长为种。若把长为L的信源序列的信源序列u分为分为M(u)个码段后，设最长的段长为个码段后，设最长的段长为lmax，而且所有小于等于，而且所有小于等于lmax 的段型全部都有，的段型全部都有，则则第49页，共51页，编辑于2022年，星期四LZ编码编码典型段，典型段，ak出现的出现的次数为次数为lmaxp(ak)第50页，共51页，编辑于2022年，星期四LZ编码设较短的段型忽略不计设较短的段型忽略不计第51页，共51页，编辑于2022年，星期四