第三章离散信源无失真编码精选文档.ppt

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

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

2、了三三种种通通用用信信源源编编码方法：香农编码法、费诺编码法和霍夫曼编码法。码方法：香农编码法、费诺编码法和霍夫曼编码法。本讲稿第二页，共四十四页本章重点：本章重点：本章重点：本章重点：1.唯一可译码的基本概念；唯一可译码的基本概念；2.Shannon编码、编码、Fano编码、编码、Huffman编码的方法；编码的方法；3.平均码长和编码效率的计算。平均码长和编码效率的计算。本讲稿第三页，共四十四页3.1 绪论绪论为了实现高质量、高效率的通信，引入了信源编码和信道编码。信源编码和信道编码主要需要解决以下两个问题。提高传输效率增强通信的可靠性本讲稿第四页，共四十四页（1）提高传输效率，用尽可能少

3、的信道传输符号来传递信源消息，目的是提高传输效率，这是信源编码主要应考虑的问题。这里又分两种情况讨论，即允许接收信号有一定的失真或不允许失真。综上所述，提高抗干扰能力往往是以牺牲信息传输效率为代价的，而为了提高传输效率又往往削弱了其抗干扰能力。这样，设计者在取舍之间就要作均衡考虑。（2）增强通信的可靠性如何增加信号的抗干扰能力，提高传输的可靠性，这是信道编码主要考虑的问题。解决这一问题，一般是采用冗余编码法，赋予信码自身一定的纠错和检错能力，只要采取适当的信道编码和译码措施，就可使信道传输的差错概率降到允许的范围之内。本讲稿第五页，共四十四页信源编码包括两个功能：（1）将信源符号变换成适合信道

4、传输的符号；（2）压缩信源冗余度，提高传输效率。本讲稿第六页，共四十四页a1,a2,aK为信源符号集，序列中每一个符号uil都取自信源符号集。b1，b2，bD是适合信道传输的D个符号，用作信源编码器的编码符号。编码输出码字ci=ci1ci2cin，cikb1，b2，bDk=1,2,n，n表示码字长度，简称码长码长。信源符号a1,a2,aK信道符号（码符号）b1,b2,bD图3-1信源编码器模型信源信源 信源编码器信源编码器 一般来说，信源编码可归纳为如图3-1所示的模型。消息ui=ui1ui2uiL 码字ci=ci1ci2cin本讲稿第七页，共四十四页信源编码可看成是从信源符号集到码符号集的一

5、种映射，即将信源符号集中的每个元素（可以是单符号，也可以是符号序列）映射成一个长度为n的码字。对于同一个信源，编码方法是多种的。【例例3.3】用u1，u2，u3，u4表示信源的四个消息，码符号集为0,1，表3-1列出了该信源的几种不同编码。表3-1同一信源的几种不同编码信 源消息各消息概率码1码2码3码4u1q(u1)000001u2q(u2)1101110u3q(u3)101000100u4q(u4)11111110003.1.1 码的分类码的分类本讲稿第八页，共四十四页3.变长码变长码若码字集合C中的所有码字cm(m=1,2,M)，其码长不都相同，称码C为变长码，表3-1中列出的码3、码4

6、就是变长码。2.等长码等长码在一组码字集合C中的所有码字cm(m=1,2,M)，其码长都相同，则称这组码C为等长码，表3-1中列出的码1、码2就码长n=2等长码。一般，可以将码简单的分成如下几类：1.二元码二元码若码符号集为0，1，则码字就是二元序列，称为二元码,二元码通过二进制信道传输，这是数字通信和计算机通信中最常见的一种码，表3-1列出的4种码都是二元码。本讲稿第九页，共四十四页5.非奇异码非奇异码从信源消息到码字的映射是一一对应的，每一个不同的信源消息都用不同的码字对其编码，例表3-1中的码2、码3和码4都是非奇异码。4.奇异码奇异码对奇异码来说，从信源消息到码字的映射不是一一对应的。

