第三章 数据压缩和信源编码

1、8:1913.1 3.1 3.2 3.2 3.3 3.3 3.4 3.4 8:192 为了实现高质量、高效率的通信，引入了信为了实现高质量、高效率的通信，引入了信源编码和信道编码。信源编码和信道编码主要需源编码和信道编码。信源编码和信道编码主要需要解决以下两个问题。要解决以下两个问题。提高传输效率提高传输效率 增强通信的可靠性增强通信的可靠性 数据压缩和信源编码数据压缩和信源编码 8:193 编码编码：将一定的符号，数字或字母按一定的要求编：将一定的符号，数字或字母按一定的要求编成不同的序列，表示出一定的意义称为编码。成不同的序列，表示出一定的意义称为编码。编码、信源编码、信道编码编码、信源编

2、码、信道编码 编码分为编码分为信源编码信源编码和和信道编码信道编码，其中信源编码又，其中信源编码又分为分为无失真信源编码无失真信源编码和和限失真信源编码限失真信源编码。 无失真信源编码无失真信源编码：适用于离散信源或数字信号。：适用于离散信源或数字信号。 限失真信源编码限失真信源编码：主要用于连续信源或模拟信号，：主要用于连续信源或模拟信号，如语音、图像等信号的数字处理。如语音、图像等信号的数字处理。8:194第一极限定理第一极限定理: :无失真信源编码定理无失真信源编码定理. .第二极限定理第二极限定理: :信道编码定理（包括离散和连信道编码定理（包括离散和连 续信道）续信道）. .第三极限

3、定理第三极限定理: :限失真信源编码定理限失真信源编码定理. .香农信息论三大定理香农信息论三大定理 8:195 信源编码的信源编码的主要任务主要任务是什么是什么? ? 由于信源符号之间存在分布由于信源符号之间存在分布不均匀不均匀和和相关性相关性，使得信源存在冗余度，信源编码的主要任务就是减使得信源存在冗余度，信源编码的主要任务就是减少冗余，提高编码效率。具体说，就是针对信源输少冗余，提高编码效率。具体说，就是针对信源输出符号序列的统计特性，寻找一定的方法把信源输出符号序列的统计特性，寻找一定的方法把信源输出符号序列变换为最短的码字序列。出符号序列变换为最短的码字序列。 信源编码信源编码 8:

4、196 信源编码的信源编码的基本途径基本途径是什么是什么? ? 信源编码的基本途径有两个，一是使序列中的信源编码的基本途径有两个，一是使序列中的各个符号尽可能地互相独立，即解除相关性；各个符号尽可能地互相独立，即解除相关性；二是使编码中各个符号出现的概率尽可能地相二是使编码中各个符号出现的概率尽可能地相等，即概率均匀化。等，即概率均匀化。 信源编码的信源编码的基础基础是什么是什么? ? 信源编码的信源编码的基础基础是：两个编码定理，即是：两个编码定理，即无失真编码定理和限失真编码定理。无失真编码定理和限失真编码定理。信源编码信源编码 8:197信源编码信源编码：以以提高通信提高通信为目的为目的

5、, ,针对信源的编码针对信源的编码. .能更加有能更加有效地传输、存储信息。效地传输、存储信息。 在不失真或允许一定失真条件下在不失真或允许一定失真条件下 如何用尽可能如何用尽可能少的符号来传送信源信息少的符号来传送信源信息, ,以便提高信息传输率以便提高信息传输率。通通常通过压缩信源的冗余度来实现。常通过压缩信源的冗余度来实现。 采用的一般方法是采用的一般方法是压缩每个信源符号的平均比特压缩每个信源符号的平均比特数或信源的码率。数或信源的码率。即同样多的信息用较少的码率传送即同样多的信息用较少的码率传送, ,使单位时间内传送的平均信息量增加使单位时间内传送的平均信息量增加, ,从而提高通信从

6、而提高通信的有效性。的有效性。信源编码信源编码8:198 说明说明： （1 1）无失真编码或可逆编码只适用于离散信源。）无失真编码或可逆编码只适用于离散信源。 （2 2）对于连续信源，编成代码后就无法无失真地）对于连续信源，编成代码后就无法无失真地恢复原来的连续值，因为后者的取值可有无限多恢复原来的连续值，因为后者的取值可有无限多个。此时只能根据限失真编码定理进行限失真编个。此时只能根据限失真编码定理进行限失真编码码 。信源编码信源编码编码定理证明：编码定理证明：（1 1）必存在一种编码方法，使代码的平均长度可）必存在一种编码方法，使代码的平均长度可 任意接近但不能低于符号熵任意接近但不能低于

