信息论基础手册.docx

《信息论基础手册.docx》由会员分享，可在线阅读，更多相关《信息论基础手册.docx（15页珍藏版）》请在三一文库上搜索。

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

2、以信息运动规律为研究内容，信息运动包括获取、传递、存储、处理和施用等环节。第二章 离散信源及离散熵X x1x2xnl单符号离散信源的数学模型： P ( X )= P ( x )P ( x )P ( x )12n自信息量：I ( xi ) = - log x P ( xi ) ，是无量纲的，一般根据对数的底来定义单位：当对数底为 2 时，自信息量的单位为比特(bit,binary unit)；对数底为 e 时，其单位为奈特(nat,nature unit)；对数底为 10 时，其单位为哈特(Hart, Hartley)自信息量性质：I(xi)是随机量；I(xi)是非负值；I(xi)是 P(xi)

3、的单调递减函数。l 单符号离散信源的离散熵：nH ( X ) = E I ( xi ) = - P ( xi )lbP ( xi ) ，单位是比特/符号(bit/symbol)。i =1离散熵的性质和定理：H(X)的非负性；H(X)的上凸性；最大离散熵定理：H ( X ) lbnl 如果除概率分布相同外，直到 N 维的各维联合概率分布也都与时间起点无关，即：P ( X k ) = P ( Xl )P ( X k X k +1 ) = P ( X l Xl +1 )P ( X k X k +1X k + N -1 ) = P ( X l X l +1 Xl + N -1 )则称该多符号离散信源为

4、 N 维离散平稳信源。l N 维离散平稳信源的数学模型：XXXN= a1a2aN12n P ( X 1 X 2 X N ) P ( a1 ) P ( a2 )P ( anN )其中, ai= xi1 xi2 xi N ,i1 , i2 , , i N 1,2, , nP ( ai ) = P ( xi1 xi2xi N ) = P ( xi1 )P ( xi2 / xi1 ) P ( xi N / xi1 xi2 xiN -1 )l 二维离散平稳信源的离散熵：n2H ( X 1 X 2 ) = - P ( ai )lbP ( ai ) = H ( X 1 ) + H ( X 2 / X1 )i

5、 =1H(X2/X1 )称为条件熵，是条件信息量在联合概率上的数学期望，H(X1X2)称为联合熵，离散熵 H(X1)、 H(X2)称为无条件熵，H2(X1X2)称为平均符号熵且：H ( X 2 / X 1 ) H ( X2 ) ，H 2 ( X 1 X 2 ) = 12 H ( X 1 X 2 ) H ( X1 )l 对于，H N ( X 1 X 2 X N ) = N1 H ( X 1 X 2 X N ) H ( X1 ) ，当 N时，平均符号熵取极限值，称之为极限熵，用 H表示：H = lim 1 H ( X 1 X 2X N )N Nl 如果离散平稳信源发出的符号序列中各符号相互独立，则

6、称该信源为离散平稳无记忆信源。N 维离散平稳无记忆信源(一维离散平稳信源的 N 次扩展信源)的数学模型：X Na1a2anN= p ( a2 ) P ( X N ) p ( a1 )p ( anN )其中, ai = xi1 xi2xi N ,i1 , i2 , i N 1,2, n ， p(ai ) = p ( xi1 ) p ( xi2 )p ( xiN )其离散熵：H ( X N ) = H ( X 1 ) + H ( X 2 ) + H ( X N ) = NH ( X1 )信源的平均符号熵： H N ( X N ) = N1 H ( X N ) = H ( X1 )l 如果离散平稳信

