信息论与编码纠错第3章.ppt

信息论与编码信息论与编码第三章第三章 离散信源无失真编码离散信源无失真编码 信息论与编码信息论与编码内容提要内容提要用尽可能少的符号来传输信源消息，目的是提高传用尽可能少的符号来传输信源消息，目的是提高传输效率，这是信源编码应考虑的问题，这章讨论在不允输效率，这是信源编码应考虑的问题，这章讨论在不允许失真情况下的信源编码。等长编码定理给出了等长编许失真情况下的信源编码。等长编码定理给出了等长编码条件下，其码长的下限值，变长编码定理（香农第一码条件下，其码长的下限值，变长编码定理（香农第一定理）给出了信源无失真变长编码时其码长的上、下限定理）给出了信源无失真变长编码时其码长的上、下限值。本章还介绍了三种通用信源编码方法：香农编码法、值。本章还介绍了三种通用信源编码方法：香农编码法、费诺编码法和霍夫曼编码法。费诺编码法和霍夫曼编码法。信息论与编码信息论与编码3.1 3.1 3.1 3.1 概概概概 述述述述 一信源编码的模型一信源编码的模型一信源编码的模型一信源编码的模型为了实现高质量、高效率的通信，引入了信源编码和信道编码。信源为了实现高质量、高效率的通信，引入了信源编码和信道编码。信源编码和信道编码主要需要解决以下两个问题。编码和信道编码主要需要解决以下两个问题。（1 1）提高传输效率：提高传输效率：提高传输效率：提高传输效率：用尽可能少的信道传输符号来传递信源消息，目的是提高传输效率，用尽可能少的信道传输符号来传递信源消息，目的是提高传输效率，这是信源编码主要应考虑的问题。这里又分两种情况讨论，即允许接收信号这是信源编码主要应考虑的问题。这里又分两种情况讨论，即允许接收信号有一定的失真或不允许失真。有一定的失真或不允许失真。（2 2）增强通信的可靠性：）增强通信的可靠性：）增强通信的可靠性：）增强通信的可靠性：如何增加信号的抗干扰能力，提高传输的可靠性，这是信道编码主要如何增加信号的抗干扰能力，提高传输的可靠性，这是信道编码主要考虑的问题。解决这一问题，一般是采用冗余编码法，赋予信码自身一定考虑的问题。解决这一问题，一般是采用冗余编码法，赋予信码自身一定的纠错和检错能力，只要采取适当的信道编码和译码措施，就可使信道传的纠错和检错能力，只要采取适当的信道编码和译码措施，就可使信道传输的差错概率降到允许的范围之内。输的差错概率降到允许的范围之内。综上所述，提高抗干扰能力往往是以降低信息传输效率为代价综上所述，提高抗干扰能力往往是以降低信息传输效率为代价 的，而为了提高传输效率又往往削弱了其抗干扰能力。这样，的，而为了提高传输效率又往往削弱了其抗干扰能力。这样，设计者在取舍之间就要作均衡考虑。设计者在取舍之间就要作均衡考虑。信息论与编码信息论与编码信源编码的概念信源编码的概念信源编码的概念信源编码的概念：对信源的原始符号按一定的数学规则进行变换的一种：对信源的原始符号按一定的数学规则进行变换的一种代码。代码。信源编码包括两个功能：信源编码包括两个功能：信源编码包括两个功能：信源编码包括两个功能：（1）将信源符号变换成适合信道传输的符号；）将信源符号变换成适合信道传输的符号；（2）压缩信源冗余度，提高传输效率。）压缩信源冗余度，提高传输效率。信源编码模型：信源编码模型：信源编码模型：信源编码模型：a1,a2,ak为信为信源符号集，序列中源符号集，序列中每一个符号每一个符号uml都取都取自信源符号集。自信源符号集。b1,b2,bD是适是适合信道传输的合信道传输的D个符个符号，用作信源编码号，用作信源编码器的编码符号。器的编码符号。编码输出码字编码输出码字cm=cm1 cm2 cmn，c mkb1,b2,bD，k=1,2,n，n表示码表示码字长度，简称字长度，简称码长码长码长码长。信息论与编码信息论与编码【例】【例】中文电报编码：中文电报编码：信源编码器信源编码器I：110000个汉字分别对应个汉字分别对应00009999 信源编码器信源编码器II：每位数字对应五位二进制等重码。对应关系如下：每位数字对应五位二进制等重码。对应关系如下：（101011，211001，.，910011，001101）如：如：信息论与编码信息论与编码二码的分类二码的分类二码的分类二码的分类信源编码可看成是从信源符号集到码符号集的一种映射，即将信源符信源编码可看成是从信源符号集到码符号集的一种映射，即将信源符号集中的每个元素（可以是单符号，也可以是符号序列）映射成一个长度号集中的每个元素（可以是单符号，也可以是符号序列）映射成一个长度为为n的码字。对于同一个信源，编码方法是多种的。的码字。对于同一个信源，编码方法是多种的。【例】【例】用用u1，u2，u3，u4表示信源的四个消息，码符号集为表示信源的四个消息，码符号集为0,1，下，下表列出了该信源的几种不同编码。表列出了该信源的几种不同编码。信源消息信源消息各消息概率各消息概率码码1码码2码码3码码4u1p(u1)000001u2p(u2)1101110u3p(u3)101000100u4p(u4)1111111000信息论与编码信息论与编码一般，可以将码简单的分成如下几类一般，可以将码简单的分成如下几类:1二元码二元码若码符号集为若码符号集为0，1，则码字就是二元序列，称为二元码，二元码通，则码字就是二元序列，称为二元码，二元码通过二进制信道传输，这是数字通信和计算机通信中最常见的一种码，例子过二进制信道传输，这是数字通信和计算机通信中最常见的一种码，例子列出的列出的4种码都是二元码。种码都是二元码。2等长码等长码在一组码字集合在一组码字集合C中的所有码字中的所有码字cm(m=1,2,M)，其码长都相同，则称这组码，其码长都相同，则称这组码C为等长码，例中的码为等长码，例中的码1、码、码2 就码长就码长n=2等长码。等长码。3变长码变长码 若码字集合若码字集合C中的所有码字中的所有码字cm(m=1,2,M)，其码长不都相同，称码，其码长不都相同，称码C为变长码，例中列出的码为变长码，例中列出的码3、码、码4 就是变长码。就是变长码。信源信源消息消息各消息各消息概率概率码码1 码码2 码码3码码4u1p(u1)000001u2p(u2)1101110u3p(u3)101000100u4p(u4)1111111000信息论与编码信息论与编码4奇异码奇异码 对奇异码来说，从信源消息到码字的映射不是一一对应的。例中的码对奇异码来说，从信源消息到码字的映射不是一一对应的。例中的码1，信源消息，信源消息u2和和u4都用码字都用码字11对其编码，因此这种码就是对其编码，因此这种码就是奇异码奇异码，奇异码，奇异码不具备惟一可译性。不具备惟一可译性。5非奇异码非奇异码从信源消息到码字的映射是一一对从信源消息到码字的映射是一一对应的，每一个不同的信源消息都用不同应的，每一个不同的信源消息都用不同的码字对其编码，例中的码的码字对其编码，例中的码2、码、码3和码和码4都是非奇异码。都是非奇异码。信源信源消息消息各消息各消息概率概率码码1码码2码码3码码4u1p(u1)000001u2p(u2)1101110u3p(u3)101000100u4p(u4)1111111000信息论与编码信息论与编码6原码原码C的的N次扩展码次扩展码原码原码C的的N次扩展码中的每个元素是次扩展码中的每个元素是N次扩展信源中的序列所对应的次扩展信源中的序列所对应的N个码字组成的序列。个码字组成的序列。原码的原码的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)即原码即原码C的的N次扩展码。次扩展码。信息论与编码信息论与编码7唯一可译码唯一可译码 定义定义：如果码的任意：如果码的任意N次扩展码都是非奇异码，则称该码为惟一可译码。次扩展码都是非奇异码，则称该码为惟一可译码。例中的码例中的码1不是唯一可译码。不是唯一可译码。对于定长码，若原码是惟一可译码，则它的对于定长码，若原码是惟一可译码，则它的N次扩展码也是惟一可译次扩展码也是惟一可译的，而对于变长码则不尽然。的，而对于变长码则不尽然。信源消息信源消息各消息概率各消息概率码码1码码2码码3码码4u1p(u1)000001u2p(u2)1101110u3p(u3)101000100u4p(u4)1111111000信息论与编码信息论与编码信源消息信源消息各消息概率各消息概率码码1码码2码码3u1p(u1)011u2p(u2)11001u3p(u3)00100001u4p(u4)1110000001码码1不是唯一可译码，码不是唯一可译码，码2、码、码3是唯一可译码。是唯一可译码。8即时码即时码对于变长码，有两个定义：对于变长码，有两个定义：（1）前缀：前缀：对于码字对于码字C=c1 c2 cn，称，称c=c1 c2 ci(i n)为码字为码字c的的字头（前缀）。字头（前缀）。（2）异字头码：异字头码：若码中任一码字都不是另一码字的字头，称该码为异若码中任一码字都不是另一码字的字头，称该码为异字头码（无前缀码）。字头码（无前缀码）。码码3是无前缀码；其他是无前缀码；其他都不是无前缀码。都不是无前缀码。信息论与编码信息论与编码即时码即时码：例中码：例中码3，收到，收到“1”后就知道一个码字已经完结，无须等待下后就知道一个码字已经完结，无须等待下一个符号抵达，所以无前缀码能够即时译码，称之为一个符号抵达，所以无前缀码能够即时译码，称之为即时可译即时可译码码，简称即时码。，简称即时码。信源消息信源消息各消息概率各消息概率码码1码码2码码3u1p(u1)011u2p(u2)11001u3p(u3)00100001u4p(u4)1110000001而对于码而对于码2，收到，收到“1”后，并不能立即做出判决，就是收到后，并不能立即做出判决，就是收到“10”也不能立即做出判决，则还要收到下面的码元才能做出判决。所以非异也不能立即做出判决，则还要收到下面的码元才能做出判决。所以非异字头码不能即时译码，称为字头码不能即时译码，称为非即时码非即时码，由于非异字头码的其中一些码字，由于非异字头码的其中一些码字是另一些码字的延长，故也称是另一些码字的延长，故也称延长码延长码。即时码是惟一可译码，而惟一可译码不一定是即时码。即时码是惟一可译码，而惟一可译码不一定是即时码。信息论与编码信息论与编码即时码的树图构造即时码的树图构造即时码的树图构造即时码的树图构造方法方法：对于：对于D进制码，从树根出发，可引出进制码，从树根出发，可引出D根树枝，每根树枝分别赋予一根树枝，每根树枝分别赋予一个不同的码符号，树枝的端点为节点，每一个节点又可引出个不同的码符号，树枝的端点为节点，每一个节点又可引出D根分根分枝，又分别赋予这枝，又分别赋予这D根分枝每根一个不同的码符号，如某一节点被根分枝每根一个不同的码符号，如某一节点被定为码字后，就不再引出树枝，该节点称为终节点。码字就是从树定为码字后，就不再引出树枝，该节点称为终节点。码字就是从树根出发，到达终节点所对应的码符号序列。根出发，到达终节点所对应的码符号序列。【例】用树图法表示码（【例】用树图法表示码（1，01，001，0001）。）。信息论与编码信息论与编码码的分类结构图码的分类结构图由上面的结构图可看出，将码分为由上面的结构图可看出，将码分为奇异码奇异码和和非奇异码非奇异码两大类，我们两大类，我们只讨论非奇异码。非奇异码又分为只讨论非奇异码。非奇异码又分为惟一可译码惟一可译码和和非惟一可译码非惟一可译码两大类，两大类，我们只讨论惟一可译码我们只讨论惟一可译码 信息论与编码信息论与编码三平均码长的计算三平均码长的计算三平均码长的计算三平均码长的计算对于变长码，码集对于变长码，码集C的平均码长定义为码的平均码长定义为码C中每个码字中每个码字cm(m=1,2,，M)其码长的概率加权平均值，用符号其码长的概率加权平均值，用符号 表示表示 式中式中nm是码字是码字cm所对应的码字的长度，所对应的码字的长度，p(cm)是码字是码字cm出现的概率。出现的概率。对于等长码，由于码集对于等长码，由于码集C中的每个码字的码长都相同，平均码长就中的每个码字的码长都相同，平均码长就等于每个码字的码长等于每个码字的码长 信息论与编码信息论与编码【例】【例】计算下表各码的平均码长：计算下表各码的平均码长：信源消息信源消息各消息概率各消息概率码码1码码2码码3码码4u10.4000001u20.21101110u30.2101000100u40.21111111000码长码长221.42.2【推广】【推广】N次扩展码的平均码长次扩展码的平均码长 等于扩展码中码字长度的概率加权平均值。等于扩展码中码字长度的概率加权平均值。对于对于2次扩展码，有：次扩展码，有：设设nm，ns分别是原信源消息分别是原信源消息um，us所对应的码长，所对应的码长，cm，cs是是um，us所对所对应的码字，则式中的应的码字，则式中的nm+ns是扩展后新的信源序列是扩展后新的信源序列umus所对应的码字所对应的码字cmcs的的长度，长度，p(um)p(us)是是cmcs出现的概率。出现的概率。信息论与编码信息论与编码四信息传输速率四信息传输速率四信息传输速率四信息传输速率定义定义：信道的信息传输速率为：信道的信息传输速率为信道单位时间内所传输的实际信息量信道单位时间内所传输的实际信息量。（1）若信息量以比特为单位，时间以秒为单位，则信息传输速率定义为：）若信息量以比特为单位，时间以秒为单位，则信息传输速率定义为：（比特（比特/秒）秒）式中：式中：H(X)为信源熵；为信源熵；为编码后的平均码长；为编码后的平均码长；t为传输一个码符号的时间。为传输一个码符号的时间。（2）若信息量以比特为单位，时间以码元时间（传输一个码符号的时间）若信息量以比特为单位，时间以码元时间（传输一个码符号的时间）为单位，则信息传输率记为：为单位，则信息传输率记为：(比特比特/码元时间码元时间)信息论与编码信息论与编码【例】【例】给定信源给定信源为提高传输效率，使平均码长尽可能短，遵照为提高传输效率，使平均码长尽可能短，遵照概率大取码长短，概率小取码长长的原则对上概率大取码长短，概率小取码长长的原则对上述信源进行二进制不等长编码，得到如右编码述信源进行二进制不等长编码，得到如右编码方案方案，求编码后的信息传输率，求编码后的信息传输率RD。（比特（比特/符号）符号）（码元（码元/符号）符号）(比特比特/码元时间码元时间)信息论与编码信息论与编码3.2 3.2 3.2 3.2 等长码及等长编码定理等长码及等长编码定理等长码及等长编码定理等长码及等长编码定理 一等长编码定理一等长编码定理一等长编码定理一等长编码定理考虑对一简单信源考虑对一简单信源S进行等长编码，信源符号集有进行等长编码，信源符号集有K个符号，码符号集个符号，码符号集含含D个符号，码字长度记为个符号，码字长度记为n。对信源作等长无差错编码，要得到惟一可译。对信源作等长无差错编码，要得到惟一可译码，必须满足下式：码，必须满足下式：K D n对单符号信源对单符号信源S的的L次扩展信源次扩展信源S（L）进行等长编码，要得到长为进行等长编码，要得到长为n的惟的惟一可译码，必须满足一可译码，必须满足:K L D n对上式两边取对数，得：对上式两边取对数，得：信息论与编码信息论与编码 ，对信源输出的，对信源输出的L长序列长序列si，i=1,2,KL 进行等进行等长编码，码字是长度为长编码，码字是长度为n的的D进制符号串，当满足条件进制符号串，当满足条件 ，则，则L 时，可使译码差错时，可使译码差错pe(、为无穷小量为无穷小量)；反之，当；反之，当 时，则不可能时，则不可能实现无差错编码。实现无差错编码。对于那些出现概率极小的字符序列不予编码，这样可以减小平均码长，对于那些出现概率极小的字符序列不予编码，这样可以减小平均码长，当然这样会带来一定的失真。当然这样会带来一定的失真。下面的定理将证明，当满足一定的条件时，在下面的定理将证明，当满足一定的条件时，在L 时，失真时，失真pe 0。【定理】等长编码定理【定理】等长编码定理 设离散无记忆信源设离散无记忆信源S=x1,x2,xk的熵为的熵为H(X)，S的的L维扩展信源为维扩展信源为 信息论与编码信息论与编码二编码效率二编码效率二编码效率二编码效率根据等长码的编码定理，我们可以得到一个衡量编码质量的重要指标，根据等长码的编码定理，我们可以得到一个衡量编码质量的重要指标，编码效率。编码效率。等长编码定理要求等长编码定理要求 ，即，即 ，可看出比值，可看出比值 是一个小于是一个小于1的无量纲纯数，定义它为等长编码的的无量纲纯数，定义它为等长编码的编码效率编码效率编码效率编码效率，记为：，记为：编码效率编码效率是衡量编码质量的一个重要指标，对信源编码时应尽量提是衡量编码质量的一个重要指标，对信源编码时应尽量提高编码效率。高编码效率。信息论与编码信息论与编码【例】【例】（1）给定离散无记忆信源）给定离散无记忆信源 ，对该信源进行二进，对该信源进行二进制等长编码，并求编码效率。制等长编码，并求编码效率。【解】【解】先确定码长：信源消息数目先确定码长：信源消息数目K3，信源序列长度，信源序列长度L1，码符号数，码符号数D2 根据根据 根据等长编码定理：根据等长编码定理：（比特（比特/符号）符号）根据前面计算，由等长编码定理计算出的下界更小，但由于码长都根据前面计算，由等长编码定理计算出的下界更小，但由于码长都取整，故取取整，故取n1=n2=2。并做如下编码：。并做如下编码：，得到唯一可译码。，得到唯一可译码。信息论与编码信息论与编码编码效率为：编码效率为：（2）对原信源进行）对原信源进行L=2维扩展，得到新信源：维扩展，得到新信源：对扩展信源进行二进制等长编码。对扩展信源进行二进制等长编码。【解】【解】对扩展码对扩展码K3，信源序列长度，信源序列长度L2，码符号数，码符号数D2 由由 确定码长：确定码长：取取n3=4，对扩展信源编码的编码如下：，对扩展信源编码的编码如下：信源序列信源序列x0 x0 x0 x1x0 x2x1x0 x1x1x1x2x2x0 x2x1x2x2码字码字0000 00010010001101000101011001111000信息论与编码信息论与编码编码效率：编码效率：按等长编码定理：按等长编码定理：取取n4=3，对扩展信源编码的编码如下：，对扩展信源编码的编码如下：信源序列信源序列 x0 x0 x0 x1x0 x2x1x0 x1x1x1x2x2x0 x2x1x2x2码字码字000001000010011100101110111对于二进制码，取码长为对于二进制码，取码长为3，共可构成，共可构成8个不同的码字，而扩展信源含个不同的码字，而扩展信源含9个序列，故编码时对序列中概率小的两个序列赋予同一个码字个序列，故编码时对序列中概率小的两个序列赋予同一个码字000，这样势，这样势必存在译码差错概率必存在译码差错概率pe：信息论与编码信息论与编码3.3 3.3 3.3 3.3 变长码及变长编码定理变长码及变长编码定理变长码及变长编码定理变长码及变长编码定理 一变长码一变长码一变长码一变长码对等长码的讨论是在对等长码的讨论是在L足够大的条件下得到的结论，当足够大的条件下得到的结论，当L为有限值时，为有限值时，则总会带来一定程度的失真。对于变长码，往往在则总会带来一定程度的失真。对于变长码，往往在L不是很大的情况下就不是很大的情况下就可编出高效且无失真的码。可编出高效且无失真的码。变长码也要求原码的任意变长码也要求原码的任意L次扩展码也是惟一可译的。变长码分为即次扩展码也是惟一可译的。变长码分为即时码和延长码，为保证即时译码，要求变长惟一可译码采用即时码。时码和延长码，为保证即时译码，要求变长惟一可译码采用即时码。对于变长码，要求整个码集的平均码长力求最小，此时编码效率最高。对于变长码，要求整个码集的平均码长力求最小，此时编码效率最高。对于给定信源，使平均码长达到最小的编码方法，称为对于给定信源，使平均码长达到最小的编码方法，称为最佳编码最佳编码，得到的，得到的码集称为码集称为最佳码最佳码。信息论与编码信息论与编码二克拉夫特不等式二克拉夫特不等式二克拉夫特不等式二克拉夫特不等式定理：定理：D进制码字集合进制码字集合C=c1，c2，cM，码集中每一，码集中每一cm（m=1,2,M）都是一个）都是一个D进制符号串，设进制符号串，设c1，c2，cM 对应的码对应的码长分别是长分别是n1，n2，nM，则存在唯一可译码的充要条件是，则存在唯一可译码的充要条件是（克拉夫特不等式）克拉夫特不等式）定理只是说是存在惟一可译码的充要条件，这里强调的是定理只是说是存在惟一可译码的充要条件，这里强调的是“存在存在”，但它并不是唯一可译码的充要条件，换言之，惟一可译码一定满足克，但它并不是唯一可译码的充要条件，换言之，惟一可译码一定满足克拉夫特不等式，反之，满足克拉夫特不等式的码不一定是惟一可译码。拉夫特不等式，反之，满足克拉夫特不等式的码不一定是惟一可译码。信息论与编码信息论与编码三变长编码定理三变长编码定理三变长编码定理三变长编码定理 定理定理：给定熵为：给定熵为H（X）的离散无记忆信源，及有）的离散无记忆信源，及有D个元素的码符号集，则总个元素的码符号集，则总可找到一种无失真编码方法，构成惟一可译码，其平均码长满足：可找到一种无失真编码方法，构成惟一可译码，其平均码长满足：其其L次扩展信源次扩展信源 的熵记为的熵记为 定理：变长编码定理定理：变长编码定理(Shannon第一定理第一定理)给定熵为给定熵为H（X）的离散无记忆信源）的离散无记忆信源 信息论与编码信息论与编码给定有给定有D个元素的码符号集，对扩展信源进行编码，总可以找到一种惟一个元素的码符号集，对扩展信源进行编码，总可以找到一种惟一可译码，使码长可译码，使码长 满足：满足：记记 为信源每个符号所对应的平均码字数，则上式为：为信源每个符号所对应的平均码字数，则上式为：Shannon第一定理的物理意义在于：对信源进行编码，使编码后的码第一定理的物理意义在于：对信源进行编码，使编码后的码集中各码元符号尽可能等概分布，如果将这码集看成为一个新的信源，集中各码元符号尽可能等概分布，如果将这码集看成为一个新的信源，这时新信源的每个码符号平均所含信息量达到最大。这时新信源的每个码符号平均所含信息量达到最大。信息论与编码信息论与编码编码效率：编码效率：是一个无量纲的数，一般情况下是一个无量纲的数，一般情况下1，在极限情况下，在极限情况下=1。信息论与编码信息论与编码3.4 3.4 3.4 3.4 变长码的编码方法变长码的编码方法变长码的编码方法变长码的编码方法 常用的变长编码法：常用的变长编码法：香农（香农（Shannon）编码法）编码法 费诺费诺(Fano)编码法编码法 霍夫曼霍夫曼(Huffman)编码法编码法 对于同一种信源，三种编码法中以香农编码法的编码效率最低，费诺对于同一种信源，三种编码法中以香农编码法的编码效率最低，费诺编码法也不是一种最佳编码法，但用这种方法有时候也能找到编码法也不是一种最佳编码法，但用这种方法有时候也能找到紧致码紧致码紧致码紧致码（在（在所有的唯一可译码中，平均码长最小的码称紧致码，也就是最佳码）。所有的唯一可译码中，平均码长最小的码称紧致码，也就是最佳码）。一般情况下，霍夫曼编码法得到的平均码长最短，即编码效率最高。一般情况下，霍夫曼编码法得到的平均码长最短，即编码效率最高。信息论与编码信息论与编码一一一一.香农编码法香农编码法香农编码法香农编码法 记离散信源记离散信源 给定有给定有D个元素的码符号集，对信源进行变长编码，将各消息概率个元素的码符号集，对信源进行变长编码，将各消息概率p(xm)(m=1,2,M)写成如下的形式：写成如下的形式：取码长取码长nm(m=1,2,M)满足：满足：由此得香农编码法码长取值范围由此得香农编码法码长取值范围:对于二进制香农编码法，有对于二进制香农编码法，有 信息论与编码信息论与编码编码步骤：编码步骤：（1）将信源发出的）将信源发出的M个消息，按其概率递减顺序进行排列；个消息，按其概率递减顺序进行排列；（2）计算出各消息的）计算出各消息的log p(xm)值，值，m=1,2,M；（3）根据式：）根据式：计算出每个消息的二进制代码的计算出每个消息的二进制代码的长度长度nm。（log p(xm)为整数时取等号）为整数时取等号）（4）计算出第）计算出第m个消息的累加概率个消息的累加概率 ，再将，再将pi变换成二进制变换成二进制小数，取小数点后面小数，取小数点后面nm位作为第位作为第m个消息的代码组。个消息的代码组。信息论与编码信息论与编码【例】【例】对给定信源进行对给定信源进行D=2进制香农编码并求编码效率。进制香农编码并求编码效率。【解】【解】（1）编码）编码消息符号消息符号xi消息概率消息概率p(xm)log p(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.991111110信息论与编码信息论与编码（2）求编码效率）求编码效率信源熵：信源熵：比特比特/符号符号 平均码长：平均码长：码元码元/符号符号 编码效率：编码效率：消息符号消息符号xi消息概率消息概率p(xm)log p(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.991111110信息论与编码信息论与编码二费诺编码法二费诺编码法二费诺编码法二费诺编码法费诺编码法的具体步骤如下：费诺编码法的具体步骤如下：（1）信源发出的）信源发出的M个消息，按其概率递减顺序进行排列，把消息集个消息，按其概率递减顺序进行排列，把消息集 x1,x2,x3,xM 按其概率大小分解成两个子集，使两个子集的概按其概率大小分解成两个子集，使两个子集的概率之和尽可能接近相等，把第一个子集编码为率之和尽可能接近相等，把第一个子集编码为“0”，第二个子集，第二个子集编码为编码为“1”，作为代码组的第一个码元；，作为代码组的第一个码元；（2）对子集做第二次分解，同样分解成两个子集，并使两个子集的概）对子集做第二次分解，同样分解成两个子集，并使两个子集的概率尽可能接近相等，再把第一个子集编码为率尽可能接近相等，再把第一个子集编码为“0”，第二个子集编，第二个子集编码为码为“1”，作为代码组的第二个码元；，作为代码组的第二个码元；（3）如此一直进行下去，直到各子集仅含一个消息为止；）如此一直进行下去，直到各子集仅含一个消息为止；（4）将逐次分解过程当中得到的码元排列起来就是各消息的代码。）将逐次分解过程当中得到的码元排列起来就是各消息的代码。信息论与编码信息论与编码【例】【例】对给定信源进行对给定信源进行D=2进制费诺编码并求编码效率。进制费诺编码并求编码效率。xmp(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）1103x60.100.11（1）0.10（0）11104x70.010.01（1）11114信源熵：信源熵：比特比特/符号符号 平均码长：平均码长：码元码元/符号符号 编码效率：编码效率：信息论与编码信息论与编码霍夫曼编码法的具体步骤如下：（先考虑霍夫曼编码法的具体步骤如下：（先考虑D=2的情况）的情况）（1）将信源发出的）将信源发出的M个消息，按其概率递减顺序进行排列，得个消息，按其概率递减顺序进行排列，得p(x1)p(x2)p(x3)p(xM)（2）将概率最小的二个消息分别编码为）将概率最小的二个消息分别编码为“1”和和“0”，（一般，将概率大，（一般，将概率大的编码为的编码为“1”，概率小的编码为，概率小的编码为“0”），再对这两个消息求概率之），再对这两个消息求概率之和；和；（3）将上述概率之和作为一新消息的概率，与余下的消息一起组成一新的）将上述概率之和作为一新消息的概率，与余下的消息一起组成一新的信源，再按概率递减顺序重新排列，如果概率之和与原信源的某个概信源，再按概率递减顺序重新排列，如果概率之和与原信源的某个概率相等，则把概率之和排在上面，这样可使合并消息重复编码的次数率相等，则把概率之和排在上面，这样可使合并消息重复编码的次数减少，使短码得到充分利用；减少，使短码得到充分利用；（4）如此一直进行下去，直到两个合并消息的概率之和为）如此一直进行下去，直到两个合并消息的概率之和为1；（5）从最后一步骤开始，沿编码逆程取下各步骤得到的码符号，如此构成）从最后一步骤开始，沿编码逆程取下各步骤得到的码符号，如此构成的码符号序列即为对应消息的码字。的码符号序列即为对应消息的码字。三霍夫曼编码法三霍夫曼编码法三霍夫曼编码法三霍夫曼编码法 设信源消息数设信源消息数M2，记概率分布为，记概率分布为 信息论与编码信息论与编码【例】【例】对给定信源进行对给定信源进行D=2进制霍夫曼编码并求编码效率。进制霍夫曼编码并求编码效率。信息论与编码信息论与编码信源熵：信源熵：比特比特/符号符号 平均码长：平均码长：码元码元/符号符号 编码效率：编码效率：信息论与编码信息论与编码本本本本 章章章章 小小小小 结结结结 本章讨论在不允许失真前提下对信源的编码，分为两种情况，等长编码本章讨论在不允许失真前提下对信源的编码，分为两种情况，等长编码和变长编码。等长编码定理和变长编码定理分别给出了这两种情况，在无失和变长编码。等长编码定理和变长编码定理分别给出了这两种情况，在无失真和码长尽可能短这两个约束条件下的平均码长的上界和下界。真和码长尽可能短这两个约束条件下的平均码长的上界和下界。一等长编码定理一等长编码定理记记H（X）为单符号信源熵，）为单符号信源熵，L为扩展信源输出序列长度，为扩展信源输出序列长度，n为码字长度，为码字长度，D为码符号集元素个数，当满足条件为码符号集元素个数，当满足条件 则则L 时，可使译码差错时，可使译码差错pe(、为无穷小量为无穷小量)；反之，反之，则不可能实现无差错编码。则不可能实现无差错编码。信息论与编码信息论与编码二变长编码定理二变长编码定理(Shannon第一定理第一定理)记记H（X）为单符号信源熵，）为单符号信源熵，L为扩展信源输出的序列长度，为扩展信源输出的序列长度，为信源每为信源每个符号所对应的平均码字数，个符号所对应的平均码字数，D为码符号集元素个数，则对信源进行编码，为码符号集元素个数，则对信源进行编码，总可以找到一种惟一可译码，使码长满足总可以找到一种惟一可译码，使码长满足 三平均码长三平均码长 四克拉夫特不等式四克拉夫特不等式 本章还介绍了常见的三种变长码的编码方法：本章还介绍了常见的三种变长码的编码方法：香农编码法、香农编码法、香农编码法、香农编码法、FanoFano编码法编码法编码法编码法和霍夫曼编码法和霍夫曼编码法和霍夫曼编码法和霍夫曼编码法。对于同一信源的编码，三种方法中，以霍夫曼编码的编码。对于同一信源的编码，三种方法中，以霍夫曼编码的编码效率最高。香农编码法没有太多实用价值，但它在证明变长编码定理时起了效率最高。香农编码法没有太多实用价值，但它在证明变长编码定理时起了重要作用，重要作用，Fano编码法是遵照变长编码定理（香农第一定理）的指导思想导编码法是遵照变长编码定理（香农第一定理）的指导思想导出的一种编码方法。出的一种编码方法。