第3章无失真信源编码--廖-2013-本科生

1、 第第3章章离散信源无失真编码第第3章章 离散信源无失真编码离散信源无失真编码内容提要用尽可能少的符号来传输信源消息，目的是提高传输效率，这是信源编码应考虑的问题，这章讨论在不允许失真情况下的信源编码。等长编码定理给出了等长编码条件下，其码长的下限值，变长编码定理（香农第一定理）给出了信源无失真变长编码时其码长的上、下限值。本章还介绍了三种通用信源编码方法：香农编码法、Fano编码法和霍夫曼编码法。z离散信源：消息集X为离散集合。即时间和幅度取值都离散的信源。31概述 为了实现高质量、高效率的通信，引入了信源编码和信道编码。信源编码和信道编码主要需要解决以下两个问题。提高传输效率增强通信的可靠

2、性信息论的研究对象信息论的研究对象-通信系统模型，信源，通信系统模型，信源，编码器，编码器，信道，信道，译码器，信宿。译码器，信宿。（1）提高传输效率，用尽可能少的信道传输符号来传递信源消息，目的是提高传输效率，这是信源编码主要应考虑的问题。这里又分两种情况讨论，即允许接收信号有一定的失真或不允许失真。 综上所述，提高抗干扰能力往往是以降低信息传输效率为代价的，而为了提高传输效率又往往削弱了其抗干扰能力。这样，设计者在取舍之间就要作均衡考虑。（2）增强通信的可靠性如何增加信号的抗干扰能力，提高传输的可靠性，这是信道编码主要考虑的问题。解决这一问题，一般是采用冗余编码法，赋予信码自身一定的纠错和

3、检错能力，只要采取适当的信道编码和译码措施，就可使信道传输的差错概率降到允许的范围之内。信源编码包括两个功能： （1）将信源符号变换成适合信道传输的符号； （2）压缩信源冗余度，提高传输效率。7由于信源符号之间存在分布由于信源符号之间存在分布不均匀和相关性不均匀和相关性，使得信源存在使得信源存在冗余度冗余度，信源编码的主要任务，信源编码的主要任务就是减少冗余，提高编码效率。就是减少冗余，提高编码效率。 8信源编码的基本途径有两个：信源编码的基本途径有两个：z使序列中的各个符号尽可能地互相独立，使序列中的各个符号尽可能地互相独立，即解除相关性；即解除相关性；z使编码中各个符号出现的概率尽可能地相

4、使编码中各个符号出现的概率尽可能地相等，即概率均匀化。等，即概率均匀化。 9信源编码的基础是信息论中的两个编码定理：信源编码的基础是信息论中的两个编码定理：z无失真编码定理无失真编码定理-香农第一定律，给出了香农第一定律，给出了信源无失真变长编码时其码长的上、下限值。信源无失真变长编码时其码长的上、下限值。z限失真编码定理限失真编码定理 无失真编码无失真编码只适用于离散信源只适用于离散信源 对于连续信源，只能在失真受限制的情况下进行对于连续信源，只能在失真受限制的情况下进行限失真编码限失真编码 无失真信源编码：无失真信源编码：能够精确地复现信源的输出，保证信源产生的全部信息无损地送给信宿，这时

5、的信源编码就是无失真信源编码。3.1.1信源编码的相关概念编码器3.1图3.1信源编码器3.1书上例子：3.1,3.2z 信源编码有以下3种主要方法：z (1)匹配编码匹配编码根据信源符号的概率不同，编码的码长不同：概率大的信源符号，所编的代码短；概率小的信源符号所编的代码长，这样使平均码长最短。将要讲述的香农编码、哈夫曼编码、费诺码都是概率匹配编码，都是无失真信源编码。z (2)变换编码变换编码 先对信号进行变换，从一种信号空间变换为另一种信号空间，然后针对变换后的信号进行编码。z (3)识别编码识别编码识别编码主要用于印刷或打字机等有标准形状的文字符号和数据的编码，比如中文文字和语音的识别

6、。z 后两种信源编码均为有失真的信源编码。z 无失真信源编码主要针对离散信源，连续信源在量化编码的过程中必然会有量化失真，所以对连续信源只能近似地再现信源的消息。 信源编码可看成是从信源符号集到码符号集的一种映射，即将信源符号集中的每个元素（可以是单符号，也可以是符号序列）映射成一个长度为n的码字。对于同一个信源，编码方法是多种的。【例例3.3】 用u1 ，u2 ，u3，u4表示信源的四个消息，码符号集为0,1，表3-1列出了该信源的几种不同编码。表3-1同一信源的几种不同编码信源消息各消息概率码1码2码3码4u1q(u1)000001u2q(u2)1101110u3q(u3)10100010

7、0u4q(u4)11111110003.1.2码的分类3.变长码变长码若码字集合C中的所有码字cm (m =1,2,M)，其码长不都相同，码码中的码字长短不一中的码字长短不一，称码C为变长码，表3-1中列出的码3、码4就是变长码。2.等长码等长码在一组码字集合C中的所有码字cm (m =1,2,M)，其码长都相同，码中所有码字的长度，都相同，码中所有码字的长度，都相同，则称这组码C为等长码，表3-1中列出的码1、码2就码长n=2等长码。一般，可以将码简单的分成如下几类：1.二元码二元码若码符号集为0，1，则码字就是二元序列，称为二元码,二元码通过二进制信道传输，这是数字通信和计算机通信中最常见

