第2章无失真信源编码

第2章无失真信源编码2.1信息量、熵和互信息量2.2信源编码定理2.3霍夫曼码及其他编码方法2.4算术编码2.5游程编码2.6改进的霍夫曼码2.7通用编码2.1信息量、熵和互信息量由于信源发出的消息是不确定的，只有当信源发出的消息通过信道传输给收方信宿后，才能消除不确定性并获得信息。事件发生的不确定性与事件发生的概率有关。事件发生的概率越小，猜测它有没有发生的困难程度就越大，不确定性就越大；而事件发生的概率越大，猜测这事件发生的可能性就越大，不确定性就越小。对于发生概率等于1的必然事件，就不存在不确定性。也就是说，信源发生的概率越小，一旦它出现必然使人感到意外，给人的信息量就越大；当消息的概率很小，即几乎不可能的消息出现了，则会给人以巨大的信息量。反之，消息出现的概率很大，一旦出现人们不会感到意外，所以给人的信息量就很小，对必然出现的信息，则不具任何信息量，从数学理论知对数函数就有上述特征。因此给出如下的信息量定义。给出一个离散信源：其中p（ui）为ui出现概率，且如果消息ui已发生，则ui包含的自信息量为（2―1）式中：p（ui）——ui发生的先验概率；I（ui

）——ui发生所含信息量。自信息量的单位与所用对数底有关。在信息论中常用的对数底是2，信息量的单位是比特（bit），即：I(ui)＝－lbp（ui

）（比特）；若取自然对数e为底，则信息量的单位为奈特（nat），即：I(ui)＝－lnp（ui

）（奈特）；若以10为对数底，则信息量的单位为笛特（det），即I(ui)＝－lgp（ui

）（笛特）。这三个信息量单位之间的转换关系如下：1bit≈0.693nat≈0.301det如果p（ui）＝0.5,则由式（2―1）得I（ui）＝1bit。所以1比特信息量就是两个互不相容的等可能事件之一发生时所提供的信息量。在这里，比特是指抽象的信息量单位，与计算机术语中“比特”的含义有所不同。当事件ui发生前，其自信息量I(ui)表示事件发生的不确定性；当事件ui发生后，其自信息量I(ui)表示事件所能提供的信息量。自信息量是针对信源发出的某一个消息而言所得出的信息量，不同的消息对应不同的自信息量。自信息量I(ui)是一个随机变量，其中任何一个消息的自信息量都代表不了信源所包含的平均自信息量。不能作为整个信源的信息测度，因此定义自信息量的数学期望为信源的平均自信息量，即：(2―2)这个平均自信息量的表达式和统计物理学中热熵的表达式很相似。在统计物理学中，热熵是一个物理系统杂乱性（无序性）的度量。这在概念上也有相似之处。因而就借用“熵”这个词把平均自信息量H（U）称为“信息熵”。信息熵的单位由自信息量的单位决定，即取决于对数底的选取，今后如不特殊说明，信息熵的单位为比特。信源的信息熵是从整个信源的统计特性来考虑的，它是从平均意义上来表征信源的总体信息测度的。对于某特定的信源（概率空间给定），其信息熵是一个特定的值。不同的信源因统计特性不同，其熵也不同。信息熵用以表征信息源的平均不确定性，平均自信息量是消除信源不确定性时所需信息的量度，即收到一个信源符号，全部解除了这个符号的不确定性。或者说获得这样大的信息量后，信源不确定性就被消除了。信息熵和平均自信息量两者在数值上相等，但含义不同。某一信源，不管它是否输出符号，只要这些符号具有某些概率特性，就必有信源的熵值；这熵值在总体平均上才有意义，因而是一个确定的值。而另一方面，信息量则只有当信源输出的符号被接收者收到后才有意义，信息量就是给予接收者的信息度量，该值本身可以是随机量，也可以与接收者的情况有关。因此说信息熵是信源的平均不确定性的描述，一般情况下它并不等于平均获得的信息量。只是在无噪情况下，接收者才能正确无误地接收到信源所发出的信息，消除了信息熵H（U）值大小的平均不确定性，所以获得的平均信息量就等于信息熵H（U）的值。在一般情况下获得的信息量是两熵之差，并不是信息熵本身。信息熵是信源输出的信息量，是信源包含的平均信息量，或信息的平均不确定性，而真正被接收者收到的信息是互信息。它是与收发双方都有关系的相对量，是指接收者从信源发送者中所获得的信息量。设信道输入为其中p（xi）为xi出现概率,i＝１,２,…,n。信道输出为其中p（yj）为yj出现概率，j＝１,２,…,m。由于收方信宿事先不知道信源在某一时刻发出的是哪一个符号，所以每个符号消息是一个随机事件。通常信宿可以预先知道信源X发出的各个消息的集合，以及它们的概率分布，即预知信源X的先验概率p（xi）。信息熵H（X）是在接收到Y以前，关于X的先验不确定性的度量，是X中某一个符号（事件）出现所必须提供的信息量，所以称为先验熵。如果信道中无干扰（噪声），信道输出符号与输入符号一一对应，那么，接收到传送过来的符号就消除了对发送符号的先验不确定性。但一般信道中有干扰（噪声）存在，接收到Y后对发送的是什么符号仍有不确定性。那么，怎样来度量接收到Y后关于X的不确定性呢？下面讨论这个问题。收到一个消息yj（yj∈{y1,y2,…,ym}）后，信宿可以计算各消息条件概率p（xi|yj），i＝１，２，３，…，n，xi∈{x1,x2,…，xn}，这种条件概率称为后验概率。因此，收到一个yj后关于X的平均不确定性为

(2―3)这是接收到yj后关于X的后验熵。可见，后验熵是当信道接收端接收到符号yj后，关于输入符号的信息测度。但式（２―３）所考虑的仅是输出端接收到Y中一种符号yj，所以这个后验熵对接收码Y求统计平均的条件熵为(2―4)式(2―4)表示，在信道输出端收到输出Y的全部符号后，对于信道输入端输入的X尚存在的不确定性（存在疑义），称这个条件熵为信道疑义度。对X尚存在的这个不确定性是由于干扰（噪声）引起的。如果是一一对应信道，那么接收到输出Y后，对X的不确定性将完全消除，则信道疑义度H（X|Y）＝0。由于条件熵小于无条件熵，即有H（X|Y）<H（X）。这正说明接收到Y的所有符号后，关于输入X的平均不确定性将减小，即总能消除一些关于输入X的不确定性，从而获得了一些信息。可见信息熵H（X）代表接收到输出符号以前关于输入X的平均不确定性，而H（X|Y）代表接收到所有输出符号后关于输入X的平均不确定性。通过信道传输消除了一些不确定性，获得了一定的信息。所以定义信道输入X和信道输出Y之间平均互信息量为I（X；Y）＝H（X）－H（X|Y）

