第2章+信源编码技术.ppt

第2章信源编码技术,2.1信源编码的基本概念2.2无失真信源编码2.3限失真信源编码,2.1信源编码的基本概念,2.1.1引言在现代通信中,信源和信道是组成通信系统的最基本单元。信源是产生信息的源,信道则是传送载荷信息的信号所通过的通道,信源与信宿之间的通信是通过信道来实现的。度量通信的技术性能主要是从通信的数量与质量两个方面来考虑的,一般数量指标用有效性度量,而质量指标用可靠性度量。前者主要与信源的统计特性有关,而后者则主要与信道的统计特性有关。,以前,通信研究的重点是信道,主要研究的问题是通信的质量,即可靠性问题,这是非常必要的,但是它是不全面的。譬如：数字调制技术同时也要考虑有效性问题。从通信系统的优化观点来看,通信研究的另一个重点应是信源,它主要研究的问题是通信的数量,即有效性问题。只有同时研究通信的数量与质量、有效性和可靠性、信源和信道,才能使整个通信系统实现优化,达到既有效又可靠。可见,通信系统是信源与信道相配合的统一体,通信系统的优化应是寻求信源与信道之间最佳的统计匹配。,在本章中,将介绍信源编码的基本概念、无失真信源编码和限失真信源编码。在信源编码的基本概念方面,主要讨论信源的分类、信源的统计特性模型、信源的信息度量和信源编码的目的等问题。在无失真信源编码方面,主要介绍无失真信源编码的基本原理、哈夫曼编码、算术编码和游程编码。在限失真信源编码方面,主要介绍限失真信源编码的基本原理、连续信源的限失真信源编码（即连续模拟信源的PCM编码,它包括抽样、量化、编码等内容）和离散信源的限失真信源编码（重点为预测编码和变换编码）。,2.1.2信源的分类1.离散信源与连续信源信源可划分为两大类型：离散(或数字)信源和连续(或模拟)信源,其中文字、电报以及各类数据属于离散信源,而未经数字化的语音、图像则属于连续信源。离散信源或连续信源的输出则称为离散消息或连续消息。,2.单个消息信源与消息序列信源如果离散信源中仅含有一个消息(符号),而这个消息是一个不确定量,比如它可以是二进制数中的“0”或“1”,也可以是英文26个字母中的某一个字母,还可以是中文数千个单字中的某一个单字,则称它为单个消息（符号）信源。如果离散信源中含有多个消息(符号),并且每个消息都是一个不确定量,可以有多种取值,则称它为消息序列信源。消息序列信源可以认为是最基本的单个消息信源的组合,实际的离散信源多为消息序列信源。,3.无记忆信源与有记忆信源消息序列信源的输出可用符号序列X=（X1,Xl,XL）表示,其中X1是在第l时刻产生的符号（l为整数）,它是一随机变量,其取值范围为一有限字符集xi,i=1,2,n。如果符号序列中各X1相互统计独立,相应的信源就称为无记忆信源；如果符号序列中各X1相互统计关联,相应的信源就称为有记忆信源。实际信源常常是有记忆信源。4.简单信源如果无记忆信源中各X1服从同一概率分布,即对于任一X1,其取值为xi(i=1,2,n)的概率P(xi)都相同,且,则相应的信源就称为简单信源。,5.平稳信源和各态历经信源对于有记忆信源,需要用联合概率空间来描述,其概率分布为P(X1,Xl,XL)=(xi1,xil,xiL)=PX1=xi1,Xl=xi1,XL=xiL(2-1)式中,il=1,2,n。如果上述概率分布与随机变量X1的下标无关,即对于任意整数m有PX1=xi1,Xl=xi1,XL=xiL=PXm+1=xi1,Xm+l=xi1,Xm+L=xiL(2-2),则相应的有记忆信源就称为平稳信源。平稳信源可以理解为随机序列中的各消息统计特性与序列所处时间(位置)无关。当PX1=xi1,Xl=xi1,XL=xiL=PXl=xi1(2-3)时,就是简单无记忆信源。如果各Xl取值为任一xi(i=1,2,n)的概率P(xi)都相同,即有P(xi)=P(x2)=P(xi)=P(xn)=P(2-4),时,式(2-3)成为PX1=xi1,Xl=xi1,XL=xiL=PXl=xi1=PX1=xi1=PL(2-5)此时就是等概率无记忆信源。若信源输出的随机序列具有各态历经性（遍历性）,即可以从随机序列的一个样本序列估计出它的数字特征（均值和相关函数）,则相应的平稳信源就称为各态历经信源。,6.有限记忆信源和马尔可夫信源在有记忆信源中,若Xl的取值只与前面的有限个随机变量有关,则此时的有记忆信源称为有限记忆信源。可用条件概率分布P(XlXl-1,Xl-2,Xl-m)来描述有限记忆信源的统计特性,其中m为正整数,称为记忆阶数,相应的信源称为m阶记忆信源,m=1为一阶记忆信源,m=2为二阶记忆信源,依次类推。实际应用时,常用有限记忆信源去近似实际信源。若随机序列中任一个随机变量的取值只与前面的一个随机变量有关（m=1）,或者随机序列中任意连续K个随机变量组成的一个状态只与前面的连续K个随机变量组成的前一个状态统计关联,其统计特性可用马尔可夫链来描述,则相应的信源称为马尔可夫信源。,7.二进制信源和多进制信源随机变量的取值为两种状态时称为二进制信源,为多种状态时称为多进制信源。2.1.3信源的统计特性模型1.单个消息信源首先讨论最简单、最基本的单个消息信源。它一般可以采用单消息取值范围X以及消息取值xi的概率P(xi)来共同描述,表达式为X,P(xi),也可写成,(2-6),例如,对于离散、单消息的二进制等概率信源,可表示为同理,可给出单个连续变量信源的表达式为其中,p(x)表示具体取连续值x的概率密度。,(2-7),(2-8),2.消息序列信源实际信源是由上述最基本的单个消息信源组合而成的。离散时,它是一个消息序列,在数学描述上可写成一随机序列X=(X1,X1,XL),这就是说表达离散的实际信源的随机序列X具有两个重要特征：在横轴方向上它是由l=1,2,L个单个消息(符号)Xl构成的,在纵轴方向上每个消息(符号)X1都是一个随机变量,当Xl=xi(i=1,2,n)时,它有n种取值可能；连续时,它是一个模拟消息,在数学描述上可写成一随机过程X(,t)简记为X(t),其中(-,+),t(-T,+T)。对某一时刻t=ti,X(,ti)是一个取值为=kk(-,+)的连续随机变量。实际上,文字信源、数据信源以及数字化以后的语音与图像信源均可表达成离散消息序列信源；语音信源与图像信源等模拟信源均可表达成连续随机过程X(t)信源。,实践证明,只要满足限时、限数这类物理上可实现的基本条件,模拟信源就可以离散化为离散消息序列信源来表达。因此对于实际信源的统计描述,这里仅讨论消息序列信源。对于离散消息序列信源,也可以采用类似于对上述单个消息信源的描述方法。假设消息序列信源由L个消息(符号)构成,且消息序列中每个消息(符号)取值集合(范围)是相同的,用X表示,则消息序列信源的取值集合可以表示为XL=XXX(共计L个X)(2-9),这时,信源输出是一个L维随机矢量X:X=(X1,Xl,XL)(2-10)随机矢量X的具体取样值为x:x=(x1,xl,xL)(2-11)取样值x的对应概率Px(x)（简写成P(x)）为P(x)=P(x1,xl,xL)=P(x1)P(x2x1)P(x3x2,x1)P(xLxL-1,x1)(2-12)这是一个L维的联合概率。,根据信源是否允许失真,又可以将信源划分为无失真信源与限失真信源两类。对于无失真消息序列信源,可以采用信源的消息序列的取值集合XL及其对应的概率P(x)来共同描述,表达式为XL,P(x),也可写成式中,消息序列长度为l=1,2,L,而每个消息又有n种可能的取值,即i=1,2,n,因此整个消息序列总共有nL种取值。,(2-13),对于离散序列信源,还可以进一步划分为无记忆与有记忆两类,当序列中的前后消息相互统计独立时称为无记忆,否则称为有记忆。对于简单的无记忆离散序列信源,由式（2-12）可导出P(x1,xl,xL)=(2-14)上式在无记忆信源条件下成立,在等概率无记忆信源条件下,上式变为P(x1,xl,xL)=实际通信中的脉冲编码调制(PCM)属于这类信源。下面我们来举例说明。,例2-1写出L=3,n=2等概率无记忆信源的数学表达式。分析：L=3表示每个消息序列有3个消息（码元）,n=2表示每个消息（码元）有两种可能的取值（二进制）,整个消息序列总共有nL=23=8种取值,每个消息（码元）的取值概率为等概率,即P(0)=P(1)=1/2,应用式(2-14),则该信源的数学表达式为,有记忆信源是指消息序列中前、后消息间不满足统计独立的条件,实际信源一般均属此类。但是描述这类信源比较困难,特别是序列消息间记忆长度L很大时,需要掌握全部记忆区域内L维的概率统计特性。在实际处理时,往往可以作进一步简化,特别是当消息序列中任一个消息仅与前面一个消息有直接统计关联,或者推而广之,消息序列中由K个消息组成的一个消息状态仅与前面K个消息组成的前一消息状态有直接统计关联时,称该信源为一阶马氏链信源。进一步,若这类一阶马氏链信源又满足齐次与遍历的条件（这里齐次是指消息的条件转移概率随时间推移不变,即与所在时间位置无关；遍历则是指当转移步数足够大时,序列的联合概率特性基本上与起始状态概率无关）,则在这种特殊情况下描述与分析可以进一步减化。比如数字图像信源往往可以采用这一模型作为分析的近似模型。,2.1.4信源的信息度量1.信息的基本概念我们在前面讨论了信源的分类与统计描述,主要利用了信源的客观概率分布(包括概率与概率密度)特性描述了信源。为了进一步深入定量地研究信源,仅限于上述一般化的描述是不够的。信源就其信息实质来说,具有不确定性,那么信息与不确定性是什么关系,而不确定性又如何利用客观概率来表达,这就是信源输出的消息(或符号)所包含信息的定量度量问题。,在正式讨论信息定量度量以前,先简要地介绍一下信息的基本概念。信息是一个既广泛而又抽象的哲学概念,至今无确切定义。其广泛性主要体现在宇宙间、自然界中充满了客观特性信息,人类生存每时每刻也离不开信息。其抽象性主要体现在它是一种内涵丰富的重要概念,能为人人理解但又无法确切定义。物质、能量与信息是支撑现代社会及其发展的三大支柱,信息既不是物质,也不是能量,但又离不开物质与能量,它是人类认识客观世界的更高层次,掌握信息不仅能充分利用物质和能量,还会创造新的物质与能量形式。在这里不打算对广义信息的概念作进一步深入探讨,而将重点放在分析、理解通信领域中狭义信息的概念上。在通信中,信息是指信源的内涵。信源所表达的内容与含义,是信道待传送的内容与含义,它是一个抽象的哲学表达层次上的概念。在通信中至少可以从两个不同的层次(侧面)来进一步描述与刻画它。,通信中描述信息的第一个层次是在工程领域中经常采用的最为具体的物理表达层,该层次的代表是信号。信号是一个物理量,可描述、可测量、可显示。通信中待传送的信息就是以信号参量形式载荷在信号上的,这些参量是信号的振幅、频率、相位乃至参量的有与无。所以就物理表达层来看,信息是信号所载荷的内容与含义。通信中描述信息的第二个层次是在理论领域中常采用的较为抽象的数学表达层,该层次的代表是消息(或符号),它将抽象的待传送的信息从数学实质上加以分类：一类为离散型,即数字信源,用相应的随机变量X、随机变量序列X=（X1,Xl,XL）来描述；另一类为连续型,即模拟信源,可以用相应的随机过程X(t)来描述。,在这个层次上抽象的信息概念可以在数学层次上被描述为随机序列和随机过程,从而为信息定量度量打下坚实的基础。在这一层次中,信息是消息所描述和度量的对象。信号、消息、信息三个表达层次是一个统一体,它们之间的关系可以看作是哲学上的内涵与外延的关系。这就是说,信息是信号与消息的内涵,即消息所要描述和度量的内容、信号所要载荷的内容；而信号是信息在物理层次上的外延,消息是信息在数学层次上的外延。这也就是说,信号与消息是信息在物理与数学两个不同方面的表达方式。同一内涵的信息可以采用不同的消息形式来描述,也可以采用不同的信号形式来载荷；相反,不同内涵的信息也可以采用同一消息形式来描述,同一类型信号形式来载荷。可见,信息、消息与信号三个层次之间是一个既统一又辩证的关系。,2.信源的信息度量信源输出的是消息,消息的内涵是信息,信息的最主要特征是具有不确定性。如何度量信息的不确定性？上一节已经讨论过信源的统计特性可以采用概率及概率密度来描述,那么度量信息的不确定性与信源的概率与概率密度是什么关系?这正是本节所要讨论的主题。信息的定量化一直是人们长期追求的目标。早在1928年,信息论的先驱学者之一哈特莱(Hartley)首先研究并给出了一种具有Nm组合的非概率(实际上可看成等概率)信源的信息度量公式,即I=logNm=mlogN(2-15),由于包含信息的消息或符号最主要的特征是不确定性，而不确定性主要来源于客观信源概率统计上的不确定性，而Hartley信息度量公式可以看成在等概率信源条件下信息度量的一个特例。后来这一观点完全被信息论创始人香农（Shannon）所吸收。这里，将首先从人们容易接受的直观概念出发，推导出信源的信息度量公式：信息熵的基本公式，它与Shannon从严格的数学上给出的结论是完全一致的，当然也可以引用熵的公理化结构来证明这一点，但由于篇幅所限，这里从略。,从直观概念推导信息熵的公式，可以分为两步：第一步首先求出当某一个具体的单个消息(符号)产生(出现)时（比如x=xi时）的信息量，用IP(xi)来表示；第二步求单个消息(符号)信源的信息熵(平均信息量)，用H(X)来表示，由于单个消息(符号)信源有i=1,2,n种取值可能，因此要取统计平均,即H(X)=EIP(xi)。通常,对单个消息信源,比如X=xi,它出现的概率P(xi)越小,它的出现必然使人越感意外,则由它所产生的信息量就越大,即P(xi),IP(xi),且当P(xi)0时,IP(xi)；反之,P(xi),IP(xi),且当P(xi)1时,IP(xi)0。,可见,对于单个消息信源,某个消息X=xi所产生的信息IP(xi)应是其对应概率P(xi)的递降函数。另外,由两个不同的消息(两者间统计独立)所提供的信息应等于它们分别提供信息量之和,即信息应满足可加性(实际上若两者不满足统计独立,也应满足条件可加性)。显然,同时满足对概率递降性与可加性的函数应是下列对数函数:通常称IP(xi)为信源是单个离散消息X=xi时的非平均自信息量。,（2-16）,同理,可以分别定义信宿Y,P(yj)在Y=yi时的非平均自信息量、两个消息有统计关联时的条件非平均自信息量和两个消息的联合非平均自信息量如下:,（2-17）,（2-18）,（2-19）,（2-20）,上面,我们从直观概念直接推导出当信源为一个单消息、条件单消息以及两个消息联合同时出现时的非平均自信息量的表达式。然而,一般离散信源,即使是单消息信源,也具有有限种取值的可能,即i=1,2,n；j=1,2,m,因此,这时信源输出的信息量就应该是上述具体单个消息产生的非平均自信息量的概率统计平均值,显然它与信源本身的概率特性有关。因此,可以定义信源输出的信息量,信息论创始人Shannon将其定义为H(X)=HP(x1),P(xn)=EIP(xi)=E-logP(xi)=P(xi)logP(xi)（2-21）,其中,“E”表示求概率统计平均值,即求数学期望值。Shannon称H(X)为信源的信息熵,简称为熵。从数学上看,熵是信源消息概率P(xi)的对数函数logP(xi)的统计平均值,故又称为P(xi)的泛函数,它是定量描述信源的一个重要物理量。它是Shannon于1948年首先给出的一个从概率统计角度来描述信源不确定性的一个客观物理量,是从信源整体角度上反映信源不确定性的度量。熵这个名词由Clausius于1864年引入统计热力学领域,在统计热力学中称为热熵,它是用来表达统计热力学中分子运动混乱程度的一个物理量。Shannon在1948年发表的经典文章“通讯的数学原理”中把熵这个概念引入通信中,用它描述信源平均不确定性,其含义是类似的。但是在热力学中已知任何孤立系统的演化热熵只会增加不会减少,然而在通信中信息熵只会减少不会增加,所以也有人称信息熵为负热熵。,信息熵的单位与非平均自信息量的单位一样,都取决于所取对数的底。在通信中最常用的是以2为底,这时单位称为比特(bit)；有时在理论分析和推导时采用以e为底比较方便,这时单位称为奈特(Nat)；在工程运算时,有时采用以10为底较方便,这时单位称为笛特(Det)。它们之间可以引用对数换底公式进行互换。比如：1bit=0.693Nat=0.301Det上面,我们从直观概念直接推导出Shannon的信息熵公式(2-21)。范因斯坦(Feinstein)等人曾证明：当信息满足对概率P(xi)的递降性、可加性的条件时,公式(2-21)的信息熵表达式是惟一的,后来人们称这一证明为熵的公理化结构证明。,类似于对信息熵H(X)的定义,也可以对信宿熵H(Y)、条件熵H(Y/X)和H(X/Y)、联合熵H(X,Y)作如下定义：H(Y)=EIP(yj)=E-logP(yj)=（2-22）H(Y/X)=EIP(yj/xi)=E-logP(yj/xi)=H(Y/X)=EIP(xi/yj)=E-logP(xi/yj)=,（2-23）,（2-24）,H(Y/X)=EIP(xi,yj)=E-logP(xi,yj)=它们之间有如下关系：(1)联合熵与条件熵的关系：H(X,Y)=H(X)+H(Y/X)=H(Y)+H(X/Y)（2-26）,（2-25）,(2)熵与条件熵的关系：H(X)H(X/Y)（2-27）H(Y)H(Y/X)（2-28）式(2-27)和式(2-28)又称为Shannon不等式。例2-2设随机变量(X,Y)具有如表2-1所示的联合概率分布,求信息熵H（X）、H（Y）,联合熵H（X,Y）和条件熵H（Y/X）、H（X/Y）。,表2-1随机变量（X,Y）的联合概率分布,解由表2-1可知n=m=4,先求出P(xi)如下：,再求出P(yj)如下：,由式（2-21）得由式（2-22）得由式（2-25）得,由式（2-26）得3.熵的基本性质设X是一个n元随机变量,其概率分布为p1=p(x1)=p(X=x1),p2=p(x2)=p(X=x2),pn=p(xn)=p(X=xn),从这个例子我们可以看出H(Y/X)H(X/Y)。,由式（2-21）可得H(X)=H(p1,p2,pn)=由可知,H(p1,p2,pn)是(n-1)元函数。P=(p1,p2,pn)是n维矢量,在pi=1(p0)的条件下常称为概率矢量,所以n元随机变量X的熵函数H(X)就是概率矢量P的函数H(P)=H(p1,p2,pn),它具有以下基本性质：1)连续性熵函数H(P)是概率矢量P的连续函数。,2)递降性设(p1,pi,pn)=,其中a为任意正整数,则必有（2-29）式（2-29）表示概率pi由1/(a+1)增加为1/a,熵函数H(p1,pi,pn)的值下降,即熵函数随着概率的增加而下降,具有递降性。这很容易理解,因为概率增加,表示不确定性下降,而熵函数正是平均不确定性的度量,所以它必然下降。,3)可加性HM(p1q11,p1q12,p1q1m1;p2q21,p2q22,p2q2m2;pnqn1,pnqn2,pnqnmn)=Hn(p1,p2,pn)+piHmi(qi1,qi2,qimi)（2-30）式中,。上式可解释如下：随机变量X的取值集（范围）可划分成n个子集,每个子集的概率为pi,则其熵为Hn(p1,p2,pn)。若对每个子集作进一步划分,例如把第i个子集划分成mi小子集,并使每个小子集出现的概率为piqij(j=1,2,mi),且。各个子集进一步划分时所分成的小子集的个数mi不一定相等。,对这样划分的取值集（范围）,当判断随机变量X在哪个小子集取值时,可分两步进行：第一步,先判断随机变量X在哪个子集取值,其平均不确定性为Hn(p1,p2,pn),即平均要付出的信息量；第二步就是判断随机变量X在子集中的哪一个小子集取值。在已知第i个子集的条件下,随机变量X在其小子集取值的平均不确定性为Hmi(qi1,qi2,qimi),相应子集的概率为pi,所以第二步判断平均付出的信息量为piHmi(qi1,qi2,qimi)。这两步之和就是判断随机变量X在哪一个小子集取值的总的平均不确定性。由此可见,当把判断分成多层次进行时,则各层次熵之和就为总的熵,这就是熵的可加性。,4)对称性H(p1,pi,pn)是(p1,p2,pn)的对称函数,即熵函数的值只与概率分布或将1分割成的n个实数取值有关,而与(p1,p2,pn)的排列顺序无关；或者说当(p1,p2,pn)的排列顺序发生变化时,熵函数的值不变。5)非负性对任何概率矢量（概率分布）P=(p1,p2,pn),总有H(p1,p2,pn)0成立,且等号成立的充分必要条件为P是一个决定性概率分布,即只有一个pi=1,其余的pj=0(ji)。,6)极值性（最大熵值定理）当概率分布服从均匀分布时,即(p1,p2,pn)=,为等概率时,熵值最大,用公式表示为H(p1,p2,pn)（2-31）此外,熵函数还具有上凸性、确定性等性质。下面举一个例子来进一步说明熵函数的性质。设X是一个二元随机变量,其概率分布为p1=p(X=1)=p、p2=p(X=0)=1-p,由式（2-21）可得：H(X)=-plogp-(1-p)log(1-p)=H(p)=H(p1,p2),定义H(p)为离散二进制信源的熵函数,则H(p)随p的变化而变化的曲线如图2-1所示。由图2-1可以直观地得到熵函数的连续性、对称性、非负性、极值性、上凸性、确定性等性质。,图2-1离散二进制信源的熵函数,4.信源编码的理论基础现在我们来讨论信源冗余度的概念,它是信源统计分析中一个非常重要的概念,是信源信息处理、信源编码的理论依据。由于实际信源几乎都是有记忆的,这也就是说信源输出的消息序列的各个消息之间存在着记忆,即统计关联。如果能首先定量地计算出这一统计关联引入的冗余度,就能充分地利用它。下面讨论冗余度及其计算。前面讨论了熵的定义及性质,由熵的非负性、Shannon不等式以及熵的极值性,对于一个最简单二进制信源有下列基本不等式:0H(X/Y)H(X)lb2=1(2-32)其中lb2为离散二进制信源消息等概率分布时的熵函数值（最大值、极值）。,下面,将公式(2-32)推广至离散多进制有记忆信源:0H(X)=lim(XL/XL-1,X1)H2(X2/X1)H1(X)H0(X)=logN(2-33)式中,l=1,2,L为信源记忆长度,H(X)为无限记忆长度时的信息熵,H2(X)为一维记忆长度时的信息熵,H1(X)为无记忆不等概率信息熵,H0(X)为无记忆等概率信源最大熵。由公式(2-33)可见,对于一般化的有记忆信源熵,最小的单个消息熵应为H(X),这就是说,从理论上看只需要在信道中传送H(X),在接收端则可利用信源统计关联的记忆特性,即无限维的全部概率特性,恢复出信源的全部信息。但是若不利用信源统计特性与统计关联,信道中传送的则是信源的最大信息熵H0(X)。若不考虑信源统计特性时,信道多传送的信息量为H(X)=H0(X)-H(X)(2-34),为了定量地描述信源的有效性,定义下面两个概念:(信源效率)=(2-35)R(信源相对冗余度)=1-=(2-36)其中,H(X)表示考虑全部信源统计特性后信源的最小信息熵,它是信道传送的理论最佳值；而H0(X)是不考虑信源统计特性,即认为信息均为等概率时信源的最大熵。公式(2-36)表示信源从统计特性上看的相对冗余度。一般说来,信源效率越低,信源相对冗余度就越大,就越有必要对信源进行统计信息处理,采用信源编码和数据压缩也就有必要。因此,可以认为信源的相对冗余度是信源编码和数据压缩的理论基础。下面,举两个例子进一步说明信源编码和信源统计信息处理的必要性。,例2-3关于英文文字信源冗余度的讨论。根据英文中各个字母（含空格）出现的概率,可列出表2-2。,表2-2英文字母出现概率统计表,由表2-2,首先求得独立等概率情况下的H0(X)值:H0(X)=lb27=4.76b再求独立不等概率情况下的H1(X)值:H1(X)=P(xi)lbP(xi)=4.03b还可进一步求得有一阶、二阶记忆下的H2(X)和H3(X)为H2(X)=3.32bH3(X)=3.1b,最后,利用统计推断方法求得H(X)的值。一般而言,由于采用不同的逼近方法和所取样本上的差异,所推算的结果也不同,这里我们采用Shannon求得的推算值：H(X)1.4b这样,利用公式(2-35)及(2-36)可分别求得=0.29,R=0.71。这一结论说明英文字母信源从理论上看,有71%是多余的,即可以认为一本100页的英文书,理论上看仅有29页是有效的,其余71页从统计角度看完全是多余的。也正是由于理论上存在着这一多余成分,引导了实际工作者对英文信源进行压缩编码的研究。英文信源的分析也带动了各国对自己国家语言文字信源的分析,现将类似结果列于表2-3。,表2-3不同文字信源冗余度估算,例2-4关于语音信源冗余度的一个粗略估计。语音信源的编码大致可以分为波形编码、参量编码与混合编码三大类。这里,仅分析冗余度最大的参量编码,即声码器的最大潜力。语音参量可以从不同角度给出,这里考虑潜力最大的语音的最基本参量单元音素。以英语为例,其音素大约有2728个,若按人们通常讲话的速率,每秒钟大约平均发送10个音素,这时英语语音信源给出的信息率为上限：I1=lb(256)10=80b/s下限：I2=lb(128)10=70b/s,若按PCM常规数字化编码传送语音,其标准速率为64kb/s,因此可求得1=0.001252=0.0011R1=1-1=1-0.00125=0.99875R2=1-2=1-0.0011=0.9989可见,语音参量编码潜力巨大。定义理论上最大压缩倍如下：K1=800(倍)K2=914(倍),2.1.5信源编码的目的过去,由于传输的信息量不大,对通信的研究主要集中在通信的可靠性上,即如何可靠地传输和接收信息。但是,随着社会进入信息化时代,通信过程中需要传输的信息量越来越大,促使人们越来越重视通信的有效性问题。一方面社会生活中需要传输的信息量日益剧增,另一方面实际信源中存在着大量的统计多余成分,这样,通过信源编码技术来去除或降低实际信源的冗余度,则成为了提高通信的有效性的有效途径之一。从信息论观点看,实际的信源若不经过信息处理,即信源编码,信源会存在大量的统计多余成分,这一部分信息完全没有必要通过信道传送给接收端,因为它完全可以利用信源的统计特性在接收端恢复出来。信源编码的目的就是在分析信源统计特性的基础上,设法通过信源的压缩编码去掉这些统计多余成分,以提高通信的有效性。这一过程称为数据压缩,所得信源编码称为压缩编码。,2.2无失真信源编码,2.2.1基本原理我们在前面讨论了无失真信源的信息度量：信源熵H（X）。在本节将进一步分析讨论实现通信系统优化的无失真信源编码定理。为了分析简化,这里仅讨论最简单情况组合下的信源无失真编码定理：离散、无记忆、平稳、遍历、二（多）进制等（变）长编码条件下的信源编码定理。下面,我们将从直观概念出发,直接推导出这类简化性信源编码。首先研究等长码,参见图2-2,其中,x为输入,它共有L位（长度）,每一位有n种取值可能;s为输出,它共有K位（长度）,每一位有m种取值可能。,图2-2信源编码原理图,倘若不考虑信源的统计特性,为了实现无失真并有效的编码,应分别满足：无失真要求：nLmK（即每个信源组合必须有对应的编码）(2-37)有效性要求：nLmK（即编码组合总数要小于信源组合总数）(2-38)从式(2-37)可推出(2-39)显然,上述两个条件是相互矛盾的。如何解决这一对矛盾呢？惟一的方法是引入信源的统计特性。这时,就无需对信源输出的全部nL种信息组合一一编码,而仅对其中少数大概率典型组合进行编码。,下面,先分析公式(2-39)的含义,并在引入信源统计特性以后对它作适当的修改。公式(2-39)的右端,其分子部分表示等概率信源的熵,而分母部分则表示等概率码元的熵。当引入信源统计特性以后,信源不再满足等概率,这时分子可修改为不等概率实际信源熵H(X),则有(2-40)再将上式稍作变化,即可求得典型Shannon第一等长编码定理形式,当(2-41),时,有效的无失真信源编译码存在,可构造；反之,当(2-42)时,有效的无失真信源编译码不存在,不可构造。再讨论变长码,这时仅需将公式(2-40)修改为(2-43)式中将等长码的码长K改成相对应变长码的平均码长,平均码长由下式计算：(2-44),再将公式(2-43)稍加修改即可求得典型的Shannon第一变长编码定理形式:对于二进制（m=2）,则有当对数取2为底时,有,(2-45),(2-46),(2-47),式中,K/L表示平均每个码元的长度。可见它要求平均每个码元的长度应与信源熵相匹配,因此又称为熵编码。实现无失真信源编码的基本方法有两大类型：一类为改造信源方式,即将实际不理想的不等概率信源变换成理想的具有最大熵值的等概率信源,再采用等长编码进行匹配；另一类为适应信源方式,即对实际的不等概率信源采用与之相匹配的变长编码方法,包括最佳变长哈夫曼（Haffman）编码、算术编码以及适合于有记忆信源的游程编码等。,2.2.2哈夫曼（Huffman）编码哈夫曼编码是一种统计压缩的可变长编码,它将欲编码的字符用另一套不定长的编码来表示,基本原理是：按照概率统计结果,出现概率高的字符用较短的编码来表示,出现概率低的字符用较长的编码来表示。编码压缩性能是由压缩率（compressionratio）来衡量的,它等于每个采样值压缩前的平均比特数与压缩后的平均比特数之比。由于编码的压缩性能与编码技术无关,而与字符集的大小有关,因此,通常可以将字符集转化成一种扩展的字符集,这样采用相同的编码技术就可以获得更好的压缩性能。,哈夫曼编码过程可用于任意两个字符集。下面分析一个任意输入字符集到一个二进制输出字符集的转换过程。哈夫曼编码过程类似于树形生成过程。首先列出输入字符集及其概率（或相对频率）,以降序排列,如图2-3所示。这些列表项相应于树枝末端,每个分支都标注了等于该分支概率的分支权值。现在开始生成包含这些分支的树：将最低概率的两个分支合并（在分支节点处）,形成一个新分支,并标注上两个概率的相加值；每次合并后,将新的分支和剩下的分支重新排序（若需要）,以保证减少的列表概率的递降性,将这种排列方法称为冒泡法。在每次合并后的重排中,新的分支在列表中不断上升至不能上升为止。,因此,如果形成一个权值为0.2的分支,在冒泡过程中发现其他两个分支的权值也是0.2,那么,新的分支将被冒泡到权值为0.2的分支组的顶端,而不是简单地加入。冒泡到同权值组的顶端可以生成码长方差小的编码,以降低缓冲溢出的可能性。为了讨论方便、描述准确,我们定义n元素m字符集为：字符集中共有n个元素,每个元素都包含m个字符,即每个元素包含的字符数目相同。,图2-36元素单字符集的哈夫曼编码树,例2-56元素单字符集的哈夫曼编码。设6元素单字符集中每个元素的出现概率如表2-4所示。,表2-46元素单字符集哈夫曼编码的详细参数,将哈夫曼编码过程应用于表2-4所示的输入字符集。按照哈夫曼编码规则,生成哈夫曼编码树,如图2-3所示。然后在哈夫曼编码树的每个分支节点标上二进制数“0”或“1”,以区分两个分支。这种标记可以是任意的,但为了保持一致,将每个节点的上向分支标为“1”,下向分支标为“0”。标记好之后,沿着树径从树基（最右）到每个分支（最左）的路径包含了到达该分支的二进制序列,该二进制序列就是分支对应字符的哈夫曼编码,哈夫曼编码的详细参数如表2-4所示。,由式(2-44)可计算出字符集的平均码长是2.4b。这好像意味着我们必须找到一个传输非整数比特的方法。实际上这个结果表明,当要传输100个输入码元时,通信信道中平均需要传输240b。比较一下,若采用等长码来表示6元素单字符集,则码长K为3b,利用式(2-21)计算输入字符集的熵（平均信息量）为2.32b。因此,哈夫曼编码提供了1.25（3.0/2.4）的压缩率,该字符集编码效率达到了96.67（2.32/2.40）。为了说明代码扩展的应用,我们再举一个例子。,例2-63元素单字符集的哈夫曼编码（元素的概率分布不均匀）。该字符集的哈夫曼编码树见图2-4,其详细参数见表2-5(i=1,2,3)。,图2-43元素单字符集的哈夫曼编码树,表2-53元素单字符集哈夫曼编码的详细参数,该哈夫曼编码的平均码长是1.27b；采用等长码则码长为2b。这里,哈夫曼编码提供的压缩率是1.57（2/1.27）,比6元素单字符集的1.25大。但是,应用式(2-21)计算字符集的熵（平均信息量）为0.9443b,该字符集编码效率为74.35（0.9443/1.27）,却比6元素单字符集的96.67小。这是因为6元素单字符集的信息熵（2.32b）与平均码长（2.4b）的匹配比3元素单字符集的信息熵（0.9443b）与平均码长（1.27b）的匹配要好。,由此可见,由于有较多元素的字符集具有较大的信息熵（平均信息量）,使得信息熵与平均码长的匹配更好些,所以具有更高的编码效率。为了提高编码效率或获得更大的压缩增益,必须重新定义信源字符集的元素,对字符集进行扩展。具体的方法是：每次从源字符集（3元素单字符集）中选择两个元素,排序形成扩展字符集（9元素双字符集）的新元素。如果假定元素是独立的,那么每个新元素的概率是各个元素独立概率之乘积。扩展字符集为XxiX,i=1,2,9,每个元素xi的编码序列通过上述哈夫曼过程获得,扩展后的9元素双字符集的参数如表2-6所示。可以算出扩展后的9元素双字符集的压缩率是2.07（2/0.9671）,编码效率是97.64（0.9443/0.9671）,比扩展前的3元素单字符集的压缩率1.57、编码效率74.35有明显的提高。,表2-63元素单字符集扩展为9元素双字符集,扩展码提供了一种利用码元关联性的技术。例如,英文中的相邻字母有很强的关联性。特别常见的字母对有：threinshhee_deeds_ngatr_teesd_下划线代表一个空格。类似地,常见的3元组合有：theandforingioness因此,一般不对单个字母采用哈夫曼编码,而是将字符集扩展为包含所有单字母、常见2字母和3字母组合的扩展字符集,然后再对扩展字符集进行哈夫曼编码,这样可以得到更高的编码效率。,例2-7概率分布均匀的3元素单字符集的哈夫曼编码。该字符集的哈夫曼编码树见图2-5,其详细参数见表2-7(i=1,2,3)。,图2-5概率分布均匀的3元素单字符集的哈夫曼编码树,表2-7概率分布均匀的3元素单字符集哈夫曼编码的详细参数,该哈夫曼编码的平均码长是1.667b,采用等长码时码长为2b,则哈夫曼编码提供的压缩率是1.20（2/1.667）。应用式(2-21)计算字符集的熵（平均信息量）为1.585b,该字符集编码效率为95.08（1.585/1.667）。若把该3元素单字符集扩展为9元素双字符集,则扩展后的9元素双字符集的参数如表2-8所示。可算出扩展后的9元素双字符集的压缩率是1.24（2/1.611）,编码效率是98.39（1.585/1.611）,与扩展前的3元素单字符集的压缩率1.20、编码效率95.08相比较,有提高但提高的幅度不大。,表2-8概率分布均匀的3元素单字符集扩展为9元素双字符集,通过例2-6与例2-7的比较,我们可以得出以下两点结论:字符集的哈夫曼编码的编码效率和压缩率与字符集的概率分布有关,概率分布不均匀,编码效率低,压缩率高；概率分布均匀,编码效率高,压缩率低。扩展后的字符集的编码效率和压缩率提高的幅度与原字符集的概率分布有关,概率分布不均匀,编码效率和压缩率提高的幅度大；概率分布均匀,编码效率和压缩率提高的幅度小。故哈夫曼编码适合用于概率分布不均匀的信源。,哈夫曼编码方法是一种不等长最佳编码方法,此处的最佳是指：对于相同概率分布的信源而言,它的平均码长比其他任何一种有效编码方法的平均码长都短。此外还有两点需要说明：一是对同一个信源,哈夫曼编码不是惟一的,但编码效率是一样的；二是对不同概率分布的信源,其编码效率不同,且编码效率与信源概率分布的不均匀性成正比,即信源概率分布越不均匀,其编码效率越高。,2.2.3算术编码1.基本原理算术编码是20世纪80年代发展起来的一种新的编码方法,在未知信源概率分布和信源概率分布比较均匀的情况下,它优于哈夫曼编码。在算术编码中,信息串的编码用01之间的一个实数区间来表示。在编码前,这个区间的完整范围是0,1）。编码时,随着信息串中一个个字符编码的完成,表示编码的区间不断减小,因而表示该区间所需的位数不断增加。信息串中的字符越多,表示信息串编码的区间就越小,表示该区间所需的位数也就越多。,信息串中的每个字符根据统计模型为它定义的出现概率来划分区间,概率大的字符对应较大区间,概率小的字符对应较小区间。在对信息串中的字符进行编码时,根据字符出现概率的大小来减小区间的范围,出现概率大的字符使区间范围减小的幅度比出现概率小的字符使区间范围减小的幅度要小。,设编码前的编码区间范围为a0,a0）0,1）,并设对信息串中的第1个字符进行算术编码后的编码区间的上、下限为第1个字符取值范围的上、下限,即a1=b1、a1=b1,则计算编码区间上下限的编码递推公式为下限:an=an-1+(an-1-an-1)bn(2-48)上限:an=an-1+(a-1-an-1)bnn2(2-49)式中,an-1和an-1、an和an分别为对信息串中的第n-1个字符、第n个字符进行算术编码后编码区间的上、下限,bn、bn为第n个字符取值范围的上、下限。,假设一信息串包含N个字符,当完成了对它的算术编码后,其算术编码为此时编码区间的下限,即c=aN。下面举例说明算术编码的过程。例2-8对字符串“age!”进行算术编码。设各字符的出现概率和取值范围如表2-9所示。,表2-9各字符的出现概率和取值范围,对第1个字符a进行编码时,取编码区间的上、下限为字符a取值范围的上、下限,有a1=b1=0,a1=b1=0.2。对第2个字符g进行编码时,由式(2-48)和式(2-49)可计算出编码区间的上、下限为a2=a1+(a1-a1)b2=0(0.20)0.80.16a2=a1+(a1-a1)b20(0.20)0.60.12则此时的编码区间为0.12,0.16）。以此类推,利用式(2-48)和式(2-49)可计算出对第3个字符e、对第4个字符！进行算术编码后的编码区间分别为0.152,0.156）和0.1556,0.156）。,字符串“age!”中的最后一个字符!是结束标志。至此可得到字符串“age!”的算术编码为ca4=0.1556。接收端收到信息串后,根据收发双方预先规定的字符概率区间分配表和取值范围,解码器就可以惟一正确地进行译码。具体的方法是：若接收的代码为0.1556,根据表2-9各字符的出现概率和取值范围,可以判断它是在0,0.2）的区间范围内,所以第1个字符应为a。从第2个字符开始,需用递推公式依次计算出各字符的相应代码,然后进行判断。计算各字符相应代码的译码递推公式为,(2-50),式中,an-1和an分别为第n-1个字符和第n个字符的相应代码,bn-1、bn-1为第n-1个字符取值范围的上、下限。应用公式(2-50)可计算出第2、3、4个字符的相应代码依次为0.778、0.89和0.9,由表2-9可以判断出第2、3、4个字符依次为g、e和！。最后一个字符！是结束标志,表示信息传输结束,解码器见到它就停止解码。这样,通过编码过程的逆运算,我们可以惟一正确地把代码0.1556翻译为字符串“age!”。,2.二进制算术编码原理1）区间的递归划分概率区间的递归划分是二进制算术编码的基础。每执行一次判定,当前概率区间就被划分成为两个子区间,并在必要时修改输出位流,使之指向该符号所在的概率子区间和下界。要进行区间划分时,小概率符号（LPS）的子区间和大概率符号（MPS）的子区间这样排序：通常取靠近0的区间作为MPS的子区间,因此,若编码的是LPS,则应向输出位流中加入MPS子区间的长度。这种约定要求把编码的符号区别为LPS或MPS,而不是0或1。所以在对一个二元判定编码时,必须知道该判定的LPS子区间和MPS的含义。,再分当前概率区间时,理论上要把当前区间乘以LPS的概率估计值。但实际上通常进行的区间划分是粗略的,所以LPS子区间可能大于MPS子区间。遇到这种情况时,进行“调整交换”,即把两个子区间的分配互换,使MPS子区间取为较大者。2）自适应二进制算术编码所谓自适应二进制算术编码,是指编码系统能够根据已经传输和编码的信息串来调整当前符号的概率估计,从而更有效地进行编码。一个自适应二进制算术编码需要使用统计模型,以便选择二元判定编码时所用的条件概率估计。若一给定的二元判定,其概率估计依赖于已编码的某些“特征”称为“上下文”）,那么它将根据这些“特征”进行调整。根据“特征”来调整概率估计的机制在编码/解码器中应该是相同的,因此只能使用两者均已知的信息。,统计模型所需的每一个条件概率估计存储于一个单独的存储区（或称“箱”）中,并以惟一的上下文索引S进行标识。自适应的算术编码器中,每个上下文索引和概率估计由系统根据该索引之前的若干编码判定来生成并予以维护。算术编码是一种高效清除字串冗余的算法。它避开用一个特定码字代替一输入符号的思想,而用一个单独的浮点数来代替一串输入符号,避开了哈夫曼编码中比特数必须取整的问题。但是算术编码的实现有两大缺陷：很难利用具有固定精度的计算机完成无