信息论与编码理论 第三章课件

第三章信源编码（一）

离散信源无失真编码第三章信源编码（一）

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

N≥LlogK/logD离散无记忆源字母表A={a1,…,aK},概率p1,…,pK6DMS的等长编码NlogD≥LH(U)H(U)是统计平均值，L达到无限时，一个具体的源输出序列的平均每符号的信息量才等于H(U)选L足够长，使NlogD≥L[H(U)+eL]DMS的等长编码NlogD≥LH(U)7DMS序列的自信息量DMS序列的自信息量8弱、强e典型序列集弱、强e典型序列集9信源划分定理典型序列集非典型序列集序列集合信源划分定理典型序列集非典型序列集序列集合10典型序列的比例典型序列的比例11编码速率和等长编码定理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

编码速率和等长编码定理R=(1/L)logM=(N/L)lo123.3DMS的不等长编码3.3DMS的不等长编码13平均码长平均码长14几个定义唯一可译码逗点码，无逗点码字头或前缀异字头码或异前缀码树码，满树，非满树，全树树码构造异字头码几个定义唯一可译码15例子信源字母集概率码A码B码C码Da1a2a3a40.50.250.1250.125001100100110101101110010110111例子信源字母集概率码A码B码C码Da10.5000016Shannon－Fano编码D元码每次信源符号化为概率近似相等的D个子集这样可以保证D个码元近似等概，每个码字承载的信息量近似最大，码就近似最短。理想情况I(ak)=nklogD,p(ak)=D-nkShannon－Fano编码D元码17Kraft不等式长度为n1，n2，…，nK的D-元异字头码存在的充分必要条件是二元异字头码Kraft不等式等号成立定理:任意唯一可译码必满足Kraft不等式Kraft不等式长度为n1，n2，…，nK的D-元异字头码存18不等长编码定理编码速率不等长编码定理编码速率193.4最佳不等长编码3.4最佳不等长编码20Huffman编码的最佳性所谓最佳：是指在所有可能的编码方法中，其编码得到的平均码长最短。定理3.4.1：对于给定信源，存在有最佳惟一可译二元码，其最小概率的两个码字CK-1和CK的长度最长且相等，它们之间仅最后一位码元取值不同(一个为0，另一个为1)。Huffman编码的最佳性所谓最佳：是指在所有可能的编码方法21Huffman编码的最佳性对信源可对aK-1和aK的码字的最后一位分别指定为1和0，然后作一辅助集Huffman编码的最佳性对信源22Huffman编码的最佳性定理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–1Huffman编码的最佳性定理3.4.2对辅助集U’为23Huffman编码的最佳性

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