(2―5)式中：I（X；Y）——信道输入X和信道输出Y之间的互信息量；H（X）——信道输入X的信息熵；H（X|Y）——收到所有输出符号后关于输入X的平均不确定性。可见，X和Y之间的互信息代表接收到输出符号后平均每个符号获得的关于X的信息量，也表明了输入X和输出Y之间的统计约束程度。根据H（X）和H（X|Y）定义得：

(2―6)式中，x∈{x1,x2,…，xn}；y∈{y1,y2,…,ym}。若X与Y独立，则I（X；Y）＝0，这时收不到关于X的任何信息，说明干扰很大。当收到y（y∈{y1,y2,…,ym}）时给出的关于x(x∈{x1,x2,…，xn})的信息量I（x；y）定义为

(2―7)互信息量可取正值也可取负值，如果互信息量I（x；y）取负值，说明在未收到消息y以前对消息x是否出现的猜测难疑程度较小。但由于噪声的存在，接收到消息y后，反而使接收者对消息x是否出现的猜测难疑程度增加了。也就是收到消息y后对x出现的不确定性反而增加，所以获得的信息量为负值。因为p（xy）＝p（x）p（y|x）＝p（y）p（x|y）这表明一对消息可以互相提供相等的信息量。所以称I（x；y）为x与y之间的互信息量。平均互信息量I（X；Y）是互信息量I（x；y）的统计平均值，所以平均互信息量I（X；Y）永远不会取负值。最差情况是I（X；Y）＝0，说明收到Y后不能获得任何关于X的信息量。由式（2―5）可推得：I（X；Y）

＝H（X）-H（X|Y）

＝H（Y）-H（Y|X）＝I（Y；X）

＝H（X）＋H（Y）-H（XY）（2―8）式中：因为H（X）是X所包含的平均信息量，或X中消息（符号）的平均不确定性，或消息集X中某一个消息（或符号）出现所必须提供的信息量，而H（X|Y）是当接收到Y时给出的关于X的不确定性。由式H（X|Y）＝H（X）－I（X；Y）可知，当收到Y时使X的不确定性减小了I（X；Y），这意味着接收到Y后，所获得的关于X的信息量是I（X；Y）。由H（X）＝I（X；Y）＋H（X|Y）可知，X的信息熵等于接收到的信息量I（X；Y）加上损失掉的信息量H（X|Y）。因为条件熵H（X|Y）是由于信道上存在干扰和噪声而损失掉的平均信息量，也叫损失熵。

由于损失掉这一部分信息量，故再要惟一的确定信源发出的信息，就显得信息量不足。条件熵H（X|Y）又可以看作信道上的干扰和噪声所造成的对信源符号X的平均不确定性。所以互信息量I（X；Y）是有扰离散信道上能传输的平均信息量，而条件熵H（X|Y）是在收到Y的条件下要惟一的确定信源发出符号所需要的平均信息量。式H（Y）＝H（Y|X）＋I（X；Y）表明，接收码Y的熵H（Y）等于接收到关于X的信息量I（X；Y）加上H（Y|X）。这完全是由于信道中噪声引起的，

故称H（Y|X）表示在已知X条件下，对Y存在不确定性，反映了信道中噪声源的不确定性。如果X与Y是相互独立的，因为收到Y时给出关于X的条件概率等于无条件概率，又因为熵就是该条件概率的对数的数学期望，所以X的条件熵就等于X的无条件熵，此时I（X；Y）＝0。这可理解为既然X与Y相互独立，无法从Y中提取关于X的信息。这可看成信道上噪声相当大，以至有H（X|Y）＝H（X）。在这种条件下，传输的平均的信息量为零，这说明收到符号y后不能提供有关信源发出符号x的任何信息量。对于这种信道，信源发出的信息量在信道上全部损失掉了，故称为全损离散信道。当X与Y有一一对应关系时，即X与Y满足确定函数关系时，条件概率必为0，也就是说I（X；Y）＝H（X），可见此时收到Y就完全解除了关于X的不确定性，所获得的信息就是X的不确定性或熵。这可看成无扰离散信道，由于没有噪声，所以信道不损失信息量，此时信道疑义度H（X|Y）＝0。于是有I（X；Y）＝H（X）＝H（Y）。在一般情况下，X与Y既非相互独立，也不是一一对应，那么从Y获得X的信息必在零与H（X）之间，即常小于X的熵。关于熵和互信息量等的更多知识请参阅有关文献。2.2信源编码定理若接收端信宿要求无失真精确的复制信源输出的消息，这时信源编码是无失真编码。只有对离散信源可以实现无失真编码，而对连续信源由于其输出量为无限大，因此不可能实现无失真的信源编码。离散信源的无失真编码实质上是一种统计匹配编码。统计匹配编码是根据信源的不同概率分布而选用与之相匹配的编码，以便达到在系统中传送速率最小，且满足在信宿复制时无失真或低于某一允许的失真限度值。

2.2.1信源编码的基本概念信源编码是指将信源输出符号，经信源编码器编码后变换成另外的压缩符号，然后将压缩后信息经信道传送给信宿。为了简化问题，研究无失真编码时，只考虑信源和信宿两个主要因素，忽略信道编、译码等的影响，这样通信系统模型变为图2―1所示。图2―1通信系统模型设图2―1编码器输入为S＝（s1,…,sl,…,sL）,sl∈{u1,u2,…,un}编码器输出的码字为X=(x1,…,xk,…,xK),xk∈{b1,b2,…,bm}可见，信源编码就是从信源符号到码符号的一种映射；译码是从码符号到信源符号的映射。

