信息论主要内容.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,信息理论与编码,提要,主讲：陈立旺,2011,年,6,月,信号,信息、消息、信号三者之间的关系,消息,信息,（,信号是消息的载体，信息含藏在消息之中，有信号有消息不一定有信息,）,香农信息论的主要内容,信源分类和描述,信息的定义和特性,信息量,表示其,不确定性,程度的大小，事件概率越小，信息量越大,比特,(bit,）、,奈特,(,nat,）、,铁特,(,Tet,）、,哈特,(Hart,）,信息量具有非负性和可加性,联合自信息量等于：,离散信源信息熵和联合熵的定义,H,(,X,),表示统计,平均的信息量,(,不确定性的量,),，表示平均每个符号,(,样本事件,),所提供的信息量,=,=,H,(,X,),信息熵也具有非负性和可加性,联合熵等于,(1),非负性,(,对于离散信源，连续信源不同,),(3),极值性,(,熵函数存在一个最大值，,等概分布条件,),(2),可加性,(,多信息源的熵，熵值增加,),离散熵重要性质和参数,定义信息速率：,Rt=H(X)/t bit/s,定义信息含量效率：,=H(X)/H,MAX,(X),定义信源冗余度：,=1-,离散二元信源的信息熵,平均互信息量和条件信息量的定义,从,Y,中获取的关于,X,的信息量，即,X,不确定性的减少量。,条件熵,平均的条件概率事件的自信息量条件熵，互信息量的关系,I,(,X,;,Y,),表示,从变量,Y,中所获得的,关于变量,X,的信息量,，是关于消息,X,的,不确定性的减少量,若,X=Y,；则,I,(,X,;,Y,)=,H,(,X,),。,从,Y,中获得了,X,的,全部信息,。,若,X,Y,相互独立；,I,(,X,;,Y,)=,0,。,从,Y,中得不到,X,的信息。,H,(,X,|,Y,),表示,变量,Y,已知的条件下,变量,X,的平均信息量，,是关于消息,X,的,不确定性的量,。,若,X=Y,；,H,(,X,|,Y,)=0,。,变量,Y,完全确定,了变量,X,的样值。,若,X,Y,相互独立；,H,(,X,|,Y,)H,(,X,),。,X,的信息量与,Y,无关。,I,(,X,;,Y,),与各个信息熵的关系,H,(,XY,),H,(,X,),H,(,Y,),H,(,Y,|,X,),H,(,X,|,Y,),(1),非负性,(2),互易性,(,对称性,),平均互信息量,I,(,X,;,Y,),的性质,不具有非负性,(3),凸函数性,当,p,(,y,|,x,),给定时，,I,(,X,;,Y,),是,p,(,x,),的上凸函数。,研究信道容量的理论基础,当,p,(,x,),给定时，,I,(,X,;,Y,),是,p,(,y,|,x,),的下凸函数。,研究信源的信息率失真函数的理论基础,相对熵（微分熵）,对相对熵的说明,非绝对值，而为相对值。定义形式相统一。,H,c,(,X,),的取值：,可能不存在,，,可能为负值,。,连续信源的相对熵,微分熵性质,可加性：,H,C,(XY)=H,C,(X)+H,C,(Y|X)=H,C,(Y)+H,C,(X|Y),幅值（峰值）受限时的最大微分熵：,随机变量服从均匀分布时获得最大微分熵,功率（方差）受限时的最大微分熵：,随机变量服从高斯分布时获得最大微分熵（,P=,2,+,2,）,(,随机,),信源的分类方法,从消息变量取值的连续性分：,离散信源和连续信源,从连续信源输出时间上的连续性分：,连续信源和波形信源,从离散信源的消息序列的长度来分：,单符号信源和序列（扩展）信源从离散信源序列之间的有无相关性分：,无记忆信源,(DMS),和有记忆信源,从离散有记忆信源序列的相关程度分：,平稳信源、,M,阶,Markov,信源、,马尔可夫信源：,马,尔可夫,链定义,：,1),马氏链的当前状态只与前一个状态有关，,2),马氏链是时间离散状态离散的随机过程,马尔可夫信源定义,：,1,）信源状态由当前输出符号和前一时刻信源状态唯一确定，,2,）某一时刻信源符号的输出只与当前的信源状态有关，与以前的状态无关,m,阶马氏源,：是指其输出某一符号的概率,只与此前的,m,个符号有关,。,马氏源与马氏链的关系,：马氏源一般可用马氏链来描述。,若是一阶,马尔可夫信源，一个符号对应一个状态，,若是,m,阶,马尔可夫信源，,m,个符号对应一个状态,。,齐次马氏链,(,时齐马氏链,),：,状态,转移概率与时间点无关：,P,ij,(m,n,)=P,ij,(K),齐次马氏链的表示方法,转移概率矩阵,状态转移图,由状态,j,转移到状态,2,的概率；,非负,=1,网格图,状态转移图与矩阵有一一对应关系,每时刻的网格节点与马氏链的状态一一对应,定义,:,若对任意整数,m,n,马氏链的状态分布满足,则称 为,平稳分布,或稳态分布，,J,为状态数,平稳,齐次,马氏链,：,为平稳状态分布,行矢量，,k,为转移步数,平稳齐次,马氏链,的分布,状态的概率分布与时间点无关,离散信道,(,数字信道,),输入输出空间为离散。,连续信道,：状态集合连续，时间集合离散。,模拟信道,(,波形信道,),：输入输出空间为连续。,有记忆信道,：输出,Y,不仅与当前的输入,X,有关，而与前面的输入有关。,无记忆信道,：输出,Y,仅与当前的输入,X,有关，而且与前面的输入无关。,信道的数学模型和分类,离散无记忆信道的信道容量,定理,2,：,对于离散对称和准对称信道，达到信道容量的输入分布为等概分布。,计算：,“,离散对称,”,和,“,准对称信道,”,“,无损信道,”,和,“,确定信道,”,“,独立并联信道,”,和,“,和信道,”,。,对称信道,：信道转移矩阵,P,中所有的行都是同一组元素的不同排列，所有的列也是同一组元素的不同排列。,准对称信道,：设,B,为信道转移矩阵,P,的列集合，如果将,B,划分成,m,个子集，而用每一个子集构成的矩阵所对应的信道都是对称信道,H,(,X,|,Y,),称为信道的“,疑义度,”或“,损失熵,”,它表示信息在信道传输过程中的损失，又表示根据输出变量,Y,不能确定输入变量,X,的样值，有疑义。,H,(,Y,|,X,),称为信道的“,散布度,”或“,噪声熵,”,从信道的输出,Y,信息中减去噪声干扰值就得到关于输入的信息，即,H,(,Y,|,X,),类似于噪声；它表示根据,X,不能确定,Y,的程度，称为散布度。,信道,H,(,X,|,Y,),和,H,(,Y,|,X,)的物理意义,费诺（,Fano,）不等式,离散无记忆信道信道疑义度,H(X|Y,),与差错率,Pe,满足如下不等式：,H(X|Y)H(Pe,1-Pe)+Pelog(n-1),，,n,是输入符号个数,应用,1,：信道编码逆定理：证当,RC,时，则不可能找到一种编码方法及译码准则，使信道输出端的平均错误译码概率达到任意小,应用,2,：,求信息率失真函数：,R(D,),R(D)=,min,I(X,Y,)=,min,H(X,)-H(X|Y),R(D)=H(X)-H(Pe,1-Pe)-Pelog(n-1),无损信道和确定信道,损失熵为“,0”,，称为,无损信道,噪声熵为“,0”,，称为,确定信道,损失熵和噪声熵都为“,0”,，,无损确定信道,独立并联信道,特点：,积信道,:,同时多输入，多输出,。,容量：,独立并联信道,和信道,特点：,随机输入,N,个信道中的一个，合成一个信道,。,容量：,分信道的使用概率：,和信道,结论：,（,1,）,带宽一定时，信道的,最大传输率,C,是信噪比的函数。,此时提高最大信息传输率的方法是提高信噪比。,（,2,）信噪比确定时，信道容量与带宽成正比。,此时提高最大信息传输率的方法是提高带宽。,（,3,）对于有确定信道容量,C,的信道，可以用,带宽,B,与,信噪比,S/N,的不同组合来传输信息。,如减少带宽，则必须发送较大功率的信号。如增大带宽，则同样的信道容量能够用较小功率的信号传输，即宽带系统具有良好的抗干扰性。,香农公式意义,唯一可译码、即时码、异前缀码和,非续长码,唯一可译码,：一个码的任意一串有限长的码符号序列 只能被唯一地译成所对应的信源符号序列。,即时码,：唯一可译码，译码时无需参考后续的码符号就能立即作出译码判断。,异前缀码,：码前缀不是任意其他码字（即非续长码）。可以在无延时的情况下解码。,存在唯一可译码的充要条件为,(,克拉夫特,Kraft,不等式,),N,次扩展信源,S,N,=,a,1,a,2,a,qN,，,共有,q,N,个符号序列。,设码符号集为,X,=,x,1,x,2,x,r,，,长度为,l,的码符号序列,W=W,1,W,2,W,qN,，,W,i,=(,x,i,1,x,i,2,x,il,),x,i,1,x,i,2,x,il,X,。,若要求编得的等长码是唯一可译码则必须满足,（理解钥匙：码字的组合数不小于信源符号总数）,q,N,r,l,或,单符号,平均码长满足：,等长编码及其无失真编码条件,定理,3,（,单符号信源的变长编码定理,）,若有一离散无记忆信源,S,具有熵,H,（,S,）,，,并有,r,个码符号的符号集,X,=,x,1,x,2,x,r,，,则总可以找到一种无失真编码方法，构成唯一可译码，使其平均码长满足,定理,4,（变,长无失真信源编码定理,香农第一编码定理,）,离散无记忆信源,S,的,N,次,扩展信源,SN,=,a,1,a,2,a,qN,，共有,q,N,个,符号序列，具有熵,H,（,S,N,）,，并有,r,个码符号的符号集,X,=,x,1,x,2,x,r,。,若对信源,S,N,（即信源输出的是,N,长的符号序列）进行编码，总可以找到一种编码方法，构成唯一可译码，使信源,S,中每个信源符号所需的码字平均长度满足,霍夫曼码的编码方法,二进制霍夫曼码的的编码方法，它的编码步骤如下：,（,1,）将,q,个信源符号按概率值的大小以递减次序排列起来，设,p,1,p,2,p,q,（,2,）,用,0,和,1,码符号分别代表概率最小的两个信源符号,，并将这,两个概率最小的信源符号合并一个符号,，从而得到包含,q,1,个符号的新信源,-,-,缩减信源,S,。,（,3,）,把缩减信源,S,的符号,仍按概率值大小以递减次序,排列，再将其最后二个概率最小的符号合并成一个符号，并分别用,0,和,1,码符号表示，这样又得到,q,2,个符号的新缩减信源,S,。,（,4,）,依次继续下去，直至信源最后只剩两个符号为止。将这最后两个信源符号分别用,0,和,1,码符号表示。然后,从最后一级缩减信源开始，向前返回，就得出各信源符号所对应的码符号序列，即得到对应的码字,。,费诺（,Fano,）,码,的编码方法,（,1,）将信源符号以概率递减次序排列起来,p,1,p,2,p,q,（,2,）,将,排列好的信源符号划分成两大组使每组的概率和近似相同，并各赋于一个二进码符号,“,0,”,和,“,1,”,。,（,3,）,将每一大组的信源符号再分成两级，使同一组的两个小组的概率和近似相同，并又各赋于一个二进码符号,“,0,”,和,“,1,”,。,（,4,）,如此下去，直至每组只剩下一个信源符号为止。这样，信源符号所对应的码符号序列就为编得的码字。,香农编码,（,1,）将信源符号以概率递减次序排列起来,p,1,p,2,p,q,（,2,）对第,1,个符号编码，,取,log1/P,1,的整数,(,不小于该值,),为码长，,取累积概率,P1,，,=0,。将,P1,转换为二进制数的小数位作为码字（以,2,乘小数位取整，再乘得第二位，至,L,位）。,（,3,）取,log1/P2,的整数为码长，,P1,，,加第,1,个符号的概率,P1,所得的累积概率,P2,，,，,作为对第,2,个字的编码依据。,（,4,）取,log1/Pi,的整数为码长，,P,i-1,，,再加第,i-1,个符号的概率,P,i-1,所得的累积概率,Pi,，,，,作为对第,i,个字的编码依据，重复第一步。,（,5,）如此下去，直至最后一个信源符号为止。这样，信源符号所对应的码符号序列就为编得的码字。,几种实用的信源编码,游程编码,用于文件传真（霍夫曼编码）,算术编码,针对小集合信源（香农编码）,基于字典的编码,针对无法确知信源的统计特性的自适应编码（,LZ,和,LZW,编码）,典型的译码准则：,最佳译码准则可以使平均译码概率达到最小值。当译码准则数量很大时，选择译码准则的运算量大，不简单。,“最大后验概率准则”,已知后验概率分布时,“最大联合概率准则”,已知联合概率分布时,“最大转移概率准则”,已知转移概率分布时，也叫,“最大似然准则”,最小汉明距离准则,等价于似然准则,用于卷积译码,最小欧氏距离准则,用于,TCM,译码,有噪声信道编码定理（香农第二编码定理）,如一个离散有噪声信道有,n,个输入符号，,m,个输出符号，信道容量为,C,。,当,信道的熵速率,RC,时，只要码长足够长，总可以找到一种编码方法及译码准则，使信道输出端的平均错误译码概率达到任意小，,pe,=,。,当,R,C,时，则不可能找到一种编码方法及译码准则，使信道输出端的平均错误译码概率达到任意小。,信源编码定理的讨论,汉明码和最小汉明距离,循环码和,CRC,码,BCH,码和,RS,码,卷积码及其,Viterbi,译码,TCM,映射和译码方法,几种实用的信道编码概念,失真（度）函数的定义,失真度（失真函数）定义,失真矩阵,d,（,失真度的矩阵表示,）,d,(,u,i,v,j,),0,（即非负性）,i,=1,，,2,，,，,n,j,=1,，,2,，,，,m,平均失真度定义,信息,率失真函数,R,（,D,）,的定义,率失真函数,定义（,D,为允许信道）,信源,信道,信源编码器,（,试验信道,）,p,(,v,|,u,),无噪信道,R,(,D,),的性质,：连续、单调下降、下凸,连续信源实际熵无穷大而信道容量有限，故不可能无失真压缩。图,b,为一般情形,R,（,D,）,的定义域,（,D,min,D,max,）,率失真函数,R,(,D,),的,性质,D,MIN,是给定失真矩阵,d,和输入变量概率分布,p(u,),条件下的最小平均失真度。某些情况下,D,MIN,=0,。等于,失真度矩阵每行最小值所构成的列矩阵与输入分布的乘积。,D,MAX,是,I(U,V),0,时的最大平均失真度。,也是,I(U,V)=0,时的最小平均失真度,，不指,D,随,p(v/u,),变化的最大值。等于,失真矩阵与输入分布相乘后所构成的行矩阵元素的最小值,上图含义：,（已知输入概率分布和失真度矩阵的条件下）,1,）,若给定接收端,允许的平均失真度,D,，则知道实验信道输出的,最小信息量,I,（,minI(U,V,)=R(D),，,I,在曲线之上和在,H(X),之下,）,。,2,）若已知从接收端,得到的信息量,I,，则知道信道可能产生的,最小平均失真度,D,（,D(R)=,minD(p,y|x,),，如,I=0,的最小,D,值为,D,max,）,。,限失真信源编码定理,(,香农第三定理,),设离散无记忆信源的率失真函数为,R,（,D,）,，,如果信源编码后平均每个信源符号的,信息传输率,R,R,（,D,）,，,则一定存在一种信源编码,C,，,使编码后的平均失真度,d,满足：,限失真信源编码定理,设离散无记忆信源的率失真函数为,R,（,D,）,，,如果信源编码后平均每个信源符号的信息传输率,R,R,（,D,）,，,则无论采用什么编译码方式，一定有平均失真度,d,成立：,限失真信源编码,逆,定理,限失真信源信道编码定理,设离散无记忆信源的信息率失真函数为,R(D),，离散无记忆信道的容量为,C,。,若满足,C,R(D,),，则存在一种编码，使信源序列通过信道传输后的平均失真,D,（,D=R,-1,(C),）,若,CD,（,D=R,-1,(C),）,信道容量,C,给定，若信源熵H(X)C,，那么直接传输即有差错，或者先进行有失真压缩使得,H(X),C,，再进行无失真传输。,例,9.16,：二元信源的符号概率为,1/4,和,3/4,，每秒发出,1.5,符号，通过一个二元对称信道传输，信道每秒使用,2,次；求信源符号通过信道传输后的最小平均失真。设失真测度为汉明失真。,解：利用信源信道编码定理：有失真时,DR,-1,(C,),二元对称信道的容量为：,C=2,(1-H(p,e,),bit/s,，,p,e,=1/4,时,C=0.38bit/s,。,汉明失真测度时,信源率失真函数为：,R(D)=1.5(H(1/4)-H(D),bit/s,。,其中：,D=D,MAX,=1/4,时，,R(D)=0bit/s,。,D=D,MIN,=0,时，,R(D)=0.285bit/s,所以,DR,-1,(C)=R,-1,(2-2H(p,e,),其中,p,e,0.29,时，最小,D=0,。当,p,e,=0.5,，最小,D=1/4,。,