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

信息定义：信息是该事物运动的状态和状态改变的方式。认识论层次的信息是同时考虑语法信息、语义信息和语用信息的全信息。全信息：同时考虑外在形式/语法信息、内在含义/语义信息、效用价值/语用信息。语法信息：事物运动状态和状态改变的方式；语义信息：事物运动状态和方式的具体含义；语用信息：事物运动状态和方式及其含义对观察者的效用价值。研究信息论的目的：提高信息系统的可靠性、有效性和安全性以便达到系统最优化。,第一章概论,单符号离散信源自信息量设离散信源X，其概率空间为如果知道事件xi已发生，则该事件所含有的自信息定义为当事件xi发生以前：表示事件xi发生的不确定性。当事件xi发生以后：表示事件xi所含有（或所提供）的信息量,第二章信源熵,联合自信息量当X和Y相互独立时，p(xiyj)=p(xi)p(yj),第二章信源熵,条件自信息量：已知yj的条件下xi仍然存在的不确定度。自信息量、条件自信息量和联合自信息量之间的关系,第二章信源熵,互信息量：yj对xi的互信息量定义为的后验概率与先验概率比值的对数。,第二章信源熵,观察者站在输出端：两个不确定度之差是不确定度被消除的部分，即等于自信息量减去条件自信息量。观察者站在输入端：观察者得知输入端发出xi前、后对输出端出现yj的不确定度的差。观察者站在通信系统总体立场上：通信后的互信息量，等于前后不确定度的差。,第二章信源熵,平均信息量信源熵：自信息的数学期望。也称为信源的信息熵/信源熵/香农熵/无条件熵/熵函数/熵。信源熵的三种物理含义信源熵H(X)是表示信源输出后每个消息/符号所提供的平均信息量；信源熵H(X)是表示信源输出前，信源的平均不确定性；用信源熵H(X)来表征变量X的随机性。,第二章信源熵,条件熵：是在联合符号集合XY上的条件自信息的数学期望。,第二章信源熵,信道疑义度H(X/Y)：表示信宿在收到Y后，信源X仍然存在的不确定度。是通过有噪信道传输后引起的信息量的损失，故也可称为损失熵。噪声熵H(Y/X)：表示在已知X的条件下，对于符号集Y尚存在的不确定性（疑义），这完全是由于信道中噪声引起的。,第二章信源熵,联合熵H(XY)：表示输入随机变量X，经信道传输到达信宿，输出随机变量Y。即收、发双方通信后，整个系统仍然存在的不确定度。,第二章信源熵,最大离散熵定理(极值性)：离散无记忆信源输出n个不同的信息符号，当且仅当各个符号出现概率相等时(即p(xi)=1/n)，熵最大。Hp(x1),p(x2),p(xn)H(1/n,1/n,1/n)=log2n出现任何符号的可能性相等时，不确定性最大。,第二章信源熵,二进制信源的熵函数H(p)为,第二章信源熵,平均互信息量定义：互信息量I(xi;yj)在联合概率P(XY)中的统计平均值。1.站在输出端：I(X;Y)收到Y前、后关于X的不确定度减少的量。从Y获得的关于X的平均信息量。2.站在输入端：I(Y;X)发出X前、后关于Y的先验不确定度减少的量。3.站在总体：I(X;Y)通信前、后整个系统不确定度减少量。,第二章信源熵,BSC信道的平均互信息量设二进制对称信道的输入概率空间为转移概率如图2.1.8所示。,第二章信源熵,平均互信息量当q不变(固定信道特性)时，可得I(X;Y)随输入概率分布p变化的曲线，如图2.1.9所示；二进制对称信道特性固定后，输入呈等概率分布时，平均而言在接收端可获得最大信息量。,第二章信源熵,当固定信源特性p时，I(X;Y)就是信道特性q的函数，如图2.1.10所示；当二进制对称信道特性q=/q=1/2时，信道输出端获得信息量最小，即等于0。说明信源的全部信息信息都损失在信道中了。这是一种最差的信道。,第二章信源熵,离散无记忆信源X的N次扩展信源的熵等于离散信源X的熵的N倍，即H(X)=H(XN)=NH(X)离散平稳信源：各维联合概率均与时间起点无关的完全平稳信源称为离散平稳信源。1.二维离散平稳信源的熵为H(X)=H(X1X2)=H(X1)+H(X2/X1)2.N维离散平稳信源的熵为H(X)=H(X1X2XN-1XN)=H(X1)+H(X2/X1)+H(X3/X1X2)+H(XN/X1X2XN-1),第二章信源熵,平均符号熵：信源平均每发一个符号提供的信息量为离散平稳有记忆信源的极限熵：当N时，平均符号熵取极限值称之为极限熵或极限信息量。用H表示，即极限熵的存在性：当离散有记忆信源是平稳信源时，极限熵等于关联长度N时，条件熵H(XN/X1X2XN-1)的极限值，即极限熵的含义：代表了一般离散平稳有记忆信源平均每发一个符号提供的信息量。,第二章信源熵,信源熵的相对率：=H/H0信源冗余度：=1=(H0H)/H0信源的冗余度表示信源可压缩的程度。,第二章信源熵,连续信源的熵为上式定义的熵在形式上和离散信源相似，也满足离散熵的主要特性，如可加性，但在概念上与离散熵有差异因为它失去了离散熵的部分含义和性质。,第二章信源熵,设信源通过一干扰信道，接收符号为Y=y1,y2，信道传递矩阵为(1)信源X中事件x1和x2分别含有的自信息量。(2)收到消息yj(j=1,2)后，获得的关于xi(i=1,2)的信息量。(3)信源X和信宿Y的信息熵。(4)信道疑义度H(X/Y)和噪声熵H(X/Y)。(5)接收到Y后获得的平均互信息量。,第二章信源熵,(1)信源X中事件x1和x2分别含有的自信息量。解：I(x1)=log2p(x1)=log20.6=0.74(bit)I(x2)=log2p(x2)=log20.4=1.32(bit)(2)收到消息yj(j=1,2)后，获得的关于xi(i=1,2)的信息量。解：p(y1/x1)=5/6p(y2/x1)=1/6p(y1/x2)=1/4p(y2/x2)=3/4p(x1y1)=p(x1)p(y1/x1)=0.65/6=0.5p(x1y2)=p(x1)p(y2/x1)=0.61/6=0.1p(x2y1)=p(x2)p(y1/x2)=0.41/4=0.1p(x2y2)=p(x2)p(y2/x2)=0.43/4=0.3p(y1)=p(x1y1)+p(x2y1)=0.5+0.1=0.6p(y2)=p(x1y2)+p(x2y2)=0.1+0.3=0.4,第二章信源熵,第二章信源熵,(3)信源X和信宿Y的信息熵。解：(4)信道疑义度H(X/Y)和噪声熵H(Y/X)。(5)接收到Y后获得的平均互信息量。,第二章信源熵,信道容量C：在信道中最大的信息传输速率，单位是比特/信道符号。单位时间的信道容量Ct：若信道平均传输一个符号需要t秒钟，则单位时间的信道容量为Ct实际是信道的最大信息传输速率。,第三章信道容量,求信道容量的方法当信道特性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)无关，而仅仅是信道转移概率的函数，只与信道统计特性有关；信道容量是完全描述信道特性的参量；信道容量是信道能够传送的最大信息量。,第三章信道容量,当n=2时的强对称离散信道就是二进制均匀信道。二进制均匀信道的信道容量为：二进制均匀信道容量曲线如图所示。,第三章信道容量,香农公式说明当信道容量一定时，增大信道带宽，可以降低对信噪功率比的要求；反之，当信道频带较窄时，可以通过提高信噪功率比来补偿。当信道频带无限时，其信道容量与信号功率成正比。,第三章信道容量,有一个二元对称信道，其信道矩阵为设该信源以1500(二元符号/秒)的速度传输输入符号。现有一消息序列共有14000个二元符号，并设p(0)=p(1)=1/2，问从信息传输的角度来考虑，10秒钟内能否将这消息序列无失真地传递完？解：信源：等概率分布1500符号/秒10秒15000(个二元符号)=15000(bit)14000个二元符号的信息量为14000(bit)信道：强对称型10秒内信道可传递信息150000.86=12900(bit)14000(bit)答：10秒钟内不能无失真传完。,第三章信道容量,失真度设离散无记忆信源为,第四章信息率失真函数,对每一对(xi,yj)，指定一个非负函数d(xi,yj)0i=1,2,nj=1,2,m称d(xi,yj)为单个符号的失真度/失真函数。表示信源发出一个符号xi，在接收端再现yj所引起的误差或失真。,第四章信息率失真函数,平均失真度定义d(xi,yj)只能表示两个特定的具体符号xi和yj之间的失真。平均失真度：平均失真度为失真度的数学期望，,第四章信息率失真函数,平均失真度意义是在平均意义上，从总体上对整个系统失真情况的描述。它是信源统计特性p(xi)、信道统计特性p(yj/xi)和失真度d(xi,yj)的函数。当p(xi)，p(yj/xi)和d(xi,yj)给定后，平均失真度就不是一个随机变量了，而是一个确定的量。如果信源和失真度一定，就只是信道统计特性的函数。信道传递概率不同，平均失真度随之改变。,第四章信息率失真函数,允许平均失真度：率失真函数中的自变量D，也就是人们规定的平均失真度的上限值。率失真函数的定义域问题就是在信源和失真函数已知的情况下，讨论允许平均失真度D的最小和最大值问题。D的选取必须根据固定信源X的统计特性P(X)和选定的失真函数d(xi,yj)，在平均失真度的可能取值范围内。,第四章信息率失真函数,常用的失真函数第一种当a=1时称为汉明失真矩阵。第二种/平方误差失真矩阵：d(xi,yj)=(yjxi)2,第四章信息率失真函数,单符号信源和单符号信道的信息率失真函数在信源和失真度给定以后，PD是满足保真度准则的试验信道集合，平均互信息I(X;Y)是信道传递概率p(yj/xi)的下凸函数，所以在PD中一定可以找到某个试验信道，使I(X;Y)达到最小，即这个最小值R(D)称为信息率失真函数，简称率失真函数。在信源给定以后，总希望在允许一定失真的情况下，传送信源所必须的信息率越小越好。从接收端来看，就是在满足保真度准则的条件下，寻找再现信源消息必须的最低平均信息量，即平均互信息的最小值。,第四章信息率失真函数,设信源，其失真度为汉明失真度，试问当允许平均失真度D=(1/2)p时，每一信源符号平均最少需要几个二进制符号(码长)？解：失真矩阵,第四章信息率失真函数,设一信源分别为0.5，0.4，和0.。（1）求二进制Huffman编码及效率。（2）求二次扩展Huffman编码及效率。解答见word文档,第五章信源编码,最佳译码准则（最大似然译码）通信是一个统计过程，纠、检错能力最终要反映到差错概率上。对于FEC方式，采用纠错码后的码字差错概率为pwe，p(C)：发送码字C的先验概率p(C/R)：后验概率若码字数为2k，对充分随机的消息源有p(C)=1/2k，所以最小化的pwe等价为最小化p(CCR)，又等价为最大化p(C=CR)；,第六章信道编码,对于BSC信道：最大化的p(C=CR)等价于最大化的p(RC)，最大化的p(RC)又等价于最小化d(R,C)，所以使差错概率最小的译码是使接收向量R与输出码字C距离最小的译码。,第六章信道编码,伴随式和错误检测用监督矩阵编码，也用监督矩阵译码：接收到一个接收字R后，校验HRT=0T是否成立：若关系成立，则认为R是一个码字；否则判为码字在传输中发生了错误；HRT的值是否为0是校验码字出错与否的依据。伴随式/监督子/校验子：S=RHT或ST=HRT。如何纠错？设发送码矢C=(Cn1,Cn2,C0)信道错误图样为E=(En1,En2,E0)，其中Ei=0，表示第i位无错；Ei=1，表示第i位有错。i=n1,n2,0。,第六章信道编码,接收字R为R=(Rn1,Rn2,R0)=C+E=(Cn1+En1,Cn2+En2,C0+E0)求接收字的伴随式（接收字用监督矩阵进行检验ST=HRT=H(C+E)T=HCT+HET由于HCT=0T，所以ST=HET总结伴随式仅与错误图样有关，而与发送的具体码字无关，即伴随式仅由错误图样决定；伴随式是错误的判别式：若S=0，则判为没有出错，接收字是一个码字；若S0，则判为有错。,第六章信道编码,构造(7,4)汉明码的一致监督矩阵并设计编、译码器。解：监督矩阵为(37)矩阵,第六章信道编码,构造(7,4)汉明码的伴随式,第六章信道编码,构造(7,4)汉明码的纠错译码电路,第六章信道编码,卷积码与分组码的不同之处在任意给定单元时刻，编码器输出的n个码元中，每一个码元不仅和此时刻输入的k个信息元有关，还与前连续m个时刻输入的信息元有关。,第六章信道编码,求(3,2,2)系统卷积码的编码电路g(1,1)=g0(1,1)g1(1,1)g2(1,1)=100g(1,2)=g0(1,2)g1(1,2)g2(1,2)=000g(1,3)=g0(1,3)g1(1,3)g2(1,3)=101g(2,1)=g0(2,1)g1(2,1)g2(2,1)=000g(2,2)=g0(2,2)g1(2,2)g2(2,2)=100g(2,3)=