第3章无失真信源编码

第3章无失真信源编码第一页，共173页。第3章离散信源无失真编码

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

增强通信的可靠性

信息论的研究对象--通信系统模型，信源，编码器，信道，译码器，信宿。第四页，共173页。（1）提高传输效率，用尽可能少的信道传输符号来传递信源消息，目的是提高传输效率，这是信源编码主要应考虑的问题。这里又分两种情况讨论，即允许接收信号有一定的失真或不允许失真。综上所述，提高抗干扰能力往往是以降低信息传输效率为代价的，而为了提高传输效率又往往削弱了其抗干扰能力。这样，设计者在取舍之间就要作均衡考虑。

（2）

增强通信的可靠性如何增加信号的抗干扰能力，提高传输的可靠性，这是信道编码主要考虑的问题。解决这一问题，一般是采用冗余编码法，赋予信码自身一定的纠错和检错能力，只要采取适当的信道编码和译码措施，就可使信道传输的差错概率降到允许的范围之内。第五页，共173页。信源编码包括两个功能：（1）

将信源符号变换成适合信道传输的符号；（2）

压缩信源冗余度，提高传输效率。第六页，共173页。7由于信源符号之间存在分布不均匀和相关性，使得信源存在冗余度，信源编码的主要任务就是减少冗余，提高编码效率。

第七页，共173页。8信源编码的基本途径有两个：使序列中的各个符号尽可能地互相独立，即解除相关性；使编码中各个符号出现的概率尽可能地相等，即概率均匀化。第八页，共173页。9信源编码的基础是信息论中的两个编码定理：无失真编码定理---香农第一定律，给出了信源无失真变长编码时其码长的上、下限值。限失真编码定理

无失真编码只适用于离散信源

对于连续信源，只能在失真受限制的情况下进行限失真编码

第九页，共173页。无失真信源编码：能够精确地复现信源的输出，保证信源产生的全部信息无损地送给信宿，这时的信源编码就是无失真信源编码。第十页，共173页。3.1.1信源编码的相关概念

编码器3.1第十一页，共173页。图3.1信源编码器第十二页，共173页。3.1第十三页，共173页。书上例子：3.1,3.2第十四页，共173页。信源编码有以下3种主要方法：(1)匹配编码根据信源符号的概率不同，编码的码长不同：概率大的信源符号，所编的代码短；概率小的信源符号所编的代码长，这样使平均码长最短。将要讲述的香农编码、哈夫曼编码、费诺码都是概率匹配编码，都是无失真信源编码。(2)变换编码先对信号进行变换，从一种信号空间变换为另一种信号空间，然后针对变换后的信号进行编码。(3)识别编码识别编码主要用于印刷或打字机等有标准形状的文字符号和数据的编码，比如中文文字和语音的识别。后两种信源编码均为有失真的信源编码。无失真信源编码主要针对离散信源，连续信源在量化编码的过程中必然会有量化失真，所以对连续信源只能近似地再现信源的消息。第十五页，共173页。信源编码可看成是从信源符号集到码符号集的一种映射，即将信源符号集中的每个元素（可以是单符号，也可以是符号序列）映射成一个长度为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.2码的分类第十六页，共173页。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}，则码字就是二元序列，称为二元码,二元码通过二进制信道传输，这是数字通信和计算机通信中最常见的一种码，表3-1列出的4种码都是二元码。第十七页，共173页。5.非奇异码从信源消息到码字的影射是一一对应的，每一个不同的信源消息都用不同的码字对其编码，若一组码中所有码字都不相同，则称为非奇异码。例表3-1中的码2、码3和码4都是非奇异码。4.奇异码对奇异码来说，从信源消息到码字的影射不是一一对应的。若一组码中有相同的码字，则称为奇异码。例表3-1中的码1，信源消息u2和u4都用码字11对其编码，因此这种码就是奇异码，奇异码不具备惟一可译性。

第十八页，共173页。扩展信源

信源编码器

信源符号{a1,a2,…,aK}

信道符号（码符号）{b1,b2,…,bD}

消息

u1

…uN=(u11u12…

u1L)…

(uN1uN2…

uNL)N次扩展码字

c1

…cN=(c11c12…

c1n)…

(cN1cN2…

cNn)图3-2N次扩展信源编码器模型

原码的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个码字组成的序列。草稿第十九页，共173页。对于定长码，若原码是惟一可译码，则它的N次扩展码也是惟一可译的，而对于变长码则不尽然，见表3-2。信源消息各消息概率码1码2码3u1q(u1)011u2q(u2)11001u3q(u3)00100001u4q(u4)1110000001表3-2同一信源的几种不同变长编码表3-2同一信源的几种不同变长编码

