信息论与编码第2.ppt

,第2章无失真信源编码原理,2.1离散信源及其信息测度 2.2信源编码的基本概念 2.3惟一可译码 2.4信源变长编码 2.5统计匹配码,2.1离散信源及其信息测度 2.1.1信源概述 1消息、信号和信息信源的输出被称做消息(message)，消息一般不能被直接传输，需要经过发送器的变换才能转换成适于信道传输的信号(signal)。消息和信号的这种区别对信息传输系统来讲是有一定意义的。,在一般情况下，消息和信号既是相互区别的，又是相互联系的。一方面，消息和信号的定义与含义不同。当信源的输出连同语义学上的意义一并加以理解时则称为消息。例如，播音员播送的一段新闻，记者拍摄的一段录像，歌手演唱的一首歌曲等，都应该说是消息。而当信源的输出只被看做是随时间变化的某一物理量f（t）或随时间、空间位置变化的某一物理量f（x，y，t）时，则称为信号。另一方面，信源的输出在收到、看到、听到之前都是随机的、不确定的，属于随机现象。因此，从信息论的观点来看，信源的输出无论是被看做消息，还是被看做信号，它均含有信息。,消息、信号和信息这三者都可以说是信源的输出，或者说它们是信源输出的三个方面。由于信息论关心的是信源输出的信息，因此可将信源称为信息源。通常，统计信息论是不研究消息、信号和信息三个方面在语义学上的意义的，它只考虑信源输出的后两个方面，即信号和信息。应该说，信号是信息的载体和具体表达形式，信息必须借助信号才能得以表现，信息不能离开信号而单独存在。所以，研究信源就是要研究信号和信息的关系，特别是信号如何才能有效地携带信息。,2信源的分类按信号取值的集合和信号取值时刻的集合是离散的或连续的进行分类，信源可分为数字信源(DigitalSource)或离散信源(DiscreteSource)、模拟信源(AnalogSource)或波形信源(WaveformSource)、连续信源(ContinuousSource)。,信源输出的信息从数学角度来看就是一种随机过程。有些信源输出的是单个符号(或代码)的消息，它们符号集的取值是有限的或可数的，即可用一维离散型随机变量来描述这些信源的输出，这样的信源称为离散信源。在实际情况中，存在着很多这样的信源。例如投硬币、书信文字、计算机的代码、电报符号、阿拉伯数字码等等。当我们掷一个六面质地均匀的骰子时，每次出现朝上一面的点数都是随机的，如把出现朝上一面的点数作为这个随机试验的结果，并把试验的结果看做信源的输出消息，无可置疑，这个随机试验可看做是一个信源。这个信源输出有限种离散数字，其组成的集合为A=1，2，3，4，5，6，而且每一个数字代表一个完整的消息，,所以，这个信源是单符号离散信源。有的信源输出的虽是单个符号(或代码)的消息，但其可能出现的消息数是不可数的或无限的，即输出消息的符号集的取值是连续的，或取值范围是实数集(-，+)。例如，语音信号、热噪声信号等某时间的连续取值数据，以及遥控系统中有关电压、温度、压力等测得的连续数据。这些数据取值虽是连续的，但又是随机的，可用一维的连续型随机变量来描述这些消息，所以这种信源可称为连续信源。,若信源只输出一个消息(符号)，则用一维随机变量来描述。然而，很多实际信源输出的消息往往是由一系列符号序列所组成的。例如，将中文自然语言文字作为信源，这时中文信源的样本空间是所有汉字与标点符号的集合。由这些汉字和标点符号组成的序列即构成中文句子和文章。因此，从时间上看，中文信源输出的消息是时间上离散的符号序列，其中每个符号的出现是不确定的、随机的，由此构成了不同的中文消息。又例如，对离散化的平面灰度图像信源来说，从XY平面空间上来看每幅画面是一系列空间离散的灰度值符号，而空间每一点的符号（灰度值）又都是随机的，由此形成了不同的图像消息。,这类信源输出的消息是按一定概率选取的符号序列,所以可以把这种信源输出的消息看做时间上或空间上离散的一系列随机变量，即随机矢量。这样，信源的输出可用N维随机矢量来描述，这N维随机矢量有时也称为随机序列，其中，N可为有限正整数或可数的无限值。若在信源输出的随机序列XX1X2XN中，每个随机变量Xi(i=1,2,N)都是取值离散的离散型随机变量，即每个随机变量Xi的可能取值是有限的或可数的,而且随机变量X的各维概率分布都与时间起点无关，也就是在任意两个不同时刻，随机变量的各维概率分布都相同，这样的信源称为离散平稳信源。前面所述的中文自然语言文字与离散化平面灰度图像都是这种离散型平稳信源。,若信源输出的消息可用N维随机序列XX1X2XN来描述，其中每个随机分量Xi(i=1,2,N)都是取值为连续的连续型随机变量(即Xi的可能取值是不可数或无限的)，并且满足随机变量X的各维概率密度函数与时间起点无关，也就是在任意两个不同时刻随机变量X的各维概率密度函数都相同，这样的信源称为连续平稳信源。例如，语音信号与热噪声信号，它们在时间上取样离散化后的信源输出矢量在时间上是离散的，但输出矢量中的随机变量的取值都是连续的，所以它们是连续型平稳信源。,某些简单的离散平稳信源先后发出的一个个符号是统计独立的。也就是说，在信源输出的随机序列XX1X2XN中，各随机变量Xi(i=1,2,N)之间是无依赖的、统计独立的，这样的信源称为离散无记忆信源。该信源在不同时刻发出的各符号之间也是无依赖的、统计独立的。离散无记忆信源输出的随机变量X所描述的信源称为离散无记忆信源的N次扩展信源。可见，N次扩展信源是由离散无记忆信源输出N长的随机序列构成的信源。一般情况下，信源在不同时刻发出的各符号之间是相互依赖的，也就是在信源输出的平稳随机序列XX1X2XN中,各随机变量Xi之间是相互依赖的。,例如，在汉字组成的序列中，只有根据中文的语法、习惯用语、修辞制约和表达实际意义的制约所构成的中文序列才是有意义的句子或文章。所以，在汉字序列中前后文字的出现是有依赖的，不能认为是彼此不相关的，其他如英文、德文等自然语言都是如此，将这种信源称为有记忆信源。对这类信源需要在N维随机矢量的联合概率分布中引入条件概率分布来说明它们之间的关联。,表述有记忆信源要比表述无记忆信源困难得多。实际上，信源发出的符号往往只与前若干个符号的依赖关系强，而与其更前面的符号依赖关系弱，为此，可以限制随机序列的记忆长度。当记忆长度为m+1时，称这种有记忆信源为m阶马尔可夫信源。也就是信源每次发出的符号只与前m个符号有关，与更前面的符号无关。假设m阶马尔可夫信源输出的随机序列为XX1X2Xi-1XiXi+1XN。在这序列中某i时刻的随机变量Xi取什么符号只与前m个随机变量Xi-1Xi-2Xi-m取什么符号有关，而与其更前面的随机变量以及后面的随机变量取什么符号都无关。,这样，就可用马尔可夫链来描述此信源。如果描述随机序列中各随机变量之间依赖关系的条件概率都与时间起点i无关，即信源输出的符号序列可看成时齐马尔可夫链，则此信源称为时齐马尔可夫信源。,一般来说，实际信源输出的消息常常是时间和取值都是连续的，如语音信号、热噪声信号和电视图像信号等时间连续函数。同时，在某一固定时间，它们的可能取值又是连续的和随机的。这种信源输出的消息可用随机过程来描述，所以称其为随机波形信源。分析一般随机波形信源的过程比较复杂和困难。常见的随机波形信源输出的消息是时间上或频率上为有限的随机过程。根据取样定理，只要是时间上或频率上受限的随机过程，都可以把随机过程用一系列时间(或频率)域上离散的取样值来表示，而每个取样值都是连续型随机变量。这样，就可把随机过程转换成时间(或频率)上离散的随机序列来处理。甚至在某种条件下可以转换成随机变量间统计独立的随机序列。如果随机过程是平稳的随机过程，时间离散化后可转换成平稳的随机序列。这样，随机波信源可以转换成连续平稳信源来处理。若再对每个取样值(连续型的)经过分层(量化)，就可将连续的取值转换成有限的或可数的离散值。也就可把连续信源转换成离散信源来处理。,2.1.2信源的数学模型根据信源输出信息所对应的不同的随机过程可以导出不同的信源模型。例如，根据随机过程具有的随机变量前后独立与否可分为独立随机信源(或称无记忆信源)和不独立随机信源(或称有记忆信源)；根据随机过程平稳与否可分为平稳(稳恒)信源和非平稳(非稳恒)信源。与特殊的随机过程相对应又有特殊的信源模型，例如，与高斯过程相对应的高斯信源，与马尔可夫过程相对应的马尔可夫信源等,其中，马尔可夫信源是有记忆信源中最简单且最具代表性的一种。信源的类型不同其对应的模型也不同，限于篇幅，这里只介绍基本离散信源的数学模型及其无记忆扩展信源的数学模型。,在信息传输系统中收信者在未收到消息以前，对信源发出什么消息是不确定的和随机的，所以可用随机变量、随机矢量或随机过程来描述信源输出的消息。或者说,用一个样本空间及其概率测度，也就是概率空间来描述信源。,一个基本离散信源的数学模型,（2-1）,【例21】随机掷一个六面质地均匀的骰子，每次出现朝上一面的点数与其概率分布为,式（21）描述了信源基本特征，即一个信源符号就代表一个完整的消息,这样的信源也叫单符号离散信源。但实际信源发出的消息往往不止一个符号，而是由多个符号的时间(或空间)序列组成的。由多个符号组成的时间(或空间)序列称为多符号离散信源。设序列由N个符号组成,且先后发出的符号间彼此统计独立,这样的多符号离散信源可看做离散无记忆信源的N次扩展信源，其数学模型为N维概率空间。,由信源U的信源空间可得信源U的N次扩展信源的信源空间为,（2-2）,例2-2 已知二元信源,分别计算信源U的2次扩展信源及3次扩展信源模型。解由式（22）可得信源U的2次扩展信源的模型为,同理，由式（22）可得信源的3次扩展信源的模型为,2.1.3自信息量信息论不研究信源的内部结构，不研究信源为什么产生和怎样产生各种不同的、可能的消息，而只研究信源的各种可能的输出，以及输出各种可能消息的不确定性。由于信源发出的消息是不确定的，只有当信源发出的消息通过信道传输给信宿后，才能消除不确定性并获得信息。事件发生的不确定性与事件发生的概率有关。事件发生的概率越小，猜测它有没有发生的困难程度就越大，不确定性也就越大；而事件发生的概率越大，猜测这事件发生的可能性就越大，不确定性也就越小。对于发生概率等于1的必然事件，就不存在不确定性。,1.自信息量自信息量是针对信源发出的某一个消息而言所得出的信息量，不同的消息对应不同的自信息。如果事件ui已发生，则信息ui包含的自信息量为,I(ui)logap（）,（2-3）,1bit0.693nat0.301det,2.联合自信息量式（2-3）的自信息量是针对一维空间的，可把它推广到二维空间,设概率空间X为：,（24）,设概率空间Y为,（25）,（2-6）,2.1.4 平均自信息量1.基本离散信源自信息量是针对信源发出的某一个消息而言所得出的信息量，不同的消息对应不同的自信息，自信息I(ui)是一个随机变量，其中任何一个消息的自信息都代表不了信源所包含的平均自信息量。不能作为整个信源的信息测度，因此定义基本离散信源自信息的数学期望为信源的平均自信息量，即：,(2-9),这个平均自信息量的表达式和统计物理学中“热熵”的表达式很相似。在统计物理学中，“热熵”是一个物理系统杂乱性（无序性）的度量，在概念上两者也有相似之处。因而就借用“熵”这个词把平均自信息量H（U）称为“信息熵”。信息熵的单位由自信息的单位决定，即取决于对数底的选取，当底分别为2、e、10时，信息熵的单位分别为比特(bit)、奈特(nat)/符号、笛特（det)/符号，今后如不特殊说明，信息熵的单位为比特/符号。,信源的信息熵是从整个信源的统计特性来考虑的，它是从平均意义上来表征信源的总体信息测度的。对于某特定的信源（概率空间给定），其信息熵是一个特定的值。不同的信源因统计特性不同，其熵也不同。信息熵是表征信息源的平均不确定性，平均自信息量是消除信源不确定性时所需的信息的量度，即收到一个信源符号可全部解除这个符号的不确定性。或者说，获得这样大的信息量后，信源不确定性就被消除了。信息熵和平均自信息量两者在数值上相等，但含义不同。某一信源，不管它是否输出符号，只要这些符号具有某些概率特性，必有信源的熵值；,同时，这个熵值在总体平均上才有意义，因而是一个确定的值。而另一方面，信息量则只有当信源输出的符号被接收者收到后才有意义，信息量就是给予接收者的信息度量，这值本身可以是随机量，也可以与接收者的情况有关。因此说信息熵是信源的平均不确定性的描述，一般情况下它并不等于平均获得信息量。只有在无噪情况下，接收者才能正确无误地接收到信源所发出的信息，从而消除了信息熵H（U）值大小的平均不确定性，因此所获得的平均信息量就等于信息熵H（U）的值。通常情况下获得的信息量是两熵之差，并不是信息熵本身。,例2-4 有一布袋内放100个球，其中70个球是红色的，30个球是白色的。若随机摸取一个球，猜测其颜色，求平均摸取一次所能获得的自信息量。解:设a1表示摸出的是红球；a2表示摸出的是白球,则这一随机事件的概率空间为,如果被告知摸出的是红球，那么获得的信息量是：,如果被告知摸出的是白球，那么获得的信息量是：,这样，平均摸取一次所能获得的信息量约为,(比特符号),例2-5有一离散无记忆信源U，其概率空间为,解由于信源U共有3个不同的消息符号，所以由信源U中每两个符号组成的不同排列共有32=9种，即二次扩展信源共有9个不同的符号。又因为信源U是无记忆的，则二次扩展信源的概率空间为,于是，得：,说明，此处单位中的“符号”是指扩展信源的输出符号它是由2个组成),说明：此处单位中的“符号”是指扩展信源的输出符号i,它由两个i组成。由此可得H(U2)=2H(U)。对于上述结论也可以直观地进行理解。因为扩展信源UN的每一个输出符号i是由N个i所组成的序列，并且序列中前后符号是统计独立的。现已知每个信源符号i含有的平均自信息量为H(U)，那么，N个i组成的无记忆序列平均含有的自信息量就为NH(U)(依据熵的可加性)。因此信源UN每个输出符号i含有的平均自信息量为NH(U)。,3.联合熵与条件熵信息熵讨论的是单个的概率空间不确定性的度量问题,当将此概率空间看做离散信源时，相当于讨论离散信源的平均信息含量。在实际应用中，常常需要考虑两个或两个以上的概率空间之间的关系，这就需要引入联合熵与条件熵的概念。在联合集XY上，每对元素xiyj的自信息量的概率加权平均值定义为联合熵（JointEntropy)。即,（211）,由式（27）和式（211）得：,（212）,在联合集XY上，条件自信息量I（xi|yj）的概率加权平均值定义为条件熵（ConditionalEntropy)。即,（2-13）,由式（2-8）和式（2-13）得,（2-14）,条件熵与联合熵的单位同自信息量一样。,2.1.5 平均互信息量信息熵H（X）代表接收到输出符号以前关于输入X的平均不确定性，而H（X|Y）代表接收到所有输出符号后关于输出X的平均不确定性。通过信道传输消除了一些不确定性，获得了一定的信息，所以定义信道输入X和信道输出Y之间平均互信息为：,I（X；Y）H（X）H（X|Y）H（Y）H（Y|X）H（X）H（Y）H（XY）,（215）,可见，X和Y之间的平均互信息量代表接收到输出符号后平均每个符号获得的关于X的信息量，也表明了输入X和输出Y之间的统计约束程度。平均互信息量具有如下性质：（1）交互性：I(X;Y)I（Y；X）；（2）非负性和极值性：0I(X;Y)min(H(X),H(Y)；（3）凸状性：I(X;Y)是信源P(X)的上凸函数（形凸函数），I(X;Y)是信道传递概率P(Y|X)的下凸函数（形凸函数）。,因为,因此和是随机变量X和Y之间相互提供的信息量，称互信息是全确切的。,因此,I(X;Y)和I(Y;X)是随机变量X和Y之间相互提供的信息量，称互信息量是完全确切的。由于H(X)H(X|Y),H(Y)H(Y|X)，于是由互信息量定义可得I(X;Y)0，由于H(X|Y)0，H(Y|X)0，又由互信息量定义可知I(X;Y)H(X),I(Y;X)H(Y)。于是可以得到I(X;Y)min(H(X),H(Y)，当随机变量X和Y之间统计独立时，有H(X|Y)=H(X),H(Y|X)=H(Y)，于是得到I(X;Y)=0。,当信道固定时，对于不同的信源概率分布，信道输出端获得的信息量是不同的。因此，对于每一个固定信道，一定存在一种概率信源(一种分布)，使输出端获得的信息量最大，即I(X；Y)是信源P(X)的上凸函数（形凸函数）；信源固定以后，用不同的信道来传输同一信源符号时，在信道输出端获得的信息量是不同的。对每一种信源一定存在一种最差的信道，此信道的干扰最大，而使输出端获得的信息量最小，即I(X;Y)是信道传递概率P(Y|X)的下凸函数（形凸函数）。,2.1.6各种熵之间的关系为了讨论各种熵之间的关系，首先需给出关于凸函数的一个结论。已知一个实值函数f，如果对任意x,yI都有,（2-16）,则称f在区间I上是凸的；如果对任意，都有式（2-16）中仅小于号成立，则称f为在区间I上是严格凸的。,（2-17）,进一步，式(2-17)中的等号成立当且仅当。容易证明，对数函数在区间上是一个连续的严格凸函数。,定理2-1,（2-18）,H（X）=0当且仅当存在一个xi(1in),有p(xi)=1，而对其他ji，有p(xj)=0，1jn。H(X)=lbn当且仅当对任意i(1in)，都有p(xi)=1/n。,证明根据H(X)的定义，H(X)0是显然的。如果H(X)=0，则对任意i(1in)，都有-p(xi)lbp(xi)=0。从而对任意i都有p(xi)=0或p(xi)=1。又因为,所以存在一个xi(1in)，有p(xi)=1，而对其他ji，有p(xj)=0(1jn)。根据Jensen不等式，有,进一步，若式中等号成立，当且仅当对任意i(1in)，都有p(xi)=1/n。,定理22,（2-19）,等号成立当且仅当X与Y相互独立。证明 因为,（220）,（221）,所以,由式(2-12)和Jensen不等式知,等号成立当且仅当对任意i,j(1in,1jm)，,c是一个常数。因为,（2-22）,所以c1，即对任意的i和j，p(xiyj)=p(xi）（yj)。因此，等号成立当且仅当X与Y相互独立。,定理23,（223）,证明,同理可证，。证毕。,推论2-1,（2-24）,由定理22和定理23可以立即得到此推论，等号成立当且仅当X与Y相互独立。,【例26】信源X,Y的概率空间分别为:,和,(x,y)联合分布如表21所示，求联合熵、条件熵及互信息量。,表21(x,y)联合分布,解由熵定义可得:,对于条件熵及互信息量有：,2.2信源编码的基本概念 2.2.1信源研究的内容对信息源或信源的研究一直是信息论研究的主要内容之一。信息论对信源研究的内容包括以下三个方面：1)信源的建模信源输出信号的数学描述已有成熟的理论，即随机过程，因此，可以说信源的建模在一定程度上也就是用恰当的随机过程来描述信号。然而，一般的随机过程理论并不涉及和讨论信号中所携带的信息，而信息论所关心的中心内容则是信号中所携带的信息。,2)信源输出信号中携带信息的效率的计算在信息论中，信源输出信号所携带信息的效率是用熵率或冗余度来表示的。3)信源输出信息的有效表示一般地，信源输出信号中携带信息的效率并不很高，如何用适当的信号有效地表示信源输出的信息才是人们感兴趣的问题，这就是有关信源编码的问题。在实际应用中，信源编码对信息的存储和传输两方面都有极大的价值。,2.2.2信源编码器信源编码是指，将信源输出符号经信源编码器编码后变换成另外的压缩符号，然后将压缩后的信息经信道传送给信宿。为了简化问题，研究无失真编码时，只考虑信源和信宿两个主要因素，忽略信道编、译码等的影响，这样信息传输系统模型可简化为图21所示的模型。,图21信息传输系统的简化模型,设信源U发出n种不同的符号，其符号集为U=u1,u2,un,其中 ui称为信源符号，若信源符号集中符号数等于2称为二元信源，等于3称为三元信源，等于n称为n元信源。又若信道的输人符号集为X=a1,a2,ar。信源编码问题,就是用信道的输人符号集X=a1,a2,ar作为码符号集，其中ai（i1，2，r）称为码符号或码元，用码符号集中的码符号,对信源U的每一种不同的符号进行一一对应变换，构成由码符号组成的序列，即码字。所有码字的集合称为码组w=w1，w2，wn；码字中所用的码符号的个数称为码长。,信息传输有时要求信道必须无失真地传递信源发出的每一种不同的符号，以及由信源符号的序列代表的每一种不同的消息，来实施无失真信息传输。要解决这个问题，当然首先要求信道是无噪信道。在无噪信道的前提条件下，必须进一步要求信源编码编出的每一种码字要与信源发出的每一种不同的符号一一对应，而且同时还要求信源的N个符号组成的序列所代表的消息，与之相对应的码字组成的码字序列也必须一一对应。只有这样，才能保证任何一个码字或码字序列唯一地翻译成相对应的信源符号或符号序列，达到无失真传递信源发出的消息的目的。无失真信源编码必须具有这种单义可译性,我们将单义可译的码称为单义可译码，也称为惟一可译码。由此可见，信源编码就是从信源符号到码符号的一种映射；译码是从码符号到信源符号的映射。若要实现无失真编码，这种映射必须是一一对应且可逆的。,2.2.3 码的类型 下面给出一些码的定义。若码符号集中符号数等于2称为二元码，等于3称为三元码，等于r称为r元码。二元码是数字通信和计算机系统中最常用一种码。若一组码中所有码字的码长都相同，称为等长码,否则称为变长码。若码组中所有码字都不相同则称为非奇异码，否则称为奇异码。例如，信源Uu1，u2，u3，u4，对应不同码字如表2-2所示。,表22信源U对应的不同码字,表22中码1的编码为等长码，其他的几种编码皆为变长码。码3有两个符号的编码相同，码3是奇异码，而码1、码2和码4都为非奇异码。若每个码符号的传输时间都相同,则称为同价码;否则称为非同价码。若码组的任意一串有限长的码符号只能被惟一地译成所对应的信源符号序列,则称为惟一可译码;否则称为非惟一可译码。例如，码字0，10，11是一种惟一可译码。因为任意一串有限长码序列，如100111000只能被分割成10，0，11，10，0，0。任何其他分割法都会产生一些非定义的码字。显然，奇异码不是惟一可译码，而非奇异码中有非惟一可译码和惟一可译码两种。,惟一可译码又分为非即时码和即时码。如果接收端收到一个完整的码字后，不能立即译码，还需等下一个码字开始接收后才能判断是否可以译码，这样的码叫做非即时码。表22中的码2是非即时码，而码4是即时码。码4中只要收到符号1就表示该码字已完整，可以立即译码。即时码又称为非延长码，若码组中没有任何完整的码字是其他码字的前缀，则称为异前缀码(或前缀条件码）。表22中的码1和码4都是前缀条件码。,表2-2 信源U对应的不同码字,在惟一可译变长码中，人们需要的是在译码时无需参考后续的码符号就能立即作出判断的一类即时码。前缀条件码一定是即时码，这可以直接由即时码的定义得出。事实上，如果没有一个码字是其他码字的前缀，那么在译码过程中，当收到一个完整码字的码符号序列，便能直接把它译成对应的信源符号，无需等待下一个符号到达后才作判断，这就是即时码。反之，非异前缀码一定不是即时码。设码中有一些码字，若码字Cj是另一码字Ci的前缀。当收到的码符号序列正好是Cj时，则它既可能是码字Cj,也可能是码字Ci的前缀部分，因此不能立即对其作出判断，译出相应的信源符号来，必须等待其后一些符号的到达，才能作出正确判断，所以这就不是即时码。即时码一定是惟一可译码，反之惟一可译码不一定是即时码，因为有些非即时码（延长码）也具有惟一可译性。,2.3惟一可译码 2.3.1Kraft不等式变长码有很多优点，但在真正使用时，往往又会遇到难题，这是由于编成的码字是不等长度的，将它传送至接收端时不能对其进行正确辨认所造成的。对等长码，接收端只要根据约定的码组长度进行判决即可，而对变长码，由于编成的码长度是不一样的，因此就无法根据码组长度进行判决。如何克服并解决这个难题，是变长码的主要矛盾。这个问题一般有两种方法可解决，一种是类似于莫尔斯电报方法，即在码字间留空隙，或者加同步信号，但这种方法不经济，它直接影响到译码的效率；另一种是采用可分离码字。,异前缀码是一种实时的惟一可译码，这类码无需另加同步信息，在接收端就能被分离出来。在信源编码和数据压缩中这类编码无论在理论还是在实际上都有很大意义，对较简单的信源，可以很方便地用码树方法直接且直观地构造出可分离码（异前缀码），但是当信源较复杂时，直接画码树就比较复杂。就这一问题，这里给出了一个与码树等效的，并在数学上表达码字可分离的充要条件，即著名的克拉夫特不等式。,定理2-4 对于n元信源编m元码，其码长分别为l1,l2，ln，则即时码存在的充要条件,(225),式（225）是1949年由L.G.Kraft提出的，所以称之为克拉夫特（Kraft）不等式，该不等式指出了即时码的码长必须满足的条件。在1956年，由麦克米伦（B.McMillan）证得对于惟一可译码也满足此不等式；在1961年,卡拉什（J.Karush)简化了麦克米伦的证明方法。这说明惟一可译码在码长的选择上并不比即时码有什么更宽松的条件，所以在码长选择的条件上，即时码与惟一可译码是一致的。,克拉夫特不等式给出了m元码中，信源序列中的消息数（符号数）n以及码字的各个码长li（i1，2，n）之间的关系。如果三者满足式（225），则至少能够构成一种这样码长的即时码或惟一可译码，否则无法构造出即时码或惟一可译码。但这个定理并不能作为判别一种码是否为即时码或惟一可译码的依据。例如，码组中有长度相等的两个码字，则这两个码字无论是否相同，都有可能使不等式成立，然而，当这两个码字相同时，它们一定不是惟一可译码。因此，惟一可译码一定满足克拉夫特不等式，反之，满足克拉夫特不等式的码不一定是惟一可译码。,例如在表22中，已知m2，n4。对码1,有l12,l22,l32,l42，则,满足式（225），则此码长的编码可能是惟一可译码。对码2有 l11,l22,l32,l42，则：,不满足式（2-25）则此码长的编码不能构成惟一可译码。,对码4,有l11,l22,l33,l44，则,满足式（225），则此码长的编码可能是惟一可译码。,2.3.2惟一可译码的判别准则惟一可译码的判断步骤如下：(1)观察是否是非奇异码。若是奇异码则一定不是惟一可译码。(2)计算是否满足克拉夫特不等式。若不满足则一定不是惟一可译码。(3)将码画成一棵树图，观察是否满足即时码的树图的构造，若满足则是惟一可译码。(4)用Sardinas和Patterson设计的判断准则。计算出码组中所有可能的尾随后缀集合F，观察F中有没有包含任一码字，若无则为惟一可译码；若有则一定不是惟一可译码。,在上述判断步骤中,Sardinas和Patterson设计的判断方法是能确切地判断出是否是惟一可译码的方法，所以可以跳过前三个步骤直接采用该判断准则。该准则是萨得纳斯(AASardinas)和彼得森(GWPatterson)于1957年设计出来的，具体内容如下所述：设S0为原始码字的集合,再构造一系列集合S1,S2,，Sn。为得到集合S1，首先分析S0中的所有码字。若码字Wj是码字Wi的前缀，即Wi=WjA，则将后缀A列为S1中的元素，S1就是由所有具有这种性质的A构成的集合。,一般地，要构成Sn(n1)，则将S0与Sn-1比较。若有码字WS0，且W是USn-1的前缀，即U=WA，则取后缀A为Sn中的元素；同样，若有码字USn-1是WS0的前缀，即W=UA，则后缀A，亦为n中的元素；如此便可构成集合n。依此类推，直至集合为空或者没有新的后缀产生为止。可见，一种码是惟一可译码的充要条件是S1,S2,，Sn中没有一个含有S0中的码字。,【例27】设消息集合共有7个元素x1,x2,x3,x4,x5,x6,x7，它们分别被编为a,c,ad，abb,bad,deb,bbcde码,判断其编码是否为惟一可译码？解按照Sardinas和Patterson设计的判断方法，可构造出如表23所列的码符号集序列。,表23码符号集序列,【例28】现有码110,11,100,00,10，判断其编码是否为惟一可译码？解按照Sardinas和Patterson设计的判断方法，可构造出如表24所列的码符号集序列。,表24码符号集序列,2.3.3即时码的树图构造树图法是构造即时码的一种简单方法。树是n个结点的集合，这n个结点中有且仅有一个作为根的结点，其余的结点可分为m个互不相交的子集，每个子集本身又是一棵树，称为根的子树，m也叫根的树枝数。如图22（a)中，结点A为树根，它的树枝数为2，结点B的树枝数为3。,图22树结构图,一个结点拥有的子树的个数称为该结点的度（Degree),一棵树的度是指该树中结点的最大度数。度为零的结点称为叶子（Leaf)或终端结点。如图22（a)中，结点A、B、E的度分别为2、3、0；树的度为3；D、E、F、H、I和J均为叶子。度不为零的结点称为分支结点或非终端结点，除根结点之外的分支结点统称为内部结点，根结点又称为开始结点。从一个结点到另一个结点之间的通路叫两个结点间路径，路径所经过的边（即连接两个结点的线段）的数目叫路径长度。图22（a)中结点A到结点I的路径是ACGI，路径长度为3。如果树中各个结点有相同的树枝数，此树称为满树，否则称为非满树。图22中（b)为满树，（a）和（c)都为非满树。下面给出树图与信源符号编码之间的对应关系：,构造树图的要点有以下两方面：(1)最上端为树根A，从根出发向下伸出树枝，树枝总数等于码符号数r，树枝的尽头为结点。(2)从每个结点再伸出r枝树枝，当某结点被安排为码字后，就不再伸枝，这个结点为终端结点。能再伸枝的结点称为中间结点。一直继续，直至都不能伸枝为止。,用码树进行信源符号编码时，先将待编码的字符作为终端结点来构造码树；然后按一定规则给每个树枝分配一个码符号；最后将从根到终端结点的路径上的码符号依次相连，作为该终端结点所表示的字符的编码。图23给出了几种码树图，图（a)对应等长二元码，图（b)对应变长二元码，图（c)对应变长三元码。各符号对应码字如图23所示。根据信源符号的编码可以求出信源序列的编码。若二元信源系列为bacabd，则对应二元变长码（图23（b)中的编码）码字序列为100110010111。,码树可用于信源符号的编码，也可用于译码。当接收到一串码符号序列后，首先从树根出发，根据接收到的第一个码字符号来选择应走的第一条路径，若沿着所选路径走到分支结点，再根据收到的第二个码符号来选择应走的第二条路径，直至走到终端结点为止。最后，根据所走路径，立即判断出所接收的符号。使系统重新返到树根，在作下一个接收码符号的判断，直至将接收到的一串码符号序列译成对应的信源符号序列。若图23（b)的编码树对应的码符号序列为100110010111，按上述方法可译出对应信源符号序列为bacabd；码符号序列为100111110，可译出对应信源符号序列为badc。,图23码树图,2.4信源变长编码 2.4.1等长码及其编码定理若等长码是非奇异码，则它的任意有限长N次扩展码一定也是非奇异码。因此等长非奇异码一定是惟一可译码。若对一个信源U进行等长编码，那么信源U存在惟一可译等长码的条件是：,（226）,式中：q信源U的符号个数；r码符号个数；l等长码的码长。,表25信源U的两种不同编码码字,信源U的N次扩展信源UN进行等长编码，若要使编得的等长码是惟一可译码，则必须满足:,（227）,对式（227）两边取对数，可得：,或,（2-28）,式中，l/N是平均每个信源符号所需要的码符号个数。该式表示对于等长惟一可译码，每个信源符号至少需要用lbqlbr个码符号来变换。,若N=1，则有,（229）,当r=2(二元码)时，lbr=1，则,（230）,例如，英文电报有32个符号(26个英文字母加上6个标点符号)，即q=32，若采用二元码时，则r=2。对信源U的逐个符号ui(i=1，2，32)进行二元编码，则有lbq=lb32=5，这就是说，每个英文电报符号至少要用5位二元符号编码。,定理25（等长信源编码定理）一个熵为H（U）的离散无记忆信源U，若用m元码对其N次扩展信源UN进行码长为L的等长编码。对于任意0，只要满足：,（231）,则当N足够大时，几乎可实现无失真编码，即译码错误概率能为任意小。反之，若,（232）,则不可能实现无失真编码，而当N足够大时，译码错误概率近似等于1。对该定理的严格证明请参阅有关参考文献。下面给出等长码的编码效率等公式。,设一个熵为H（U）的离散无记忆信源U，若用m元码对其N次扩展信源UN进行码长为L的等长编码。定义编码信息率R：,（比特/信源符号）,(233),R编码后平均每个信源符号能载荷最大信息量。,定义等长编码效率：,(234),由定理25可知，最佳等长编码效率为,0,(235),对等长编码，若要实现几乎无失真编码，则信源长度N必须满足；,（236）,式中：2信源U的方差；编码效率；Pe差错率。,【例29】设离散无记忆信源,信源熵：,方差：,若取差错率Pe106，编码效率为95%，则可计算出等长编码需联合的信源符号数N应满足：,可见，在差错率和编码效率要求并不十分苛刻的条件下，就需要近一百万个信源符号进行联合编码，这显然是没有必要实现的。若对例29用变长码来实现，其效率可达100。这虽然是一个特例，但是一般情况下变长码的编码效率都很高，要优于等长编码。,2.4.2变长码的平均码长及编码效率对式（21）基本离散信源进行编码，设编码后各码字的码长分别为l1,l2,，ln,则定义该码的平均码长度为,码符号/信源符号,(237),平均码长是每个信源符号平均需用的码元数。信源编码的目的是为了提高信息传输系统有效性，而和编码后的压缩效果密切相关，若平均码长大则压缩效果差，系统有效性差，若平均码长小则压缩效果好，系统有效性高，为此，人们感兴趣的码是平均码长最短码，这种编码可使信息传输系统更经济、简单，使信息传输效率更高。,当信源给定时，信源的熵H（U）就确定了，编码后每个信源符号的平均码元数为L，那么平均每个码元携带的信息量即编码后信道的信息传输率R为,(比特/码符号),(238),若传输一个码符号平均需要秒钟，则编码后信道每秒钟传输的信息量为：,(比特/秒),(239),设对信源U进行编码所得到的平均码长，因为一定大于或者等于Hm(U)(m元码的熵)，所以定义编码的效率为：,(240),式中：,(码符号/信源符号)；,(比特/信源符号)。,对同一信源来说，码的平均码长L越短，越接近极限值Hm（U），信道的信息传输率就越高，也就越接近无噪无损信道容量，这时的越接近于1。所以可用码的效率来衡量各种信源编码的优劣。另外，为了衡量各种编码与最佳码的差距，定义码的剩余度为,(241),在二元无噪无损信道中,m2，所以Hm(U)H(U)，式（240）为,（242）,所以在二元无噪无损信道中信息传输率为,（243）,注意:上式中R与的数值相同，单位不同，是个无单位的比值。为此，在二元信道中可直接用码的效率来衡量编码后的信息传输率是否提高了。当1，即R1(比特码符号)时，表明已达到了二元无噪无损信道的信道容量，其编码效率最高，码剩余度为零。,2.4.3变长码的特点1使信道复杂化一般情况下，信源符号以恒速输出。信源输出经变长编码后，其输出的每秒比特数就不是常量，因而不能直接由信道来传送。为了适应信道输出，必须有缓冲设备，将编码输出暂存在缓冲器中，然后再送到信道去传送。从理论上说，信道传送速率应等于信源输出速率S与平均码长的乘积。就是当存储器容量为无限时，信源输出与信道传送之间取得平衡。在时间趋向于无限时，信源输出的比特数和信道上传送比特数接近相等。,2容易产生溢出或取空错误根据前面分析可知，当存储器容量无限时，信源