应用信息论基础期末复习(2011)

应用信息论基础应用信息论基础110-11学年第二学期春季应用信息论基础金明录教授应用信息论基础应用信息论基础2期末复习应用信息论基础应用信息论基础3噪声信道调制器信道编码器加密器信源编码器信息源解调器信道译码器解密器信源译码器受信者模拟信道数字信道1-p1-p1001+S(t)n(t)r(t)无失真编码(香农第一定理)、哈夫曼编码有失真编码(香农第三定理)应用信息论基础课程概要有效性信道编码(香农第二定理)香农公式可靠性熵、互信息、鉴别信息、信道容量、率失真函数、典型序列基本概念基本方法凸函数、詹姆森不等式、渐进均分原理（大数定理）基本定理最大熵定理、数据处理定理、Fano不等式、Kraft不等式应用信息论基础应用信息论基础4单符号离散信源⎭⎬⎫⎩⎨⎧⋅)(,),(,),(),(:)(,,,,,::][2121NiNixPxPxPxPPxxxxPXXX自信息)(log)(1log)(iiixPxPxI−==信源的信息熵[]∑=⋅==NiiiixIxPxIEH1)()()()(X¾信源的平均不确定性（随机性）¾信源的平均信息量¾表示信源所需的最少比特数信息熵的物理意义离散信源的信息描述应用信息论基础应用信息论基础5离散信源X的N次扩展信源1)(12121=⎥⎥⎦⎤⎢⎢⎣⎡=⎥⎦⎤⎢⎣⎡∑=qiiqqppppaaaxpX，，，，，，单符号离散信源⎥⎥⎦⎤⎢⎢⎣⎡=⎥⎥⎦⎤⎢⎢⎣⎡)2121()()()(NNqqiNppppXααααααα，，，，，，),,,(321Niiiiiaaaa=α()∑==Nqiip11α)()(XNHXHN=离散信源的扩展信源应用信息论基础应用信息论基础6熵函数的性质应用信息论基础应用信息论基础7定义:一个信源的实际信息熵与具有同样符号集的最大熵的比值称为熵的相对率，即∞H0H0HH∞=η定义:1减去熵的相对率称为信源剩余度，即011HHr∞−=−=η可见，信源符号之间依赖关系越大，就越小，信源剩余度就越大。∞H离散信源的冗余度应用信息论基础应用信息论基础8⎪⎪⎩⎪⎪⎨⎧⎪⎪⎭⎪⎪⎬⎫YbababaXsr##2211ＸＹ)/(ijabP离散信道一般模型1)/(1=∑=sjijabp∑==riijijabpapbp1)/()()(∑===riijiijijjijiabpapabpapbpbapbap1)/()()/()()(),()/(离散信道描述应用信息论基础应用信息论基础9关于ai的不确定性收到bj后关于ai的不确定性收到bj后消除的关于ai的不确定性(;)()(/)ijiijIxyIxIxy=−互信息概念物理解释1(/)log(/)ijijIxyPxy=应用信息论基础应用信息论基础10ＸＹ)/(ijabPH(XY)H(Y/X)I(X;Y)H(X/Y)H(Y)H(X)信道疑义度（损失熵）噪声熵（散布度）)/()();(YXHXHYXI−=各种熵函数关系熵函数计算！11应用信息论基础金明录教授DUTJensen’sinequality‰Theorem:(Jensen’sinequality)Iffisconvex,thenIffisstrictlyconvex,theequalityimpliesX=E[X]withprobability1.12应用信息论基础金明录教授DUTLog-suminequality应用信息论基础应用信息论基础13平均互信息的数学性质ＸＹ)/(ijabP（2）极值性)()(XHYXI≤；（1）非负性0)(≥YXI；()()XYIY；；=XI)()()()/()()/()()(XYHYHXHXYHYHYXHXHYXI−+=−=−=；（4）平均互信息与各类熵的关系（5）凸函数性在条件下，是的∩型凸函数()xyp/()xp在条件下，是的∪型凸函数()xyp/()xp);(YXI平均互信息的特性(3)对称性应用信息论基础应用信息论基础14信息传输速率)/()()(YXHXHYXIR−==；比特/符号)/(1)(1)(1YXHtXHtYXItRt−==；比特/秒ＸＹ)/(ijabP信息传输速率15应用信息论基础金明录教授DUT随机过程的熵率‰Entropyrate.Twodefinitionsofentropyrateforastochasticprocessare‰Forastationarystochasticprocess,‰EntropyrateofastationaryMarkovchain‰FunctionsofaMarkovchain.IfX1,X2,...,XnformastationaryMarkovchainandYi=φ(Xi),then16应用信息论基础金明录教授DUTFano’sinequality17应用信息论基础金明录教授DUT鉴别信息‰定义:两个随机分布p(x)和q(x)之间的鉴别信息定义为‰物理意义：为鉴别H2和H1而对随机变量X在H2假设的分布下进行观察所平均得到的倾向于H2的信息量观察者对随即变量X的了解由分布q(x)变为p(x)时，所获得的信息量当实际分布为p(x)而估计为q(x)时，D(p||q)衡量了这种估计的偏差程度，描述信源所需的平均比特数为‰也称为Kullback-Leibler距离、交叉熵（Cross-Entropu）、散度（Divergence）、相对熵（relativeentropy）18应用信息论基础金明录教授DUT熵、互信息和鉴别信息‰信息论的三个基本概念分别给出了随机变量不确定性的量度以及在消除或减少这一不确定性时所获信息的量度。随机变量不确定性的量度:香农定义的熵是随机变量不确定性的最合理的量度。减少或消除随机变量的不确定性的两条途径和信息的两种量度:一条是对另一个与我们感兴趣的随机变量统计关联的随机变量进行观察、试验,从而获得关于原随机变量的信息,减少或消除其不确定性。该信息量可以用互信息进行量度。另一条是对我们感兴趣的随机变量本身进行观察、试验,从而获得信息,减少或消除其不确定性。该信息量可以用鉴别信息进行量度。19应用信息论基础金明录教授DUT熵、互信息和鉴别信息‰从统计数学的角度来看,信息论的三个基本概念给出了三个统计量,代表了三种量度,其中:熵是一个系统无序性的量度;鉴别信息是两种概率分布之间差异性的量度;互信息是两个随机变量之间统计依存性的量度。‰因此,熵、互信息和鉴别信息大大丰富了统计数学中对随机现象的描述方法,其意义超过了随机变量一般的数字特征。‰三者的相互关系:在信息论的三个基本概念中,熵是最基础的。鉴别信息则是最普遍的,由鉴别信息可以推出互信息,故互信息是鉴别信息的特例。由互信息又可以推出熵,故熵是互信息的特例。应用信息论基础应用信息论基础20¾信道容量消息在不失真传输的条件下，信道所允许的最大信息传输速率称为信道容量，即C=Rmax。（或Ct=Rtmax）¾信道容量的计算{})(max)(YXICxp；=最佳输入分布信道容量C已与输入信源的概率分布无关，它只是信道转移概率的函数，只与信道的统计特性有关。即对于一个特定的信道，其信道容量C是确定的，是不随输入信源的概率分布而变得，信道容量C取值的大小，直接反映了信道质量的高低。所以，信道容量是完全描述信道特性的参量，是信道能够传输的最大信息量。信道容量应用信息论基础应用信息论基础21)()(YXIZXI；；≤)()(ZYIZXI；；≤数据处理不等式二元对称信道就是ｒ＝２的均匀信道，可计算得其信道容量为：)(1pHC−=比特/符号BSC信道容量数据处理定理1-p1-p1001XYZI(X;Z)I(Y;Z)I(X;Y)应用信息论基础应用信息论基础22•分组码•二元码•等长码•变长码•非奇异码•奇异码•同价码•码的N次扩展码•唯一可译码•即时码•树码编码器},,,{21qsssS=},,,{21rxxxX=},,,{21q=),,,(21liiiiixxxws=↔CWWSssWWssjijijiji∈∈≠⇒≠,,(){}NNiiiiqiqiii====信源编码基本概念应用信息论基础应用信息论基础23编码器},,,{21qsssS=},,,{21rxxxX=},,,{21q=),,,(21Liiiiixxxws=↔Lrq≤LNrq≤单符号信源N次扩展信源),,,(),,,(2121LNiiiiiiiixxxWsss=↔=αN长共有qN个L长共有rL个单个符号共有q个L长共有rL个无失真信源编码应用信息论基础应用信息论基础24任何一个离散随机序列信源当序列长度N→∝时,信源序列会产生两极分化.大概率事件集合与小概率事件集合,即qN=∪NGε])([log])([22εεεξ−−−+≈=sHqNNSHNNNqqGNGεNGεNGε信源序列集合NqNGεNGε))(())(())((21))((22)1(2),,,(2)(;1)(εεεεεεεδεδ−−+−−−+−−≤−SHNNSHNSHNNSHNNNGSSSPGPGP等长信源编码定理rSHNLlog)(ε+≥rSHNLlog2)(ε−≤[]()δηη2221)()(N−≥SHSIDN编码效率⎟⎟⎠⎞⎜⎜⎝⎛==rLSNHRSHlog)(')(ηrNLRlog'=典型序列与等长信源编码定理应用信息论基础应用信息论基础25Kraft不等式：设信源符号，码符号，对信源进行编码，相应的码字为，其分别对应的码长为，则即时码存在的充分必要条件是：{}qsssS,,,21={}rxxxX,,,21={}q=qlll,,,2111≤∑=−qilir无失真变长信源编码定理:离散无记忆平稳信源S，其熵率为，并有码符号X={x1,…,xr}。对信源S进行编码,总可以找到一种编码方法，构成惟一可译码，使信源S中每个信源符号所需的平均码长满足:另一方面,必可以找到前缀码，使其平均码长满足编码效率)(SHrSHLlog)(≥1log)(+≤rSHLKraft不等式与无失真信源编码定理LSHrLSHr)(log)(==η应用信息论基础应用信息论基础26霍夫曼编码方法缩减信源信源符号码字码长概率1S2S3S0.61s110.410.410.410.42s0120.2010.2010.400013s00030.20000.20000.2014s001040.100100.201001015s001140.1010011霍夫曼编码方法2.241.041.032.022.014.0)(51=×+×+×+×+×==∑=iiilsPL()%5.96==LSHη霍夫曼编码求解！应用信息论基础应用信息论基础27霍夫曼编码方法缩减信源信源符号码字码长概率1S2S3S0.60.40.41s0020.4000.40.42s1020.2100.200010.23s1120.2110.2100014s01030.10100.20101015s01130.101011101()2.231.031.022.022.024.051=×+×+×+×+×==∑=iiilspL()%5.96==LSHη霍夫曼编码方法应用信息论基础应用信息论基础28有噪信道编码编码器译码器信道S’SYX编译码准则与错误概率is),,(21niiiixxxX=),,(21njjjjyyyY=jsqsss#21⎩⎨⎧≠==iijXYXYYYF***)(错对译码)/})(({1)/})(({)/(jijjijjYXYFPYXYFPYeP=−=≠=错误概率∑===sjjjjEYePYPYePEP1)/()()]/([nq2应用信息论基础应用信息论基础29编译码准则与错误概率***),/()/(,)(XXYXPYXPXYFijijj≠≥=最大后验概率译码编码器译码器信道S’SYXis),,(21niiiixxxX=),,(21njjjjyyyY=js***),/()/(,)(XXXYPXYPXYFiijjj≠≥=最大似然概率译码***),,(),(,)(XXYXDYXDXYFijijj≠≤=最小汉