《信息论与编码》绪论-信源及信源熵.doc

南京工程学院备课笔记-信息论与编码-绪论、信源与信息熵第1次课 第一章 绪论简单介绍本课程1. 教学重点和计划1) 信源及信源熵：约8学时2) 无失真信源及无失真信源编码：约8学时3) 限失真信源及限失真信源编码：约8学时4) 信道及信道容量、信道编码：约12学时5) 密码学：约8学时2. 参考书1）信息论及信息处理，吴伟陵，人民邮电出版社2）信息论基础理论与应用，傅祖芸编著，电子工业出版社，20013）信息理论与编码，姜丹，钱玉美编著4）信息论基础教程，李亦农编著，北京邮电大学出版社，20051信息的概念信息这一概念是在人类社会互通情报的实践过程中产生的。信息在发展过程中主要经历了五次大的革命：1、声音、手势及语言；2、文字符号进入人类社会；3、印刷术提供了新的信息活动手段：增大了信息的传播范围；4、电磁波开始传播信息：加快了传播速度；5、计算机与通信的完美结合。推动信息革命和信息技术发展的三项技术： 微电子技术信息技术的“细胞” 通信技术信息技术的神经 计算机技术信息技术的大脑信息科学是一门综合性学科，它是研究信息及其运动规律的科学。其内容包括：信息的本质及其度量，信息的产生、获取、传播、处理和施效的规律。研究的目的是扩展人类获取和利用信息的能力。信息技术是运用信息科学的研究成果来解决生产实际问题，包括： 感测技术（信息获取） 通信技术（信息传输） 计算机技术（信息处理） 自动控制技术（信息施效）信息产业是专门从事信息生产、传播、出售和服务的产业，包括：信息技术设备制造、信息服务等。n 信息的定义我国学者钟义信教授对信息的定义为：信息就是在事物运动的状态和方式，就是关于事物运动的千差万别的状态和方式的认识。信息是事物的状态和状态变化的方式。1、 信息是无形的2、 信息是可共享的3、 信息是可扩充的4、 信息是可以度量的分析通信过程，通信的目的不外有两种情形：一是自己有某种形式的信息要告诉对方，同时估计对方既会对这种信息感到兴趣，而又尚不知道这个信息。也就是说，对方在关于这个信息的知识上存在着不确定性；另一种情况是，自己有某种疑问要向对方询问，而且估计对方能够解答自己的疑问。在前一种情况下，如果估计对方已经了解所欲告之的消息，就没有必要通信了；在后一种情况，如果自己没有疑问，当然就不必询问了。这里所谓“疑问”、“不知道”，就是一种知识上的“不确定性”，即对某个事情的若干种可能结果，或对某个问题的若干可能答案，不能做出明确的判断。因此可以把作为“通信的消息”来理解的“狭义信息”，看作(或明确定义)为一种用来消除通信对方知识上的“不确定性”的东西。引伸出一个十分重要而关键的结论：接收者收到某一消息后所获得的信息，可以用接收者在通信前后“不确定性”的消除量来度量。简而言之，接收者所得到的信息量，在数量上等于通信前后“不确定性”的消除量(或减少量)。这就是信息理论中度量信息的基本观点。那么，很自然地接着要问这样一个问题：这就是，“不确定性”本身是否可度量？是否可用数学方法来表示呢？而不确定性是与“多种结果的可能性”相联系的，在数学上这些“可能性”正是以概率来度量的。概率大，即“可能性”大；概率小，“可能性”小。显然“可能性”大，即意味“不确定性”小；“可能性”小，即意味“不确定性”大。可见，“不确定性”与概率的大小存在着一定的联系，“不确定性”应该是概率的某一函数；那么，“不确定性”的消除量(减少量)，也就是狭义信息量，也一定可由概率的某一函数表示。这样就完全解决了作为“通信的消息”来理解的“狭义信息”的度量问题。这个问题先放在这，我们到底用什么样的数学公式来度量信息，这个公式是否是唯一的？以及如何度量？这是我们下一步要解决的疑问。2信息论的研究对象、目的和内容信息论的奠基人香农“通信的基本问题就是在一点重新准确地或近似地再现另一点所选择的消息”。这是数学家香农（Claude E.Shanon）在他的惊世之著通信的数学理论中的一句铭言。正是沿着这一思路他应用数理统计的方法来研究通信系统，从而创立了影响深远的信息论。香农，1816年生于美国密执安州的加洛德。在大学中他就表现出了对数理问题的高度敏感。他的硕士论文就是关于布尔代数在逻辑开关理论中的应用。后来他就职于贝尔电话研究所。在这个世界上最大的通信公司（美国电话电报公司）的研究基地里，他受着前辈的工作的启示，其中最具代表性的是贝尔系统技术杂志上所披露的奈奎斯特的影响电报速率的一些因素和哈特莱的信息的传输。正是他们最早研究了通信系统的信息传输能力，第一次提出了信息量的概念，并试图用教学公式予以描述。香农则创造性地继承了他们的事业，在信息论的领域中钻研了8年之久，终于在1948年也在贝尔系统技术杂志上发表了244页的长篇论著，这就是上面提到的那篇通信的数学理论。次年，他又在同一杂志上发表了另一篇名著噪声下的通信。在这两篇文章中，他解决了过去许多悬而未决的问题：经典地阐明了通信的基本问题，提出了通信系统的模型，给出了信息量的数学表达式，解决了信道容量、信源统计特性、信源编码、信道编码等有关精确地传送通信符号的基本技术问题。两篇文章成了现在信息论的寞基著作。而香农，也一鸣惊人，成了这门新兴学科的奠基人。那时，他才不过刚刚三十出头。那么信息论的研究对象、目的和内容具体是什么呢？信息论的研究对象、目的和内容信息论或称为通信的数学理论，是应用近代数理统计方法研究信息的度量、传输、存储、交换与处理的一门科学。它是通信理论中的基础理论。信息论研究的主要问题是在通信系统设计中如何实现信息传输、存储和处理的有效性和可靠性。传输系统的模型主要几个部分： 信源编码、信源译码解决了信息传输的有效性。 信道编码、信道译码解决了信息传输的可靠性。 加密编码、解密译码限制了信息传输的共享，增加了保密性。信息传输系统的要求 可靠性：可靠性高，就是要使信源发出的消息经过信道传输以后，尽可能准确地、不失真地再现在接收端。如何来提高可靠性呢？ 有效性：有效性高，就是用尽可能短的时间和尽可能少的设备来传送一定数量的信息。如何提高有效性呢？ 保密性：保密性高，就是隐蔽和保护通信系统中传送的消息，使它只能被授权接收者获取，而不能被未授权者接收和理解。如何获取保密性？ 认证性：是指接收者能正确判断所接收消息的正确性，验证消息的完整性，而不是伪造的和被篡改的。信源和信宿信源：产生消息的源。消息可以是文字、语言、图像等。它可以是离散序列，也可以是连续形式，但都是随机发生的，即在未收到这些消息之前不可能确切地知道它们的内容。这些消息可以用随机变量或随机过程来描述。信源研究的主要内容是消息的统计特性和信源产生信息的速率。信宿：消息传送过程中的接收者，即接收消息的人或物。信宿和信源可处于不同的地点或存在于不同时刻。例如：远古时代的文字。信道信道：把载荷消息的信号从发射端传到接收端的媒质或通道，是包括收发设备在内的物理设施。在狭义的通信系统中，实际信道有架空明线、电缆、波导、光纤、无线电波传播空间等。对广义的通信系统来说，信道还可以是其他传输媒介。信道中存在干扰源。实际干扰可以分成以下两大类：1、加性干扰。由外界引入的随机干扰，如天电干扰以及设备内部噪声，它们与信道的输入信号统计无关。信道的输出是输入信号和干扰的和。2、乘性干扰。信号在传播过程中由于物理条件的变化引起信号参量的随机变化而构成的干扰。此时信道的输出信号是输入信号与某些随机参量相乘的结果。研究信道的中心课题是它的统计特性和传输能力。编码部分编码部分：将信源发出的消息变换成适于信道传送的信号的设备。在此回答前面的三个问题：1、信源编码器：在一定的准则下，对信源输出的消息进行适当的变换和处理，其目的在于提高信息传输的效率。2、纠错编码器：对信源编码器的输出进行变换，用以提高对于信道抗干扰能力，亦即提高信息传输的可靠性。3、调制器。调制器是将纠错编码器的输出变成适合于信道要求的信号形式。是通信系统要研究的主要内容，通信原理研究的内容。译码部分译码：编码的逆变换。它要从受干扰的信号中最大限度地提取出有关信源输出消息的信息，并尽可能地复现信源的输出。译码器可分为：信源译码器和信道译码器。信道译码器又包括：纠错译码器和解调器。译码部分的输出送给信宿，完成通信过程。2.3信息论的内容n 狭义信息论（香农基本理论）在信息可以度量的基础上，对如何有效、可靠地传递信息进行研究的科学，涉及信息度量、信息特性、信息传输速率、信道容量、干扰对信息传输的影响等。无失真信源编码有失真信源编码压缩理论传输理论网络信息理论算术码LZ码MH码保密理论香农信息论无噪声有噪声保密系统的信息论等长编码定理变长编码定理最优码构成压缩编码码构成信道编码定理网络最佳码网络信道保密码纠错码代数编码卷积码n 一般信息论（通信理论）主要研究信息传输和处理问题。除香农理论外，还包括噪声理论、信号滤波和预测、统计检测和估计理论、调制理论、抗干扰理论、信号处理理论以及保密理论。n 广义信息论（信息科学）不仅包含上述内容，还包括所有与信息有关的自然和社会领域，具有更广泛的研究内容。2.4信息论的形成与发展1924年奈奎斯特解释了信号带宽和信息率（传递信息的速率）之间的关系：如果以一个确定的速率来传输电报信号，就需要一定的带宽。将信息率和带宽联系起来了。1928年哈特莱引入了非统计（等概率事件）信息量概念。提出信息量等于可能消息数的对数。1936年达得利提出在传输过程中增大带宽可以增强抑制干扰的能力。根据这一思想，提出了宽频移的频率调制方法。20世纪40年代初期，由于军事上的需要，维纳在研究防空火炮的控制问题时，提出了平稳时间序列的外推、内插与平滑及其工程应用的论文。他把随机过程和数理统计的观点引入通信和控制系统中来，揭示了信息传输和处理过程的统计本质。这种统计观点的引入使得信息论产生质的飞跃。他还利用早在20世纪30年代初他本人提出的“广义谐波分析理论”对信息系统中随机过程进行谱分析。这就使通信系统的理论研究引起了质的飞跃，取得了突破性进展。1948年香农在贝尔系统技术杂志上发表了两篇有关“通信的数学理论”的文章。在这两篇论文中，他用概率测度和数理统计的方法，系统地讨论了通信的基本问题，得出了几个重要的而带有普遍意义的结论，并由此奠定了现代信息论的基础。从20世纪50年代开始，信息论在学术界引起巨大的反响。1951年美国IRE成立了信息论组。1955年正式出版了信息论汇刊。在此期间，一些科学家（包括香农本人）做了大量工作，发表了许多重要文章。他们将香农已得到的数学结论作了进一步的严格论证和推广。信息论中无失真信源编码部分的发展：香农在1948年论文中提出无失真信源编码定理，也给出了简单的编码方法（香农编码）。麦克米伦于1956年首先证明了唯一可译变长码的克拉夫特不等式。对于无失真编码的研究具有重要的意义。1952年费诺提出了费诺码。1952年霍夫曼首先构造了一种霍夫曼编码方法，并证明了它是最佳码。早期的传真采用霍夫曼编码方法。1968年，埃利斯发展了香农费诺码，提出了算术编码的初步思路。1976年里斯桑内给出和发展了算术编码。1982年他和兰登一起将算术编码系统化，并省去了乘法运算，更为简化，易于实现。通用信源编码算法LZ码是1977年由齐弗和兰佩尔提出的。1978年他们又提出了改进算法，并证明此方法可达到信源的熵值。1990年贝尔等在LZ算法基础上又作了一系列变化和改进。LZ码已广泛应用于文本的数据压缩中。信息论中信道编码纠错码理论的发展：60年代，信道编码技术有了较大发展，使它成为信息论的一个重要分支纠错码理论。1950年出现汉明码，把代数方法引入到纠错码的研究，形成了代数编码理论。但代数编码的渐进性很差，不能够实现香农信道编码定理所指出的结果。1960年左右提出了卷积码的概率译码，形成一系列概率译码理论。几十年来，相继出现的很多编码方法，其性能与香农限相差很远，以致人们认为香农限是不可能达到的。1993年C.Berrou等人提出的Turbo码的并行级联卷积码，性能非常接近香农限，同时复杂度较低可以实现，为信道编码领域带来一场革命。限失真信源编码的发展：有一定失真的信源编码称限失真信源编码，它的研究比信道编码和无失真信源编码晚约十年。香农在1948年论文中已体现出关于率失真函数的思想。1959年香农发表了“保真度准则下的离散信源编码定理”，首先提出了信息率失真函数及信息率失真信源编码定理。从此，发展成为信息率失真编码理论。1971年伯格尔给出更一般信源的率失真编码定理。率失真信源编码理论是信源编码的核心问题，是频带压缩、数据压缩的理论基础。信息量过大一定要进行压缩。网络信息论的发展：1961年香农发表的论文双路通信信道开拓了多用户理论的研究。随着卫星通信、计算机通信网络的迅速发展，多用户理论的研究取得了许多突破性进展。从20世纪70年代以后，人们从经典的香农单向通信的信息论推广到多用户信息理论。多用户信息理论成为当前信息论的中心研究课题之一。第2次课 第二章 信源与信息熵1自信息量和平均自信息量一个随机事件在事件发生前有不确定性，在事件发生时有惊讶度，在事件发生后有信息量。当一个概率很低的随机事件发生，我们就会感到非常惊讶，并得到很大的信息量。从信息源获得信息的过程就是其不确定性缩减的过程。随机事件包含的信息与其不确定性紧密相关。上节课中讲过，在统计分析中，使用概率作为衡量不确定性的一种指标。可以推论出：随机事件包含信息的度量应是其概率的函数。那么，随机事件所包含的信息量与其发生的概率有什么样的关系呢？1.1自信息量n 自信息量的定义任意随机事件的自信息量定义为该事件发生概率的对数的负值。自信息量的单位取决于对数选取的底。当对数的底取2时，比特（bit）；以e为底时，奈特（nat）；以10为底时，哈特（hart）。三者之间的转换关系如下： n 自信息量的性质1、当时， 确定事件信息量为02、当时， 概率为0的事件带来极大的信息量3、非负，因为概率是01之间的随机数4、是的单调递减函数5、是一个随机量，是的函数，也是一个随机变量，没有确定的值。提问：能反映整个信源的不确定性吗？不能，那么用什么量来反映呢？1.2平均自信息量熵一个信源可以用一个概率空间来描述：其中：X是信源的状态空间，为一个离散集，表示了随机事件的状态数；P(X)是随机事件各种可能状态的概率分布，且，即状态是完备的；各状态是独立的。通常记为。n 平均自信息量信息熵定义集X上，随机变量的数学期望定义为平均自信息量：集X的平均自信息量即X的信息熵，简称熵。数值上与平均不确定度相同，含义不同。平均不确定性的含义：集X的平均自信息量表示集X中事件出现的平均不确定性。在观测之前，确定集X中出现一个事件平均所需的信息量；在观测之后，集X中每出现一个事件平均给出的信息量。举个例子说明熵的计算和物理含义。n 熵函数的性质1、对称性：当概率矢量中的各分量的次序任意变更时，熵值不变。该性质说明信源的熵仅与信源总体的统计特性有关。2、 非负性：等号成立的充要条件是当且仅当对某，其余的。即确知信源的信源熵等于零。（非负性对于离散信源的熵是正确的，但是对于连续信源来说，其性质不存在。）此时即为熵的确定性：3、扩展性：含义：若集合X有q个事件，另一个集合X有q+1个事件，但X和X集的差别只是多了一个概率接近于零的事件，则两个集的熵值一样。换言之，一个事件的概率与其中其它事件的概率相比很小时，它对集合的熵值的贡献可以忽略不计。4、可加性如果有两个随机变量X、Y，它们不是相互独立的，则二维随机变量（X,Y）的熵等于X的无条件熵加上当X已给定时Y的条件概率定义的熵的统计平均值，即其中：为已知条件下，的条件概率；（对一切i）。当二维随机变量X，Y相互统计独立时，则有：5、极值性，其中n是集合X的元素数目。在离散情况下，集合X中的各事件等概率发生时，熵达到极大值。这个重要结论称为最大熵定理。集合中元素的数目n越多，其熵值就越大。对数函数的单调上升性。6、上凸性是概率分布的严格上凸函数。凸函数定义为：设为一多元函数。若对仪任意一个小于1的正数以及函数f(X)定义域内的任意两个矢量、有则称f(X)为定义域上的上凸函数。如是大于，则为严格上凸函数。反之若有则称f(X)为定义域上的下凸函数（Cup型函数）。如是小于，则为严格下凸函数。2联合自信息量和联合熵n 联合自信息量二维联合集XY上的元素的联合自信息量定义为：。式中为积事件（联合随机事件），为元素的二维联合概率。当X和Y相互独立时，。即两个随机事件相互独立时，同时发生得到的自信息量，等于这两个随机事件各自独立发生得到的自信息量之和。n 联合熵（共熵）联合集XY上，每对元素的自信息量的概率加权平均值定义为联合熵。将积事件作为一个随机事件求其平均不确定性。根据联合自信息量的定义，联合熵又可定义为：。3条件自信息量和条件熵n 条件自信息量定义：在联合集XY中，对事件和，事件在事件发生的条件下的条件自信息量定义为：。是条件概率，即事件在事件发生的情况下的概率。由于每个随机事件的条件概率都处于01范围内，所以条件自信息量均为非负值。几种自信息量之间的关系：1、自信息量、联合自信息量、条件自信息量都满足非负性和单调递减性。2、三者都是随机变量，其值随着变量和的变化而变化。3、三者之间有如下关系式：n 条件熵联合集XY上，条件自信息量I(x|y)的概率加权平均值定义为条件熵。其定义式为：联合集XY中，集Y相对于集X的条件熵。还可写成。提问：为什么在求和中要用联合概率进行加权平均？表示前面一个消息符号给定时，信源输出下一个消息符号的平均不确定性。由于给定不同的，是变动的，因此，是一个随机变量。故应求出的统计平均值：小结自信息量-平均自信息量联合自信息量-联合熵条件自信息量-条件熵第3次课4互信息量和平均互信息4.1互信息量n 定义信源发出的符号消息集X，Y表示信宿接收的符号消息集合，各自的概率空间为：和。当接收端收到集合Y 中的一个消息符号后，重新估计关于信源的各个消息发生的概率就变成条件概率，即后验概率。收信者收到一个消息后，所获得的信息量等于收到消息前后不确定程度的减少量。不确定程度减少的原因，是由于收到消息前后概率空间的概率分布改变所致。当接收到后，重新估计的发生。收信者从不确定到比较确定或完全确定，依赖于所获得的信息量。可以直观地将它定义为：I（信息量）=不确定程度的减少量。当接收者收到后，所获得的信息量为收信者所获得的信息量随先验概率的增加而减少，随后验概率的增加而增加。在通信前，将信道看成关闭，可以认为输入随机变量X和输出随机变量Y之间没有任何关联关系，即X、Y统计独立。根据概率的性质，输入端出现和输出端出现的概率，有先验不确定度。在通信后，输入随机变量X和输出随机变量Y之间由信道的统计特性相联系。输入端出现和输出端出现的联合概率为，则有后验不确定度。通信后流经信道的信息量等于通信前后不确定度的差，即带来关于的信息量：，其中。互信息量定义为自信息量减去条件自信息量的差。互信息量为两个不确定度之差，是不确定度被消除的部分，代表已经确定的东西。实际是从得到的关于的信息量。即等于先验的不确定性减去尚存在的不确定性。同样道理，可定义对的互信息量为：n 互信息量的性质1. 互易性：2. 互信息量可为零当事件、统计独立时，互信息量为零：。这表示不能从观测获得关于另一个事件的任何信息。反之亦然。3. 互信息量可正可负当后验概率大于先验概率时，互信息量大于零，为正值。互信息量为正，意味着事件的出现有助于肯定事件的出现；当后验概率小于先验概率时，互信息量小于零，为负值。互信息量为负是不利的，原因是由于信道干扰使估计变得更加困难，即不确定性增加了。4. 任何两个事件之间的互信息量小于其中任一事件的自信息量；这说明自信息量是为了确定事件的出现所必须提供的信息量，也是任何其它事件所能提供的关于事件的最大信息量。4.2平均互信息量n 定义在联合集XY上，由提供的关于集X的平均条件互信息量等于由所提供的互信息量在整个X中以后验概率加权的平均值，其定义式为定理：联合集XY上的平均条件互信息量有，等号成立当且仅当X集中的各个都与事件相互独立。平均条件互信息量表示观测到后获得的关于集X的平均信息量。仍然是一个随机变量，随的变化而变化，因此，不能作为信道中流通信息量的整体测度。n 平均互信息量的性质1. 非负性：，当且仅当X与Y相互独立时，等号成立。即如果X与Y相互独立，它们之间相互不能提供任何信息。2. 互易性（对称性）：从集Y中获得关于X的信息量等于从集X中获得关于Y的信息量。集X和集Y统计独立时，有，它意味着不能从一个集获得关于另一个集的任何信息。3. 平均互信息和各类熵的关系集X和Y统计独立时，得到。n 平均互信息量的物理含义I(X;Y)是H(X)和H(X/Y)之差。因为H(X)是符号集合X的熵或不确定度，而H(X/Y)是当Y已知时X的不确定度，可见“Y已知”这件事使X的不确定度减少了I(X;Y)，这意味着“Y已知”后所获得的关于X的信息量是I(X;Y)。这可以看成是信源符号集合X，信宿符号集合Y，平均互信息量I(X;Y)表示在有扰离散信道上传输的平均信息量。信宿收到的平均信息量等于信宿对信源符号不确定度的平均减少量。损失熵H（X/Y）、疑义度：条件熵H（X/Y）表示在已知输出Y的条件下输入X的剩余不确定性，即信道损失。根据互信息量与条件熵的关系可看出，等于输入平均信息量减去信道损失，它反映了信道传输信息的能力。最大平均互信息量就是信道容量。噪声熵H（Y/X）、散布度：互信息量可以看作在有扰离散信道上传递消息时，唯一地确定接受符号y所需要的平均信息量H(Y)，减去当信源消息已知时确定接受符号y仍然需要的平均信息量H(Y/X)，因此，H(Y/X)可认为是唯一地确定信道噪声所需要的平均信息量。两种特殊情况：1）此时，这表明，当后验概率p(xi/yj)1(即收到输出符号yj，推测输入符号xi的概率为1)时，收到yj即可确切无误地收到输入符号xi，消除对xi得全部不定度，从yj中获取xi本身含有的全部信息量，即xi的自信息量I(xi)。此时Y已知就完全解除了关于X的不确定度，所获得的信息就是X的不确定度或熵。也可以看成是无扰信道，由于没有噪声，疑义度H(X/Y)为零，噪声熵也为零。于是有I(X;Y)=H(X)=H(Y)。2）这时，由于后验概率等于先验概率p(xi)，所以后验概率与先验概率的比值等于1，即有。这表明，当后验概率等于先验概率p(xi)时，收到yj后对信源发xi的不定度等于收到yj前对信源发xi的不定度，收到yj后并没有减少对信源发xi的不定度，从yj中获取不到关于xi的信息量。4. 极值性：5. 凸函数性上凸性：给定时，是信源概率分布的上凸函数。引出后面章节中信道容量的定义：下凸性：给定时，是信道传递概率分布的下凸函数。引出后面章节中率失真函数的定义：5数据处理中信息的变化n 三维联合集（X，Y，Z）上的平均互信息量在联合集XYZ中，在给定的条件下，与之间的互信息量定义为条件互信息量。其定义为：联合集XYZ上还存在与之间的互信息量，其定义式为：可进一步表示为：上式表明，一切事件出现后所提供的有关的信息量等于事件出现后所提供的有关的信息量加上在给定事件的条件下再出现事件所提供的有关的信息量。三维联合集（X，Y，Z）上的平均互信息量有：I(X;Y,Z)=I(X;Y)+I(X;Z/Y)I(Y,Z;X)=I(Y;X)+I(Z;X/Y)I(X;Y,Z)=I(X;Z,Y)=I(X;Z)+I(X;Y/Z)第一级处理第二级处理XYZn 数据处理中信息的变化由I(X,Y;Z)=I(X;Z)+I(Y;Z/X)和I(X,Y;Z)=I(Y;Z)+I(X;Z/Y)可得：I(X;Z)=I(Y;Z)+I(X;Z/Y)-I(Y;Z/X)假设在Y条件下X与Z相互独立，即I(X;Z/Y)=0，且I(X;Y/Z)和I(Y;Z/X)均非负，则有：I(X;Z)I(Y;Z) I(X;Z)I(X;Y)说明：当消息经过多级处理时，随着处理级数的增多，输入消息和输出消息之间的平均互信息量趋于变小。数据处理定理：数据的处理过程中只会失掉一些信息，绝不会创造出新的信息，即信息不增性。6各种熵的性质n 各种熵的关系1、联合熵与信息熵、条件熵的关系2、联合熵与信息熵的关系3、条件熵与通信熵的关系：例：求联合集X，Y上的各种熵设一系统的输入符号集，输出符号集，如图所示。解：首先求先验概率、后验概率 ， ， ， ，然后计算联合熵和信息熵计算条件熵关系式验证例题注意到：小结：为了介绍两个离散集之间的平均互信息量，首先定义了在一个事件发生条件下，给出的另一个离散事件集的平均条件互信息量。在平均条件互信息量的基础上，定义了一个离散集合对另一个离散集的平均互信息量。分析总结了各种信息熵与平均互信息量之间的关系，并给出了反映这种关系的维拉图。最后，讨论了平均互信息的性质。第4次课 第2章 离散信源1 信源的数学模型及其分类n 概述信源：信息的来源，是产生消息（符号）、时间离散的消息序列（符号序列）以及时间连续的消息的来源。信息论中，用随机变量X、随机矢量X和随机过程X(e,t)分别表示产生消息、消息序列和时间连续消息的信源。主要解决的问题：n 如何描述信源？（数学模型）n 如何定量描述信源输出信息的能力？n 怎样有效地表示信源输出的消息？（信源编码）对信源的分类主要基于两方面的考虑：一是信源消息取值的集合以及消息取值时刻的集合，由此可分为离散信源、连续信源或数字信源、模拟信源（波形信源）二是信源消息的统计特性，由此可分为无记忆信源、有记忆信源、平稳信源、非平稳信源、高斯信源、马尔可夫信源等。实际中经常是它们的组合，如离散无记忆信源等。无记忆信源：信源发出的消息符号间彼此是统计独立的，并且他们具有相同的概率分布，且N维随机矢量的联合概率分布为：称为离散无记忆信源。同样，若N维随机矢量中X每个变量是连续随机变量，且相互独立，则X的联合概率密度函数为，这种信源叫连续型无记忆信源。有记忆信源：信源发出的符号间是彼此相互依存和关联的。通常用联合概率或条件概率来描述这种关联性。按记忆长度划分有：有限记忆信源（马尔可夫信源）；无限记忆信源。M阶马尔卡夫信源m阶马尔可夫信源：信源记忆长度为m+1，即信源每次发出的符号仅与前面m个符号有关，与更前面的符号无关。用条件概率描述为：其中m为阶数。当m=1时，为一阶马尔可夫信源，此时条件概率转化成状态转移概率时齐遍历马尔可夫信源时齐性：转移概率与时间起点无关。遍历性：当转移步数足够大时，转移概率与起始状态武官，即达到平稳分布。时齐遍历马尔可夫信源：同时满足时齐性和遍历性。混合信源按信源输出时间和取值划分：时间连续、取值连续或随机的，称之为随机波形信源，表示为X(t)。输出既有连续分量又有离散分量，称之为混合信源。n 信源的数学模型随机变量X：离散信源：输出的消息数有限。，其中，即信源的概率空间是完备的。连续信源：可能输出的消息数是无限的或不可数的。，其中为连续随机变量X的概率密度函数，(a, b)为X的存在域，且。随机序列X随机序列即多符号信源的数学模型N重离散概率空间：其中非平稳信源：马尔可夫信源：输出的随机序列X中各随机变量之间有依赖关系，但记忆长度有限，并满足马尔可夫链的条件式。平稳信源：离散平稳信源：输出的随机序列X中每个随机变量取值是离散的，并且随机矢量X的各维概率分布不随时间平移而改变。离散无记忆信源的N次扩展信源：输出的平稳随机序列X中各随机变量统计独立。每个随机变量取值于同一概率空间。每N个符号一组，等效为一个新的信源。有限记忆信源：输出的平稳随机序列X中各随机变量之间有依赖关系，记忆长度有限。随机过程X(t)：随机波形信源：信源输出的消息是时间（或空间）上和取值上都是连续的函数。2离散无记忆信源2.1单个符号离散无记忆信源设信源X输出符号集，q为消息符号个数，每个符号发生的概率为，如消息符号彼此互不相关，则称X为离散无记忆信源。前述基本是单个符号离散信源。回顾：消息与不确定度、不确定度与自信息量的关系；自信息量与信源熵2.2多符号离散无记忆信源离散无记忆序列设X是一个离散无记忆信源，其概率空间，其中q为信源符号个数，。则X的N次扩展信源是具有个消息符号的离散无记忆信源，其概率空间为，其中：，。即积事件是N长的随机序列，其中每个随机变量有q个消息符号，且每个消息统计独立。2.3离散序列的熵n 定义长度为L的离散无记忆序列信源X=(X1,X2,Xl,XL)，序列中的单个符号变量Xlx1,x2,xn。根据熵的定义，可得序列熵为：信源无记忆时满足平稳特性时，这样，平均符号熵=序列熵/L，即为单个符号的符号熵。n 例题设有一离散无记忆信源X，其概率空间为，求长度为2的离散序列信源的熵。因为信源X共有q=3个符号，扩展N=2次，故二次扩展信源有个不同的符号，又因为信源是无记忆的，所以离散序列熵为：所以有。4离散平稳信源n 平稳的定义若信源产生的随机序列满足：1、 所有都取值于有限的信源符号集；（A中每个状态是离散的、状态明晰的）2、 随机序列是平稳的，即对所有非负整数及有则称此信源为离散平稳信源。平稳信源发出的符号序列的概率分布与时间起点无关，即，平稳信源发出的符号序列的概率分布函数可以平移。这样讨论N长的时间序列时不需要考虑时间起点。一维平稳信源对于随机变量序列，若任意两个不同时刻i和j信源发出消息的概率分布完全相同，这种信源为一维平稳信源。写成数学描述式即一维平稳信源无论在什么时刻均以分布发出符号。一维平稳信源即前面讨论的无记忆信源。二维平稳信源对于一个一维平稳信源，如果联合概率分布也与时间起点无关，即，其中为任意整数，且，则称为二维平稳信源。二维平稳信源在任何时刻发出两个符号的概率完全相同。二维平稳信源的二维联合分布与时间起点无关。N维平稳信源其中，i和j为任意整数，则称具有这样性质的信源为N维平稳信源。对于N维平稳信源，它在某个时刻发出什么样的符号只和它前面发出的k(kN)个符号有关。n 离散平稳信源的定义如各维联合概率分布均与时间起点无关，对两个不同的时刻i和j，有这种各维联合概率均与时间起点无关的完全平稳信源称为离散平稳信源。离散平稳信源一般是有记忆信源。发出的各个符号之间具有统计关联关系。4.2离散平稳信源的熵n 联合熵以最简单的二维平稳信源为例，它是N长为2的有记忆平稳信源。信源，概率空间为。由熵的定义得到联合熵：n 条件熵当平稳信源输出一个符号，那么对于信源的下一个输出符号，存在一个平均不确定性，显然该不确定性的大小因而异，对所有进行加权平均即可得当已知一个输出符号，信源输出下一个符号的总平均不确定性，即n 平稳信源熵的性质1、 熵的可加性 熵的强可加性。2、 二维平稳信源与二次扩展信源的关系当和取值于同一集合（概率空间时），与离散无记忆信源的二次扩展信源情况相同。所以离散无记忆信源的二次扩展信源可看成是二维离散平稳信源的特例。二维离散平稳信源是离散无记忆信源的二次信源的推广。3、二维平稳信源与二次扩展信源的熵说明二维离散平稳有记忆信源的熵小于等于二维离散无记忆信源的熵。对于二维离散平稳无记忆信源来说，是否发生对不产生任何影响。对于二维离散平稳有记忆信源，由于和有统计依赖关系，的发生会提供的部分相关信息。n 二维离散平稳信源熵例题设二维离散信源的原始信源X的信源模型为，中前后两个符号的条件概率如表。信源的熵为：条件熵比信源熵（无条件熵）减少了0.672比特/符号，这正是符号之间的依赖性所造成的。联合熵为信源X的每一个信源符号所提供的平均信息量为：显然它小于信源X提供的平均信息量，也是由于符号间的统计相关性所引起的。4.3极限熵n 离散平稳信源序列熵的特点1、是L的单调非增函数。2、3、是L的单调非增函数。4、极限熵：当，极限熵的意义：多符号离散平稳信源实际上就是信源在不断地发出符号，符号之间的统计关联关系也并不仅限于长度N，而是伸向无穷远。研究实际信源，必须器具出信源的极限熵。提问：是否存在？答：是存在的，且等于关联长度N趋于时，条件熵的极限值。如何求？极限熵存在定理对任意离散平稳信源，若则有：根据平稳信源的平稳性和条件熵的性质，有则。这表明是N的非递增函数，因而是有界的，即。可见平均符号熵的极限是存在的。n 极限熵的计算通过极限熵的存在性定理，可证明的值在和之间。令，有，所以这就是平稳有记忆信源极限熵的定义式，它规定了平稳离散有记忆信源输出符号序列中平均每个信源符号的熵值。小结实际信源往往比较复杂，在其定义上加入平稳性约束条件即为平稳信源，而平稳信源通常都是有记忆信源。分析了二维平稳有记忆信源和平稳无记忆二次扩展信源的关系。极限熵代表了一般离散平稳有记忆信源平均每发出一个符号所提供的信息量。计算联合熵或极限熵很困难，需要测定信源的无穷阶联合概率和条件概率。可用条件熵或平均符号熵作为极限熵的近似值。第5次课5马尔可夫信源5.1有限状态马尔可夫链m阶马尔可夫信源的定义：当信源的记忆长度为m+1时，该时该发出的符号与前m个符号有关联性，而与更前面的符号无关。n 马尔可夫链的定义由于高阶马尔可夫信源需要引入矢量进行分析，现方法将矢量转化为状态变量。定义状态：可知，将来时刻的状态与过去时刻的状态无关，仅与现在时刻的状态有关。即，已知系统的现在，那么系统的将来与过去无关。这种特性称为马尔可夫特性。n 转移概率1、定义为了知道系统状态的转化情况，引入转移概率它表示：已知在时刻m系统处于状态si的条件下，经(n-m)步后转移到状态sj的概率。转移概率的性质：(1)(2)2、 一步转移概率当n-m=1时，即为一步转移概率，记为。一步转移概率性质：1)；2) 3、k步转移概率它表示在时刻m时，的状态为i的条件下，经过k步转移到达状态j的概率。性质：1）；2）4、 k步转移矩阵系统在任一时刻可处于状态空间中的任一个状态，因此，状态转移时，各种转移概率构成一个矩阵称为k步转移矩阵。对应于矩阵P中的第i行j列之元素。满足性质 1、2的矩阵P是一个随机矩阵，它决定了系统所取状态过程的概率法则。一般地，在状态空间是是一可数无穷集合，所以转移矩阵P是一无穷行无穷列的随机矩阵。n 时齐马尔可夫链定义：若对于任意的，马尔可夫链的转移概率与m无关，即，则称这类马尔可夫链为时齐马尔可夫链，或齐次马尔可夫链。它是具有平稳转移概率的马尔可夫链。对于时齐马尔可夫链，一步转移概率具有性质：1、2、由一步转移概率可以写出其转移矩阵为：如果状态空间是有限的，则称它是有限状态的马尔可夫链。如果状态空间是无穷集合，则称它是可数无穷状态的马尔可夫链。切普曼-柯尔莫哥洛夫方程对于具有m+r步转移概率的齐次马尔可夫链，存在下述切普曼-柯尔莫哥洛夫方程：利用此方程就可以用一步转移概率表达多步转移概率。一般有：对于齐次马尔可夫链，一步转移概率完全决定了k步转移概率。值得指出的是，转移概率不包含初始分布，即第0次随机实验中的概率不能由转移概率表达。n 具有遍历性的马尔可夫链定义：若齐次马尔可夫链对一切i,j存在不依赖于i的极限：且满足，则称其具有遍历性，称为平稳分布。遍历性的意义：不论质点从哪个状态出发，当转移步数n充分大时，转移到状态的概率都近似等于某个常数。即如果转移步数n充分大，就可以用常数作为n步转移概率的近似值。n 马尔可夫链的稳态分布如果马尔可夫链具有遍历性，意味着马尔可夫信源在初始时刻可以处在任意状态，然后信源状态之间可以转移。由初始分布及各时刻的一步转移概率就可以完整描述马尔可夫链的统计特性。经过足够长时间之后，信源处于什么状态已与初始状态无关。这时，每种状态出现的概率已达到一种稳定分布，即平稳分布。对于有限状态马尔可夫链，如果存在一个数集，且满足，则称该马尔可夫链的稳态分布存在。对于一个有r个状态的马尔可夫链，若令：则可以写出t=n-1与t=n时刻的状态方程设，则上式可以表示成将上式递推运算后可得，这就是说，t=n时刻的状态分布矢量是初始分布矢量与转移矩阵P的n次幂的乘积。稳态分布存在性定理一：设有一马尔可夫链，其状态转移矩阵为，其稳态分布为，则：1）2）是该链的稳态分布矢量，即WP=W；2）如果初始分布，则对所有的n，；3）W是该链的唯一稳态分布，即如果有而且，则，这意味着。稳态分布存在性定理二：设P为某一马尔可夫链的状态转移矩阵，则该链稳态分布存在的充要条件是存在一个正整数N，使矩阵中的所有元素均大于零。实质上，该定理所给定的条件等价于存在一个状态和正整数N，使得从任意初始状态出发，经过N步转移之后，一定可以到达状态。同时，从该定义可以推论出，如果P中没有零元素，即任一状态经一步转移之后便可以到达其他状态，即稳态分布存在。例题：设有一马尔可夫链，其状态转移矩阵为验证它是否有稳态分布？若有，其稳态分布是什么？解：计算矩阵，*表示非零元素。故这个马尔可夫链是遍历的，其稳态分布存在。由稳态定理一，有WP=W，其中，即可得稳态分布：第6次课5.2马尔可夫信源有记忆信源在任一时刻发出符号的概率通常仅与前面的若干个符号有关，与更前面的符号无关，因此我们可以认为信源在某一时刻发出的符号与信源的状态有关。设信源状态空间为，在每一状态下信源可能输出的符号，每一时刻，当信源发出一个符号后，信源所处的状态将发生变化，并转入一个新的状态。信源输出的随机符号序列为，信源所处的状态序列为，。n 马尔可夫信源定义若信源输出的符号序列和状态序列满足下述条件则称此信源为马尔可夫信源：1、 某一时刻l信源的输出仅与信源的当前状态有关，即其中，。2、信源的状态只由当前的输出符号和前一时刻信源状态唯一确定，即n 马尔可夫信源状态的一步转移概率马尔可夫信源输出的符号序列完全由信源所处的状态决定。所以，可将信源的输出符号系列变换成状态系列，将信源输出符号的不确定性问题变成信源状态的转换问题，即，信源在l-1时刻的状态，当它发出一个符号后，所处的状态变成l时刻的状态，这种状态间的变化可用一步转移概率描述：，其中n 马尔可夫链状态转移图的例题1、例题1一个二进制一阶马尔可夫信源，信源符号集为A=0,1，条件概率为p(0|0)=0.25, p(0|1)=0.5, p(1|0)=0.75, p(1|1)=0.5, q=2, m=1,所以。由条件概率求得信源状态转移概率为：2、例题2设有一个二进制二阶马尔可夫信源，信源符号集为0,1，条件概率为p(0|00)=p(1|11)=0.8p(1|00)=p(0|11)=0.2p(0|01)=p(0|10)=p(1|01)=p(1|10)=0.5解：该信源符号数是q=2，共有个状态：，由已知条件容易求得各状态转移概率：二阶马尔可夫信源状态转移图：状态转移矩阵：3、例题3设一信源，它在开始时以P(a)=0.6, P(b)=0.3. P(c)=0.1的概率发出。如果为a，则为a,b,c的概率为；如果为b，则为a,b,c的概率为；如果为c，则为a,b的概率为为c的概率为0。其后发出的概率只与有关，且，请画出状态转移图。由题意知，信源在开始发出信号后，后面发出什么符号只与前一个所发符号有关，即且由此可见该信源是一阶马尔可夫信源，状态空间就等于信源符号集E=a,b,c，其状态转移图：一步转移矩阵为。n M阶马尔可夫信源的极限熵。当时间足够长时，遍历的m阶马尔可夫信源可以视为平稳信源，又因为信源发出的符号只与最近的m个符号有关，所以由极限熵定理：任意离散平稳信源，若。m阶马尔可夫信源的极限熵为：即m阶马尔可夫信源的极限熵等于m阶条件熵。齐次、遍历的马尔可夫链，其状态由唯一确定，因此该式两端同取对数，并对取统计平均，然后取负，得故马尔可夫信源的极限熵。其中是马尔可夫链的平稳分布，熵函数表示信源处于某一状态时发出一个消息符号的平均不确定度。例题：计算此马尔可夫信源熵信源的转移矩阵为：解：设稳态分布，由方程WP=W及条件，可解得。从而求得信源熵：小结：讨论了具有平稳性和遍历性的马尔可夫信源，了解了马尔可夫信源极限熵的存在条件：信源的状态极限概率存在；给出了马尔可夫信源极限熵