信息论复习重点

1、信息论导论参考资料作者 龙非池第一章 概论l 在认识论层次研究信息时，把只考虑到形式因素的部分称为语法信息，把只考虑到含义因素的部分称为语义信息；把只考虑到效用因素的部分称为语用信息。目前，信息论中主要研究语法信息l 归纳起来，香农信息论的研究内容包括：1) 信息熵、信道容量和信息率失真函数2) 无失真信源编码定理、信道编码定理和保真度准则下的信源编码定理3) 信源编码、信道编码理论与方法l 一般认为，一般信息论的研究内容除香农信息论的研究内容外，还包括维纳的微弱信号检测理论：包括噪声理论、信号滤波与预测、统计检测与估计理论、调制理论等。信息科学以信息为研究对象，信息科学以信息运动规律为研究内

2、容，信息运动包括获取、传递、存储、处理和施用等环节。第二章 离散信源及离散熵l 单符号离散信源的数学模型：自信息量：，是无量纲的，一般根据对数的底来定义单位：当对数底为2时，自信息量的单位为比特(bit,binary unit)；对数底为e时，其单位为奈特(nat,nature unit)；对数底为10时，其单位为哈特(Hart, Hartley) 自信息量性质：I(xi)是随机量；I(xi)是非负值；I(xi)是P(xi)的单调递减函数。l 单符号离散信源的离散熵：，单位是比特/符号(bit/symbol)。离散熵的性质和定理：H(X)的非负性；H(X)的上凸性；最大离散熵定理：l 如果除概

3、率分布相同外，直到N维的各维联合概率分布也都与时间起点无关，即：则称该多符号离散信源为N维离散平稳信源。l N维离散平稳信源的数学模型：l 二维离散平稳信源的离散熵：H(X2/X1 )称为条件熵，是条件信息量在联合概率上的数学期望，H(X1X2)称为联合熵，离散熵H(X1)、 H(X2)称为无条件熵，H2(X1X2)称为平均符号熵且：，l 对于，当N时，平均符号熵取极限值，称之为极限熵，用H表示：l 如果离散平稳信源发出的符号序列中各符号相互独立，则称该信源为离散平稳无记忆信源。N维离散平稳无记忆信源(一维离散平稳信源的N次扩展信源)的数学模型：，其离散熵：信源的平均符号熵：l 如果离散平稳信

4、源发出的符号只与前面已经发出的m(<N)个符号相关，则称该信源为m阶马尔科夫信源。可将m阶马尔科夫信源发出的符号序列看成长度为m+1的一段段符号序列，m阶马尔科夫信源的数学模型：为强调m阶马尔科夫信源的长度特征，一般将其极限熵H记为Hm+1，即：马尔科夫链的各态历经定理：第三章 离散信源无失真编码l 码字的每一个比特携带信息的效率即编码效率：，平均码长一般采用不等长编码，使平均码长接近离散熵，从而在无失真前提下提高编码效率；编码的基本原则是大概率符号元编成短码，小概率符号元编成长码如果所采用的不等长编码使接收端能从码序列中唯一地分割出对应与每一个符号元的码字，则称该不等长编码为单义可译码

5、。单义可译码中，如果能在对应与每一个符号元的码字结束时立即译出的称为即时码，如果要等到对应与下一个符号元的码字才能译出的称为延时码。异前置码：任何一个码字都不是其他码字的前缀m元长度为ki , i=1,2, ,n的异前置码存在的充分必要条件是：，（克拉夫特(Kraft)不等式）l 无失真编码定理：（香农第一定理）如果L维离散平稳信源的平均符号熵为HL(X1X2XL)，对信源符号进行m元不等长组编码，一定存在一种无失真编码方法，当L足够大时，使得每个信源符号所对应码字的平均比特数：无失真编码定理从理论上阐明了编码效率：l L时，则极限熵H是一个界限，通常也称为香农界对于L维离散平稳无记忆信源，由

6、于其平均符号熵HL(X1X2XL) =H(X)，故对信源符号进行m元不等长组编码，一定存在一种无失真编码方法，当L足够大时，使得每个信源符号所对应码字的平均比特数：，此时香农界为H(X)。对离散平稳信源进行无失真编码，每个信源符号所对应码字的平均比特数平稳无记忆信源最多， m阶马尔科夫信源次之，一般平稳信源最少。l 二进制香农码的编码步骤如下：1) 将符号元xi按概率进行降序排列2) 令p(x0)=0，计算第j-1个码字的累加概率：3) 确定第i个码字的码长ki，满足下列不等式：4) 将pa(xj)用二进制表示，取小数点后ki位作为符号元xi的码字。l 哈夫曼(Huffman)编码1) 将符号

