（精选幻灯片）信息论 总复习_new

1,总复习,1概论2信源及信息熵3信源编码4信道及信道容量5信道编码6信息率失真函数7考试情况,2,信息与消息和信号的区别消息：是指包含有信息的语言、文字和图像等，可表达客观物质运动和主观思维活动的状态。信号：把消息变换成适合信道传输的物理量，这种物理量称为信号（如电信号、光信号、声音信号等）。信息是事物运动状态和状态改变的方式。,第1章概论,3,信息信息是事物运动状态和状态改变的方式。研究信息论的目的：它的主要目的是提高信息系统的可靠性、有效性和安全性以便达到系统最优化。在通信系统中形式上传输的是消息，但实质上传输的是信息。消息只是表达信息的工具，载荷信息的客体。,4,编码器,信宿,信道,消息,干扰,消息,通信系统模型,信源,信号,解码器,信号+干扰,噪声源,信息论的研究对象:通信系统模型.,信源信道加密,信源信道解密,通信系统的基本任务要求可靠:要使信源发出的消息经过传输后，尽可能准确地、不失真或限定失真地再现在接收端有效:用尽可能短的时间和尽可能少的设备来传输最大的消息,5,单符号离散信源自信息量用概率测度定义信息量，设离散信源X，其概率空间为如果知道事件xi已发生，则该事件所含有的自信息定义为,第2章信源熵,6,联合自信息量当X和Y相互独立时，p(xiyj)=p(xi)p(yj),7,条件自信息量：已知yj的条件下xi仍然存在的不确定度。自信息量、条件自信息量和联合自信息量之间的关系,8,互信息量：yj对xi的互信息量定义为的后验概率与先验概率比值的对数。,两个不确定度之差是不确定度被消除的部分，即等于自信息量减去条件自信息量。,9,平均信息量信源熵：自信息的数学期望。也称为信源的信息熵/信源熵/熵。信息熵的意义：信源的信息熵H是从整个信源的统计特性来考虑的。它是从平均意义上来表征信源的总体特性的。对于某特定的信源，其信息熵是唯一的。不同的信源因统计特性不同，其熵也不同。,10,条件熵：是在联合符号集合XY上的条件自信息的数学期望。,联合熵H(XY)：表示输入随机变量X，经信道传输到达信宿，输出随机变量Y。即收、发双方通信后，整个系统仍然存在的不确定度。,11,信道疑义度H(X|Y)：表示信宿在收到Y后，信源X仍然存在的不确定度。是通过有噪信道传输后引起的信息量的损失，故也可称为损失熵。噪声熵H(Y|X)：表示在已知X的条件下，对于符号集Y尚存在的不确定性，这完全是由于信道中噪声引起的。唯一确定信道噪声所需要的平均信息量。,12,平均互信息量定义：互信息量I(xi;yj)在联合概率空间P(XY)中的统计平均值。从一个事件获得另一个事件的平均互信息需要消除不确定度，一旦消除了不确定度，就获得了信息。,13,平均互信息和熵的关系,14,数据处理定理（信息不增原理）,当消息通过多级处理器时,随着处理器数目的增多,输入消息和输出消息之间的平均互信息量趋于变小。信息不增,I(X;Z)I(X;f(Z)=I(X;Y)H(X|Z)H(X|f(Z)=H(X|Y),15,最大离散熵定理(极值性)：离散无记忆信源输出n个不同的信息符号，当且仅当各个符号出现概率相等时(即p(xi)=1/n)，熵最大。Hp(x1),p(x2),p(xn)logn,16,二进制信源的熵函数H(p)为,17,BSC信道的平均互信息量设二进制对称信道的输入概率空间为,18,19,连续信源的熵为,定义的熵在形式上和离散信源相似。连续信源熵并不是实际信源输出的信息量(绝对熵)；Hc(X)也称为相对熵,连续信源的信息量为无限大；Hc(X)已不能代表信源的平均不确定度，也不能代表连续信源输出的信息量。,20,限峰值的最大熵定理:若信源的N维随机变量的取值在一定的范围之内，则在有限的定义域内，均匀分布的连续信源具有最大熵。限平均功率的最大熵定理：若信源输出信号的平均功率P或方差受限，则其输出信号幅度的概率密度函数为高斯分布时，信源具有最大熵值。限均值的最大连续熵定理：若连续信源X输出非负信号的均值受限，则其输出信号幅度呈指数分布时，连续信源X具有最大熵值。,21,离散信源的无失真编码实质上是一种统计匹配编码。信息论指出信源中的统计多余度主要决定于以下两个主要因素：一是消息概率分布的非均匀性，另一个是消息间的相关性。对无记忆信源主要决定于概率分布的非均匀性，但是，对于有记忆信源，两者都起作用，且后者相关性更加重要。,第3章信源编码,22,Def.可达速率：对于给定的信源和编码速率R及任意0，若存在L0、()、D()，使当码长LL0时，PeH(U)，则R是可达的；若RH(U),契比雪夫不等式的右边是理论上的误码率的上限，必须小于给定的误码率才能保证到达编码性能要求,25,定长编码定理,其中差错率满足如下式子,26,凡是能载荷一定的信息量,且码字的平均长度最短,可分离的变长码的码字集合就称为最佳变长码.必须将概率大的信息符号以短的码字,将概率小的信息符号以长的码字.主要有:香农-费诺(Shannon-Fano),哈夫曼(Huffman)编码等,唯一可译性的两种解决方法Def.逗点码Def.异字头码,27,2香农费诺编码,费诺编码步骤如下：a.将概率按从大到小的顺序排列，令b.按编码进制数将概率分组，使每组概率尽可能接近或相等。c.给每一组分配一位码元。d.将每一分组再按同样原则划分，重复步骤b和c，直至概率不再可分为止。,28,3哈夫曼编码,a.将信源符号按概率从大到小的顺序排列，令b.给两个概率最小的信源符号p(xn-1)和p(xn)各分配一个码位0和1，将这两个符号合并成一个新符号，其概率之和作为新符号的概率，得到(n1)个符号。c.将缩减信源符号按概率排列，重复步骤a,b。直至缩减信源只剩两个符号为止。d.从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。,注意3进制编码？,29,4算术编码,算术编码是计算序列的累计分布，用累计分布值表示序列，所以称为算术编码以二元信源输出序列的编码为例01110,u对应区间的宽度等于符号序列的概率,30,算术编码,递推公式编码P(u=bbbbbbaa)=0.7560.252=F(a)=0,F(b)=0.25,H=HP(ul+1),G=G+HF(al+1),31,LZ编码,利用字典编码方法信源符号A=(a1aK)将序列分为不同的段取最短长度的连续符号构成段，保证互不相同。先取一个符号分段，若与前面段相同，就再取一个符号，直至序列结束得到字典表，码字由段号加后一个符号组成。单符号的码字，段号为0,32,LZ编码的特点特点一编码效率可以接近信息熵的上限。特点二不需要事先知道信源的概率分布。特点三用一种巧妙的方式使用字典技术。特点四文件越小，压缩比例越小；文件越大，压缩比例越大。LZ编码的应用领域几乎垄断了整个通用数据压缩领域，如PKZIP、WinZIP、WinRAR、gzip等压缩工具以及ZIP、GIF、PNG等文件格式都是LZ系列算法的受益者。,33,我们学习了几种信源编码：香农费诺编码、哈夫曼编码、游程编码、算术编码、LZ编码等。游程编码和算术编码是非分组编码；游程编码是限失真信源编码。本章介绍的都是离散信源变长编码。优点：提高编码效率；缺点：需要大量缓冲设备来存储这些变长码，然后再以恒定的码率进行传送；如果出现了误码，容易引起错误扩散，所以要求有优质的信道。,34,信道容量C：在信道中最大的信息传输速率，单位是比特/符号。单位时间的信道容量Ct：若信道平均传输一个符号需要t秒钟，则单位时间的信道容量为Ct实际是信道的最大信息传输速率。,第3章信道容量,35,根据信道中所受噪声种类的不同,可分为随机差错信道和突发差错信道.在有记忆信道中，噪声干扰的影响往往是前后相关的，错误是成串出现的，一般在编码中我们称这类信道为突发差错信道。实际的衰落信道、码间干扰信道均属于这类信道。有些实际信道既有独立随机差错,也有突发性成串差错，我们称它为混合信道。,36,求信道容量的方法当信道特性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)无关，而仅仅是信道转移概率的函数，只与信道统计特性有关；信道容量是完全描述信道特性的参量；信道容量是信道能够传送的最大信息量。,37,当n=2时的强对称离散信道就是二进制均匀信道。二进制均匀信道的信道容量为：二进制均匀信道容量曲线如图3.2.5所示。,38,对称DMC容量的计算,结论实现对称DMC信道容量的输入分布为等概分布,信道只关于输入对称的话（输入分布为等概分布）,39,一般DMC的容量计算,40,一般DMC的容量计算,这是K个未知量0,1,K-1=C+logw(0),C+logw(1),C+logw(K-1)的线性方程组，系数矩阵是可逆方阵，因此唯一解出0,1,K-1,41,一般DMC的容量计算,另一个等式：w(0)+w(1)+w(K-1)=1。于是,i=C+logw(i),42,积信道或独立并行信道,C1maxI(X1,Y1)，C2maxI(X2,Y2)信道1和信道2同时传递消息，输入集X=X1X2，输出集Y=Y1Y2，转移概率p(jj|kk)=p(j|k)p(j|k)称这样组合成的信道为1和2的积信道或独立并行信道,积信道的容量C=C1+C2,43,和信道或并信道,单位时间内可以且只能随机选用信道1和信道2中的一个，选用信道1的概率为p1，选用信道2的概率为p2，p1p21输入空间X=X1+X2，Y=Y1+Y2，,44,级联信道或串行信道,信道1的输出作为信道2的输入,（3）令自级连的次数N+，则级连信道的转移概率矩阵趋向于,信道容量趋向于0。,45,香农公式当信道容量一定时，增大信道带宽，可以降低对信噪功率比的要求；反之，当信道频带较窄时，可以通过提高信噪功率比来补偿。当信道频带无限时，其信道容量与信号功率成正比。,46,差错控制的基本方式前向纠错(FEC)：发送端的信道编码器将信息码组编成具有一定纠错能力的码。接收端信道译码器对接收码字进行译码，若传输中产生的差错数目在码的纠错能力之内时，译码器对差错进行定位并加以纠正。自动请求重发(ARQ)：用于检测的纠错码在译码器输出端只给出当前码字传输是否可能出错的指示，当有错时按某种协议通过一个反向信道请求发送端重传已发送的码字全部或部分。,第6章信道编码,47,混合纠错(HEC)：是FEC与ARQ方式的结合。发端发送同时具有自动纠错和检测能力的码组，收端收到码组后，检查差错情况，如果差错在码的纠错能力以内，则自动进行纠正。如果信道干扰很严重，错误很多，超过了码的纠错能力，但能检测出来，则经反馈信道请求发端重发这组数据。,48,最佳译码准则（最大似然译码）通信是一个统计过程，纠、检错能力最终要反映到差错概率上。对于FEC方式，采用纠错码后的码字差错概率为pwe，p(C)：发送码字C的先验概率p(C/R)：后验概率若码字数为2k，对充分随机的消息源有p(C)=1/2k，所以最小化的pwe等价为最小化p(CCR)，又等价为最大化p(C=CR)；,49,对于BSC信道：最大化的p(C=CR)等价于最大化的p(RC)，最大化的p(RC)又等价于最小化d(R,C)，所以使差错概率最小的译码是使接收向量R与输出码字C距离最小的译码。,50,对给定离散无记忆信道和任意e0，若有一种编码速率为R的码，在N足够大时，能使pee，就称R是可达的。,定理(Shannon信道编码定理)，给定容量为C的离散无记忆信道X，p(x|y)，