7、例表3-1中的码1，信源消息u2和u4都用码字11对其编码，因此这种码就是奇异码，奇异码不具备惟一可译性。本讲稿第十页，共四十四页扩展信源信源编码器信源符号a1,a2,aK信道符号（码符号）b1,b2,bD消息u1 uN=(u11u12u1L)(uN1uN2uNL)N次扩展码字c1 cN=(c11c12c1n)(cN1cN2cNn)图3-2N次扩展信源编码器模型原码的N次扩展码是将信源作N次扩展得到的新信源符号序列u（N）=u1 uN =(u11u12u1L)(uN1uN2uNL)，对应码符号序列c（N）=c1 cN=(c11c12c1n)(cN1cN2cNn)，记集合C(N)=c1(N),c

8、2(N),，C(N)即原码C的N次扩展码。6.原码原码C的的N次扩展码次扩展码原码C的N次扩展码中的每个元素是N次扩展信源中的序列所对应的N个码字组成的序列。本讲稿第十一页，共四十四页对于定长码，若原码是惟一可译码，则它的N次扩展码也是惟一可译的，而对于变长码则不尽然，见表3-2。信源消息各消息概率码1码2码3u1q(u1)011u2q(u2)11001u3q(u3)00100001u4q(u4)1110000001表3-2同一信源的几种不同变长编码7.惟一可译码惟一可译码定义定义3.1 如果码的任意如果码的任意N次扩展码都是非奇异码，则称该码为惟一可译次扩展码都是非奇异码，则称该码为惟一可译

9、码。码。本讲稿第十二页，共四十四页8.即时码即时码对于变长码，又有如下定义定义定义3.2 对于码字对于码字c=c1 c2 cn,称称c、=c1 c2 ci(i n)为码字为码字c的字的字头（前缀）。头（前缀）。定义定义3.3若码中任一码字都不是另一码字的字头，称该码为异字头码（无前缀码）。本讲稿第十三页，共四十四页表3-2中码3，收到“1”后就知道一个码字已经完结，无须等待下一个符号抵达，所以无前缀码能够即时译码,称之为即时可译码，简称即时即时码码。而对于码2，收到“1”后，并不能立即做出判决，就是收到“10”也不能立即做出判决，则还要收到下面的码元才能做出判决。所以非异字头码不能即时译码，称

10、为非非即即时时码码，由于非异字头码的其中一些码字是另一些码字的延长，故也称延长码。显然，即时码是惟一可译码，而惟一可译码不一定是即时码。本讲稿第十四页，共四十四页即时码可用树图法来构造。图3-3用树图法编码树根编码深度u1：1u2：01u3：001u4：000110u1u2u3u411100【例例3.4】用树图法表示表3-2中的码3，如图3-3所示（D=2）。本讲稿第十五页，共四十四页码奇异码非奇异码非惟一可译码惟一可译码变长码等长码即时码延长码图3-5码的分类结构图图3-5是码的分类结构图由上面的结构图可看出，将码分为奇异码和非奇异码两大类，我们只讨论非奇异码。非奇异码又分为惟一可译码和非惟

11、一可译码两大类，我们只讨论惟一可译码。本讲稿第十六页，共四十四页3.1.2 平均码长的计算平均码长的计算对于变变长长码码，码集C的平均码长，用符号表示，定义为码C中每个码字cm(m=1,2,，M)其码长的概率加权平均值为(3-1)式中nm是码字cm所对应的码字的长度，p(cm)是码字cm出现的概率。对于等等长长码码，由于码集C中的每个码字的码长都相同，平均码长就等于每个码字的码长本讲稿第十七页，共四十四页N次次扩扩展展码码的平均码长等于扩展码中码字长度的概率加权平均值。对于2次扩展码，有：(3-2)设nm,ns分别是原信源消息um,us所对应的码长,cm,cs是um,us所对应的码字，则式(3

12、-2)中的nm+ns是扩展后新的信源序列nmns所对应的码字cmcs的长度，q(um)q(us)是cmcs出现的概率。本讲稿第十八页，共四十四页3.1.3 信息传输速率信息传输速率 信道的信信息息传传输输速速率率为信道单位时间内所传输的实际信息量。若信息量以比特为单位，时间以秒为单位，则信息传输率定义为：(比特/秒)(3-3)若信息量以比特为单位，时间以码元时间（传输一个码符号的时间）为单位，则信息传输率记为(比特/码元时间)(3-4)为编码后的平均码长；H(X)为信源熵；式中：t为传输一个码符号的时间。本讲稿第十九页，共四十四页【例例3.8】给定信源，为提高传输效率，使平均码长尽可能短，遵照