7、符号熵（2 2）达到这目标的途径，就是使概率与码长匹配。）达到这目标的途径，就是使概率与码长匹配。 8:199 信道编码：信道编码： 是以是以提高信息传输的提高信息传输的为目的的编码。在信道为目的的编码。在信道受干扰的情况下如何增加信号的受干扰的情况下如何增加信号的, ,同时同时又使得信息传输率最大。通常通过增加信源的冗余又使得信息传输率最大。通常通过增加信源的冗余度来实现。采用的一般方法是增大码率度来实现。采用的一般方法是增大码率/ /带宽。与带宽。与信源编码正好相反。信源编码正好相反。 密码：密码： 是以提高通信系统的是以提高通信系统的为目的的编码。通常通为目的的编码。通常通过加密和解密来

8、实现。从信息论的观点出发过加密和解密来实现。从信息论的观点出发“加密加密”可视为增熵的过程可视为增熵的过程, ,“解密解密”可视为减熵的过程。可视为减熵的过程。信道编码、密码信道编码、密码8:1910信源编码包括两个功能：信源编码包括两个功能： （1 1）将信源符号变换成适合信道传输的符号；）将信源符号变换成适合信道传输的符号； （2 2） 压缩信源冗余度，提高传输效率。压缩信源冗余度，提高传输效率。 提高传输效率往往削弱了其抗干扰能力。提高传输效率往往削弱了其抗干扰能力。提高抗提高抗干扰能力往往是以降低信息传输效率为代价。干扰能力往往是以降低信息传输效率为代价。 8:1911l由信源的渐近等

9、分性导出了信源编码定理：由信源的渐近等分性导出了信源编码定理：只要只要编码的码率大于编码的码率大于信源的熵（或熵率），则必存在信源的熵（或熵率），则必存在编译码方案编译码方案, ,使当被编码的信源分组长趋于无穷时使当被编码的信源分组长趋于无穷时, ,译译码误差概率可以充分小码误差概率可以充分小, ,这解决了最优码的存在性问这解决了最优码的存在性问题。题。l怎样构造最优码？怎样构造最优码？信源编码信源编码8:1912信源编码的分类：离散信源编码、连续信源编码和相信源编码的分类：离散信源编码、连续信源编码和相关信源编码三类关信源编码三类离散信源编码离散信源编码：独立信源编码，可做到无失真编独立信源

10、编码，可做到无失真编码；码；连续信源编码连续信源编码：独立信源编码，只能做到限失真独立信源编码，只能做到限失真信源编码信源编码；相关信源编码相关信源编码：非独立信源编码。非独立信源编码。信源编码的分类信源编码的分类8:1913 冗余度压缩编码冗余度压缩编码: : 是可逆压缩，经编译码后可以无失真地恢复。是可逆压缩，经编译码后可以无失真地恢复。 基本途径：基本途径：压缩信源的冗余度，即压缩信源的冗余度，即 1) 1) 去除码符号间的相关性；去除码符号间的相关性； 2) 2) 使码符号等概分布。使码符号等概分布。信源编码的分类信源编码的分类8:1914熵压缩编码：是不可逆压缩熵压缩编码：是不可逆压

11、缩 压缩超过一定限度，必然带来失真压缩超过一定限度，必然带来失真, ,允许的失真允许的失真越大，压缩的比例越大越大，压缩的比例越大, ,译码时能按一定的失真容许译码时能按一定的失真容许度恢复，保留尽可能多的信息。度恢复，保留尽可能多的信息。信源编码的分类信源编码的分类8:1915l 信源编码将信源编码将信源符号序列信源符号序列按一定的数学规律映射成按一定的数学规律映射成码码符号序列符号序列。是从信源符号集到码符号集的一种映射，它。是从信源符号集到码符号集的一种映射，它把信源输出的符号变换成码元序列。把信源输出的符号变换成码元序列。信宿信宿信道信道信源信源编码器编码器译码器译码器 信源编码器模型

12、信源编码器模型 译码是从码符号到信源符号的映射。若要实现无失译码是从码符号到信源符号的映射。若要实现无失真编码，这种映射必须是一一对应的、可逆的。真编码，这种映射必须是一一对应的、可逆的。 信源编码器模型信源编码器模型8:1916编码器编码器12: ,.,DXx xx码字码字12,qXXXX12liiiiicx xx12 ,qCc ccl 将信源符号集中的符号将信源符号集中的符号 （或者长为（或者长为n的信源符号序的信源符号序列）映射成由码符号列）映射成由码符号 组成的长度为组成的长度为 的一一对应的的一一对应的码符号序列码符号序列 。ixiXilic信源编码器的模型信源编码器的模型8:191