7、元按概率进行降序排列2) 为概率最小的符号元分配一个码元1，概率次小的符号元分配一个码元03) 将概率最小的两个符号元合并成一个新的符号元，用两者概率之和作为该新符号元的概率；4) 重复以上三个步骤，直到最后合并出一个以1为概率的符号元哈弗曼码有两种排列方式，分前置和后置。采用不同排列方法编出的哈夫曼码，其码字和码长可能完全不相同，但平均码长一定是相等的，因此编码效率不会因排列方法而改变。但放在前面可以使短码得到充分利用第四章 离散信道及信道容量l 符号离散信道的数学模型可表示为：l 互信息量在有噪信道的情况下，将信源发出xi 而信宿接收到yj所包含的信息量用I(yj;xi )来表示并将其称为

8、xi对yj的互信息量，则互信息量的定义为：I(yj/xi )称为条件信息量，表示信道给出的“信息”。互信息量的性质：I(yj;xi )是随机量，I(yj;xi )可为正值也可为负值，I(yj;xi )具有对称性l 单符号离散信道的平均互信息量：，条件熵H(Y/X)是信道所给出的平均信息量，通常称为噪声熵，条件熵H(X/Y)也是信道所给出的平均“信息”量，通常称为损失熵，也称为信道疑义度l 平均互信息量的性质和定理：1) I(Y;X)的对称性2) I(Y;X)的非负性3) I(Y;X)的极值性： 4) I(Y;X)的凸函数性当信道固定时，I(Y;X)是信源概率分布P(X)的上凸函数；当信源固定时

9、，I(Y;X)是信道转移概率分布P(Y/X)的下凸函数5) 数据处理定理： 一个信息传递并进行数据处理的问题可看成是一个由串联信道进行信息传递的问题l 单符号离散信道的信道容量由于平均互信息量反映的是每传输一个符号在信道中流通的平均信息量，从这个意义上，可以将其理解为信道的信息传输率(不是信息传输速率！)，即。定义最大的信息传输率为信道容量，即：。定义最大信息传输速率为：l 信道容量的计算步骤 l 均匀信道和对称信道的信道容量，则称该信道为均匀信道均匀信道的信息传输率可达最大，其信道容量为：l 对称信道和对称信道的信道容量既是行可排列的，又是列可排列的，则称该矩阵所表示的信道为对称信道则称该信

10、道为对称信道如果每一行都是同一集合中诸元素的不同排列，则称该矩阵为行可排列的；如果每一列都是同一集合中诸元素的不同排列，则称该矩阵为列可排列的均匀信道的信息传输率可达最大，其信道容量为：l 离散无记忆信道及其信道容量对应于多符号离散信源和多符号离散信宿的信道为多符号离散信道，可表示为：当信源和信宿均为平稳无记忆时，信道矩阵中的条件概率：该信道矩阵表示的多符号离散信道称为离散无记忆信道(DMC, Discrete Memoryless Channel)。可称其为L次扩展信道如果记一维离散无记忆信道的信道容量为C，则其L次扩展信道的信道容量为：第五章 离散信道编码l 信道编码定理译码规则的设计依据

11、的是最小错误概率准则。为了降低错误概率，可以考虑重复发送，如重复三次，即将x1编码为a1=x1x1x1，x2编码为a2=x2x2x2，称为3重复码香农第二定理：对于离散无记忆信道，如其信道容量为C，只要信息传输率R<C，一定存在一种编码，当L足够大时，使得译码错误概率Pe< ，其中为任意给定的小正数。该定理从理论上证明了译码错误概率任意小的理想纠错编码的存在性信道编码定理也指出，信道容量C是一个界限，如果信息传输率超过这个界限一定会出错l 汉明距离与线性分组码线性分组码通常用于前向纠错，可表示为(n,k)，其中n为码字长度，k为信息位长度，从而校验位长度为n-k在m(=2k)个码字

12、构成的码中，两个长度为n的码字之间的汉明距离(码距)是指两个码字对应位置上不同码元的个数；对于二元码，码距可表示为：长度为n的码字的汉明重量(码重)是指码字中非零码元的个数；对于二元码，码重可表示为：对于二元码，两个长度为n的码字之间的码距可用码重表示：线性分组码(n,k)能检e个错误并能纠t个错误的充要条件是：最简单的能检1个错误并能纠1个错误的线性分组码(n,k)的将错误序列E的随机结果ei称为错误图案，当eik=1时，表示第i个码字的第k位在传输中出现错误。最简单的能检1个错误并能纠1个错误的线性分组码(n,k)的错误图案为0001，0010，0100，1000l (7,4)汉明码设码字

