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

南京工程学院备课笔记-信息论与编码-绪论、信源与信息熵

第1次课 第一章 绪论

简单介绍本课程

1. 教学重点和计划

1) 信源及信源熵：约8学时

2) 无失真信源及无失真信源编码：约8学时 3) 限失真信源及限失真信源编码：约8学时 4) 信道及信道容量、信道编码：约12学时 5) 密码学：约8学时参考书

1）信息论及信息处理，吴伟陵，人民邮电出版社

2）信息论—基础理论与应用，傅祖芸编著，电子工业出版社，2001 3）信息理论与编码，姜丹，钱玉美编著

4）信息论基础教程，李亦农编著，北京邮电大学出版社，2005

§1 信息的概念

信息这一概念是在人类社会互通情报的实践过程中产生的。信息在发展过程中主要经历了五次大的革命：

1、声音、手势及语言； 2、文字符号进入人类社会；

3、印刷术提供了新的信息活动手段：增大了信息的传播范围； 4、电磁波开始传播信息：加快了传播速度； 5、计算机与通信的完美结合。

推动信息革命和信息技术发展的三项技术：

? 微电子技术—信息技术的“细胞” ? 通信技术—信息技术的神经 ? 计算机技术—信息技术的大脑

信息科学是一门综合性学科，它是研究信息及其运动规律的科学。其内容包括：信息的本质及其度量，信息的产生、获取、传播、处理和施效的规律。研究的目的是扩展人类获取和利用信息的能力。

信息技术是运用信息科学的研究成果来解决生产实际问题，包括：

? 感测技术（信息获取） ? 通信技术（信息传输） ? 计算机技术（信息处理） ? 自动控制技术（信息施效）

信息产业是专门从事信息生产、传播、出售和服务的产业，包括：信息技术设备制造、信息服务等。

? 信息的定义

我国学者钟义信教授对信息的定义为：信息就是在事物运动的状态和方式，就是关于事物运动的千差万别的状态和方式的认识。

信息是事物的状态和状态变化的方式。 1、 信息是无形的 2、 信息是可共享的 3、 信息是可扩充的 4、 信息是可以度量的

分析通信过程，通信的目的不外有两种情形：一是自己有某种形式的信息要告诉对方，同时估

第1页

南京工程学院备课笔记-信息论与编码-绪论、信源与信息熵

计对方既会对这种信息感到兴趣，而又尚不知道这个信息。也就是说，对方在关于这个信息的知识上存在着不确定性；另一种情况是，自己有某种疑问要向对方询问，而且估计对方能够解答自己的疑问。在前一种情况下，如果估计对方已经了解所欲告之的消息，就没有必要通信了；在后一种情况，如果自己没有疑问，当然就不必询问了。

这里所谓“疑问”、“不知道”，就是一种知识上的“不确定性”，即对某个事情的若干种可能结果，或对某个问题的若干可能答案，不能做出明确的判断。

因此可以把作为“通信的消息”来理解的“狭义信息”，看作(或明确定义)为一种用来消除通信对方知识上的“不确定性”的东西。引伸出一个十分重要而关键的结论：接收者收到某一消息后所获得的信息，可以用接收者在通信前后“不确定性”的消除量来度量。简而言之，接收者所得到的信息量，在数量上等于通信前后“不确定性”的消除量(或减少量)。这就是信息理论中度量信息的基本观点。

那么，很自然地接着要问这样一个问题：这就是，“不确定性”本身是否可度量？是否可用数学方法来表示呢？而不确定性是与“多种结果的可能性”相联系的，在数学上这些“可能性”正是以概率来度量的。概率大，即“可能性”大；概率小，“可能性”小。显然“可能性”大，即意味“不确定性”小；“可能性”小，即意味“不确定性”大。可见，“不确定性”与概率的大小存在着一定的联系，“不确定性”应该是概率的某一函数；那么，“不确定性”的消除量(减少量)，也就是狭义信息量，也一定可由概率的某一函数表示。这样就完全解决了作为“通信的消息”来理解的“狭义信息”的度量问题。

这个问题先放在这，我们到底用什么样的数学公式来度量信息，这个公式是否是唯一的？以及如何度量？这是我们下一步要解决的疑问。

§2 信息论的研究对象、目的和内容

信息论的奠基人——香农

“通信的基本问题就是在一点重新准确地或近似地再现另一点所选择的消息”。

这是数学家香农（Claude E.Shanon）在他的惊世之著《通信的数学理论》中的一句铭言。正是沿着这一思路他应用数理统计的方法来研究通信系统，从而创立了影响深远的信息论。

香农，1816年生于美国密执安州的加洛德。在大学中他就表现出了对数理问题的高度敏感。他的硕士论文就是关于布尔代数在逻辑开关理论中的应用。后来他就职于贝尔电话研究所。在这个世界上最大的通信公司（美国电话电报公司）的研究基地里，他受着前辈的工作的启示，其中最具代表性的是《贝尔系统技术杂志》上所披露的奈奎斯特的《影响电报速率的一些因素》和哈特莱的《信息的传输》。正是他们最早研究了通信系统的信息传输能力，第一次提出了信息量的概念，并试图用教学公式予以描述。

香农则创造性地继承了他们的事业，在信息论的领域中钻研了8年之久，终于在1948年也在《贝尔系统技术杂志》上发表了244页的长篇论著，这就是上面提到的那篇《通信的数学理论》。次年，他又在同一杂志上发表了另一篇名著《噪声下的通信》。在这两篇文章中，他解决了过去许多悬而未决的问题：经典地阐明了通信的基本问题，提出了通信系统的模型，给出了信息量的数学表达式，解决了信道容量、信源统计特性、信源编码、信道编码等有关精确地传送通信符号的基本技术问题。两篇文章成了现在信息论的寞基著作。而香农，也一鸣惊人，成了这门新兴学科的奠基人。那时，他才不过刚刚三十出头。

那么信息论的研究对象、目的和内容具体是什么呢？ 信息论的研究对象、目的和内容

信息论或称为通信的数学理论，是应用近代数理统计方法研究信息的度量、传输、存储、交换与处理的一门科学。它是通信理论中的基础理论。信息论研究的主要问题是在通信系统设计中如何实现信息传输、存储和处理的有效性和可靠性。 传输系统的模型

主要几个部分：

? 信源编码、信源译码解决了信息传输的有效性。