13、7l编码器输出的码符号序列编码器输出的码符号序列 称为称为码字码字；长度；长度 称为称为码字长度，简称码字长度，简称码长码长；全体码字的集合记为；全体码字的集合记为C C。l将信源符号集中的每个信源符号将信源符号集中的每个信源符号 依照固定的码表依照固定的码表映射成某一个码字映射成某一个码字 ，这样的码称为，这样的码称为分组码分组码。l只有分组码才有对应的码表，而非分组码中则不存在只有分组码才有对应的码表，而非分组码中则不存在码表。码表。iciXicil对于同一个信源，编码方法是多种的。对于同一个信源，编码方法是多种的。分组码分组码8:1918 3. 变长码变长码若码字集合若码字集合C中的所有

14、码字中的所有码字cm (m = 1,2, ,M)，其码长，其码长不都相同不都相同，称码称码C为变长码。为变长码。 2. 等长码等长码在一组码字集合在一组码字集合C中的所有码字中的所有码字cm (m = 1,2, ,M)，其码长，其码长都相都相同同，则称这组码，则称这组码C为等长码。为等长码。 1. 二元码二元码若码符号集为若码符号集为0，1，则码字就是二元序列，称为二元码，则码字就是二元序列，称为二元码, ,二二元码通过二进制信道传输，这是数字通信和计算机通信中最常元码通过二进制信道传输，这是数字通信和计算机通信中最常见的一种码。见的一种码。码的分类码的分类8:1919 4.非奇异码非奇异码从

15、信源消息到码字的映射从信源消息到码字的映射是一一对应的是一一对应的，每一个不同的信源消，每一个不同的信源消息都用不同的码字对其编码。息都用不同的码字对其编码。非奇异码非奇异码码中所有码字互不相同码中所有码字互不相同. 5.奇异码奇异码从信源消息到码字的映射从信源消息到码字的映射不是一一对应的不是一一对应的。奇异码不具备惟。奇异码不具备惟一可译性。一可译性。原码的原码的N次扩展码是将信源作次扩展码是将信源作N次扩展得到的新信源符号序列次扩展得到的新信源符号序列u（N）=u1 uN = (u11 u12 u1L) (uN1 uN2 uNL)，对应码符号序列对应码符号序列c（N）=c1 cN = (

16、c11 c12 c1n) (cN1 cN2 cNn) ，记集合记集合 C (N) = c1(N), c2(N), 即原码即原码C的的N次扩展码。次扩展码。 6.原码原码C的的N次扩展码次扩展码8:1920对于等长码，若原码是惟一可译码，则它的对于等长码，若原码是惟一可译码，则它的N N次扩展码也是次扩展码也是惟一可译的，而对于变长码则不尽然。惟一可译的，而对于变长码则不尽然。 7.惟一可译码惟一可译码定义定义 若任意一串有限长的码符号序列只能被惟一地译为对若任意一串有限长的码符号序列只能被惟一地译为对应的信源符号序列，则称此码为应的信源符号序列，则称此码为惟一可译码惟一可译码。l 惟一可译码惟