若要实现无失真编码，这种映射必须是一一对应的，可逆的。下面给出一些码的定义。若码集为{0，1}，所得码字为二元序列，则称为二元码(也叫二进制码)。二元码是数字通信和计算机系统中最常用的一种码。若一组码中所有码字的码长都相同，称为等长码。例如，信源符号U＝{u1，u2，u3，u4}，对应不同码字如表2―1所示。表2―1信源U对应的不同码字表2―1中码1的编码为等长码，其他的几种编码皆为变长码。表2―1中的码3有两个符号的编码相同，这样的编码叫奇异码，否则称为非奇异码。即奇异码是有相同码字的一种编码；非奇异码是一组码中所有码字都不同的编码。表2―1中的码1、码2和码4都为非奇异码。任意有限长的码元系列，只能被惟一的分割成一个个的码字，便称为惟一可译码。例如，码字{0，10，11}是一种惟一可译码。因为任意一串有限长码序列，例如100111000，只能被分割成10，0，11，10，0，0。任何其他分割法都会产生一些非定义的码字。显然，奇异码不是惟一可译码，而非奇异码中有非惟一可译码和惟一可译码。惟一可译码中又分为非即时码和即时码；如果接收端收到一个完整的码字后，不能立即译码，还需等收到下一个码字后才能判断是否可以译码，这样的码叫做非即时码。表2―1中,码2是非即时码，而码4是即时码。码4中只要收到符号1就表示该码字已完整，可以立即译码。即时码又称为非延长码。其中任意一个码字都不是其他码字的前缀部分，这种码称为异前缀码。表2―1中的码1和码4都是异前缀码。在惟一可译变长码中，需要的是在译码时无需参考后续的码符号就能立即做出判断的一类即时码。异前缀码一定是即时码，这可以直接从即时码的定义得出。事实上，如果没有一个码字是其他码字的前缀，则在译码过程中，当收到一个完整码字的码符号序列时，就能直接把它译成对应的信源符号，无需等待下一个符号到达后才作判断。反之，非异前缀码一定不是即时码。设码中有一些码字，例如码字Cj是另一码字Ci的前缀。收到的码符号序列正好是Cj时，它可能是码字Cj，也可能是码字Ci的前缀部分，因此不能立即作出判断，译出相应的信源符号来，必须等待其后一些符号的到达，才能做出正确判断。即时码一定是惟一可译码，反之惟一可译码不一定是即时码。因为有些非即时码（延长码）也具有惟一可译性。树图法是构造即时码的一种简单方法。树是n个结点的集合，这n个结点中有且仅有一个作为根的结点，其余的结点可分为m个互不相交的子集，每个子集本身又是一棵树，称为根的子树，也叫根的树枝数。图2―2（a）中，结点A为树根，它的树枝数为2，结点B的树枝数为3。图2―2树结构图一个结点拥有的子树的个数称为该结点的度（Degree）；一棵树的度是指该树中结点的最大度数。度为零的结点称为叶子（Leaf）或终端结点。图2―2（a）中，结点A，B，E的度分别为2，3，0；树的度为3；D，E，F，H，I，J和K均为叶子。度不为零的结点称为分支结点或非终端结点，除根结点之外的分支结点统称为内部结点，根结点又称为开始结点。从一个结点到另一个结点之间的通路叫两个结点间的路径，路径所经过的边（即连接两个结点的线段）的数目，叫路径长度。

图2―2（a）中结点A到结点I的路径是ACGI，路径长度为3。如果树中各个结点有相同的树枝数，且每层结点数达到最大值，此树称为满树，否则称为非满树。图2―2（b）所示为满树，（a）和（c）为非满树。可用树图对信源符号进行编码。下面给出树图与信源符号编码之间的对应关系：树根码字的起点树的度码元数分支结点码的符号的一部分终端结点待编码符号满树等长码非满树变长码用于编码时，树图又称为码树。用码树进行信源符号编码时，将待编码的字符作为终端结点，构造码树；然后按一定规则给每个树枝分配一个标记；最后将从根到终端结点的路径上的标号依次相连，作为该终端结点所表示的字符的编码。图2―3给出了几种码树图。图（a）对应等长二元码，图（b）对应变长二元码，图（c）对应变长三元码。信源各个符号对应的码字如图2―3所示。利用该图可以求出信源序列的编码。若信源序列为bacabd，则对应二元变长码（图2―3（b）编码）的码字序列为100110010111。码树既可用于信源符号的编码，也可用于译码。当接收到一串码符号序列后，首先从树根出发，根据接收到的第一个码字符号来选择应走的第一条路径。若沿着所选路径走到分支结点，再根据收到的第二个码符号来选择应走的第二条路经，如此下去，直至走到终端结点为止。最后，根据所走路径，可立即判断出接收到的码符号。使系统重新返到树根，再作下一个接收码符号的判断，如此下去，就可以将接收到的一串码符号序列译成对应的信源符号序列。对图2―3（b）所示编码树，若收到的码符号序列为100110010111，则按上述方法可译出信源符号序列为bacabd；若码符号序列为100111110，可译出对应信源符号序列为badc。图2―3码树图2.2.2变长码若要实现无失真编码，不但要求信源符号与每个符号的码字是一一对应的，而且要求码符号序列与信源符号序列也是一一对应的。也就是说，任意一串有限长的码符号序列只能被惟一的译成对应的信源符号序列，满足这种条件的码称为惟一可译码。如果所编的码不具有惟一可译性，就会在译码中引起错误与失真。对等长码，要做到无失真，必须取足够大数量的符号一起编码，这显然是不现实的，如果采用变长码，情况则完全不一样。下面先给出定长编码定理，然后说明为什么研究变长码及变长码特点。

定理2―1

（等长信源编码定理）

一个熵为

的离散无记忆信源，若对信源长为N的符号序列进行等长编码，设码字是从m个字母的码符号集中选取L个码元组成。对于任意ε>0，只要满足：

（2―9）则当N足够大时，几乎可实现无失真编码，即译码错误概率能为任意小。反之，若（2―10）则不可能实现无失真编码，而当N足够大时，译码错误概率近似等于1。对该定理的严格证明请参阅有关参考文献。为了衡量编码效果，定义编码信息率：

(2―11)式中：L——码长；m——码元数；N——信源序列长度;R′——编码后平均每个信源符号能载荷的最大信息量。

定义等长编码效率η：式中：H（U）——信源熵。由定理2―1可知，最佳等长编码效率η为(2―1２)(2―13)对等长编码，若要实现几乎无失真编码，则信源长度必满足:（2―14）式中：

σ2——信源方差；H(U)——信源熵；η——编码效率；

Pe——差错率。

式（2―14）给出了在已知方差和信源熵条件下，信源序列长度N与最佳编码效率和允许错误率之间的关系。可见，编码效率越高，允许错误率越小，则信源序列长度N越长。在实际情况下，要实现几乎无失真的等长编码，N需要大到难以实现的程度。下面举例说明。

