1、华北电力大学电子与通信工程系1第三章第三章 离散信源无失真编码离散信源无失真编码2用尽可能少的符号来传输信源消息，目的是提高传输效用尽可能少的符号来传输信源消息，目的是提高传输效率，这是信源编码应考虑的问题，这章讨论在不允许失真情况率，这是信源编码应考虑的问题，这章讨论在不允许失真情况下的信源编码。等长编码定理给出了等长编码条件下，其码长下的信源编码。等长编码定理给出了等长编码条件下，其码长的下限值，变长编码定理（香农第一定理）给出了信源无失真的下限值，变长编码定理（香农第一定理）给出了信源无失真变长编码时其码长的上、下限值。本章还介绍了三种通用信源变长编码时其码长的上、下限值。本章还介绍了三
2、种通用信源编码方法：香农编码法、费诺编码法和霍夫曼编码法。编码方法：香农编码法、费诺编码法和霍夫曼编码法。内内 容容 提提 要要33.1 3.1 概概 述述一信源编码的模型一信源编码的模型为了实现高效、可靠的通信，引入了信源编码和信道编码。为了实现高效、可靠的通信，引入了信源编码和信道编码。用尽可能少的信道传输符号来传递信源消息，目的是提高传输效率，用尽可能少的信道传输符号来传递信源消息，目的是提高传输效率，这是信源编码主要应考虑的问题。这是信源编码主要应考虑的问题。如何增加信号的抗干扰能力，提高传输的可靠性，这是信道编码主要如何增加信号的抗干扰能力，提高传输的可靠性，这是信道编码主要考虑的问
3、题。解决这一问题，一般是采用冗余编码法，赋予信码自身一定考虑的问题。解决这一问题，一般是采用冗余编码法，赋予信码自身一定的纠错和检错能力，只要采取适当的信道编码和译码措施，就可使信道传的纠错和检错能力，只要采取适当的信道编码和译码措施，就可使信道传输的差错概率降到允许的范围之内。输的差错概率降到允许的范围之内。综上所述，提高抗干扰能力往往是以降低信息传输效率为代价综上所述，提高抗干扰能力往往是以降低信息传输效率为代价 的，而为了提高传输效率又往往削弱了其抗干扰能力。这样，的，而为了提高传输效率又往往削弱了其抗干扰能力。这样，设计者在取舍之间就要作均衡考虑。设计者在取舍之间就要作均衡考虑。4信源
4、编码的概念信源编码的概念：对信源的原始符号序列按一定的数学规则映射成由码：对信源的原始符号序列按一定的数学规则映射成由码符号组成的码序列的过程符号组成的码序列的过程。信源编码包括两个功能：信源编码包括两个功能：（1）将信源符号变换成适合信道传输的符号；）将信源符号变换成适合信道传输的符号；（2）压缩信源冗余度，提高传输效率。）压缩信源冗余度，提高传输效率。无失真无失真信源编码信源编码信源符号可以通过编码序列无差错地恢复信源符号可以通过编码序列无差错地恢复（适用于离散信源的编码）（适用于离散信源的编码）信信源源编编码码器器限失真限失真信源编码信源编码信源符号不能通过编码序列无差错地恢复信源符号不
5、能通过编码序列无差错地恢复(可以把差错限制在某一个限度内）可以把差错限制在某一个限度内）5信源编码模型：信源编码模型：码长（码长（n）：）：每个码字中所包含的码元的个数每个码字中所包含的码元的个数 D元码元码/D进制码进制码码（字）集合码（字）集合/码组码组/码码6中文电报编码：中文电报编码：信源编码器信源编码器I：110000个汉字分别对应个汉字分别对应00009999信源编码器信源编码器II：每位十进制数对应五位二进制等重码。对应关系如下：每位十进制数对应五位二进制等重码。对应关系如下：（101011，211001，.，910011，001101）如：如：11001110010110101
6、10109480022国中7二码的分类二码的分类信源编码可看成是从信源符号集到码符号集的一种映射，即将信源符信源编码可看成是从信源符号集到码符号集的一种映射，即将信源符号集中的每个元素（可以是单符号，也可以是符号序列）映射成一个长度号集中的每个元素（可以是单符号，也可以是符号序列）映射成一个长度为为n的码字。对于同一个信源，编码方法是多种的。的码字。对于同一个信源，编码方法是多种的。用用 a,b,c,d 表示信源的四个消息，码符号集为表示信源的四个消息，码符号集为0,1，下表列，下表列 出了该信源的几种不同编码。出了该信源的几种不同编码。信源符号信源符号 码码C1码码C2码码C3码码C4码码C
7、5码码C6a 0 0 00 0 1 0b 0 1 01 10 01 01c 1 10 10 110 001 011 10 11 111 0001 0111d 118等长码等长码码码变长码变长码一个码中所一个码中所有码字的码有码字的码长都相同长都相同一个码中所一个码中所有码字的码有码字的码长长不不都相同都相同1.1.几个基本概念几个基本概念:信源符号信源符号 码码C1码码C2码码C3码码C4码码C5码码C6a 0 0 00 0 1 0b 0 1 01 10 01 01c 1 10 10 110 001 011 10 11 111 0001 0111d 119非奇异码非奇异码码码奇异码奇异码码中没
8、有重复码中没有重复的码字，也即的码字，也即信源消息符号信源消息符号与码字之间是与码字之间是一一对应的一一对应的码中若存在重复码中若存在重复的码字，称为奇的码字，称为奇异码，也即会将异码，也即会将不同的信源消息不同的信源消息符号对应为同一符号对应为同一个码字。个码字。信源符号信源符号 码码C1码码C2码码C3码码C4码码C5码码C6a 0 0 00 0 1 0b 0 1 01 10 01 01c 1 10 10 110 001 011 10 11 111 0001 0111d 11102 2原码原码C的的N次扩展码次扩展码将原信源的将原信源的N次扩展信源的符号序列中，每个信源符号的码字排列起次扩
9、展信源的符号序列中，每个信源符号的码字排列起来，就构成长为来，就构成长为N的符号序列的码字，所有符号序列的码字构成的码组称的符号序列的码字，所有符号序列的码字构成的码组称为为原码原码C的的N次扩展码，记为次扩展码，记为C(N)。信源符号集合信源符号集合X=x0，x1 信道符号集合信道符号集合B=0，1码集合码集合C=0，1 X的二次扩展信源的二次扩展信源 X2=x0 x0,x0 x1,x1x0,x1x1 码码C的二次扩展码的二次扩展码 C(2)=00,01,10,11相当于原码相当于原码C的级联码的级联码113 3惟一可译码（惟一可译码（Uniquely decodable code）定义定义
10、：如果码的任意：如果码的任意N次扩展码都是非奇异码，则称该码为次扩展码都是非奇异码，则称该码为惟一可译码惟一可译码。惟一可译码惟一可译码延长码（前缀码）延长码（前缀码）某些码字是其他某些码字是其他码字的前缀，或码字的前缀，或者说，某些码字者说，某些码字后面增加一些码后面增加一些码元就可以变成其元就可以变成其他码字他码字非延长码非延长码（异前缀码）（异前缀码）码中的任何一个码中的任何一个码字都不是其他码字都不是其他码字的前缀，或码字的前缀，或者说，任一个码者说，任一个码字后面增加一些字后面增加一些信道符号（码元）信道符号（码元）都不可能变成另都不可能变成另一个码字一个码字非延长码一定是惟一可译码
11、非延长码一定是惟一可译码延长码不全是惟一可译码延长码不全是惟一可译码12d 11信源符号信源符号 码码C1码码C2码码C3码码C4码码C5码码C6a 0 0 00 0 1 0b 0 1 01 10 01 01c 1 10 10 110 001 011 10 11 111 0001 0111对于等长码，只要非奇异，就惟一可译对于等长码，只要非奇异，就惟一可译13定理定理：D进制码集合进制码集合C C=c1，c2，cM，码集中每一，码集中每一ci（i=1,2,M）都是一个）都是一个D进制符号串，设进制符号串，设c1，c2，cM 对应的码对应的码长分别是长分别是n1，n2，nM，则存在惟一可译码的充
12、要条件是，则存在惟一可译码的充要条件是 11iMinD（克拉夫特不等式）克拉夫特不等式）惟一可译码的存在性定理惟一可译码的存在性定理克拉夫特不等式所说的充要条件是对于码长组合而言的，而不是克拉夫特不等式所说的充要条件是对于码长组合而言的，而不是对于码字本身。也就是说，满足克拉夫特不等式的码长组合一定对于码字本身。也就是说，满足克拉夫特不等式的码长组合一定能构成惟一可译码，但满足克拉夫特不等式的码不一定是惟一可能构成惟一可译码，但满足克拉夫特不等式的码不一定是惟一可译码。译码。惟一可译码不是唯一的。惟一可译码不是唯一的。14码码1，码长组合为，码长组合为1，1，1，2，2-13+2-2=1.75
13、1，不满足，不满足Kraft不不等式，故不是单义可译码；等式，故不是单义可译码；码码2的码长组合为的码长组合为1，1，2，2，不满足，不满足Kraft不等式，故也不是单不等式，故也不是单义可译码；义可译码；码码3的码长组合为的码长组合为2，2，2，2，2-24=1，满足，满足Kraft不等式，但不等式，但还不能确定其是否为单义可译码。又因为码还不能确定其是否为单义可译码。又因为码3是异前缀码，故是单是异前缀码，故是单义可译码；义可译码；再如，码再如，码0，11，100，110，码长组合满足，码长组合满足Kraft不等式，但不是不等式，但不是单义可译码，单义可译码，110可译为可译为d，也可译为
14、，也可译为ba；如果将该码的编；如果将该码的编码方法稍加改变为码方法稍加改变为0，10，110，111，即为单义可译码，又还是异，即为单义可译码，又还是异前缀码，故还是即时码。前缀码，故还是即时码。信源符号信源符号 码码C1码码C2码码C3码码C4码码C5码码C6a 0 0 00 0 1 0b 0 1 01 10 01 01c 1 10 10 110 001 011 10 11 111 0001 0111d 11154即时码即时码即时码：即时码：例中码例中码5，收到，收到“1”后就知道一个码字已经完结，无须等待下后就知道一个码字已经完结，无须等待下一个符号抵达，所以异前缀码能够即时译码，称之为
15、一个符号抵达，所以异前缀码能够即时译码，称之为即时可译即时可译码码，简称，简称即时码即时码。信源符号信源符号 码码C1码码C2码码C3码码C4码码C5码码C6a 0 0 00 0 1 0b 0 1 01 10 01 01c 1 10 10 110 001 011 10 11 111 0001 0111d 11及及时时码码及及时时码码及及时时码码非非及及时时码码 即时码是惟一可译码，而惟一可译码不一定是即时码即时码是惟一可译码，而惟一可译码不一定是即时码16码的树图构造码的树图构造方法：方法：对于对于D进制码，从树根出发，可引出进制码，从树根出发，可引出D根树枝，每根树枝分别赋予根树枝，每根树枝
16、分别赋予一个不同的码符号，树枝的端点为节点，每一个节点又可引出一个不同的码符号，树枝的端点为节点，每一个节点又可引出D根根分枝，又分别赋予这分枝，又分别赋予这D根分枝每根一个不同的码符号，如某一节点根分枝每根一个不同的码符号，如某一节点被定为码字后，就不再引出树枝，该节点称为终节点。码字就是从被定为码字后，就不再引出树枝，该节点称为终节点。码字就是从树根出发，到达终节点所对应的码符号序列。树根出发，到达终节点所对应的码符号序列。用树图法表示码（用树图法表示码（1，01，001，0001）。）。17码的分类结构图码的分类结构图18对于对于变长码变长码，码集，码集C的的平均码长平均码长定义为码定义
17、为码C中每个码字中每个码字ci(i=1,2,，M)其码长的概率加权平均值，用符号其码长的概率加权平均值，用符号 表示表示 n1Miiinn p式中式中ni是码字是码字ci所对应的码长，所对应的码长，p i是码字是码字ci出现的概率。出现的概率。对于对于等长码等长码，由于码集，由于码集C中的每个码字的码长都相同，中的每个码字的码长都相同，平均码长平均码长就就等于每个码字的码长等于每个码字的码长 11MMiiiiinn pnpn19计算下表各码的平均码长：计算下表各码的平均码长：信源消息信源消息各消息概率各消息概率码码1码码2码码3码码4u10.4000001u20.21101110u30.210
18、1000100u40.21111111000平均码长平均码长221.42.2【推广】【推广】N次扩展码的平均码长次扩展码的平均码长 等于扩展码中码字长度的概率加权平均值等于扩展码中码字长度的概率加权平均值。n对于对于2次扩展码，有：次扩展码，有：msmsmsnnn p up u设设nm，ns分别是原信源消息分别是原信源消息um，us所对应的码长，所对应的码长，cm，cs是是um，us所对所对应的码字，则式中的应的码字，则式中的nm+ns是扩展后新的信源序列是扩展后新的信源序列nmns所对应的码字所对应的码字cmcs的的长度，长度，p(um)p(us)是是cmcs出现的概率。出现的概率。20定义
19、：定义：编码后每个信道码元所携带的平均信息量称为编码后信道的编码后每个信道码元所携带的平均信息量称为编码后信道的信息传信息传 输率输率。（2）若信息量以比特为单位，传送每个码元用）若信息量以比特为单位，传送每个码元用t秒，则秒，则定义为：定义为：()DRHXtttnR（比特（比特/秒）秒）式中：式中：H(X)为信源熵；为信源熵；为编码后的平均码长；为编码后的平均码长；t为传输一个码符号的时间。为传输一个码符号的时间。n（1）若信息量以比特为单位，则）若信息量以比特为单位，则记为：记为：DH XRn(比特比特/码元码元)21给定信源给定信源0123456711111111()4488161616
20、16xxxxxxxxXp X为提高传输效率，使平均码长尽可能短，遵照为提高传输效率，使平均码长尽可能短，遵照概率大取码长短，概率小取码长长的原则对上概率大取码长短，概率小取码长长的原则对上述信源进行二进制不等长编码，得到如右编码述信源进行二进制不等长编码，得到如右编码方案方案，求编码后的信息传输率，求编码后的信息传输率RD。04152637:00:1000:01:1001:110:1110:101:1111xxxxxxxx1111112log2log4log2.7544881616HX（比特（比特/符号）符号）1112223442.754816n（码元（码元/符号）符号）2.7512.75DH
21、 XRn(比特比特/码元码元)22考虑对一简单信源考虑对一简单信源X进行等长编码，信源符号集有进行等长编码，信源符号集有K个符号，码符号集个符号，码符号集含含D个符号，码字长度记为个符号，码字长度记为n。对信源作等长无差错编码，要得到惟一可译。对信源作等长无差错编码，要得到惟一可译码，必须满足下式：码，必须满足下式：K D n对单符号信源对单符号信源X的的L次扩展信源次扩展信源XL进行等长编码，要得到长为进行等长编码，要得到长为n的惟一的惟一可译码，必须满足可译码，必须满足:K L D n对上式两边取对数，得：对上式两边取对数，得：loglognKLD23下面的定理将说明，当满足一定的条件时，
22、在下面的定理将说明，当满足一定的条件时，在L 时，失真时，失真pe 0。【定理】等长编码定理【定理】等长编码定理 ，对信源输出的，对信源输出的L长序列长序列si，i=1,2,KL 进行等进行等长编码，码字是长度为长编码，码字是长度为n的的D进制符号串，当满足条件进制符号串，当满足条件 ，则，则L 时，可使译码差错时，可使译码差错pe(、为无穷小量为无穷小量)；反之，当；反之，当 时，则时，则不可能实现无差错编码。不可能实现无差错编码。设离散无记忆信源设离散无记忆信源X=x1,x2,xk的熵为的熵为H(X)，X的的L维扩展信源为维扩展信源为 12,()Xs ssLLklogH X+nLDlogH
23、 X+nLD24码率码率的定义式为的定义式为 log/nDRbitL 信源符号表示编码后，一个信源符号平均携带的最大信息量，也可以理表示编码后，一个信源符号平均携带的最大信息量，也可以理解为传送一个信源符号需要的平均信息量。解为传送一个信源符号需要的平均信息量。如果信源每秒发出如果信源每秒发出1/t个信源符号，那么个信源符号，那么 tlog/s()nDRbitbpstL 就表示信源每秒发出的符号需要多少就表示信源每秒发出的符号需要多少bit来表示。由于每一位二来表示。由于每一位二进制数所能携带的最大信息量是进制数所能携带的最大信息量是1bit，码率也称为，码率也称为位速位速。25等长编码定理要
24、求等长编码定理要求 ，即，即 ，可看出比值，可看出比值 是一个小于是一个小于1的无量纲纯数，定义它为等长编码的的无量纲纯数，定义它为等长编码的，记为：，记为：logH XnLD()1logL H XnD()logLH XnD()logLH XnD编码效率编码效率是衡量编码质量的一个重要指标，对信源编码是衡量编码质量的一个重要指标，对信源编码时应尽量提高编码效率。时应尽量提高编码效率。26根据前面计算，由等长编码定理计算出的下界更小，但由于码长都根据前面计算，由等长编码定理计算出的下界更小，但由于码长都取整，故取取整，故取n1=n2=2。并做如下编码：。并做如下编码：，得到唯一可，得到唯一可译码
25、。译码。012:00:01:10 xxx；（1）给定离散无记忆信源）给定离散无记忆信源 ，对该信，对该信源进行二进制等长编码，并求编码效率。源进行二进制等长编码，并求编码效率。0120.10.70.2()XxxxP X先确定码长：信源消息数目先确定码长：信源消息数目K3，信源序列长度，信源序列长度L1，码符号数，码符号数D2loglognKLD 根据根据1loglog31.585loglog2LKnD 根据等长编码定理：根据等长编码定理：logH XnLD21.1561.156loglog2LH XnD()0.1log0.1 0.7log0.70.2log0.21.156H X （比特（比特/
26、符号）符号）27编码效率为：编码效率为：12()1.1560.578log2log2LH XnD（2）对原信源进行）对原信源进行L=2维扩展，得到新信源：维扩展，得到新信源：(2)000102101112202122(2)0.010.070.020.070.490.140.020.140.04()Xx xx xx xx xx xx xx xx xx xp X对扩展信源进行二进制等长编码。对扩展信源进行二进制等长编码。【解】【解】对扩展码对扩展码K3，信源序列长度，信源序列长度L2，码符号数，码符号数D2 由由 确定码长：确定码长：loglognKLD3log2log33.170loglog2L
27、KnD取取n3=4，对扩展信源编码的编码如下：，对扩展信源编码的编码如下：信源序列信源序列x0 x0 x0 x1x0 x2x1x0 x1x1x1x2x2x0 x2x1x2x2码字码字00000001001000110100010101100111100028编码效率：编码效率：33()2 1.1560.578log4log2LH XnD 按等长编码定理：按等长编码定理：42 1.1562.312loglog2LH XnD取取n4=3，对扩展信源编码的编码如下：，对扩展信源编码的编码如下：信源序列信源序列x0 x0 x0 x1x0 x2x1x0 x1x1x1x2x2x0 x2x1x2x2码字码字
28、000001000010011100101110111对于二进制码，取码长为对于二进制码，取码长为3，共可构成，共可构成8个不同的码字，而扩展信源含个不同的码字，而扩展信源含9个序列，故编码时对序列中概率小的两个序列赋予同一个码字个序列，故编码时对序列中概率小的两个序列赋予同一个码字000，这样，这样势必存在编码差错概率势必存在编码差错概率pe：0.010.02(0.010.02)0.030.010.020.010.02pe44()2 1.1560.771log3log2LH XnD29变长码也要求原码的任意变长码也要求原码的任意L次扩展码也是惟一可译的。变次扩展码也是惟一可译的。变长码分为即
29、时码和延长码，为保证即时译码，要求变长惟一长码分为即时码和延长码，为保证即时译码，要求变长惟一可译码采用即时码。可译码采用即时码。对于变长码，要求整个码集的平均码长力求最小，此时编对于变长码，要求整个码集的平均码长力求最小，此时编码效率最高。对于给定信源，使平均码长达到最小的编码方码效率最高。对于给定信源，使平均码长达到最小的编码方法，称为法，称为最佳编码最佳编码，得到的码集称为，得到的码集称为最佳码最佳码。30平均码长极限定理（离散无记忆信源变长编码定理）：平均码长极限定理（离散无记忆信源变长编码定理）：给定熵为给定熵为H（X）的离散无记忆信源，及有）的离散无记忆信源，及有D个元素的码符号集
30、，个元素的码符号集，则总可找到一种无失真编码方法，构成惟一可译码，其平均码则总可找到一种无失真编码方法，构成惟一可译码，其平均码长满足：长满足：1loglogH XH XnDD 定理的证明过程给了我们一种最佳编码的构造方法，即如果信源定理的证明过程给了我们一种最佳编码的构造方法，即如果信源的概率分布均有的概率分布均有 1inD的形式，那么直接取的形式，那么直接取ni作为对应消息符号的码字长度，就可以得到作为对应消息符号的码字长度，就可以得到紧致码（最佳码）。紧致码（最佳码）。3112341111()2488xxxxXP X对其进行二元编码，码长分别取对其进行二元编码，码长分别取 1，2，3，3
31、此时的平均码长为此时的平均码长为 （码元（码元/符号）符号）111123 21.75248n 信源熵为信源熵为 （bit/符号）符号）1 1 1 1()(,)1.752 4 8 8H XH编码效率编码效率()1logLH XnD信息传输率信息传输率 （bit/码元）码元）()H XRn32其其L次扩展信源次扩展信源 的熵记为的熵记为 定理：变长编码定理定理：变长编码定理(Shannon第一定理第一定理)给定熵为给定熵为H（X）的离散无记忆信源）的离散无记忆信源()()()()1212MMxxxXp xp xp xp X1212()()()()LLLMLMxxxXp xp xp xp X()LH
32、 X1loglogLH XH XnDLDL给定有给定有D个元素的码符号集，对扩展信源进行编码，总可以找到一种惟一个元素的码符号集，对扩展信源进行编码，总可以找到一种惟一可译码，使码长可译码，使码长 满足：满足：Ln1loglogH XH XnDDL记记 为信源每个符号所对应的平均码字数，则上式为：为信源每个符号所对应的平均码字数，则上式为：LnnL33编码效率编码效率：loglogH XDH XnnD是一个无量纲的数，一般情况下是一个无量纲的数，一般情况下10.811loglog2H Xn L=D取取 n=1,x10,x21,()0.811=81.1%logLH X=nD 信息传输率信息传输率
33、()0.811bit/H XR=n元（）编码速率编码速率()0.811bit/LH XR=n元（）35 对对X2进行二进制变长编码进行二进制变长编码x1x1x1x2x2x1x2x2Pi9/163/163/161/16C0101101114=1/93127=1+(2+3)+3=16161616iiiNp N元 符N27()=0.84375=0.811L32logH XnD()0.811=96.1%27loglog232H XnD()bit/=0.961H XRn元（）(严格的无失真编码严格的无失真编码)若进行等长编码效率若进行等长编码效率=0.96,=0.96,差错率差错率 Pe10-5,L4.
34、13107（有失真编码）（有失真编码）36 对对X3进行二进制变长编码进行二进制变长编码=98.5%，R=0.985 bit/符号符号 对对X3进行二进制变长编码进行二进制变长编码=99.1%，R=0.991 bit/符号符号37常用变常用变长编码长编码霍夫曼霍夫曼（Huffman）编码编码费诺费诺（Fano）编码编码香农香农（Shannon）编码编码38记离散信源记离散信源1212()()()()MMxxxXp xp xp xp X给定有给定有D个元素的码符号集，对信源进行变长编码，将各消息概率个元素的码符号集，对信源进行变长编码，将各消息概率p(xm)(m=1,2,M)写成如下的形式：写成
35、如下的形式：1()mtmp xD取码长取码长nm(m=1,2,M)满足：满足：1mmmtnt由此得香农编码法码长取值范围由此得香农编码法码长取值范围:log()log()1loglogmmmp xp xnDD 对于二进制香农编码法，有对于二进制香农编码法，有log()log()1mmmp xnp x 39编码步骤：编码步骤：（1）将信源发出的）将信源发出的M个消息，按其概率递减顺序进行排列；个消息，按其概率递减顺序进行排列；（2）计算出各消息的）计算出各消息的log p(xm)值，值，m=1,2,M；（3）根据式：）根据式：计算出每个消息的二进计算出每个消息的二进制代码的长度制代码的长度nm。
36、log()log()1mmmp xnp x（log p(xm)为整数时取等号）为整数时取等号）（4）计算出第）计算出第m个消息的累加概率个消息的累加概率 ，再将，再将pi变换成二变换成二进制小数，取小数点后面进制小数，取小数点后面nm位作为第位作为第m个消息的代码组。个消息的代码组。11()iimmpp x 40对给定信源进行对给定信源进行D=2进制香农编码并求编码效率。进制香农编码并求编码效率。1234567()0.20.190.180.170.150.100.01Xxxxxxxxp X（1）编码）编码消息符号消息符号xi消息概率消息概率p(xm)log p(xm)码长码长ni累加概率累加概
37、率pi码字码字Cix10.22.3430000 x20.192.4130.2001x30.182.4830.39011x40.172.5630.57100 x50.152.7430.74101x60.103.3440.891110 x70.016.6670.99111111041（2）求编码效率）求编码效率信源熵：信源熵：71()()log()2.61mmmH Xp xp x 比特比特/符号符号平均码长：平均码长：71()3.14mmmnp xn码元码元/符号符号编码效率：编码效率：()2.610.831log3.14 log2H XnD消息符号消息符号xi消息概率消息概率p(xm)log p
38、(xm)码长码长ni累加概率累加概率pi码字码字Cix10.22.3430000 x20.192.4130.2001x30.182.4830.39011x40.172.5630.57100 x50.152.7430.74101x60.103.3440.891110 x70.016.6670.99111111042费诺编码法的具体步骤如下：费诺编码法的具体步骤如下：（1）信源发出的）信源发出的M个消息，按其概率递减顺序进行排列，把消息集个消息，按其概率递减顺序进行排列，把消息集 x1,x2,x3,xM 按其概率大小分解成两个子集，使按其概率大小分解成两个子集，使两个子集的概率之两个子集的概率之和
39、尽可能接近相等和尽可能接近相等，把第一个子集编码为，把第一个子集编码为“0”，第二个子集编码，第二个子集编码为为“1”，作为代码组的第一个码元；，作为代码组的第一个码元；（2）对子集做第二次分解，同样分解成两个子集，并使两个子集的概）对子集做第二次分解，同样分解成两个子集，并使两个子集的概率尽可能接近相等，再把第一个子集编码为率尽可能接近相等，再把第一个子集编码为“0”，第二个子集编，第二个子集编码为码为“1”，作为代码组的第二个码元；，作为代码组的第二个码元；（3）如此一直进行下去，直到各子集仅含一个消息为止；）如此一直进行下去，直到各子集仅含一个消息为止；（4）将逐次分解过程当中得到的码元
40、排列起来就是各消息的代码。）将逐次分解过程当中得到的码元排列起来就是各消息的代码。43对给定信源进行对给定信源进行D=2进制费诺编码并求编码效率。进制费诺编码并求编码效率。1234567()0.20.190.180.170.150.100.01Xxxxxxxxp Xxmp(xm)第一次第一次分解分解第二次第二次分解分解第三次第三次分解分解第四次第四次分解分解代码组代码组 长度长度nmx10.20.57（0）0.2（0）002x20.190.37（1）0.19（0）0103x30.180.18（1）0113x40.170.43（1）0.17（0）102x50.150.26（1）0.15（0）11
41、03x60.100.11（1）0.10（0）11104x70.010.01（1）11114信源熵：信源熵：71()()log()2.61mmmH Xp xp x 比特比特/符号符号平均码长：平均码长：()712.74mmm=n=p xn码元码元/符号符号编码效率：编码效率：()2.61=0.9352.74 log2H XnlogD441.霍夫曼编码法的具体步骤如下：（先考虑霍夫曼编码法的具体步骤如下：（先考虑D=2的情况）的情况）（1）将信源发出的）将信源发出的M个消息，按其概率递减顺序进行排列，得个消息，按其概率递减顺序进行排列，得p(x1)p(x2)p(x3)p(xM)（2）将概率最小的二
42、个消息分别编码为）将概率最小的二个消息分别编码为“1”和和“0”，（一般，将概率大的，（一般，将概率大的编码为编码为“1”，概率小的编码为，概率小的编码为“0”），再对这两个消息求概率之和；），再对这两个消息求概率之和；（3）将上述概率之和作为一新消息的概率，与余下的消息一起组成一新的）将上述概率之和作为一新消息的概率，与余下的消息一起组成一新的信源，再按概率递减顺序重新排列，如果概率之和与原信源的某个概信源，再按概率递减顺序重新排列，如果概率之和与原信源的某个概率相等，则把概率之和排在上面，这样可使合并消息重复编码的次数率相等，则把概率之和排在上面，这样可使合并消息重复编码的次数减少，使短码
43、得到充分利用；减少，使短码得到充分利用；（4）如此一直进行下去，直到两个合并消息的概率之和为）如此一直进行下去，直到两个合并消息的概率之和为1；（5）从最后一步骤开始，沿编码逆程取下各步骤得到的码符号，如此构成）从最后一步骤开始，沿编码逆程取下各步骤得到的码符号，如此构成的码符号序列即为对应消息的码字。的码符号序列即为对应消息的码字。45对给定信源进行对给定信源进行D=2进制霍夫曼编码并求编码效率。进制霍夫曼编码并求编码效率。1234567()0.20.190.180.170.150.100.01Xxxxxxxxp X46信源熵：信源熵：71()()log()2.61mmmH Xp xp x
44、比特比特/符号符号平均码长：平均码长：71()2.72mmmnp xn码元码元/符号符号编码效率：编码效率：()2.610.96log2.72 log2H XnD47D进制霍夫曼编码法的具体步骤：（进制霍夫曼编码法的具体步骤：（D 2的情况）的情况）（1）将信源发出的）将信源发出的M个消息，按其概率递减顺序进行排列，得个消息，按其概率递减顺序进行排列，得p(x1)p(x2)p(x3)p(xM)（2）将概率最小的）将概率最小的m0个消息组合成一个新消息。选择个消息组合成一个新消息。选择m0的原则是使的原则是使 （N-m0）/(D-1)的比值等于正整数的最小正整数即为的比值等于正整数的最小正整数即
45、为m0（m01）的值。）的值。对这对这m0个消息分别用个消息分别用0，1，2，（，（D-1）进行编码（一般，将概率）进行编码（一般，将概率最大的编码为最大的编码为“D-1”，概率最小的编码为，概率最小的编码为“0”），再对这），再对这m0个消息求个消息求概率之和；概率之和；（3）将上述概率之和作为一新消息的概率，与余下的（）将上述概率之和作为一新消息的概率，与余下的（M-m0）个消息一起）个消息一起组成一新的信源，再按概率递减顺序重新排列，如果概率之和与原信组成一新的信源，再按概率递减顺序重新排列，如果概率之和与原信源的某个概率相等，则把概率之和排在上面，这样可使合并消息重复源的某个概率相等，
46、则把概率之和排在上面，这样可使合并消息重复编码的次数减少，使短码得到充分利用；编码的次数减少，使短码得到充分利用；（4）如此一直进行下去，直到新集合仅包含）如此一直进行下去，直到新集合仅包含D个消息为止；个消息为止；（5）从最后一步骤开始，沿编码逆程取下各步骤得到的码符号，如此构成）从最后一步骤开始，沿编码逆程取下各步骤得到的码符号，如此构成的码符号序列即为对应消息的码字。的码符号序列即为对应消息的码字。48本章讨论在不允许失真前提下对信源的编码，分为两种情况，等长编码本章讨论在不允许失真前提下对信源的编码，分为两种情况，等长编码和变长编码。等长编码定理和变长编码定理分别给出了这两种情况，在无
47、失和变长编码。等长编码定理和变长编码定理分别给出了这两种情况，在无失真和码长尽可能短这两个约束条件下的平均码长的上界和下界。真和码长尽可能短这两个约束条件下的平均码长的上界和下界。一等长编码定理一等长编码定理记记H（X）为单符号信源熵，）为单符号信源熵，L为扩展信源输出序列长度，为扩展信源输出序列长度，n为码字长度，为码字长度，D为码符号集元素个数，当满足条件为码符号集元素个数，当满足条件 logH XnLD则则L 时，可使译码差错时，可使译码差错pe(、为无穷小量为无穷小量)；反之，反之，logH XnLD则不可能实现无差错编码。则不可能实现无差错编码。本本 章章 小小 结结49二变长编码定
48、理二变长编码定理(Shannon第一定理第一定理)记记H（X）为单符号信源熵，）为单符号信源熵，L为扩展信源输出的序列长度，为扩展信源输出的序列长度，为信源每为信源每个符号所对应的平均码字数，个符号所对应的平均码字数，D为码符号集元素个数，则对信源进行编码，为码符号集元素个数，则对信源进行编码，总可以找到一种惟一可译码，使码长满足总可以找到一种惟一可译码，使码长满足 1loglogH XH XnDDL三平均码长三平均码长 1()Mmmmnn p c c四克拉夫特不等式四克拉夫特不等式 MmnmD11本章还介绍了常见的三种变长码的编码方法：本章还介绍了常见的三种变长码的编码方法：。对于同一信源的编码，三种方法中，以霍夫曼编码的编码。对于同一信源的编码，三种方法中，以霍夫曼编码的编码效率最高。香农编码法没有太多实用价值，但它在证明变长编码定理时起了效率最高。香农编码法没有太多实用价值，但它在证明变长编码定理时起了重要作用，重要作用，Fano编码法是遵照变长编码定理（香农第一定理）的指导思想导编码法是遵照变长编码定理（香农第一定理）的指导思想导出的一种编码方法。出的一种编码方法。