17、一可译码应当满足的条件应当满足的条件(1,2,., )(1,2,., )iic iqX iq码字与信源符号一一对应码字与信源符号一一对应2) 不同的信源符号序列对应不同的码字序列。不同的信源符号序列对应不同的码字序列。1) 8:1921 8. 即时码即时码定义定义 对于码字对于码字c = c1 c2 cn, ,称称c、 = c1 c2 ci ( (i0，只要满足，只要满足 则当则当N足够大时，可实现几乎无失真编码，即译码错误足够大时，可实现几乎无失真编码，即译码错误概率概率 PE 为任意小；为任意小； （D进制）进制） 反之，如果反之，如果 则不可能实现无失真编码，当则不可能实现无失真编码，当

18、N足够大时，译码错误概足够大时，译码错误概率率 PE 为为1。()logkH XND()2logkH XNDNX等长编码定理等长编码定理8:1942等长编码的等长编码的效率效率 （D进制）进制）(),logH XLD 为使编码真正有效，必须增大信源序列的分组长为使编码真正有效，必须增大信源序列的分组长度度N，这就会使编、译码的延时增大，同时也会使编，这就会使编、译码的延时增大，同时也会使编、译码器的复杂程度增加，因此，等长编码在冗余度、译码器的复杂程度增加，因此，等长编码在冗余度压缩编码中的理论意义远大于其实用价值。压缩编码中的理论意义远大于其实用价值。1()qiiiLp X k等长编码定理等

19、长编码定理8:1943 如果无论怎样编码都是有错编码，但可以使如果无论怎样编码都是有错编码，但可以使当地编码和译码使译码错误的概率当地编码和译码使译码错误的概率pe任意小，这任意小，这就是所谓就是所谓“渐进无错编码渐进无错编码”。( , ) ( ().nnerfPPf xx一个编译码方案为概率的错误等长编码定理等长编码定理8:1944() 2,1log().nH XeDMPRMH Xn若用 进数字表出个码字，要使译码错误概率只需码率() 2,1loglog().knH XkDDMkRMDH Xnn若编码成 长的 进码字，则于是码率等长编码定理等长编码定理8:1945( ),nnerPP xWn

20、由渐近等分性知这样编码的错误概率为当 充分大时成立。等长编码定理等长编码定理nn但在实际应用中， 不可能无限增大，这就要求我们在给定的有限 寻求尽可能好的编译码方案，使得码率尽可能接近时,理论值。8:1946l等长编码定理同样也适用于离散平稳有记忆信源，差等长编码定理同样也适用于离散平稳有记忆信源，差别是要将信源熵别是要将信源熵 改为极限熵改为极限熵 。l可以验证，对等长信源编码来说，要想实现无失真信可以验证，对等长信源编码来说，要想实现无失真信源编码，源编码，N常常要取非常大的值常常要取非常大的值，这在实际应用中很，这在实际应用中很 难实现。难实现。()H XH 等长编码在引入失真的前提下，

21、还需要取很长等长编码在引入失真的前提下，还需要取很长的信源序列进行编码，才能达到较高的编码效率。的信源序列进行编码，才能达到较高的编码效率。既要不失真，又要很高的编码效率，只能采用变长既要不失真，又要很高的编码效率，只能采用变长编码。编码。等长编码定理等长编码定理8:1947 对等长码的讨论是在对等长码的讨论是在N足够大的条件下得到的结足够大的条件下得到的结论，论，当当N为有限值时，则总会带来一定程度的失真。为有限值时，则总会带来一定程度的失真。对于变长码，往往在对于变长码，往往在N不是很大的情况下不是很大的情况下就可编出高就可编出高效且无失真的码。效且无失真的码。 变长码也要求原码的变长码也

22、要求原码的任意任意N次扩展码次扩展码也是惟一可也是惟一可译的。变长码分为即时码和延长码，为保证即时译码，译的。变长码分为即时码和延长码，为保证即时译码，要求变长惟一可译码采用即时码。对于变长码，要求要求变长惟一可译码采用即时码。对于变长码，要求整个码集的平均码长力求最小，此时编码效率最高。整个码集的平均码长力求最小，此时编码效率最高。 当信源较复杂当信源较复杂, ,直接画码树就比较复杂。针对这直接画码树就比较复杂。针对这一问题，在数学上给出一个与码树等效的，表达码字一问题，在数学上给出一个与码树等效的，表达码字可分离的充要条件，即著名的克拉夫特不等式。可分离的充要条件，即著名的克拉夫特不等式。

23、变长编码变长编码8:1948 Kraft定理定理 即时码存在的充要条件即时码存在的充要条件是是 McMillan定理定理 惟一可译码存在的充要条件惟一可译码存在的充要条件是是12, ,.,1.ilmiDl llD码字字母取值于 进字母集的即时码，其码字长分别为时必须满足12, ,.,1.ilmiDl llD码字字母取值于 进字母集的惟一可译码，其码字长分别为时必须满足Kraft不等式和不等式和McMillan不等式不等式8:1949l上述定理是上述定理是存在性定理存在性定理当满足当满足KraftKraft（或（或McMillanMcMillan）不等式时，必然可）不等式时，必然可以构造出即时码

24、（或惟一可译码），否则不能构以构造出即时码（或惟一可译码），否则不能构造出即时码（或惟一可译码）。但满足造出即时码（或惟一可译码）。但满足KraftKraft不等不等式的码长集未必是最优的，即它的平均码长未必式的码长集未必是最优的，即它的平均码长未必是最小的。是最小的。该定理该定理不能不能作为判断一种码是否是即时码（或惟作为判断一种码是否是即时码（或惟一可译码）的判断依据。一可译码）的判断依据。KraftKraft不等式和不等式和McMillanMcMillan不等式不等式8:19501( )qiiiLp x l码符号码符号/信源符号信源符号l 平均码长平均码长L 对于给定的信源和码符号集，若

25、有一个惟一可译码，对于给定的信源和码符号集，若有一个惟一可译码，其平均长度其平均长度 小于所有其它惟一可译码小于所有其它惟一可译码,则称这种码则称这种码为为最佳码最佳码或或紧致码紧致码。 所谓所谓最佳最佳：是指在所有可能的编码方法中，：是指在所有可能的编码方法中，其编其编码得到的平均码长最短码得到的平均码长最短。 8:1951()()1loglogNH XLH XDNDN香农第一定理香农第一定理 设离散无记忆信源的熵为设离散无记忆信源的熵为H H( (X X ) )，它的，它的N N 次扩展次扩展信源为信源为 ，对扩展信源，对扩展信源 进行编码进行编码（D D进制）进制），总，总可以找到一种编

26、码方法，构成惟一可译码，使平均码可以找到一种编码方法，构成惟一可译码，使平均码长满足长满足 NXNX 变长编码不要求所有码字长度相同变长编码不要求所有码字长度相同, ,但希望平均码长最小但希望平均码长最小, ,变长无失真信源编码定理给出了在无失真编码的前提下平均变长无失真信源编码定理给出了在无失真编码的前提下平均码长的界限。码长的界限。变长无失真信源编码定理变长无失真信源编码定理8:1952*(),().()()11.DLH XlHXHXH XLl 冗余度相 一个 进制惟一可译码的冗余度为其平均长度与信源熵的差，即余度或冗或对定义 变长编码采用即时码变长编码采用即时码,力求平均码长最小力求平均

27、码长最小,此时此时编码效率最高，信源的冗余得到最大程度的压缩。编码效率最高，信源的冗余得到最大程度的压缩。将概率大的信息符号编以短的码字，概率小的符号将概率大的信息符号编以短的码字，概率小的符号编以长的码字，可使得平均码字长度最短。编以长的码字，可使得平均码字长度最短。冗余度冗余度8:1953 对于同一种信源，对于同一种信源，香农编码不能使平均码长达到最小，因香农编码不能使平均码长达到最小，因此不是最佳编码。三种编码法中此不是最佳编码。三种编码法中,以以香香农编码法的编码效率最低农编码法的编码效率最低，法诺编码法也不是一种最佳编码法，但用这种方法有时候也，法诺编码法也不是一种最佳编码法，但用这

28、种方法有时候也能找到最优码。能找到最优码。 一般情况下一般情况下, ,哈夫曼编码法得到的平均码长哈夫曼编码法得到的平均码长 最短，即最短，即编编码效率码效率 最高。最高。()lo gHXLDL香农（香农（Shannon）编码法）编码法法诺法诺( (Fano) )编码法编码法哈夫曼哈夫曼( (Huffman) )编码法编码法变长编码法变长编码法变长码的编码方法变长码的编码方法8:1954香农码编码步骤：香农码编码步骤：1. 将信源符号按概率从大到小顺序排列，方便起见，令将信源符号按概率从大到小顺序排列，方便起见，令 2. 按下式计算第按下式计算第i个符号对应的码字的码长个符号对应的码字的码长3.

29、 计算第计算第i个符号的累加概率个符号的累加概率4. 将累加概率变换成将累加概率变换成二进制小数二进制小数，取小数点后，取小数点后li位位数作为数作为 第第i个符号的码字。个符号的码字。12()()()np xp xp x11()iikkPp x1log 1( )iilp x(1)(1)香农（香农（ShannonShannon）编码）编码8:19550.0171234567( )0.200.190.180.170.150.100.01XxxxxxxxP x例例 对如下信源进行对如下信源进行香农香农编码编码信源符号符号概率累加概率码长码字x10.2002.3430000.190.22.41300

30、10.180.392.483011x40.170.572.563100 x50.150.742.743101x60.100.893.3441110 x70.996.661111110iPix()ip xillog()ip xx2x38:1956 平均码长平均码长1( )3.14/qiiiLp x l码元符号 信源符号信源熵信源熵1()( )log( )2.61/qiiiH Xp xp x 比特 信源符号结论：结论： 1) 2) 香农码是即时码，但冗余度稍大，不是最佳码。香农码是即时码，但冗余度稍大，不是最佳码。()() 1.H XLH X2.6183.1%3.14编码效率编码效率8:1957

31、在众多变长码中，哈夫曼码是效率最高的变长在众多变长码中，哈夫曼码是效率最高的变长无失真信源编码方法，它是一种逐个符号的编码方无失真信源编码方法，它是一种逐个符号的编码方法，是在编码理论指导下法，是在编码理论指导下平均码长最短的码平均码长最短的码。 原理：原理： 构造一个码树。构造一个码树。 (2)(2)哈夫曼哈夫曼(Huffman)(Huffman)编码编码8:19581.1. 将信源符号按概率从大到小的顺序排列，令将信源符号按概率从大到小的顺序排列，令2.2. 给两个概率最小的信源符号给两个概率最小的信源符号xn-1和和xn各分配一个码元各分配一个码元“0 0”和和“1 1”，并将这两个信源

32、符号合并成一个新符，并将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含结果得到一个只包含n1个信源符号的新信源。称个信源符号的新信源。称为为信源的第一次缩减信源信源的第一次缩减信源，用，用X X1 1表示。表示。12( )()()np xp xp x哈夫曼码编码步骤：哈夫曼码编码步骤：(2)(2)哈夫曼哈夫曼(Huffman)(Huffman)编码编码8:1959 3. 3. 将缩减信源将缩减信源X1的符号仍按概率从大到小顺序排的符号仍按概率从大到小顺序排 列，列，重复步骤重复步骤2 2，得到只含，得到

33、只含n2个符号的缩减信源个符号的缩减信源X2。 4. 4. 重复上述步骤，直至缩减信源只剩两个符号为重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为止，此时所剩两个符号的概率之和必为1 1。然后从。然后从最后一级缩减信源开始，依编码路径向前返回，就最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。得到各信源符号所对应的码字。(2)(2)哈夫曼哈夫曼(Huffman)(Huffman)编码编码8:196012345:0.4:0.2:0.2:0.1:0.1xxxxx014 . 02 . 02 . 02 . 0014 . 04 . 02 . 0016

34、. 04 . 00111c 201c 3000c 40010c 50011c 1( )2.2qiiiLp x l码符号码符号/信源符号信源符号8:196112345:0.4:0.2:0.2:0.1:0.1xxxxx014 . 02 . 02 . 02 . 0014 . 04 . 02 . 0016 . 04 . 001100c 210c 311c 4010c 5011c 1( )2.2qiiiLp x l码符号码符号/信源符号信源符号8:1962讨论：讨论：1) 1) 两种方法平均码长相等。两种方法平均码长相等。2) 2) 计算两种码的码长方差：计算两种码的码长方差：52211( )()1.3