7.惟一可译码定义3.1如果码的任意N次扩展码都是非奇异码，则称该码为惟一可译码。NYY第二十页，共173页。对于码1，由于它的每一个信源符号对应不同的码字，所以它本身是唯一可译，但将它进行二次扩展后得到的二次扩展码就不唯一可译，例如，二次扩展码中的u1u3和u3u1对应同一个码字000，u2u4和u4u2对应同一个码字111，因此码1不是唯一可译码。对于码2，码3不仅本身是唯一可译码，进行N次扩展后得到的N次扩展码也是唯一可译的，按照定义3.1，码2、码3是唯一可译码。第二十一页，共173页。第三章：离散信源无失真编码

编码器第二十二页，共173页。码的分类

1.二元码：若码符号集为{0，1}，则码字就是二元序列，称为二元码；2.等长码：码中所有码字的长度，都相同；3.变长码：码中的码字长短不一；4.奇异码：若一组码中有相同的码字，则称为奇异码；5.非奇异码：若一组码中所有码字都不相同。6.原码C的N次扩展码7.惟一可译码：如果码的任意N次扩展码都是非奇异码，则称该码为惟一可译码。第二十三页，共173页。8.即时码对于变长码，又有如下定义定义3.2

对于码字c

=c1c2…

cn,称c、

=c1c2…

ci(i<n)为码字c的字头（前缀）。定义3.3若码中任一码字都不是另一码字的字头，称该码为异字头码（无前缀码）。码3是无前缀码，码1和2都不是无前缀码第二十四页，共173页。表3-2中码3，收到“1”后就知道一个码字已经完结，无须等待下一个符号抵达，所以无前缀码能够即时译码,称之为即时可译码，简称即时码。而对于码2，收到“1”后，并不能立即做出判决，就是收到“10”也不能立即做出判决，则还要收到下面的码元才能做出判决。所以非异字头码不能即时译码，称为非即时码，由于非异字头码的其中一些码字是另一些码字的延长，故也称延长码。显然，即时码是惟一可译码，而惟一可译码不一定是即时码。因为有些非即时码(延长码)具有唯一可译性，但不满足前缀条件，不能即时译码第二十五页，共173页。即时码可用树图法来构造。对给定码字的全体集合来说，可以用码树来描述它，例子下面。所谓树，既有根，枝，又有节点。树中最顶部的节点称为根节点，从根出发向下伸出树枝，树枝的数目等于码符号的总数r。没有子节点的节点称为叶子节点。所有根节点的子节点称为一阶节点，所有一阶节点的子节点称为二阶节点，依此类推。n阶节点最多有个。节点的阶次又称为节点的深度。当某一节点被安排为码字后，它就不再继续伸枝，此节点称为终端节点，用粗黑点表示。图3-3用树图法编码树根编码深度u1：1u2：01u3：001u4：00011

0u1u2u3u41

1

1

00【例3.4】用树图法表示表3-2中的码3，如图3-3所示（D=2）。第二十六页，共173页。复习上次课的内容：编码器码的分类第二十七页，共173页。复习上次课的内容：第二十八页，共173页。码的分类

1.二元码：若码符号集为{0，1}，则码字就是二元序列，称为二元码；2.等长码：码中所有码字的长度，都相同；3.变长码：码中的码字长短不一；4.奇异码：若一组码中有相同的码字，则称为奇异码；5.非奇异码：若一组码中所有码字都不相同。6.原码C的N次扩展码7.惟一可译码：如果码的任意N次扩展码都是非奇异码，则称该码为惟一可译码。8.即时码:无需考虑后续的码符号就可以从码符号序列中译出码字，这样的唯一可译码称为即时码。第二十九页，共173页。8.即时码对于变长码，又有如下定义定义3.2

对于码字c

=c1c2…

cn,称c、

=c1c2…

