信息论与编码-第24讲-总复习.ppt

2019/11/20,1,信息与消息和信号的区别消息：是指包含有信息的语言、文字和图像等，可表达客观物质运动和主观思维活动的状态。信号：把消息变换成适合信道传输的物理量，这种物理量称为信号（如电信号、光信号、声音信号等）。,第一章概论,2019/11/20,2,信息“本体论”层次定义：信息是该事物运动的状态和状态改变的方式。认识论层次的信息是同时考虑语法信息、语义信息和语用信息的全信息。全信息：同时考虑外在形式/语法信息、内在含义/语义信息、效用价值/语用信息，称为全信息。语法信息：事物运动状态和状态改变的方式；语义信息：事物运动状态和方式的具体含义；语用信息：事物运动状态和方式及其含义对观察者的效用。研究信息论的目的：它的主要目的是提高信息系统的可靠性、有效性和安全性以便达到系统最优化。,第一章概论,2019/11/20,3,单符号离散信源自信息量用概率测度定义信息量设离散信源X，其概率空间为如果知道事件xi已发生，则该事件所含有的自信息定义为当事件xi发生以前：表示事件xi发生的不确定性。当事件xi发生以后：表示事件xi所含有（或所提供）的信息量,第二章信源熵,2019/11/20,4,联合自信息量当X和Y相互独立时，p(xiyj)=p(xi)p(yj),第二章信源熵,2019/11/20,5,条件自信息量：已知yj的条件下xi仍然存在的不确定度。自信息量、条件自信息量和联合自信息量之间的关系,第二章信源熵,2019/11/20,6,互信息量：yj对xi的互信息量定义为的后验概率与先验概率比值的对数。,第二章信源熵,2019/11/20,7,观察者站在输出端：两个不确定度之差是不确定度被消除的部分，即等于自信息量减去条件自信息量。观察者站在输入端：观察者得知输入端发出xi前、后对输出端出现yj的不确定度的差。观察者站在通信系统总体立场上：通信后的互信息量，等于前后不确定度的差。,第二章信源熵,2019/11/20,8,平均信息量信源熵：自信息的数学期望。也称为信源的信息熵/信源熵/香农熵/无条件熵/熵函数/熵。信息熵的意义：信源的信息熵H是从整个信源的统计特性来考虑的。它是从平均意义上来表征信源的总体特性的。对于某特定的信源，其信息熵只有一个。不同的信源因统计特性不同，其熵也不同。信源熵的三种物理含义信源熵H(X)是表示信源输出后每个消息/符号所提供的平均信息量；信源熵H(X)是表示信源输出前，信源的平均不确定性；用信源熵H(X)来表征变量X的随机性。,第二章信源熵,2019/11/20,9,条件熵：是在联合符号集合XY上的条件自信息的数学期望。,第二章信源熵,2019/11/20,10,信道疑义度H(X/Y)：表示信宿在收到Y后，信源X仍然存在的不确定度。是通过有噪信道传输后引起的信息量的损失，故也可称为损失熵。噪声熵H(Y/X)：表示在已知X的条件下，对于符号集Y尚存在的不确定性（疑义），这完全是由于信道中噪声引起的。,第二章信源熵,2019/11/20,11,联合熵H(XY)：表示输入随机变量X，经信道传输到达信宿，输出随机变量Y。即收、发双方通信后，整个系统仍然存在的不确定度。,第二章信源熵,2019/11/20,12,最大离散熵定理(极值性)：离散无记忆信源输出n个不同的信息符号，当且仅当各个符号出现概率相等时(即p(xi)=1/n)，熵最大。Hp(x1),p(x2),p(xn)H(1/n,1/n,1/n)=log2n出现任何符号的可能性相等时，不确定性最大。,第二章信源熵,2019/11/20,13,平均互信息量定义：互信息量I(xi;yj)在联合概率空间P(XY)中的统计平均值。从一个事件获得另一个事件的平均互信息需要消除不确定度，一旦消除了不确定度，就获得了信息。,第二章信源熵,2019/11/20,14,站在输出端：I(X;Y)收到Y前、后关于X的不确定度减少的量。从Y获得的关于X的平均信息量。站在输入端：I(Y;X)发出X前、后关于Y的先验不确定度减少的量。站在总体：I(X;Y)通信前、后整个系统不确定度减少量。,第二章信源熵,2019/11/20,15,BSC信道的平均互信息量设二进制对称信道的输入概率空间为转移概率如图2.1.8所示。,第二章信源熵,2019/11/20,16,平均互信息量当q不变(固定信道特性)时，可得I(X;Y)随输入概率分布p变化的曲线，如图2.1.9所示；二进制对称信道特性固定后，输入呈等概率分布时，平均而言在接收端可获得最大信息量。,第二章信源熵,2019/11/20,17,当固定信源特性p时，I(X;Y)就是信道特性q的函数，如图2.1.10所示；当二进制对称信道特性q=/q=1/2时，信道输出端获得信息量最小，即等于0。说明信源的全部信息信息都损失在信道中了。这是一种最差的信道。,第二章信源熵,2019/11/20,18,离散无记忆信源X的N次扩展信源的熵等于离散信源X的熵的N倍，即H(X)=H(XN)=NH(X)离散平稳信源：各维联合概率均与时间起点无关的完全平稳信源称为离散平稳信源。二维离散平稳信源的熵为,第二章信源熵,2019/11/20,19,平均符号熵：信源平均每发一个符号提供的信息量为离散平稳有记忆信源的极限熵：当N时，平均符号熵取极限值称之为极限熵或极限信息量。用H表示，即极限熵的存在性：当离散有记忆信源是平稳信源时，极限熵等于关联长度N时，条件熵H(XN/X1X2XN-1)的极限值，即极限熵的含义：代表了一般离散平稳有记忆信源平均每发一个符号提供的信息量。,第二章信源熵,2019/11/20,20,m阶马尔可夫信源m阶马尔可夫信源的极限熵有限齐次马尔可夫链各态历经定理有关问题的说明H并非在任何情况下都存在。对n元m阶马尔可夫信源来说，只有状态极限概率p(ej)，j=1,2,nm都存在时，方能计算出H。从理论上可以证明，如果m阶马尔可夫信源稳定后具有各态历经性，则状态极限概率p(ej)可根据下式求出。,第二章信源熵,2019/11/20,21,信源熵的相对率：=H/H0信源冗余度：=1=(H0H)/H0信源的冗余度表示信源可压缩的程度。,第二章信源熵,2019/11/20,22,随机过程x(t)中某一样本函数x(t)的时间平均值定义：随机过程x(t)在某时刻ti所取的随机变量的统计平均值/集平均定义：遍历的随机过程：时间平均与统计平均相等，即,第二章信源熵,2019/11/20,23,连续信源的熵为上式定义的熵在形式上和离散信源相似，也满足离散熵的主要特性，如可加性，但在概念上与离散熵有差异因为它失去了离散熵的部分含义和性质。,第二章信源熵,2019/11/20,24,连续信源熵有关问题说明连续信源熵并不是实际信源输出的绝对熵；连续信源的绝对熵还有一项正的无限大量，虽然log2(ba)小于0，但两项相加还是正值，且一般还是一个无限大量。因为连续信源的可能取值数有无限多，若假定等概率，确知其输出值后所得信息量也将为无限大；Hc(X)已不能代表信源的平均不确定度，也不能代表连续信源输出的信息量。连续信源熵的意义这种定义可以与离散信源在形式上统一起来；在实际问题中常常讨论的是熵之间的差值问题，如信息变差、平均互信息等。在讨论熵差时，两个无限大量互相抵消。所以熵差具有信息的特征；连续信源的熵Hc(X)具有相对性，因此Hc(X)也称为相对熵。,第二章信源熵,25,例2.4已知信源空间信道特性如图2.4所示，求在该信道上传输的疑义度H(X|Y)，噪声熵H(Y|X)和共熵H(XY)。,图2.4例2.4的信道特性,解（1）根据P(xiyj)=P(xi)P(yj|xi)，求各联合概率，得P(x1y1)=P(x1)P(y1|x1)=0.50.98=0.49P(x1y2)=P(x1)P(y2|x1)=0.50.02=0.01P(x2y1)=P(x2)P(y1|x2)=0.50.20=0.10P(x2y2)=P(x2)P(y2|x2)=0.50.80=0.40（2）求Y集合中各符号的概率，得P(y1)=P(x1)P(y1|x1)+P(x2)P(y1|x2)=0.50.980.50.2=0.59P(y2)=10.59=0.41,（3）求各种熵，有,H(X|Y)=H(XY)H(Y)=1.430.98=0.45比特H(Y|X)=H(XY)H(X)=1.431=0.43比特,2019/11/20,29,信道容量C：在信道中最大的信息传输速率，单位是比特/信道符号。单位时间的信道容量Ct：若信道平均传输一个符号需要t秒钟，则单位时间的信道容量为Ct实际是信道的最大信息传输速率。,第三章信道容量,2019/11/20,30,求信道容量的方法当信道特性p(yj/xi)固定后，I(X;Y)随信源概率分布p(xi)的变化而变化。调整p(xi)，在接收端就能获得不同的信息量。由平均互信息的性质已知，I(X;Y)是p(xi)的上凸函数，因此总能找到一种概率分布p(xi)（即某一种信源），使信道所能传送的信息率为最大。C和Ct都是求平均互信息I(X;Y)的条件极大值问题，当输入信源概率分布p(xi)调整好以后，C和Ct已与p(xi)无关，而仅仅是信道转移概率的函数，只与信道统计特性有关；信道容量是完全描述信道特性的参量；信道容量是信道能够传送的最大信息量。,第三章信道容量,2019/11/20,31,当n=2时的强对称离散信道就是二进制均匀信道。二进制均匀信道的信道容量为：二进制均匀信道容量曲线如图3.2.5所示。,第三章信道容量,2019/11/20,32,香农公式说明当信道容量一定时，增大信道带宽，可以降低对信噪功率比的要求；反之，当信道频带较窄时，可以通过提高信噪功率比来补偿。当信道频带无限时，其信道容量与信号功率成正比。,第三章信道容量,2019/11/20,33,信道编码定理：若有一离散无记忆平稳信道，其容量为C，输入序列长度为L，只要待传送的信息率RC时，任何编码的Pe必大于零，当L，Pe1。信道编码定理说明：同无失真信源编码定理类似，信道编码定理也是一个理想编码的存在性定理。它指出信道容量是一个临界值，只要信息传输率不超过这个临界值，信道就可几乎无失真地把信息传送过去，否则就会产生失真。,第三章信道容量,2019/11/20,34,失真度设离散无记忆信源为,第四章信息率失真函数,2019/11/20,35,对每一对(xi,yj)，指定一个非负函数d(xi,yj)0i=1,2,nj=1,2,m称d(xi,yj)为单个符号的失真度/失真函数。表示信源发出一个符号xi，在接收端再现yj所引起的误差或失真。,第四章信息率失真函数,2019/11/20,36,平均失真度定义d(xi,yj)只能表示两个特定的具体符号xi和yj之间的失真。平均失真度：平均失真度为失真度的数学期望，,第四章信息率失真函数,2019/11/20,37,平均失真度意义是在平均意义上，从总体上对整个系统失真情况的描述。它是信源统计特性p(xi)、信道统计特性p(yj/xi)和失真度d(xi,yj)的函数。当p(xi)，p(yj/xi)和d(xi,yj)给定后，平均失真度就不是一个随机变量了，而是一个确定的量。如果信源和失真度一定，就只是信道统计特性的函数。信道传递概率不同，平均失真度随之改变。,第四章信息率失真函数,2019/11/20,38,允许平均失真度：率失真函数中的自变量D，也就是人们规定的平均失真度的上限值。率失真函数的定义域问题就是在信源和失真函数已知的情况下，讨论允许平均失真度D的最小和最大值问题。D的选取必须根据固定信源X的统计特性P(X)和选定的失真函数d(xi,yj)，在平均失真度的可能取值范围内。,第四章信息率失真函数,2019/11/20,39,常用的失真函数第一种当a=1时称为汉明失真矩阵。第二种/平方误差失真矩阵：d(xi,yj)=(yjxi)2,第四章信息率失真函数,2019/11/20,40,单符号信源和单符号信道的信息率失真函数在信源和失真度给定以后，PD是满足保真度准则的试验信道集合，平均互信息I(X;Y)是信道传递概率p(yj/xi)的下凸函数，所以在PD中一定可以找到某个试验信道，使I(X;Y)达到最小，即这个最小值R(D)称为信息率失真函数，简称率失真函数。在信源给定以后，总希望在允许一定失真的情况下，传送信源所必须的信息率越小越好。从接收端来看，就是在满足保真度准则的条件下，寻找再现信源消息必须的最低平均信息量，即平均互信息的最小值。,第四章信息率失真函数,2019/11/20,41,求信息率失真函数的方法信息率失真函数R(D)是假定信源给定的情况下，在用户可以容忍的失真度内再现信源消息所必须获得的最小平均信息量。它反映的是信源可压缩程度。率失真函数一旦找到，就与求极值过程中选择的试验信道不再有关，而只是信源特性的参量。不同的信源，其R(D)是不同的。,第四章信息率失真函数,2019/11/20,42,对偶问题：信道容量和信息率失真函数的问题，都是求平均互信息极值问题。分三个方面说明：求极值问题平均互信息I(X;Y)是信源概率分布p(xi)(i=1,2,n)的上凸函数，信道容量就是在固定信道情况下，求平均互信息极大值的问题，即I(X;Y)又是信道转移概率分布p(yj/xi)(i=1,2,n;j=1,2,m)的下凸函数，信息率失真函数就是在试验信道（满足保真度准则的信道）中寻找平均互信息极小值的问题，即,第四章信息率失真函数,2019/11/20,43,特性信道容量C一旦求出后，就只与信道转移概率p(yj/xi)有关，反映信道特性，与信源特性无关；信息率失真函数R(D)一旦求出后，就只与信源概率分布p(xi)有关，反映信源特性，与信道特性无关。解决的问题信道容量是为了解决通信的可靠性问题，是信息传输的理论基础，通过信道编码增加信息的冗余度来实现；信息率失真函数是为了解决通信的有效性问题，是信源压缩的理论基础，通过信源编码减少信息的冗余度来实现。,第四章信息率失真函数,2019/11/20,44,限失真信源编码定理：设一离散平稳无记忆信源的输出随机变量序列为X=(X1,X2,XL)，若该信源的信息率失真函数是R(D)，并选定有限的失真函数。对于任意允许平均失真度D0，和任意小的0，当信息率RR(D)，只要信源序列长度L足够长，一定存在一种编码方式C，使译码后的平均失真度；反之，若Rt)的充要条件是码的最小距离为dmin=t+l+1或t+l=dmin1(6.2.23)证明：因为dmin2t+1，根据最小距离与纠错能力定理，该码可纠t个错误。因为dminl+1，根据最小距离与检错能力定理，该码有检l个错误的能力。纠错和检错不会发生混淆：设发送码字为V，接收字为R，实际错误数为l，且tt+1t(6.2.24)因而不会把R误纠为U。,第六章信道编码,2019/11/20,69,几何意义：,第六章信道编码,2019/11/20,70,循环码的码矢的i次循环移位与码多项式的关系上式表明：码矢循环一次的码多项式C(1)(x)是原码多项式C(x)乘以x除以(xn+1)的余式。写作因此，C(x)的i次循环移位C(i)(x)是C(x)乘以xi除以(xn