马尔可夫过程在信源编码中的应用

河南城建学院马尔科夫过程在信源编码中的应用信

自

息、名： 专业名称： 电子信息工程专业班级：0934121指导老师： 所在院系：电气与信息工程学院2014年12月20日摘要首先主要讲述了马尔科夫过程，对马尔科夫过程进行了简介，介绍了马尔科夫过程的数学描述方法并对马尔科夫过程的发展历史进行了简述。在第二章节对马尔科夫过程在信源编码中的应用进行了简单的论述及讲解。信息论中的编码主要包括信源编码和信道编码。信源编码的主要目的是提高有效性，通过压缩每个信源符号的平均比特数或降低信源的码率来提高编码效率；信道编码的主要目标是提高信息传输的可靠性，在信息传输率不超过信道容量的前提下，尽可能增加信源冗余度以减小错误译码概率。研究编码问题是为了设计出使通信系统优化的编译码设备随机过程是与时间相关的随机变量，在确定的时刻它是随机变量。随机过程的具体取值称作其样本函数，所有样本函数构成的集合称作随机过程的样本函数空间，所有样本函数空间及其统计特性即构成了随机过程。目录TOC\o"1-5"\h\z\o"CurrentDocument"1引言 1\o"CurrentDocument"2马尔科夫过程 2\o"CurrentDocument"3马尔科夫过程在信源编码中的应用 4\o"CurrentDocument"4参考文献 131引言随着现代科学技术的发展，特别是移动通信技术的发展，信息的传输在社会科学进步的地位越来越重要。因此如何更加高效的传输信息成了现代科技研究的重要目标。马尔可夫过程是一类非常重要的随机过程。很多在应用中出现的马氏过程模型的研究受到越来越多的重视。在现实世界中，有很多过程都是马尔可夫过程，马尔可夫过程在研究质点的随机运动、自动控制、通信技术、生物工程等领域中有着广泛的应用。我们可以通过对马尔可夫过程的研究来分析马尔可夫信源的特性。由于研究马尔科夫过程在信源编码中的作用，可以利用马尔科夫模型减少信息传输的冗余，提高信息传输的效率。马尔可夫信源是一类有限长度记忆的非平稳离散信源，信源输出的消息是非平稳的随机序列，它们的各维概率分布可能会随时间的平移而改变。由于马尔可夫信源的相关性及可压缩性，它已成为信息领域的热点问题。2马尔科夫过程2.1尔可夫过程简介马尔科夫过程(MARKOVProcess)是一个典型的随机过程。设X(t)是一随机过程，当过程在时刻t0所处的状态为已知时，时刻t(t>t0)所处的状态与过程在t0时刻之前的状态无关，这个特性成为无后效性。无后效的随机过程称为马尔科夫过程。马尔科夫过程中的时同和状态既可以是连续的，又可以是离散的。2.2马尔可夫过程的数学描述2.2.1马尔科夫过程马尔可夫过程是下述这样的一种过程:在已经时刻t0系统所处状态的条件下，在时刻t0以后系统到达的情况与时刻t0以前系统所处的状态无关，完全取决于时刻t0系统所处的状态。这个特性称为无后效性，也称为“马尔可夫性”。马尔可夫过程数学定义如下：设{X(t),tuT}为随机过程，如果对于任意正整数n及t<t<...<t,P{X(t)=X,X(t)=X,...,X(t)=X}>0,并且12 n 112 2 n-1 n-1其条件分布为P{X(t)<X|X(t)=X,X(t)=X，…，X(t)=X}=P{X(t)<X|X(t)=X}nn112 2 n-1 n-1 nn n-1 n-1则称{X(t),惟T}为马尔可夫过程，或称该过程具有马尔可夫性。按照时间和状态的离散、连续情况马尔可夫过程可分为三类：时间与状态(空间)都离散的过程，称为马尔可夫链；时间连续与状态(空间)离散的过程，称为连续时间的马尔可夫过链；时间与状态(空间)都连续的马尔可夫过程。2.2.2马尔可夫链马尔可夫链的数学定义：设有随机过程{Xn，neT}，若对于任意的整数neT和任意的i。，i“-・in+1eI，条件概率满足P{X=i|X=i,X=i,...,X=i}=P{X=i|X=i}n+1n+1 00 11 nn n+1n+1 nn则称{XnneT}为马尔科夫链，简称马氏链。2.3马尔可夫过程的发展20世纪50年代以前，研究马尔可夫过程的主要工具是微分方程和半群理论；1936年前后就开始探讨马尔可夫过程的轨道性质，直到把微分方程和半群理论的分析方法同研究轨道性质的概率方法结合运用，才使这方面的研究工作进一步深化，并形成了对轨道分析必不可少的强马尔可夫性概念。1942年，伊藤清用他创立的随机积分和随机微分方程理论来研究一类特殊而重要的马尔可夫过程一扩散过程，开辟了研究马尔可夫过程的又一重要途径。出于扩大极限定理应用范围的目的，马尔科夫在20世纪初开始考虑相依随机变量序列的规律，并从中选出了最重要的一类加以研究。1906年他在《大数定律关于相依变量的扩展》一文中，第一次提到这种如同锁链般环环相扣的随机变量序列，其中某个变量各以多大的概率取什么值，完全由它前面的一个变量来决定，而与它更前面的那些变量无关。这就是被后人称作马尔科夫链的著名概率模型。也是在这篇论文里，马尔科夫建立了这种链的大数定律。马尔科夫链的引入，在物理、化学、天文、生物、经济、军事等科学领域都产生了连锁性的反应，很快地涌现出一系列新的课题、新的理论和新的学科，并揭开了概率论中一个重要分支一一随机过程理论蓬勃发展的序幕。3马尔可夫过程在信源编码中的应用3.1通信中研究随机过程的重要性在通信、雷达探测、地震探测等领域中，都有传递信号与接收信号的问题。传递信号时会受到噪声的干扰，为了准确地传递和接收信号，就要把干扰的性质分析清楚，然后采取办法消除干扰。这是信息论的主要目的。噪声本身是随机的，所以概率论是信息论研究中必不可少的工具。信息论中的滤波问题就是研究在接收信号时如何最大限度地消除噪声的干扰，而编码问题则是研究采取什么样的手段发射信号，能最大限度地抵抗干扰。在空间科学和工业生产的自动化技术中需要用到信息论和控制理论，而研究带随机干扰的控制问题，也要用到马尔可夫随机过程。图3.1是通信系统模型。从信息论的角度来说，通信的过程就是不确定度减小的过程。而不确定性就是过程的随机性，所以从这个角度来说通信过程的研究可以归结到对于随机过程特性的研究过程。信息噪声信息噪声图3.1通信系统模型从图中可以看到，通信系统中用于表示信息的信号不可能是单一的确定的，而是具有不确定性和随机性的。这种具有不确定性，随机性的信号即称为随机信号。同时通信系统中存在各种干扰和噪声，这些干扰和噪声的波形更具有随机性，是不可预测的,我们称其为随机噪声。尽管随机信号和随机噪声都是不可预测的，但是它们具有一定的统计规律性。在通信系统中，编码过程分为信源编码和信道编码两种，信源编码是为了压缩信息之间的相关性，最大限度提高传信率，目的在于提高通信效率；而信道编码则相反，通过引入相关性，使信息具有一定的纠错和检错的能力从而提高传输信息的可靠性。对于信源编码，实现降低相关性有两种途径，一种是信源概率分布均匀化，另一种是信源独立化。从概率论和随机过程的角度来说，概率分布均匀化就是每个事件发生的概率大致相同，这样就会使每个信源携带的信息量基本相同，那么不确定性就达到最大，即传输过程中产生的信息量就最大；类似的信源独立化是通过对信源进行扩展达到的，通过信源的高次扩展，是扩展信源中每个