35、6iiip xlL52221( )()0.16iiip xlL第二种方法编出的码码字长度变化较小，便于实现。第二种方法编出的码码字长度变化较小，便于实现。8:19631234567( )0.200.190.180.170.150.100.01XxxxxxxxP x解解 哈夫曼编码结果：哈夫曼编码结果：12345671011000001 01001100111xxxxxxx信源符号码字例例 对如下信源进行哈夫曼编码对如下信源进行哈夫曼编码8:1964l平均码长为平均码长为l信源熵为信源熵为l编码效率为编码效率为71( )2.72/iiiLp x l码元符号 信源符号2.6196.0%2.7271

36、()( )log( )2.61/iiiH Xp xp x 比特 信源符号8:1965注：哈夫曼编码后的码字不是惟一的。注：哈夫曼编码后的码字不是惟一的。1 1）每次对缩减信源两个概率最小的符号）每次对缩减信源两个概率最小的符号分配分配“0 0”或或“1 1”码元码元是任意的是任意的，所以可得到不同的码字。不同的码元分配，得，所以可得到不同的码字。不同的码元分配，得到的具体码字不同，但码长不变，平均码长也不变，所以到的具体码字不同，但码长不变，平均码长也不变，所以没有本质区别。没有本质区别。2 2）缩减信源时，）缩减信源时，若合并后的概率与其它概率相等，这几个概若合并后的概率与其它概率相等，这几