8、的一种码，表3-1列出的4种码都是二元码。5.非奇异码非奇异码从信源消息到码字的影射是一一对应的，每一个不同的信源消息都用不同的码字对其编码，若一组码中所有码字都不相同，则称为非奇异码。例表3-1中的码2、码3和码4都是非奇异码。4.奇异码奇异码对奇异码来说，从信源消息到码字的影射不是一一对应的。若一组码中有相同的码字，则称为奇异码。例表3-1中的码1，信源消息u2和u4都用码字11对其编码，因此这种码就是奇异码，奇异码不具备惟一可译性。扩展信源信源编码器 信源符号 a1,a2,aK 信道符号（码符号）b1, b2,bD消息u1 uN =(u11u12 u1L) (uN1uN2 uNL)N次扩

9、展码字 c1 cN =(c11c12 c1n) (cN1cN2 cNn)图3-2 N次扩展信源编码器模型原码的N次扩展码是将信源作N次扩展得到的新信源符号序列u（N）=u1 uN =(u11u12 u1L) (uN1uN2 uNL)，对应码符号序列c（N）=c1 cN =(c11c12 c1n) (cN1cN2 cNn)，记集合C (N)=c1(N),c2(N),，C (N)即原码C的N次扩展码。6.原码原码C的的N次扩展码次扩展码原码C的N次扩展码中的每个元素是N次扩展信源中的序列所对应的N个码字组成的序列。草稿对于定长码，若原码是惟一可译码，则它的N次扩展码也是惟一可译的，而对于变长码则不

10、尽然，见表3-2。信源消息各消息概率码1码2码3u1q(u1)011u2q(u2)11001u3q(u3)00100001u4q(u4)1110000001表3-2同一信源的几种不同变长编码表3-2同一信源的几种不同变长编码7.惟一可译码惟一可译码定义定义3.1 如果码的任意如果码的任意N次扩展码都是非奇异码，则称该码为次扩展码都是非奇异码，则称该码为惟一可译码。惟一可译码。NYYz对于码1，由于它的每一个信源符号对应不同的码字，所以它本身是唯一可译，但将它进行二次扩展后得到的二次扩展码就不唯一可译，例如，二次扩展码中的u1u3和u3u1对应同一个码字000，u2u4和u4u2对应同一个码字1

11、11，因此码1不是唯一可译码。z对于码2，码3不仅本身是唯一可译码，进行N次扩展后得到的N次扩展码也是唯一可译的，按照定义3.1，码2、码3是唯一可译码。第三章：离散信源无失真编码z编码器码的分类z1.二元码：若码符号集为0，1，则码字就是二元序列，称为二元码；z2.等长码：码中所有码字的长度，都相同；z3.变长码：码中的码字长短不一；z4.奇异码：若一组码中有相同的码字，则称为奇异码；z5.非奇异码：若一组码中所有码字都不相同。z6.原码C的N次扩展码z7.惟一可译码：如果码的任意N次扩展码都是非奇异码，则称该码为惟一可译码。8.即时码即时码对于变长码，又有如下定义定义定义3.2 对于码字对

12、于码字c = c1 c2 cn, ,称称c、 = c1 c2 ci ( (i n) )为码字为码字c的字头（前缀）的字头（前缀）。定义定义3.3 若码中任一码字都不是另一码字的字头，称该码为异字头码（无前缀码）。码3是无前缀码，码1和2都不是无前缀码表3-2中码3，收到“1”后就知道一个码字已经完结，无须等待下一个符号抵达，所以无前缀码能够即时译码, 称之为即时可译码，简称即时码即时码。 而对于码2，收到“1”后，并不能立即做出判决，就是收到“10”也不能立即做出判决，则还要收到下面的码元才能做出判决。所以非异字头码不能即时译码，称为非即时非即时码码，由于非异字头码的其中一些码字是另一些码字的

13、延长，故也称延长码。显然，即时码是惟一可译码，而惟一可译码不一定是即时码。因为有些非即时码(延长码)具有唯一可译性，但不满足前缀条件，不能即时译码即时码可用树图法来构造。对给定码字的全体集合来说，可以用码树来描述它，例子下面。所谓树，既有根，枝，又有节点。树中最顶部的节点称为根节点根节点，从根出发向下伸出树枝，树枝的数目等于码符号的总数r。没有子节点的节点称为叶叶子节点子节点。所有根节点的子节点称为一阶节点一阶节点，所有一阶节点的子节点称为二阶二阶节点节点，依此类推。n阶节点最多有个。节点的阶次又称为节点的深度深度。当某一节点被安排为码字后，它就不再继续伸枝，此节点称为终端节点，用粗黑点表示。

14、图3-3 用树图法编码树根编码深度u1：1u2：01u3：001u4：000110u1u2u3u411100【例例3.4】 用树图法表示表3-2中的码3，如图3-3所示（D =2）。复习上次课的内容：编码器码的分类复习上次课的内容：码的分类z 1.二元码：若码符号集为0，1，则码字就是二元序列，称为二元码；z 2.等长码：码中所有码字的长度，都相同；z 3.变长码：码中的码字长短不一；z 4.奇异码：若一组码中有相同的码字，则称为奇异码；z 5.非奇异码：若一组码中所有码字都不相同。z 6.原码C的N次扩展码z 7.惟一可译码：如果码的任意N次扩展码都是非奇异码，则称该码为惟一可译码。z 8.