7、源发出的符号只与前面已经发出的 m( 0, p ( ej ) = 1i=1j=1第三章 离散信源无失真编码l 码字的每一个比特携带信息的效率即编码效率：h = H K(X ) ，K 平均码长一般采用不等长编码，使平均码长接近离散熵，从而在无失真前提下提高编码效率；编码的基本原则是大概率符号元编成短码，小概率符号元编成长码如果所采用的不等长编码使接收端能从码序列中唯一地分割出对应与每一个符号元的码字，则称该不等长编码为单义可译码。单义可译码中，如果能在对应与每一个符号元的码字结束时立即译出的称为即时码，如果要等到对应与下一个符号元的码字才能译出的称为延时码。异前置码：任何一个码字都不是其他码字的

8、前缀m 元长度为 ki , i=1,2, ,n 的异前置码存在的充分必要条件是：n m-ki 1，（克拉夫特(Kraft)不等式）i =1l 无失真编码定理：（香农第一定理）如果 L 维离散平稳信源的平均符号熵为 HL(X1X2XL)，对信源符号进行 m 元不等长组编码，一定存在一种无失真编码方法，当 L 足够大时，使得每个信源符号所对应码字的平均比特数：H L ( X 1 X 2 X L ) KL lbm H L ( X 1 X 2 X L ) + e ，e为任意给定的小数只要e lbmL ，H L ( X 1 X 2 X L ) KL lbm H L ( X 1 X 2 X L ) + e

9、无失真编码定理从理论上阐明了编码效率：h 1l L时，h =H= 1limKlbmL L则极限熵 H是一个界限，通常也称为香农界对于 L 维离散平稳无记忆信源，由于其平均符号熵 HL(X1X2XL) =H(X)，故对信源符号进行 m 元不等长组编码，一定存在一种无失真编码方法，当 L 足够大时，使得每个信源符号所对应码字的平均比特数：H ( X ) KL lbm H ( X ) + e ，此时香农界为 H(X)。对离散平稳信源进行无失真编码，每个信源符号所对应码字的平均比特数平稳无记忆信源最多， m 阶马尔科夫信源次之，一般平稳信源最少。l 二进制香农码的编码步骤如下：1) 将符号元 xi 按

10、概率进行降序排列j-12) 令 p(x0)=0，计算第 j-1 个码字的累加概率：pa (x j ) = p ( xi )，j = 1,2, , ni =03) 确定第 i 个码字的码长 ki，满足下列不等式：-lbp ( xi ) k i -lbp ( xi ) +14) 将 pa(xj)用二进制表示，取小数点后 ki 位作为符号元 xi 的码字。l 哈夫曼(Huffman)编码1) 将符号元按概率进行降序排列2) 为概率最小的符号元分配一个码元 1，概率次小的符号元分配一个码元 03) 将概率最小的两个符号元合并成一个新的符号元，用两者概率之和作为该新符号元的概率；4) 重复以上三个步骤，

11、直到最后合并出一个以 1 为概率的符号元哈弗曼码有两种排列方式，分前置和后置。采用不同排列方法编出的哈夫曼码，其码字和码长可能完全不相同，但平均码长一定是相等的，因此编码效率不会因排列方法而改变。但放在前面可以使短码得到充分利用第四章 离散信道及信道容量l 符号离散信道的数学模型可表示为：P (Y / X ) = p( y1 / x1 )p ( y 2 / x1 )p( y1 / x2 )p ( y 2 / x2 )p( y1 / xn )p ( y 2 / xn )p ( y m / x1 ) p ( y m / x2 ) p ( y m / xn )p ( y j )l 互信息量在有噪信道

12、的情况下，将信源发出 xi 而信宿接收到 yj 所包含的信息量用I(yj;xi )来表示并将其称为 xi 对 yj 的互信息量，则互信息量的定义为：I ( y j ; xi ) = I ( y j ) - I ( y j / xi ) = - lbp ( y j ) + lbp ( y j / xi ) = lb p( y j / xi )I(yj/xi )称为条件信息量，表示信道给出的“信息”。互信息量的性质：I(yj;xi )是随机量，I(yj;xi )可为正值也可为负值，I(yj;xi )具有对称性l 单符号离散信道的平均互信息量：n mn mp( y j / xi )I (Y ; X

13、) = p ( xi y j )I ( y j ; xi ) = p ( xi y j )lbp ( y j )i =1 j =1i =1 j=1I (Y ; X ) = H (Y ) - H (Y / X ) ，条件熵 H(Y/X)是信道所给出的平均信息量，通常称为噪声熵I (Y ; X ) = H ( X ) - H ( X / Y ) ，条件熵 H(X/Y)也是信道所给出的平均“信息”量，通常称为损失熵，也称为信道疑义度I (Y ; X ) = H ( X ) + H (Y ) - H ( XY )l 平均互信息量的性质和定理：1) I(Y;X)的对称性2) I(Y;X)的非负性3) I