1234567LZ编码000000011000011000011047LZ编码设长为L的信源序列u分为M(u)个码段，每段短语的二元码符号长度为总码长平均+LZ编码设长为L的信源序列u分为M(u)个码段，每段短语的二48LZ编码设长度为l段有Kl种。若把长为L的信源序列u分为M(u)个码段后，设最长的段长为lmax，而且所有小于等于lmax的段型全部都有，则LZ编码设长度为l段有Kl种。若把长为L的信源序列u分为M(49LZ编码典型段，ak出现的次数为lmaxp(ak)LZ编码典型段，ak出现的次数为lmaxp(ak)50LZ编码设较短的段型忽略不计LZ编码设较短的段型忽略不计51第三章信源编码（一）

离散信源无失真编码第三章信源编码（一）

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

N≥LlogK/logD离散无记忆源字母表A={a1,…,aK},概率p1,…,pK57DMS的等长编码NlogD≥LH(U)H(U)是统计平均值，L达到无限时，一个具体的源输出序列的平均每符号的信息量才等于H(U)选L足够长，使NlogD≥L[H(U)+eL]DMS的等长编码NlogD≥LH(U)58DMS序列的自信息量DMS序列的自信息量59弱、强e典型序列集弱、强e典型序列集60信源划分定理典型序列集非典型序列集序列集合信源划分定理典型序列集非典型序列集序列集合61典型序列的比例典型序列的比例62编码速率和等长编码定理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

编码速率和等长编码定理R=(1/L)logM=(N/L)lo633.3DMS的不等长编码3.3DMS的不等长编码64平均码长平均码长65几个定义唯一可译码逗点码，无逗点码字头或前缀异字头码或异前缀码树码，满树，非满树，全树树码构造异字头码几个定义唯一可译码66例子信源字母集概率码A码B码C码Da1a2a3a40.50.250.1250.125001100100110101101110010110111例子信源字母集概率码A码B码C码Da10.5000067Shannon－Fano编码D元码每次信源符号化为概率近似相等的D个子集这样可以保证D个码元近似等概，每个码字承载的信息量近似最大，码就近似最短。理想情况I(ak)=nklogD,p(ak)=D-nkShannon－Fano编码D元码68Kraft不等式长度为n1，n2，…，nK的D-元异字头码存在的充分必要条件是二元异字头码Kraft不等式等号成立定理:任意唯一可译码必满足Kraft不等式Kraft不等式长度为n1，n2，…，nK的D-元异字头码存69不等长编码定理编码速率不等长编码定理编码速率703.4最佳不等长编码3.4最佳不等长编码71Huffman编码的最佳性所谓最佳：是指在所有可能的编码方法中，其编码得到的平均码长最短。定理3.4.1：对于给定信源，存在有最佳惟一可译二元码，其最小概率的两个码字CK-1和CK的长度最长且相等，它们之间仅最后一位码元取值不同(一个为0，另一个为1)。Huffman编码的最佳性所谓最佳：是指在所有可能的编码方法72Huffman编码的最佳性对信源可对aK-1和aK的码字的最后一位分别指定为1和0，然后作一辅助集Huffman编码的最佳性对信源73Huffman编码的最佳性定理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–1Huffman编码的最佳性定理3.4.2对辅助集U’为74Huffman编码的最佳性

Huffman编码的最佳性75例：Huffman编码过程例：Huffman编码过程76例：Huffman编码过程例：Huffman编码过程77Shannon-Fano编码例子cabcedeacacdeddaaabaababaaabbacdebaceada共40个字母频度a-16，b-7，c-6，d-6，e-51)将给定符号按照其频率从大到小排序。a-16b-7c-6d-6e–52)将序列分成左右两部分，使得左部频率总和尽可能接近右部频率总和。有：(a,b),(c,d,e)Shannon-Fano编码例子cabcedeacacded78Shannon-Fano编码例子3)我们把第二步中划分出的上部作为二叉树的左子树，记0，下部作为二叉树的右子树，记1。4)分别对左右子树重复23两步，直到所有的符号都成为二叉树的树叶为止。bacde00101011a00b01c10d110e111Shannon-Fano编码例子3)我们把第二步中划分出的79Shannon-Fano编码例子编码结果Cabcedeacacdeddaaabaababaaabbacdebaceada1000011011111011100100010......长91bit采用3bit等长编码需120bit采用ASCII码需要320bitShannon-Fano编码例子编码结果80采用Huffman编码a16b7c6d6e511132401010101a0b100c101d110e111总比特数88，信源熵为86.601bit采用Huffman编码a16b7c6d6e81Huffman编码Shannon-Fano编码构造二叉树是自树根到树叶，很难保证最佳性。Huffman编码则是从树叶到树根，是最佳的Huffman编码Shannon-Fano编码构造二叉树是自82总结Huffman需要知道信源的概率分布，这在实际中有时是比较困难的。采用半静态模型、自适应模型、markov模型，部分匹配预测模型等等解决这一问题。总结Huffman需要知道信源的概率分布，这在实际中有时是比83D元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))D元Huffman编码共有K个符号，概率最小的R个符号码长最84Shannon-Fano-Elias编码累计分布函数修正累计分布函数Shannon-Fano-Elias编码累计分布函数修正累计85Shannon-Fano-Elias编码采用的数值作为ak的码字码长Shannon-Fano-Elias编码采用86Shannon-Fano-Elias编码Shannon-Fano-Elias编码87Shannon-Fano-Elias编码信源符号P(ak)F(ak)修正值二进制码长码字a10.250.250.1250.0013001a20.50.750.50.10210a30.1250.8750.81250.110141101a40.1251.00.93750.111141111Shannon-Fano-Elias编码信源符号P(ak)F88算术码应用于JPEG2000,H.263等图像压缩标准算术码应用于JPEG2000,H.263等图像压缩标准89算术码信源序列(u1u2…un)的累计分布算术编码是计算序列的累计分布，用累计分布值表示序列，所以称为算术编码以二元信源输出序列的编码为例01110P(0)P(1)F(0)F(1)01算术码信源序列(u1u2…un)的累计分布P(0)P(1)F90算术码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)算