编码理论第4章

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,4,章 信源压缩编码原理,4.1,信源编码的基本原理,4.1.1,信源研究内容,4.1.2,信源编码器,4.1.3,码的类型,4.1.4 Kraft,不等式,4.1 5,惟一可译码判别准则,4.1.6,即时码的树图构造,4.2,无失真信源编码原理,4.2.1,等长码及其编码定理,4.2.2,变长码平均码长及编码效率,4.2.3,变长码的特点,4.2.4,变长信源编码定理,4.3,限失真信源编码原理,4.3.1,失真函数及保真度准则,4.3.2,信息率失真函数,4.3.3,信息率失真函数定义域及性质,4.3.4,离散信源信息率失真函数计算,4.3.5,保真度准则下的信源编码定理,第,4,章 信源压缩编码原理,4.1,信源编码的基本原理,4.1.1,信源研究内容,信息论对信源研究的内容包括,3,个方面：,(1),信源的建模,信源输出信号的数学描述已有成熟的理论,随机过程，一般的随机过程理论并不涉及和讨论信号中所携带的信息，而信息论所关心的中心内容则是信号中携带的信息。,(2),信源输出信号中携带信息的效率的计算,在信息论中，信源输出信号所携带信息的效率是用熵率或冗余度来表示的。,(3),信源输出信息的有效表示,一般地，信源输出信号中携带信息的效率并不很高，如何用适当的信号有效地表示信源输出的信息是人们感兴趣的问题，这就是信源编码的问题。,信源,信源编码器,信道,信源译码器,信宿,4.1.2,信源编码器,为了简化问题，研究无失真编码时，只考虑信源和信宿两个主要因素，这样信息传输系统模型变为图,4-1,所示。,图,4-1,简化信息系统传输模型,概念,信源符号,二元信源,n,元信源,码符号集,码符号,码元,码字,码组,码长,二元码,r,元码,等长码,变长码,非奇异码,奇异码,惟一可译码,非惟一可译码,即时码,非即时码,设信源,U,发出,n,种不同的符号，其符号集为,U=u1,u2,u,n,其中,ui,称为,信源符号,，若信源符号集中符号数等于,2,称为,二元信源,，等于,3,称为,三元信源,，,，等于,n,称为,n,元信源,。,又若信道的输人符号集为,X=a1,a2,ar,。信源编码问题,就是用信道的输人符号集,X=a1,a2,ar,作为码符号集，其中,ai,（,i,1,，,2,，,，,r,）称为,码符号或码元,，用码符号集中的码符号,对信源,U,的每一种不同的符号进行一一对应变换，构成由码符号组成的序列，即,码字,。,所有码字的集合称为,码组,w=w1,，,w2,，,，,wn,；码字中所用的码符号的个数称为,码长,。,4.1.3,码的类型,若码符号集中符号数等于,2,称为,二元码,，等于,3,称为三元码，,，等于,r,称为,r,元码,。若一组码中所有码字的码长都相同，称为,等长码,否则称为,变长码,。若码组中所有码字都不相同则称为,非奇异码,，否则称为,奇异码,。,符号,码,1,码,2,码,3,码,4,a,00,0,0,1,b,01,10,11,01,c,10,00,00,001,d,11,01,11,0001,表,4-1,信源,X,对应的不同码字,表,4-1,中码,1,的编码为等长码，其它的几种编码皆为变长码。码,3,有两个符号的编码相同，码,3,是奇异码，而码,1,、码,2,和码,4,都为非奇异码。,若每个码符号的传输时间都相同则称为,同价码,，否则称为,非同价码,。,信源编码编出的每一种码字要与信源发出的每一种不同的符号一一对应，而且同时还要求信源的,N,个符号组成的序列所代表的消息，与之相对应的码字组成的码字序列也必须一一对应。只有这样，才能保证任何一个码字或码字序列唯一地翻译成相对应的信源符号或符号序列，达到无失真传递信源发出的消息的目。无失真信源编码必须具有这种单义可译性,单义可译的码称为单义可译码，也称为,惟一可译码,。,例如码字,0,，,10,，,11,是一种惟一可译码。因为任意一串有限长码序列，例如,100 111 000,，只能被分割成,10,，,0,，,11,，,10,，,0,，,0,。任何其他分割法都会产生一些非定义的码字。非奇异码中有非惟一可译码和惟一可译码。,惟一可译码中又分为,非即时码,和,即时码,；如果接收端收到一个完整的码字后，不能立即译码，还需等下一个码字开始接收后才能判断是否可以译码，这样的码叫做非即时码。,表,4-1,中码,2,是非即时码，而码,4,是即时码。码,4,中只要收到符号,1,就表示该码字已完整，可以立即译码。即时码又称为非延长码，若码组中，没有任何完整的码字是其它码字的前缀则称为,异前缀码,(,或前缀条件码），表,4-1,中的码,1,和码,4,都是前缀条件码。,在惟一可译变长码中，人们需要的是在译码时无需参考后续的码符号就能立即做出判断的一类即时码。,4.1.4 Kraft,不等式,在数学上表达码字可分离的充要条件，即著名,Kraft,不等式。,定理,4-1,对于,n,元信源编,m,元码，其码长分别为,l,1,l,2,，,，,ln,，则即时码存在的充要条件,式（,4-1,）称克拉夫特（,Kraft,）不等式。,式（,4-1,）是,1949,年由,L.G.Kraft,提出的，所以称克拉夫特（,Kraft,）不等式，,Kraft,不等式指出了即时码的码长必须满足的条件。后来在,1956,年由麦克米伦（,B.McMillan,）证得对于惟一可译码也满足此不等式，,1961,年卡拉什（,J.karuSh,),简化了麦克米伦的证明方法。这说明惟一可译码在码长的选择上并不比即时码有什么更宽松的条件，而是惟一可译码的码长也必须满足克拉夫特不等式，所以在码长选择的条件上，即时码与惟一可译码是一致的。,如表,4-1,中，,m,2,，,n,4,。,对码,1,有,l,1,2,l,2,2,l,3,2,l,4,2,，则：,满足式（,4-1,），则此码长的编码可能是惟一可译码。,对码,2,有,l,1,1,l,2,2,l,3,2,l,4,2,，则：,不满足式（,4-1,）则此码长编码不能构成惟一可译码。,对码,4,有,l,1,1,l,2,2,l,3,3,l,4,4,，则：,满足式（,4-1,），则此码长的编码可能是惟一可译码。,符号,码,1,码,2,码,3,码,4,a,00,0,0,1,b,01,10,11,01,c,10,00,00,001,d,11,01,11,0001,表,4-1,信源,X,对应的不同码字,4.1 5,惟一可译码判别准则,惟一可译码的判断步骤：,(1),观察是否是非奇异码，若是奇异码则一定不是惟一可译码；,(2),计算是否满足,Kraft,不等式，若不满足一定不是惟一可译码；,(3),将码画成一棵树图，观察是否满足即时码的树图的构造，若满足则是惟一可译码；,(4),用,Sardinas,和,Patterson,设计的判断方法：计算出码组中所有可能的尾随后缀集合,F,，观察,F,中有没有包含任一码字，若无则为惟一可译码；若有则一定不是惟一可译码。,上述判断步骤中,Sardinas,和,Patterson,设计的判断方法是能确切地判断出是否是惟一可译码的方法，所以可以跳过前三个步骤直接采用该判断法。该准则是萨得纳斯,(A,A,Sardinas,),和彼得森,(G,W,Patterson),于,1957,年设计出来的,.,4.1.6,即时码的树图构造,树图法是构造即时码的一种简单方法。,树,是,n,个结点的集合，这,n,个结点中有且仅有一个作为根的结点，其余的结点可分为,m,个互不相交的子集，每个子集本身又是一棵树，称为根的,子树,，也叫根的树枝数。,树图与信源符号编码之间对应关系：,树根 码字的起点,树的度 码的进制数,分支结点 码的符号的一部分,终端结点 待编码符号,满树 等长码,非满树 变长码,构造树图的要点是：,(1),最上端为树根,A,，从根出发向下伸出树枝，树枝总数等于码符号数,r,，树枝的尽头为节点。,(2),从每个节点再伸出,r,枝树枝，当某节点被安排为码字后，就不再伸枝，这节点为终端节点。能再伸枝的节点称为中间节点。一直继续进行，直至都不能伸枝为止。,用码树进行信源符号编码时，将待编码的字符作为终端结点，构造码树；然后按一定规则给每个树枝分配一个码符号；最后将从根到终端结点的路径上的码符号依次相连，作为该终端结点所表示的字符的编码。,码树可用于信源符号的编码，也可用于译码。,0,0,0,0,1,1,1,1,(a),图,5-2,例,5-2,两种霍夫曼编码,4.2,无失真信源编码原理,4.2.1,等长码及其编码定理,4.2.2,变长码的平均码长及编码效率,对,n,元基本离散信源，设编码后各码字的码长分别为,l,1,l,2,，,ln,则定义码的平均码长度为,编码的效率,为,4.2.3,变长码的特点,1,使信道复杂化,2,容易产生溢出或取空错误,3,差错的扩散,4.2.4,变长信源编码定理,用变长码实现无失真编码时，平均码长越短越好，那么平均码长的极限是多少？下面的定理将回答这个问题。,定理,4-3,一个熵为,H,（,U,）的基本离散无记忆信源,U,，若用,m,元码对其进行变长编码，则总可找到一种无失真编码方法，构成惟一可译码，使其平均码长满足,此编码定理给出了最佳变长码的平均码长的上限和下限。定理表明码字的平均长度不能小于极限,H,(,U,)/,lb,m,，否则惟一可译码不存在。,实际上，信源,U,发出的消息，往往不是信源,U,的单个符号，而是由单个符号组成的序列来表示。倘若信源发出的消息由,N,个符号组成，则每一条消息都可看作信源,U,的,N,次扩展信源的某一个“符号”，因此在构造即时码时，如不把信源,U,的单个符号作为编码对象，而直接把扩展信源的某一个输出“符号”作为编码对象，使码字与一一对应，能否使信源,U,每个符号所需要的平均码符号数，即平均码长有所下降,?,也就是说，能否用扩展信源的手段，达到数据压缩的目的,?,下面讨论这个问题。,定理,4-4,无失真变长信源编码定理（香农第一定理）离散无记忆信源,U,的,N,次扩展信源,UN,，其熵为,H,(,UN,),，用,m,元码对信源,UN,进行编码，总可以找到一种编码方法，构成惟一可译码，使信源,U,中每个信源符号所需的平均码长满足：,4.3,限失真信源编码原理,在实际生活中，信宿一般并不要求完全无失真地恢复消息。通常总是要求在保证一定质量,(,一定保真度,),的条件下近似地再现原来的消息，也就是允许有一定的错误,(,失真,),存在。,在允许一定程度失真的条件下，能够把信源信息压缩到什么程度，即最少需要多少比特数才能描述信源。也就是，在允许一定程度失真的条件下，如何能快速地传输信息。这就是本节将讨论的问题。,4.3.1,失真函数及保真度准则,由于只涉及信源编码问题。所以可以将信道编码和译码看成是信道的一部分。这样接收者收到消息后所产生的失真（或误差）只是由信源编码带来的。从直观感觉可知，若允许失真越大，信息传输率可越小,;,若允许失真越小，信息传输率需越大。所以信息传输率与信源编码所引起的失真（或误差）是有关的。为了定量地描述信息传输率和失真的关系，可以略去广义的无扰信道，所谓广义无扰信道是指，把信道编码、信道、信道译码这三部分看成一个没有任何干扰的广义信道。这样通信系统可简化成如图,4-4,所示。,图,4-4,简化的通信系统,信源,信源编码,广义无扰信道,信道,信源译码,U,V,P(v|u,),1,基本离散信源失真,设离散无记忆信源：,信源符号通过信道传输到接收端，则接收端接收量为：,对应于一对（,u,v,），定义一个非负函数：,i,1,，,2,，,，,n,；,j,1,，,2,，,，,m,称此函数为,失真函数,（或称单个符号失真度）。,失真函数 有 个，这 个非负的,函数可以排成矩阵形式，即：,称它为,失真矩阵,。,失真函数应尽可能符合信宿的主观特性；也就是主观上的失真感觉应与失真函数的值相对应。设,x,为信源输出信息，,