第2页

南京工程学院备课笔记-信息论与编码-绪论、信源与信息熵

? 信道编码、信道译码解决了信息传输的可靠性。

? 加密编码、解密译码限制了信息传输的共享，增加了保密性。

信息传输系统的要求

? 可靠性：可靠性高，就是要使信源发出的消息经过信道传输以后，尽可能准确地、不失真

地再现在接收端。如何来提高可靠性呢？

? 有效性：有效性高，就是用尽可能短的时间和尽可能少的设备来传送一定数量的信息。如

何提高有效性呢？

? 保密性：保密性高，就是隐蔽和保护通信系统中传送的消息，使它只能被授权接收者获取，

而不能被未授权者接收和理解。如何获取保密性？

? 认证性：是指接收者能正确判断所接收消息的正确性，验证消息的完整性，而不是伪造的

和被篡改的。

信源和信宿

信源：产生消息的源。消息可以是文字、语言、图像等。它可以是离散序列，也可以是连续形式，但都是随机发生的，即在未收到这些消息之前不可能确切地知道它们的内容。这些消息可以用随机变量或随机过程来描述。信源研究的主要内容是消息的统计特性和信源产生信息的速率。

信宿：消息传送过程中的接收者，即接收消息的人或物。信宿和信源可处于不同的地点或存在于不同时刻。例如：远古时代的文字。 信道

信道：把载荷消息的信号从发射端传到接收端的媒质或通道，是包括收发设备在内的物理设施。在狭义的通信系统中，实际信道有架空明线、电缆、波导、光纤、无线电波传播空间等。对广义的通信系统来说，信道还可以是其他传输媒介。

信道中存在干扰源。实际干扰可以分成以下两大类：

1、加性干扰。由外界引入的随机干扰，如天电干扰以及设备内部噪声，它们与信道的输入信号统计无关。信道的输出是输入信号和干扰的和。

2、乘性干扰。信号在传播过程中由于物理条件的变化引起信号参量的随机变化而构成的干扰。此时信道的输出信号是输入信号与某些随机参量相乘的结果。

研究信道的中心课题是它的统计特性和传输能力。 编码部分

编码部分：将信源发出的消息变换成适于信道传送的信号的设备。在此回答前面的三个问题：1、信源编码器：在一定的准则下，对信源输出的消息进行适当的变换和处理，其目的在于提高信息传输的效率。2、纠错编码器：对信源编码器的输出进行变换，用以提高对于信道抗干扰能力，亦即提高信息传输的可靠性。3、调制器。调制器是将纠错编码器的输出变成适合于信道要求的信号形式。是通信系统要研究的主要内容，通信原理研究的内容。 译码部分

译码：编码的逆变换。它要从受干扰的信号中最大限度地提取出有关信源输出消息的信息，并尽可能地复现信源的输出。译码器可分为：信源译码器和信道译码器。信道译码器又包括：纠错译码器和解调器。

译码部分的输出送给信宿，完成通信过程。 §2.3 信息论的内容

? 狭义信息论（香农基本理论）

在信息可以度量的基础上，对如何有效、可靠地传递信息进行研究的科学，涉及信息度量、信息特性、信息传输速率、信道容量、干扰对信息传输的影响等。

第3页

南京工程学院备课笔记-信息论与编码-绪论、信源与信息熵

香农信息论 压缩理论 传输理论 保密理论 无噪声 有噪声 保密系统的信息论 信道编码定理 有失真信源编码 无失真信源编码 网络信道 等长编码定理 变长编码定理 网络信息理论 最优码构成 压缩编码 码构成 网络最佳码 保密码 算术码 LZ码 MH码 纠错码 代数编码 卷积码 ? 一般信息论（通信理论）

主要研究信息传输和处理问题。除香农理论外，还包括噪声理论、信号滤波和预测、统计检测和估计理论、调制理论、抗干扰理论、信号处理理论以及保密理论。 ? 广义信息论（信息科学）

不仅包含上述内容，还包括所有与信息有关的自然和社会领域，具有更广泛的研究内容。 §2.4 信息论的形成与发展

1924年奈奎斯特解释了信号带宽和信息率（传递信息的速率）之间的关系：如果以一个确定的速率来传输电报信号，就需要一定的带宽。将信息率和带宽联系起来了。1928年哈特莱引入了非统计（等概率事件）信息量概念。提出信息量等于可能消息数的对数。1936年达得利提出在传输过程中增大带宽可以增强抑制干扰的能力。根据这一思想，提出了宽频移的频率调制方法。

20世纪40年代初期，由于军事上的需要，维纳在研究防空火炮的控制问题时，提出了《平稳时间序列的外推、内插与平滑及其工程应用》的论文。他把随机过程和数理统计的观点引入通信和控制系统中来，揭示了信息传输和处理过程的统计本质。这种统计观点的引入使得信息论产生质的飞跃。他还利用早在20世纪30年代初他本人提出的“广义谐波分析理论”对信息系统中随机过程进行谱分析。这就使通信系统的理论研究引起了质的飞跃，取得了突破性进展。

1948年香农在贝尔系统技术杂志上发表了两篇有关“通信的数学理论”的文章。在这两篇论文中，他用概率测度和数理统计的方法，系统地讨论了通信的基本问题，得出了几个重要的而带有普遍意义的结论，并由此奠定了现代信息论的基础。

从20世纪50年代开始，信息论在学术界引起巨大的反响。1951年美国IRE成立了信息论组。

第4页

南京工程学院备课笔记-信息论与编码-绪论、信源与信息熵

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年代以后，人们从经典的香农单向通信的信息论推广到多用户信息理论。多用户信息理论成为当前信息论的中心研究课题之一。

第5页

南京工程学院备课笔记-信息论与编码-绪论、信源与信息熵

第2次课 第二章 信源与信息熵

§1 自信息量和平均自信息量

一个随机事件在事件发生前有不确定性，在事件发生时有惊讶度，在事件发生后有信息量。当一个概率很低的随机事件发生，我们就会感到非常惊讶，并得到很大的信息量。

从信息源获得信息的过程就是其不确定性缩减的过程。随机事件包含的信息与其不确定性紧密相关。上节课中讲过，在统计分析中，使用概率作为衡量不确定性的一种指标。可以推论出：随机事件包含信息的度量应是其概率的函数。

那么，随机事件所包含的信息量与其发生的概率有什么样的关系呢？

