第3章离散无失真信源编码精选PPT.ppt

《第3章离散无失真信源编码精选PPT.ppt》由会员分享，可在线阅读，更多相关《第3章离散无失真信源编码精选PPT.ppt（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1页，本讲稿共49页用尽可能少的符号来传输信源消息，目的是提高传输效率，这是用尽可能少的符号来传输信源消息，目的是提高传输效率，这是信源编码应考虑的问题，这章讨论在不允许失真情况下的信源编码。等信源编码应考虑的问题，这章讨论在不允许失真情况下的信源编码。等长编码定理给出了等长编码条件下，其码长的下限值，变长编码定理长编码定理给出了等长编码条件下，其码长的下限值，变长编码定理（香农第一定理）给出了信源无失真变长编码时其码长的上、下限值。（香农第一定理）给出了信源无失真变长编码时其码长的上、下限值。本章还介绍了三种通用信源编码方法：香农编码法、费诺编码法和霍夫本章还介绍了三种通用信源编码方法：香

2、农编码法、费诺编码法和霍夫曼编码法。曼编码法。内内 容容 提提 要要2第2页，本讲稿共49页3.1 3.1 概概 述述 一信源编码的模型一信源编码的模型为了实现高效、可靠的通信，引入了信源编码和信道编码。为了实现高效、可靠的通信，引入了信源编码和信道编码。（1 1）提高传输效率：提高传输效率：提高传输效率：提高传输效率：用尽可能少的信道传输符号来传递信源消息，目的是提高传输效率，这是用尽可能少的信道传输符号来传递信源消息，目的是提高传输效率，这是信源编码主要应考虑的问题。信源编码主要应考虑的问题。（2 2）增强通信的可靠性：）增强通信的可靠性：）增强通信的可靠性：）增强通信的可靠性：如何增加信

3、号的抗干扰能力，提高传输的可靠性，这是信道编码主要考虑的问题。如何增加信号的抗干扰能力，提高传输的可靠性，这是信道编码主要考虑的问题。解决这一问题，一般是采用冗余编码法，赋予信码自身一定的纠错和检错能力，只要采解决这一问题，一般是采用冗余编码法，赋予信码自身一定的纠错和检错能力，只要采取适当的信道编码和译码措施，就可使信道传输的差错概率降到允许的范围之内。取适当的信道编码和译码措施，就可使信道传输的差错概率降到允许的范围之内。综上所述，提高抗干扰能力往往是以降低信息传输效率为代价综上所述，提高抗干扰能力往往是以降低信息传输效率为代价 的，而的，而为了提高传输效率又往往削弱了其抗干扰能力。这样，

4、设计者在取舍为了提高传输效率又往往削弱了其抗干扰能力。这样，设计者在取舍之间就要作均衡考虑。之间就要作均衡考虑。3第3页，本讲稿共49页信源编码的概念信源编码的概念：对信源的原始符号序列按一定的数学规则映射成由码符号：对信源的原始符号序列按一定的数学规则映射成由码符号组成的码序列的过程组成的码序列的过程。信源编码包括两个功能：信源编码包括两个功能：（1）将信源符号变换成适合信道传输的符号；）将信源符号变换成适合信道传输的符号；（2）压缩信源冗余度，提高传输效率。）压缩信源冗余度，提高传输效率。无失真信源编码信源符号可以通过编码序列无差错地恢复信源符号可以通过编码序列无差错地恢复（适用于离散信源