14、(Y;X)的极值性：I (Y ; X ) H (Y )I (Y ; X ) H ( X )4) I(Y;X)的凸函数性当信道固定时，I(Y;X)是信源概率分布 P(X)的上凸函数；当信源固定时，I(Y;X)是信道转移概率分布 P(Y/X)的下凸函数5) 数据处理定理：I (Z ; X ) I (Y ; X )I ( X ; Z ) I (Y ; Z )一个信息传递并进行数据处理的问题可看成是一个由串联信道进行信息传递的问题l 单符号离散信道的信道容量由于平均互信息量反映的是每传输一个符号在信道中流通的平均信息量，从这个意义上，可以将其理解为信道的信息传输率(不是信息传输速率！)，即R = I

15、(Y ; X ) 。定义最大的信息传输率为信道容量，即：C = max R = max I (Y ; X ) 。P ( X )P ( X )定义最大信息传输速率为：C =1max R =1max I (Y ; X )tt P ( X )t P ( X )l 信道容量的计算步骤mm(1)由 p ( y j / xk )lbp ( y j / xk ) = p ( y j / xk ) b j，k = 1, 2, n，求出b j，j = 1, 2, mj =1j=1m(2)求出C = lb( 2 b j )j =1(3)求出p( y j ) = 2 b j -Cj = 1, 2, mn(4)由p(

16、 y j ) = p ( xi ) p ( y j / xi )j = 1, 2, m ，求出p ( xk )k = 1, 2, ni=1l 均匀信道和对称信道的信道容量 p p如果离散信道 X , P (Y / X ), Y的信道矩阵 ， P (Y / X ) = n -1 p则称该信道为均匀信道ppn -1n -1ppn -1，ppn -1当p ( x1 ) = p ( x2 ) = = p ( xn ) = 1n 时，均匀信道的信息传输率可达最大，其信道容量为：C max = lbn + plbp + plb n p-1l 对称信道和对称信道的信道容量如果离散信道 X , P (Y /

17、X ), Y的信道矩阵既是行可排列的，又是列可排列的，则称该矩阵所表示的信道为对称信道则称该信道为对称信道如果每一行都是同一集合Q q1 , q2 , qm中诸元素的不同排列，则称该矩阵为行可排列的；如果每一列都是同一集合P p1 , p2 , , pn 中诸元素的不同排列，则称该矩阵为列可排列的当p ( x1 ) = p ( x2 ) = p ( xn ) = 1n 时，均匀信道的信息传输率可达最大，其信道m容量为：C max = lbm + q j lbqjj =1l 离散无记忆信道及其信道容量对应于多符号离散信源和多符号离散信宿的信道为多符号离散信道，可表示为： X1 X 2 X L P