ci(i<n)为码字c的字头（前缀）。定义3.3若码中任一码字都不是另一码字的字头，称该码为异字头码（无前缀码）。码3是无前缀码，码1和2都不是无前缀码第三十页，共173页。表3-2中码3，收到“1”后就知道一个码字已经完结，无须等待下一个符号抵达，所以无前缀码能够即时译码,称之为即时可译码，简称即时码。而对于码2，收到“1”后，并不能立即做出判决，就是收到“10”也不能立即做出判决，则还要收到下面的码元才能做出判决。所以非异字头码不能即时译码，称为非即时码，由于非异字头码的其中一些码字是另一些码字的延长，故也称延长码。显然，即时码是惟一可译码，而惟一可译码不一定是即时码。因为有些非即时码(延长码)具有唯一可译性，但不满足前缀条件，不能即时译码第三十一页，共173页。即时码可用树图法来构造。对给定码字的全体集合来说，可以用码树来描述它，例子下面。所谓树，既有根，枝，又有节点。树中最顶部的节点称为根节点，从根出发向下伸出树枝，树枝的数目等于码符号的总数r。没有子节点的节点称为叶子节点。所有根节点的子节点称为一阶节点，所有一阶节点的子节点称为二阶节点，依此类推。n阶节点最多有个。节点的阶次又称为节点的深度。当某一节点被安排为码字后，它就不再继续伸枝，此节点称为终端节点，用粗黑点表示。图3-3用树图法编码树根编码深度u1：1u2：01u3：001u4：00011

0u1u2u3u41

1

1

00【例3.4】用树图法表示表3-2中的码3，如图3-3所示（D=2）。第三十二页，共173页。即时码的树图构造法我们可以用树图的形式构造即时码，如01001111010010001码4的树图10110000101001000码3的树图树根——码字的起点树枝数——码的数节点数——码字的一部分节数——码长端点——码字满树——等长码非满树——变长码第三十三页，共173页。第三十四页，共173页。书上例子3.5第三十五页，共173页。9同价码

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

定义

将信源符号集中的每个信源符号固定地映射成一个码字Wi，这样的码称为分组码。用分组码对信源符号进行编码时，为了使接收端能够迅速准确地将码译出，分组码必须具有一些直观属性。与分组码对应的是非分组码，又称为树码、树码编码器输出的码符号通常与编码器的所有信源符号都有关。si第三十七页，共173页。图3-5码的分类结构图

图3-5是码的分类结构图

由上面的结构图可看出，我们只讨论非奇异码。非奇异码又分为惟一可译码和非惟一可译码两大类，我们只讨论惟一可译码。

第三十八页，共173页。3.1.3平均码长的计算

对于变长码，码集C的平均码长，用符号表示，定义为码C中每个码字cm(m=1,2,…，M)其码长的概率加权平均值为 (3-1)式中nm是码字cm所对应的码字的长度，p(cm

)是码字cm出现的概率。对于等长码，由于码集C中的每个码字的码长都相同，平均码长就等于每个码字的码长第三十九页，共173页。书上例子P54页，计算平均码长n1,n2,n3,n4第四十页，共173页。N次扩展码的平均码长等于扩展码中码字长度的概率加权平均值。对于2次扩展码，有：

(3-2)设nm,

ns分别是原信源消息um,

us所对应的码长,cm,

cs是um,

us所对应的码字，则式(3-2)中的nm+ns是扩展后新的信源序列nmns所对应的码字cmcs的长度，q(um)q(us)是cmcs出现的概率。书上的例子3.6第四十一页，共173页。3.1.4信息传输速率信道的信息传输速率为信道单位时间内所传输的实际信息量。若信息量以比特为单位，时间以秒为单位，则信息传输率定义为： (比特/秒)(3-3)若信息量以比特为单位，时间以码元时间（传输一个码符号的时间）为单位，则信息传输率记为

(比特/码元时间) (3-4)

为编码后的平均码长；H(X)为信源熵；式中：t为传输一个码符号的时间。可以看出，越小，则越大，信息传输率就越高，因此我们感兴趣的码是使平均码长最短的码。第四十二页，共173页。书上例子。3.7第四十三页，共173页。【例3.8】

给定信源，为提高传输效率，使平均码长尽可能短，遵照概率大取码长短，概率小取码长长的原则对上述信源进行二进制不等长编码，得到，求编码后的信息传输率RD。第四十四页，共173页。解：根据定义第四十五页，共173页。如果码的任意N次扩展码都是非奇异码，则称该码为惟一可译码。(非奇异码为码中所有码字都不相同)第四十六页，共173页。DS2S3:10110,S5S1:10110FS1S4:0110S6S1:0110第四十七页，共173页。信源S共有q=4个信源符号，s1,s2,s3,s4,现进行二元等长编码，其中码符号个数r=2，则根据5.1式可知，存在唯一可译等长码的条件是码长l必须不小于2第四十八页，共173页。如果N=1，则，则与前面的5.1式一样。l/N是平均每个信源符号所需要的码符号个数，表明对于等长唯一可译码，每个信源符号至少需要用个码符号来变换,也就是说，每个信源符号所需最短的码长为个。第四十九页，共173页。当r=2（二元码）时，logr=1.则式5.2成为这结果表明，对于二元等长唯一可译码，每个信源符号至少需要用logq个二元符号来变换，也表明对信源进行二元等长不失真编码时，每个信源符号所需码长的极限值为logq个。第五十页，共173页。定理3.1