37、个概率的次序可任意排列率的次序可任意排列，但得到的码字不相同，但得到的码字不相同, ,对应的码长也对应的码长也不相同不相同, ,但平均码长不变。但平均码长不变。哈夫曼编码哈夫曼编码8:1966 第一，哈夫曼编码实际上构造了一个码树，码第一，哈夫曼编码实际上构造了一个码树，码树从最上层的端点开始构造，直到树根结束，最后树从最上层的端点开始构造，直到树根结束，最后得到一个横放的码树，因此，编出的码是即时码。得到一个横放的码树，因此，编出的码是即时码。 第二，哈夫曼编码采用概率匹配方法来决定各第二，哈夫曼编码采用概率匹配方法来决定各码字的码长，概率大的符号对应于短码，概率小的码字的码长，概率大的符号

38、对应于短码，概率小的符号对应于长码，从而使平均码长最小。符号对应于长码，从而使平均码长最小。 第三，每次对概率最小的两个符号求概率之和第三，每次对概率最小的两个符号求概率之和形成缩减信源时形成缩减信源时,就构造出两个树枝，由于给两个树就构造出两个树枝，由于给两个树枝赋码元时是任意的枝赋码元时是任意的,因此编出的码字并不惟一。因此编出的码字并不惟一。哈夫曼编码的基本特点哈夫曼编码的基本特点8:1967 哈夫曼哈夫曼优点：优点：编码方便易行，效率高编码方便易行，效率高。 在哈夫曼编码过程中，对缩减信源符号按概在哈夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应使率由大到小的顺序重新