18、 (Y1Y2 YL / X 1 X 2 X L )Y1Y2 YL p(b1 / a1 )p (b2 / a1 )p (bm L / a1 ) p (b1 / a2 )p (b2 / a2 )p (b L / a2 ) 其中P (Y1Y2 YL / X 1 X 2 X L ) = m p (b1 / aL ) p (b2 / a L )p (bL / aL )nnmn当信源和信宿均为平稳无记忆时，信道矩阵中的条件概率：p(b j / ai ) = p ( y j1 y j2y j L / xi1 xi2 xiL ) = p ( y j1 / xi1 ) p ( y j2 / xi2 ) p (

19、y j L / xiL )该信道矩阵表示的多符号离散信道称为离散无记忆信道(DMC, Discrete Memoryless Channel)。可称其为 L 次扩展信道如果记一维离散无记忆信道的信道容量为 C，则其 L 次扩展信道的信道容量为：C L = max I (Y L ; X L ) = LCP ( X )第五章 离散信道编码l 信道编码定理译码规则的设计依据的是最小错误概率准则。为了降低错误概率，可以考虑重复发送，如重复三次，即将 x1 编码为 a1=x1x1x1，x2 编码为 a2=x2x2x2，称为 3 重复码香农第二定理：对于离散无记忆信道，如其信道容量为 C，只要信息传输率R

20、C，一定存在一种编码，当 L 足够大时，使得译码错误概率 Pe ，其中 为任意给定的小正数。该定理从理论上证明了译码错误概率任意小的理想纠错编码的存在性信道编码定理也指出，信道容量 C 是一个界限，如果信息传输率超过这个界限一定会出错l 汉明距离与线性分组码线性分组码通常用于前向纠错，可表示为(n,k)，其中 n 为码字长度，k 为信息位长度，从而校验位长度为 n-k在 m(=2k)个码字构成的码中，两个长度为 n 的码字之间的汉明距离(码距)是指两个码字对应位置上不同码元的个数；对于二元码，码距可表示为：nd ( ci , c j ) = cik c jki , j = 1,2, m , i

21、 jk =1长度为 n 的码字的汉明重量(码重)是指码字中非零码元的个数；对于二元码，码重可表示为：nw( ci ) = ciki = 1, 2, mk =1对于二元码，两个长度为 n 的码字之间的码距可用码重表示：d ( ci , c j ) = w( cik c jk )i , j = 1,2, m , i j线性分组码(n,k)能检 e 个错误并能纠 t 个错误的充要条件是：d min e + t +1 最简单的能检 1 个错误并能纠 1 个错误的线性分组码(n,k)的dmin 3将错误序列 E 的随机结果 ei 称为错误图案，当 eik=1 时，表示第 i 个码字的第 k 位在传输中出

22、现错误。最简单的能检 1 个错误并能纠 1 个错误的线性分组码(n,k)的错误图案为0001，0010，0100，1000l (7,4)汉明码设码字为：ci = ci1 ci2 ci3 ci4 ci5 ci6 ci7 ，i = 1,2, m ，其中ci1 ci2 ci3 ci4 为信息位，长度为k=4，cicici为校验位，长度为 n-k=3567(7,4)汉明码的编码由生成矩阵产生：1000111 0011ci2xi2xi3 0 10 ci1ci3ci4 ci5 ci6 ci7 = xi1xi4 01010010001011(7,4)汉明码的最小距离：d min = min d ( ci ,

23、 c j ) = 3i , j = 1, 2, ,16 ,i ji , j由线性分组码(n,k)能检e 个错误并能纠t 个错误的充要条件d min e + t +1 ，(7,4)汉明码只能检出并纠正 1 个错误110l 3重复码的校验矩阵H = 1013 重复码的最小距离d min = d ( c1 , c2 ) = w( c1 c2 ) = 3 ，3 重复码也只能检出并纠正 1 个错误，5 重复码能检出并纠正 2 个错误第六章 连续信源与连续信道l 单变量连续信源的数学模型 X P ( X )定义连续信源的相对熵：H c ( X ) = -ab a x b= p ( x)p ( x )lbp

24、 ( x ) dx 。相对熵不能反映连续信源的平均不确定度。定义相对熵的目的在于在形式上与离散信源熵统一并使熵差具有信息测度的意义。两个连续随机变量的联合熵：H c ( XY ) = - p ( xy )lbp ( xy ) dxdyR 2两个连续随机变量的条件熵：H c ( X / Y ) = - p ( xy )lbp ( x / y ) dxdyR2l 均匀分布连续信源的相对熵：p(x ) =1, a x b ， H c ( X ) = lb (b - a)b- a高斯分布连续信源的相对熵：1e -( x -m)21lbe + lb 2ps 21lb (2p es 2 )p ( x )