§1.1 自信息量

? 自信息量的定义

任意随机事件的自信息量定义为该事件发生概率的对数的负值。

I(xi)?log[1]??logp(xi) p(xi)自信息量的单位取决于对数选取的底。当对数的底取2时，比特（bit）；以e为底时，奈特（nat）；以10为底时，哈特（hart）。三者之间的转换关系如下：

1nat?log2e?1.433bit 1Har?tlog210?3.322bi t? 自信息量的性质

1、当p(xi)?1时，I(xi)?0 确定事件信息量为0

2、当p(xi)?0时，I(xi)?? 概率为0的事件带来极大的信息量 3、I(xi)非负，因为概率是0—1之间的随机数 4、I(xi)是p(xi)的单调递减函数

5、xi是一个随机量，I(xi)是xi的函数，也是一个随机变量，没有确定的值。 提问：能反映整个信源的不确定性吗？

不能，那么用什么量来反映呢？

§1.2 平均自信息量——熵

一个信源可以用一个概率空间来描述：?x1,x3,...,xi,...??X????? ??P(X)??p(x1),p(x2),...,p(xi),...?其中：X是信源的状态空间，为一个离散集，表示了随机事件的状态数；P(X)是随机事件各种可能状态的概率分布，且

?P(X)?1，即状态是完备的；各状态是独立的。通常记为?X,P(X)?。

? 平均自信息量——信息熵定义

集X上，随机变量I(Xi)的数学期望定义为平均自信息量：

第6页

南京工程学院备课笔记-信息论与编码-绪论、信源与信息熵

H(X)?E[I(xi)]?E[?logp(xi)]???p(xi)logp(xi)

i?1q集X的平均自信息量即X的信息熵，简称熵。数值上与平均不确定度相同，含义不同。平均不确定性的含义：集X的平均自信息量表示集X中事件出现的平均不确定性。

在观测之前，确定集X中出现一个事件平均所需的信息量； 在观测之后，集X中每出现一个事件平均给出的信息量。 举个例子说明熵的计算和物理含义。 ? 熵函数的性质

1、对称性：当概率矢量P?(p1,p2,...,pq)中的各分量的次序任意变更时，熵值不变。该性质说明信源的熵仅与信源总体的统计特性有关。

2、 非负性：H(X)?H[p(x1),p(x2),...,p(xn)]???p(x)logp(x)?0

iii?1n等号成立的充要条件是当且仅当对某i,pi?1，其余的pk?0(k?i)。即确知信源的信源熵等于零。（非负性对于离散信源的熵是正确的，但是对于连续信源来说，其性质不存在。）此时即为熵的确定性：H(1,0)?H(1,0,0)?H(1,0,0,0)?...?H(1,0,...,0)?0

3、扩展性：limHq?1(p1,p2,...,pq??,?)?Hp1,p2,...,pq

??0??含义：若集合X有q个事件，另一个集合X’有q+1个事件，但X和X’集的差别只是多了一个概率接近于零的事件，则两个集的熵值一样。换言之，一个事件的概率与其中其它事件的概率相比很小时，它对集合的熵值的贡献可以忽略不计。

4、可加性

如果有两个随机变量X、Y，它们不是相互独立的，则二维随机变量（X,Y）的熵等于X的无条件熵加上当X已给定时Y的条件概率定义的熵的统计平均值，即

Hmn(p1p11,p1p21,...,p1pm1;p2p22,...,p2pm2;...;pnp1n,pnp2n,...,pnpmn)?HN(p1,p2,...,pn)??piHmi(p1i,p2i,...,pmi)i?1n

其中：pij为已知xi条件下，yj的条件概率；

?pi?1ni。 ?1,pi?0;（对一切i）

当二维随机变量X，Y相互统计独立时，则有：

Hmn(?)?Hn(p1,p2,...,pn)?Hm(q1,q2,...,qm)

5、极值性

111H(p1,p2,...,pn)?H(,,...,)?logn，其中n是集合X的元素数目。在离散情况下，集

nnn合X中的各事件等概率发生时，熵达到极大值。这个重要结论称为最大熵定理。集合中元素的数目

n越多，其熵值就越大。对数函数的单调上升性。

6、上凸性

第7页

南京工程学院备课笔记-信息论与编码-绪论、信源与信息熵

H(p1,p2,...,pq)是概率分布(p1,p2,...,pq)的严格上凸函数。

凸函数定义为：设f(X)?f(x1,x2,...,xi,...xn)为一多元函数。若对仪任意一个小于1的正数?(0???1)以及函数f(X)定义域内的任意两个矢量X1、X2有

f??X1?(1??)X2???f(X1)?(1??)f(X2)

则称f(X)为定义域上的上凸函数。如是大于，则为严格上凸函数。 反之若有f??X1?(1??)X2???f(X1)?(1??)f(X2)

则称f(X)为定义域上的下凸函数（Cup型函数）。如是小于，则为严格下凸函数。

§2 联合自信息量和联合熵

? 联合自信息量

二维联合集XY上的元素(xiyj)的联合自信息量定义为：I(xiyj)??logp(xiyj)。式中（联合随机事件），p(xiyj)为元素(xiyj)的二维联合概率。当X和Y相互独立时，(xiyj)为积事件

I(xiyj)??logp(xiyj)??log[p(xi)p(yj)]?I(xi)?I(yj)。即两个随机事件相互独立时，同时

发生得到的自信息量，等于这两个随机事件各自独立发生得到的自信息量之和。 ? 联合熵（共熵）

联合集XY上，每对元素的自信息量的概率加权平均值定义为联合熵。

H(X,Y)??p(xiyj)I(xiyj)

XY将积事件xiyj作为一个随机事件求其平均不确定性。根据联合自信息量的定义，联合熵又可定义为：H(X,Y)???p(xyiXYj)logp(xiyj)。

§3 条件自信息量和条件熵

? 条件自信息量

定义：在联合集XY中，对事件xi和yj，事件xi在事件yj发生的条件下的条件自信息量定义为：I(xi|yj)??logp(xi|yj)。p(xi|yj)是条件概率，即事件xi在事件yj发生的情况下的概率。由于每个随机事件的条件概率都处于0~1范围内，所以条件自信息量均为非负值。

几种自信息量之间的关系：

1、自信息量、联合自信息量、条件自信息量都满足非负性和单调递减性。