13、概率大取码长短，概率小取码长长的原则对上述信源进行二进制不等长编码，得到，求编码后的信息传输率RD。（比特/符号）（码元/符号）(比特/码元时间)本讲稿第二十页，共四十四页3.2 等长码及等长编码定理等长码及等长编码定理考虑对一简单信源S进行等长编码，信源符号集有K个符号，码符号集含D个符号，码字长度记为n。要得到惟一可译码，必须满足下式K D n对单符号信源S的L次扩展信源S（L）进行等长编码，要得到码长为n的惟一可译码，必须满足K L D n （3-5）对式（3-5）两边取对数，得（3-6）对于那些出现概率极小的字符序列不予编码，这样可以减小平均码长，当然这样会带来一定的失真。下面的定理3

14、.1将证明，当满足一定的条件时，在L 时，译码错误概率pe0本讲稿第二十一页，共四十四页定定理理3.1等等长长编编码码定定理理 设离散无记忆信源S=x1，x2，xk的熵为H（X），S的L维扩展信源为，对信源输出的L长序列si，i=1,2,kL 进行等长编码，码字是长度为n的D进制符号串，当满足条件，则L 时，可使译码差错pe(、为无穷小量)；反之，当时，则不可能实现无差错编码。编码效率编码效率定理3.1要求，即，可看出比值是一个小于1的无量纲纯数，定义它为等长编码的编码效率，记为（3-7）本讲稿第二十二页，共四十四页3.3 变长码及变长编码定理变长码及变长编码定理 3.3.1 变长码变长码 对

15、等长码的讨论是在L足够大的条件下得到的结论，当L为有限值时，则总会带来一定程度的失真。对于变长码，往往在L不是很大的情况下就可编出高效且无失真的码。变长码也要求原码的任意L次扩展码也是惟一可译的。变长码分为即时码和延长码，为保证即时译码，要求变长惟一可译码采用即时码。对于变长码，要求整个码集的平均码长力求最小，此时编码效率最高。对于给定信源，使平均码长达到最小的编码方法，称为最最佳佳编编码码，得到的码集称为最佳码最佳码。本讲稿第二十三页，共四十四页3.3.2 克拉夫特不等式克拉夫特不等式 定定理理3.2 D进制码字集合C=c1,c2,cM，码集中每一cm（m=1,2,M）都是一个D进制符号串，

16、设c1,c2,cM 对应的码长分别是n1,n2,nM，则存在唯一可译码的充要条件是(3-10)式（3-10）也称克拉夫特不等式克拉夫特不等式定理3.2只是说是存在惟一可译码的充要条件，这里强调的是“存在”，但它并不是唯一可译码的充要条件，换言之，惟一可译码一定满足克拉夫特不等式，反之，满足克拉夫特不等式的码不一定是惟一可译码。本讲稿第二十四页，共四十四页3.3.3 变长编码定理变长编码定理 定定理理3.3 给定熵为H（X）的离散无记忆信源，及有D个元素的码符号集，则总可找到一种无失真编码方法，构成惟一可译码，其平均码长满足：（3-19）定理定理3.4 变长编码定理变长编码定理(Shannon第

17、一定理第一定理)给定熵为H（X）的离散无记忆信源，其L次扩展信源的熵记为H（X），给定有D个元素的码符号集，对扩展信源进行编码，总可以找到一种惟一可译码，使码长满足(3-23)本讲稿第二十五页，共四十四页记为信源每个符号所对应的平均码字数，则式(3-23)为（3-24）Shannon第一定理的物理意义在于：对信源进行编码，使编码后的码集中各码字尽可能等概分布，如果将这码集看成为一个新的信源，这时新信源所含信息量最大。定义编码效率编码效率(3-26)是一个无量纲的数，一般情况下1，在极限情况下=1。本讲稿第二十六页，共四十四页上一讲复习上一讲复习 上一讲我们主要讨论了在不允许失真前提下对信源的编