25、=2s 2, - x ， H c ( X ) =2ps 222指数分布连续信源的相对熵：1-xp ( x ) =e m,0 x ， H c ( X ) = lbe + lbm = lb ( em)ml 相对熵的性质及最大相对熵定理1) 相对熵不具有非负性2) 相对熵的可加性：H c ( XY ) = H c ( X ) + H c (Y / X ) ， H c ( XY ) = H c (Y ) + H c ( X / Y )最大相对熵定理：连续信源没有一般意义下的最大熵，只有限制条件下的最大熵1) 取值范围受限条件下的最大熵定理随机变量取值被限定在一定范围内，则在该有限定义域内均匀分布的连续

26、信源具有最大熵，即：H c ( X ) lb (b - a ),a x b2) 平均功率受限条件下的最大熵定理随机变量的平均功率被限定，则均值为零、方差为该平均功率的高斯分布的连续信源具有最大熵，即：H c ( X ) 1l b(2p es 2 ) =1l b(2p eP ), - x 223) 均值受限条件下的最大熵定理非负随机变量的均值被限定，则均值为该限定值的指数分布的连续信源具有最大熵，即：H c ( X ) lb ( em ),0 x l 连续信道的平均互信息量Ic (Y ; X ) = H c (Y ) - H c (Y X ) ，Ic ( X ; Y ) = H c ( X )

27、- H c ( X Y )平均互信息量的性质和定理：平均互信息量具有非负性，平均互信息量具有对称性，平均互信息量具有凸函数性。数据处理定理Ic ( X ; Z ) I c ( X ; Y )Ic ( X ; Z ) I c (Y ; Z )信道固定时，总能找到一种信源概率密度函数，使信道的信息传输率最大，称该最大值为信道容量，即：C = max R = max I c ( X ; Y )p ( x )p ( x)l 如果噪声 N 是均值为 0、方差为 2 的高斯噪声，输入 X 均值为零、方差为 X2 的高斯分布，则称为高斯加性信道，此时H c (N) = 12 lb (2p es 2 ) =

28、12 lb (2p ePN )X 的平均功率被限定为 PX，已知噪声 N 的平均功率为 PN，可取输出 Y 的平均功率：PY = s Y2 = s X2 + s 2 = PX + PN 。输出 Y 为均值等于零、方差 Y2 等于 PY 的高斯分布时具有最大熵，即max H(Y) =1lb (2p es 2 )=1lb (2p eP )p(x)c2Y2Y高斯加性信道的信道容量：C = max H c (Y ) - H c (N ) =1lbPY=1lb (PX + PN) =1lb(1+PX)2PN22p ( x)PNPN条件是 p(x)满足均值为 0，方差为 X2 的高斯分布，其中PX 为信噪

29、功率比。PNl 香农公式当信道的频带为(0,W)时，将信道的一次传输看成是一次采样，根据采样定理，采样率为 2W 可保证不失真从而不失真的一次传输所需时间为 1/2W，相应的最大信息传输速率：Ct = Wlb (1+ PX ) = Wlb(1+ PX )PNWN0式中，N0 = WPN 为加性高斯噪声的单边功率谱密度。第七章 信息率失真理论l 离散信源的信息率失真函数总能找到一种信道转移概率分布，使信息传输率最小定义非负函数 d(xi,yj)i=1,2, ,n; j=1,2, ,m 为失真度，称全部 nm 个失真度组成的矩阵为失真矩阵： d ( x1 , y1 )d ( x1 , y 2 )