等长编码定理

设离散无记忆信源S={x1

，x2

，…，xk}的熵为H（X），S的L维扩展信源为，对信源输出的L长序列si，i=1,2,…,KL进行等长编码，码字是长度为n的D进制符号串，当满足条件，则L→∞时，可使译码差错pe<δ(ε、δ为无穷小量)；反之，当 时，则不可能实现无差错编码。定理3.1

等长编码定理第五十一页，共173页。将定理要求的下界与式（3-6）要求的下界作一个比较:H（X）是单符号信源S={x1

，x2

，…，xk}的熵，根据极大离散熵定理，信源等概分布时熵值最大，其最大值为logk，即有H（X）

logK，这就说明了定理3.1要求的下界比式（3-6）要求的下界更紧致，对的要求更低。

仍然考虑[例3-7]中所列举的英文字符信源，根据式（3-6），可求出根据定理3.1要求，可求出显然n1>n2，实际上由于要求码长取整数，故只能取n1=n2=5。n为码长----lK信源的符号个数----qD码符号个数---rn为码长----lL为信源序列长度---N第五十二页，共173页。编码效率定理3.1要求，即，可看出比值是一个小于1的无量纲纯数，定义它为等长编码的编码效率，记为

（3-7）

定理3.1要求，是为了实现无差错编码每个信源符号所需要的最少码符号数，这是等长码编码时的理论极限。事实上这种几乎无失真的代价是要求信源序列长L→∞,L大就意味着实现的复杂性及译码的时延加大。n为码长----lL为信源序列长度---ND码符号个数---r第五十三页，共173页。例子3.9P58第五十四页，共173页。3.3变长码及变长编码定理

3.3.1变长码对变长码的讨论是在L足够大的条件下得到的结论，当L为有限值时，则总会带来一定程度的失真。对于变长码，往往在L不是很大的情况下就可编出高效且无失真的码。变长码也要求原码的任意L次扩展码也是惟一可译的。变长码分为即时码和延长码，为保证即时译码，要求变长惟一可译码采用即时码。对于变长码，要求整个码集的平均码长力求最小，此时编码效率最高。对于给定信源，使平均码长达到最小的编码方法，称为最佳编码，得到的码集称为最佳码。第五十五页，共173页。3.3.2克拉夫特不等式定理3.2

D进制码字集合C={c1,c2,…,cM}，码集中每一cm（m=1,2,…,M）都是一个D进制符号串，设c1,c2,…,cM对应的码长分别是n1,n2,

…,nM

，则存在唯一可译码的充要条件是

(3-10)

式（3-10）也称克拉夫特不等式

定理3.2只是说是存在惟一可译码的充要条件，这里强调的是“存在”，但它并不是唯一可译码的充要条件，换言之，惟一可译码一定满足克拉夫特不等式，反之，满足克拉夫特不等式的码不一定是惟一可译码。

第五十六页，共173页。575.1编码的定义例：设二进制码树中X(a1，a2，a3，a4)，l1＝1，l2＝2，l3＝2，l4＝3，应用上述判断定理：

因此不存在满足这种li的唯一可译码。

第五十七页，共173页。585.1编码的定义a1=1

01

01

01a2=01a3=001a4=000{1，01，001，000}

惟一可译码；{1，01，101，000}

不是惟一可译码；均满足克劳夫特不等式第五十八页，共173页。595.1编码的定义克劳夫特不等式只是用来说明唯一可译码是否存在，并不能作为唯一可译码的判据。第五十九页，共173页。3.3.3变长编码定理定理3.3

给定熵为H（X）的离散无记忆信源，及有D个元素的码符号集，则总可找到一种无失真编码方法，构成惟一可译码，其平均码长满足： （3-19）证明：(1)先证下界，即证。设离散无记忆信源含M个消息，信源熵为H（X），其统计模型为第六十页，共173页。

则：（利用克拉夫特不等式）第六十一页，共173页。当即

时，上式中等号成立，有