39、排列时，应使合并后的新合并后的新符号尽可能排在靠前的位置符号尽可能排在靠前的位置，这样可使合并后的，这样可使合并后的新符号重复编码次数减少新符号重复编码次数减少, ,使短码得到充分利用。使短码得到充分利用。 通过最佳的信源编码虽然可以消除信源的冗通过最佳的信源编码虽然可以消除信源的冗余度，提高信息传输率，但结果却使码变得十分余度，提高信息传输率，但结果却使码变得十分“脆弱脆弱”，经不起信道中噪声的干扰，容易造成，经不起信道中噪声的干扰，容易造成译码错误。译码错误。哈夫曼编码的优点哈夫曼编码的优点8:1968 （1 1）如果对单个字母编码时，平均码字长与理论）如果对单个字母编码时，平均码字长与理

40、论上的最优压缩率可能还有一定距离（可能差上的最优压缩率可能还有一定距离（可能差1比比特）。特）。 当信源熵当信源熵H(X)很大时，这很大时，这1比特比特可能无关重要；可能无关重要；但当但当H(X)本身就接近本身就接近1比特时，这额外的比特时，这额外的1比特可比特可能决定了编码的码率，这显然不经济，因此要进能决定了编码的码率，这显然不经济，因此要进一步提高编码效率，使码率尽可能接近信源熵，一步提高编码效率，使码率尽可能接近信源熵，则仍需则仍需对长的信源序列来编码对长的信源序列来编码。 哈夫曼编码的缺点哈夫曼编码的缺点8:1969（2 2）哈夫曼哈夫曼编码算法是从下而上地构造码树编码算法是从下而上

41、地构造码树, ,当信源字母集很大时当信源字母集很大时, ,这种算法甚为不便。另这种算法甚为不便。另外外, ,哈夫曼编码需要知道信源的概率分布哈夫曼编码需要知道信源的概率分布, ,这这在实际中有时是比较困难的。在实际中有时是比较困难的。哈夫曼编码的缺点哈夫曼编码的缺点8:1970(3)().()logkkkkkkxlxpLHXLlpHX 由哈夫曼编码方法可以看到，当信源字母 对应的码长与 的概率满足关系时，编码后的平均码长 是理论上可达到的最短平均码长，即信源的熵率如果不满足该条件时（称统计失配）， 与就有差距，这时编码性能下降。哈夫曼编码的缺点哈夫曼编码的缺点8:1971 （4 4）从硬件实现

42、上来看，哈夫曼编码有变长码）从硬件实现上来看，哈夫曼编码有变长码的固有缺点：的固有缺点：需缓冲存储器需缓冲存储器。 因为一般信源和信道传输信号是恒速的，但因为一般信源和信道传输信号是恒速的，但经变长编码后信源编码的每秒输出的比特数就不经变长编码后信源编码的每秒输出的比特数就不是常量，不能直接用信道来传输，为适应信道必是常量，不能直接用信道来传输，为适应信道必须加缓冲设备，将编码器输出暂存在缓冲器中，须加缓冲设备，将编码器输出暂存在缓冲器中，然后再接到信道去传送。然后再接到信道去传送。 从理论上讲当存储器容量为无限时，信源输从理论上讲当存储器容量为无限时，信源输出与信道传输之间才能取得平衡，当存

43、储器容量出与信道传输之间才能取得平衡，当存储器容量有限时，这种平衡不一定能保持。有限时，这种平衡不一定能保持。哈夫曼编码的缺点哈夫曼编码的缺点8:1972 当信源连续输出低概率符号，其对应的码字较长，输入当信源连续输出低概率符号，其对应的码字较长，输入缓冲器的比特数大于信道能输出的比特数，会造成存储器溢缓冲器的比特数大于信道能输出的比特数，会造成存储器溢出。出。 反之，当信源连续输出高概率符号，其对应的码字较短，反之，当信源连续输出高概率符号，其对应的码字较短，输入缓冲器的比特数小于信道能输出的比特数，会造成存储输入缓冲器的比特数小于信道能输出的比特数，会造成存储器取空，信道上无信息可送，而使