5、的编码）（适用于离散信源的编码）信源编码器限失真信源编码信源符号不能通过编码序列无差错地恢复信源符号不能通过编码序列无差错地恢复(可以把差错限制在某一个限度内）可以把差错限制在某一个限度内）4第4页，本讲稿共49页信源编码模型：信源编码模型：码长（码长（n）：）：每个码字中所包含的码元的个数每个码字中所包含的码元的个数 D元码元码/D进制码进制码码（字）集合码（字）集合/码组码组/码码5第5页，本讲稿共49页【例【例【例【例3.1.13.1.1】中文电报编码：中文电报编码：信源编码器信源编码器I：110000个汉字分别对应个汉字分别对应00009999 信源编码器信源编码器II：每位十进制数对

6、应五位二进制等重码。对应关系如下：每位十进制数对应五位二进制等重码。对应关系如下：（101011，211001，.，910011，001101）如：如：6第6页，本讲稿共49页二码的分类二码的分类信源编码可看成是从信源符号集到码符号集的一种映射，即将信源符号集中的每个元素信源编码可看成是从信源符号集到码符号集的一种映射，即将信源符号集中的每个元素（可以是单符号，也可以是符号序列）映射成一个长度为（可以是单符号，也可以是符号序列）映射成一个长度为n的码字。对于同一个信源，的码字。对于同一个信源，编码方法是多种的。编码方法是多种的。【例【例【例【例3.1.23.1.2】用用 a,b,c,d 表示信

7、源的四个消息，码符号集为表示信源的四个消息，码符号集为0,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 117第7页，本讲稿共49页等长码等长码码码变长码变长码一个码中所有一个码中所有码字的码长都码字的码长都相同相同一个码中所有一个码中所有码字的码长码字的码长不不都相同都相同1.1.几个基本概念几个基本概念:信源符号信源符号 码码C1码码C2码码C3码码C4

8、码码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 118第8页，本讲稿共49页非奇异码非奇异码码码奇异码奇异码码中没有重复的码中没有重复的码字，也即信源码字，也即信源消息符号与码字消息符号与码字之间是一一对应之间是一一对应的的码中若存在重复码中若存在重复的码字，称为奇的码字，称为奇异码，也即会将异码，也即会将不同的信源消息不同的信源消息符号对应为同一符号对应为同一个码字。个码字。信源符号信源符号 码码C1码码C2码码C3码码C4码码C5码码C6a 0 0 00 0 1 0b 0 1

9、 01 10 01 01c 1 10 10 110 001 011 10 11 111 0001 0111d 119第9页，本讲稿共49页2 2原码原码C的的N次扩展码次扩展码将原信源的将原信源的N次扩展信源的符号序列中，每个信源符号的码字排列起来，就构成长为次扩展信源的符号序列中，每个信源符号的码字排列起来，就构成长为N的符号序列的码字，所有符号序列的码字构成的码组称为的符号序列的码字，所有符号序列的码字构成的码组称为原码原码C的的N次扩展码，记次扩展码，记为为C(N)。【例【例【例【例3.1.33.1.3】信源符号集合信源符号集合X=x0，x1 信道符号集合信道符号集合B=0，1码集合码集

10、合C=0，1 X的二次扩展信源的二次扩展信源 X2=x0 x0,x0 x1,x1x0,x1x1 码码C的二次扩展码的二次扩展码 C(2)=00,01,10,11相当于原码相当于原码C的级联码的级联码10第10页，本讲稿共49页3 3惟一可译码（惟一可译码（Uniquely decodable code）定义定义：如果码的任意：如果码的任意N次扩展码都是非奇异码，则称该码为次扩展码都是非奇异码，则称该码为惟一可译码惟一可译码。惟一可译码惟一可译码延长码（前缀码）延长码（前缀码）某些码字是其他某些码字是其他码字的前缀，或码字的前缀，或者说，某些码字者说，某些码字后面增加一些码后面增加一些码元就可以

11、变成其元就可以变成其他码字他码字非延长码非延长码（异前缀码）（异前缀码）码中的任何一个码字码中的任何一个码字都不是其他码字的前都不是其他码字的前缀，或者说，任一个缀，或者说，任一个码字后面增加一些信码字后面增加一些信道符号（码元）都不道符号（码元）都不可能变成另一个码字可能变成另一个码字非延长码一定是惟一可译码非延长码一定是惟一可译码延长码不全是惟一可译码延长码不全是惟一可译码11第11页，本讲稿共49页d 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

12、111 0001 0111对于等长码，只要非奇异，就惟一可译对于等长码，只要非奇异，就惟一可译12第12页，本讲稿共49页定理定理：D进制码集合进制码集合C=c1，c2，cM，码集中每一，码集中每一ci（i=1,2,M）都是一）都是一个个D进制符号串，设进制符号串，设c1，c2，cM 对应的码长分别是对应的码长分别是n1，n2，nM，则存在惟一可译码的充要条件是则存在惟一可译码的充要条件是（克拉夫特不等式）克拉夫特不等式）惟一可译码的存在性定理惟一可译码的存在性定理克拉夫特不等式所说的充要条件是对于码长组合而言的，而不是克拉夫特不等式所说的充要条件是对于码长组合而言的，而不是对于码字本身。也就

13、是说，满足克拉夫特不等式的码长组合一定对于码字本身。也就是说，满足克拉夫特不等式的码长组合一定能构成惟一可译码，但满足克拉夫特不等式的码不一定是惟一可能构成惟一可译码，但满足克拉夫特不等式的码不一定是惟一可译码。译码。惟一可译码不是唯一的。惟一可译码不是唯一的。13第13页，本讲稿共49页码码1，码长组合为，码长组合为1，1，1，2，2-13+2-2=1.751，不满足，不满足Kraft不等式，故不等式，故不是单义可译码；不是单义可译码；码码2的码长组合为的码长组合为1，1，2，2，不满足，不满足Kraft不等式，故也不是单义可译码；不等式，故也不是单义可译码；码码3的码长组合为的码长组合为2

14、，2，2，2，2-24=1，满足，满足Kraft不等式，但还不能确不等式，但还不能确定其是否为单义可译码。又因为码定其是否为单义可译码。又因为码3是异前缀码，故是单义可译码；是异前缀码，故是单义可译码；再如，码再如，码0，11，100，110，码长组合满足，码长组合满足Kraft不等式，但不是单义可译码，不等式，但不是单义可译码，110可译为可译为d，也可译为，也可译为ba；如果将该码的编码方法稍加改变为；如果将该码的编码方法稍加改变为0，10，110，111，即为单义可译码，又还是异前缀码，故还是即时码。，即为单义可译码，又还是异前缀码，故还是即时码。信源符号信源符号 码码C1码码C2码码C

15、3码码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 1114第14页，本讲稿共49页4即时码即时码即时码：即时码：例中码例中码5，收到，收到“1”后就知道一个码字已经完结，无须等待下一个符号抵后就知道一个码字已经完结，无须等待下一个符号抵达，所以异前缀码能够即时译码，称之为达，所以异前缀码能够即时译码，称之为即时可译码即时可译码，简称，简称即时码即时码。信源符号信源符号 码码C1码码C2码码C3码码C4码码C5码码C6a 0 0 00 0 1 0b 0 1 01 10 01

16、 01c 1 10 10 110 001 011 10 11 111 0001 0111d 11及及时时码码及及时时码码及及时时码码非及非及时码时码 即时码是惟一可译码，而惟一可译码不一定是即时码即时码是惟一可译码，而惟一可译码不一定是即时码15第15页，本讲稿共49页码的树图构造码的树图构造方法：方法：对于对于D进制码，从树根出发，可引出进制码，从树根出发，可引出D根树枝，每根树枝分别赋予一个不根树枝，每根树枝分别赋予一个不同的码符号，树枝的端点为节点，每一个节点又可引出同的码符号，树枝的端点为节点，每一个节点又可引出D根分枝，又分根分枝，又分别赋予这别赋予这D根分枝每根一个不同的码符号，如

17、某一节点被定为码字后，根分枝每根一个不同的码符号，如某一节点被定为码字后，就不再引出树枝，该节点称为终节点。码字就是从树根出发，到达终节就不再引出树枝，该节点称为终节点。码字就是从树根出发，到达终节点所对应的码符号序列。点所对应的码符号序列。【例【例【例【例3.1.43.1.4】用树图法表示码（用树图法表示码（1，01，001，0001）。）。16第16页，本讲稿共49页码的分类结构图码的分类结构图17第17页，本讲稿共49页三平均码长的计算三平均码长的计算三平均码长的计算三平均码长的计算对于对于变长码变长码，码集，码集C的的平均码长平均码长定义为码定义为码C中每个码字中每个码字ci(i=1,

18、2,，M)其码长的概率加权平均值，用符号其码长的概率加权平均值，用符号 表示表示 式中式中ni是码字是码字ci所对应的码长，所对应的码长，p i是码字是码字ci出现的概率。出现的概率。对于对于等长码等长码，由于码集，由于码集C中的每个码字的码长都相同，中的每个码字的码长都相同，平均码长平均码长就等于每个就等于每个码字的码长码字的码长 18第18页，本讲稿共49页【例【例【例【例3.1.53.1.5】计算下表各码的平均码长：计算下表各码的平均码长：信源消息信源消息各消息概率各消息概率码码1码码2码码3码码4u10.4000001u20.21101110u30.2101000100u40.2111

19、1111000平均码长平均码长221.42.2【推广】【推广】N次扩展码的平均码长次扩展码的平均码长 等于扩展码中码字长度的概率加权平均值等于扩展码中码字长度的概率加权平均值。对于对于2次扩展码，有：次扩展码，有：设设nm，ns分别是原信源消息分别是原信源消息um，us所对应的码长，所对应的码长，cm，cs是是um，us所对应的码字，则所对应的码字，则式中的式中的nm+ns是扩展后新的信源序列是扩展后新的信源序列nmns所对应的码字所对应的码字cmcs的长度，的长度，p(um)p(us)是是cmcs出现的概率。出现的概率。19第19页，本讲稿共49页四信息传输率四信息传输率四信息传输率四信息传

20、输率定义：定义：编码后每个信道码元所携带的平均信息量称为编码后信道的编码后每个信道码元所携带的平均信息量称为编码后信道的信息传信息传 输率输率。（2）若信息量以比特为单位，传送每个码元用）若信息量以比特为单位，传送每个码元用t秒，则秒，则信息传输速率信息传输速率信息传输速率信息传输速率定义为：定义为：（比特（比特/秒）秒）式中：式中：H(X)为信源熵；为信源熵；为编码后的平均码长；为编码后的平均码长；t为传输一个码符号的时间。为传输一个码符号的时间。（1）若信息量以比特为单位，则）若信息量以比特为单位，则信息传输率信息传输率信息传输率信息传输率记为：记为：(比特比特/码元码元)20第20页，本

21、讲稿共49页【例【例【例【例3.1.63.1.6】给定信源给定信源为提高传输效率，使平均码长尽可能短，遵照为提高传输效率，使平均码长尽可能短，遵照概率大取码长短，概率小取码长长的原则对上概率大取码长短，概率小取码长长的原则对上述信源进行二进制不等长编码，得到如右编码述信源进行二进制不等长编码，得到如右编码方案方案，求编码后的信息传输率，求编码后的信息传输率RD。（比特（比特/符号）符号）（码元（码元/符号）符号）(比特比特/码元码元)21第21页，本讲稿共49页3.2 3.2 3.2 3.2 等长码及等长编码定理等长码及等长编码定理等长码及等长编码定理等长码及等长编码定理 一等长编码定理一等长

22、编码定理一等长编码定理一等长编码定理考虑对一简单信源考虑对一简单信源X进行等长编码，信源符号集有进行等长编码，信源符号集有K个符号，码符号集含个符号，码符号集含D个符号，个符号，码字长度记为码字长度记为n。对信源作等长无差错编码，要得到惟一可译码，必须满足下式：。对信源作等长无差错编码，要得到惟一可译码，必须满足下式：K D n对单符号信源对单符号信源X的的L次扩展信源次扩展信源XL进行等长编码，要得到长为进行等长编码，要得到长为n的惟一可译码，必的惟一可译码，必须满足须满足:K L D n对上式两边取对数，得：对上式两边取对数，得：22第22页，本讲稿共49页下面的定理将说明，当满足一定的条

23、件时，在下面的定理将说明，当满足一定的条件时，在L 时，失真时，失真pe 0。【定理】等长编码定理【定理】等长编码定理 ，对信源输出的，对信源输出的L长序列长序列si，i=1,2,KL 进行等进行等长编码，码字是长度为长编码，码字是长度为n的的D进制符号串，当满足条件进制符号串，当满足条件 ，则，则L 时，可使译码差错时，可使译码差错pe(、为无穷小量为无穷小量)；反之，当；反之，当 时，则不可能时，则不可能实现无差错编码。实现无差错编码。设离散无记忆信源设离散无记忆信源X=x1,x2,xk的熵为的熵为H(X)，X的的L维扩展信源为维扩展信源为 23第23页，本讲稿共49页二编码速率（码率）二

24、编码速率（码率）二编码速率（码率）二编码速率（码率）码率码率的定义式为的定义式为 表示编码后，一个信源符号平均携带的最大信息量，也可以理解为传送一表示编码后，一个信源符号平均携带的最大信息量，也可以理解为传送一个信源符号需要的平均信息量。个信源符号需要的平均信息量。如果信源每秒发出如果信源每秒发出1/t个信源符号，那么个信源符号，那么 就表示信源每秒发出的符号需要多少就表示信源每秒发出的符号需要多少bit来表示。由于每一位二进制数所来表示。由于每一位二进制数所能携带的最大信息量是能携带的最大信息量是1bit，码率也称为，码率也称为位速位速。24第24页，本讲稿共49页三编码效率三编码效率三编码

25、效率三编码效率等长编码定理要求等长编码定理要求 ，即，即 ，可看出比值，可看出比值 是一个小于是一个小于1的无量纲纯数，定义它为等长编码的的无量纲纯数，定义它为等长编码的编码效率编码效率编码效率编码效率，记为：，记为：编码效率编码效率是衡量编码质量的一个重要指标，对信源编码时应尽是衡量编码质量的一个重要指标，对信源编码时应尽量提高编码效率。量提高编码效率。25第25页，本讲稿共49页根据前面计算，由等长编码定理计算出的下界更小，但由于码长都取整，故根据前面计算，由等长编码定理计算出的下界更小，但由于码长都取整，故取取n1=n2=2。并做如下编码：。并做如下编码：，得到唯一可译码。，得到唯一可译

26、码。【例【例【例【例3.2.13.2.1】（1）给定离散无记忆信源）给定离散无记忆信源 ，对该信源进行，对该信源进行二进制等长编码，并求编码效率。二进制等长编码，并求编码效率。【解】【解】【解】【解】先确定码长：信源消息数目先确定码长：信源消息数目K3，信源序列长度，信源序列长度L1，码符号数，码符号数D2 根据根据 根据等长编码定理：根据等长编码定理：（比特（比特/符号）符号）26第26页，本讲稿共49页编码效率为：编码效率为：（2）对原信源进行）对原信源进行L=2维扩展，得到新信源：维扩展，得到新信源：对扩展信源进行二进制等长编码。对扩展信源进行二进制等长编码。【解】【解】对扩展码对扩展码

27、K3，信源序列长度，信源序列长度L2，码符号数，码符号数D2 由由 确定码长：确定码长：取取n3=4，对扩展信源编码的编码如下：，对扩展信源编码的编码如下：信源序列信源序列x0 x0 x0 x1x0 x2x1x0 x1x1x1x2x2x0 x2x1x2x2码字码字00000001001000110100010101100111100027第27页，本讲稿共49页编码效率：编码效率：按等长编码定理：按等长编码定理：取取n4=3，对扩展信源编码的编码如下：，对扩展信源编码的编码如下：信源序列信源序列x0 x0 x0 x1x0 x2x1x0 x1x1x1x2x2x0 x2x1x2x2码字码字0000

28、01000010011100101110111对于二进制码，取码长为对于二进制码，取码长为3，共可构成，共可构成8个不同的码字，而扩展信源含个不同的码字，而扩展信源含9个序列，个序列，故编码时对序列中概率小的两个序列赋予同一个码字故编码时对序列中概率小的两个序列赋予同一个码字000，这样势必存在编码差错，这样势必存在编码差错概率概率pe：28第28页，本讲稿共49页3.3 3.3 3.3 3.3 变长码及变长编码定理变长码及变长编码定理变长码及变长编码定理变长码及变长编码定理 一变长码一变长码一变长码一变长码变长码也要求原码的任意变长码也要求原码的任意L次扩展码也是惟一可译的。变长码分为即次扩

29、展码也是惟一可译的。变长码分为即时码和延长码，为保证即时译码，要求变长惟一可译码采用即时码。时码和延长码，为保证即时译码，要求变长惟一可译码采用即时码。对于变长码，要求整个码集的平均码长力求最小，此时编码效率最对于变长码，要求整个码集的平均码长力求最小，此时编码效率最高。对于给定信源，使平均码长达到最小的编码方法，称为高。对于给定信源，使平均码长达到最小的编码方法，称为最佳编码最佳编码，得到的码集称为得到的码集称为最佳码最佳码。29第29页，本讲稿共49页二变长编码定理二变长编码定理二变长编码定理二变长编码定理 平均码长极限定理（离散无记忆信源变长编码定理）：平均码长极限定理（离散无记忆信源变

30、长编码定理）：给定熵为给定熵为H（X）的离散无记忆信源，及有）的离散无记忆信源，及有D个元素的码符号集，则总可个元素的码符号集，则总可找到一种无失真编码方法，构成惟一可译码，其平均码长满足：找到一种无失真编码方法，构成惟一可译码，其平均码长满足：定理的证明过程给了我们一种最佳编码的构造方法，即如果信源的定理的证明过程给了我们一种最佳编码的构造方法，即如果信源的概率分布均有概率分布均有 的形式，那么直接取的形式，那么直接取ni作为对应消息符号的码字长度，就可以得到紧致码（最佳码）作为对应消息符号的码字长度，就可以得到紧致码（最佳码）。30第30页，本讲稿共49页【例【例【例【例3.3.13.3.

31、1】对其进行二元编码，码长分别取对其进行二元编码，码长分别取 1，2，3，3此时的平均码长为此时的平均码长为 （码元（码元/符号）符号）信源熵为信源熵为 （bit/符号）符号）编码效率编码效率信息传输率信息传输率 （bit/码元）码元）31第31页，本讲稿共49页其其L次扩展信源次扩展信源 的熵记为的熵记为 定理：变长编码定理定理：变长编码定理(Shannon第一定理第一定理)给定熵为给定熵为H（X）的离散无记忆信源）的离散无记忆信源 给定有给定有D个元素的码符号集，对扩展信源进行编码，总可以找到一种惟一个元素的码符号集，对扩展信源进行编码，总可以找到一种惟一可译码，使码长可译码，使码长 满足

32、：满足：记记 为信源每个符号所对应的平均码字数，则上式为：为信源每个符号所对应的平均码字数，则上式为：32第32页，本讲稿共49页编码效率编码效率：是一个无量纲的数，一般情况下是一个无量纲的数，一般情况下 2的情况）的情况）（1）将信源发出的）将信源发出的M个消息，按其概率递减顺序进行排列，得个消息，按其概率递减顺序进行排列，得p(x1)p(x2)p(x3)p(xM)（2）将概率最小的）将概率最小的m0个消息组合成一个新消息。选择个消息组合成一个新消息。选择m0的原则是使的原则是使 （N-m0）/(D-1)的比值等于正整数的最小正整数即为的比值等于正整数的最小正整数即为m0（m01）的值。对这

33、）的值。对这m0个个消息分别用消息分别用0，1，2，（，（D-1）进行编码（一般，将概率最大的编码为）进行编码（一般，将概率最大的编码为“D-1”，概率最小的编码为，概率最小的编码为“0”），再对这），再对这m0个消息求概率之和；个消息求概率之和；（3）将上述概率之和作为一新消息的概率，与余下的（）将上述概率之和作为一新消息的概率，与余下的（M-m0）个消息一起组成一新的信）个消息一起组成一新的信源，再按概率递减顺序重新排列，如果概率之和与原信源的某个概率相等，则把概源，再按概率递减顺序重新排列，如果概率之和与原信源的某个概率相等，则把概率之和排在上面，这样可使合并消息重复编码的次数减少，使短

34、码得到充分利用；率之和排在上面，这样可使合并消息重复编码的次数减少，使短码得到充分利用；（4）如此一直进行下去，直到新集合仅包含）如此一直进行下去，直到新集合仅包含D个消息为止；个消息为止；（5）从最后一步骤开始，沿编码逆程取下各步骤得到的码符号，如此构成的码符号序列）从最后一步骤开始，沿编码逆程取下各步骤得到的码符号，如此构成的码符号序列即为对应消息的码字。即为对应消息的码字。47第47页，本讲稿共49页本章讨论在不允许失真前提下对信源的编码，分为两种情况，等长编码和变长编本章讨论在不允许失真前提下对信源的编码，分为两种情况，等长编码和变长编码。等长编码定理和变长编码定理分别给出了这两种情况

35、，在无失真和码长尽可能短码。等长编码定理和变长编码定理分别给出了这两种情况，在无失真和码长尽可能短这两个约束条件下的平均码长的上界和下界。这两个约束条件下的平均码长的上界和下界。一等长编码定理一等长编码定理记记H（X）为单符号信源熵，）为单符号信源熵，L为扩展信源输出序列长度，为扩展信源输出序列长度，n为码字长度，为码字长度，D为码符号集元素个数，当满足条件为码符号集元素个数，当满足条件 则则L 时，可使译码差错时，可使译码差错pe(、为无穷小量为无穷小量)；反之，反之，则不可能实现无差错编码。则不可能实现无差错编码。本本 章章 小小 结结48第48页，本讲稿共49页二变长编码定理二变长编码定

36、理(Shannon第一定理第一定理)记记H（X）为单符号信源熵，）为单符号信源熵，L为扩展信源输出的序列长度，为扩展信源输出的序列长度，为信源每为信源每个符号所对应的平均码字数，个符号所对应的平均码字数，D为码符号集元素个数，则对信源进行编码，为码符号集元素个数，则对信源进行编码，总可以找到一种惟一可译码，使码长满足总可以找到一种惟一可译码，使码长满足 三平均码长三平均码长 四克拉夫特不等式四克拉夫特不等式 本章还介绍了常见的三种变长码的编码方法：本章还介绍了常见的三种变长码的编码方法：香农编码法、香农编码法、香农编码法、香农编码法、FanoFano编码法和霍夫曼编码法和霍夫曼编码法和霍夫曼编码法和霍夫曼编码法编码法编码法编码法。对于同一信源的编码，三种方法中，以霍夫曼编码的编码效率最高。香农编码法没有。对于同一信源的编码，三种方法中，以霍夫曼编码的编码效率最高。香农编码法没有太多实用价值，但它在证明变长编码定理时起了重要作用，太多实用价值，但它在证明变长编码定理时起了重要作用，Fano编码法是遵照变长编码定理编码法是遵照变长编码定理（香农第一定理）的指导思想导出的一种编码方法。（香农第一定理）的指导思想导出的一种编码方法。49第49页，本讲稿共49页