30、.d ( x1 , ym ) d ( x , y )d ( x , y) .d ( x , y) D = 2122.2m ., y1 )d ( xn , y 2 ) . d ( xnd ( xn , ym ) 0a .常用的失真矩阵：D =a 0 . . .aa .a a . ，当 =1 时，称为汉明失真矩阵。 0 d ( xi , y j ) = ( y j - xi )2 称为平方误差失真度。nm平均失真度：D = p ( xi ) p ( y i / xi ) d ( xi , y j )i =1j=1保真度准则：如果给定的允许失真为 D，则称D D 为保真度准则。定义保真度准则下的最小

31、信息传输率为信息率失真函数：R(D )=minR =minI ( X ; Y )p ( y j/ xi )PDp ( y j/ xi )PD信息率失真函数的性质和定义域：R(D)具有非负性，R(D)是 D 的下凸函数，R(D)是 D 单调递减连续函数信息率失真函数的定义域：nmDmin = p ( xi ) mind ( xi , y j ) ，Dmax = min p ( y j ) D j = min Dji=1jp ( y)j=1jj特别地，当 D =Dmin=0，即不允许任何失真时 R(D)=H(X)l 信息率失真函数的参量表达式m信道转移概率分布的 n 个约束条件是， p ( y j

32、 / xi ) = 1i = 1, 2, n 。平均j=1nm失真度的约束条件是：D = p ( xi ) p ( y i / xi ) d ( xi , y j ) 。i =1j=1信息率失真函数的计算步骤为：n(1)由1 = li p(xi ) e Sd ( xi , y j )，求含S的li , j = 1, 2, mi =1m(2)由1 = li p ( y j ) e Sd ( xi , y j )，求含S的p ( y j ), i = 1, 2, nj =1(3)求含S的p ( y j / xi ) = li p ( y j )e Sd ( xi , y j)，i = 1, 2,

33、, n, j = 1, 2, , mnmnm(4)求D S = p ( xi ) p ( y i / xi ) d ( xi , y j ) = p ( xi ) li p ( y j ) e Sd ( xi , y j ) d ( xi , yj )i =1 j =1i =1 j=1n mp ( y j / xi )(5)求R S ，即含S的R ( D ) = p ( xi ) p ( y j / xi )lnp ( y j )i =1 j=1n mli p ( y j)eSd ( xi , y j )n= p ( xi )lip ( y j)e Sd ( xi , y j ) ln= SD

34、 S + p ( xi )ln lip ( yj )i =1 j=1i=1其中 dDdR = S ，且 S 0l 等概率信源的信息率失真函数当 p=0.5，即二元等概率信源时的信息率失真函数：R ( D ) = H (0.5) - H ( aD ) = ln 2 - H (aD )n 元等概率信源，其信息率失真函数：DR ( D ) = ln n + aD ln na-1 + (1- aD )ln(1- aD )l 连续信源的信息率失真函数定义随机变量 X、Y 之间的失真函数为非负函数 d(x,y)，则平均失真度：D = - - p ( xy ) d ( x , y ) dxdy记实验信道的集

35、合：PD = p ( y / x ) : D D 。定义信息率失真函数：R( D ) =infI c ( X ; Y )p ( y / x )PDD S = -+ -+ p ( x )l( x ) p ( y ) d ( x , y ) e Sd ( x , y) dxdyR S = SD S + -+ p ( x ) ln l( x ) dx ，其中S = dDdRl 高斯信源的信息率失真函数平均失真度D = -+ p ( y ) dy -+ p ( x / y )( x - y ) 2 dxY=y 条件下的条件熵：H c ( X / y ) = - -+ p ( x / y )ln p ( x / y ) dx 1ln2p eD ( y)2信道疑义度：H c ( X / Y ) = - -+ -+ p ( y ) p ( x / y ) ln p ( x / y ) dxdy = -+ p ( y ) H c ( X / y ) dy在满足保真度准则D D 的条件下H c ( X / Y ) 12 ln(2p eD)I c ( X ; Y ) = H c ( X ) - H c ( X / Y ) 1ln(2p es 2 ) -1ln(2p eD) =1ln(s 2)222D保真度准则下的信