信息论与编码原理第6章信源编码.ppt

第1页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,信息论与编码原理,（第六章）信源编码,第2页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,第六章信源编码,6.1引言,6.2香农编码,6.3费诺编码,6.4哈夫曼编码,6.8LZW码,6.7LZ码,6.6算术编码,6.5游程编码,6.9信源编码总结,第3页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.1引言,6.1.1编码的目的,6.1.2信源编码概论,第4页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.1.1编码的目的,香农编码定理虽然指出了理想编码器的存在性，但是并没有给出实用码的结构及构造方法；编码理论正是为了解决这一问题而发展起来的科学理论；编码的目的是为了优化通信系统，使这些指标达到最佳；通信系统的性能指标主要是有效性、可靠性、安全性和经济性，除了经济性外，这些指标正是信息论研究的对象。按不同的编码目的，编码分为三类：信源编码、信道编码和安全编码（密码）。,6.1引言,第5页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.1.1编码的目的,信源编码：提高通信有效性为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。信道编码：提高信息传输的可靠性为目的的编码。通常通过增加信源的冗余度来实现。采用的一般方法是增大码率（带宽）。与信源编码正好相反。保密编码：提高通信系统的安全性为目的的编码。通常通过加密和解密来实现。从信息论的观点出发，“加密”可视为增熵的过程，“解密”可视为减熵的过程。,返回目录,6.1引言,第6页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.1.2信源编码概述,(1)信源编码的理论基础信源编码理论是信息论的一个重要分支，其理论基础是信源编码的两个定理。无失真信源编码定理：是离散信源/数字信号编码的基础；限失真信源编码定理：是连续信源/模拟信号编码的基础。,6.1引言,第7页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.1.2信源编码概述,(2)信源编码的分类根据信源特性离散信源编码：独立信源编码，可做到无失真编码；连续信源编码：独立信源编码，只能做到限失真信源编码；相关信源编码：非独立信源编码。根据压缩的特性冗余度压缩编码：可逆压缩，经编译码后可以无失真地恢复。熵压缩编码：不可逆压缩。,6.1引言,第8页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.1.2信源编码概述,(3)数据压缩概貌KLT：Karhunen-LoeveTransformDCT：DiscreteCosineTransformDST：DiscreteSinusoidTransformDFT：DiscreteFourierTransformWHT：Walsh-HadamardTransformSLT：SlantTransformHAAR：HaarTransformLPC-10：GovernmentStandardLinearPredictiveCodingAlgorithm:LPC-10MELP：MixedExcitedLinearPredictiveCodingCELP：CodebookExcitedLinearPredictiveCodingACELP：AlgebraicCocebookExcitationLPCQCELP：QualcomCocebookExcitationLPCEVRC：EnhancedVariableRateCodecLD-CELP：LowDelay-CELP,28种,6.1引言,第9页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.1.2信源编码概述,(3)数据压缩概貌CS-ACELP：Conjugate-StructureAlgebraicCELPVSELP：VectorSumExcitationLPCRPE-LT：LongTimePredictiveRegular-PulseExcitationLPCMPLPC：Multi-PulseExcitationLPCMP-MLQ：MultipulseMaximumLikelihoodQuantizationMBE：Multi-BandExcitationSpeechCoderSTC：SinusoidTransformCocingCVSD：ContinuouslyVariableSlopeDeltaModulatorSB-ADPCM：Sub-BandAdaptiveDifferentialPulseCodeModulationPTC：PictureTelTransformCoderAC-2；AC-3：DigitalAudioCompressionStandard，美国Dolby公司AAC：AdvancedAudioCoding,日本138187,MPEG-2MUSICAM：MaskingPatternAdaptedUniversalSubbandIntegratedCodingandMultiplexingATRAC：AdaptiveTransformAcousticCoder,6.1引言,第10页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.1.2信源编码概述,(3)数据压缩概貌,6.1引言,第11页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.1.2信源编码概述,有些编码原理和技术在通信原理和信号处理等相关课程中已经介绍过。例如：,返回目录,连续信源编码：脉冲编码调制(PCM)、矢量量化技术,相关信源编码：预测编码：增量编码、差分脉冲调制(DPCM)、自适应差分脉冲调制(ADPCM)、线性预测声码器；变换编码：KL变换、离散变换、子带编码、小波变换。,6.1引言,第12页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.2香农编码,设离散无记忆信源：二进制香农码的编码步骤如下：将信源符号按概率从大到小的顺序排列，为方便起见，令：p(x1)p(x2)p(xn)令p(x0)=0，用pa(xj)，j=i+1表示第i个码字的累加概率，则：,第13页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.2香农编码,设离散无记忆信源：二进制香农码的编码步骤如下：确定满足下列不等式的整数ki，并令ki为第i个码字的长度log2p(xi)ki1log2p(xi)将pa(xj)用二进制表示，并取小数点后ki位作为符号xi的编码。,第14页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.2香农编码,例6.1.1：有一单符号离散无记忆信源：对该信源编二进制香农码。其编码过程如表5.2.1所示。,第15页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.2香农编码,例6.1.1：计算出给定信源香农码的平均码长：若对上述信源采用等长编码，要做到无失真译码，每个符号至少要用3个比特表示。相比较，香农编码对信源进行了压缩。,第16页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.2香农编码,例6.1.1：由离散无记忆信源熵定义，可计算出信源上熵为：对上述信源采用香农编码的信息率为：编码效率为信源熵和信息率之比。则：可以看出，编码效率并不是很高。,返回目录,第17页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.3费诺编码,将概率按从大到小的顺序排列，令：p(x1)p(x2)p(xn)按编码进制数将概率分组，使每组概率尽可能接近或相等。如编二进制码就分成两组，编m进制码就分成m组。给每一组分配一位码元。将每一分组再按同样原则划分，重复步骤2和3，直至概率不再可分为止。,第18页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.3费诺编码,例6.3.1：设有一单符号离散信源对该信源编二进制费诺码。编码过程如表5.3.1。,第19页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.3费诺编码,例6.3.1该信源的熵为：平均码长为：对上述信源采用费诺编码的信息率为：编码效率为：本例中费诺编码有较高的编码效率。费诺码比较适合于每次分组概率都很接近的信源。特别是对每次分组概率都相等的信源进行编码时，可达到理想的编码效率。,第20页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.3费诺编码,例6.3.2：有一单符号离散无记忆信源对该信源编二进制费诺码，编码过程如表5.3.2。,第21页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.3费诺编码,例5.3.2信源熵为：H(X)=2.75(比特/符号)平均码长为：编码效率为=1。之所以如此，因为每次所分两组的概率恰好相等。,返回目录,第22页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.4哈夫曼编码,哈夫曼(Huffman)编码是一种效率比较高的变长无失真信源编码方法。,6.4.1编码步骤,6.4.2二进制哈夫曼编码,6.4.3m进制哈夫曼编码,第23页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.4.1编码步骤,(1)将信源符号按概率从大到小的顺序排列，令：p(x1)p(x2)p(xn)(2)信源的第一次缩减信源：给两个概率最小的信源符号p(xn1)和p(xn)各分配一个码位“0”和“1”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含(n1)个信源符号的新信源，用S1表示。(3)将缩减信源S1的符号仍按概率从大到小顺序排列，重复步骤(2)，得到只含(n2)个符号的缩减信源S2。(4)重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。,6.4哈夫曼编码,返回目录,第24页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.4.2二进制哈夫曼编码,例6.4.1设单符号离散无记忆信源如下，要求对信源编二进制哈夫曼码。编码过程如图5.4.1。在图中读取码字的时候，一定要从后向前读，此时编出来的码字才是可分离的异前置码。若从前向后读取码字，则码字不可分离。,6.4哈夫曼编码,第25页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.4.2二进制哈夫曼编码,例6.4.1,6.4哈夫曼编码,第26页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.4.2二进制哈夫曼编码,例6.4.1信源熵为：平均码长为：编码效率为：若采用定长编码，码长K=3，则编码效率：哈夫曼的编码效率提高了12.7%。,6.4哈夫曼编码,第27页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.4.2二进制哈夫曼编码,注意：哈夫曼的编法并不惟一。每次对缩减信源两个概率最小的符号分配“0”和“1”码元是任意的，所以可得到不同的码字。只要在各次缩减信源中保持码元分配的一致性，即能得到可分离码字。不同的码元分配，得到的具体码字不同，但码长ki不变，平均码长也不变，所以没有本质区别；缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方法上来说，这几个符号的次序可任意排列，编出的码都是正确的，但得到的码字不相同。不同的编法得到的码字长度ki也不尽相同。,6.4哈夫曼编码,第28页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.4.2二进制哈夫曼编码,例6.4.2：单符号离散无记忆信源用两种不同的方法对其编二进制哈夫曼码。方法一：合并后的新符号排在其它相同概率符号的后面。,6.4哈夫曼编码,第29页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.4.2二进制哈夫曼编码,例6.4.2：单符号离散无记忆信源用两种不同的方法对其编二进制哈夫曼码。方法二：合并后的新符号排在其它相同概率符号的前面。,6.4哈夫曼编码,第30页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.4.2二进制哈夫曼编码,例6.4.2：单符号信源编二进制哈夫曼码，编码效率主要决定于信源熵和平均码长之比。对相同的信源编码，其熵是一样的，采用不同的编法，得到的平均码长可能不同。平均码长越短，编码效率就越高。编法一的平均码长为：编法二的平均码长为：可见，本例两种编法的平均码长相同，所以编码效率相同。,6.4哈夫曼编码,第31页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.4.2二进制哈夫曼编码,讨论：码字长度的方差2：长度ki与平均码长之差的平方的数学期望，即：编法一码字长度方差：编法二码字长度方差：,哪种方法更好？,6.4哈夫曼编码,第32页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.4.2二进制哈夫曼编码,比较：第二种编码方法的码长方差要小许多。第二种编码方法的码长变化较小，比较接近于平均码长。第一种方法编出的5个码字有4种不同的码长；第二种方法编出的码长只有两种不同的码长；第二种编码方法更简单、更容易实现，所以更好。结论：在哈夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应使合并后的新符号尽可能排在靠前的位置，这样可使合并后的新符号重复编码次数减少，使短码得到充分利用。,返回目录,6.4哈夫曼编码,第33页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.4.3m进制哈夫曼编码,(1)“全树”概念,(2)举例,(3)结论,6.4哈夫曼编码,第34页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.4.3m进制哈夫曼编码,(1)“全树”概念定义：码树图中每个中间节点后续的枝数为m时称为全树；若有些节点的后续枝数不足m，就称为非全树。二进制码不存在非全树的情况，因为后续枝数是1时，这个枝就可以去掉使码字长度缩短。m进制编码：若所有码字构成全树，可分离的码字数（信源个数）必为m+k(m1)。k为信源缩减次数。若信源所含的符号数n不能构成m进制全树，必须增加s个不用的码字形成全树。显然s0(i=1,2,n)信源符号的累积分布函数为：所得累积分布函数为每台级的下界值，则其区间为0,1)左闭右开区间。F(a1)=0F(a2)=P(a1)F(a3)=P(a1)+P(a2)当A=0,1二元信源时：F(0)=0F(1)=P(0),6.6算术编码,第58页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.6.2累积分布函数F(s)及对应的区间,计算二元无记忆信源序列的累积分布函数初始时：在0,1)区间内由F(1)划分成二个子区间0,F(1)和F(1),1)，F(1)=P(0)。子区间0,F(1)的宽度为：A(0)=P(0)，对应于信源符号“0”；子区间F(1),1)的宽度为：A(1)=P(1)，对应于信源符号“1”；若输入符号序列的第一个符号为s=“0”，落入0,F(1)区间，得累积分布函数F(s=“0”)=F(0)=0；,图示,6.6算术编码,第59页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.6.2累积分布函数F(s)及对应的区间,计算二元无记忆信源序列的累积分布函数输入第二个符号为“1”，s=“01”s=“01”所对应的区间是在区间0,F(1)中进行分割；符号序列“00”对应的区间宽度为：A(00)=A(0)P(0)=P(0)P(0)=P(00)对应的区间为：0,F(s=“01”)符号序列“01”对应的区间宽度为：A(01)=A(0)P(1)=P(0)P(1)=P(01)对应的区间为：F(s=“01”),F(1)累积分布函数：F(s=“01”)=P(0)P(0)=P(00),图示,6.6算术编码,第60页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.6.2累积分布函数F(s)及对应的区间,计算二元无记忆信源序列的累积分布函数输入第三个符号为“1”：输入序列可记做s1=“011”，对应的区间是对区间F(s),F(1)进行分割；序列s0=“010”对应的区间宽度为：A(s=“010”)=A(s=“01”)P(0)=A(s)P(0)其对应的区间为：F(s),F(s)+A(s)P(0)序列s1=“011”对应的区间宽度为：A(s=“011”)=A(s)P(1)其对应的区间为：F(s)+A(s)P(0),F(1)符号序列s1=“011”的累积分布函数为：F(s1)=F(s)+A(s)P(0)若第三个符号输入为“0”，符号序列s0=“010”的区间下界值仍为F(s)，得符号序列s0=“010”的累积分布函数为F(s0)=F(s)。,图示,6.6算术编码,第61页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.6.2累积分布函数F(s)及对应的区间,计算二元无记忆信源序列的累积分布函数归纳当已知前面输入符号序列为s，若接着再输入一个符号“0”，序列s0的累积分布函数为：F(s0)=F(s)对应区间宽度为：A(s0)=A(s)P(0)若接着输入的一个符号是“1”，序列的累积分布函数为：F(s1)=F(s)+A(s)P(0)对应区间宽度为：A(s1)=A(s)P(1),图示,6.6算术编码,第62页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.6.2累积分布函数F(s)及对应的区间,计算二元无记忆信源序列的累积分布函数归纳符号序列对应的区间宽度A(s=“0”)=P(0)A(s=“1”)=1A(0)=P(1)A(s=“00”)=P(00)=A(0)P(0)=P(0)P(0)A(s=“01”)=P(01)=A(0)P(1)=P(0)P(1)A(s=“10”)=P(10)=A(1)P(0)=P(1)P(0)A(s=“11”)=P(11)=A(1)P(1)=P(1)P(1)A(s=“010”)=A(01)P(0)=P(01)P(0)P(010)A(s=“011”)=A(01)P(1)=P(01)P(1)=P(011)信源符号序列s所对应区间的宽度等于符号序列s的概率P(s)。,返回目录,6.6算术编码,第63页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.6.3信源序列累积分布函数的递推公式,6.6算术编码,二元信源符号序列的累积分布函数的递推公式F(sr)=F(s)+P(s)F(r)(r=0,1)(5.6.1)sr表示已知前面信源符号序列为s，接着再输入符号为rF(0)=0，F(1)=P(0)F(s0)=F(s)F(s1)=F(s)+P(s)F(1)=F(s)+P(s)P(0)A(sr)=P(sr)=P(s)P(r)(r=0,1)(5.6.2)A(s0)=P(s0)=P(s)P(0)A(s1)=P(s1)=P(s)P(1),第64页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,举例：已输入二元符号序列为s=“011”，接着再输入符号为“1”，得序列累积分布函数为：F(s1)=F(0111)=F(s=“011”)+P(011)P(0)=F(s=“01”)+P(01)P(0)+P(011)P(0)=F(s=“0”)+P(0)P(0)+P(01)P(0)+P(011)P(0)=0+P(00)+P(010)+P(0110)对应的区间宽度为：A(s1)=P(s=“011”)P(1)=P(011)P(1)=P(0111)F(s1)=F(s)+P(s)P(0)A(s1)=P(s1)=P(s)P(1),6.6.3信源序列累积分布函数的递推公式,图示,6.6算术编码,第65页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,上述整个分析过程可用图5.6.1描述,6.6.3信源序列累积分布函数的递推公式,图示返回,6.6算术编码,第66页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,式(5.6.1)和(5.6.2)是可递推运算，在实际中，只需两个存储器，把P(s)和F(s)存下来，然后，根据输入符号和式(5.6.1)、(5.6.2)更新两个存储器中的数值。因此在编码过程中，每输入一个符号要进行乘法和加法运算，所以称为算术编码。F(sr)=F(s)+P(s)F(r)(r=0,1)(5.6.1)A(sr)=P(sr)=P(s)P(r)(r=0,1)(5.6.2),6.6.3信源序列累积分布函数的递推公式,返回目录,6.6算术编码,第67页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,通过关于信源符号序列的累积分布函数的计算，把区间分割成许多小区间，不同的信源符号序列对应不同的区间。可取小区间内的一点来代表这序列。编码方法：将符号序列的累积分布函数写成二进位的小数，取小数点后k位，若后面有尾数，就进位到第k位，这样得到的一个数C，并使k满足：举例：,6.6.4算术编码方法,6.6算术编码,第68页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,编码效率算术编码的编码效率很高。当信源符号序列很长时，L很大时，平均码长接近信源的熵。,6.6.4算术编码方法,返回目录,6.6算术编码,第69页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,译码就是一系列比较过程，每一步比较CF(s)与P(s)P(0)。F(s0)=F(s)F(s1)=F(s)+P(s)P(0)s前面已译出的序列串P(s)序列串s对应的宽度F(s)是序列串s的累积分布函数，即为s对应区间的下界；P(s)P(0)是此区间内下一个输入为符号“0”所占的子区间宽度；若CF(s)P(s)P(0)则译输出符号为“1”。,6.6.5算术编码的译码,6.6算术编码,第70页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,举例：设二元无记忆信源S=0,1，其P(0)=1/4，P(1)=3/4。对二元序列11111100做算术编码。解：P(s=11111100)=P2(0)P6(1)=(1/4)2(3/4)6F(sr)=F(s)+P(s)F(r)F(s0)=F(s)F(s1)=F(s)+P(s)F(1)=F(s)+P(s)P(0)F(s)=P(0)+P(1)P(0)+P(1)2P(0)+P(1)3P(0)+P(1)4P(0)+P(1)5P(0)=0.82202=0.110100100111得C0.1101010得s的码字为1101010。编码效率：,6.6.5算术编码的译码,6.6算术编码,第71页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,举例：,6.6.5算术编码的译码,返回目录,6.6算术编码,第72页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,6.7LZ(Lempel-Ziv)码,(1)通用编码和统计编码,(2)基于字典的编码方法,(3)LZ码的原理,(4)举例,(5)计算LZ78码的平均码长的界限,第73页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,(1)通用编码和统计编码统计编码需要精确知道信源的概率分布pi。统计编码对于实际分布与假设分布的偏差非常灵敏；许多场合不知道实际信源的统计特性，或者信源不存在统计特性。通用信源编码：与信源统计特性无关而且有效的编码方法。,6.7LZ(Lempel-Ziv)码,返回目录,第74页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,(2)基于字典的编码方法LZ码是1977年两位以色列研究人员，齐费(J.Ziv)和兰佩尔(A.Lempel)提出的，它是一种基于字典的编码方法。至今，几乎日常使用的所有通用压缩工具，象ARJ，PKZip，WinZip，LHArc，RAR，GZip，ACE，ZOO，TurboZip，Compress，JAR甚至许多硬件如网络设备中内置的压缩算法，都可以最终归结为这两个以色列人的杰出贡献。字典模型的思路：在对信息进行压缩（说）和解压缩（听）的过程中都对字典进行查询操作。字典压缩模型正是基于这一思路设计实现的。,6.7LZ(Lempel-Ziv)码,第75页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,(2)基于字典的编码方法静态字典模型的算法：对一篇中文文章压缩，已有一本现代汉语词典。首先扫描要压缩的文章，对其中的句子进行分词操作，对每一个独立的词语查找它的出现位置，如果找到，就输出页码和该词在该页中的序号，如果没有找到，就输出一个新词。静态字典模型的缺点适应性不强，必须为每类不同的信息建立不同的字典；必须维护信息量并不算小的字典，这一额外的信息量影响了最终的压缩效果。自适应字典模型：把已经编码过的信息作为字典，如果要编码的字符串曾经出现过，就输出该字符串的出现位置及长度，否则输出新的字符串。几乎所有通用的字典模型都使用这种方式。,6.7LZ(Lempel-Ziv)码,第76页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,(2)基于字典的编码方法根据这一思路，你能从下面这幅图中读出其中包含的原始信息吗？是“吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮”。,6.7LZ(Lempel-Ziv)码,返回目录,第77页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,(3)LZ码的原理LZ78的基本算法：将长度不同的符号串编成一个个新的短语（单词），形成短语字典的索引表，短语字典由前面已见到的文本来定义，是一个潜在的无限列表。LZ78的编码算法：设信源符号集A=a0,a1,a2,aq1共q个符号设输入信源序列为s1,s2,s3,snsiA将此序列分成不同的C段。分段规则：尽可能取最少个连着的信源符号，并保证各段都不相同。不同段内的信源符号可看成一短语，可得不同段对应的短语字典表.,6.7LZ(Lempel-Ziv)码,第78页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,(3)LZ码的原理LZ78的基本算法：将长度不同的符号串编成一个个新的短语（单词），形成短语字典的索引表，短语字典由前面已见到的文本来定义，是一个潜在的无限列表。LZ78的编码算法：码字组成：段号后面一个符号二元码：段号码长：，每个信源符号码长：单符号码字的段号为0。n信源序列的输入长度C(n)输入长度为n的信源序列被分解成字符片段的数目,6.7LZ(Lempel-Ziv)码,返回目录,第79页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,(4)举例设q=4，信源序列为：a0a0a2a3a1a1a0a0a0a3a2分段为：a0,a0a2,a3,a1,a1a0,a0a0,a3a2共7段编码字典如下表：字典共7段，段号l=3位二元码符号；q=4，每个符号需要2位二元码符号：a000，a101，a210，a311。得序列符号：00000001100001100001100000010001110,6.7LZ(Lempel-Ziv)码,码符号序列译码：一边译码一边又建成字典表，字典表无需传送。在本例中，二元序列共35位，似乎比不编码还坏。当序列n增长时段内短语的符号数也增长，尤其是某些符号重复出现的话，编码效率将会提高。,返回目录,第80页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,(5)计算LZ78码的平均码长的界限信源符号序列长度n；段的数目：C(n)；每段二元码符号长度：每个信源符号码长：每段二元码符号数：n长信源符号序列数：平均每个信源符号所需码长：因此：,6.7LZ(Lempel-Ziv)码,第81页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,(5)计算LZ78码的平均码长的界限设长度为k的段有qk种，最长的段的长度为K，所有长度K的段型都存在，则：,6.7LZ(Lempel-Ziv)码,返回,第82页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,(5)计算LZ78码的平均码长的界限平稳无记忆m元信源序列，设信源pi(i=0,1,2,q1)当K很大时，典型段中ai出现piK个，这种段型有NK种，则：,6.7LZ(Lempel-Ziv)码,第83页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,(5)计算LZ78码的平均码长的界限结论：LZ78码的平均码长仍以信源熵为极限，当n很长时（即K很大时），平均码长渐进地接近信源的熵。,6.7LZ(Lempel-Ziv)码,返回目录,第84页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,(1)什么是LZW码？(2)LZW码的格式规定(3)LZW码的编码方法(4)LZW码的译码(5)LZW码的应用,6.8LZW码,第85页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,(1)什么是LZW码？LZW算法是韦尔奇（T.A.Welch）对LZ算法的一种修正，它保留了LZ算法原有的自适应性。为了使长短不一的“单词”更便于处理，专门为“单词”建立了一种通用的格式。(2)LZW码的格式规定每个“单词”均由前缀字符串和尾字符串两部分组成。前缀字符串为字典中已有的“单词”，尾字符是本“单词”的最后一个字符.对本身已经是单节的“单词”，没有前缀词时则在前面加上一个空前缀，并规定字典最后一个“单词”为“空”。,6.8LZW码,返回目录,第86页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,(3)LZW码的编码方法“单词”的内容用3个字节表示：前缀字符串(2字节)尾字符(1字节),6.8LZW码,第87页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,(3)LZW码的编码方法初始化时将字典的前256个单元依次分给0 x00至0 xFF的256个字节字符;每读入一个字符W1，先在字典中查找，若这个字符字典已有，则更新当前词为W1，且以当前词W1做前缀，再读入一个字符W2做尾字符，组成一个单词W1W2，再次在字典中查找，若字典中没有W1W2，则输出W1位置码，并将W1W2添加到字典中。然后将W2做当前词，重复以上步骤，直到没有字符读入时，完成编码.LZW算法在储存压缩文件时，不需要保存字典，是一种自适应的算法。,6.8LZW码,返回目录,第88页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,(4)LZW码的译码LZW的译码算法同样是基于字典的自适应算法；LZW编码的输出压缩文件中仅包含码字，并不包含字典，译码过程同样为一边译码，一边生成字典。,6.8LZW码,返回目录,第89页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,(5)LZW码的应用LZW码的优点是一种通用编码方法，不依赖信源概率分布；编码方法简单，编码速度快；具有自适应性。目前市场上常用的Winzip，ARJ，ARC等著名压缩软件都是LZW码的改进与应用。,6.8LZW码,返回目录,第90页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,我们学习了7种信源编码：香农编码、费诺编码、哈夫曼编码、游程编码、算术编码、LZ编码、LZW编码。游程编码和算术编码是非分组编码；游程编码是限失真信源编码。本章介绍的都是离散信源变长编码。优点：提高编码效率；缺点：需要大量缓冲设备来存储这些变长码，然后再以恒定的码率进行传送；在传输的过程中如果出现了误码，容易引起错误扩散，所以要求有优质的信道。有时为了得到较高的编码效率，先采用某种正交变换，解除或减弱信源符号间的相关性，然后再进行信源编码；有时则利用信源符号间的相关性直接编码。,6.9信源编码总结,第91页,2020/5/23,DepartmentofElectronicsandInformation,NCUTSongPeng,THEEND,