13、为：，其中为信息位，长度为k=4，为校验位，长度为n-k=3(7,4)汉明码的编码由生成矩阵产生：(7,4)汉明码的最小距离：由线性分组码(n,k)能检e个错误并能纠t个错误的充要条件，(7,4)汉明码只能检出并纠正1个错误l3重复码的最小距离，3重复码也只能检出并纠正1个错误，5重复码能检出并纠正2个错误第六章 连续信源与连续信道l 单变量连续信源的数学模型定义连续信源的相对熵：。相对熵不能反映连续信源的平均不确定度。定义相对熵的目的在于在形式上与离散信源熵统一并使熵差具有信息测度的意义。两个连续随机变量的联合熵：两个连续随机变量的条件熵：l 均匀分布连续信源的相对熵：，高斯分布连续信源的相

14、对熵：，指数分布连续信源的相对熵：，l 相对熵的性质及最大相对熵定理1) 相对熵不具有非负性2) 相对熵的可加性：，最大相对熵定理：连续信源没有一般意义下的最大熵，只有限制条件下的最大熵1) 取值范围受限条件下的最大熵定理随机变量取值被限定在一定范围内，则在该有限定义域内均匀分布的连续信源具有最大熵，即：2) 平均功率受限条件下的最大熵定理随机变量的平均功率被限定，则均值为零、方差为该平均功率的高斯分布的连续信源具有最大熵，即：3) 均值受限条件下的最大熵定理非负随机变量的均值被限定，则均值为该限定值的指数分布的连续信源具有最大熵，即：l 连续信道的平均互信息量，平均互信息量的性质和定理：平均

15、互信息量具有非负性，平均互信息量具有对称性，平均互信息量具有凸函数性。数据处理定理 信道固定时，总能找到一种信源概率密度函数，使信道的信息传输率最大，称该最大值为信道容量，即：l 如果噪声N是均值为0、方差为2的高斯噪声，输入X均值为零、方差为X2的高斯分布，则称为高斯加性信道，此时X的平均功率被限定为PX，已知噪声N的平均功率为PN，可取输出Y的平均功率：。输出Y为均值等于零、方差Y2等于PY的高斯分布时具有最大熵，即高斯加性信道的信道容量：条件是p(x)满足均值为0，方差为X2的高斯分布，l 香农公式当信道的频带为(0,W)时，将信道的一次传输看成是一次采样，根据采样定理，采样率为2W可保

16、证不失真从而不失真的一次传输所需时间为1/2W，相应的最大信息传输速率： 第七章 信息率失真理论l 离散信源的信息率失真函数总能找到一种信道转移概率分布，使信息传输率最小定义非负函数d(xi,yj) i=1,2, ,n; j=1,2, ,m为失真度，称全部n×m个失真度组成的矩阵为失真矩阵：常用的失真矩阵：，当=1时，称为汉明失真矩阵。称为平方误差失真度。平均失真度：保真度准则：如果给定的允许失真为D，则称为保真度准则。定义保真度准则下的最小信息传输率为信息率失真函数：信息率失真函数的性质和定义域：R(D)具有非负性，R(D)是D的下凸函数，R(D)是D单调递减连续函数信息率失真函数

17、的定义域：，特别地，当D =Dmin=0，即不允许任何失真时R(D)=H(X)l 信息率失真函数的参量表达式信道转移概率分布的n个约束条件是，。平均失真度的约束条件是：。信息率失真函数的计算步骤为： 其中，且S < 0及l 等概率信源的信息率失真函数当p=0.5，即二元等概率信源时的信息率失真函数：n元等概率信源，其信息率失真函数：l 连续信源的信息率失真函数定义随机变量X、Y之间的失真函数为非负函数d(x,y)，则平均失真度：记实验信道的集合：。定义信息率失真函数：，其中l 高斯信源的信息率失真函数平均失真度Y=y条件下的条件熵：信道疑义度：在满足保真度准则的条件下保真度准则下的信源编

18、码定理（香农第三定理）：序列长度为L的离散平稳无记忆信源，信息率失真函数为R(D)，对于任意允许失真D和任意小的数>0，只要信息传输率R>R(D)，总可以找到一种编码，使得当L足够长时，译码后的平均失真度，香农第一定理香农第一定理(可变长无失真信源编码定理)设离散无记忆信源X包含N个符号x1,x2,xi,.,xN，信源发出K重符号序列，则此信源可发出Nk个不同的符号序列消息，其中第j个符号序列消息的出现概率为PKj，其信源编码后所得的二进制代码组长度为Bj，代码组的平均长度B为B=PK1B1+PK2B2+PNkBNk当K趋于无限大时，B和H(X)之间的关系为B/K=H(X)(K趋近无穷）香农第一定理又称为无失真信源编码定理或变长码信源编码定理。香农第一定理的意义：将原始信源符号转化为新的码符号，使码符号尽量服从等概分布，从而每个码符号所携带的信息量达到最大，进而可以用尽