符号出现的概率大致相同，这样也实现信息量最大化。对于信道编码，由于信道中存在随机噪声，或者随机干扰，使得经过信道传输后所接收到的码元与发送码元之间存在差异，这种差异就是传输产生的差错。一般信道噪声干扰越大，码元产生差错的概率也就越大。所以信道编码的任务就是构造出以最小冗余度代价换取最大抗干扰性能的码字组合。从信道编码的构造方法看，其基本思路是根据一定的规律在待发送的信息码中加入一些人为多余的码字。这些码字的引入时信息之间具有相关性，虽然降低了信息所能携带的信息量，但是通过相关性可以克服由于随机噪声引入的误码情况。3.2马尔可夫信源3.2.1马尔可夫信源概述马尔可夫信源是一类相对简单的有记忆信源，信源在某一时刻发出某一符号的概率除与该符号有关外，只与此前发出的有限个符号有关。…震I Xm_}Xr"1fS--1fS--图3.2马尔可夫信源模型我们把前面若十个符号看作一个状态，可以认为信源在某一时刻发出某一符号的概率除了与该符号有关外，只与该时刻信源所处的状态有关，而与过去的状态无关。信源发出一个符号后，信源所处的状态即发生改变，这些状态的变化组成了马氏链。马尔可夫信源有记忆的特点:有限记忆长度;信源输出不仅与符号集有关，而且与状态有关；每发一个符号状态要发生转移。所谓状态，是指有限的相关符号组构成的序列。信源的状态集：se侈,e，…e}信源基本符号集：xe{X，X，…X}1 2j 1 2n在每一状态下可能输出的符号：输出随机符号序列：X1X2...X^1X「・.输出随机状态序列：SS...SS...12 l-1l设l时刻信源处于e，输出x.的概率为P（x/e）,p（e/e）lkiiji在l时刻，其前一时刻的状态e.之下而转移到e.的状态转移概率为p（S=e/x=x，Se）=1称为—牛状态转移概率lilml-1=i"1J称为步状态转移概率信源输出的随机状态序列：SS2...Sl1Sl...构成一个马尔可夫链P（x/e）,P（e/e）一般与时刻l相关lk.ljl如果上述条件概率与时刻l无关，称随机过程为时齐的。即有：pl（e/e）＞o此时，信源输出的随机状态序列：SS2...Sl1Sl...构成时齐马尔科夫链马尔可夫信源：以信源输出符号序列内各符号间条件概率来反映记忆特性的一类信源，其满足下列条件：（1）某时刻输出符号仅与此刻信源所处的状态有关；p(S=e/x=x,Se)=lilm l-1=i当具有时齐性时，满足P（x/e）=p（x/e）lki ki（2）某时刻所处状态由当前输出符号与前一时刻信源状态唯一确定p（S=e/x=x,Se）=lilm l-1=i马尔可夫信源输出的状态序列呈时齐马尔科夫链。下面是一个马尔可夫信源的分析实例，马尔可夫信源的信源符号X』x,x,x｝，其可能的状态Se｛e,e,e,e,e｝，状态转移图及1 2 3 1 2 3 4 5£k1p（xk/e）=1矩阵如下所示：a）J矩阵表示］b）一步转移矩阵-彳图3.3马尔可夫信源的状态转移图及相关矩阵x1「x,x.....x1 2,mP(x/x...-lm+1 1…七)-=pxLlk/x...k...•-xk)]m+1 1 mP(e/e)=p(x/e)»p(S=ej^/x,S=e)lji ki, k=1 Jik l-1 i3.2.2m阶马尔可夫信源信源输出当前符号仅与前面m个符号有关的马尔可夫信源，这m个符号为信源在当前时刻的状态。状态总数为n的m次方。信源输出长度为m+1的随机序列转化为对应的状态序列，其构成马尔科夫链。x,x.....x