15、即时码即时码:无需考虑后续的码符号就可以从码符号序列中译出码字，这样的唯一可译码称为即时码即时码。8.即时码即时码对于变长码，又有如下定义定义定义3.2 对于码字对于码字c = c1 c2 cn, ,称称c、 = c1 c2 ci ( (i n) )为码字为码字c的字头（前缀）的字头（前缀）。定义定义3.3 若码中任一码字都不是另一码字的字头，称该码为异字头码（无前缀码）。码3是无前缀码，码1和2都不是无前缀码表3-2中码3，收到“1”后就知道一个码字已经完结，无须等待下一个符号抵达，所以无前缀码能够即时译码, 称之为即时可译码，简称即时码即时码。 而对于码2，收到“1”后，并不能立即做出判决

16、，就是收到“10”也不能立即做出判决，则还要收到下面的码元才能做出判决。所以非异字头码不能即时译码，称为非即时非即时码码，由于非异字头码的其中一些码字是另一些码字的延长，故也称延长码。显然，即时码是惟一可译码，而惟一可译码不一定是即时码。因为有些非即时码(延长码)具有唯一可译性，但不满足前缀条件，不能即时译码即时码可用树图法来构造。对给定码字的全体集合来说，可以用码树来描述它，例子下面。所谓树，既有根，枝，又有节点。树中最顶部的节点称为根节点根节点，从根出发向下伸出树枝，树枝的数目等于码符号的总数r。没有子节点的节点称为叶叶子节点子节点。所有根节点的子节点称为一阶节点一阶节点，所有一阶节点的子

17、节点称为二阶二阶节点节点，依此类推。n阶节点最多有个。节点的阶次又称为节点的深度深度。当某一节点被安排为码字后，它就不再继续伸枝，此节点称为终端节点，用粗黑点表示。图3-3 用树图法编码树根编码深度u1：1u2：01u3：001u4：000110u1u2u3u411100【例例3.4】 用树图法表示表3-2中的码3，如图3-3所示（D =2）。即时码的树图构造法我们可以用树图的形式构造即时码，如01001111010010001码4的树图10110000101001000码3的树图树根码字的起点树枝数码的数节点数码字的一部分节数码长端点码字满树等长码非满树变长码书上例子3.59同价码同价码 同

18、价码：同价码：每个码符号所占的传输时间都相同的码。对同价码来说，等长码中每个码字的传输时间相同。而变长码中的每个码字的传输时间不一定相同。电报中常用的莫尔斯码是非同价码，其码符号点（）和划（-）所占的传输时间不相同。最早的摩尔斯电码是一些表示数字的点和划。数字对应单词，需要查找一本代码表才能知道每个词对应的数。用一个电键可以敲击出点、划以及中间的停顿。虽然摩尔斯发明了电报，但他缺乏相关的专门技术。他与艾尔菲德维尔签定了一个协议，让他帮自己制造更加实用的设备。艾尔菲德维尔构思了一个方案，通过点、划和中间的停顿，可以让每个字元和标点符号彼此独立地发送出去。他们达成一致，同意把这种标识不同符号的方案

19、放到摩尔斯的专利中。这就是现在我们所熟知的美式摩尔斯电码。10.z分组码和非分组码分组码和非分组码z 定义定义 将信源符号集中的每个信源符号 固定地映射成一个码字 Wi，这样的码称为分组码。分组码。z 用分组码对信源符号进行编码时，为了使接收端能够迅速准确地将码译出，分组码必须具有一些直观属性。与分组码对应的是非分组码非分组码，又称为树码树码、树码编码器输出的码符号通常与编码器的所有信源符号都有关。si图3-5 码的分类结构图图3-5是码的分类结构图由上面的结构图可看出，我们只讨论非奇异码。非奇异码又分为惟一可译码和非惟一可译码两大类，我们只讨论惟一可译码。3.1.3 平均码长的计算平均码长的