2、三者都是随机变量，其值随着变量xi和yj的变化而变化。 3、三者之间有如下关系式：

I(xiyj)??logp(xi)p(yj|xi)?I(xi)?I(yj|xi)

第8页

南京工程学院备课笔记-信息论与编码-绪论、信源与信息熵

I(yjxi)??logp(yj)p(xi|yj)?I(yj)?I(xi|yj)

? 条件熵

联合集XY上，条件自信息量I(x|y)的概率加权平均值定义为条件熵。其定义式为：

H(Y|X)??p(xy)I(y|x)：联合集XY中，集Y相对于集X的条件熵。还可写成

XYH(Y|X)??p(xy)log(y|x)。

XY提问：为什么在求和中要用联合概率进行加权平均？

H(Y|X?xi)???p(yj|xi)log(yj|xi)表示前面一个消息符号给定时，X?xi，信源输

j?1m出下一个消息符号的平均不确定性。由于给定不同的xi，H(Y|X?xi)是变动的，因此，

H(Y|X?xi)是一个随机变量。故应求出H(Y|X?xi)的统计平均值：

H(Y|X)???p(xi)H(Y|X?xi)????p(xi)p(yj|xi)log(yj|xi)

i?1i?1j?1nnm小结

自信息量?---->平均自信息量 联合自信息量?---->联合熵 条件自信息量?---->条件熵

第9页

南京工程学院备课笔记-信息论与编码-绪论、信源与信息熵

第3次课 §4 互信息量和平均互信息

§4.1 互信息量 ? 定义

?X?信源发出的符号消息集X，Y表示信宿接收的符号消息集合，各自的概率空间为：??和

P(X)???Y??P(Y)?。当接收端收到集合Y 中的一个消息符号yj后，重新估计关于信源的各个消息xi发生的概??率就变成条件概率p(xi|yj)，即后验概率。

收信者收到一个消息后，所获得的信息量等于收到消息前后不确定程度的减少量。不确定程度减少的原因，是由于收到消息前后概率空间的概率分布改变所致。

当接收到yj后，重新估计xi的发生。收信者从不确定到比较确定或完全确定，依赖于所获得的信息量。可以直观地将它定义为：I（信息量）=不确定程度的减少量。

当接收者收到yj后，所获得的信息量为Ij?log11 ?logp(xi)p(xi|yj)收信者所获得的信息量随先验概率的增加而减少，随后验概率的增加而增加。

在通信前，将信道看成关闭，可以认为输入随机变量X和输出随机变量Y之间没有任何关联关系，即X、Y统计独立。根据概率的性质，输入端出现xi和输出端出现yj的概率

p(xiyj)?p(xi)p(yj)，有先验不确定度I'(xiyj)?log1。

p(xi)p(yj)在通信后，输入随机变量X和输出随机变量Y之间由信道的统计特性相联系。输入端出现xi和输出端出现yj的联合概率为p(xiyj)?p(xi)p(yj|xi)?p(yj)p(xi|yj)，则有后验不确定度

I''(xiyj)?log1。

p(xiyj)∴通信后流经信道的信息量等于通信前后不确定度的差，即yj带来关于xi的信息量：

I(xi;yj)?I'(xiyj)?I''(x)?log?logp(xiyj)p(xi)p(yj)?logp(xi|yj)p(xi)11?logp(xi)p(yj)p(xiyj)111?log?log?logp(xi)p(yj)p(xiyj)

I(xi;yj)?I(xi)?I(yj)?I(xiyj)，其中i?1,2,...,n;j?1,2,...,m。

第10页

南京工程学院备课笔记-信息论与编码-绪论、信源与信息熵

∴互信息量定义为自信息量减去条件自信息量的差。

I(xi;yj)??logp(xi)?logp(xi|yj)?I(xi)?I(xi|yj)

互信息量为两个不确定度之差，是不确定度被消除的部分，代表已经确定的东西。实际是从yj得到的关于xi的信息量。即等于先验的不确定性减去尚存在的不确定性。同样道理，可定义xi对yj的互信息量为：

I(yj;xi)?logp(yj|xi)p(yj)?I(yj)?I(yj|xi)(i?1,2,...,n,j?1,2,...,m)

? 互信息量的性质

1. 互易性：I(xi;yj)?I(yj;xi) 2. 互信息量可为零

当事件xi、yj统计独立时，互信息量为零：I(xi;yj)?0。这表示不能从观测yj获得关于另一个事件xi的任何信息。反之亦然。

3. 互信息量可正可负

当后验概率p(xi|yj)大于先验概率p(xi)时，互信息量I(xi;yj)大于零，为正值。互信息量为正，意味着事件yj的出现有助于肯定事件xi的出现；

当后验概率p(xi|yj)小于先验概率p(xi)时，互信息量I(xi;yj)小于零，为负值。互信息量为负是不利的，原因是由于信道干扰使估计变得更加困难，即不确定性增加了。

4. 任何两个事件之间的互信息量小于其中任一事件的自信息量

I(xi;yj)?log11?I(yj) ?I(xi)；I(yj|xi)?logp(xi)p(yj)这说明自信息量I(xi)是为了确定事件xi的出现所必须提供的信息量，也是任何其它事件所能提供的关于事件xi的最大信息量。 §4.2

平均互信息量

? 定义

在联合集XY上，由yj提供的关于集X的平均条件互信息量等于由yj所提供的互信息量

I(xi;yj)在整个X中以p(xi|yj)后验概率加权的平均值，其定义式为

I(X;yj)def?p(xi|yj)I(xi;yj)??p(xi|yj)logXXp(xi|yj)p(xi)

第11页

南京工程学院备课笔记-信息论与编码-绪论、信源与信息熵

定理：联合集XY上的平均条件互信息量有I(X;yj)?0，等号成立当且仅当X集中的各个xi都与事件yj相互独立。

平均条件互信息量表示观测到yj后获得的关于集X的平均信息量。

I(X;yj)仍然是一个随机变量，随yj的变化而变化，因此，不能作为信道中流通信息量的整

体测度。

? 平均互信息量的性质

1. 非负性：I(X;Y)?0，当且仅当X与Y相互独立时，等号成立。即如果X与Y相互独立，

它们之间相互不能提供任何信息。 2. 互易性（对称性）：I(X;Y)?I(Y;X)

