信息论与编码复习.ppt

信息论与编码信息论与编码信息论与编码信息论与编码课程内容课程内容信息论的基本问题信息的度量无失真信源编码定理香农第一定理信道编码定理香农第二定理限失真信源编码定理香农第三定理信源编码信道编码2绪绪绪绪 论论论论第一章第一章1、信息论的奠基人香农及其重要著作；2、信息、消息、信号的区别和联系3、通信系统的模型各主要功能模块（包括信源、信道、信宿、信源编译码器、信道编译码器）及其作用4信息论的奠基人：香农信息时代的里程碑：1948年 香农通信的数学理论(A mathematical theory of communication)。第一次提出了信息量的概念，并应用数理统计的方法来研究通信系统，创立了信息论。三大定理无失真信源编码定理（第一极限定理）信道编码定理（第二极限定理）限失真信源编定理（第三极限定理）（一）信息论的形成与发展5（二）信息、消息和信号的区别与联系（二）信息、消息和信号的区别与联系信息是事物运动状态或存在方式。消息是指包含有信息的语言、文字和图像等 信号是消息的物理体现。信号是信息的载荷子或载体，是物理性的。6同一信息，可以采用不同的信号形式(比如文字、语言、图象等）来载荷；同一信号形式，比如“0”与“1”可以表达不同形式的信息，比如无与有、断与通、低与高(电平)等。在通信系统中，实际传输的是信号，但本质内容的是信息。信息包含在信号之中，信号是信息的载体。通信的结果是消除或部分消除不确定性，从而获得信息。7（三）数字通信系统模型（三）数字通信系统模型信道信源信源编码加密信道编码干 扰 源信宿信源解码解密信道解码加密密钥解密密钥u u u ux x x xy y y yk k k kz z z zv v v vz z z z y y y y x x x x 8信源、信宿和信道信源、信宿和信道 信源：向通信系统提供消息u的人和机器。发送消息的源信宿：信息归宿之意，亦即收信者或用户，是信息传送的终点或目的地。信道：传输信息的物理媒介 9信源编码器与译码器信源编码器与译码器 信源编码器符号转换；压缩信源的冗余度,提高通信系统传输效率；包括无失真信源编码、限失真信源编码。信源译码器把信道译码器输出的代码组变换成信宿所需要的消息形式，它的作用相当于信源编码器的逆过程10信道编码器与译码器信道编码器与译码器信道编码提高信息传送的可靠性。在信源编码器输出的代码组上有目的地增加一些监督码元,使之具有检错或纠错的能力信道译码器具有检错或纠错的功能,它能将落在其检错或纠错范围内的错传码元检出或纠正,以提高传输消息的可靠性。11信源与信息熵信源与信息熵信源与信息熵信源与信息熵第二章第二章熟练掌握：自信息量、离散信源熵、互信息、信息不增性的定义概念、并能进行相关计算熵的性质(非负性、对称性、确定性、香农辅助定理、最大熵定理、条件熵小于无条件熵)p28掌握互信息量和熵之间的关系.离散平稳无记忆信源X的N次扩展信源的熵等于信源X的熵的N倍 13(一一)自信息量自信息量设离散信源X，其概率空间为自信息量：某符号出现后提供给收信者的信息量14自信息量自信息量自信息的单位的确定在信息论中常用的对数底是2,信息量的单位为比特(bit)；若取自然对数e,则信息量的单位为奈特(nat);若以10为对数底,则信息量的单位为笛特(det)15I(xi)的特性：I(xi)是非负值 当p(xi)=1时，I(xi)=0 当p(xi)=0时，I(xi)=I(xi)是先验概率p(xi)的单调递减函数，即 当p(x1)p(x2)时，I(x1)I(x2)两个独立事件的联合自信息量等于它们分别的自信息量之和。1617(二二)离散信源熵离散信源熵离散信源熵H(X)(平均不确定度/香农熵)定义信源的平均不确定度，是在总体平均意义上的信源不确定度。单位为比特/符号或比特/符号序列 18条件熵条件熵1920联合熵联合熵联合熵是联合符号集合(X,Y)上的每个元素对(xi,yj)的自信息量的概率加权统计平均值。联合熵H(X,Y)表示X 和Y同时发生的不确定度。21H(XY)与与H(X)、H(X/Y)之间的关系之间的关系 H(X,Y)H(X)H(Y|X)H(X,Y)H(Y)H(X|Y)当X、Y独立时H(X,Y)H(X)H(Y)22(三三)、互信息、互信息定义为 xi的后验概率与先验概率比值的对数互信息I(xi;yj)：表示接收到某消息yj后获得的关于事件xi的信息量。23平均互信息平均互信息 互信息=先验不确定性后验不确定性 =不确定性减少的量Y未知,X 的不确定度为H(X)Y已知,X 的不确定度变为H(X|Y)24i.对称性：ii.非负性：iii.极值性：(四四)、平均互信息的性质、平均互信息的性质iv.凸函数性（1）平均互信息量I(X;Y)是输入信源概率分布 p(xi)的上凸函数研究信道容量的理论基础。（2）平均互信息量I(X;Y)是是信道转移概率 p(yj|xi)的下凸函数研究信源的信息率失真函数的理论基础。25平均互信息与各类熵的关系平均互信息与各类熵的关系 26维拉图维拉图 H(X|Y)H(X)H(Y)H(XY)H(Y|X)I(X;Y)27（五）、数据处理定理（五）、数据处理定理 数据处理定理说明：当对信号、数据或消息进行多级处理时,每处理一次,就有可能损失一部分信息,也就是说数据处理会把信号、数据或消息变成更有用的形式，但是绝不会创造出新的信息,这就是所谓的信息不增原理。32(六六)、熵的性质、熵的性质1.非负性 H(X)H(p1，p2，pn)0式中等号只有在pi=1时成立。2.对称性 H(p1，p2，pn)=H(p2，p1，pn)例如下列信源的熵都是相等的：333.确定性 H(X)H(p1，p2，pn)0只要信源符号中有一个符号出现概率为1,信源熵就等于零。4.极值性(香农辅助定理)对任意两个消息数相同的信源 345.最大熵定理 离散无记忆信源输出M个不同的信息符号,当且仅当各个符号出现概率相等时即(pi1/M)熵最大。6.条件熵小于无条件熵 35信道与信道容量信道与信道容量信道与信道容量信道与信道容量第三章第三章熟练掌握信道容量的定义以及相关计算（包括计算信道容量以及达到信道容量时对应的输入概率分布）重点：无干扰离散信道、对称DMC（离散无记忆）信道 37信道容量信道容量信道容量C：最大的信息传输率单位时间的信道容量：381 1、无干扰离散信道、无干扰离散信道设信道的输入X XA=a1 an,输出YB=b1 bm 1 1）无嗓无损）无嗓无损信道输入和输出符号之间有确定的一一对应关系39 无嗓无损无嗓无损信道由噪声熵H(Y|X)=0 损失熵H(X|Y)=0402 2）无嗓有损）无嗓有损信道多个输入变成一个输出(nm)噪声熵H(Y|X)0 损失熵H(X|Y)041 3 3）有嗓无损）有嗓无损信道一个输入对应多个输出(nm)接收到符号Y后,对发送的X符号是完全确定的。噪声熵H(Y|X)0 损失熵H(X|Y)=0422 2、对称、对称DMCDMC信道信道对称离散信道：对称性:每一行都是由同一集q1,q2,qm的诸元素不同排列组成输入对称每一列都是由p1,p2,pn集的诸元素不同排列组成输出对称43对称对称DMCDMC信道信道若输入符号和输出符号个数相同,都等于n,且信道矩阵为此信道称为强对称信道(均匀信道)信道矩阵中各列之和也等于1 44对称离散信道的平均互信息为45对称DMC信道的容量：上式是对称离散信道能够传输的最大的平均信息量,它只与对称信道矩阵中行矢量p1,p2,pm 和输出符号集的个数m有关。强对称信道的信道容量：46例某对称离散信道的信道矩阵为 信道容量为 47信息率失真函数信息率失真函数信息率失真函数信息率失真函数 第第4 4章章1、概念、定义：失真函数、平均失真、允许失真度、试验信道2、信息率失真函（注意与信道容量的比较)3、信息率失真函数的定义域(即Dmin和Dmax）及相应的信道转移概率的计算491 1、失真函数、失真函数失真函数在信号空间中可以看作一类“距离”侧度，它有性质：失真函数定义为：50将所有的d(xi,yj)排列起来,用矩阵表示为:失真矩阵512 2、平均失真、平均失真 xi和yj都是随机变量,所以失真函数d(xi,yj)也是随机变量,限失真时的失真值只能用数学期望表示将失真函数的数学期望称为平均失真：允许失真D：平均失真的上界 52失真函数d(xi,yj)(信号空间中某类“距离”)：描述了某个信源符号通过传输后失真的大小平均失真 ：描述某个信源在某一试验信道传输下的失真大小,它对信源和信道进行了统计平均,是从总体上描述整个系统的失真533 3、试验信道、试验信道若平均失真度 不大于我们所允许的失真,即则称此为保真度准则当信源p(xi)给定,单个符号失真度d(xi,yj)给定时,选择不同的信道p(yj|xi),相当于不同的编码方法,其所得的平均失真度不同。54满足 条件的所有转移概率分布pij,构成了一个信道集合称为D失真允许的试验信道：满足保真度准则的试验信道。554 4、信息率失真函数、信息率失真函数R(D)R(D)R(D)：在限定失真为D的条件下信源输出的最小信息速率。在信源给定后,我们希望在满足一定失真的情况下,使信源必须传输给收信者的信息传输率R尽可能地小。若从接收端来着,就是在满足保真度准则下,寻找再现信源消息所必须获得的最低平均信息量。即在满足保真度准则的条件下寻找平均互信息I(X,Y)的最小值。56PD是所有满足保真度准则的试验信道集合,因而可以在集合PD中寻找某一个信道pij,使I(X,Y)取极小值。离散无记忆信源57R(D)的定义域率失真的定义域问题就是在信源和失真函数已知的情况下,讨论允许平均失真度D的最小和最大取值问题。由于平均失真度是非负实数d(xi,yj)的数学期望,因此也是非负的实数,即 的下界是0。R(D)=0意味着不需传输任何消息，D越大，直至无穷大都能满足这种情况。Dmin Dmax为R(D)的定义域。（确界）58Dmin 和R(Dmin)的计算信源的最小平均失真度：只有当失真矩阵的每一行至少有一个0元素时,信源的平均失真度才能达到下限值0。5960Dmax和R(Dmax)选择所有满足R(D)0中D的最小值，定义为R(D)定义域的上限Dmax，即 由于I(X,Y)=0的充要条件是X与Y统计独立,即：61例4-3:设输入输出符号表为X=Y=0,1,输入概率分布p(x)=1/3,2/3,失真矩阵 求：Dmin 和Dmax 失真矩阵的每一行至少有一个0元素时,Dmin=062平均互信息平均互信息平均互信息平均互信息平均互信息I(X;Y)：信源的概率分布p(xi)的上凸函数。信道传递概率p(yj|xi)的下凸函数。信道容量：信息率失真函数：63信道容量信道容量信道容量信道容量 信道容量：信道容量：假定信道固定的前提下,选择一种试验信源使信息传输率最大。它所反映的是信道传输信息的能力,是信道可靠传送的最大信息传输率。一旦找到了信道容量,它就与信源不再有关,而是信道特性的参量,随信道特性的变化而变化不同的信道其信道容量不同。64信息率失真函数信息率失真函数信息率失真函数信息率失真函数 信息率失真函数：信息率失真函数：假定信源给定的情况下,用户可以容忍的失真度内再现信源消息所必须获得的最小平均信息量。它反映的是信源可以压缩的程度,是在满足一定失真度要求下信源可压缩的最低值。率失真函数一旦找到,就与求极值过程中选择的试验信道不再有关,而只是信源特性的参量不同的信源其R(D)不同。65 研究信道容量研究信道容量：充分利用已给信道,使传输的信息量最大,而发生错误的概率任意小。研究信息率失真函数研究信息率失真函数：解决在已知信源和允许失真度D的条件下,使信源必须传送给信宿的信息率最小。即用尽可能少的码符号尽快地传送尽可能多的信源消息,以提高通信的有效性。66第五章第五章 信源编码信源编码1、编码的定义和分类：信源编码、信道编码、安全编码2、信源编码的目的3、唯一可译码的特殊结论4、熟练掌握三种能获得最佳变长编码的方法：香农编码、费诺编码、哈夫曼编码；了解游程编码67第六章第六章 信道编码信道编码1、信道编码的目的2、纠错码的分类：不同的分类标准，得到不同的分类，3、从编码定理的公式出发分析使得差错概率尽可能小可以采取的措施4、掌握两种译码方法：最优译码和最大似然译码方法5、了解如下线性分组码的相关概念：线性分组码的生成矩阵、校验矩阵、伴随式和标准阵列译码6、了解特殊的线性分组码的特性 循环码、汉明码68