18、码，分为两种情况，等长编码和变长编码。等长编码定理和变长编码定理分别给出了这两种情况，在无失真和码长尽可能短这两个约束条件下的平均码长的上界和下界。等等长长编编码码定定理理 记H（X）为单符号信源熵，L为扩展信源输出序列 长 度，n为 码 字 长 度，D为 码 符 号 集 元 素 个 数，当 满 足 条 件 ，则L 时，可使译码差错pe(、为无穷小量)；反之，当时，则不可能实现无差错编码。变长编码定理变长编码定理(Shannon第一定理)记H（X）为单符号信源熵，L为扩展信源输出的序列长度，为信源每个符号所对应的平均码字数，D为码符号集元素个数，则对信源进行编码，总可以找到一种惟一可译码，使码

19、长满足本讲稿第二十七页，共四十四页对于同一种信源，三种编码法中以香农编码法的编码效率最低，费诺编码法也不是一种最佳编码法，但用这种方法有时候也能找到紧致码。一般情况下，霍夫曼编码法得到的平均码长最短，即编码效率最高。3.4 变长码的编码方法变长码的编码方法香农（Shannon）编码法费诺(Fano)编码法霍夫曼(Huffman)编码法变长编码法：本讲稿第二十八页，共四十四页3.4.1 香农编码法香农编码法 D进制香农编码法其码长的取值范围:-logDq(xm)nm-logDq(xm)+1（3-30）记离散信源，给定有D个元素的码符号集，对信源进行变长编码，将各消息概率q(xm)(m=1,2,M

20、)写成如下的形式：取码长nm(m=1,2,M)满足：tm nm tm+1（3-28）本讲稿第二十九页，共四十四页香农编码法具体步骤如下:（以D=2为例）（4）计算出第m个消息的累加概率，再将pm变换成二进制小数，取小数点后面nm位作为第m个消息的代码组。（3）根据式（3-31）：-logq(xm)nm2的D进制霍夫曼编码，先根据 D*2，3，D（3-31）和D*=M mod(D-1)（3-32）算出D*，即最长的码字数为D*，第一次取D*个概率合并，以后每次取D个概率合并。本讲稿第四十一页，共四十四页本本 章章 小小 结结 本章讨论在不允许失真前提下对信源的编码，分为两种情况，等长编码和变长编

21、码。等长编码定理和变长编码定理分别给出了这两种情况，在无失真和码长尽可能短这两个约束条件下的平均码长的上界和下界。等等长长编编码码定定理理 记H（X）为单符号信源熵，L为扩展信源输出序列 长 度，n为 码 字 长 度，D为 码 符 号 集 元 素 个 数，当 满 足 条 件 ，则L 时，可使译码差错pe(、为无穷小量)；反之，当时，则不可能实现无差错编码。变长编码定理变长编码定理(Shannon第一定理)记H（X）为单符号信源熵，L为扩展信源输出的序列长度，为信源每个符号所对应的平均码字数，D为码符号集元素个数，则对信源进行编码，总可以找到一种惟一可译码，使码长满足本讲稿第四十二页，共四十四页平均码长平均码长克拉夫特不等式克拉夫特不等式本章还介绍了常见的三种变长码的编码方法：香农编码法、Fano编码法和霍夫曼编码法。对于同一信源的编码，三种方法中，以霍夫曼编码的编码效率最高。香农编码法没有太多实用价值，但它在证明变长编码定理时起了重要作用，Fano编码法是遵照变长编码定理（香农第一定理）的指导思想导出的一种编码方法。本讲稿第四十三页，共四十四页本讲稿第四十四页，共四十四页