信息论基本概念.ppt

3.离散有记忆信源马尔可夫信源,马尔可夫信源非平稳离散信源中的一类特殊信源。是由信源发出的各个符号之间的关连性构成一个整体消息。这种关连性用符号的转移概率（条件概率）表示：如：BOY P(B)P(O|B)P(Y|BO)若马尔可夫信源发出每个符号都取决于它与前面的K个符号之间的关连性，也就是该信源是以转移概率P(Xi|Xi-k,Xi-k+1,Xi-1)发出每个符号，这种信源称作K阶马尔可夫信源。,马尔可夫过程：对于任意的大于2的自然数n，在连续的时间T轴上有n个不同时刻，t1，t2，tn满足，在tn时刻的随机变量Xn与其前面（n1）个时刻的随机变量X1，X2，Xn1的关系可用它们之间的条件概率密度函数来表示，如果满足下式：p(Xn，tn|Xn 1，tn1，Xn2，tn2，X1，t1)p(Xn，tn|Xn 1，tn 1)则这种随机过程称为单纯马尔可夫过程（一阶马尔可夫过程）K阶马尔可夫过程的特征为：p(Xn，tn|Xn 1，tn1，Xn2，tn2，X1，t1)p(Xn，tn|Xn1，tn1，Xn2，tn2，Xnk，tnk),预备知识:马尔可夫过程、马尔可夫链,马尔可夫链：当马尔可夫过程的随机变量幅度和时间参数均取离散值时，就称作马尔可夫链。设随机过程在时间域上Tt1，t2，tk1，tk，tn1，tn的n个离散时刻上的状态Xk(k1，2，3，n)都是离散型的随机变量，并且有M个不同的取值S1,S2,SM，这M个取值便构成一个状态空间S，SS1,S2,SM.在n个时刻上的n个状态构成一个随机序列（X1，X2，Xk1，Xk，Xn1，Xn）,对于这个随机序列，若有：则此序列称为单纯马尔可夫链（一阶马尔可夫链）。一阶马尔可夫链在tn时刻的取值Xn Sin的概率仅与前一状态Xn-1有关，与其它时刻状态无关，它的记忆长度为两个时刻。若与它前面K个时刻tn-1，tn-2，tn-k有关，则为K阶马尔可夫链，它的记忆长度为（K+1）个时刻。设一阶马尔可夫链在时刻tk1随机序列的取值Xk1Si，而在下一时刻tk，随机序列的取值XkSj，则条件概率为:P(j|i)P(XkSj|Xk1Si)因为P(j|i)仅取决于状态Sj和Si，因此称P(j|i)为由状态Si向Sj的转移概率。,对于具有M个不同的状态空间，M2个转移概率可排成一转移矩阵：每行元素代表同一起始状态到M个不同终止状态的转移概率；每列元素代表M个不同起始状态到同一终止状态的转移概率；显然有：P(j|i)1（i=1,2,M）K阶马尔可夫链每个状态由K个符号组成。若信源符号有D种，则状态数目M为：MDK,马尔可夫链可以用香农线图表示。(a),(b),(c)分别表示信源含两种字母(D2)的一阶、二阶和三阶马尔可夫链的线图。(d),(e)分别表示D3和D4的一阶马尔可夫链的线图。,一、概述 一般情况下，信源输出符号之间的相关性可以追溯到最初的一个符号，而在许多信源的输出符号序列中，符号之间的依赖关系是有限的任何时刻信源符号发生的概率只与前面已经发出的若干个符号有关，而与更前面发出的符号无关。这类信源在输出符号时不仅与符号集有关，还与信源的状态有关。,状态转移图(香农线图),【注】E1、E2、E3是三种状态，箭头是指从一个状态转移到另一个状态，旁边的数字代表发出的某符号和条件概率p(ak/Ei)。这就是香农提出的马尔可夫状态转移图，也叫香农线图。,二、马尔可夫信源 若信源输出的符号和信源所处的状态满足以下两个条件，则称为马尔可夫信源：,【注】上述条件表明，若信源处于某一状态Ei，当它发出一个符号后，所处的状态就变了。状态的转移依赖于所发出的信源符号，因此任何时刻信源处在什么状态完全由前一时刻的状态和发出的符号决定。又因条件概率p(ak/Ei)已给定，所以状态之间的转移有一定的概率分布，并可求出状态的一步转移概率p(Ej/Ei)。,例：设某信源符号XA=a1,a2,a3，信源所处的状态SE=E1,E2,E3,E4,E5。各状态之间的转移情况如下图所示，请判断这是否是一个马尔可夫信源？,解：（1）信源在Ei状态下输出符号ak的条件概率p(ak/Ei)用矩阵表示为:,（2）该信源在l时刻所处的状态由当前的输出符号与前一时刻(l-1)信源的状态唯一决定:,此信源满足马尔可夫的两个条件，所以是马尔可夫信源，并且是齐次马尔可夫信源。,三、m阶马尔可夫信源 一般有记忆信源：发出的是有关联性的各符号构成的整体消息，即输出的是符号序列，并用符号间的联合概率描述这种关系。马尔可夫信源：用符号之间的转移概率（条件概率）来描述这种关联关系。即马尔可夫信源是以转移概率输出每个信源符号。,m阶马尔可夫信源 在某一时刻l，符号出现的概率仅与前面已出现的m个符号有关，可以把这前面m个符号序列看成信源在l时刻所处的状态。若每符号取值q种，则共有qm种状态，每种状态对应一个m长(q 进制)序列，这种状态序列符合马尔可夫链的性质，可用马氏链来描述，这种信源称为m阶马尔可夫信源。数学模型：,【注】当m=1时，为一阶马尔可夫信源。,马尔可夫信源熵,设状态,信源处于状态,时，再发出下一个符号,此时，符号序列,就组成了新的信源状态,，这时信源所处的状态由,转移到,【注】可见求解马尔可夫信源条件熵关键是要得到,【注】上述定理说明，有限齐次、遍历马尔可夫链信源，在初始时刻可以处在任意时刻，然后状态之间可以转移，经过足够长时间之后，信源处于什么状态已与初始状态无关。状态极限概率方程组可写为：,例1 设有二元二阶马尔可夫信源：,【结论】信源达到稳定后，信源符号的概率分布与初始概率不同，因此一般马尔可夫信源并非是平稳信源。但当时齐、遍历的马尔可夫信源达到稳定后，就可看成一个稳定信源。计算信源的信息熵，对于平稳信源须知道信源的各维概率分布，而对于m阶马尔可夫信源，只要知道与前面m个符号有关的条件概率，因此一般信源可用m阶马尔可夫信源来近似。,例2：有一个马尔可夫信源，已知 试画出该信源的香农线图，并求出信源熵。解：该信源的香农线图为：在计算信源熵之前，先用转移概率求稳定状态下二个状态x1和 x2 的概率 和 可得：马尔可夫信源熵,例3：一阶马尔可夫信源的状态图如下，信源的符号集为0,1,2，并定义p+q=1。(1)求信源平稳后的状态极限概率分布;(2)求此信源的熵；(3)近似认为信源无记忆时，符号的概率分布等于平 稳分布。求近似信源的熵H(X)，并与H进行比较；(4)对一阶马尔可夫信源p取何值时H取最大值？又当p=0或p=1时结果如何？,例4：设有一信源，它在开始时以p(a)=0.6、p(b)=0.3、p(c)=0.1的概率发出符号X1，如果X1为a时，则X2为a、b、c的概率均为1/3；如果X1为b时，则X2为a、b、c的概率均为1/3；如果X1为c时，则X2为a、b的概率均为1/2，为c的概率为0。而且后面发出Xi的概率只与Xi-1有关。又p(Xi|Xi-1)=p(X2|X1)，i3。利用马尔可夫信源的图示画出状态转移图，并计算信源熵H。,马氏链的可约性,马氏链可约性:若对所有 k，都有k步转移概率p(k)ij=0，就意味着一旦出现 Si以后不可能到达Sj,也就是不能各态遍历，或者状态中应把Sj取消，这样就成为可约的了。k步转移概率：经过k个时刻后状态的转移概率。p(k)ij=p(sl+k=Ej|sl=Ei),马氏链不可约性:对任意一对i和j，都存在至少一个k使p(k)ij0，这就是说从Si开始，总有可能到达 Sj.,由状态S3转移到S1的转移概率p(k)31=0，因为一进人状态S3就一直继续下去，而不会再转移到其他状态。P(k)41=0也是明显的，因S4和S1之间没有连接箭头，因此这种链就是可约的。,小结 两种有记记忆信源比较,总结:各种离散信源的熵(1)发出单个符号消息的离散无记忆信源熵 若信源发出N个不同符号X1，X2，Xi，XN,代表N种不同的符号，各个符号的概率分别为 P1，P2，Pi，PN 因为这些符号相互独立，所以该信源熵为：H（X）PilogPi bit/符号(2)发出符号序列消息的离散无记忆信源熵 发出K重符号序列消息的离散无记忆信源熵为共熵H(XK)，它与单个符号消息信源熵H(X)有如下关系：H(XK)KH(X)K PilogPi bit/符号序列,(3)发出符号序列消息的离散有记忆信源熵 发出K重符号序列消息的离散有记忆信源熵也为共熵H(XK)当K2时 H(X2)H(X)H(X|X)H(X|X)H(X)H(X2)2H(X)推广到K重,(4)发出符号序列消息的马尔可夫信源熵 马尔可夫信源熵是条件熵 若从前一状态Ei转移到后一状态Ej有多种可能性，则信源由状态Ei发出一个符号的Hi为 Hi P(j|i)logP(j|i)再进一步对前一状态Ei的全部可能性作统计平均，就得马尔可夫信源熵 H 为 H P(i)Hi P(i)P(j|i)logP(j|i)bit/符号,4.各种离散信源的时间熵 信源的时间熵在单位时间内信源发出的平均信息量，单位 为s(秒)或其他特定的时间单位 发出单个符号消息的离散无记忆信源的时间熵 已知离散无记忆信源各符号的概率空间 由于发出各符号所占有时间是不同的 可设符号X1的长度为b1，X2为b2，Xi为bi，XN为bN 单位均为s(秒)则信源各符号的平均长度是各个的概率加权平均值，即,s/符号,则信源的时间熵 Ht为：若各符号时间长度相同，均为b(s)，则可直接得 又若信源每秒平均发出 n个符号，有 此时，信源熵 Ht为：,bit/s,符号/s,bit/s,发出符号序列消息的离散无记忆信源的时间熵 对K重符号序列的离散无记忆信源的信源熵为：H(XK)KH(X)bit/符号序列 K重符号序列消息的平均长度为信源各符号平均长度的K倍，即 这种信源的时间熵 Ht为：可见，它在数值上与上面一种信源的时间熵相同,s/符号序列,bit/s,若该信源每秒内平均发出n个K重符号序列消息，则有：此时 Ht为：发出符号序列消息的离散有记忆信源的时间熵 计算方法与发出符号序列无记忆信源的时间熵一致，但 H(XK)KH(X)同样若信源在每秒内平均发出n个K重符号序列消息，有,符号序列/s,bit/s,bit/s,符号序列/s,bit/s,5.信源的冗余度,信源熵 表示信源输出每一个符号所携带的信息量。,对于一个具体信源，它所具有的总信息量是一定的 信息熵越大（每个信源符号所承载的信息量越大）输出全部信源信息所需传送的符号就越少 通信效率越高 这是我们研究信息熵的目的,离散无记忆信源：信源符号间彼此无依赖、等概率分布，信源熵最大（最大熵定理）Hmax，携带信息的效率最高。离散有记忆信源：信源输出符号间彼此依赖、相关，信源熵减小（条件熵无条件熵），输出符号间相关长度越长，信源熵越小。所有有记忆信源、非等概率离散无记忆信源熵 Hmax,信源的冗余度R 1减去熵的相对率。,熵的相对率 信源的实际信息熵与具有同样符号集的最大熵的比值。,【注】信源符号间依赖关系越大，信源冗余度越大。信息论研究目的提高信息传输的有效性、可靠性、保密性。从提高信源输出有效性的观点出发，希望减少或去掉冗余度。,冗余度大的信源具有较强的抗干扰能力，当干扰使信息在传输过程中出现错误时，可从它的上下关联中纠正错误，因此从提高信息传输可靠性观点出发，总是希望增加信源冗余度。信源编码就是通过减少或消除信源冗余度来提高通信的传输效率，即提高通信的有效性。信道编码则是通过增加信源的冗余度来提高通信的抗干扰能力，即提高通信的可靠性。,连续信源的熵,对连续信源的分析，也可以类似于离散信源从单个连续消息（随机变量）开始，再推广至连续消息序列。对于单个连续随机变量可采用概率密度来描述：对连续随机序列可采用相应的序列概率密度来描述；而对于连续的随机过程一般也可以按照采样定理分解为连续随机序列来描述。,连续随机变量可以看作是离散随机变量的极限，故可采用离散随机变量来逼近。首先类比概率pi与概率密度p(x)：,（一）单个连续随机变量信源熵,令xa,b，且ab,现将它均匀的划分为n份，每份宽度为，则x处于第i个区间的概率为pi，则pi=(中值定理)即当p(x)为x的连续函数时，由中值定理，必存在一个xi值，使上式成立。再按照离散信源的信息熵的定义有：,于是我们定义前一项取有限值的项为连续信源的信息熵，并记为Hc(X).也叫相对熵,即：Hc(X)=也可记为：Hc(X)=其中R1 表示实轴。,(二)两个连续随机变量信源熵 联合熵条件熵,几种特殊连续信源的熵和最大熵定理,一、均匀分布信源：Hc(X)=log2(b-a)结论 熵值只与均匀分布间隔(b-a)有关，若 b-a 1，则Hc(X)为负,二、高斯分布信源 结论 熵值 只与方差有关，与m无关。,三、指数分布信源 m数学期望 结论 熵值只与数学期望m有关,四、最大熵定理1.限峰值功率的最大熵定理 均匀分布的连续信源具最大熵2.限平均功率的最大熵定理 高斯分布的连续信源具最大熵3.限均值的最大熵定理 指数分布的连续信源具最大熵结论 连续信源的最大熵因条件而异 离散信源的最大熵出现于等概之时,