信息论与编码马尔可夫信源.ppt

1、2.2.4 马尔可夫信源,(1) 马尔可夫信源的定义 (2) m阶马尔可夫信源 (3) 举例,(1) 马尔可夫信源的定义, 信源的状态和符号集 马尔可夫信源定义 举例, 信源的状态和符号集,有一类信源，输出的符号序列中符号之间的依赖关系是有限的，即任何时刻信源符号发生的概率只与前面已经发出的若干个符号有关，而与更前面发出的符号无关。 设符号集为X和状态为S。信源输出的信息符号还与信源所处的状态有关。 状态Se1,e2,ej 符号Xx1,x2, ,xn 每一时刻信源发出一个符号后，所处的状态将发生转移。 信源输出的随机符号序列为 X1,X2, ,Xl-1,Xl, 信源所处的随机状态序列为 S1,

2、S2, ,Sl-1,Sl, ,在第l 时刻，信源状态为ei时，输出符号xk的概率为 pl(xk /ei)=P(Xl=xk /Sl=ei) 在第l-1时刻，信源状态ei时，下一时刻转移到ej的状态转移概率为 pl(ej /ei)=P(Sl=ej /Sl-1=ei) 一步转移概率：状态转移概率 pl(ej /ei)=P(Sl=ej /Sl-1=ei) 称为马尔可夫链在时刻l 的状态一步转移概率。 时齐/齐次马尔可夫链：一般情况下，状态转移概率和已知状态下符号发生的概率均与时刻l 有关。若这些概率与时刻l 无关，即 pl(xk /ei)= p(xk /ei) pl(ej /ei)= p(ej /ei

3、) 则称为时齐的或齐次的。此时的信源状态服从时齐马尔可夫链。, 马尔可夫信源定义,马尔可夫信源：信源输出的符号和所处的状态满足下列两个条件。 某一时刻信源符号的输出只与此刻信源所处的状态有关，与以前的状态和以前的输出符号都无关。即 P(Xl=xk /Sl=ei , Xl-1=xk-1 , Sl-1=ej ,) =pl(xk /ei) 当具有时齐性时有 pl(xk /ei)= p(xk /ei) 信源某l时刻所处的状态由当前的输出符号和前一时刻(l-1)信源的状态惟一确定。即,结论： 若信源处于某一状态ei，当它发出一个符号后，所处的状态就变了； 任何时刻信源处在什么状态完全由前一时刻的状态和发

4、出的符号决定； 因为条件概率p(xk /ei)已给定，所以状态的转移满足一定的概率分布，并可求出状态的一步转移概率p(ej /ei)。 马尔可夫链的状态转移图：每个圆圈代表一种状态，状态之间的有向线代表某一状态向另一状态的转移。有向线一侧的符号和数字分别代表发出的符号和条件概率。, 举 例,例2.2.3 设信源符号 Xx1, x2, x3 ，信源所处的状态Se1, e2, e3, e4, e5 。各状态之间的转移情况由图2.2.1给出。,将图中信源在ei状态下发符号xk 的条件概率p(xk /ei)用矩阵表示 由矩阵看出： 由图中看出： 由图中可得状态的一步转移概率： 该信源满足马尔可夫信源定

5、义。,结论： 一般有记忆信源发出的是有关联性的各符号构成的整体消息，即发出的是符号序列，并用符号间的联合概率描述这种关联性； 马尔可夫信源的不同之处在于它用符号之间的转移概率/条件概率来描述这种关联关系。即马尔可夫信源是以转移概率发出每个信源符号； 转移概率的大小取决于它与前面符号之间的关联性。,(2) m阶马尔可夫信源, m阶马尔可夫信源 m阶马尔可夫信源的极限熵 有限齐次马尔可夫链各态历经定理 有关问题的说明, m阶马尔可夫信源,m阶有记忆离散信源的状态：对m阶有记忆离散信源，在任何时刻l，符号发出的概率只与前面m个符号有关，把这m个符号看作信源在l时刻的状态。 n信源符号集； nm信源不