【例2―1】

设离散无记忆信源:信源熵：方差：若取差错率Pe＝10－6，编码效率为95%，则可计算出等长编码需联合的信源符号数N应满足：可见，在差错率和编码效率要求并不十分苛刻的条件下，就需要近100万个信源符号进行联合编码，这显然是很难实现的。若对例2―1用变长码实现（具体编码方法及、η公式在后面介绍），则符号u1

u2

u3

u4码字010110111信源熵：平均码长：编码效率：可见，若采用变长码，其效率可达100％。这虽然是一个特例，但一般情况下变长码的编码效率都很高，它优于等长编码。实际上，一般离散无记忆信源输出的各消息（符号）的概率是不相等的。对出现概率大的信源符号采用较短的码字；而对出现概率小的信源符号采用较长的码字。这样，从整个信源来看，编成的信源码字的平均码长最短，它也实现了与信源统计特性相匹配。这就是变长码的基本思想。那么为什么要使平均码长最短呢？下面讨论此问题。设信源为编码后各码字的码长分别为：l1,l2,…，ln,则定义码字的平均码长度为码符号/信源符号(2―15)平均码长是每个信源符号平均需用的码元数。信源编码的目的是为了提高通信系统的有效性，而和编码后的压缩效果密切相关。平均码长大，则压缩效果差，系统有效性差；若平均码长小，则压缩效果好，系统有效性高。为此，我们感兴趣的是平均码长最短的编码，这种编码可使通信系统更经济、简单，使信息传输效率更高。当信源给定时，信源的熵H（U）就确定了，编码后每个信源符号的平均码元数为，那么平均每个码元携带的信息量，即编码后信道的信息传输率为比特/码符号(2―16)若传输一个码符号平均需要ｔ秒，则编码后信道每秒钟传输的信息量为比特/秒(2―17)由此可见平均码长越短，Rt越大，信息传输效率就越高，为此我们感兴趣的码是平均码长最短的码。另外，变长码一般不能直接由信道来传送，为了适应信道，必须有缓冲设备，将码符号暂存于缓冲设备中，若平均码长大，则编码后需存储的信息就多，需要的存储器的容量就大，反之，若平均码长最短，则需要存储的信息量就最少，这时可使通信系统更经济。对于某一信源和某一码符号集来说，若有一个惟一可译码，其平均长度小于所有其他惟一可译码的平均长度，则该码称为紧致码，或称最佳码。无失真信源编码的基本问题就是要找最佳码。那么，平均码长有没有极限值，如果有，它的值又是多少呢？这个问题将在2.2.4节中介绍。下面讨论变长码的缺点和需采取的措施。1．使信道复杂化一般情况下，信源符号以恒速输出，信源输出经变长编码后，输出的每秒比特数就不是常量，因而不能直接由信道来传送。为了适应信道，必须有缓冲设备，将编码输出暂存在缓冲器中，然后再送到信道去传送。从理论上说，信道传送速率应等于信源输出速率S与平均码长的乘积。就是当存储器容量为无限时，信源输出与信道传送之间取得平衡。在时间趋向于无限时，信源输出的比特数和信道上传送比特数接近相等。2．容易产生溢出或取空错误根据前面分析，当存储器容量无限时，信源输出与信道传送之间取得平衡。当存储器容量有限时，这种平衡不一定能保持。如当信源连续输出低概率符号时，由于每个符号的码长较长，输入到存储器的比特数将大于信道能输出的比特数，可能使存储器存不下而溢出；反之，若高概率符号连续出现，输入比特数将小于信道中传送的比特数，以致存储器被取空，信道上将无信息可传送。这两种情况都会造成不良后果。前者可使信息由于溢出而丢失，后者由于取空而使信道上出现连0或连1，在译码时会误译，也造成差错。所以应估计所需存储器容量，才能使上述现象发生的概率小至可以容忍。

一般的说，变长码只适用于有限长的信息传送，也就是送出一段信息后，信源能停止输出，如传真机送出一张纸以上的信息后就停止。对于长信息，在实际使用时可把长信息分段发送，也可检测存储器状态，发现将要溢出就停止信源输出，发现将要取空就插入空闲标志在信道上传送，或加快信源输出。3．差错的扩散

因为采用异前缀码来分解码字，一旦在传送中出现误码，某个码字的前缀部分可能成为另一个码字，因而错译为另一符号，而剩下部分又与后面码字的一部分译成某一符号。这样下去，可能要经过一段信息被错译后，才能正确分离码字。克服这种缺点的措施是力求信道不出误码，如采用纠错或检错编码。尤其是检错重发方式，设计得好可基本上不出差错或差错小到可容忍的程度。检错可用附加监督位的方式,也可在编码时有意识地不编成满树,某些树叶不用来代表某个符号,一旦这种码字出现在接收端,说明传送中有误码,可要求发端重发。变长编码具有很高的编码效率，有时几乎接近于1，但上述缺点限制了它的应用范围。采用变长码时,常需有大容量的存储设备作为缓冲，这也有利于重发。近来存储器发展很快，不但容量越来越大，价格也越来越低，这会使变长码应用范围不断扩大。2.2.3克拉夫特（Kraft）不等式变长码有很多优点，但真正使用时，又会遇到难题，这就是由于编成的码字是不等长度的，将它传送至接收端，如何进行辨认。对等长码，接收端只要根据约定的码组长度进行判决即可。对变长码，由于编成的码长度是不一样的，无法根据码组长度进行判决。如何克服并解决这一难题，是采用变长码时应解决的主要问题。解决它一般有两种方法，一种是类似于莫尔斯电报方法，码字间留空隙，或者加同步信号，但这种方法不经济，直接影响译码效率；另一种是采用可分离码字。

异前缀码是一种实时的惟一可译码，这类码无需另加同步信息，就能在接收端被分离出来。在信源编码和数据压缩中这类编码无论在理论还是在实际中都有很大意义，对较简单的信源，可以很方便地用码树法直接且直观地构造出可分离码（异前缀码），但是当信源较复杂，直接画码树就比较复杂。针对这一问题，在数学上给出一个与码树等效的，表达码字可分离的充要条件，即著名的克拉夫特不等式。定理2―2