→这时得到的码就是紧致码，意味着信源消息概率分布q(xm)必须有(hm为整数)的形式，直接取各消息码字的码长nm等于q(xm)所对应的指数hm即可。这就是[例3.8]所例举的情况，在[例3.8]中，信源分布可以表示为取信源各消息相应的码字的码长等于其分布概率所对应的指数，即n0=2n1=2n2=3n3=3n4=4n5=4n6=4n7=4得到的信源编码就是紧致码（最佳码）。第六十二页，共173页。第六十三页，共173页。[定理3.3]说明，只有满足否则惟一可译码不存在。但平均码长应该小于，这是按应尽可能短的要求，这时得到的码是最佳码，其实，也能找到惟一可译码。

，才能构成惟一可译码，第六十四页，共173页。【例3.10】

信源对信源进行二进制变长编码，D=2，信源各消息概率恰好表示成D=2的整数次幂，取码长等于其幂次，即取n1=1n2=2n3=3n4=3对信源各消息编码，得到的码就是紧致码，下面计算RD。（码元/符号）因为信息传输率RD的值小于等于1，所以上述RD=1达到最大值，得到的码集为紧致码。（比特/码元时间）第六十五页，共173页。【例3.11】对下述信源进行二进制变长编码，

根据式(3-20)，即码长nm

应满足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)

则有

第六十六页，共173页。定理3.4

变长编码定理(Shannon第一定理)

给定熵为H（X）的离散无记忆信源，其L次扩展信源的熵记为H（X），给定有D个元素的码符号集，对扩展信源进行编码，总可以找到一种惟一可译码，使码长满足(3-23)

定理3.3推广到L次扩展信源，就得到如下定理，即Shannon第一定理第六十七页，共173页。记为信源每个符号所对应的平均码字数，则式(3-23)为

（3-24）

Shannon第一定理的物理意义在于：对信源进行编码，使编码后的码集中各码字尽可能等概分布，如果将这码集看成为一个新的信源，这时新信源所含信息量最大。定义编码效率(3-26)η是一个无量纲的数，一般情况下η<1，在极限情况下η=1。讲书上例子3.12,3.13,P66第六十八页，共173页。对于同一种信源，三种编码法中以香农编码法的编码效率最低，费诺编码法也不是一种最佳编码法，但用这种方法有时候也能找到紧致码。一般情况下，霍夫曼编码法得到的平均码长最短，即编码效率最高。3.4变长码的编码方法香农（Shannon）编码法费诺(Fano)编码法霍夫曼(Huffman)编码法变长编码法：第六十九页，共173页。705.2无失真信源编码最佳变长编码

凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合称为最佳变长码。

第七十页，共173页。715.2无失真信源编码能获得最佳码的编码方法主要有：香农（Shannon）费诺（Fano）哈夫曼（Huffman）等

第七十一页，共173页。725.2无失真信源编码香农（Shannon）编码1.将信源消息符号按其出现的概率大小依次排列2.确定满足下列不等式的整数码长Ki。第七十二页，共173页。735.2无失真信源编码为了编成唯一可译码，计算第i个消息的累加概率将累加概率Pi变换成二进制数。取Pi二进数的小数点后Ki位即为该消息符号的二进制码字。第七十三页，共173页。745.2无失真信源编码例设信源共7个符号消息，其概率和累加概率如下表所示。---后面有题目

第七十四页，共173页。【例3.14】对给定信源

进行D=2进制香农编码。消息符号ai消息概率qi-log2qi码长ni累加概率码字cia10.22.3430000a20.192.4130.2001a30.182.4830.39011a40.172.5630.57100a50.152.7430.74101a60.103.3440.891110a70.016.6670.99

表3-8香农编码

第七十五页，共173页。765.2无失真信源编码信源消息符号ai符号概率(ai)累加概率Pi-logp(ai)码字长度Ki码字a10.2002.323000a20.190.22.393001a30.180.392.473011a40.170.572.563100a50.150.742.743101a60.100.893.3241110a70.010.996.647第七十六页，共173页。以消息x5为例，对其进行编码：计算出-logq(x5)=-log0.15=2.74，取整数n5=3作为x5的码字的码长，计算出消息x1,x2,x3,x4累加概率将0.74变换成二进制小数(0.74)10=(0.1011110)2，取小数点后面三位101作为x5的代码。

计算该编码的编码效率

先算出信源熵=2.61(比特/符号)平均码长=3.14(比特/符号)则编码效率

第七十七页，共173页。785.2无失真信源编码以i=4为例，第七十八页，共173页。复习上一次课的主要内容一、平均码长的计算二、等长编码定理三、变长编码定理(Shannon第一定理)第七十九页，共173页。3.1.3平均码长的计算