pxkml/xH的计算m阶马尔可夫信源的条件概率...xkn N—M N-M+1P(x/x.・.xx ...xkn N—M N-M+1厂(kk...kkk) (kkN-N-1TOC\o"1-5"\h\zn 1 m m+1 n-1=P(x /x.・.x)P(kk...k).M+1 1 mm阶马尔可夫信源的极限熵H=limH(l°gP(x /x...x/XX...X)8NW 2 kM+1 k1 km 1 2 N-1=lim-£...工P(xz...x,)logP(X/x,...x,){}N“k=1k=1 k1 k、 2kNk1 kN-1-"N a=limLIL.・・-]£P(x...x )logp(x /x...x)>N"[k=1k=1 k1 kN- 2 kM+1 k1 「i N/x...x)

kk.1m/x...x)

kk.1mk•%)xklogP(xk/xk1"mHkM+1 2kM+1k=1k=1 1 . M+1=H(x /Mxx...x)M+1 12mAhm+1Lk8=1mLk8=1m+1/e)=P(e/e)ki jiHm+1=-2l.…。/eLM+1 k=1 jiiP(x/x...x)=P(xkkk.M+1 1 m(^.^.••人及)全e；^.ax；(%,...%,%,)全eTOC\o"1-5"\h\z1 2m 七1 k虹2七七1 'p(e)是马尔可夫信源稳定后(N*)各状态的极限概率ip(x/X ...X )=P(X/e)=p(e/e)几 XV XV. ki jiM+1 1 m JH=H=-^LTp(e)p(e/e)logp(e/e)8 M+1i j i 2 j 'i=1 j=1 J3.2.3各态经历定理对于有限齐次马尔科夫链，若存在正整数10>1,对一切i，j=1,2，…，nm都有X,X,x，则对每一个j都存在不依赖于I的极限1imp(/e)=P()(j=1,2,,.....M)Lsli N称此马尔科夫链是各态历经的。其极限概率是约束方程组的解p(e)=Enmp(e)p(e./e)(j=1,2,....nm)suchp(e)〉o,Enmp(e)=1马氏链的各态历经定理说明：只有在转移了一定步数后各状态之间可相通的条件下，当转移步数足够大时，处于某一状态的概率才能稳定在某一极限值;各状态相通，均可经历；每个由各状态经历过程产生的序列都有同样的统计特性，即统计均匀性。3.2.4信源的相关性和剩余度讨论信源最主要的目的是为了得到高效率的信源编码，衡量信源编码效率的尺度是什么？能够使信源编码提高效率的根本原因是什么？信源的冗余度实际上就是信源在发出消息时无用信息量所占的百分比。初始信源的冗余度通常是很大的，这为信源的压缩编码提供了可能。压缩编码的目标就是寻找某种编码方法，使得编码后消息序列中的冗余度趋近于0.如果将这种编码包含在信源中，也可以说是寻找某种能够使信源冗余度趋近于0的编码方法。冗余度成为衡量信源编码效率的一个物理量，冗余度越低，编码效率就越高。实际离散信源熵的计算与近似表示过程：H乂H、（X图3.4信源的马尔可夫建模由最大熵定理：H1(X)<Ho(X)=l°gn，logn=H>H>H>...>H>H2 0 12 m+1 s信源符号的相关性越强，所提供的平均信息量就越少。冗余度是编码理论中的一个重要的概