20、计算对于变长码变长码，码集C的平均码长，用符号 表示，定义为码C中每个码字cm( m = 1,2,，M)其码长的概率加权平均值为 (3-1)式中nm是码字cm所对应的码字的长度，p (cm )是码字cm出现的概率。 1()Mmmmnnpc cn对于等长码等长码，由于码集C中的每个码字的码长都相同，平均码长就等于每个码字的码长npnpnnmmmmm11)()(c cc c书上例子P54页，计算平均码长n1,n2,n3,n4N次次扩展码扩展码的平均码长等于扩展码中码字长度的概率加权平均值。对于2次扩展码，有：(3-2)设nm,ns分别是原信源消息um,us所对应的码长,cm,cs是um,us所对应

21、的码字，则式(3-2)中的nm + ns是扩展后新的信源序列nmns所对应的码字cmcs的长度，q(um) q(us)是cmcs出现的概率。n smmssmuquqnnn书上的例子3.63.1.4 信息传输速率信息传输速率 信道的信息传输速率信息传输速率为信道单位时间内所传输的实际信息量。若信息量以比特为单位，时间以秒为单位，则信息传输率定义为： (比特/秒) (3-3)nXtHtR若信息量以比特为单位，时间以码元时间（传输一个码符号的时间）为单位，则信息传输率记为 (比特/码元时间) (3-4)nXHRDn为编码后的平均码长；H(X)为信源熵；式中：t为传输一个码符号的时间。可以看出，越小，

22、则越大，信息传输率就越高，因此我们感兴趣的码是使平均码长最短的码。书上例子。3.7【例例3.8】 给定信源 ，为提高传输效率，使平均码长尽可能短，遵照概率大取码长短，概率小取码长长的原则对上述信源进行二进制不等长编码，得到 ，求编码后的信息传输率RD 。16116116116181814141)(76543210 xxxxxxxxXqX1111:101:1110:110:1001:01:1000:00:73625140 xxxxxxxx解：根据定义如果码的任意如果码的任意N次扩展码都是非奇异码，则称该码为次扩展码都是非奇异码，则称该码为惟一可译码。惟一可译码。(非奇异码为码中所有码字都不相同非

23、奇异码为码中所有码字都不相同)DS2S3:10110,S5S1:10110FS1S4:0110S6S1:0110信源S共有q=4个信源符号，s1,s2,s3,s4,现进行二元等长编码，其中码符号个数r=2，则根据5.1式可知，存在唯一可译等长码的条件是码长l必须不小于2如果N=1，则，则与前面的5.1式一样。l/N是平均每个信源符号所需要的码符号个数，表明对于等长唯一可译码，每个信源符号至少需要用个码符号来变换,也就是说，每个信源符号所需最短的码长为个。loglogqlrz当r=2（二元码）时，logr=1.则式5.2成为z这结果表明，对于二元等长唯一可译码，每个信源符号至少需要用 logq个

24、二元符号来变换，也表明对信源进行二元等长不失真编码时，每个信源符号所需码长的极限值为logq个。loglqN定理定理3.1 等长编码定理等长编码定理 设离散无记忆信源S =x1 ，x2 ，xk的熵为H（X），S的L维扩展信源为 ，对信源输出的L长序列si ，i=1,2,KL 进行等长编码，码字是长度为n的D进制符号串，当满足条件 ，则L 时，可使译码差错pe n2，实际上由于要求码长取整数，故只能取n1=n2=5。75. 42log27log1loglog1DKLn03. 42log03. 41log)(2DXHLnLnn为码长-lK信源的符号个数-qD码符号个数-rn为码长-lL为信源序列长

25、度-N编码效率编码效率定理3.1要求 ，即 ，可看出比值 是一个小于1的无量纲纯数，定义它为等长编码的编码效率，记为 （3-7） DXHLnlogDnXHLlog)(1DnXLHlog)(DnXLHlog)(定理3.1要求，是为了实现无差错编码每个信源符号所需要的最少码符号数，这是等长码编码时的理论极限。事实上这种几乎无失真的代价是要求信源序列长L , L 大就意味着实现的复杂性及译码的时延加大。n为码长-lL为信源序列长度-ND码符号个数-rz例子3.9zP583.3 3.3 变长码及变长编码定理变长码及变长编码定理 3.3.1 变长码变长码 对变长码的讨论是在L足够大的条件下得到的结论，当

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

27、，则存在唯一可译码的充要条件是 (3-10)MmnmD11式（3-10）也称克拉夫特不等式克拉夫特不等式 定理3.2只是说是存在惟一可译码的充要条件，这里强调的是“存在”，但它并不是唯一可译码的充要条件，换言之，惟一可译码一定满足克拉夫特不等式，反之，满足克拉夫特不等式的码不一定是惟一可译码。575.1 5.1 编码的定义编码的定义例例：设二进制码树中设二进制码树中X (a1， a2 ， a3 ， a4 )，l11，l22，l32，l43，应用上述判断，应用上述判断定理：定理：41223192222218ili因此不存在满足这种因此不存在满足这种li的唯一可译码的唯一可译码。585.1 5.1

28、 编码的定义编码的定义a1=1010101a2=01a3=001a4=0001，01，001，000 惟一可译码；惟一可译码；1，01，101，000 不是惟一可译码；不是惟一可译码；均满足克劳夫特不等式均满足克劳夫特不等式122222332141iKi595.1 5.1 编码的定义编码的定义克劳夫特不等式克劳夫特不等式只是用来说明唯一可译码是只是用来说明唯一可译码是否否存存在，并不能作为唯一可译码的判据。在，并不能作为唯一可译码的判据。 3.3.3 变长编码定理变长编码定理 定理定理3.3 给定熵为H（X）的离散无记忆信源，及有D个元素的码符号集，则总可找到一种无失真编码方法，构成惟一可译码

29、，其平均码长 满足： （3-19）n DXHnDXHlog1log证明：(1)先证下界，即证。 DXHnlog 0logDnXH设离散无记忆信源含M个消息，信源熵为H（X），其统计模型为)()()()(2121MMxqxqxqxxxXqX DnXHlogMmMmmmmmnxqDxqxq11)(log)(1log)(MmMmnmmmmDxqxqxq11log)()(1log)(MmmnmxqDxqm1)(log)(MmmnmxqDxqm1)()(logMmnmD1log则：（利用克拉夫特不等式）log101)(mnxqDm mmnnmDDxq1 0log DnXH当即时，上式中等号成立，有下界D

30、XHnlog这时得到的码就是紧致码，意味着信源消息概率分布q(xm)必须有(hm为整数)的形式，直接取各消息码字的码长nm等于q(xm)所对应的指数hm即可。这就是例3.8所例举的情况，在例3.8中，信源分布可以表示为44443322765432102121212121212121)(xxxxxxxxXqX取信源各消息相应的码字的码长等于其分布概率所对应的指数，即n0=2n1=2n2=3n3=3n4=4n5=4n6=4n7=4得到的信源编码就是紧致码（最佳码）。mhD 1DXHnlogn DXHlog1n DXHnlog1定理3.3说明，只有满足否则惟一可译码不存在。但平均码长应该小于，这是按

31、应尽可能短的要求，这时得到的码是最佳码，其实，也能找到惟一可译码。，才能构成惟一可译码，332432143212121212181814121)(xxxxxxxxXqXmmmxqnn75. 13221)(814121 )/(75. 12log75. 18log8124log412log21)(log)(41符号比特iiixqxqXH1)(nXHRD【例例3.10】 信源 对信源进行二进制变长编码，D=2，信源各消息概率恰好表示成D=2的整数次幂，取码长等于其幂次，即取n1=1n2=2n3=3n4=3对信源各消息编码，得到的码就是紧致码，下面计算RD。（码元/符号）因为信息传输率RD的值小于等于

32、1，所以上述RD =1达到最大值，得到的码集为紧致码。（比特/码元时间）2733. 2737. 1322. 3322. 25432154321212121212125. 015. 03 . 01 . 02 . 0)(xxxxxxxxxxXqX55. 2225. 0315. 023 . 041 . 032 . 0n 25. 0log25. 015. 0log15. 03 . 0log3 . 01 . 0log1 . 02 . 0log2 . 0XH 228. 22loglogXHDXH DXHnDXHlog1log【例例3.11】对下述信源进行二进制变长编码， 根据式(3-20)，即码长nm 应

33、满足tm nm tm+1 ，tm是消息xm（m=1，2，3，4，5）的2次幂概率所对应的幂次，取x1,x2,x3,x4,x5所对应的码字的码长分别为n1=3n2=4n3=2n4=3 n5=2，计算出平均码长 熵 =2.228（比特/符号） 满足式(3-19) 则有定理定理3.4 变长编码定理变长编码定理 ( (Shannon第一定理第一定理) ) 给定熵为H（X）的离散无记忆信源 ，其L次扩展信源 的熵记为H（X），给定有D个元素的码符号集，对扩展信源进行编码，总可以找到一种惟一可译码，使码长 满足 (3-23)()()()(2121MMxqxqxqxxxXqX)()()()(2121LMMq

34、qqqx xx xx xx xx xx xX XX XLnLDXHLnDXHL1loglog定理3.3推广到L次扩展信源，就得到如下定理，即Shannon第一定理记 为信源每个符号所对应的平均码字数，则式(3-23)为 （3-24）nLnL LDXHnDXH1loglogShannon第一定理的物理意义在于：对信源进行编码，使编码后的码集中各码字尽可能等概分布，如果将这码集看成为一个新的信源，这时新信源所含信息量最大。定义编码效率编码效率 (3-26)是一个无量纲的数，一般情况下1，在极限情况下=1。 DnXHnDXHloglog讲书上例子3.12,3.13,P66 对于同一种信源，三种编码法

35、中以香农编码法的编码效率最低，费诺编码法也不是一种最佳编码法，但用这种方法有时候也能找到紧致码。一般情况下，霍夫曼编码法得到的平均码长 最短，即编码效率 最高。DnXHlogn3.4 3.4 变长码的编码方法变长码的编码方法香农（Shannon）编码法费诺(Fano)编码法霍夫曼(Huffman)编码法变长编码法：705.2 5.2 无失真信源编码无失真信源编码最佳变长编码最佳变长编码 凡是能载荷一定的信息量，且码字的平均长凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合称为度最短，可分离的变长码的码字集合称为最最佳变长码佳变长码。 715.2 5.2 无失真信源编码无失

36、真信源编码能能获得最佳码的编码方法主要有：获得最佳码的编码方法主要有：z香农（香农（Shannon）z费诺（费诺（Fano）z哈夫曼（哈夫曼（Huffman）等）等725.2 5.2 无失真信源编码无失真信源编码香农香农（Shannon）编码）编码z 1. 将信源消息符号按其出现的概率大小将信源消息符号按其出现的概率大小依次排列依次排列z 2. 确定满足下列不等式的整数码长确定满足下列不等式的整数码长Ki。nppp211loglog22iiipKp735.2 5.2 无失真信源编码无失真信源编码z 为了编成唯一可译码，计算第为了编成唯一可译码，计算第i个消息的个消息的累加概率累加概率z 将累加

37、概率将累加概率Pi变换成二进制数。变换成二进制数。z 取取Pi二进数的小数点后二进数的小数点后Ki位即为该消息符位即为该消息符号的二进制码字。号的二进制码字。 11ikkiapP745.2 5.2 无失真信源编码无失真信源编码例例 设信源共设信源共7个符号消息，其概率和累加概个符号消息，其概率和累加概率如下表所示。率如下表所示。-后面有题目后面有题目 【例例3.14】对给定信源 进行D=2进制香农编码。01. 010. 015. 017. 018. 019. 02 . 0)(7654321xxxxxxxXqX消息符号消息符号ai消息概率消息概率qi-log2qi码长码长ni累加概率累加概率码字

38、码字cia10.22.3430000a20.192.4130.2001a30.182.4830.39011a40.172.5630.57100a50.152.7430.74101a60.103.3440.891110a70.016.6670.991111110 表3-8香农编码765.2 5.2 无失真信源编码无失真信源编码信源消息信源消息符号符号ai符号概符号概率率(ai)累加概累加概率率Pi-log p(ai)码字长码字长度度Ki码字码字a10.2002.323000a20.190.22.393001a30.180.392.473011a40.170.572.563100a50.150.7

39、42.743101a60.100.893.3241110a70.010.996.6471111110以消息x5为例，对其进行编码：计算出 -logq(x5)=-log0.15=2.74，取整数n5=3作为x5的码字的码长，计算出消息x1,x2,x3,x4累加概率将0.74变换成二进制小数 (0.74)10=(0.1011110)2，取小数点后面三位101作为 x5的代码。151574. 017. 018. 019. 02 . 0)(mmxqp计算该编码的编码效率先算出信源熵 =2.61(比特/符号)71)(log)()(mmmxqxqXH平均码长 =3.14(比特/符号) 71)(mmmxqn

40、n则编码效率 831. 0114. 361. 2logDnXH785.2 5.2 无失真信源编码无失真信源编码，即117. 017. 04lbklb以以i=4为例，为例，316.526.5244kk，4440.57,0.1001.3,100.pka其累加概率变换成二进制：由于所 的编码为复习上一次课的主要内容z一、平均码长的计算z二、等长编码定理z三、变长编码定理 (Shannon第一定理) 3.1.3 平均码长的计算平均码长的计算对于变长码变长码，码集C的平均码长，用符号 表示，定义为码C中每个码字cm( m = 1,2,，M)其码长的概率加权平均值为 (3-1)式中nm是码字cm所对应的码

41、字的长度，p (cm )是码字cm出现的概率。 1()Mmmmnnpc cn对于等长码等长码，由于码集C中的每个码字的码长都相同，平均码长就等于每个码字的码长npnpnnmmmmm11)()(c cc c3.1.4 信息传输速率信息传输速率 信道的信息传输速率信息传输速率为信道单位时间内所传输的实际信息量。若信息量以比特为单位，时间以秒为单位，则信息传输率定义为： (比特/秒) (3-3)nXtHtR若信息量以比特为单位，时间以码元时间（传输一个码符号的时间）为单位，则信息传输率记为 (比特/码元时间) (3-4)nXHRDn为编码后的平均码长；H(X)为信源熵；式中：t为传输一个码符号的时间

42、。可以看出，越小，则越大，信息传输率就越高，因此我们感兴趣的码是使平均码长最短的码。信源S共有q=4个信源符号，s1,s2,s3,s4,现进行二元等长编码，其中码符号个数r=2，则根据5.1式可知，存在唯一可译等长码的条件是码长l必须不小于2如果N=1，则，则与前面的5.1式一样。l/N是平均每个信源符号所需要的码符号个数，表明对于等长唯一可译码，每个信源符号至少需要用个码符号来变换,也就是说，每个信源符号所需最短的码长为个。loglogqlrz当r=2（二元码）时，logr=1.则式5.2成为z这结果表明，对于二元等长唯一可译码，每个信源符号至少需要用 logq个二元符号来变换，也表明对信源

43、进行二元等长不失真编码时，每个信源符号所需码长的极限值为logq个。loglqN定理定理3.1 等长编码定理等长编码定理 设离散无记忆信源S =x1 ，x2 ，xk的熵为H（X），S的L维扩展信源为 ，对信源输出的L长序列si ，i=1,2,KL 进行等长编码，码字是长度为n的D进制符号串，当满足条件 ，则L 时，可使译码差错pe (、为无穷小量)；反之，当 时，则不可能实现无差错编码。,21)(LkLSs ss ss s DXHLnlog DXHLnlog定理定理3.1等长编码定理等长编码定理编码效率编码效率定理3.1要求 ，即 ，可看出比值 是一个小于1的无量纲纯数，定义它为等长编码的编码

44、效率，记为 （3-7） DXHLnlogDnXHLlog)(1DnXLHlog)(DnXLHlog)(定理3.1要求，是为了实现无差错编码每个信源符号所需要的最少码符号数，这是等长码编码时的理论极限。事实上这种几乎无失真的代价是要求信源序列长L , L 大就意味着实现的复杂性及译码的时延加大。n为码长-lL为信源序列长度-ND码符号个数-r3.3 3.3 变长码及变长编码定理变长码及变长编码定理 3.3.1 变长码变长码 对变长码的讨论是在L足够大的条件下得到的结论，当L为有限值时，则总会带来一定程度的失真。对于变长码，往往在L不是很大的情况下就可编出高效且无失真的码。 对于变长码，要求整个码

45、集的平均码长力求最小，此时编码效率最高。对于给定信源，使平均码长达到最小的编码方法，称为最佳编码最佳编码，得到的码集称为最佳码最佳码。3.3.2 克拉夫特不等式克拉夫特不等式 定理定理3.2 D进制码字集合C =c1, c2, cM ，码集中每一cm（m =1,2,M）都是一个D进制符号串，设c1, c2, cM 对应的码长分别是n1,n2, ,nM，则存在唯一可译码的充要条件是 (3-10)MmnmD11式（3-10）也称克拉夫特不等式克拉夫特不等式 定理3.2只是说是存在惟一可译码的充要条件，这里强调的是“存在”，但它并不是唯一可译码的充要条件，换言之，惟一可译码一定满足克拉夫特不等式，反

46、之，满足克拉夫特不等式的码不一定是惟一可译码。3.3.3 变长编码定理变长编码定理 定理定理3.3 给定熵为H（X）的离散无记忆信源，及有D个元素的码符号集，则总可找到一种无失真编码方法，构成惟一可译码，其平均码长 满足： （3-19）n DXHnDXHlog1logDXHnlogn DXHlog1n DXHnlog1定理3.3说明，只有满足否则惟一可译码不存在。但平均码长应该小于，这是按应尽可能短的要求，这时得到的码是最佳码，其实，也能找到惟一可译码。，才能构成惟一可译码，定理定理3.4 变长编码定理变长编码定理 ( (Shannon第一定理第一定理) ) 给定熵为H（X）的离散无记忆信源

47、，其L次扩展信源 的熵记为H（X），给定有D个元素的码符号集，对扩展信源进行编码，总可以找到一种惟一可译码，使码长 满足 (3-23)()()()(2121MMxqxqxqxxxXqX)()()()(2121LMMqqqqx xx xx xx xx xx xX XX XLnLDXHLnDXHL1loglog定理3.3推广到L次扩展信源，就得到如下定理，即Shannon第一定理记 为信源每个符号所对应的平均码字数，则式(3-23)为 （3-24）nLnL LDXHnDXH1loglogShannon第一定理的物理意义在于：对信源进行编码，使编码后的码集中各码字尽可能等概分布，如果将这码集看成为一

48、个新的信源，这时新信源所含信息量最大。定义编码效率编码效率 (3-26)是一个无量纲的数，一般情况下1，在极限情况下=1。 DnXHnDXHloglog 对于同一种信源，三种编码法中以香农编码法的编码效率最低，费诺编码法也不是一种最佳编码法，但用这种方法有时候也能找到紧致码。一般情况下，霍夫曼编码法得到的平均码长 最短，即编码效率 最高。DnXHlogn3.4 3.4 变长码的编码方法变长码的编码方法香农（Shannon）编码法费诺(Fano)编码法霍夫曼(Huffman)编码法变长编码法：945.2 5.2 无失真信源编码无失真信源编码香农香农（Shannon）编码）编码z 1. 将信源消息

49、符号按其出现的概率大小将信源消息符号按其出现的概率大小依次排列依次排列z 2. 确定满足下列不等式的整数码长确定满足下列不等式的整数码长Ki。nppp211loglog22iiipKp955.2 5.2 无失真信源编码无失真信源编码z 计算第计算第i个消息的累加概率个消息的累加概率z 将累加概率将累加概率Pi变换成二进制数。变换成二进制数。z 取取Pi二进数的小数点后二进数的小数点后Ki位即为该消息符位即为该消息符号的二进制码字。号的二进制码字。 11ikkiapP 05. 015. 03 . 05 . 0 xxxx)X(PX4321n, 2 , 1j)x(p)x(p1j0iija 1k12l

50、b)x(lbp11 2k74. 21)x(lbp,74. 13 . 0lb)x(lbp222 取取3k74. 31)x(lbp,74. 215. 0lb)x(lbp333 取取5k32. 51)x(lbp,32. 405. 0lb)x(lbp444 取取05. 0lb05. 015. 0lb15. 03 . 0lb3 . 05 . 0lb5 . 0)x(lbp)x(p)X(H41iii )symbol/bit(648. 1 )symbol/bit( 8 . 1505. 0315. 023 . 015 . 0k )x (pK41iii %6 .91916. 08 . 1648. 1K)X(H 信

51、息传输率=1035.2 5.2 无失真信源编码无失真信源编码费诺费诺编码方法编码方法费诺编码属于概率匹配编码费诺编码属于概率匹配编码(1)将信源消息符号按其出现的概率大小依将信源消息符号按其出现的概率大小依次排列：次排列： (2)将依次排列的信源符号按概率值分为两将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近于相同，大组，使两个组的概率之和近于相同，并对各组赋予一个二进制码元并对各组赋予一个二进制码元“0”和和“1”。nppp211045.2 5.2 无失真信源编码无失真信源编码(3)将每一大组的信源符号进一步再分成两将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率之

52、和近于组，使划分后的两个组的概率之和近于相同，并又赋予两个组一个二进制符号相同，并又赋予两个组一个二进制符号“0”和和“1”。(4)如此重复，直至每个组只剩下一个信源如此重复，直至每个组只剩下一个信源符号为止。符号为止。(5)信源符号所对应的码字即为费诺码。信源符号所对应的码字即为费诺码。1055.2 5.2 无失真信源编码无失真信源编码例例 对以下信源进行费诺编码对以下信源进行费诺编码。 消息符消息符号号ai各 个 消各 个 消息概率息概率 p(ai)第一次第一次分组分组第二次第二次分组分组第三次第三次分组分组第四次第四次分组分组二元二元码字码字码长码长Kia10.2000002a20.19

53、100103a30.1810113a40.1710102a50.15101103a60.101011104a70.011111141065.2 5.2 无失真信源编码无失真信源编码74. 2)(71iiiKapK953. 074. 261. 2)(KXHR码元码元/符号符号bit/符号符号1095.2 5.2 无失真信源编码无失真信源编码 哈夫曼哈夫曼编码方法编码方法(1)将信源消息符号按其出现的概率大小依次将信源消息符号按其出现的概率大小依次排列，排列，(2)取两个概率最小的字母分别配以取两个概率最小的字母分别配以0和和1两个两个码元，并将这两个概率相加作为一个新字码元，并将这两个概率相加作

54、为一个新字母的概率，与未分配的二进符号的字母重母的概率，与未分配的二进符号的字母重新排队。新排队。nppp21Thesixthweek1105.2 5.2 无失真信源编码无失真信源编码(3)对重排后的两个概率最小符号重复步骤对重排后的两个概率最小符号重复步骤(2)的过程。的过程。(4)不断继续上述过程，直到最后两个符号配不断继续上述过程，直到最后两个符号配以以0和和1为止。为止。(5)从最后一级开始，向前返回得到各个信源从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。符号所对应的码元序列，即相应的码字。【例例3.15.15】 对例3.14给出的 信源进行费诺编码01.

55、010. 015. 017. 018. 019. 02 . 0)(7654321xxxxxxxXqX （1）将信源消息分成两个子集 x1，x2，x3和 x4，x5，x6，x7，两个子集的和概率分别为0.2+0.19+0.18=0.57与0.17+0.15+0.10+0.01=0.43，赋予第一个子集码元“0”，赋予第二个子集码元“1”；（2）又将子集分成和概率尽可能接近相等的两个子集，分别赋予第一个子集码元“0”，赋予第二个子集码元“1”；（3）一直进行下去，直到每个子集仅含一个消息为止。该编码的编码效率：例3.14中已算出信源熵 H（X）=2.61（比特/符号）平均码长 =2.7471)(m

56、mmxqnn则编码效率： 935. 0174. 261. 2logDnXH1125.2 5.2 无失真信源编码无失真信源编码例例 对以下信源进行哈夫曼编码对以下信源进行哈夫曼编码 信源符号信源符号ai概率概率p(ai) 码字码字Wi码长码长Kia10.20102a20.19112a30.180003a40.170013a50.150103a60.1001104a70.01011141135.2 5.2 无失真信源编码无失真信源编码0.20 0.20 0.26 0.35 0.39 0.61 1.00.19 0.19 0.20 0.26 0.35 0.390.18 0.18 0.19 0.20 0

57、.260.17 0.17 0.18 0.190.15 0.15 0.170.10 0.110.010101010101011145.2 5.2 无失真信源编码无失真信源编码码元码元/符号符号bit/符号符号72. 2)(71iiiKapK96. 072. 261. 2)(KXHR1215.2 5.2 无失真信源编码无失真信源编码哈夫曼编码方法得到的码并哈夫曼编码方法得到的码并非唯一非唯一的的z每次对信源缩减时，赋予信源最后两个概每次对信源缩减时，赋予信源最后两个概率最小的符号，用率最小的符号，用0和和1是可以任意的，所是可以任意的，所以可以得到不同的哈夫曼码，但不会影响以可以得到不同的哈夫曼码

58、，但不会影响码字的长度。码字的长度。1225.2 5.2 无失真信源编码无失真信源编码z对信源进行缩减时，两个概率最小的符对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率号合并后的概率与其它信源符号的概率相同相同时，这两者在缩减信源中进行概率时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响故会得到不同的哈夫曼码。此时将影响码字的长度，一般将码字的长度，一般将合并的概率放在上合并的概率放在上面面，这样可获得，这样可获得较小的码方差较小的码方差。1235.2 5.2 无失真信源编码无失真信源编码

59、例例 设有离散无记忆信源设有离散无记忆信源1 . 01 . 02 . 02 . 04 . 054321aaaaaPX1245.2 5.2 无失真信源编码无失真信源编码信源符号信源符号ai概率概率p(ai)码字码字Wi1码长码长Ki1码字码字Wi2码长码长Ki2a10.411002a20.2012102a30.20003112a40.1001040103a50.1001140113 其有两种哈夫曼编码方法：其有两种哈夫曼编码方法：1255.2 5.2 无失真信源编码无失真信源编码0.4 0.4 0.4 0.6 1.0 0.2 0.2 0.4 0.40.2 0.2 0.20.1 0.2 0.10.

60、4 0.4 0.4 0.6 1.0 0.2 0.2 0.4 0.40.2 0.2 0.20.1 0.20.101010101010101011265.2 5.2 无失真信源编码无失真信源编码2 . 2)(71iiiKapK为：二者平均码长相等，均 码元码元/符号符号965. 0)(KXH1275.2 5.2 无失真信源编码无失真信源编码qiiiilKkapKkE1222)(36. 121l16. 022l1285.2 5.2 无失真信源编码无失真信源编码 进行哈夫曼编码时，为得到进行哈夫曼编码时，为得到码方差码方差最小的码，最小的码，应使合并的信源符号位于缩减信源序列应使合并的信源符号位于缩减