信息论与编码复习期末考试要点

信息论与编码2课程内容•信息论的基本问题—信息的度量•无失真信源编码定理—香农第一定理•信道编码定理—香农第二定理•限失真信源编码定理—香农第三定理•信源编码•信道编码绪论第一章4•1、信息论的奠基人香农及其重要著作；•2、信息、消息、信号的区别和联系•3、通信系统的模型各主要功能模块（包括信源、信道、信宿、信源编译码器、信道编译码器）及其作用5•信息论的奠基人：香农•重要著作：•1948年香农在《贝尔系统技术》杂志上发表的《通信的数学理论》(Amathematicaltheoryofcommunication)。第一次提出了信息量的概念，并应用数理统计的方法来研究通信系统，创立了信息论。通信的基本问题就是在一点重新准确地或近似地再现另一点所选择的消息-----香农（一）信息论的形成与发展6（二）信息、消息和信号的区别与联系•信息–是事物运动状态或存在方式。•信息的基本概念在于它的不确定性,任何已确定的事物都不含信息。•消息–是指包含有信息的语言、文字和图像等•信号–是消息的物理体现。信号是信息的载荷子或载体，是物理性的。7（三）数字通信系统模型信道信源信源编码加密信道编码干扰源信宿信源解码解密信道解码加密密钥解密密钥uxykzvz'y'x'信源与信息熵第二章•1、掌握相关概念•信源分类（如离散与连续、有记忆和无记忆等）•自信息、信源熵、平均互信息等概念及性质•2、熟练熵、互信息的相关计算•3、掌握马尔科夫信源中状态转移概率、符号转移概率的相关概念以及运算•4、了解数据处理定理•5、了解连续信源中，最大熵定理•1）限峰功率最大熵定理•2）限平均功率最大熵定理910一、自信息量•设离散信源X，其概率空间为•自信息量：某符号出现后提供给收信者的信息量)(log)(iixpxI)()()(2121nnxpxpxpxxxPX1)(0)(1niiixpxp11特性•I(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)⑸两个独立事件的联合自信息量等于它们分别的自信息量之和。12二、离散信源熵•离散信源熵H(X)•(平均不确定度/香农熵)iiiiiixpxpxIxpXH)(log)()()()(单位为比特/符号或比特/符号序列13•条件熵（极限情况条件熵）(|)(,)log(|)ijijiHXYpxypxy(|)(,)log(|)ijjiijHYXpxypyx当X，Y相互独立时，条件熵等于无条件熵(|)()HXYHX(|)()HYXHY14几个概念•联合熵•联合熵H(X,Y)表示X和Y同时发生的不确定度。(,)(,)log(,)ijijijHXYpxypxy15三、互信息•互信息•定义为xi的后验概率与先验概率比值的对数)()|(log);(2ijijixpyxpyxI•互信息I(xi;yj)：表示接收到某消息yj后获得的关于事件xi的信息量。16平均互信息•平均互信息定义互信息=先验不确定性－后验不确定性=不确定性减少的量(;)()(|)()(|)IXYHXHXYHYHYX•Y未知,X的不确定度为H(X)•Y已知,X的不确定度变为H(X|Y)17(;)(;)IXYIYX(;)0IXY(;)()(;)()IXYHXIYXHYi.对称性：ii.非负性：iii.极值性：四、平均互信息的性质(;)(;)IXYIYX(;)0IXY(;)()()(;)()()IXYHXIXIYXHYIYiv.凸函数性（1）平均互信息量I(X;Y)是输入信源概率分布p(xi)的上凸函数，这一点研究信道容量的理论基础。（2）平均互信息量I(X;Y)是信道转移概率p(yj|xi)的下凸函数，这一点是研究信源的信息率失真函数的理论基础。18维拉图H(X|Y)H(X)H(Y)H(XY)H(Y|X)I(X;Y))()()()|()()|()();(XYHYHXHXYHYHYXHXHYXI)|()()|()()()()()|()()|()()(XYHYHYXHXHYHXHXYHYXHYHXYHXHXYH平均互信息与各类熵的关系收、发两端的熵关系I(X;Y)H(X)H(Y)H(X/Y)损失熵H(Y/X)噪声熵20条件熵•H(X|Y)：信道疑义度，损失熵–信源符号通过有噪信道传输后所引起的信息量的损失。•信源X的熵等于接收到的信息量加上损失掉的信息量。•H(Y|X)：噪声熵，散布熵–它反映了信道中噪声源的不确定性。•输出端信源Y的熵H(Y)等于接收到关于X的信息量I(X;Y)加上H(Y|X),这完全是由于信道中噪声引起的。)|()()|()();(XYHYHYXHXHYXI21五、数据处理定理•数据处理定理说明：–当对信号、数据或消息进行多级处理时,每处理一次,就有可能损失一部分信息,也就是说数据处理会把信号、数据或消息变成更有用的形式，但是绝不会创造出新的信息,这就是所谓的信息不增原理。六、熵的性质1.非负性H(X)＝H(p1，p2，…，pn)≥0–式中等号只有在pi=1时成立。2.对称性H(p1，p2，…，pn)=H(p2，p1，…，pn)3.确定性H(X)＝H(p1，p2，…，pn)≥0–只要信源符号中有一个符号出现概率为1,信源熵就等于零。23熵的性质4.极值性(香农辅助定理)–对任意两个消息数相同的信源niyqYxpX,2,1,)()(iniiniiinqppppppHloglog),,(11215.最大熵定理(sl)离散无记忆信源输出M个不同的信息符号,当且仅当各个符号出现概率相等时即(pi＝1/M)熵最大。MMMHXH2log1,1)(24熵的性质(|)()(|)()()()()HXYHXHYXHYHXYHXHY6.条件熵小于无条件熵25七、马尔可夫信源•马尔可夫信源–一类相对简单的离散平稳有记忆信源–该信源在某一时刻发出字母的概率除与该字母有关外,只与此前发出的有限个字母有关•m阶马尔可夫信源：–信源输出某一符号的概率仅与以前的m个符号有关，而与更前面的符号无关。•条件概率111(|,)(|,)LLLLLmpxxxpxxx26马氏链的基本概念•令si=(xi1,xi2,…xim)xi1,,xi2,…xim∈(a1,a2,…an)•状态集S={s1,s2,…,sQ}Q=nm•信源输出的随机符号序列为：x1,x2,…xi-1,xi…•信源所处的随机状态序列为：s1,s2,…si-1,si…•例：二元序列为…01011100…•考虑m=2，Q=nm=22=4•s1=00s2=01s3=10s4=11•变换成对应的状态序列为…s2s3s2s4s4s3s1…27•若信源处于某一状态si,当它发出一个符号后,所处状态就变了,任何时候信源处于什么状态完全由前一时刻的状态和发出符号决定。•系统在任一时刻可处于状态空间S={s1,s2,…,sQ}中的任意一个状态,状态转移时,转移概率矩阵1111(|)QjiQQQppPpsspp1111(|)njiQQnppPpxspp•符号条件概率矩阵区别28马尔可夫信源•一个不可约的、非周期的、状态有限的马尔可夫链其k步转移概率pij(k)在k→∞时趋于一个和初始状态无关的极限概率Wj，它是满足方程组的唯一解；•Wj：马尔可夫链的一个平稳分布，•Wj[或p(sj)]就是系统此时处于状态sj的概率。1jiijijjWWpW无论随机点从哪一个状态si出发，当转移的步数k足够大时，转移到状态sj的概率pij(k)都近似于一个常数Wj29•例5：有一个二元二阶马尔可夫信源,其信源符号集为{0，1}，已知符号条件概率：p(0|00)=1/2p(1|00)=1/2p(0|01)=1/3p(1|01)=2/3p(0|10)=1/4p(1|10)=3/4p(0|11)=1/5p(1|11)=4/5•求：⑴信源全部状态及状态转移概率⑵画出完整的二阶马尔可夫信源状态转移图。⑶求平稳分布概率30121234(0)(1)(00)1/21/2(01)1/32/3(|)(10)1/43/4(11)1/54/5jiaasspasss•状态转移概率矩阵•符号条件概率矩阵123412341/21/200001/32/3(|)1/43/400001/54/5jisssssspssss(1)1/2(0)1/2(0)1/3(1)2/300011110s2s1s4s3(1)3/4(0)1/4(0)1/5(1)4/531•稳态分布概率131132243244123411221344113524351ijijiWW12343664,,,35353571316161492353354355735八、连续信源的熵和互信息32()()log()cXXHXpxpxdx相对熵/连续熵33•限峰功率的最大相对熵定理对于定义域为有限的随机矢量X，当它是均匀分布时，其熵最大。随机变量X幅度取值限制在[a,b]，当信源达到最大熵。a1()0()1XbXpxbapxaxb其他()log()cHXba34•限平均功率最大相对熵定理对于相关矩阵一定的随机矢量X，当它是正态分布(高斯分布)时具有最大相对熵。即随机变量X的概率密度分布为信源熵最大。22221()()exp22Xxmpxm为均值，为方差。21()ln(2)2cHXe奈特/样值信道与信道容量第三章36•熟练掌握信道容量的相关概念信道分类（有记忆和无记忆信道）、信道容量、信源与信道匹配•熟练计算信道容量以及达到信道容量时对应的输入概率分布重点：无干扰离散信道、对称DMC（离散无记忆）信道、准对称信道习题5、637信道容量•信道容量C：–最大的信息传输率()1max(;),.()0,()1iniipaiCIXYstpapa381、无干扰离散信道•设信道的输入X∈A={a1…an},输出Y∈B={b1…bm}•1）无嗓无损信道–输入和输出符号之间有确定的一一对应关系0(|)(|)(,1,2,3)1jiijijpbapabijij()()()IXYHXHY；39•2）无嗓有损信道–多个输入变成一个输出(n＞m)(|)10(|)10ijijpbapab或或•噪声熵H(Y|X)＝0•损失熵H(X|Y)≠0()()()IXYHYHX；()max(;)max()ipaCIXYHY40•3）有嗓无损信道–一个输入对应多个输出(n＜m)•接收到符号Y后,对发送的X符号是完全确定的。•噪声熵H(Y|X)≠0损失熵H(X|Y)=0(;)()()IXYHXHY()max(;)max()ipaCIXYHX412、对称DMC信道•对称离散信道：•对称性:–每一行都是由同一集{q1,q2,…qm}的诸元素不同排列组成——输入对称–每一列都是由{p1,p2,…pn}集的诸元素不同排列组成——输出对称由输入对称推出由输出对称推出最佳的输入分布以及信道容量具体表达式12(|)(|)(,,)imHYXHYaHppp12log(,)mCmHppp42•对称DMC信道的容量（最佳输入为等概率分布）：•上式是对称离散信道能够传输的最大的平均信息量,它只与对称信道矩阵中行矢量{p1,p2,…pm}和输出符号集的个数m有关。121log(,)loglogmmijijjCmHpppmpp•强对称信道的信道容量：2log(1,,,)11pp