信息论与编码理论第三章

信息论与编码理论第三章第1页，课件共51页，创作于2023年2月3.1信源及其分类3.2离散无记忆信源的等长编码3.3离散无记忆信源的不等长编码3.4最佳不等长编码第2页，课件共51页，创作于2023年2月3.1信源及其分类第3页，课件共51页，创作于2023年2月信源及其分类离散信源…U-2,U-1,U0,U1,U2,…，Ul取自字母表A无记忆信源:Ul彼此独立有记忆信源：Ul彼此相关简单信源：Ul独立同分布平稳信源，各态历经源M阶记忆源（有限状态马尔可夫链）连续信源时间离散连续源随机波形源第4页，课件共51页，创作于2023年2月3.2离散无记忆源的等长编码第5页，课件共51页，创作于2023年2月离散无记忆源字母表A={a1,…,aK},概率p1,…,pK,长为L的源输出序列uL={u1,…,uL}，共有KL种序列码符号字母表B={b1,…,bD},以码符号表示源输出序列，D元码等长D元码，不等长D元码单义可译码，每个消息都至少有一个码字与之对应。单义可译码存在充要条件DN≥KL

N≥LlogK/logD第6页，课件共51页，创作于2023年2月DMS的等长编码NlogD≥LH(U)H(U)是统计平均值，L达到无限时，一个具体的源输出序列的平均每符号的信息量才等于H(U)选L足够长，使NlogD≥L[H(U)+eL]第7页，课件共51页，创作于2023年2月DMS序列的自信息量第8页，课件共51页，创作于2023年2月弱、强e典型序列集第9页，课件共51页，创作于2023年2月信源划分定理典型序列集非典型序列集序列集合第10页，课件共51页，创作于2023年2月典型序列的比例第11页，课件共51页，创作于2023年2月编码速率和等长编码定理R=(1/L)logM=(N/L)logD,M为码字总数定义：对于给定信源和编码速率R以及任意e>0，若有L0,以及编译码方法，使得L>L0,错误概率小于e，R是可达的等长编码定理

R>H(U),R是可达的，R<H(U)是不可达的编码效率=H(U)/R

第12页，课件共51页，创作于2023年2月3.3DMS的不等长编码第13页，课件共51页，创作于2023年2月平均码长第14页，课件共51页，创作于2023年2月几个定义唯一可译码逗点码，无逗点码字头或前缀异字头码或异前缀码树码，满树，非满树，全树树码构造异字头码第15页，课件共51页，创作于2023年2月例子信源字母集概率码A码B码C码Da1a2a3a40.50.250.1250.125001100100110101101110010110111第16页，课件共51页，创作于2023年2月Shannon－Fano编码D元码每次信源符号化为概率近似相等的D个子集这样可以保证D个码元近似等概，每个码字承载的信息量近似最大，码就近似最短。理想情况I(ak)=nklogD,p(ak)=D-nk第17页，课件共51页，创作于2023年2月Kraft不等式长度为n1，n2，…，nK的D-元异字头码存在的充分必要条件是二元异字头码Kraft不等式等号成立定理:任意唯一可译码必满足Kraft不等式第18页，课件共51页，创作于2023年2月不等长编码定理编码速率第19页，课件共51页，创作于2023年2月3.4最佳不等长编码第20页，课件共51页，创作于2023年2月Huffman编码的最佳性所谓最佳：是指在所有可能的编码方法中，其编码得到的平均码长最短。定理3.4.1：对于给定信源，存在有最佳惟一可译二元码，其最小概率的两个码字CK-1和CK的长度最长且相等，它们之间仅最后一位码元取值不同(一个为0，另一个为1)。第21页，课件共51页，创作于2023年2月Huffman编码的最佳性对信源可对aK-1和aK的码字的最后一位分别指定为1和0，然后作一辅助集第22页，课件共51页，创作于2023年2月Huffman编码的最佳性定理3.4.2对辅助集U’为最佳的码，对原始消息集U也是最佳的。若C’1，C’2，…，C’K-1是对辅助集U'的最佳码，相应码长为n’1，n’2，…，n’K-1，则对U的码字C1，C2,…,CK的码长为nk=n’k

k≤K–2nk=n’K-1+1k=K,K–1第23页，课件共51页，创作于2023年2月Huffman编码的最佳性