对于码长分别为l1,l2，…，ln的m元码，若此码为即时码，则必定满足(2―18)反之，若码长满足不等式（2―18），则一定存在具有这样码长的即时码。不等式（2―18）是1949年由L.G.Kraft提出的，所以称克拉夫特（Kraft）不等式。克拉夫特不等式指出即时码的码长必须满足的条件。后来在1956年，麦克米伦（B.McMillan）证明惟一可译码也满足此不等式，1961年卡拉什（J.karuSh)简化了麦克米伦的证明方法。这说明惟一可译码在码长的选择上并不比即时码有什么更宽松的条件，而是惟一可译码的码长也必须满足克拉夫特不等式，所以在码长选择的条件上，即时码与惟一可译码是一致的。下面给出克拉夫特不等式的证明。证明设任意即时码C对应码长分别为l1,l2，…，ln。因为任意即时码都可以用码树来描述，则即时码C一定可以用m元码树来表示。从码树看，第N阶所有可能伸出树枝数为mN。当某第i（i＜N）阶结点作为码字，即码长li＝i0，它将影响到第N阶所伸出树枝。它使第N阶不能伸出的树枝数为

。因为共有n个码字，每个码字作为树终端结点后，都会影响第N阶所伸出树枝。假设N≥maxli(i＝1,2,3,…,n)，则n个码字影响第N阶总共不能伸出的树枝为（2―19）这些总共不能伸出树枝数必小于或等于第N阶所有可能伸出树枝数，所以有整理得定理充分性的证明可参见相关参考文献。克拉夫特不等式给出了m元码字中，信源序列中的消息数（符号数）n以及码字的各个码长li（i＝1，2，…，n）之间的关系。如果二者满足式（2―18），则至少能够构成一种这样码长的即时码，即时码是惟一可译码。否则，无法构成惟一可译码。如表2―1中，m＝2，n＝4。对码1有l1＝2,l2＝2,l3＝2,l4＝2，则满足式（2―18），则此码长的编码是惟一可译码。对码2有l1＝1,l2＝2,l3＝2,l4＝2，则不满足式（2―18），则此码长的编码不能构成惟一可译码。对码4有l1＝1,l2＝2,l3＝3,l4＝4，则满足式（2―18），则此码长的编码是惟一可译码。2.2.4信源编码定理由前面讨论可知，用变长码实现无失真编码时，平均码长越短越好，那么平均码长的极限是多少？下面的定理将回答这个问题。

定理2―3

若一个离散无记忆信源U的熵为H（U），每个信源符号用m码元进行变长编码，则总可找到一种无失真编码方法，构成惟一可译码，使其平均码长满足：(2―20)此编码定理给出了最佳变长码的平均码长的上限和下限。定理表明码字的平均长度不能小于极限H(U)/lbm，否则惟一可译码不存在；该定理还给出了最佳码的最短平均码长，并指出这个最短的平均码长与信源熵是有关的。在尚未编出码字之前就知道平均码长落在什么范围，这当然是很重要的。该定理指出，最佳变长码应是与信源熵相匹配的编码，其下限更重要，因为它是信源压缩编码的极限。我们通常称达到下限的最佳变长码为熵编码。定理的证明参见有关文献。

定理2―4

无失真变长信源编码定理（香农第一定理）。离散无记忆信源U的N次扩展信源UN＝{α1,α2,…，αNn}，其熵为H(UN)，并有码符号

X＝{x1,x2，…，xm}，对信源UN进行编码，总可以找到一种编码方法，构成惟一可译码，使信源U中每个信源符号所需的平均码长满足：

或者(2―21)(2―22)当N→∞时，则得式中：式中：(2―23)而λi是αi所对应的码字长度，因此，是无记忆扩展信源UN中每个符号αi的平均码长，可见

仍是信源U中每一单个信源符号所需的平均码长。的含义是为了得到这个平均值，不是对单个信源符号ui进行编码，而是对N个信源符号的序列αi进行编码。定理2―4指出，要做到无失真的信源编码，对每个信源符号编码平均所需最少的码元数m就是信源的熵值。若编码的平均码长小于信源的熵值，则惟一可译码不存在。变长编码后平均每个信源符号能载荷的最大信息量为（2―24）式中：

——N次扩展信源的平均码长；m——码元数。

这时，香农第一定理也可陈述为：若R′>H（U），就存在惟一可译变长编码；若R′<H（U），惟一可译变长码不存在，不能实现无失真的信源编码。若从信道角度看，当平均码长达到极限值H（U）/lbm时，根据式（2-16）可得编码后的信道的信息传输率为R＝lbm,比特/码符号

由此可见，这时信道的信息传输率等于无噪无损信道的信道容量，信息传输效率最高。

因此，无失真信源编码的实质就是对离散信源进行适当的变换，使变换后新的码符号信源（信道的输入信源）尽可能为等概率分布，以使新信源的每个码符号平均所包含的信息量达到最大，从而使信道的信息传输率和信道容量相等，实现信源与信道理想的统计匹配，这也是香农第一定理的物理意义。无失真信源编码定理通常又称为无噪信道编码定理。此定理可以表述为：若信道的信息传输率不大于信道容量，总能对信源的输出进行适当的编码，使得在无噪无损信道上能无差错地以最大信息传输率传输信息；但要使信道的信息传输率大于信道容量而无差错的传输信息是不可能的。下面讨论变长码达到极限的情况。设对信源U进行编码所得到的平均码长，因为一定大于或者等于Hm(U)，所以定义编码的效率η为

(2―25)η小于或等于1。对同一信源来说，若码的平均码长越短，越接近极限值Hr（U），信道的信息传输率就越高，就越接近无噪无损信道容量，这时η也越接近于1，所以可用码的效率η来衡量各种信源编码的优劣。另外，为了衡量各种编码与最佳码的差距，定义码剩余度为(2―26)在二元无噪无损信道中m＝2，所以Hm(U)＝H(U)，式（2―25）为所以在二元无噪无损信道中信息传输率为注意式中R与η数值相同，单位不同，其中η是个无单位的比值。2.2.5统计匹配码

从信源编码定理可以看出，离散无失真编码实质上是一种统计匹配编码，是根据信源符号的不同概率分布分配与之相对应码字，对出现概率大的符号分配短的码字，对出现概率小的符号分配长的码字，这样可使信源符号的平均码长最短，从而保证通信系统的有效性。那么，如果不考虑信源的统计特性，能否做到有效且无失真呢？下面讨论这个问题。编码器输入为S=（s1,…,sl,…,sL）,sl∈{u1,u2,…,un}编码器输出的码字为X＝(x1,…,xk,…,xK),xk∈{b1,b2,…,bm}

