第二章-信息论基本概念.

3.离散有记忆信源－马尔可夫信源马尔可夫信源－非平稳离散信源中的一类特殊信源。是由信源发出的各个符号之间的关连性构成一个整体消息。这种关连性用符号的转移概率（条件概率）表示：如：BOYP(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与其前面（n－1）个时刻的随机变量X1，X2，…，Xn－1的关系可用它们之间的条件概率密度函数来表示，如果满足下式：p(Xn，tn|Xn－1，tn－1，Xn－2，tn－2，…，X1，t1)＝p(Xn，tn|Xn－1，tn－1)则这种随机过程称为单纯马尔可夫过程（一阶马尔可夫过程）K阶马尔可夫过程的特征为：p(Xn，tn|Xn－1，tn－1，Xn－2，tn－2，…，X1，t1)＝p(Xn，tn|Xn－1，tn－1，Xn－2，tn－2，…，Xn－k，tn－k)预备知识:－马尔可夫过程、马尔可夫链马尔可夫链：当马尔可夫过程的随机变量幅度和时间参数均取离散值时，就称作马尔可夫链。设随机过程在时间域上T＝{t1，t2，…，tk－1，tk，…，tn－1，tn}的n个离散时刻上的状态Xk(k＝1，2，3，…，n)都是离散型的随机变量，并且有M个不同的取值S1,S2,…,SM，这M个取值便构成一个状态空间S，S＝{S1,S2,…,SM}.在n个时刻上的n个状态构成一个随机序列（X1，X2，…，Xk－1，Xk，…，Xn－1，Xn）对于这个随机序列，若有：则此序列称为单纯马尔可夫链（一阶马尔可夫链）。一阶马尔可夫链在tn时刻的取值Xn＝Sin的概率仅与前一状态Xn-1有关，与其它时刻状态无关，它的记忆长度为两个时刻。若与它前面K个时刻tn-1，tn-2，…，tn-k有关，则为K阶马尔可夫链，它的记忆长度为（K+1）个时刻。设一阶马尔可夫链在时刻tk－1随机序列的取值Xk－1＝Si，而在下一时刻tk，随机序列的取值Xk＝Sj，则条件概率为:P(j|i)＝P(Xk＝Sj|Xk－1＝Si)因为P(j|i)仅取决于状态Sj和Si，因此称P(j|i)为由状态Si向Sj的转移概率。111111(|,...,)(|)nnnnniniininipxSxSxSpxSxS对于具有M个不同的状态空间，M2个转移概率可排成一转移矩阵：每行元素代表同一起始状态到M个不同终止状态的转移概率；每列元素代表M个不同起始状态到同一终止状态的转移概率；显然有：P(j|i)＝1（i=1,2,…,M）K阶马尔可夫链每个状态由K个符号组成。若信源符号有D种，则状态数目M为：M＝DK)|()|2()|1()2|()2|2()2|1()1|()1|2()1|1(MMPMPMPMPPPMPPPPMj1马尔可夫链可以用香农线图表示。(a),(b),(c)分别表示信源含两种字母(D＝2)的一阶、二阶和三阶马尔可夫链的线图。(d),(e)分别表示D＝3和D＝4的一阶马尔可夫链的线图。AA(A)(B)BB(a)(AB)(BA)(BB)ABBBBAA(AA)B(b)(AAA)(BBB)(ABB)(BAA)(BBA)(AAB)(ABA)(BAB)ABBBAAAABBBAABBA(c)(A)A(B)BBABACC(C)C(d)(A)(B)(C)(D)ACBCBDBAAACDDBCD(e)一、概述一般情况下，信源输出符号之间的相关性可以追溯到最初的一个符号，而在许多信源的输出符号序列中，符号之间的依赖关系是有限的——任何时刻信源符号发生的概率只与前面已经发出的若干个符号有关，而与更前面发出的符号无关。这类信源在输出符号时不仅与符号集有关，还与信源的状态有关。1212121121,,,,,,,,,,,,,,,,(/)1JqlllliklkliijSEEEEXAaaaxxxxsssslEapxasElElE设一般信源所处的状态：每种状态下可能输出的符号：每一个时刻，信源发出一个符号后，状态发生转移，信源输出的符号序列：信源所处的随机状态序列：第时刻，信源处于状态时，输出符号的概率：设信源在时刻处于，时刻转移到的状态转移概率：11(/)(/)(/)(/)(/)(/)ljiljlilklikiljlijipEEpsEsEpxasEpaEpsEsEpEEl信源状态序列服时齐（齐次）马尔可与时刻夫从；，链：无关。状态转移图(香农线图)E1E3E20:0.51:0.51:0.40:0.61【注】E1、E2、E3是三种状态，箭头是指从一个状态转移到另一个状态，旁边的数字代表发出的某符号和条件概率p(ak/Ei)。这就是香农提出的马尔可夫状态转移图，也叫香农线图。二、马尔可夫信源若信源输出的符号和信源所处的状态满足以下两个条件，则称为马尔可夫信源：1111(/,,,)(/)(/)(/)(/)1(/klklilkljlklilklikikiaAljlklpxasExasEpxasEpxasEpaEpaElpsExas（1）某一时刻信源符号的输出只与此刻信源所处的状态有关，而与以前的状态和输出符号都无关，即：当具有时齐性时，有：及（2）信源某时刻所处的状态由当前的输出符号和前一时刻信源的状态唯一决定，即：，0)1iE【注】上述条件表明，若信源处于某一状态Ei，当它发出一个符号后，所处的状态就变了。状态的转移依赖于所发出的信源符号，因此任何时刻信源处在什么状态完全由前一时刻的状态和发出的符号决定。又因条件概率p(ak/Ei)已给定，所以状态之间的转移有一定的概率分布，并可求出状态的一步转移概率p(Ej/Ei)。例：设某信源符号X∈A={a1,a2,a3}，信源所处的状态S∈E={E1,E2,E3,E4,E5}。各状态之间的转移情况如下图所示，请判断这是否是一个马尔可夫信源？解：（1）信源在Ei状态下输出符号ak的条件概率p(ak/Ei)用矩阵表示为:3111124411022(/)(/)11,2,3,4,531044100111442kikikpaEpaEi，且满足，（2）该信源在l时刻所处的状态由当前的输出符号与前一时刻(l-1)信源的状态唯一决定:2111111122112311(/)0(/)1(/)1(/)0llllllllllllpsExasEpsExasEpsExasEpsExasE111002441100022(/)3100044000013100044jipEE可求得状态的一步转移概率：此信源满足马尔可夫的两个条件，所以是马尔可夫信源，并且是齐次马尔可夫信源。三、m阶马尔可夫信源一般有记忆信源：发出的是有关联性的各符号构成的整体消息，即输出的是符号序列，并用符号间的联合概率描述这种关系。马尔可夫信源：用符号之间的转移概率（条件概率）来描述这种关联关系。即马尔可夫信源是以转移概率输出每个信源符号。m阶马尔可夫信源在某一时刻l，符号出现的概率仅与前面已出现的m个符号有关，可以把这前面m个符号序列看成信源在l时刻所处的状态。若每符号取值q种，则共有qm种状态，每种状态对应一个m长(q进制)序列，这种状态序列符合马尔可夫链的性质，可用马氏链来描述，这种信源称为m阶马尔可夫信源。数学模型：11211211212112112(/)(/)112mmmmmqmmkkkkqkkkkmkaaaXkkkkqpaaaapaaaakkkq：，，，，，，，同时满足：，，，，，，【注】当m=1时，为一阶马尔可夫信源。马尔可夫信源熵12111111212121112112111(/)(/)(/)lim(/)lim(/)lim()log(/NmmNNNmNmNmmNNNNkkkkkkkkkkkkkkNNNNNNqqkkkkkkkNkkpaaaaaapaaaapaaaaHHXXXXHHXXXXpaaapaaaa由马尔可夫信源定义及其齐次性：由极限熵，可得：1211211211121111111112)lim()log(/)()log(/)(/)NmmNmmmmqqkkkkkkkNkkqqkkkkkmmkkkkmpaaapaaaapaaapaaaaHXXHXXmHm阶马尔可夫信源的极限熵就等于阶条件熵，记为这表明：设状态12()mikkkEaaaiE1mka,信源处于状态时，再发出下一个符号此时，符号序列231()mkkkaaa231()mjkkkEaaaiE就组成了新的信源状态，这时信源所处的状态由转移到jE112111111(/)(/)(/)(/)(12,12)()(/)log(/)()(/)l()(1,2,,)og(/)(/mmmmmmkkkkkikijimqqmijijiijqqikikiikjimipaaaapaEpaEpEEkqijqHHpEpEEpEEpEpaEpaEpEEpEiqm是阶马尔可夫信源稳定后的，，，，，，其中，状态极限概率)是状态之间的一步转移概率。【注】可见求解马尔可夫信源条件熵关键是要得到()(1,2,,)mipEiq11(/)0lim(/)()(1,2,,)()()(/)(1,2,,)()0()mmljimljijlqmjijiijjli,j=1,2,...,qpEEjipEEpEjqpEpEpEEjqpEpE：对于有限齐次马尔可夫链，若存在一个正整数，对一切都有：则对每一个都存在不依赖于的极限：这种有限齐次马尔可夫马尔可夫链是各态遍历的。其极限概率是方程组满足条件，链的各态遍历定理11mqj的唯一解。【注】上述定理说明，有限齐次、遍历马尔可夫链信源，在初始时刻可以处在任意状态，然后状态之间可以转移，经过足够长时间之后，信源处于什么状态已与初始状态无关。状态极限概率方程组可写为：112()1,()0[(),(),...,()]mmqiqWPWWiWiWWpEpEpEP，其中为状态极限概率分布矢量：为状态一步转移矩阵。[例1]设有二元二阶马尔可夫信源：(0)1/3(1)2/3(0/00)(1/11)0.8(1/00)(0/11)0.2(0/01)(0/10)(1/01)(1/10)0.5pppppppppp信源符号集为{0,1}，初始概率大小为，；条件概率为：画出信源状态转移图？信源熵？信源稳定后符号0、1的概率分布？21234114421343223421324(/)(/)0.8(/)(/)0.2(/)(/)(/)(/)0.50mqEEEEpEEpEEpEEpEEpEEpEEpEEpEE解：由题意得：信源任何时刻发出什么符号只与前面两个符号有关，与前面得符号无关。信源就有种可能的状态，即为00、01、10、11，分别用、、、符号表示。同时可求得状态转移概率：除此之外，其它状态转移概率为，状态转移图如下所示：0.80.200000.50.5(/)0.50.500000.20.8jipEE状态的一步转移概率矩阵为：111321332442441142()()(/)(1,2,,)()0.8()0.5()()0.2()0.5()()0.5()0.2()()0.5()0.8()()15()()14()(mqmjijiijjpEpEpE