第三章数据压缩和信源编码讲义课件

*13.1 3.1 等长码等长码3.2 3.2 变长编码变长编码3.3 3.3 哈夫曼码哈夫曼码3.4 3.4 香农码和费诺玛香农码和费诺玛*2 为为了了实实现现高高质质量量、高高效效率率的的通通信信，引引入入了了信信源源编编码码和和信信道道编编码码。信信源源编编码码和和信信道道编编码码主主要要需需要解决以下两个问题。要解决以下两个问题。提高传输效率提高传输效率 增强通信的可靠性增强通信的可靠性 数据压缩和信源编码数据压缩和信源编码 *3编码编码：将一定的符号，数字或字母按一定的要求编：将一定的符号，数字或字母按一定的要求编成不同的序列，表示出一定的意义称为编码。成不同的序列，表示出一定的意义称为编码。编码、信源编码、信道编码编码、信源编码、信道编码编码分为编码分为信源编码信源编码和和信道编码信道编码，其中信源编码又，其中信源编码又分为分为无失真信源编码无失真信源编码和和限失真信源编码限失真信源编码。无失真信源编码无失真信源编码：适用于离散信源或数字信号。：适用于离散信源或数字信号。限失真信源编码限失真信源编码：主要用于连续信源或模拟信号，：主要用于连续信源或模拟信号，如语音、图像等信号的数字处理。如语音、图像等信号的数字处理。*4第一极限定理第一极限定理:无失真信源编码定理无失真信源编码定理.第二极限定理第二极限定理:信道编码定理（包括离散和连信道编码定理（包括离散和连 续信道）续信道）.第三极限定理第三极限定理:限失真信源编码定理限失真信源编码定理.香农信息论三大定理香农信息论三大定理 *5信源编码的信源编码的主要任务主要任务是什么是什么?由于信源符号之间存在分布由于信源符号之间存在分布不均匀不均匀和和相关性相关性，使，使得信源存在冗余度，信源编码的主要任务就是减少得信源存在冗余度，信源编码的主要任务就是减少冗余，提高编码效率。具体说，就是针对信源输出冗余，提高编码效率。具体说，就是针对信源输出符号序列的统计特性，寻找一定的方法把信源输出符号序列的统计特性，寻找一定的方法把信源输出符号序列变换为最短的码字序列。符号序列变换为最短的码字序列。信源编码信源编码 *6 信源编码的信源编码的基本途径基本途径是什么是什么?信源编码的基本途径有两个，一是使序列中的信源编码的基本途径有两个，一是使序列中的各个符号尽可能地互相独立，即解除相关性；各个符号尽可能地互相独立，即解除相关性；二是使编码中各个符号出现的概率尽可能地相二是使编码中各个符号出现的概率尽可能地相等，即概率均匀化。等，即概率均匀化。信源编码的信源编码的基础基础是什么是什么?信源编码的信源编码的基础基础是：两个编码定理，即是：两个编码定理，即无失真编码定理和限失真编码定理。无失真编码定理和限失真编码定理。信源编码信源编码 *7信源编码信源编码：以以提高通信提高通信有效性有效性有效性有效性为目的为目的,针对信源的编码针对信源的编码.能更加有能更加有效地传输、存储信息。效地传输、存储信息。在不失真或允许一定失真条件下在不失真或允许一定失真条件下,如何用尽可能如何用尽可能少的符号来传送信源信息少的符号来传送信源信息,以便提高信息传输率以便提高信息传输率。通通常通过压缩信源的冗余度来实现。常通过压缩信源的冗余度来实现。采用的一般方法是采用的一般方法是压缩每个信源符号的平均比特压缩每个信源符号的平均比特数或信源的码率。数或信源的码率。即同样多的信息用较少的码率传送即同样多的信息用较少的码率传送,使单位时间内传送的平均信息量增加使单位时间内传送的平均信息量增加,从而提高通信从而提高通信的有效性。的有效性。信源编码信源编码*8 说明说明：（1 1）无失真编码或可逆编码只适用于离散信源。）无失真编码或可逆编码只适用于离散信源。（2 2）对于连续信源，编成代码后就无法无失真地）对于连续信源，编成代码后就无法无失真地恢复原来的连续值，因为后者的取值可有无限多恢复原来的连续值，因为后者的取值可有无限多个。此时只能根据限失真编码定理进行限失真编个。此时只能根据限失真编码定理进行限失真编码码 。信源编码信源编码编码定理证明：编码定理证明：（1 1）必存在一种编码方法，使代码的平均长度可）必存在一种编码方法，使代码的平均长度可 任意接近但不能低于符号熵任意接近但不能低于符号熵（2 2）达到这目标的途径，就是使概率与码长匹配。）达到这目标的途径，就是使概率与码长匹配。*9信道编码：信道编码：是以是以提高信息传输的提高信息传输的可靠性可靠性可靠性可靠性为目的的编码。在信道为目的的编码。在信道受干扰的情况下如何增加信号的受干扰的情况下如何增加信号的抗干扰能力抗干扰能力抗干扰能力抗干扰能力,同时又同时又使得信息传输率最大。通常通过增加信源的冗余度使得信息传输率最大。通常通过增加信源的冗余度来实现。采用的一般方法是增大码率来实现。采用的一般方法是增大码率/带宽。与信源带宽。与信源编码正好相反。编码正好相反。密码：密码：是以提高通信系统的是以提高通信系统的安全性安全性安全性安全性为目的的编码。通常通为目的的编码。通常通过加密和解密来实现。从信息论的观点出发过加密和解密来实现。从信息论的观点出发“加密加密”可视为增熵的过程可视为增熵的过程,“解密解密”可视为减熵的过程。可视为减熵的过程。信道编码、密码信道编码、密码*10信源编码包括两个功能：信源编码包括两个功能：（1 1）将信源符号变换成适合信道传输的符号；）将信源符号变换成适合信道传输的符号；（2 2）压缩信源冗余度，提高传输效率。压缩信源冗余度，提高传输效率。提高传输效率往往削弱了其抗干扰能力。提高传输效率往往削弱了其抗干扰能力。提高抗提高抗干扰能力往往是以降低信息传输效率为代价。干扰能力往往是以降低信息传输效率为代价。*11l由信源的渐近等分性导出了信源编码定理：由信源的渐近等分性导出了信源编码定理：只要只要编码的码率大于编码的码率大于信源的熵（或熵率），则必存在信源的熵（或熵率），则必存在编译码方案编译码方案,使当被编码的信源分组长趋于无穷时使当被编码的信源分组长趋于无穷时,译译码误差概率可以充分小码误差概率可以充分小,这解决了最优码的存在性问题。这解决了最优码的存在性问题。l怎样构造最优码？怎样构造最优码？信源编码信源编码*12信源编码的分类：离散信源编码、连续信源编码和相信源编码的分类：离散信源编码、连续信源编码和相关信源编码三类关信源编码三类离散信源编码离散信源编码：独立信源编码，可做到无失真编独立信源编码，可做到无失真编码；码；连续信源编码连续信源编码：独立信源编码，只能做到限失真独立信源编码，只能做到限失真信源编码信源编码；相关信源编码相关信源编码：非独立信源编码。非独立信源编码。信源编码的分类信源编码的分类*13 冗余度压缩编码冗余度压缩编码:是可逆压缩，经编译码后可以无失真地恢复。是可逆压缩，经编译码后可以无失真地恢复。基本途径：基本途径：压缩信源的冗余度，即压缩信源的冗余度，即 1)1)去除码符号间的相关性；去除码符号间的相关性；2)2)使码符号等概分布。使码符号等概分布。信源编码的分类信源编码的分类*14熵压缩编码：是不可逆压缩熵压缩编码：是不可逆压缩 压缩超过一定限度，必然带来失真压缩超过一定限度，必然带来失真,允许的失真允许的失真越大，压缩的比例越大越大，压缩的比例越大,译码时能按一定的失真容许译码时能按一定的失真容许度恢复，保留尽可能多的信息。度恢复，保留尽可能多的信息。信源编码的分类信源编码的分类*15l 信源编码将信源编码将信源符号序列信源符号序列按一定的数学规律映射成按一定的数学规律映射成码码符号序列符号序列。是从信源符号集到码符号集的一种映射，它。是从信源符号集到码符号集的一种映射，它把信源输出的符号变换成码元序列。把信源输出的符号变换成码元序列。信宿信宿信道信道信源信源编码器编码器译码器译码器 信源编码器模型信源编码器模型译码是从码符号到信源符号的映射。若要实现无失译码是从码符号到信源符号的映射。若要实现无失真编码，这种映射必须是一一对应的、可逆的。真编码，这种映射必须是一一对应的、可逆的。信源编码器模型信源编码器模型*16编码器编码器码字码字l 将信源符号集中的符号将信源符号集中的符号（或者长为（或者长为n的信源符号序的信源符号序列）映射成由码符号列）映射成由码符号 组成的长度为组成的长度为 的一一对应的码的一一对应的码符号序列符号序列 。信源编码器的模型信源编码器的模型*17l编码器输出的码符号序列编码器输出的码符号序列 称为称为码字码字；长度；长度 称为称为码字长度，简称码字长度，简称码长码长；全体码字的集合记为；全体码字的集合记为C C。l将信源符号集中的每个信源符号将信源符号集中的每个信源符号 依照固定的码表依照固定的码表映射成某一个码字映射成某一个码字 ，这样的码称为，这样的码称为分组码分组码。l只有分组码才有对应的码表，而非分组码中则不存在只有分组码才有对应的码表，而非分组码中则不存在码表。码表。对于同一个信源，编码方法是多种的。对于同一个信源，编码方法是多种的。分组码分组码*18 3.变长码变长码若码字集合若码字集合C中的所有码字中的所有码字cm(m=1,2,M)，其码长，其码长不都相同不都相同，称码称码C为变长码。为变长码。2.等长码等长码在一组码字集合在一组码字集合C中的所有码字中的所有码字cm(m=1,2,M)，其码长，其码长都相都相同同，则称这组码，则称这组码C为等长码。为等长码。1.二元码二元码若若码码符符号号集集为为0，1，则则码码字字就就是是二二元元序序列列，称称为为二二元元码码,二二元元码码通通过过二二进进制制信信道道传传输输，这这是是数数字字通通信信和和计计算算机机通通信信中中最最常常见见的一种码。的一种码。码的分类码的分类*19 4.非奇异码非奇异码从信源消息到码字的映射从信源消息到码字的映射是一一对应的是一一对应的，每一个不同的信源消，每一个不同的信源消息都用不同的码字对其编码。息都用不同的码字对其编码。非奇异码非奇异码码中所有码字互不相同码中所有码字互不相同.5.奇异码奇异码从信源消息到码字的映射从信源消息到码字的映射不是一一对应的不是一一对应的。奇异码不具备惟。奇异码不具备惟一可译性。一可译性。原码的原码的N次扩展码是将信源作次扩展码是将信源作N次扩展得到的新信源符号序列次扩展得到的新信源符号序列u（N）=u1 uN =(u11 u12 u1L)(uN1 uN2 uNL)，对应码符号序列对应码符号序列c（N）=c1 cN=(c11 c12 c1n)(cN1 cN2 cNn)，记集合记集合 C(N)=c1(N),c2(N),即原码即原码C的的N次扩展码。次扩展码。6.原码原码C的的N次扩展码次扩展码*20对于等长码，若原码是惟一可译码，则它的对于等长码，若原码是惟一可译码，则它的N N次扩展码也是惟次扩展码也是惟一可译的，而对于变长码则不尽然。一可译的，而对于变长码则不尽然。7.惟一可译码惟一可译码定义定义 若任意一串有限长的码符号序列只能被惟一地译为对应若任意一串有限长的码符号序列只能被惟一地译为对应的信源符号序列，则称此码为的信源符号序列，则称此码为惟一可译码惟一可译码。l 惟一可译码惟一可译码应当满足的条件应当满足的条件码字与信源符号一一对应码字与信源符号一一对应2)不同的信源符号序列对应不同的码字序列。不同的信源符号序列对应不同的码字序列。1)*21 8.即时码即时码定义定义 对于码字对于码字c=c1 c2 cn,称称c、=c1 c2 ci(i0，只要满足，只要满足 则当则当N足够大时，可实现几乎无失真编码，即译码错误足够大时，可实现几乎无失真编码，即译码错误概率概率 PE 为任意小；为任意小；（D进制）进制）反之，如果反之，如果 则不可能实现无失真编码，当则不可能实现无失真编码，当N足够大时，译码错误概足够大时，译码错误概率率 PE 为为1。等长编码定理等长编码定理*42等长编码的等长编码的效率效率（D进制）进制）为使编码真正有效，必须增大信源序列的分组长为使编码真正有效，必须增大信源序列的分组长度度N，这就会使编、译码的延时增大，同时也会使编、，这就会使编、译码的延时增大，同时也会使编、译码器的复杂程度增加，因此，等长编码在冗余度压译码器的复杂程度增加，因此，等长编码在冗余度压缩编码中的理论意义远大于其实用价值。缩编码中的理论意义远大于其实用价值。等长编码定理等长编码定理*43 如果无论怎样编码都是有错编码，但可以使如果无论怎样编码都是有错编码，但可以使当地编码和译码使译码错误的概率当地编码和译码使译码错误的概率pe任意小，这任意小，这就是所谓就是所谓“渐进无错编码渐进无错编码”。等长编码定理等长编码定理*44等长编码定理等长编码定理*45等长编码定理等长编码定理*46l等长编码定理同样也适用于离散平稳有记忆信源，差等长编码定理同样也适用于离散平稳有记忆信源，差别是要将信源熵别是要将信源熵 改为极限熵改为极限熵 。l可以验证，对等长信源编码来说，要想实现无失真信可以验证，对等长信源编码来说，要想实现无失真信源编码，源编码，N常常要取非常大的值常常要取非常大的值，这在实际应用中很，这在实际应用中很 难实现。难实现。等长编码在引入失真的前提下，还需要取很长等长编码在引入失真的前提下，还需要取很长的信源序列进行编码，才能达到较高的编码效率。的信源序列进行编码，才能达到较高的编码效率。既要不失真，又要很高的编码效率，只能采用变长既要不失真，又要很高的编码效率，只能采用变长编码。编码。等长编码定理等长编码定理*47 对对等等长长码码的的讨讨论论是是在在N足足够够大大的的条条件件下下得得到到的的结结论论，当当N为为有有限限值值时时，则则总总会会带带来来一一定定程程度度的的失失真真。对对于于变变长长码码，往往往往在在N不不是是很很大大的的情情况况下下就就可可编编出出高高效且无失真的码。效且无失真的码。变变长长码码也也要要求求原原码码的的任任意意N次次扩扩展展码码也也是是惟惟一一可可译译的的。变变长长码码分分为为即即时时码码和和延延长长码码，为为保保证证即即时时译译码码，要要求求变变长长惟惟一一可可译译码码采采用用即即时时码码。对对于于变变长长码码，要要求求整个码集的平均码长力求最小，此时编码效率最高。整个码集的平均码长力求最小，此时编码效率最高。当当信信源源较较复复杂杂,直直接接画画码码树树就就比比较较复复杂杂。针针对对这这一一问问题题，在在数数学学上上给给出出一一个个与与码码树树等等效效的的，表表达达码码字字可分离的充要条件，即著名的克拉夫特不等式。可分离的充要条件，即著名的克拉夫特不等式。变长编码变长编码*48Kraft定理定理 即时码存在的充要条件即时码存在的充要条件是是McMillan定理定理 惟一可译码存在的充要条件惟一可译码存在的充要条件是是Kraft不等式和不等式和McMillan不等式不等式*49l上述定理是上述定理是存在性定理存在性定理当满足当满足KraftKraft（或（或McMillanMcMillan）不等式时，必然可）不等式时，必然可以构造出即时码（或惟一可译码），否则不能构造以构造出即时码（或惟一可译码），否则不能构造出即时码（或惟一可译码）。但满足出即时码（或惟一可译码）。但满足KraftKraft不等式不等式的码长集未必是最优的，即它的平均码长未必是最的码长集未必是最优的，即它的平均码长未必是最小的。小的。该定理该定理不能不能作为判断一种码是否是即时码（或惟作为判断一种码是否是即时码（或惟一可译码）的判断依据。一可译码）的判断依据。KraftKraft不等式和不等式和McMillanMcMillan不等式不等式*50码符号码符号/信源符号信源符号l 平均码长平均码长 对于给定的信源和码符号集，若有一个惟一可译码，对于给定的信源和码符号集，若有一个惟一可译码，其平均长度其平均长度 小于所有其它惟一可译码小于所有其它惟一可译码,则称这种码为则称这种码为最佳码最佳码或或紧致码紧致码。所谓所谓最佳最佳：是指在所有可能的编码方法中，：是指在所有可能的编码方法中，其编其编码得到的平均码长最短码得到的平均码长最短。*51香农第一定理香农第一定理 设离散无记忆信源的熵为设离散无记忆信源的熵为H H(X X)，它的，它的N N 次扩展信次扩展信源为源为 ，对扩展信源，对扩展信源 进行编码进行编码（D D进制）进制），总可以，总可以找到一种编码方法，构成惟一可译码，使平均码长满找到一种编码方法，构成惟一可译码，使平均码长满足足 变长编码不要求所有码字长度相同变长编码不要求所有码字长度相同,但希望平均码长最小但希望平均码长最小,变长无失真信源编码定理给出了在无失真编码的前提下平均变长无失真信源编码定理给出了在无失真编码的前提下平均码长的界限。码长的界限。变长无失真信源编码定理变长无失真信源编码定理*52 变长编码采用即时码变长编码采用即时码,力求平均码长最小力求平均码长最小,此时此时编码效率最高，信源的冗余得到最大程度的压缩。编码效率最高，信源的冗余得到最大程度的压缩。将概率大的信息符号编以短的码字，概率小的符号将概率大的信息符号编以短的码字，概率小的符号编以长的码字，可使得平均码字长度最短。编以长的码字，可使得平均码字长度最短。冗余度冗余度*53 对于同一种信源，对于同一种信源，香农编码不能使平均码长达到最小，因香农编码不能使平均码长达到最小，因此不是最佳编码。三种编码法中此不是最佳编码。三种编码法中,以以香香农编码法的编码效率最低，农编码法的编码效率最低，法诺编码法也不是一种最佳编码法，但用这种方法有时候也能法诺编码法也不是一种最佳编码法，但用这种方法有时候也能找到最优码。找到最优码。一般情况下一般情况下,哈夫曼编码法得到的平均码长哈夫曼编码法得到的平均码长 最短，即最短，即编编码效率码效率 最高。最高。香农（香农（Shannon）编码法）编码法法诺法诺(Fano)编码法编码法哈夫曼哈夫曼(Huffman)编码法编码法变长编码法变长编码法变长码的编码方法变长码的编码方法*54香农码编码步骤：香农码编码步骤：1.将信源符号按概率从大到小顺序排列，方便起见，令将信源符号按概率从大到小顺序排列，方便起见，令 2.按下式计算第按下式计算第i个符号对应的码字的码长个符号对应的码字的码长3.计算第计算第i个符号的累加概率个符号的累加概率4.将累加概率变换成将累加概率变换成二进制小数二进制小数，取小数点后，取小数点后li位位数作为数作为 第第i个符号的码字。个符号的码字。(1)(1)香农（香农（ShannonShannon）编码）编码*550.017例例 对如下信源进行对如下信源进行香农香农编码编码信源符号符号概率累加概率码长码字x10.2002.3430000.190.22.4130010.180.392.483011x40.170.572.563100 x50.150.742.743101x60.100.893.3441110 x70.996.661111110 x2x3*56 平均码长平均码长信源熵信源熵结论：结论：1)2)香农码是即时码，但冗余度稍大，不是最佳码。香农码是即时码，但冗余度稍大，不是最佳码。编码效率编码效率*57 在众多变长码中，哈夫曼码是效率最高的变长在众多变长码中，哈夫曼码是效率最高的变长无失真信源编码方法，它是一种逐个符号的编码方无失真信源编码方法，它是一种逐个符号的编码方法，是在编码理论指导下法，是在编码理论指导下平均码长最短的码平均码长最短的码。原理：原理：构造一个码树。构造一个码树。(2)(2)哈夫曼哈夫曼(Huffman)(Huffman)编码编码*581.1.将信源符号按概率从大到小的顺序排列，令将信源符号按概率从大到小的顺序排列，令2.2.给两个概率最小的信源符号给两个概率最小的信源符号xn-1和和xn各分配一个码元各分配一个码元“0 0”和和“1 1”，并将这两个信源符号合并成一个新，并将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含率，结果得到一个只包含n1个信源符号的新信源。个信源符号的新信源。称为称为信源的第一次缩减信源信源的第一次缩减信源，用，用X X1 1表示。表示。哈夫曼码编码步骤：哈夫曼码编码步骤：(2)(2)哈夫曼哈夫曼(Huffman)(Huffman)编码编码*59 3.3.将缩减信源将缩减信源X1的符号仍按概率从大到小顺序排的符号仍按概率从大到小顺序排 列，列，重复步骤重复步骤2 2，得到只含，得到只含n2个符号的缩减信源个符号的缩减信源X2。4.4.重复上述步骤，直至缩减信源只剩两个符号为重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为止，此时所剩两个符号的概率之和必为1 1。然后从最。然后从最后一级缩减信源开始，依编码路径向前返回，就得后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。到各信源符号所对应的码字。(2)(2)哈夫曼哈夫曼(Huffman)(Huffman)编码编码*6001010101码符号码符号/信源符号信源符号*6101010101码符号码符号/信源符号信源符号*62讨论：讨论：1)1)两种方法平均码长相等。两种方法平均码长相等。2)2)计算两种码的码长方差：计算两种码的码长方差：第二种方法编出的码码字长度变化较小，便于实现。第二种方法编出的码码字长度变化较小，便于实现。*63解解 哈夫曼编码结果：哈夫曼编码结果：例例 对如下信源进行哈夫曼编码对如下信源进行哈夫曼编码*64l平均码长为平均码长为l信源熵为信源熵为l编码效率为编码效率为*65注：哈夫曼编码后的码字不是惟一的。注：哈夫曼编码后的码字不是惟一的。1 1）每次对缩减信源两个概率最小的符号）每次对缩减信源两个概率最小的符号分配分配“0 0”或或“1 1”码码元是任意的元是任意的，所以可得到不同的码字。不同的码元分配，得，所以可得到不同的码字。不同的码元分配，得到的具体码字不同，但码长不变，平均码长也不变，所以没到的具体码字不同，但码长不变，平均码长也不变，所以没有本质区别。有本质区别。2 2）缩减信源时，）缩减信源时，若合并后的概率与其它概率相等，这几个概若合并后的概率与其它概率相等，这几个概率的次序可任意排列率的次序可任意排列，但得到的码字不相同，但得到的码字不相同,对应的码长也对应的码长也不相同不相同,但平均码长不变。但平均码长不变。哈夫曼编码哈夫曼编码*66 第一，哈夫曼编码实际上构造了一个码树，码第一，哈夫曼编码实际上构造了一个码树，码树从最上层的端点开始构造，直到树根结束，最后树从最上层的端点开始构造，直到树根结束，最后得到一个横放的码树，因此，编出的码是即时码。得到一个横放的码树，因此，编出的码是即时码。第二，哈夫曼编码采用概率匹配方法来决定各第二，哈夫曼编码采用概率匹配方法来决定各码字的码长，概率大的符号对应于短码，概率小的码字的码长，概率大的符号对应于短码，概率小的符号对应于长码，从而使平均码长最小。符号对应于长码，从而使平均码长最小。第三，每次对概率最小的两个符号求概率之和第三，每次对概率最小的两个符号求概率之和形成缩减信源时形成缩减信源时,就构造出两个树枝，由于给两个树就构造出两个树枝，由于给两个树枝赋码元时是任意的枝赋码元时是任意的,因此编出的码字并不惟一。因此编出的码字并不惟一。哈夫曼编码的基本特点哈夫曼编码的基本特点*67 哈夫曼哈夫曼码码码码优点：优点：编码方便易行，效率高编码方便易行，效率高。在哈夫曼编码过程中，对缩减信源符号按概在哈夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应使率由大到小的顺序重新排列时，应使合并后的新合并后的新符号尽可能排在靠前的位置符号尽可能排在靠前的位置，这样可使合并后的，这样可使合并后的新符号重复编码次数减少新符号重复编码次数减少,使短码得到充分利用。使短码得到充分利用。通过最佳的信源编码虽然可以消除信源的冗余通过最佳的信源编码虽然可以消除信源的冗余度，提高信息传输率，但结果却使码变得十分度，提高信息传输率，但结果却使码变得十分“脆弱脆弱”，经不起信道中噪声的干扰，容易造成译，经不起信道中噪声的干扰，容易造成译码错误。码错误。哈夫曼编码的优点哈夫曼编码的优点*68 （1 1）如果对单个字母编码时，平均码字长与理论）如果对单个字母编码时，平均码字长与理论上的最优压缩率可能还有一定距离（可能差上的最优压缩率可能还有一定距离（可能差1比特）比特）。当信源熵当信源熵H(X)很大时，这很大时，这1比特比特可能无关重要；可能无关重要；但当但当H(X)本身就接近本身就接近1比特时，这额外的比特时，这额外的1比特可比特可能决定了编码的码率，这显然不经济，因此要进能决定了编码的码率，这显然不经济，因此要进一步提高编码效率，使码率尽可能接近信源熵，一步提高编码效率，使码率尽可能接近信源熵，则仍需则仍需对长的信源序列来编码对长的信源序列来编码。哈夫曼编码的缺点哈夫曼编码的缺点*69（2 2）哈夫曼哈夫曼编码算法是从下而上地构造码树编码算法是从下而上地构造码树,当信源字母集很大时当信源字母集很大时,这种算法甚为不便。另这种算法甚为不便。另外外,哈夫曼编码需要知道信源的概率分布哈夫曼编码需要知道信源的概率分布,这这在实际中有时是比较困难的。在实际中有时是比较困难的。哈夫曼编码的缺点哈夫曼编码的缺点*70哈夫曼编码的缺点哈夫曼编码的缺点*71 （4 4）从硬件实现上来看，哈夫曼编码有变长码）从硬件实现上来看，哈夫曼编码有变长码的固有缺点：的固有缺点：需缓冲存储器需缓冲存储器。因为一般信源和信道传输信号是恒速的，但因为一般信源和信道传输信号是恒速的，但经变长编码后信源编码的每秒输出的比特数就不经变长编码后信源编码的每秒输出的比特数就不是常量，不能直接用信道来传输，为适应信道必是常量，不能直接用信道来传输，为适应信道必须加缓冲设备，将编码器输出暂存在缓冲器中，须加缓冲设备，将编码器输出暂存在缓冲器中，然后再接到信道去传送。然后再接到信道去传送。从理论上讲当存储器容量为无限时，信源输从理论上讲当存储器容量为无限时，信源输出与信道传输之间才能取得平衡，当存储器容量出与信道传输之间才能取得平衡，当存储器容量有限时，这种平衡不一定能保持。有限时，这种平衡不一定能保持。哈夫曼编码的缺点哈夫曼编码的缺点*72 当信源连续输出低概率符号，其对应的码字较长，输入当信源连续输出低概率符号，其对应的码字较长，输入缓冲器的比特数大于信道能输出的比特数，会造成存储器溢缓冲器的比特数大于信道能输出的比特数，会造成存储器溢出。出。反之，当信源连续输出高概率符号，其对应的码字较短，反之，当信源连续输出高概率符号，其对应的码字较短，输入缓冲器的比特数小于信道能输出的比特数，会造成存储输入缓冲器的比特数小于信道能输出的比特数，会造成存储器取空，信道上无信息可送，而使信道上出现连个器取空，信道上无信息可送，而使信道上出现连个0 0或连个或连个1 1，导致误译。，导致误译。因此因此需设计适当的存储器容量需设计适当的存储器容量（降低成本，增加容量），（降低成本，增加容量），并把信源发出的信息分段发送，或经常检查存储器，如有溢并把信源发出的信息分段发送，或经常检查存储器，如有溢出，就转停，如有取空，则加入空间符号。出，就转停，如有取空，则加入空间符号。哈夫曼编码的缺点哈夫曼编码的缺点*73（5 5）差错扩散）差错扩散:对变长码一旦产生误码对变长码一旦产生误码,某个码字的前缀某个码字的前缀部分可能成为另一个码字而发生错译部分可能成为另一个码字而发生错译,并可导并可导致错误后传致错误后传.哈夫曼编码的缺点哈夫曼编码的缺点*74法诺法诺(Fano)(Fano)码编码步骤：码编码步骤：1.1.将概率按从大到小的顺序排列，令将概率按从大到小的顺序排列，令2.2.将依次排列的信源符号按概率分成两组，使每组概率和尽可将依次排列的信源符号按概率分成两组，使每组概率和尽可能接近或相等。能接近或相等。3.3.给每一组分配一位码元给每一组分配一位码元“0 0”或或“1 1”。4.4.将每一分组再按同样方法划分，重复步骤将每一分组再按同样方法划分，重复步骤2 2和和3 3，直至概率不，直至概率不再可分为止。由此即可构造一个码树，所有终端节点上的码再可分为止。由此即可构造一个码树，所有终端节点上的码字组成法诺码。字组成法诺码。原理原理：它是通过构造一个码树，编出的码是即时码，但不一定：它是通过构造一个码树，编出的码是即时码，但不一定是最佳码。是最佳码。(3)(3)法诺法诺(Fano)(Fano)编码编码*75解解信源符号符号概率第一次分组第二次分组第三次分组第四次分组码字码长0.20000020.191001030.18101130.17101020.151011030.1010111040.01111114例例 对如下信源进行法诺编码对如下信源进行法诺编码*76l平均码长为平均码长为l信源熵为信源熵为l编码效率为编码效率为*77(1)(1)法诺编码在构造码树时，是从树根开始到终端节法诺编码在构造码树时，是从树根开始到终端节点结束，这点结束，这与哈夫曼编码相反与哈夫曼编码相反；(2)(2)由于赋码元时的任意性，因此法诺编码编出的码由于赋码元时的任意性，因此法诺编码编出的码字字不惟一不惟一；(3)(3)法诺编码不全是按法诺编码不全是按“概率大码长小、概率小码长概率大码长小、概率小码长大大”来决定码长，有时会出现概率小码长反而小的来决定码长，有时会出现概率小码长反而小的情况，因此情况，因此平均码长一般不会最小平均码长一般不会最小。法诺编码法诺编码的特点的特点*78l香农码、法诺码、哈夫曼码都考虑了香农码、法诺码、哈夫曼码都考虑了信源的统计特性信源的统计特性,使经常出现的信源符号对应较短的码字使经常出现的信源符号对应较短的码字,使信源的平均使信源的平均码长缩短，从而实现了对信源的压缩码长缩短，从而实现了对信源的压缩.l香农编码结果香农编码结果惟一惟一,但在很多情况下但在很多情况下编码效率不高编码效率不高.l法诺码和哈夫曼码的编码方法都法诺码和哈夫曼码的编码方法都不惟一不惟一.l法诺码比较适合于对法诺码比较适合于对分组概率相等或接近的信源编码分组概率相等或接近的信源编码.l哈夫曼哈夫曼码对信源的统计特性没有特殊要求码对信源的统计特性没有特殊要求,编码效率编码效率比较高，对编码设备的要求也比较简单，因此比较高，对编码设备的要求也比较简单，因此综合性能综合性能优于香农码和法诺码优于香农码和法诺码.三种三种编码编码方法的对比方法的对比*79cabcedeacacdeddaaabaababaaabbacdebaceadcabcedeacacdeddaaabaababaaabbacdebaceada a 共共4040个字母个字母 采用法诺编码法采用法诺编码法频度频度a-16a-16，b-7b-7，c-6c-6，d-6d-6，e-5 e-5 1)1)将给定符号按照其频率从大到小排序。将给定符号按照其频率从大到小排序。a a 16 b-7 c-6 d-6 e 16 b-7 c-6 d-6 e 5 52)2)将序列分成左右两部分，使得左部频率总和将序列分成左右两部分，使得左部频率总和尽可能接近右部频率总和。尽可能接近右部频率总和。(a,b),(c,d,e)(a,b),(c,d,e)例例 对如下信源进行编码对如下信源进行编码*803)3)我们把第二步中划分出的上部作为二叉树的左子树，我们把第二步中划分出的上部作为二叉树的左子树，记记 0 0，下部作为二叉树的右子树，记，下部作为二叉树的右子树，记 1 1。4)4)分别对左右子树重复分别对左右子树重复 2),3)2),3)两步，直到所有的符号两步，直到所有的符号都成为二叉树的树叶为止。都成为二叉树的树叶为止。bacde00101011a 00b 01c 10d 110e 111编码结果编码结果cabcedeacacdeddaaabaababaaabbacdebaceada10 00 01 10 111 110 111 00 10 00 10.*81采用哈夫曼编码法采用哈夫曼编码法a 16b 7c 6d 6e 511132401010101a 0b 100c 101d 110e 111总比特数总比特数8888，信源熵为，信源熵为86.601 bit86.601 bit*82 对于离散信源对于离散信源,虽然变长编码可提高编码效率，虽然变长编码可提高编码效率，但也有它的固有缺点：需要大量缓冲设备来存储这些但也有它的固有缺点：需要大量缓冲设备来存储这些变长码，然后再以恒定的码率进行传送。另外，在传变长码，然后再以恒定的码率进行传送。另外，在传输的过程中，如果出现了误码，容易引起错误扩散，输的过程中，如果出现了误码，容易引起错误扩散，所以要求有所以要求有优质的信道优质的信道。很多情况下很多情况下信源是连续的信源是连续的，那么离散信源编码，那么离散信源编码方法就不适用，也不能做到无失真编码，需要采取另方法就不适用，也不能做到无失真编码，需要采取另外的编码方法。外的编码方法。有时为了得到较高的编码效率，先有时为了得到较高的编码效率，先采用某种正交采用某种正交变换变换，解除或减弱信源符号间的相关性，然后再进行，解除或减弱信源符号间的相关性，然后再进行信源编码。有时则利用信源符号间的相关性直接编码。信源编码。有时则利用信源符号间的相关性直接编码。*83 算术编码是计算序列的累计分布，用累计分布值算术编码是计算序列的累计分布，用累计分布值表示序列，所以称为表示序列，所以称为算术编码算术编码。ShannonShannon码，码，FanoFano码码就是一种就是一种利用累计分布函数来分配码字的构造性利用累计分布函数来分配码字的构造性的编的编码方法。码方法。算术编码算术编码*84算术编码算术编码1.1.基本思路基本思路用用二进制小数二进制小数表示信源的概率分布，表示信源的概率分布，如果概率分布取值大，则它的二进制位数就低如果概率分布取值大，则它的二进制位数就低；另外，为了使算术码具有前缀性（无尾随后另外，为了使算术码具有前缀性（无尾随后 缀），对概率分布缀），对概率分布采用累计求和计算采用累计求和计算.*85算术编码算术编码2.2.编码方法编码方法1 1）将信源符号）将信源符号X=a1,a2,aq 依次排列（不要求以依次排列（不要求以 概率大小排序）；概率大小排序）；2 2）计算各符号的修正累积分函数值）计算各符号的修正累积分函数值 3 3）确定各信源符号所对应码字的码长）确定各信源符号所对应码字的码长4 4）将）将F(ak)表示为二进制小数，并用小数点后的表示为二进制小数，并用小数点后的l(ak)位位 作为作为ak的码字的码字.若若二进制小数后二进制小数后面有尾数，则面有尾数，则截断截断.*86算术编码算术编码例：若信源的概率分布为 ，取 信号字母表为 ，求信源的算 术码.*87算术编码算术编码1 0