要实现无失真信源编码，必须同时满足无失真和有效性两个条件。如果不考虑信源统计特性，若要满足无失真，就必须使每个信源输出的消息（或符号）都能找到一个对应的码字，即满足：mK≥nL

(2―27)若取m＝n，由式（2―27）得K≥L说明码序列的长度大于信源序列长度，显然不满足有效性。若选K＝L，由式（2―27）得m≥n这显然不满足无失真。所以若先考虑有效性，则无失真得不到满足。要想同时满足上述两个基本条件的要求，惟一办法是从信源统计特性上去考虑。由式（2―27）得

(2―28)式（2―28）中的logan和logam分列是不考虑信源统计特性或等概率条件下消息熵H（U）＝logan与码熵H（X）＝logam。当考虑信源的统计特性时，信源符号一般是不等概率的，这时消息熵H（U）为将其代入式（2―28）得：(2―29)2.3霍夫曼码及其他编码方法无失真的信源编码定理，既是存在性定理也是构造性定理，即它给出了构造信源编码的原理性方法，这样构造出的码的平均码长与信源统计特性相匹配。为此，香农、费诺、霍夫曼都各自按上述思路设计出不同的具体编码方法，其中霍夫曼给出的方法最好。本节将介绍这些具体的编码方法。2.3.1霍夫曼(Huffman)码1952年，霍夫曼提出了一种构造最佳码的方法，它是一种逐个符号的编码方法。所得的码字是异前缀码的变长码，其平均码长最短，是最佳变长码，又称霍夫曼码。二元霍夫曼码编码步骤如下：(1)将n个信源U的各个符号ui按概率分布p（ui）以递减次序排列起来。(2)将两个概率最小的信源符号合并成一个新符号，新符号的值为两个信源符号值的和，从而得到只包含n－1个符号的新信源，称为U信源的缩减信源U1。(3)把缩减信源U1的符号仍按概率以递减次序排列，然后将其中两个概率最小的符号合并成一个符号，这样又形成了n－2个符号的缩减信源U2。(4)依次继续下去，直至信源最后只剩下１个符号为止。(5)将每次合并的两个信源符号分别用0和1码符号表示。(6)从最后一级缩减信源开始，向前返回，就得出各信源符号所对应的码符号序列，即得各信源符号对应的码字。【例２―２】

离散无记忆信源:对应的霍夫曼编码如图２―４所示。图2―4例2―2霍夫曼编码信源熵:平均码长：编码效率：

【例2―3】

离散无记忆信源:的两种霍夫曼编码如图2―5所示。这两种方法对应的霍夫曼树分别如图2―6(a)、(b)所示。图2―5例2―3两种霍夫曼编码图2―5例2―3两种霍夫曼编码

图2―6例2―3对应码树例2―3中（a）、（b）两种方案的霍夫曼编码平均码长都为信源熵为编码效率为两种码有相同的平均码长，有相同的编码效率，但每个信源符号的码长却不相同，其均方差也不同。下面分别计算两种码的均方差σ2，即：(方法(a)方差)(方法(b)方差)可见，方法（a）的方差比方法（b）的方差要小许多。方法(a）的具体编码原则是，把合并后的概率总是放在其他相同概率的信源符号之上（或之左），方法（b）的编码原则是，把合并后的概率放在其他相同概率的信源符号之下（或之右）。从上面的分析可以看出，方法（a）要优于方法（b）。2.3.2m元霍夫曼码前面讨论的二元霍夫曼码的编码方法可以推广到m元编码中。不同的只是每次把概率最小的m个符号合并成一个新的信源符号，并分别用0，1，…，（m－1）等码元表示。为了使短码得到充分利用，使平均码长最短，必须使最后一步的缩减信源有m个信源符号。因此对于m元编码，信源U符号个数n必须满足：n＝（m－1）Q＋m（2―30）式中：n——信源符号个数；m——进制数（码元数）；Q——缩减次数。对于二元码，总能找到一个Q，满足式（2―30）。但对于m元码，n为任意正整数时不一定能找到一个Q满足式（2―30），此时，可以人为地增加一些概率为零的符号，以满足式（2―30）。然后取概率最小的m个符号合并成一个新符号（结点），并把这些符号的概率相加作为该结点的概率，重新按概率由大到小顺序排队，再取概率最小的m个符号（结点）合并；如此下去直至树根。下面给出m元霍夫曼编码步骤：(1)验证所给n是否满足式（2―30），若不满足该式，可以人为地增加一些概率为零的符号，以使最后一步有m个信源符号；(2)取概率最小的m个符号合并成一个新结点，并分别用0，1，…，（m－１）给各分支赋值,把这些符号的概率相加作为该新结点的概率；(3)将新结点和剩下结点重新排队，重复（2），如此下去直至树根。(4)取树根到叶子（信源符号对应结点）的各树枝上的赋值，得到各符号码字。后来新加的概率为零的符号，虽也赋予码字，实际上这是冗余码字，并未用上，但这样编成的码，仍是最佳的，也就是平均码长最短，如果等概率符号排队时注意到顺序，则码长的方差也是最小的。【例2―4】

已知离散无记忆信源其三元霍夫曼编码如图2―7所示，四元霍夫曼编码如图2―8所示。下面计算例2―4的编码效率。图2.7例2―4三元霍夫曼编码图2―8例2―4四元霍夫曼编码信源熵：两种编码的平均码长分别为因为lb3＝1.58bit,lb4＝2bit，所以其编码效率分别为可见，要发挥霍夫曼编码的优势，一般情况下，信源符号集的元数应远大于码元数。对例2―4中，若编五元码，只能对每个信源符号赋予一个码数，等于没有编码，当然无压缩可言。那么，什么样的编码能获得最佳的压缩效果呢？下面讨论这个问题。图2―92.3.3霍夫曼码的最佳性设信源U中每个符号ui(ui∈｛u1，u2，…，un})的频度为fi，码长为li，则表示编码后的信源总长。有时并非每次压缩都去统计各字符在文件中出现的频度，而是通过对定义在相同字符集上的大量文件进行统计分析，得出每个字符ui的概率p（ui），此时的表示平均码长。将使或最小的即时编码称为最佳码。所谓最佳码，就是指对于某个给定信源，在所有可能的惟一可译码中，此码的平均码长最短。另外霍夫曼编码可由霍夫曼树构造，平均码长（或文件总长）是霍夫曼树的带权路径长度。由于霍夫曼树是权最小的树，因此霍夫曼编码的平均码长亦最小，霍夫曼码是最佳码。最优的前缀码对文件的压缩效果亦最佳。霍夫曼编码的特点之一是高频先见。霍夫曼的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，即