44、信道上出现连个器取空，信道上无信息可送，而使信道上出现连个0 0或连个或连个1 1，导致误译。导致误译。 因此因此需设计适当的存储器容量需设计适当的存储器容量（降低成本，增加容量），（降低成本，增加容量），并把信源发出的信息分段发送，或经常检查存储器，如有溢并把信源发出的信息分段发送，或经常检查存储器，如有溢出，就转停，如有取空，则加入空间符号。出，就转停，如有取空，则加入空间符号。 哈夫曼编码的缺点哈夫曼编码的缺点8:1973（5 5）差错扩散）差错扩散: : 对变长码一旦产生误码对变长码一旦产生误码, ,某个码字的前缀某个码字的前缀部分可能成为另一个码字而发生错译部分可能成为另一个码字而发

45、生错译, ,并可导并可导致错误后传致错误后传. .哈夫曼编码的缺点哈夫曼编码的缺点8:1974法诺法诺(Fano)(Fano)码编码步骤：码编码步骤：1.1. 将概率按从大到小的顺序排列，令将概率按从大到小的顺序排列，令2.2. 将依次排列的信源符号按概率分成两组，使每组概率和尽可将依次排列的信源符号按概率分成两组，使每组概率和尽可能接近或相等。能接近或相等。3.3. 给每一组分配一位码元给每一组分配一位码元“0 0”或或“1 1”。4.4. 将每一分组再按同样方法划分，重复步骤将每一分组再按同样方法划分，重复步骤2 2和和3 3，直至概率不，直至概率不再可分为止。由此即可构造一个码树，所有终

46、端节点上的码再可分为止。由此即可构造一个码树，所有终端节点上的码字组成法诺码。字组成法诺码。 原理原理：它是通过构造一个码树，编出的码是即时码，但不一定：它是通过构造一个码树，编出的码是即时码，但不一定是最佳码。是最佳码。12( )()()qp xp xp x(3)(3)法诺法诺(Fano)(Fano)编码编码8:1975解解信源符号符号概率第一次分组第二次分组第三次分组第四次分组码字码长0.20000020.191001030.18101130.17101020.151011030.1010111040.011111141x2x4x3x5x6x7x1234567( )0.200.190.18

47、0.170.150.100.01XxxxxxxxP x例例 对如下信源进行法诺编码对如下信源进行法诺编码8:1976l平均码长为平均码长为l信源熵为信源熵为l编码效率为编码效率为2.6195.3%2.7471()( )log( )2.61/iiiH Xp xp x 比特 信源符号71( )2.74/iiiLp x l码元符号 信源符号8:1977 (1) (1) 法诺编码在构造码树时，是从树根开始到终端法诺编码在构造码树时，是从树根开始到终端节点结束，这节点结束，这与哈夫曼编码相反与哈夫曼编码相反； (2) (2) 由于赋码元时的任意性，因此法诺编码编出的由于赋码元时的任意性，因此法诺编码编出

48、的码字码字不惟一不惟一； (3) (3) 法诺编码不全是按法诺编码不全是按“概率大码长小、概率小码概率大码长小、概率小码长大长大”来决定码长，有时会出现概率小码长反而小来决定码长，有时会出现概率小码长反而小的情况，因此的情况，因此平均码长一般不会最小平均码长一般不会最小。法诺编码法诺编码的特点的特点8:1978l香农码、法诺码、哈夫曼码都考虑了香农码、法诺码、哈夫曼码都考虑了信源的统计特性信源的统计特性, ,使经常出现的信源符号对应较短的码字使经常出现的信源符号对应较短的码字, ,使信源的平均使信源的平均码长缩短，从而实现了对信源的压缩码长缩短，从而实现了对信源的压缩. .l香农编码结果香农编

49、码结果惟一惟一, ,但在很多情况下但在很多情况下编码效率不高编码效率不高. .l法诺码和哈夫曼码的编码方法都法诺码和哈夫曼码的编码方法都不惟一不惟一. .l法诺码比较适合于对法诺码比较适合于对分组概率相等或接近的信源编码分组概率相等或接近的信源编码. .l哈夫曼哈夫曼码对信源的统计特性没有特殊要求码对信源的统计特性没有特殊要求, ,编码效率编码效率比较高，对编码设备的要求也比较简单，因此比较高，对编码设备的要求也比较简单，因此综合性综合性能优于香农码和法诺码能优于香农码和法诺码. .三种三种编码编码方法的对比方法的对比8:1979 cabcedeacacdeddaaabaababaaabbac

50、debaceacabcedeacacdeddaaabaababaaabbacdebaceada da 共共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