对于变长码，码集C的平均码长，用符号表示，定义为码C中每个码字cm(m=1,2,…，M)其码长的概率加权平均值为 (3-1)式中nm是码字cm所对应的码字的长度，p(cm

)是码字cm出现的概率。对于等长码，由于码集C中的每个码字的码长都相同，平均码长就等于每个码字的码长第八十页，共173页。3.1.4信息传输速率信道的信息传输速率为信道单位时间内所传输的实际信息量。若信息量以比特为单位，时间以秒为单位，则信息传输率定义为： (比特/秒)(3-3)若信息量以比特为单位，时间以码元时间（传输一个码符号的时间）为单位，则信息传输率记为

(比特/码元时间) (3-4)

为编码后的平均码长；H(X)为信源熵；式中：t为传输一个码符号的时间。可以看出，越小，则越大，信息传输率就越高，因此我们感兴趣的码是使平均码长最短的码。第八十一页，共173页。信源S共有q=4个信源符号，s1,s2,s3,s4,现进行二元等长编码，其中码符号个数r=2，则根据5.1式可知，存在唯一可译等长码的条件是码长l必须不小于2第八十二页，共173页。如果N=1，则，则与前面的5.1式一样。l/N是平均每个信源符号所需要的码符号个数，表明对于等长唯一可译码，每个信源符号至少需要用个码符号来变换,也就是说，每个信源符号所需最短的码长为个。第八十三页，共173页。当r=2（二元码）时，logr=1.则式5.2成为这结果表明，对于二元等长唯一可译码，每个信源符号至少需要用logq个二元符号来变换，也表明对信源进行二元等长不失真编码时，每个信源符号所需码长的极限值为logq个。第八十四页，共173页。定理3.1

等长编码定理

设离散无记忆信源S={x1

，x2

，…，xk}的熵为H（X），S的L维扩展信源为，对信源输出的L长序列si，i=1,2,…,KL进行等长编码，码字是长度为n的D进制符号串，当满足条件，则L→∞时，可使译码差错pe<δ(ε、δ为无穷小量)；反之，当 时，则不可能实现无差错编码。定理3.1

等长编码定理第八十五页，共173页。编码效率定理3.1要求，即，可看出比值是一个小于1的无量纲纯数，定义它为等长编码的编码效率，记为

（3-7）

定理3.1要求，是为了实现无差错编码每个信源符号所需要的最少码符号数，这是等长码编码时的理论极限。事实上这种几乎无失真的代价是要求信源序列长L→∞,L大就意味着实现的复杂性及译码的时延加大。n为码长----lL为信源序列长度---ND码符号个数---r第八十六页，共173页。3.3变长码及变长编码定理

3.3.1变长码对变长码的讨论是在L足够大的条件下得到的结论，当L为有限值时，则总会带来一定程度的失真。对于变长码，往往在L不是很大的情况下就可编出高效且无失真的码。对于变长码，要求整个码集的平均码长力求最小，此时编码效率最高。对于给定信源，使平均码长达到最小的编码方法，称为最佳编码，得到的码集称为最佳码。第八十七页，共173页。3.3.2克拉夫特不等式定理3.2

D进制码字集合C={c1,c2,…,cM}，码集中每一cm（m=1,2,…,M）都是一个D进制符号串，设c1,c2,…,cM对应的码长分别是n1,n2,

…,nM

，则存在唯一可译码的充要条件是

(3-10)

式（3-10）也称克拉夫特不等式

定理3.2只是说是存在惟一可译码的充要条件，这里强调的是“存在”，但它并不是唯一可译码的充要条件，换言之，惟一可译码一定满足克拉夫特不等式，反之，满足克拉夫特不等式的码不一定是惟一可译码。

第八十八页，共173页。3.3.3变长编码定理定理3.3

给定熵为H（X）的离散无记忆信源，及有D个元素的码符号集，则总可找到一种无失真编码方法，构成惟一可译码，其平均码长满足： （3-19）第八十九页，共173页。[定理3.3]说明，只有满足否则惟一可译码不存在。但平均码长应该小于，这是按应尽可能短的要求，这时得到的码是最佳码，其实，也能找到惟一可译码。

，才能构成惟一可译码，第九十页，共173页。定理3.4

变长编码定理(Shannon第一定理)

给定熵为H（X）的离散无记忆信源，其L次扩展信源的熵记为H（X），给定有D个元素的码符号集，对扩展信源进行编码，总可以找到一种惟一可译码，使码长满足(3-23)