p（uj）>p（uk），有lj≤lk。这是现代编码的基础，是汉字编码的简码设计原则，也是动态高频优选的原则。符号集中的任一字符的码字都不是其他字符编码的前缀，可直接用于译码，所以霍夫曼码是即时码。2.3.4费诺（Fano)编码费诺编码属于统计匹配编码，但它不是最佳的编码方法。其编码步骤如下：(1)将信源消息（符号）按其出现的概率由大到小依次排列；(2)将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近于相同，并对各组分别赋予一个二进制码元“0”和“1”。(3)将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率之和近于相同，并又分别赋予一个二进制符号“0”和“1”。(4)如此重复，直至每个组只剩下一个信源符号为止。(5)信源符号所对应的码字即为费诺码。【例2―5】

离散无记忆信源的费诺编码如图2―9所示。信源熵：平均码长：【例2―6】

离散无记忆信源编码效率：的费诺编码如图2―10所示。图2―10例2―6费诺编码图信源熵：平均码长：编码效率：【例2―7】

已知离散无记忆信源的费诺编码如图2―11所示。由上述分析可见，费诺码考虑了信源的统计特性，使经常出现的信源符号能对应码长短的码字。显然，费诺码仍然是一种相当好的编码方法。但是，这种编码方法不一定能使短码得到充分利用。尤其当信源符号较多，并有一些符号概率分布很接近时，分两大组的组合方法就很多。可能某种分配结果，会出现后面小组的“概率和”相差较远，因而使平均码长增加，所以费诺码不一定是最佳码。费诺码的编码方法实际上是构造码树的一种方法，所以费诺码是一种即时码。图2―11例2―7费诺编码图

2.3.5香农―费诺―埃利斯码香农―费诺―埃利斯码不是分组码，它根据信源符号的积累概率分配码字，不是最佳码，但它的编码和译码效率都很高。设信源为定义信源符号积累概率为(2―31)由信源符号积累概率定义可知，和F(uk)都是小于1的正数，可将这些小于1的正数映射到区间（0，1］内，图2―12描绘了积累概率分布。图2―12积累概率分布图可见，符号的积累概率函数呈级跃形，符号的积累概率的值是上界值，每个台级的高度（或宽度）就是该符号的概率p(uk)值，修正的积累概率对应台级的中点。因为所有的积累概率F(uk)都是正数，且当ui≠uj时，F(ui)≠F(uj),所以这些积累概率F(ui)将区间（0，1］分成许多互不重叠的小区间。若知道了，就能确定其处在哪个小区间，就能确定相应的信源符号uk,所以可采用的数值作为符号uk的码字。那么，这样给出的符号的编码是即时码吗？码长又如何选取呢？下面讨论这些问题。

一般情况下，为一实数，将其转换成二进制小数的形式，取小数点后l(uk)位作为uk的码字。根据二进制小数截去位数的影响得：（2―33）式中：——取l(uk)位小于等于的最大整数。若取(2―34)式中：［X］——取大于或等于X的最小整数。得：

(2―35)(2―36)则这样编得的码字在信源符号uk对应的区间内。上面证明了将转化为二进制数的形式，取小数点后l(uk)位作为符号uk的码字，此码字恰好在符uk对应的区间内。那么，这样得到的码字是即时码吗？从F(uk)划分的区间看，若每个信源符号uk所对应的区间都没有重叠，那么，此编码一定是即时码。由式（2―34）可得香农―费诺―埃利斯码平均码长为则：

(2―37)【例2―8】

离散无记忆信源的香农―费诺―埃利斯码编码如表2―2所示。表2―2例2―8香农―费诺―埃利斯码码表信源熵：平均码长：编码效率：【例2―9】

离散无记忆信源的香农―费诺―埃利斯码编码如表2―3所示。此编码比霍夫曼码每位信源符号多1.2位码元。表2―3例2―9香农―费诺―埃利斯码码表前面讨论了信源编码原理及各种编码方法。霍夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，而且所有短码得到充分利用；且每次缩减信源的最后两个码字总是最后一位不同，前面各位相同，这两个特点保证了所得的霍夫曼码一定是最佳码。对信源的N次扩展信源同样可以采用霍夫曼编码方法，因为霍夫曼码是最佳码，所以编码后单个信源符号所编得的平均码长随N的增加很快接近于极限值——信源的熵。费诺码不一定是最佳码，但有时也可获得最佳的编码效果。费诺码也是统计匹配码，但这种方法不一定能使短码得到充分利用。用这种编码方法得到码字是即时码。费诺编码方法同样适合于m元编码，只需每次分成m组即可。香农―费诺―埃利斯码不是最佳码，但由它扩展而得到的算术编码，在数据压缩中得到了广泛的应用。2.4算

术

编

码用霍夫曼编码方法对小消息信源进行编码，要实现统计匹配，提高编码效率，必须扩展信源，即由一维扩展至多维进行霍夫曼编码时，才能使平均码长接近信源的熵,二元序列用二元码编码,等于没有编码,也无压缩而言,且编码效率也不高。例如，设二元序列中两个符号概率分别为

p（a）＝0.7,p(b)＝0.3,其信源熵为平均码长:编码效率:要想提高二元信源的编码效率，可以用合并信源符号的办法扩展符号集，若进行二次扩展,即取2个相邻符号作为新符号编霍夫曼码。二次扩展的一种霍夫曼码如表2―4所示。

表2―4二元信源二次扩展平均码长：编码效率:

表2―5二元信源三次扩展若进行三次扩展,即取3个相邻符号作为新符号编霍夫曼码。三次扩展的一种霍夫曼码如表2―5所示。三次扩展的编码效率η＝96.9%。可见,合并的信源符号越多，编码效率越高，但扩展阶次越高，系统延时越长、存储量越大、设备也越复杂，合并的符号数达到一定值时，再增加符号数所提高的效率将不显著，所以工程上只能在效率与经济性之间作合理的选择。另外,算术编码就比较适合二元信源，这种方法主要是对信源序列进行编码,并且可达到很好的压缩效果。

