信息论与编码第五章.ppt

第第5 5章章 无失真信源编码无失真信源编码5.15.1编码的定义编码的定义5.25.2定长编码定理定长编码定理5.35.3编码器变长码定理编码器变长码定理5.45.4最佳编码最佳编码将信源信息通过信道传送给信宿，怎样才将信源信息通过信道传送给信宿，怎样才能做到尽可能不失真而又快速呢？这就需能做到尽可能不失真而又快速呢？这就需要解决两个问题：要解决两个问题：第一，在不失真或允许一定失真的条件下，第一，在不失真或允许一定失真的条件下，如何用尽可能少的符号来传送信源信息；如何用尽可能少的符号来传送信源信息；第二，在信道受干扰的情况下，如何增加第二，在信道受干扰的情况下，如何增加信号的抗干扰能力，同时又使得信息传输信号的抗干扰能力，同时又使得信息传输率最大。率最大。为了解决这两个问题，就要引入信源编码为了解决这两个问题，就要引入信源编码和信道编码。和信道编码。信源编码：信源编码：在不失真或允许一定失真条在不失真或允许一定失真条件下件下,如何用尽可能少的符号来传送信源如何用尽可能少的符号来传送信源信息信息,以便以便提高信息传输率。提高信息传输率。在通信中要求精确的复现信源的输出，在通信中要求精确的复现信源的输出，就要保证信源产生的全部信息无损的传就要保证信源产生的全部信息无损的传送给信宿，这时的信源编码就是无失真送给信宿，这时的信源编码就是无失真信源编码。信源编码。5.15.1编码的定义编码的定义信源编码的定义信源编码的定义编码实质上是对信源的原始符号按一定的编码实质上是对信源的原始符号按一定的数学规则进行的一种变换。数学规则进行的一种变换。说明：说明：（1 1）输出的码符号序列称为输出的码符号序列称为码字码字;（2)2)长度长度l称为码字长度或简称码长称为码字长度或简称码长;(3)(3)编码就是从信源符号到码符号的一种编码就是从信源符号到码符号的一种映射映射;(4)(4)若要实现无失真编码，则这种映射必若要实现无失真编码，则这种映射必须是一一对应的，并且是可逆的。须是一一对应的，并且是可逆的。二元信道的基本符号集为二元信道的基本符号集为0,1,0,1,若将信源通若将信源通过一个二元信道传输，就必须把信源符号变过一个二元信道传输，就必须把信源符号变换成由换成由0,10,1符号组成的码符号序列，即编码。符号组成的码符号序列，即编码。可用不同的码符号序列，如表可用不同的码符号序列，如表 若把若把N次无记忆扩展信源的概念加以引申，次无记忆扩展信源的概念加以引申，便可得到便可得到N次扩展码。次扩展码。信源变码的分类信源变码的分类等长码等长码：码中所有码字的长度都相同：码中所有码字的长度都相同变长码变长码：码中的码字长短不一：码中的码字长短不一定义定义5.1 5.1 将信源符号集中的每个信源符号将信源符号集中的每个信源符号 映射成一个固定的码字映射成一个固定的码字 ，这样的码称为分组，这样的码称为分组码。码。采用分组编码方法，需要分组码具有某些属性，采用分组编码方法，需要分组码具有某些属性，以保证在接受端能够迅速准确地将码译出。下面以保证在接受端能够迅速准确地将码译出。下面首先讨论分组码的一些直观属性。首先讨论分组码的一些直观属性。（1 1）奇异码奇异码和和非奇异码非奇异码：若信源符号和码：若信源符号和码字是一一对应的，则该码为非奇异码。反之字是一一对应的，则该码为非奇异码。反之为奇异码为奇异码。信源符号信源符号 信源符号信源符号出现概率出现概率 码码 表表 码码0 0码码1 1码码2 2码码3 3码码4 4a1p(a1)=1/200000 00 01 11 1a2p(a2)=1/401011111101010100101a3p(a3)=1/8101000000000100100001001a4p(a4)=1/81111111101011000100000010001（2 2）唯一可译码：唯一可译码：若码的任意一串有限长的码若码的任意一串有限长的码符号序列只能唯一地被译成所对应的信源符号符号序列只能唯一地被译成所对应的信源符号序列，则此码称为唯一可译码，否则就称为非序列，则此码称为唯一可译码，否则就称为非唯一可译码。唯一可译码。唯一可译码唯一可译码 码码码码 信源信源概率概率p pi i 编码编码编码编码编码编码编码编码编码编码U U1 11/21/21 11 10 00 00 0U U2 21/41/4101001011 110100101U U3 31/81/81001000010010000110110011011U U4 41/81/81000100000010001111111111101110111即时码：即时码：无须考虑后续的码符号即可从码无须考虑后续的码符号即可从码符号序列中译出码字，这样的唯一可译码符号序列中译出码字，这样的唯一可译码称为即时码。称为即时码。设设 为一个码字，对于任意为一个码字，对于任意的的 ，码符号序列的前，码符号序列的前j个元素个元素 为码字为码字Wi的前缀。的前缀。一个唯一可译码成为即时码的充分必要条件是其一个唯一可译码成为即时码的充分必要条件是其中任何一个码字都不是其他码字的前缀。中任何一个码字都不是其他码字的前缀。码树：码树：表示各码字的构成表示各码字的构成 A A0 01 10 00 00 00 00 00 00 00 00 00 00 00 00 01 11 11 11 11 11 11 10 01 11 11 11 11 1二进制码树二进制码树2 20 00 00 00 00 01 11 11 11 11 12 22 22 22 22 2三进制码树三进制码树树根树根码字的起点码字的起点 分成分成r r个树枝个树枝码的进制数码的进制数终端节点终端节点码字码字11011101中间节点中间节点码字的一部分码字的一部分节数节数码长码长满树满树：每个节点上都有每个节点上都有r r个分枝的树个分枝的树等长码等长码非满树：非满树：变长码变长码 用树的概念可导出唯一可译码存在的充分和必用树的概念可导出唯一可译码存在的充分和必要条件要条件综上所述，可将码作如下分类：综上所述，可将码作如下分类：定理定理5.1 5.1 对于码符号为对于码符号为X=x1,x2,xr的任意唯的任意唯一可译码，其码字为一可译码，其码字为W1,W2,Wq，所对应的码所对应的码长为长为l1,l2lq，则必定满足克拉夫特不等式则必定满足克拉夫特不等式注意：克拉夫特不等式只是说明唯一可译注意：克拉夫特不等式只是说明唯一可译码是否存在，并不能作为唯一可译码的判码是否存在，并不能作为唯一可译码的判据据。【例例5.15.1】设二进制码树中设二进制码树中X=x1,x2,x3,x4，对应的对应的l1=1,l2=2,l3=2,l4=3，由上述定理，可由上述定理，可得得因此不存在满足这种码长的唯一可译码。因此不存在满足这种码长的唯一可译码。唯一可译码的判断法（变长）唯一可译码的判断法（变长）（1 1）观察码观察码C中最短的码字是否是其它码字的中最短的码字是否是其它码字的前缀，若是，将其所有可能的尾随后缀排列出。前缀，若是，将其所有可能的尾随后缀排列出。而这些尾随后缀又有可能是某些码字的前缀，而这些尾随后缀又有可能是某些码字的前缀，再将这些尾随后缀产生的新的尾随后缀列出再将这些尾随后缀产生的新的尾随后缀列出。（2 2）再观察这些新的尾随后缀是否是某些再观察这些新的尾随后缀是否是某些码字的前缀，再将产生的尾随后缀列出，码字的前缀，再将产生的尾随后缀列出，依此下去，直到没有一个尾随后缀是码字依此下去，直到没有一个尾随后缀是码字的前缀为止。的前缀为止。（3 3）这样，首先获得了由最短的码字能引起的这样，首先获得了由最短的码字能引起的所有尾随后缀，接着，按照上述步骤将次短码所有尾随后缀，接着，按照上述步骤将次短码字、字、等等所有码字可能产生的尾随后缀全部等等所有码字可能产生的尾随后缀全部列出。列出。由此得到由码由此得到由码C的所有可能的尾随后缀的集合的所有可能的尾随后缀的集合F。当且仅当集合当且仅当集合F中没有包含任一码字，则可中没有包含任一码字，则可判断此码判断此码C为唯一可译码。为唯一可译码。5.2 5.2 定长码编码定理定长码编码定理编码的目的，就是要是信源的信息率最小，编码的目的，就是要是信源的信息率最小，也就是说，要用最少的符号来代表信源。也就是说，要用最少的符号来代表信源。在定长编码中，对每一个简单信源在定长编码中，对每一个简单信源 ，码，码字的长度字的长度 都是定值，要实现无失真的信源都是定值，要实现无失真的信源编码编码要求要求:信源符号信源符号s s1 1 s s2 2s sq q是一一对应码字是一一对应码字W W1 1 W W2 2WWq q,能够无失真或无差错地从能够无失真或无差错地从W恢复恢复 ,也就是能正确地进行反变换或译码也就是能正确地进行反变换或译码 ;传送传送Y时所需要的信息率最小时所需要的信息率最小 如果对一个简单信源如果对一个简单信源S进行定长编码，那么信进行定长编码，那么信源源S存在惟一可译码的条件是存在惟一可译码的条件是q是信源是信源S的符号个数的符号个数，r是信道基本码符号是信道基本码符号数数,l是定长码的码长是定长码的码长如果对信源如果对信源S的的N次扩展信源次扩展信源SN进行定长编码，进行定长编码，若要编得的定长码是惟一可译码，则须满足若要编得的定长码是惟一可译码，则须满足对上式两边取对数，有对上式两边取对数，有 表示表示SN中平均每个原始信源符号所需中平均每个原始信源符号所需要的码符号个数。要的码符号个数。对于定长唯一可译码，平均每个原始信对于定长唯一可译码，平均每个原始信源符号至少用源符号至少用 个码符号来变换。个码符号来变换。例如英文电报有例如英文电报有3232个符号，即个符号，即 ，采用，采用二元编码时，则二元编码时，则 。对信源每个符号进。对信源每个符号进行二元编码，则行二元编码，则 ，也就是说，每，也就是说，每个英文电报符号至少要用个英文电报符号至少要用5 5位二元符号进行位二元符号进行编码才能得到唯一可译码。编码才能得到唯一可译码。定理定理5.2 5.2 设离散无记忆信源设离散无记忆信源的熵为的熵为H(S)，其，其N次扩展信源为次扩展信源为 次扩展信源熵次扩展信源熵现在用码符号集现在用码符号集X=x1,x2,xr对对N次扩展次扩展信源信源SN进行长度为进行长度为l的定长编码，对于的定长编码，对于 ，只要满足只要满足则当则当N N足够大时，必可使译码差错小于足够大时，必可使译码差错小于 。反之，若反之，若则当则当N足够大时，译码错误概率趋于足够大时，译码错误概率趋于1 1。定义定义5.25.2设熵为设熵为H(S)离散无记忆信源，若对信源的长离散无记忆信源，若对信源的长为为N的符号序列进行定长编码，设码字是从的符号序列进行定长编码，设码字是从r个码符个码符号集中选取号集中选取l个码元构成，定义个码元构成，定义R为编码速率（单位为编码速率（单位：bit/符号），即符号），即此时若此时若 则可以实现无失真传输。则可以实现无失真传输。定义称定义称 为编码效率。为编码效率。则有：则有：设差错概率为设差错概率为当当 和和 均为定值时，只要均为定值时，只要N足够足够大，大，均为定值时，只要均为定值时，只要N足够大，即足够大，即【例【例5.15.1】设离散无记忆信源概率空间为】设离散无记忆信源概率空间为信源熵为信源熵为自信息方差为自信息方差为对信源符号采用定长二元编码，要求编码效对信源符号采用定长二元编码，要求编码效率率 ，无记忆信源有无记忆信源有 ，因此因此可以得到可以得到如果要求译码错误概率如果要求译码错误概率因此，一般说来，当因此，一般说来，当N有限时，高传输效率的定长码有限时，高传输效率的定长码往往要引入一定的失真和译码错误。解决的办法是可往往要引入一定的失真和译码错误。解决的办法是可以采用变长编码。以采用变长编码。5.3 5.3 变长码定理变长码定理码平均长度码平均长度定义设有信源定义设有信源编码后的码字为编码后的码字为W1,W2,Wq，其码字相应的码长，其码字相应的码长分别为分别为l1,l2,lq。因是惟一可译码，信源符号因是惟一可译码，信源符号si和码字和码字Wi一一对应，则这个码的平均长度为一一对应，则这个码的平均长度为表示每个信源符号编码对平均需用的码符号个数表示每个信源符号编码对平均需用的码符号个数单位：码符号单位：码符号/信源符号信源符号当信源当信源S给定，信源的熵为给定，信源的熵为H(S)，则每，则每个信道码元所携带的平均信息量可以个信道码元所携带的平均信息量可以表示为表示为:传输一个码符号平均需要传输一个码符号平均需要t秒时间，则编码后信道秒时间，则编码后信道每秒传输的信息量（单位：每秒传输的信息量（单位：bit/s)定义定义5.5 5.5 对应一给定的信源和一给定的对应一给定的信源和一给定的码符号集码符号集,若有一种惟一可译码若有一种惟一可译码,其其平均平均码长码长 小于所有其他唯一可译码，则小于所有其他唯一可译码，则称这种码为紧致码，或最佳码。称这种码为紧致码，或最佳码。定理定理5.35.3设离散无记忆信源设离散无记忆信源若该离散无记忆离散信源的符号熵为若该离散无记忆离散信源的符号熵为H(S)，每个，每个信源符号信源符号的用具的用具r进制码元进行定长编码进制码元进行定长编码，一定一定存在一种无失真编码方法，其码字平均码长存在一种无失真编码方法，其码字平均码长 满满足足离散平稳无记忆序列变长编码定理离散平稳无记忆序列变长编码定理（香农第一定理）（香农第一定理）定理定理5.45.4设离散无记忆信源设离散无记忆信源的熵为的熵为H(S)，其其N次扩展信源为次扩展信源为现在用码符号集现在用码符号集X=x1,x2,xr 对对N次扩展信源次扩展信源SN进行编码，总可以找到一种编码方法，构成惟一进行编码，总可以找到一种编码方法，构成惟一可译码，使信源可译码，使信源S中的每个信源符号所需的码字平中的每个信源符号所需的码字平均长度满足均长度满足或或且当且当N时，则：时，则：号号si所对应的平均码长。所对应的平均码长。定义定义5.7 5.7 编码效率定义为编码效率定义为表示离散无记忆信源表示离散无记忆信源S S中的每个信源符中的每个信源符定义定义5.65.6变长编码的编码速变长编码的编码速率定义为率定义为它表示编码后平均每个信源符号能载荷的它表示编码后平均每个信源符号能载荷的最大信息量。于是，定理最大信息量。于是，定理5.45.4又可表述为，又可表述为，其中其中，L为平均码长。此处为平均码长。此处 L=故编码效率一定小于或等于故编码效率一定小于或等于1 1的数。的数。定义对于变长码，定义码的剩余度为定义对于变长码，定义码的剩余度为【例【例5.45.4】设离散无记忆信源的概率空间为】设离散无记忆信源的概率空间为其信源熵为其信源熵为比特比特/符号符号若用二元定长编码（若用二元定长编码（0,10,1）来构造一个即时码：）来构造一个即时码：这时平均码长这时平均码长二元码符号二元码符号/信源符号信源符号编码效率为编码效率为输出的信息率为输出的信息率为比特比特/二元码符号二元码符号再对长度为再对长度为2 2的信源序列进行变长编码，其即时的信源序列进行变长编码，其即时码如码如下下表所示表所示序列序列序列概念序列概念即时码即时码序列序列序列概率序列概率即时码即时码9/1603/161103/16101/16111这个码得码字平均长度这个码得码字平均长度二元码符号二元码符号/信源符号信源符号每一单个符号的平均码长每一单个符号的平均码长二元码符号二元码符号/信源符号信源符号其编码效率其编码效率用同样的方法可进一步将信源序列的长度用同样的方法可进一步将信源序列的长度增加，增加，L=3或或L=4，对这些信源序列，对这些信源序列X进行进行编码，并求出其编码效率为编码，并求出其编码效率为这时信息传输率分别为这时信息传输率分别为如果对这一信源采用定长二元码编码，要求编如果对这一信源采用定长二元码编码，要求编码效率达到码效率达到96%96%时，允许译码错误概率时，允许译码错误概率 自信息的方差自信息的方差10-5 2=0.4715所需要的信源序列长度所需要的信源序列长度4.13107 5.4 5.4 最佳编码最佳编码紧致码：紧致码：香农、费诺、霍夫曼香农、费诺、霍夫曼香农香农码、费诺码、霍夫曼码码、费诺码、霍夫曼码都考虑了信都考虑了信源的源的统计特性统计特性,使经常出现的信源符号对使经常出现的信源符号对应较短的码字应较短的码字,使信源的平均码长缩短使信源的平均码长缩短,从而实现了对信源的压缩；从而实现了对信源的压缩；香农香农码码有系统的、有系统的、惟一惟一的编码方法的编码方法,但但在很多情况下编码效率不是很高；在很多情况下编码效率不是很高；费诺费诺码和码和霍夫曼霍夫曼码的编码方法都码的编码方法都不惟一不惟一；费诺码比较适合于对分组概率相等或接费诺码比较适合于对分组概率相等或接近的信源编码近的信源编码,费诺码也可以编费诺码也可以编m进制码进制码,但但m越大越大,信源的符号数越多信源的符号数越多,可能的编可能的编码方案就越多码方案就越多,编码过程就越复杂编码过程就越复杂,有时有时短码未必能得到充分利用；短码未必能得到充分利用；霍夫曼码霍夫曼码对信源的统计特性没有特殊要求对信源的统计特性没有特殊要求,编码效率比较高编码效率比较高,对编码设备的要求也比对编码设备的要求也比较简单较简单,因此因此综合性能优于综合性能优于香农码和费诺香农码和费诺码。码。1.香香农（Shannon）编码 (1)(1)将信源消息符号按其出将信源消息符号按其出现的概率大小依次的概率大小依次排列排列 (2)(2)确定确定满足下列不等式的整数足下列不等式的整数码长Ki。(3)(3)为了编成唯一可译码，计算第为了编成唯一可译码，计算第i个消息个消息的累加概率的累加概率 (4)(4)将累加概率将累加概率Pi变换成二进制数。变换成二进制数。(5)(5)取取Pi二进数的小数点后二进数的小数点后Ki位即为该消息位即为该消息符号的二进制码字。符号的二进制码字。例例5.4 设信源共信源共7个符号消息，个符号消息，a1、a2、a3、a4、a5、a6、a7，概率分，概率分别为别为0.20、0.19、0.18、0.17、0.15、0.10、0.01，求，求香香农编码。信源消息符信源消息符号号ai符号概符号概率率p(ai)累加概率累加概率Pi-log p(ai)码码字字长长度度Ki码码字字a10.2002.323000a20.190.22.393001a30.180.392.473011a40.170.572.563100a50.150.742.743101a60.100.893.3241110a70.010.996.6471111110 信源熵：信源熵：信源符号的平均码长为：信源符号的平均码长为：编码效率为：编码效率为：香香农编码方法特点：方法特点：由于由于ki总是是进一取整，香一取整，香农编码方法不一定方法不一定是最佳的；是最佳的；码字集合是惟一的，且字集合是惟一的，且为即即时码；先有先有码字的字的长度再有度再有码字；字；对于一些信源，于一些信源，编码效率不高，多余度稍大，效率不高，多余度稍大，因此其因此其实用性受到用性受到较大限制。大限制。2.费诺编码方法费诺编码方法 费诺编码属于概率匹配编码费诺编码属于概率匹配编码 (1)将将信信源源消消息息符符号号按按其其出出现现的的概概率率大大小小依依次次排列：排列：(2)将将依依次次排排列列的的信信源源符符号号按按概概率率值值分分为为两两大大组组，使使两两个个组组的的概概率率之之和和近近于于相相同同，并并对对各各组组赋予一个二进制码元赋予一个二进制码元“0”和和“1”。(3)将每一大将每一大组的信源符号的信源符号进一步再分成两一步再分成两组，使划分后的两个使划分后的两个组的的概率之和近于相同概率之和近于相同，并又，并又赋予两个予两个组一个二一个二进制符号制符号“0”和和“1”。(4)如此重复，直至每个如此重复，直至每个组只剩下一个信源符只剩下一个信源符号号为止。止。(5)信源符号所信源符号所对应的的码字即字即为费诺码。例例5.5 设信源共信源共7个符号消息，个符号消息，a1、a2、a3、a4、a5、a6、a7，概率分，概率分别为别为0.20、0.19、0.18、0.17、0.15、0.10、0.01，求，求费诺编码。消消息息符符号号ai各各 个个 消消息息概概率率 p(ai)第一次第一次分分组组第二次第二次分分组组第三次第三次分分组组第四次第四次分分组组二元二元码码字字码长码长Kia10.2000002a20.19100103a30.1810113a40.1710102a50.15101103a60.101011104a70.01111114 信源符号的平均信源符号的平均码长为：编码效率效率为：例例5.6 有一单符号离散无记忆信源有一单符号离散无记忆信源 对该信源用费诺编码方法，求其二进制对该信源用费诺编码方法，求其二进制代码组及其编码效率。代码组及其编码效率。信源符号信源符号概率概率编码编码码字码字码长码长x10.2500002x20.251012x30.1251001003x40.12511013x50.062510011004x60.0625111014x70.06251011104x80.0625111114 该信源信源熵为：平均平均码长：编码效率：效率：费诺编码特点：特点：概率大，概率大，则分解的次数小；概率小分解的次数小；概率小,则分解的分解的次数多。次数多。这符合最佳符合最佳编码原原则。码字集合是惟一可字集合是惟一可译码，且，且为即即时码；分解完了，同分解完了，同时可以得到可以得到码字和字和码长。3.哈夫曼编码方法哈夫曼编码方法 (1)将信源消息符号按其出现的概率大小依次排将信源消息符号按其出现的概率大小依次排列，列，(2)取两个概率最小的字母分别配以取两个概率最小的字母分别配以0和和1两个码两个码元，并将这两个概率相加作为一个新字母的概率，元，并将这两个概率相加作为一个新字母的概率，与未分配的二进符号的字母重新排队。与未分配的二进符号的字母重新排队。(3)对重重排排后后的的两两个个概概率率最最小小符符号号重重复复步步骤(2)的的过程。程。(4)不不断断继续上上述述过程程，直直到到最最后后两两个个符符号号配配以以0和和1为止。止。(5)从从最最后后一一级开开始始，向向前前返返回回得得到到各各个个信信源源符号所符号所对应的的码元序列，即相元序列，即相应的的码字。字。例例5.7 设信源共信源共7个符号消息，个符号消息，a1、a2、a3、a4、a5、a6、a7，概率分，概率分别为别为0.20、0.19、0.18、0.17、0.15、0.10、0.01，求，求哈夫哈夫曼曼编码。5.2 5.2 无失真信源无失真信源编码0.200.190.180.170.150.100.0101010101010.200.190.180.170.150.110.260.200.190.180.170.350.260.200.190.390.350.260.610.391.001信源符号信源符号ai概率概率p(ai)码码字字Wi码长码长Kia10.20102a20.19112a30.180003a40.170013a50.150103a60.1001104a70.0101114 信源符号的平均信源符号的平均码长为：编码效率效率为：哈夫曼哈夫曼编码方法得到的方法得到的码并非唯一的。并非唯一的。每每次次对信信源源缩减减时，赋予予信信源源最最后后两两个个概概率率最最小小的的符符号号，用用0和和1是是可可以以任任意意的的，所所以以可可以以得得到到不不同同的的哈哈夫夫曼曼码，但但不不会会影影响响码字的字的长度。度。对信信源源进行行缩减减时，两两个个概概率率最最小小的的符符号号合合并并后后的的概概率率与与其其它它信信源源符符号号的的概概率率相相同同时，这两两者者在在缩减减信信源源中中进行行概概率率排排序序，其其位位置置放放置置次次序序是是可可以以任任意意的的，故故会会得得到到不不同同的的哈哈夫夫曼曼码，此此时将将影影响响码字的字的长度。度。例例5.8 设有离散无记忆信源设有离散无记忆信源 求求哈夫曼编码。哈夫曼编码。01010101解法一解法一1.00.40.20.20.2 0.40.40.20.60.40.40.20.20.10.1 信源符号信源符号ai概率概率p(ai)码码字字Wi1码长码长Ki1a10.411a20.2012a30.20003a40.100104a50.100114解法二解法二010101011.00.40.20.20.2 0.40.40.20.60.40.40.20.20.10.1 信源符号信源符号ai概率概率p(ai)码码字字Wi2码长码长Ki2a10.4002a20.2102a30.2112a40.10103a50.10113 信源符号的平均信源符号的平均码长为：编码效率效率为：在实际应用中，选择那种编码方法？在实际应用中，选择那种编码方法？我们定义码字长度的方差为我们定义码字长度的方差为ki与平均码与平均码长之差的平方的数学期望，记为长之差的平方的数学期望，记为 2，即，即 计算上例中两种算上例中两种码的方差分的方差分别得得 21=1.36 22=0.16 可可见第二种第二种编码方法的方法的码长方差要小方差要小许多。多。这意味着第二种意味着第二种编码方法的方法的码长变化化较小，比小，比较接近平均接近平均码长。进行哈夫曼行哈夫曼编码时，为得到得到码方差最方差最小的小的码，应使合并的信源符号位于使合并的信源符号位于缩减减信源序列尽可能高的位置上，以减少再信源序列尽可能高的位置上，以减少再次合并的次数，充分利用短次合并的次数，充分利用短码。哈夫曼哈夫曼码是用概率匹配方法是用概率匹配方法进行信源行信源编码。哈哈夫夫曼曼码的的编码方方法法保保证了了概概率率大大的的符符号号对应于于短短码，概概率率小小的的符符号号对应于于长码，充充分分利利用了短用了短码；缩减减信信源源的的最最后后二二个个码字字总是是最最后后一一位位不不同同，从而保从而保证了哈夫曼了哈夫曼码是即是即时码。把二把二进制的制的编码方法推广到方法推广到m进制哈夫制哈夫曼曼码。所不同的只是每次把。所不同的只是每次把m个概率最个概率最小的符号分小的符号分别用用0,1,m-1等等码元来表示，元来表示，然后再合并成一个新的信源符号。其余然后再合并成一个新的信源符号。其余步步骤与二与二进制制编码相同。相同。在在编m进制哈夫曼制哈夫曼码时，为了使平均了使平均码长最短，必最短，必须使最后一步使最后一步缩减信源有减信源有m个信源符号。个信源符号。这样，第一步，第一步给概率最小概率最小的符号分配的符号分配码元元时，所取的符号数就不，所取的符号数就不一定是一定是m个。个。所所谓全全树，就是，就是码树图中每个中中每个中间节点点后后续的枝数必的枝数必为m。若有些若有些节点的后点的后续枝数不足枝数不足m，就称就称为非全非全树。必。必须用非用非全全树时，第一次分配，第一次分配码元就不能取元就不能取m个个符号。符号。对于于m进制制编码，若所有，若所有码字构成全字构成全树，可，可分离的分离的码字数必字数必为：m+k(m-1)式中式中k为非非负整数。因整数。因为从根从根节点开始，必点开始，必须伸出伸出m个个树枝才能构成全枝才能构成全树。以后每次从一个。以后每次从一个节点分出点分出m枝，枝，码字数就增加字数就增加m-1个，即去掉个，即去掉原来的一个原来的一个码字，加上字，加上m个个码字，所以字，所以总码字字数必数必为m+k(m-1)个才能构成全个才能构成全树。若信源所含的符号数若信源所含的符号数n不能构成不能构成m进制制的全的全树，就必，就必须增加增加s个不用的个不用的码字来形字来形成全成全树。显然然sm-1。当有当有s个个码字不用字不用时，第一次，第一次对最小概最小概率符号分配率符号分配码元元时就只取就只取m-s个，分个，分别配配以以0,1,m-s-1，把把这些符号的概率相加些符号的概率相加作作为一个新的符号概率，与其他符号一一个新的符号概率，与其他符号一起重新排列。以后每次就可以取起重新排列。以后每次就可以取m个符个符号，分号，分别配以配以0,1,m-1；如此下去。如此下去。例例5.9 设单符号离散无记忆信源如下，对信源设单符号离散无记忆信源如下，对信源编三进制哈夫曼码。编三进制哈夫曼码。m=3，n=8 令令k=3，m+k(m-1)=9 则不用的码字数为则不用的码字数为s=9-n=1，所以第一次取所以第一次取m-s=2个符号进行编码。个符号进行编码。概率概率编码过程编码过程0.220.380.092012101.0三进制代码组三进制代码组ki消息消息x6x2x3x4x5x1x7x80.070.10.180.10.40.060.050.04100120102122111220020112222233 平均平均码长 相相应的信息率的信息率 编码效率效率