第二章-信息论基本概念

回顾：单符号无记忆信源熵：H(X)bit/符号符号序列无记忆信源熵：KH(X)bit/序列符号序列有记忆信源熵：联合熵H(X1X2…XN)bit/序列平均符号熵极限熵121lim()lim()bit/NNNNHHHXXXNX符号121()bit/NHXXXN符号121lim()lim(/)bit/NNNNNHHHXXXXX符号平稳信源马尔可夫信源有记忆的特点：1、有限记忆长度2、信源输出不仅与符号集有关，而且与状态有关3、发出一个个符号，每发一个符号状态要发生转移状态：有限的相关符号组构成的序列马尔可夫信源：以信源输出符号序列内各符号间条件概率来反映记忆特性的一类信源。m阶马尔可夫信源：信源输出的当前符号仅与前面m个符号有关的马尔可夫信源。1111211()()(,,)mmmnimmiiiiixxxXxXPpXXxxsxx此时，状态模型阶马尔可夫信源的数学m121,,,1,2,,miiin马尔可夫信源的定义：（1）某一时刻信源符号的输出只与当前的信源状态有关，而与以前的状态无关。(2)信源状态只由当前输出符号和前一时刻的信源状态唯一确定。llXXXX121输出符号序列：llSSSS121输出状态序列：符号条件概率:状态转移概率:)(iksxp)(ijssp通过引入符号条件概率和状态转移概率,马尔可夫信源可转化为马尔可夫链。一步转移概率：1()(|)ijmjmipmpSsSs1()(|)ijmjmiijpmpSsSsp对于齐次马尔可夫链，有(|)kipxs状态转移概率可用条件概率计算。转移概率矩阵和状态转移图（香农线图）1111...=...qqqqppPpp状态转移图（香农线图）圆圈表示状态。状态之间的有向线段表示状态转移。有向线段边的符号和数字代表发出的符号和条件概率。马尔可夫链可以用香农线图表示。(a),(b),(c)分别表示信源含两种字母(D＝2)的一阶、二阶和三阶马尔可夫链的线图。(d),(e)分别表示D＝3和D＝4的一阶马尔可夫链的线图。AA(A)(B)BB(a)(AAA)(BBB)(ABB)(BAA)(BBA)(AAB)(ABA)(BAB)ABBBAAAABBBAABBA(c)(A)(B)(C)(D)ACBCBDBAAACDDBCD(e)2k...K,4.X{,,,}kkXXXXX12mkiiii112n1输出的消息是符号序列：xxx2发出的符号序列是顺序发出3在第次发出的符号x取自单符号信源从而信源模型可以表示为：xxx马尔可夫信源的特点：15.)(|)kkmkiiikpxxxkk-mk-m+1k-1iiii在第次发出的符号x与前面m个符号有关。（xxx称为状态这种关联性用条件概率表示：111106.))(|)(|)7.(|)(|)(|)kkmkmjmiiiimjmijijikpSsSspxxxpSsSspSsSspsskk-mk-m+1k-1k-m+1k-m+1kiiiiijiii在第次发出的符号x,状态改变s=（xxxs=（xxx用状态转移概率表示：齐次马尔可夫信源＝＝例：(0|00)(1|11)0.8(1|00)(0|11)0.2(0|01)(0|10)0.5(1|01)(1|10)0.5pppppppp设有一个二进制二阶马尔可夫信源，其信源符号集为{0,1},条件概率为求状态转移矩阵，并给出香农线图。1234112132421323344400010(|)(0|00)0.8(|)(1|00)0.2(|)(0|01)0.5(|)(1|01)0.5(|)(0|10)0.5(|)(1|10)0.5(|)(0|11)0.2(|)(1|11)0.8sssspssppssppssppssppssppssppssppssp令＝，＝，＝1，＝11，转移概率矩阵P为0.80.P=00000.50.50.50.500000.20.82001001110.80.20.50.50.50.20.50.8m阶马尔可夫信源的极限熵121lim()NNNXHHXXX111)(mmmHXXXH)s/X(H)s(p)/sx(logp)s/x(p)s(p)/sx(logp)s,x(p)XXX/X(HHHin1iin1in1jijijin1in1jijijm211m1mmmmP(si)为状态概率的平稳分布，由转移概率矩阵决定，H(X/si)表示信源处于某一状态si时发出某一个消息符号的平均不确定性。遍历性对于齐次马尔可夫链，若对于所有状态si,sj,均存在不依赖于初始状态si的极限1,0lim)(jjijiijjnijnpppppp且满足则称其为具有遍历性的马尔可夫链。遍历性的意义无论从哪个状态出发，当转移步数足够大时，转移到状态sj的概率近似等于一个常数pj。也就是说：马尔可夫链在初始时刻可以处于任意状态，经过足够长时间的状态转移后，它所处的状态与初始状态无关。此时每种状态出现的概率已达到一种平稳分布。()lim()jjkjkppspSs称为状态的平稳分布。jijiiWpWWPW即有对齐次马尔可夫链，例:一个二阶马尔可夫信源，其香农线图如下，求其信源熵。001001110.80.20.50.50.50.20.50.81234112132421323344400010(|)(0|00)0.8(|)(1|00)0.2(|)(0|01)0.5(|)(1|01)0.5(|)(0|10)0.5(|)(1|10)0.5(|)(0|11)0.2(|)(1|11)0.8sssspssppssppssppssppssppssppssppssp令＝，＝，＝1，＝11，转移概率矩阵P为0.80.P=00000.50.50.50.500000.20.82令平稳分布：4321,,,spspspspW则：41iijijjsspspspW写成矩阵形式：WPW145()()14psps232()()14psps)5.0log5.05.0log5.0()/()/()2.0log2.08.0log8.0()/()/()/(log)/()/()(8.0)/()(324121413sXHsXHsXHsXHsxpsxpsXHbitsXHspHHijijjiiii这里：符号注意：1、平稳信源，即其概率分布具有时间推移不变性。Hnm一、并非在任何情况下都存在，对元阶马尔可夫信源2()1,2,,mjpsjn、存在，二、m阶马尔可夫与发生长度为m的符号序列的有记忆信源的区别：1、马尔可夫信源发出一个个符号，有限长度有记忆信源发出一组组符号；2、马尔可夫信源记忆长度虽然有限，但依赖关系延伸到无穷远。长为m的有限记忆信源符号间的依赖关系仅限于每组内，组与组之间没有依赖关系；有记忆信源的极限熵是平均符号熵的极限。是条件熵，熵、马尔可夫信源的极限13mH)(1limXHNN例：设某信源符号X∈A={a1,a2,a3},信源所处的状态S∈E={E1,E2,E3,E4,E5}.各状态之间的转移情况如下图所示，请判断这是否是一个马尔可夫信源？1E2E3E4E5E11:2a21:4a31:4a21:2a31:2a13:4a31:4a1:1a21:4a31:2a11:4a马尔可夫信源定义：若一信源满足下列两点，即为马尔可夫信源。(1)输出符号只与当前状态有关；(2)当前状态和输出唯一决定了下一状态。解：（1）信源在Ei状态下输出符号ak的条件概率p(ak/Ei)用矩阵表示为2141410014104321210414121)]|([ikEap31(|)1,1,2,3,4,5kikpaEi并且满足（2）该信源在l时刻所处的状态由当前的输出符号与前一时刻(l-1)信源的状态唯一决定1E2E3E4E5E11:2a21:4a31:4a21:2a31:2a13:4a31:4a1:1a21:4a31:2a11:4a状态的一步转移概率：11100244110002231[(|)]00044000013100044jipEE此信源满足马尔可夫信源的两个条件，是马尔可夫信源，并且是齐次马尔可夫信源。例：设两位二进制码所代表的四个状态分别为00，01，10，11，其符号转移概率和状态转移概率由下列两表给出：试求稳定条件下各状态的概率起始状态发出符号S0(00)S1(01)S2(10)S3(11)011/21/31/41/51/22/33/44/5起始状态终止状态S0(00)S1(01)S1(01)S2(10)S3(11)S0(00)S2(10)S3(11)1/201/401/203/4001/301/502/304/5解：据题意，可画出相应的香农线图设稳定状态下，各个状态的概率为P(S0)＝P0，P(S1)＝P1，P(S2)＝P2，P(S3)＝P3根据图示，可得P0＝1/2P0＋1/4P2P1＝1/2P0＋3/4P2P2＝1/3P1＋1/5P3P3＝4/5P3＋2/3P1P0＋P1＋P2＋P3＝1由上面五个方程，可得：P0＝3/35，P1＝6/35,P2＝6/35，P3＝4/7(01)(10)(11)011110001/21/21/32/31/43/4(00)1/54/5例：有一个一阶马尔可夫信源，已知试画出该信源的香农线图，并求出信源熵。解：该信源的香农线图为：在计算信源熵之前，先用转移概率求稳定状态下二个状态x1和x2的概率和3211)(xxp3112)(xxp1)(21xxp0)(22xxp1/3(x2)(x1)2/31)(2xp)(1xp)()()(21321xpxpxp)(0)()(21312xpxpxp1)()(21xpxp4/3)(1xp4/1)(2xp2211()()log()322111loglog1log14333340.689ijijiijHpxpxxpxxbit/符号[小结]两种有记记忆信源比较类型m阶马氏过程m长有记忆信源依赖关系(相当于)记忆长度为m符号间关系可延伸到无穷（卷积码）m个符号为一组组内相关，组间无关（分组码）描述状态转移(条件)概率联合概率每符号平均熵极限熵Hm+1Hm(X)=(1/m)H(X1X2…Xm)总结:各种离散信源的熵(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/符号序列]Ni1Ni1(3)发出符号序列消息的离散有记忆信源熵发出K重符号序列消息的离散有记忆信源熵也为共熵H(XK)当K＝2时H(X2)＝H(X)＋H(X|X)∵H(X|X)H(X)∴H(X2)2H(X)推广到K重H(XK)＝H(X)＋H(X|X)＋…＋H(X|XX…X)[bit/符号序列](K－1)个(4)发出符号序列消息的马尔可夫信源熵马尔可夫信源熵是条件熵若从前一状态Ei转移到后一状态Ej有多种可能性，则信源由状态Ei发出一个符号的熵H（X/i）为H（X/i）＝－P(xj|Ei)logP(xj|Ei)再进一步对前一状态E