定理3.3推广到L次扩展信源，就得到如下定理，即Shannon第一定理第九十一页，共173页。记为信源每个符号所对应的平均码字数，则式(3-23)为

（3-24）

Shannon第一定理的物理意义在于：对信源进行编码，使编码后的码集中各码字尽可能等概分布，如果将这码集看成为一个新的信源，这时新信源所含信息量最大。定义编码效率(3-26)η是一个无量纲的数，一般情况下η<1，在极限情况下η=1。第九十二页，共173页。对于同一种信源，三种编码法中以香农编码法的编码效率最低，费诺编码法也不是一种最佳编码法，但用这种方法有时候也能找到紧致码。一般情况下，霍夫曼编码法得到的平均码长最短，即编码效率最高。3.4变长码的编码方法香农（Shannon）编码法费诺(Fano)编码法霍夫曼(Huffman)编码法变长编码法：第九十三页，共173页。945.2无失真信源编码香农（Shannon）编码1.将信源消息符号按其出现的概率大小依次排列2.确定满足下列不等式的整数码长Ki。第九十四页，共173页。955.2无失真信源编码计算第i个消息的累加概率将累加概率Pi变换成二进制数。取Pi二进数的小数点后Ki位即为该消息符号的二进制码字。第九十五页，共173页。例1，对单符号离散信源编二进制香农码，并计算其编码效率。解：①将xi按概率进行降序排列xip(xi)pa(xj)ki码字x10.5x20.3x30.15x40.05第九十六页，共173页。②令p(x0)=0，计算第j-1个码字的累加概率pa(x1)=0pa(x2)=0+0.5=0.5pa(x3)=0.5+0.3=0.8pa(x4)=0.8+0.15=0.95③确定第i个码字的码长ki：第九十七页，共173页。④将pa(xj)用二进制表示，取小数点后ki位作为xi的码字pa(x1)=0.0=(0.0)2→0pa(x2)=0.5=(0.10)2→10pa(x3)=0.8=(0.110…)2→110pa(x4)=0.95=(0.11110…)2→11110第九十八页，共173页。xip(xi)pa(xj)ki码字x10.5010x20.30.5210x30.150.83110x40.050.95511110第九十九页，共173页。信息传输率第一百页，共173页。第一百零一页，共173页。=第一百零二页，共173页。1035.2无失真信源编码费诺编码方法费诺编码属于概率匹配编码(1)将信源消息符号按其出现的概率大小依次排列：(2)将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近于相同，并对各组赋予一个二进制码元“0”和“1”。第一百零三页，共173页。1045.2无失真信源编码(3)将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率之和近于相同，并又赋予两个组一个二进制符号“0”和“1”。(4)如此重复，直至每个组只剩下一个信源符号为止。(5)信源符号所对应的码字即为费诺码。第一百零四页，共173页。1055.2无失真信源编码例对以下信源进行费诺编码。

消息符号ai各个消息概率p(ai)第一次分组第二次分组第三次分组第四次分组二元码字码长Kia10.2000002a20.19100103a30.1810113a40.1710102a50.15101103a60.101011104a70.01111114第一百零五页，共173页。1065.2无失真信源编码

码元/符号

bit/符号

第一百零六页，共173页。第一百零七页，共173页。第一百零八页，共173页。1095.2无失真信源编码

哈夫曼编码方法(1)将信源消息符号按其出现的概率大小依次排列，(2)取两个概率最小的字母分别配以0和1两个码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进符号的字母重新排队。Thesixthweek第一百零九页，共173页。1105.2无失真信源编码(3)对重排后的两个概率最小符号重复步骤(2)的过程。(4)不断继续上述过程，直到最后两个符号配以0和1为止。(5)从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。第一百一十页，共173页。【例3.15】

对[例3.14]给出的信源进行费诺编码

（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.74则编码效率：

第一百一十一页，共173页。1125.2无失真信源编码例对以下信源进行哈夫曼编码

信源符号ai概率p(ai)码字Wi码长Kia10.20102a20.19112a30.180003a40.170013a50.150103a60.1001104a70.0101114第一百一十二页，共173页。1135.2无失真信源编码0.20 0.200.260.350.390.611.00.190.190.200.260.350.390.180.180.190.200.260.170.170.180.190.150.150.170.100.110.01010101010101第一百一十三页，共173页。1145.2无失真信源编码

码元/符号

bit/符号