2.4.1积累概率的递推公式设信源：定义信源符号的积累概率：（2―38）由（2―38）式可知：F（uk）∈［0，1)由（2―38）式得:F（u1）＝0，F（u2）＝p（u1），

F（u3）＝p（u1）＋p（u2），…且p（ui）＝F（ui＋1）－F（ui）因为F（ui）和F（ui＋1）都是小于1的正数，因此可用［0，1）区间的两个点来表示，p（ui）就是这两点间小区间的长度。不同的符号对应不同的小区间，这些小区间互不重叠，小区间内的任意的一个点可作为该符号的码字，且此编码为即时码。下面给出信源序列的积累概率的递推公式，其证明可见相关的参考文献。设独立信源序列：S=s1s2…sk，…,sn∈{u1,u2,…,um},k＝1，2，…，n则信源序列的积累概率的递推公式：F(Sur)=F(S)+p(S)F(ur)p(Sur)=p(S)p(ur)式中：F（Sur）——

信源序列S添加一个新的信源符号ur后所得到的新序列Sur的积累概率；（2―39）p（S）——信源序列S的概率；F（ur）——信源符号ur的积累概率；p（Sur）——信源序列S添加一个新的信源符号ur后所得到的新序列Sur的概率；p（ur）——信源符号ur的概率。公式（2―39）对于有相关性的序列同样适用，只是需要将公式中的单符号概率改成条件概率。信源序列的积累概率F（S）与信源符号的积累概率一样，可用［0，1）区间内的一个点来表示，因此积累概率F（S）将区间［0，1）分成许多不同的小区间，它们互不重叠，序列S的概率p（S）就是两点间小区间的长度。小区间内的一个点可用来表示序列的概率，这就是算术编码的基本思想。2.4.2算术编码原理由前面的讨论可知，信源符号的积累概率将区间［0，1）分成许多互不重叠的小区间，每个信源符号对应一个不同的小区间。每个小区间的长度等于这个信源符号的概率，在此小区间内取一点，该点的取值可作为这个信源符号的码字。这个原理同样适用于信源序列。把信源序列的积累概率映射到［0，1）区间上，使每个序列对应该区间内的一个点，这些点把区间［0，1)分成许多不同的小区间，这些小区间的长度等于对应序列的概率，在小区间内取一个浮点小数，使其长度与该序列的概率相匹配，因而达到高效编码的目的。

算术编码的主要任务是计算信源序列对应的小区间。下面先给出小区间划分的递推计算公式,然后举例说明如何划分小区间。设小区间左、右端点的值分别用low和high表示，用range表示小区间的长度，则小区间左、右端点的递推公式：low(Sur)=low(S)+range(S)×low(ur)high(Srr)=low(S)+range(S)×high(ur)（2―40）式中：low（Sur）——

信源序列S添加一个新符号ur后所得到的新序列Sur对应区间的左端点值；high（Sur）——

信源序列S添加一个新信源符号ur后所得到的新序列Sur对应区间的右端点值；low（S）——信源序列S对应区间的左端点值；range（S）——信源序列S对应区间的宽度值；low（ur）——信源符号ur对应区间的左端点值；high（ur）——信源符号ur对应区间的右端点值。使用公式（2―40）计算小区间端点值的步骤：(1)给出信源符号对应的区间；(2)初始时设S＝（代表空集），low（）＝0，high（）＝1，range（）＝1；(3)输入信源序列的一个符号ur，根据公式（2―40）计算序列Sur的左右端点值。依次下去，直至全部信源序列对应的区间被确定为止。【例2―10】

设信源求信源序列S=abda对应的小区间。各个信源符号对应的小区间如表2―6所示。表2―6例2―10信源符号对应区间端点值不同的信源符号分别对应不同的小区间,哪个符号被设在哪个区段并不重要,也就是说不需要各符号按概率顺序排列,只要编码和译码都以同样的方式进行就可以。信源序列S=abda对应的小区间的左、右端点的值如表2―7所示。表2―7例2―10信源序列对应区间的端点值表2―7信源序列abda对应区间的端点值的计算：设low（）＝0，high（）＝1，range（）＝1；输入信源序列的第1个符号a：

low（a）＝low（）＋range（）×low（a）＝0＋1×0＝0.000high（a）＝low（）＋range（）×high（a）＝0＋1×0.5＝0.500输入信源序列的第2个符号b：

low（ab）＝low（a）＋range（a）×low（b）＝0.00＋0.5×0.5＝0.250high（ab）＝low（a）＋range（a）×high（b）＝0.00＋0.5×0.75＝0.375输入信源序列的第3个符号d：

low（abd）＝low（ab）＋range（ab）×low（d）＝0.25＋0.875×0.125＝0.359375high（abd）＝low（ab）＋range（ab）×high（d）＝0.25＋0.125×1＝0.375输入信源序列的第4个符号a：

low（abda）＝low（abd）＋range（abd）×low（a）＝0.359375high（abda）＝low（abd）＋range（abd）×high（a）＝0.3671875信源序列S=abda对应区间的划分如图2―13所示。图2―13例2―10信源序列对应区间的划分不同的信源序列分别对应不同的互不重叠的小区间,取小区间内的一个点作为对应序列的编码,此码是即时码。根据上述分析，可取0.359375作为信源序列S=abda的编码。译码是编码的逆过程，就是根据接收到的码字翻译出对应的信源序列。

译码步骤：(1)判断码字落在哪个符号区间，翻译出1个符号；(2)将码字减去刚翻译出的符号的左端点值；(3)用刚翻译出的符号对应的区间的长度去除步骤2的结果，判断此值落在哪个符号区间，翻译出一个新符号；(4)重复步骤(2)、(3)直至全部信源序列被翻译完为止。下面以码字0.359375为例,说明译码过程。码字0.359375落在［0，0.5）之间,即0.359375∈［0，0.5），于是翻译出第1个符号为a；用符号a对应区间的长度0.5去除码字与符号a的左端点值的差得0.71875,即(0.359375－0)/０.5＝0.71875∈［0.5,0.75］,则翻译出第2个符号为b；用符号b对应区间的长度0.25去除码字0.71875与符号b的左端点值的差得0.875,于是翻译出第3个符号为d；用符号d对应区间的长度0.125去除码字0.875与符号d的左端点值的差得0,码字0落在［0，0.5）之间,即0∈［0,0.5),于是翻译出第4个