第24页，课件共51页，创作于2023年2月例：Huffman编码过程第25页，课件共51页，创作于2023年2月例：Huffman编码过程第26页，课件共51页，创作于2023年2月Shannon-Fano编码例子cabcedeacacdeddaaabaababaaabbacdebaceada共40个字母频度a-16，b-7，c-6，d-6，e-51)将给定符号按照其频率从大到小排序。a-16b-7c-6d-6e–52)将序列分成左右两部分，使得左部频率总和尽可能接近右部频率总和。有：(a,b),(c,d,e)第27页，课件共51页，创作于2023年2月Shannon-Fano编码例子3)我们把第二步中划分出的上部作为二叉树的左子树，记0，下部作为二叉树的右子树，记1。4)分别对左右子树重复23两步，直到所有的符号都成为二叉树的树叶为止。bacde00101011a00b01c10d110e111第28页，课件共51页，创作于2023年2月Shannon-Fano编码例子编码结果Cabcedeacacdeddaaabaababaaabbacdebaceada1000011011111011100100010......长91bit采用3bit等长编码需120bit采用ASCII码需要320bit第29页，课件共51页，创作于2023年2月采用Huffman编码a16b7c6d6e511132401010101a0b100c101d110e111总比特数88，信源熵为86.601bit第30页，课件共51页，创作于2023年2月Huffman编码Shannon-Fano编码构造二叉树是自树根到树叶，很难保证最佳性。Huffman编码则是从树叶到树根，是最佳的第31页，课件共51页，创作于2023年2月总结Huffman需要知道信源的概率分布，这在实际中有时是比较困难的。采用半静态模型、自适应模型、markov模型，部分匹配预测模型等等解决这一问题。第32页，课件共51页，创作于2023年2月D元Huffman编码共有K个符号，概率最小的R个符号码长最长K+B=D+m(D-1)注意B<D-1K-2=m(D-1)+D-2-BB个R个B=D-2-((K-2)mod(D-1))R=2+((K-2)mod(D-1))第33页，课件共51页，创作于2023年2月Shannon-Fano-Elias编码累计分布函数修正累计分布函数第34页，课件共51页，创作于2023年2月Shannon-Fano-Elias编码采用的数值作为ak的码字码长第35页，课件共51页，创作于2023年2月Shannon-Fano-Elias编码第36页，课件共51页，创作于2023年2月Shannon-Fano-Elias编码信源符号P(ak)F(ak)修正值二进制码长码字a10.250.250.1250.0013001a20.50.750.50.10210a30.1250.8750.81250.110141101a40.1251.00.93750.111141111第37页，课件共51页，创作于2023年2月算术码应用于JPEG2000,H.263等图像压缩标准第38页，课件共51页，创作于2023年2月算术码信源序列(u1u2…un)的累计分布算术编码是计算序列的累计分布，用累计分布值表示序列，所以称为算术编码以二元信源输出序列的编码为例01110P(0)P(1)F(0)F(1)01第39页，课件共51页，创作于2023年2月算术码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)第40页，课件共51页，创作于2023年2月算术码信源符号序列u对应区间的宽度等于符号序列的概率第41页，课件共51页，创作于2023年2月算术编码F(u)将[0,1)分割成许多小区间，取小区间内的一个点代表该序列，以该点数值的二进制小数表示该序列，码字长度为第42页，课件共51页，创作于2023年2月算术编码第43页，课件共51页，创作于2023年2月例：P(0)=0.25,P(1)=0.75,u=11111100P(u=11111100)=0.7560.252L=7F(s)=0.110100100111C=1101010编码效率92.7%第44页，课件共51页，创作于2023年2月LZ编码利用字典编码方法信源符号A=(a1…aK)将序列分为不同的段取最短长度的连续符号构成段，保证互不相同。先取一个符号分段，若与前面段相同，就再取一个符号，直至序列结束得到字典表，码字由段号加后一个符号组成。单符号的码字，段号为0第45页，课件共51页，创作于2023年2月LZ编码符号码字a0a1a2a300011011第46页，课件共51页，创作于2023年2月LZ编码00000001100001100001100000010001110

1234567第47页，课件共51页，创作于2023年2月LZ编码设长为L的信源序列u分为M(u)个码段，每段短语的二