信息论与编码复习总结

信息论与编码理论复习资料By疯狂阿德第一章绪论考点：信息、消息、信号的区别通信系统模型香农1.信息、消息、信号的区别信息：指事物运动的状态或存在方式的不确定性的描述。消息：包含信息的语言、文字、图像等。信号：信息的物理体现。在通信系统中，实际传输的是信号，但实质内容是信息，信息包含在信号中，信号是信息的载体，通信的结果是消除或部分消除不确定性，从而获得信息。2.通信系统模型通信系统模型信源：信息输出的源。分离散信源和模拟信源。信宿：信息归宿之意，意即收信者或用户，是信息传送的终点或目的地。信道：传送信息的物理媒介。密钥源：产生密钥k的源。信号x经过k的加密运算后，就把明文x变换为密文y。一般地说，通信系统的性能指标主要是有效性、可靠性、安全性和经济性。除了经济性外，这些指标正是信息论的研究对象。信源编码：信源编码器的作用：一、将信源发出的信息变换成基带信号；二、压缩冗余度，提高效率（有效性）。信道编码：在信源编码器输出的代码组上有目的地增加一些监督码元，使之具有检错和纠错能力。信道译码器具有检错和纠错能力，它能将在其检错或纠错能力范围内的错传码元检测出来并加以纠正，以提高传输信息的可靠性。信道编码包括调制解调和纠错检错编译码。信道中的干扰通常使通信质量下降，对于模拟信号，表现在受到的信号的信噪比下降；对于数字信号就是误码率增大。信道编码的主要方法是增大码率或频带，即增大所需的信道容量。这恰与信源编码相反。3.香农他在1941年至1944年对通信和密码进行深入研究，并用概率论的方法研究通信系统，揭示了通信系统传递的对象就是信息，并对信息给以科学的定量描述，提出了信息熵的概念。还指出通信系统的中心问题是在噪声下如何有效而可靠地传送信息，而实现这一目标的主要方法是编码等。这一成果于1948年在《贝尔系统技术杂志》以《通信的数学理论》为题公开发表，次年，他又在同一杂志上发表了《噪声下的通信》香农因此成为信息论的奠基人。简答题：一、信源编码与信道编码的区别答：信源编码是压缩信源发出的信息的冗余度，是为了提高信息传输的有效性；而信道编码是在信源编码器输出的代码组上有目的地增加了一些监督码元，增大了信息的冗余度，以提高传输信息的可靠性。二、能否将三种码（信源编码、信道编码、密码）合成一种码进行编译？答：提高有效性必须去掉信源符号中的冗余部分,此时信道误码会使接收端不能恢复原来的信息,也就是必须相应提高传送的可靠性,不然会使通信质量下降；反之,为了可靠而采用信道编码,往往需扩大码率,也就降低了有效性。安全性也有类似情况编成密码,有时需扩展码位,这样就降低有效性；有时也会因失真而使授权用户无法获得信息,必须重发而降低有效性,或丢失信息而降低可靠性。从理论方面来说，若能把三种码合并成一种码来编译，即同时考虑有效、可靠和安全，可使编译码器更理想化，在经济上可能也更优越。这种三码合一的设想是当前众所关心的课题，但因理论上和技术上的复杂性，要取得有用的结果，还是相当困难。第二章信源与信息熵考点：自信息概率空间样本空间：某事物各种可能出现的不同状态。先验概率p(xi)：选择符号xi作为消息的概率。•对xi的不确定性可表示为先验概率p(xi)的倒数的某一函数。自信息后验概率p(xi|yj)：接收端收到消息yj后而发送端发的是xi的概率设离散信源X，其概率空间为如果知道事件xi已发生,则该事件所含有的信息量定义为:I(xi)含义:–当事件xi发生以前,表示事件xi发生的不确定性–当事件xi发生以后,表示事件xi所含有的信息量I(xi)的特性：)()()(2121nnxpxpxpxxxPX)(log)(iixpxI)()()(2121nnxpxpxpxxxPX)(1log)(iixPxI)(1log)(1log);(jiijiyxpxPyxI⑴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)⑸两个独立事件的联合信息量等于它们分别的信息量之和。即统计独立信源的信息量等于它们分别的信息量之和。•一个出现概率接近于1的随机事件，发生的可能性很大，所以它包含的不确定度就很小；•一个出现概率很小的随机事件，很难猜测在某个时刻它能否发生，所以它包含的不确定度就很大；•若是确定性事件，出现概率为1，则它包含的不确定度为0。联合自信息量两个消息xi，yj同时出现的联合自信息量•注意:•当xi,yj相互独立时，有p(xiyj)=p(xi)p(yj)，那么就有I(xiyj)=I(xi)+I(yj)。•xiyj所包含的不确定度在数值上也等于它们的自信息量。条件自信息量在事件yj出现的条件下，随机事件xi发生的条件概率为p(xi|yj)，则它的条件自信息量定义为条件概率对数的负值：信源–产生消息(符号)、消息序列和连续消息的来源–产生随机变量、随机序列和随机过程的源。)(log)(jijiyxpyxI)|(log)|(jijiyxpyxI–在通信系统中收信者在未收到消息以前对信源发出什么消息是不确定的,是随机的，所以可用随机变量、随机序列或随机过程来描述信源输出的消息,或者说用一个样本空间及其概率测度—概率空间来描述信源–信源的基本特性：具有随机不确定性。香农信息论的基本点：一、用随机变量和随机矢量来表示信源；二、用概率论和随机过程来研究信息。信源的分类：连续信源：指发出在时间和幅度上都是连续的消息（模拟消息）的信源。离散信源：指发出在时间和幅度上都是离散分布的离散消息的信源。离散无记忆信源：所发出的各个符号是相互独立的，发出的符号序列中的各个符号之间没有统计关联性，各个符号的出现概率是它自身的先验概率。•发出单个符号的信源–指信源每次只发出一个符号代表一个消息；•发出符号序列的信源–指信源每次发出一组含二个以上符号的符号序列代表一个消息信源的描述6/16/16/16/16/16/1654321xxxxxxPX离散有记忆信源：所发出的各个符号的概率是有关联的。发出符号信源的有记忆信源：用信源发出的一个符号序列的整体概率(即联合概率)反映有记忆信源的特征发出符号序列的马尔可夫信源：一个符号出现的概率只与前面一个或有限个符号有关,而不依赖更前面的那些符号不确定度定义：随机事件的不确定度在数量上等于它的自信息量。两者的单位相同，但含义却不相同。具有某种概率分布的随机事件不管发生与否，都存在不确定度，不确定度表征了该事件的特性，而自信息量是在该事件发生后给予观察者的信息量。平均自信息平均不确定度信源熵（公式一定要记住）H(X):平均信息量,称为信源X的熵。信源熵、香农熵离散信源熵H(X)(平均不确定度/平均信息量/平均自信息量)定义：信源的平均不确定度H(X)为信源中各个符号不确定度的数学期望，即：单位为比特/符号或比特/符号序列信息熵：从平均意义上来表征信源的总体信息测度的一个量。自信息：指某一信源发出某一消息所含有的信息量。所发出的消息不同,它们所含有的信息量也就不同。自信息I(xi)是一个随机变量,不能用它来作为整个信源的信息测度。信源熵具有以下三种物理含意：–信息熵H(X)表示信源输出后,每个离散消息所提供的平均信息量。–信息熵H(X)表示信源输出前,信源的平均不确定性。–信息熵H(X)反映了变量X的随机性条件熵H(x|y)、H(x|Y)在给定yj条件下，xi的条件自信息量为I(xi|yj),X集合的条件熵H(X|yj)为iiiiiixpxpxIxpXH)(log)()()()()|()|()|(jiijijyxIyxpyXH在给定Y(即各个yj)条件下,X集合的条件熵H(X|Y)条件熵是在联合符号集合(X,Y)上的条件自信息量的联合概率加权统计平均值。条件熵H(X|Y)表示已知Y后，X的不确定度。相应地，在给定X(即各个xi)条件下，Y集合的条件熵H(Y|X)定义为联合熵H(X,Y)H(X,Y)=H(X)+H(Y|X)联合熵是联合符号集合(X,Y)上的每个元素对(xi,yj)的自信息量的概率加权统计平均值。联合熵H(X,Y)表示X和Y同时发生的不确定度。H(XY)与H(X)、H(X/Y)之间的关系H(X,Y)＝H(X)＋H(Y|X)H(X,Y)＝H(Y)＋H(X|Y)单符号序列马尔科夫信源，m阶马尔科夫信源（了解）马尔科夫信源：一类相对简单的离散平稳信源，该信源在某一时刻发出字母的概率除与该信源有关外，只与此前发出的有限个字母有关。)|(),()|()|()()|()()|(jiijjijijiijjjjjyxIyxpyxIyxpypyXHypYXH)|(log),()|(),()|(ijijjiijijjixypyxpxyIyxpXYH),(log),(),(),(),(jiijjijiijjiyxpyxpyxIyxpYXHm阶马尔科夫信源：信源输出的某一符号的概率只与以前的m个符号有关，而与更前面的符号无关。马氏链的基本概念一阶马尔科夫信源：•若把有限个字母记作一个状态S，则信源发出某一字母的概率除与该字母有关外，只与该时刻信源所处的状态有关。•信源将来的状态及其送出的字母将只与信源现在的状态有关，而与信源过去的状态无关。•令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…状态转移图，状态转移概率•设信源在时刻m处于si状态,它在下一时刻(m+1)状态转移到sj的转移概率为：pij(m)=p{Sm+1=sj|Sm=si}=p{sj|si}•pij(m)：基本转移概率（一步转移概率）•若pij(m)与m的取值无关,则称为齐次马尔可夫链pij=p{Sm+1=sj|Sm=si}=p{S2=sj|S1=si}•pij具有下列性质：pij≥0•若信源处于某一状态si,当它发出一个符号后,所处状态就变了,任何时候信源处于什么状态完全由前一时刻的状态和发出符号决定。•系统在任一时刻可处于状态空间S={s1,s2,…,sQ}中的任意一个状态,状态转移时,转移概率矩阵•符号条件概率矩阵)|()|()|()(),,,(121121321LLLLLxxpxxpxxpxpxxxxpjijp1QQQQijppppsspP1111)|(QnQnijppppsxpP1111)|(符号条件概率到状态转移概率的转换：如在状态01时，出现符号0，则将0加到状态01的后面，再将第一位符号0挤出，转移到状态10互信息I(X,Y)定义为xi的后验概率与先验概率比值的对数互信息I(xi;yj)表示接收到某消息yj后获得的关于事件xi的信息量。平均互信息定义•Y未知,X的不确定度为H(X)•Y已知,X的不确定度变为H(X|Y)信息=先验不确定性－后验不确定性=不确定性减少的量条件互信息我们定义在已知事件zk的条件下,接收到yj后获得关于某事件xi的条件互信息平均互信息与各类熵的关系)()|(log);(2ijijixpyxpyxI)()|(log)()()(log)()|(log);(jijjijiijijiypxypypxpyxpxpyxpyxI)|()()|()();(ijjjiijixyIyIyxIxIyxI)|()();(YXHXHYXI)|()|()|(log)|()|(log)|()|(log)|;(kjkikjikjkijk