6、同的状态数； m信源长度； 信源输出依赖长度为m+1的随机序列就转化为对应的状态序列，这种状态序列符合简单的马尔可夫链的性质。 m阶马尔可夫信源数学模型：m阶有记忆离散信源的数学模型可由一组信源符号集和一组条件概率确定：,一阶马尔可夫信源：当m=1时，任何时刻信源符号发生的概率只与前面一个符号有关。 m阶马尔可夫信源的条件概率（考虑其平稳性） 说明： 对m阶有记忆离散信源，它在任何时刻l，符号发出的概率只与前面m个符号有关，把这m个符号看作信源在l 时刻的状态。 原始信源符号集共有n个符号，则有记忆信源可以有nm个不同的状态，分别对应nm个长度为m的序列。 信源输出依赖长度为m+1的随机序列转

7、化为对应的状态序列，这种状态序列符合简单的马尔可夫链的性质。, m阶马尔可夫信源的极限熵,m阶马尔可夫信源的极限熵 m阶马尔可夫信源的极限熵H等于m阶条件熵，记为Hm+1,上式中的 可表示为状态ei (i=1,2,nm)； 信源处于状态ei时，再发下一个符号 （或写成xk），则信源从状态ei转移到ej，即 。所以 其中p(ei)(i=1,2,nm)是m阶马尔可夫信源稳定后的状态极限概率， p(ej /ei)是一步转移概率。,这里利用了m阶马尔可夫信源“有限记忆长度”的根本特性，使无限大参数N变为有限值m，把求极限熵的问题变成了一个求m阶条件熵的问题。 状态一步转移概率p(ej /ei)是给定或

8、测定的。求解Hm+1条件熵的关键就是要得到p(ei)(i=1,2,nm) 。 p(ei)是马尔可夫信源稳定后(N)各状态的极限概率。 有限状态的马尔可夫链：状态空间的状态是有限的。 可列状态的马尔可夫链：状态空间I是0,1,2,。, 有限齐次马尔可夫链各态历经定理,定理：对于有限齐次马尔可夫链，若存在一个正整数l01，且经过l0步，从状态ei转移到ej的l0步转移概率 凡具有各态历经性的m阶马尔可夫信源，其状态极限概率p(ei)可由上式求出。有了p(ei)和测定的p(ej /ei)，就可求出m阶马尔可夫信源的熵Hm+1 。, 有关问题的说明,m阶马尔可夫信源在起始的有限时间内，信源不是平稳和遍

9、历/各态历经性的，状态的概率分布有一段起始渐变过程。经过足够长时间之后，信源处于什么状态已与初始状态无关，这时每种状态出现的概率已达到一种稳定分布。 一般马尔可夫信源并非是平稳信源。但当时齐、遍历的马尔可夫信源达到稳定后，这时就可以看成是平稳信源。,(3) 举 例,例2.2.4 二元2阶马尔可夫信源，原始信号X的符号集为X1=0, X2=1，其状态空间共有nm=22=4个不同的状态e1,e2,e3,e4，即 E：e1=00,e2=01,e3=10,e4=11 状态转移图见右图所示。 解：p(e1/e1)= p(x1/e1)=p(0/00)=0.8 p(e2/e1)= p(x2/e1)=p(1/

10、00)=0.2 p(e3/e2)= p(x1/e2)=p(0/01)=0.5 p(e4/e2)= p(x2/e2)=p(1/01)=0.5 p(e1/e3)= p(x1/e3)=p(0/10)=0.5 p(e2/e3)= p(x2/e3)=p(1/10)=0.5 p(e3/e4)= p(x1/e4)=p(0/11)=0.2 p(e4/e4)= p(x2/e4)=p(1/11)=0.8,由二元信源X0,1得到的状态空间(e1,e2,e3,e4)和相应的一步转移概率构成的2阶马尔可夫信源模型为 求出稳定状态下的p(ej) ，称为状态极限概率。 将一步转移概率代入上式得 p(e1)=0.8 p(e1)+0.5 p(e3) p(e2)=0.2 p(e1)+0.5 p(e3) p(e3)=0.5 p(e2)+0.2 p(e4) p(e4)=0.5 p(e2)+0.8 p(e4),解方程组得 p(e1)= p(e4)=5/14 p(e2)= p(e3)=2/14 计算极限熵 注意： H并非