第一百一十四页，共173页。第一百一十五页，共173页。第一百一十六页，共173页。第一百一十七页，共173页。第一百一十八页，共173页。第一百一十九页，共173页。第一百二十页，共173页。1215.2无失真信源编码哈夫曼编码方法得到的码并非唯一的每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1是可以任意的，所以可以得到不同的哈夫曼码，但不会影响码字的长度。第一百二十一页，共173页。1225.2无失真信源编码对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可获得较小的码方差。第一百二十二页，共173页。1235.2无失真信源编码例设有离散无记忆信源第一百二十三页，共173页。1245.2无失真信源编码信源符号ai概率p(ai)码字Wi1码长Ki1码字Wi2码长K’i2a10.411002a20.2012102a30.20003112a40.1001040103a50.1001140113

其有两种哈夫曼编码方法：第一百二十四页，共173页。1255.2无失真信源编码0.40.40.40.61.00.20.20.40.40.20.20.20.10.20.10.40.40.40.61.00.20.20.40.40.20.20.20.10.20.10101010101010101第一百二十五页，共173页。1265.2无失真信源编码

码元/符号

第一百二十六页，共173页。1275.2无失真信源编码第一百二十七页，共173页。1285.2无失真信源编码

进行哈夫曼编码时，为得到码方差最小的码，应使合并的信源符号位于缩减信源序列尽可能高的位置上，以减少再次合并的次数，充分利用短码。

第一百二十八页，共173页。1295.2无失真信源编码哈夫曼码是用概率匹配方法进行信源编码。哈夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，充分利用了短码；缩减信源的最后二个码字总是最后一位不同，从而保证了哈夫曼码是即时码。第一百二十九页，共173页。r进制哈夫曼编码第一百三十页，共173页。第一百三十一页，共173页。第一百三十二页，共173页。第一百三十三页，共173页。第一百三十四页，共173页。考虑第一百三十五页，共173页。习题：书P3.18第一百三十六页，共173页。第一百三十七页，共173页。本

章

小

结

本章讨论在不允许失真前提下对信源的编码，分为两种情况，等长编码和变长编码。等长编码定理和变长编码定理分别给出了这两种情况，在无失真和码长尽可能短这两个约束条件下的平均码长的上界和下界。等长编码定理

记H（X）为单符号信源熵，L为扩展信源输出序列长度，n为码字长度，D为码符号集元素个数，当满足条件，则L→∞时，可使译码差错pe<δ(ε、δ为无穷小量)；反之，当时，则不可能实现无差错编码。变长编码定理(Shannon第一定理)记H（X）为单符号信源熵，L为扩展信源输出的序列长度，为信源每个符号所对应的平均码字数，D为码符号集元素个数，则对信源进行编码，总可以找到一种惟一可译码，使码长满足第一百三十八页，共173页。平均码长

克拉夫特不等式

本章还介绍了常见的三种变长码的编码方法：香农编码法、Fano编码法和霍夫曼编码法。对于同一信源的编码，三种方法中，以霍夫曼编码的编码效率最高。香农编码法没有太多实用价值，但它在证明变长编码定理时起了重要作用，Fano编码法是遵照变长编码定理（香农第一定理）的指导思想导出的一种编码方法。

第一百三十九页，共173页。作业：书P3.18第一百四十页，共173页。复习上次课的内容：编码器码的分类等长编码定理变长编码定理(Shannon第一定理)变长码的编码方法第一百四十一页，共173页。复习上次课的内容：第一百四十二页，共173页。码的分类

1.二元码：若码符号集为{0，1}，则码字就是二元序列，称为二元码；2.等长码：码中所有码字的长度，都相同；3.变长码：码中的码字长短不一；4.奇异码：若一组码中有相同的码字，则称为奇异码；5.非奇异码：若一组码中所有码字都不相同。6.原码C的N次扩展码7.惟一可译码：如果码的任意N次扩展码都是非奇异码，则称该码为惟一可译码。8.即时码:无需考虑后续的码符号就可以从码符号序列中译出码字，这样的唯一可译码称为即时码。9.同价码：每个码符号所占的传输时间都相同的码。10.分组码将信源符号集中的每个信源符号固定地映射成一个码字Wi，这样的码称为分组码。第一百四十三页，共173页。第一百四十四页，共173页。第一百四十五页，共173页。定理3.1

等长编码定理

设离散无记忆信源S={x1

，x2

，…，xk}的熵为H（X），S的L维扩展信源为，对信源输出的L长序列si，i=1,2,…,KL进行等长编码，码字是长度为n的D进制符号串，当满足条件，则L→∞时，可