从集Y中获得关于X的信息量等于从集X中获得关于Y的信息量。集X和集Y统计独立时，有I(X;Y)?I(Y;X)?0，它意味着不能从一个集获得关于另一个集的任何信息。

3. 平均互信息和各类熵的关系

I(X;Y)?H(X)?H(X|Y) I(X;Y)?H(Y)?H(Y|X)

I(X;Y)?H(X)?H(Y)?H(XY)集X和

Y统计独立时，I(X;Y)?0，得到

I(X;Y)max?H(X)?H(Y)。

? 平均互信息量的物理含义

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的剩余不确定性，即信道损失。

根据互信息量I(X;Y)与条件熵H(X|Y)的关系可看出，I(X;Y)等于输入平均信息量H(X)减去信道损失，它反映了信道传输信息的能力。最大平均互信息量就是信道容量。

噪声熵H（Y/X）、散布度：

互信息量可以看作在有扰离散信道上传递消息时，唯一地确定接受符号y所需要的平均信息量H(Y)，减去当信源消息已知时确定接受符号y仍然需要的平均信息量H(Y/X)，因此，H(Y/X)可认为是唯一地确定信道噪声所需要的平均信息量。

第12页

南京工程学院备课笔记-信息论与编码-绪论、信源与信息熵

两种特殊情况： 1）p(xi/yj)?1

此时I(xi;yj)?I(xi)，这表明，当后验概率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/yj)?p(xi)

这时，由于后验概率p(xi/yj)等于先验概率p(xi)，所以后验概率与先验概率的比值等于1，即有I(xi;yj)?0。

这表明，当后验概率p(xi/yj)等于先验概率p(xi)时，收到yj后对信源发xi的不定度等于收到yj前对信源发xi的不定度，收到yj后并没有减少对信源发xi的不定度，从yj中获取不到关于xi的信息量。

4. 极值性：I(X;Y)?H(X);I(X;Y)?H(Y) 5. 凸函数性

上凸性：p(yj|xi)给定时，I(X;Y)是信源概率分布p(xi)的上凸函数。 引出后面章节中信道容量的定义：C?maxI(X;Y)

p(xi)下凸性：p(xi)给定时，I(X;Y)是信道传递概率分布p(yj|xi)的下凸函数。 引出后面章节中率失真函数的定义：R(D)?minI(X;Y)

P(yj/xi)§5 数据处理中信息的变化

? 三维联合集（X，Y，Z）上的平均互信息量

在联合集XYZ中，在给定zk的条件下，xi与yj之间的互信息量定义为条件互信息量。其定义为：I(xi;yj|zk)?logp(xi|yjzk)p(xi|zk)

联合集XYZ上还存在xi与yjzk之间的互信息量，其定义式为：

I(xi;yjzk)?logp(xi|yjzk)p(xi)

可进一步表示为：

第13页

南京工程学院备课笔记-信息论与编码-绪论、信源与信息熵

I(xi;yjzk)?log[?logp(xi|yj)p(xi)p(xi|yjzk)p(xi|yj)?]p(xi)p(xi|yj)p(xi|yjzk)p(xi|yj)?I(xi;yj)?I(xi;zk|yj)

?log上式表明，一切事件yjzk出现后所提供的有关xi的信息量I(xi;yjzk)等于事件yj出现后所提供的有关xi的信息量I(xi;yj)加上在给定事件yj的条件下再出现事件zk所提供的有关xi的信息量。

三维联合集（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) ? 数据处理中信息的变化 X 第一级处理 Y Z 第二级处理

由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 各种熵的性质

? 各种熵的关系

1、联合熵与信息熵、条件熵的关系

H(X,Y)?H(X)?H(Y|X)?H(Y)?H(X|Y)H(X)?H(X|Y)?H(Y)?H(Y|X)H(X1,X2,...,XN)?H(X1)?H(X2|X1)?...?H(XN|X1X2...XN)2、联合熵与信息熵的关系

H(X,Y)?H(X)?H(Y)

H(X1,X2,...,XN)?H(X1)?H(X2)?...?H(XN)3、条件熵与通信熵的关系：H(Y|X)?H(Y) 例：求联合集X，Y上的各种熵

第14页

南京工程学院备课笔记-信息论与编码-绪论、信源与信息熵

设一系统的输入符号集X?(x1,x2,x3,x4,x5)，输出符号集Y?(y1,y2,y3,y4)，如图所示。 解：首先求先验概率、后验概率

p(x1)?0.25 p(y1)?0.25?0.10?0.35，

p(x2)?0.10?0.30?0.40 p(y2)?0.30?0.05?0.35，

p(x3)?0.05?0.10?0.15 p(y3)?0.10?0.05?0.05?0.2， p(x4)?0.05?0.10?0.15 p(y4)?0.10，p(x5)?0.05

p(x1|y1)?p(x1y1)0.255p(y1x1)0.25??，p(y1|x1)???1

p(y1)0.357p(x1)0.25p(x2y2)0.3060.303? ??，p(y2|x2)?0.404p(y2)0.357p(x2|y2)?p(x3|y3)?0.1010.1020.10?，p(y3|x3)??，p(x4|y4)??1 0.2020.1530.100.1020.1020.101p(y4|x4)??，p(x2|y1)??，p(y1|x2)??

0.1530.3570.4040.0510.0510.051p(x3|y2)??，p(y2|x3)??，p(x4|y3)??

0.3570.1530.2040.0510.0510.05p(y3|x4)??，p(x5|y3)??，p(y3|x5)??1

0.1530.2040.05然后计算联合熵和信息熵

H(X,Y)????p(xkyj)log(p(xkyj)XY??0.25log0.25?0.10log0.10?0.30log0.30?0.05log0.05

?0.10log0.10?0.05log0.05?0.10log0.10?0.05log0.05?2.665H(X)????p(xkyj)log(p(xk)XY??0.25log0.25?0.10log0.40?0.30log0.40?0.05log0.15

?0.10log0.15?0.05log0.15?0.10log0.15?0.05log0.05?2.066第15页

南京工程学院备课笔记-信息论与编码-绪论、信源与信息熵

P(Xi?x1)?P(Xj?x1)?p(x1)P(Xi?x2)?P(Xj?x2)?p(x2)...P(Xi?xn)?P(Xj?xn)?p(xn)

一维平稳信源无论在什么时刻均以?p(x1),p(x2),...,p(xn)?分布发出符号。一维平稳信源即前面讨论的无记忆信源。 二维平稳信源

对于一个一维平稳信源，如果联合概率分布P(XiXi?1)也与时间起点无关，即

P(XiXi?1)?P(XjXj?1)，其中i,j为任意整数，且i?j，则称为二维平稳信源。

二维平稳信源在任何时刻发出两个符号的概率完全相同。二维平稳信源的二维联合分布

p(x1x2)与时间起点无关。

N维平稳信源

P(Xi1?x1,Xi2?x2,...,XiN?xN)?P(Xj1?x1,Xj2?x2,...,XjN?xN)?p(x1x2...xN)

其中，i和j为任意整数，i?j,x1,x2,...,xN?A?(a1,a2,...,aq)，则称具有这样性质的信源为N维平稳信源。对于N维平稳信源，它在某个时刻发出什么样的符号只和它前面发出的k(k

? 离散平稳信源的定义

如各维联合概率分布均与时间起点无关，对两个不同的时刻i和j，有

P(Xi)?P(Xj)P(XiXi?1)?P(XjXj?1)...P(XiXi?1Xi?2...Xi?N)?P(XjXj?1Xj?2...Xj?N)

这种各维联合概率均与时间起点无关的完全平稳信源称为离散平稳信源。离散平稳信源一般是有记忆信源。发出的各个符号之间具有统计关联关系。 §4.2

离散平稳信源的熵

? 联合熵

以最简单的二维平稳信源为例，它是N长为2的有记忆平稳信源。信源X?X1X2，概率空间

?X??a1a1为????p(aa)P(X)???11aqaq?。

p(a1a2)...p(aqaq)??a1a2...由熵的定义得到联合熵：H(X)?H(X1X2)??? 条件熵

第21页

??p(aaii?1j?1qqj)logp(aiaj)

南京工程学院备课笔记-信息论与编码-绪论、信源与信息熵

当平稳信源输出一个符号X1?ai，那么对于信源的下一个输出符号X2?aj，存在一个平均不确定性H(X2|X1?ai)，显然该不确定性的大小因ai而异，对所有ai进行加权平均即可得当已知一个输出符号，信源输出下一个符号的总平均不确定性，即

H(X2|X1)??p(ai)H(X2|X1?ai)i?1q????p(ai)p(aj|ai)logp(aj|ai)????p(aiaj)logp(aj|ai)i?1j?1i?1j?1qqqq

? 平稳信源熵的性质

1、 熵的可加性

H(X1,X2)?H(X1)?H(X2|X1) 熵的强可加性。

2、 二维平稳信源与二次扩展信源的关系 当X1和X2取值于同一集合（概率空间时），

?H(X1)?H(X2)?H(X),H(X)?2H(X)?H(X2)

与离散无记忆信源的二次扩展信源情况相同。所以离散无记忆信源的二次扩展信源可看成是二维离散平稳信源的特例。二维离散平稳信源是离散无记忆信源的二次信源的推广。

3、二维平稳信源与二次扩展信源的熵

H(X1X2)?H(X1)?H(X1|X2)H(X1X2)?H(X1)?H(X2)

说明二维离散平稳有记忆信源的熵小于等于二维离散无记忆信源的熵。对于二维离散平稳无记忆信源X2?X1X2来说，X1是否发生对X2不产生任何影响。对于二维离散平稳有记忆信源，由

于X1和X2有统计依赖关系，X1的发生会提供X2的部分相关信息。 ? 二维离散平稳信源熵例题

设二维离散信源X?X1X2的原始信源X的信源模型为

x?X??1?P???1????4如表。

信源的熵为：H(X)??33x249x3?11?，X?X1X2中前后两个符号的条件概率?36??p(x)logii?132p(xi)?1.542(bit/fuhao)

H(X2|X1)????p(xi)p(xj|xi)log2p(xj|xi)?0.870(比特/符号)

i?1j?1第22页

南京工程学院备课笔记-信息论与编码-绪论、信源与信息熵

条件熵H(X2|X1)比信源熵（无条件熵）H(X)减少了0.672比特/符号，这正是符号之间的依赖性所造成的。

联合熵为H(X1X2)?H(X1)?H(X2|X1)?1.542?0.870?2.412(比特/符号) 信源X的每一个信源符号所提供的平均信息量为：

H2(X)?11H(X)?H(X1X2)?1.206(比特/符号) 22显然它小于信源X提供的平均信息量H(X)，也是由于符号间的统计相关性所引起的。 §4.3

极限熵

? 离散平稳信源序列熵的特点

1、H(XL/XL?1)是L的单调非增函数。

L?12、HL(X)?H(XL/X)

3、HL(X)是L的单调非增函数。

4、极限熵：当L??，H?(X)deflimHL(X)?limH(XL|X1,X2,...,XL?1)

N??N??极限熵的意义：

多符号离散平稳信源实际上就是信源在不断地发出符号，符号之间的统计关联关系也并不仅限于长度N，而是伸向无穷远。研究实际信源，必须器具出信源的极限熵H?。

提问：H?是否存在？

答：H?是存在的，且等于关联长度N趋于?时，条件熵的极限值。 如何求H?？

极限熵存在定理——对任意离散平稳信源，若H1(X)??则有：

N??limHN(X)?limH(XN|X1,X2,...,XN?1)

N??NHN(X)?H(XN)?H(X1,X2,...,XN?1)?H(XN|XN?1)?(N?1)HN?1(X)?H(XN|XNN?1)

根据平稳信源的平稳性和条件熵的性质，有

NHN(X)?H(X)??H(XN|XN?1)?NH(XN|XN?1)

Nn?1HN(X)?NH(XN|XN?1)?NHN(X)?(N?1)HN?1(X)?HN(X)

第23页

南京工程学院备课笔记-信息论与编码-绪论、信源与信息熵

则HN(X)?HN?1(X)。这表明HN(X)是N的非递增函数，因而是有界的，即

0?HN(X)?HN?1(X)?...?H1(X)??。可见平均符号熵HN(X)的极限是存在的。

? 极限熵的计算

通过极限熵的存在性定理，可证明H(XN|XN?1)的值在HN(X)和HN?j(X)之间。令

N??，有HN(X)?H?(X),HN?J(X)?H?(X)，所以

N??limHN(X)?limH(XN|XN?1)

N??这就是平稳有记忆信源极限熵的定义式，它规定了平稳离散有记忆信源输出符号序列中平均每个信源符号的熵值。

小结

实际信源往往比较复杂，在其定义上加入平稳性约束条件即为平稳信源，而平稳信源通常都是有记忆信源。

分析了二维平稳有记忆信源和平稳无记忆二次扩展信源的关系。

极限熵代表了一般离散平稳有记忆信源平均每发出一个符号所提供的信息量。 计算联合熵或极限熵很困难，需要测定信源的无穷阶联合概率和条件概率。 可用条件熵或平均符号熵作为极限熵的近似值。

第24页

南京工程学院备课笔记-信息论与编码-绪论、信源与信息熵

第5次课 §5 马尔可夫信源

§5.1

有限状态马尔可夫链

m阶马尔可夫信源的定义：当信源的记忆长度为m+1时，该时该发出的符号与前m个符号有关联性，而与更前面的符号无关。

p(x1,x2,?,xL)?p(xL/x1,x2,....xL?1)p(x1,x2,?xL?1)?p(xL/xL?m,...,xL?1)p(x1,x2,...,xL?1)?p(xL/xL?m,...,xL?1)p(xL?1/xL?m?1,...,xL?2)p(x1,x2,...,xL?2)?...? 马尔可夫链的定义

由于高阶马尔可夫信源需要引入矢量进行分析，现方法将矢量转化为状态变量。定义状态：

si?(xi1,xi2,?xim)xij?A??a1,?an?可知，将来时刻的状态与过去时刻的状态无关，仅与现在时刻的状态有关。即，已知系统的现在，那么系统的将来与过去无关。这种特性称为马尔可夫特性。 ? 转移概率

1、定义

为了知道系统状态的转化情况，引入转移概率

pij(m,n)?P?Sn?sj|Sm?si??P?sj|si?si,sj?S

它表示：已知在时刻m系统处于状态si的条件下，经(n-m)步后转移到状态sj的概率。转移概率的性质：

(1)pij(m,n)?0,i,j?S (2)

?p(m,n)?1,i?S

ijj?S2、 一步转移概率

当n-m=1时，pij(m,m?1)即为一步转移概率，记为pij(m),m?0。

pij(m)?P{Sm?1?j|Sm?i},i,j?S

一步转移概率性质：1)pij(m)?0,i,j?S；2) 3、k步转移概率

?p(m,n)?1

ijj?Spij(m)?P{Sm?k?j|Sm?i},i,j?S

它表示在时刻m时，Sm的状态为i的条件下，经过k步转移到达状态j的概率。 性质：1）pij(k)(k)(m)?0,i,j?S；2）?pij(m)?1,i,j?S

(k)j?S4、 k步转移矩阵

?中的任一个状态，因此，状态转移时，各种转系统在任一时刻可处于状态空间S??0,?1,?2,...移概率构成一个矩阵P?pij?(k)(m),i,j?S称为k步转移矩阵。

第25页

?

南京工程学院备课笔记-信息论与编码-绪论、信源与信息熵

pij(m)对应于矩阵P中的第i行j列之元素。pij(m)满足性质 1、2的矩阵P是一个随机

矩阵，它决定了系统X1,X2,...所取状态过程的概率法则。

一般地，在状态空间是S??0,?1,?2,...?是一可数无穷集合，所以转移矩阵P是一无穷行无穷列的随机矩阵。

? 时齐马尔可夫链

定义：若对于任意的i,j?S，马尔可夫链?Sm,m?T?的转移概率pij(m)与m无关，即

(k)(k)pij(m)?P?Sm?1?j|Sm?i??pij,i,j?S，则称这类马尔可夫链为时齐马尔可夫链，或齐次马尔

可夫链。它是具有平稳转移概率的马尔可夫链。

对于时齐马尔可夫链，一步转移概率pij具有性质： 1、pij2、

(k)?0,i,j?S

ij?pj?S?1,i,j?S

由一步转移概率pij可以写出其转移矩阵为：

?p11?pP?{pij,i,j?S}或P??21?p31??...p12p22p32...p13p23p33......?...?? ...??...?如果状态空间S??0,1,2,...,n?是有限的，则称它是有限状态的马尔可夫链。如果状态空间

S??0,?1,?2,...?是无穷集合，则称它是可数无穷状态的马尔可夫链。

切普曼-柯尔莫哥洛夫方程

对于具有m+r步转移概率的齐次马尔可夫链，存在下述切普曼-柯尔莫哥洛夫方程：

Pij(k)??pirprj(l)k?S(k?l),(i,j?S)

利用此方程就可以用一步转移概率表达多步转移概率。一般有：

Pij(k)??pirk?S(k?1)prj??pirprjk?S(k?1),(i,j?S)

对于齐次马尔可夫链，一步转移概率完全决定了k步转移概率。

值得指出的是，转移概率pij不包含初始分布，即第0次随机实验中Xo?Si的概率不能由转移概率pij表达。

? 具有遍历性的马尔可夫链

定义：若齐次马尔可夫链对一切i,j存在不依赖于i的极限：limpijn??(n)?pj且满足

第26页

南京工程学院备课笔记-信息论与编码-绪论、信源与信息熵

pj?0;pj??pij;?pj?1，则称其具有遍历性，pj称为平稳分布。

i?0j??遍历性的意义：

不论质点从哪个状态Si出发，当转移步数n充分大时，转移到状态Sj的概率pij某个常数pj。即如果转移步数n充分大，就可以用常数pj作为n步转移概率pij(n)(n)都近似等于

的近似值。

? 马尔可夫链的稳态分布

如果马尔可夫链具有遍历性，意味着马尔可夫信源在初始时刻可以处在任意状态，然后信源状态之间可以转移。由初始分布及各时刻的一步转移概率就可以完整描述马尔可夫链Xn,n?N?的统计特性。经过足够长时间之后，信源处于什么状态已与初始状态无关。这时，每种状态出现的概率已达到一种稳定分布，即平稳分布。

对于有限状态马尔可夫链，如果存在一个数集W1,W2,...,Wr，且满足

n????limpij(n)?Wj,i,j?1,2,...,r，则称该马尔可夫链的稳态分布存在。

对于一个有r个状态的马尔可夫链，若令：

Wj(n)?P?t?n时刻的状态为Sj??P?Xn?Sj?

(n)(n)(n)则可以写出t=n-1与t=n时刻的状态方程

Wj(n)?W1p1j?W2p2j?...?Wrprj,j?1,2,...,r

设W(n)?W1W2...Wr?(n)(n)(n)?，则上式可以表示成W(0)(n)?W(n?1)P

将上式递推运算后可得W分布矢量W(n)(n)?W(n?1)P?W(n?2)P2?...?W(0)Pn，这就是说，t=n时刻的状态

与转移矩阵P的n次幂的乘积。

是初始分布矢量W稳态分布存在性定理一：

设有一马尔可夫链，其状态转移矩阵为P?(pij),i,j?1,2,...,r，其稳态分布为Wj,j?1,2,...,r，则：

1）

?Wj?1rj?1;2）W?(W1,W2,...,Wr)是该链的稳态分布矢量，即WP=W；

(0)2）如果初始分布W?W，则对所有的n，W(n)?W；

3）W是该链的唯一稳态分布，即如果有

?????...??而且?12ri?0;??i?1，则

i?1r?P??，这意味着??W。

稳态分布存在性定理二：

第27页

南京工程学院备课笔记-信息论与编码-绪论、信源与信息熵

设P为某一马尔可夫链的状态转移矩阵，则该链稳态分布存在的充要条件是存在一个正整数N，使矩阵P中的所有元素均大于零。

实质上，该定理所给定的条件等价于存在一个状态Sj和正整数N，使得从任意初始状态出发，经过N步转移之后，一定可以到达状态Sj。

同时，从该定义可以推论出，如果P中没有零元素，即任一状态经一步转移之后便可以到达其他状态，即稳态分布存在。

N01??0??例题：设有一马尔可夫链，其状态转移矩阵为P?1/21/31/6验证它是否有稳态分布？????1/21/20??若有，其稳态分布是什么？

?00*??00*??**0???????2解：计算矩阵P?******?***

????????**0????**0????***???***??，*表示非零元素。故这个马尔可夫链是遍历的，其稳态分布存在。

P3??***????***??由稳态定理一，有WP=W，其中W??W1W2W3?，即

11111W1?W2?W3;W2?W2?W3;W3?W1?W2; 22326另有条件：W1?W2?W3?1可得稳态分布：W1?128;W2?;W3? 3721第28页

南京工程学院备课笔记-信息论与编码-绪论、信源与信息熵

第6次课 §5.2

马尔可夫信源

有记忆信源在任一时刻发出符号的概率通常仅与前面的若干个符号有关，与更前面的符号无关，因此我们可以认为信源在某一时刻发出的符号与信源的状态有关。

设信源状态空间为S?(S1,S2,...,SJ)，在每一状态下信源可能输出的符号

X?A(a1,a2,...,aq)，每一时刻，当信源发出一个符号后，信源所处的状态将发生变化，并转入一

个新的状态。

信源输出的随机符号序列为x1x2...xl...，xl?A?(a1a2...aq),l?1,2,...，信源所处的状态序列为

u1u2...ul...，ul?S?(S1,S2,...,SJ),l?1,2,...。

? 马尔可夫信源定义

若信源输出的符号序列和状态序列满足下述条件则称此信源为马尔可夫信源： 1、 某一时刻l信源的输出仅与信源的当前状态有关，即

p(xl?ak|ul?Sj,xl?1?ak1|ul?1?Si,...)?p(xl?ak|ul?Sj)

其中，ak、ak1?A;Si、Sj?S。

2、信源的状态只由当前的输出符号和前一时刻信源状态唯一确定，即

?1p(ul?Si|xl?ak,ul?1?Sj)??

?0? 马尔可夫信源状态的一步转移概率

马尔可夫信源输出的符号序列xl完全由信源所处的状态ul决定。所以，可将信源的输出符号系列变换成状态系列，将信源输出符号的不确定性问题变成信源状态的转换问题，即，信源在l-1时刻的状态Sj，当它发出一个符号后，所处的状态变成l时刻的状态Si，这种状态间的变化可用一步转移概率描述：

pji?P(ul?Si|ul?1?Sj)，其中Si,Sj?S?(S1,S2,...,SJ)

? 马尔可夫链状态转移图的例题

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,所以S1?0,S2?1。

由条件概率求得信源状态转移概率为：

p(S1|S1)?0.25,p(S1|S2)?0.5,p(S2|S1)?0.75,p(S2|S2)?0.5

2、例题2

设有一个二进制二阶马尔可夫信源，信源符号集为

第29页

南京工程学院备课笔记-信息论与编码-绪论、信源与信息熵

{0,1}，条件概率为

p(0|00)=p(1|11)=0.8 p(1|00)=p(0|11)=0.2

p(0|01)=p(0|10)=p(1|01)=p(1|10)=0.5

解：该信源符号数是q=2，共有qm?4个状态：

S1?00,S2?01,S3?10,S4?11，由已知条件容易求得各状态转移概率：

p(S1|S1)?p(S4|S4)?0.8p(S2|S1)?p(S3|S4)?0.2p(S3|S2)?p(S1|S3)?p(S4|S2)?p(S2|S3)?0.5二阶马尔可夫信源状态转移图：

状态转移矩阵：

0??0.80.20?0?00.50.5?? ?0.50.500???000.20.8??3、例题3

设一信源，它在开始时以P(a)=0.6, P(b)=0.3. P(c)=0.1的概率发出X1。 如果X1为a，则X2为a,b,c的概率为c，则X2为a,b的概率为

11；如果X1为b，则X2为a,b,c的概率为；如果X1为331为c的概率为0。其后发出Xi的概率只与Xi?1有关，且2P(Xi|Xi?1)?P(X2|X1),i?3，请画出状态转移图。

由题意知，信源在开始发出信号后，后面发出什么符号只与前一个所发符号有关，即

P(Xi|Xi?1)?P(X2|X1),i?3且

1 31P(X2?a|X1?b)?P(X2?b|X1?b)?P(X2?c|X1?b)?

31P(X2?a|X1?c)?P(X2?b|X1?c)?

2P(X2?a|X1?a)?P(X2?b|X1?a)?P(X2?c|X1?a)?P(X2?c|X1?c)?0

由此可见该信源是一阶马尔可夫信源，状态空间就等于信源符号集E={a,b,c}，其状态转移图：

第30页

本文来源：https://www.bwwdw.com/article/d2o7.html