马尔可夫进程在信源编码中应用.docx

百度文库好好学习,天天向上河南城建学马尔科夫进程在信源编码中的应姓 名：王叫专业名称：电子信息工程专业班级：0934班1指导老师：贺伟所在院系：电气与信息工程学院2014年12月20日百度文库-好好学习，天天向上摘要首先主要讲述了马尔科夫进程，对马尔科夫进程进行了简介，介绍了马尔 科夫进程的数学描述方式并对马尔科夫进程的发展历史进行了简述。在第二章节对马尔科夫进程在信源编码中的应用进行了简单的论述及讲 解。信息论中的编码主要包括信源编码和信道编码。信源编码的主要目的是提 高有效性，通过紧缩每一个信源符号的平均比特数或降低信源的码率来提高编 码效率；信道编码的主要目标是提高信息传输的靠得住性，在信息传输率不超 过信道容量的前提下，尽可能增加信源冗余度以减小错误译码概率。研究编码 问题是为了设计出使通信系统优化的编译码设备随机进程是与时间相关的随机变量，在肯定的时刻它是随机变量。随机进 程的具体取值称作其样本函数，所有样本函数组成的集合称作随机进程的样本 函数空间，所有样本函数空间及其统计特性即组成了随机进程。-#百度文库-好好学习，天天向上目录1引言12马尔科夫进程23马尔科夫进程在信源编码中的应用44参考文献131引言随着现代科学技术的发展，特别是移动通信技术的发展，信息的传输在社 会科学进步的地位愈来愈重要。因此如何加倍高效的传输信息成了现代科技研 究的重要目标。马尔可夫进程是一类超级重要的随机进程。很多在应用中出现 的马氏进程模型的研究受到愈来愈多的重视。在现实世界中，有很多进程都是 马尔可夫进程，马尔可夫进程在研究质点的随机运动、自动控制、通信技术、 生物工程等领域中有着普遍的应用。咱们可以通过对马尔可夫进程的研究来分 析马尔可夫信源的特性。由于研究马尔科夫进程在信源编码中的作用，可以利用马尔科夫模型减少信息 传输的冗余，提高信息传输的效率。马尔可夫信源是一类有限长度记忆的非平稳离散信源，信源输出的 消息是不平稳的随机序列，它们的各维概率散布可能会随时间的平移而 改变。由于马尔可夫信源的相关性及可紧缩性，它已成为信息领域的热 点问题。2马尔科夫进程尔可夫进程简介马尔科夫进程(MARKOV Process)是一个典型的随机进程。设X(t)是一随 机进程，当进程在时刻to所处的状态为已知时，时刻t(t>tO)所处的状态与 进程在tO时刻之前的状态无关，这个特性成为无后效性。无后效的随机进程 称为马尔科夫进程。马尔科夫进程中的时同和状态既可以是持续的，乂可以是 离散的。马尔可夫进程的数学描述马尔科夫进程马尔可夫进程是下述这样的一种进程：在已经时刻to系统所处状态的条件 下，在时刻tO以后系统抵达的情况与时刻tO以前系统所处的状态无关，完全取 决于时刻tO系统所处的状态。这个特性称为无后效性,也称为“马尔可夫性”。马尔可夫进程数学概念如下：设U'(t),左7为随机进程，若是对于任意 正整数n及乙心<<PX(A)= %,X优)=电,X(九t)= X't>。，而且 其条件散布为PX(G < . I x(G=%, x%)=%，x(%)=%I=P X(九)<X(%)=xJ则称>69, ”刀为马尔可夫进程，或称该进程具有马尔可夫性。依照时间和状态的离散、持续情况马尔可夫进程可分为三类：(1)时间与状态(空间)都离散的进程，称为马尔可夫链；(2)时间持续与状态(空间)离散的进程，称为持续时间的马尔可夫过链；(3)时间与状态(空间)都持续的马尔可夫进程。马尔可夫链马尔可夫链的数学概念：设有随机进程Xn, neT,若对于任意的整数neT和任意的io, ii,in+itl, 条件概率知足n+lP X 向=心 IX。=io, X 尸片，X f=P X则称X“，eT为马尔科夫链，简称马氏链。马尔可夫进程的发展20世纪50年代以前，研究马尔可夫进程的主要工具是微分方程和半群理 论；1936年前后就开始探讨马尔可夫进程的轨道性质，直到把微分方程和半 群理论的分析方式同研究轨道性质的概率方式结合运用，才使这方面的研究工-1百度文库-好好学习，天天向上作进一步深化，并形成了对轨道分析必不可少的强马尔可夫性概念。1942年, 伊藤清用他创建的随机积分和随机微分方程理论来研究一类特殊而重要的马 尔可夫进程一扩散进程，开辟了研究马尔可夫进程的乂一重要途径。出于扩大极限定理应用范围的目的，马尔科夫在20世纪初开始考虑 相依随机变量序列的规律，并从中选出了最重要的一类加以研究。1906年他 在大数定律关于相依变量的扩展一文中，第一次提到这种如同锁链般环环 相扣的随机变量序列，其中某个变量各以多大的概率取什么值，完全由它前面 的一个变量来决定，而与它更前面的那些变量无关。这就是被后人称作马尔科 夫链的著名概率模型。也是在这篇论文里，马尔科夫建立了这种链的大数定律。马尔科夫链的引入，在物理、化学、天文、生物、经济、军事等科学 领域都产生了连锁性的反映，很快地涌现出一系列新的课题、新的理论和新的 学科，并揭开了概率论中一个重要分支一一随机进程理论蓬勃发展的序幕。-#百度文库-好好学习，天天向上3马尔可夫进程在信源编码中的应用通信中研究随机进程的重要性在通信、雷达探测、地震探测等领域中，都有传递信号与接收信号的问题。 传递信号时会受到噪声的干扰，为了准确地传递和接收信号，就要把干扰的性 质分析清楚，然后采取办法消除干扰。这是信息论的主要目的。噪声本身是随 机的，所以概率论是信息论研究中必不可少的工具。信息论中的滤波问题就是 研究在接收信号时如何最大限度地消除噪声的干扰，而编码问题则是研究采取 什么样的手腕发射信号，能最大限度地抵抗干扰。在空间科学和工业生产的自 动化技术中需要用到信息论和控制理论，而研究带随机干扰的控制问题，也要 用到马尔可夫随机进程。图是通信系统模型。从信息论的角度来讲，通信的进程就是不肯定度减小 的进程。而不肯定性就是进程的随机性，所以从这个角度来讲通信进程的研究 可以归结到对于随机进程特性的研究进程。信息 1发信 J传输媒介 J收信，受信噪声图3.1通信系统模型从图中可以看到，通信系统顶用于表示信息的信号不可能是单一的肯定 的，而是具有不肯定性和随机性的。这种具有不肯定性，随机性的信号即称为 随机信号。同时通信系统中存在各类干扰和噪声，这些干扰和噪声的波形更具 有随机性，是不可预测的，咱们称其为随机噪声。虽然随机信号和随机噪声都 是不可预测的，可是它们具有必然的统计规律性。在通信系统中，编码进程分为信源编码和信道编码两种，信源编码是为了 紧缩信息之间的相关性，最大限度提高传信率，目的在于提高通信效率；而信 道编码则相反，通过引入相关性，使信息具有必然的纠错和检错的能力从而提 高传输信息的靠得住性。对于信源编码，实现降低相关性有两种途径，一种是信源概率散布均匀化, 另一种是信源独立化。从概率论和随机进程的角度来讲，概率散布均匀化就是 每一个事件发生的概率大致相同，这样就会使每一个信源携带的信息量大体相 -3百度文库-好好学习，天天向上同，那么不肯定性就达到最大，即传输进程中产生的信息量就最大；类似的信 源独立化是通过对信源进行扩展达到的，通过信源的高次扩展，是扩展信源中 每一个符号出现的概率大致相同，这样也实现信息量最大化。对于信道编码，由于信道中存在随机噪声，或随机干扰，使得通过信道传 输后所接收到的码元与发送码元之间存在不同，这种不同就是传输产生的过 失。一般信道噪声干扰越大，码元产生过失的概率也就越大。所以信道编码的任务就是构造出以最小冗余度代价换取最大抗干扰性能 的码字组合。从信道编码的构造方式看，其大体思路是按照必然的规律在待发 送的信息码中加入一些人为多余的码字。这些码字的引入时信息之间具有相关 性，虽然降低了信息所能携带的信息量，可是通过相关性可以克服由于随机噪 声引入的误码情况。马尔可夫信源马尔可夫信源概述马尔可夫信源是一类相对简单的有记忆信源，信源在某一时刻发出某一符 号的概率除与该符号有关外，只与此前发出的有限个符号有关。X加兀xw+1 图马尔可夫信源模型咱们把前面若干个符号看做一个状态，可以以为信源在某一时刻发出某一 符号的概率除与该符号有关外，只与该时刻信源所处的状态有关，而与过去的 状态无关。信源发出一个符号后，信源所处的状态即发生改变，这些状态的转 变组成了马氏链。马尔可夫信源有记忆的特点:有限记忆长度;信源输出不仅与符号集有关, 而且与状态有关；每发一个符号状态要发生转移。所谓状态，是指有限的相关 符号组组成的序列。信源的状态集：S£&,«，,信源大体符号集：xeX1,X,，.Xj在每一状态下可能输出的符号：输出随机符号序列：XiXlXzXl输出随机状态序列：SSlS-Sl设1时刻信源处于&,输出乂的概率为P/（xJe），P/（eJe）在1时刻，其前一时刻的状态8之下而转移到约的状态转移概率为_JopS = e, /%=% S“e）=（J称为一步状态转移概率 信源输出的随机状态序列：SS-SiS,组成一个马尔可夫链0%/6）力（6/6）一般与时刻1相关若是上述条件概率与时刻1无关，称随机进程为时齐的。即有：此时，信源输出的随机状态序列：SSLSiSr组成时齐马尔科夫链马尔可夫信源：以信源输出符号序列内各符号间条件概率来反映记忆特性的一类信源，其 知足下列条件：-5百度文库-好好学习，天天向上（1）某时刻输出符号仅与此刻信源所处的状态有关;当具有时齐性时，知足p卬e= p（xje）（2）某时刻所处状态由当前输出符号与前一时刻信源状态唯一肯定O、p（S/ = eJy = X/S/.£）= 1/马尔可夫信源输出的状态序列呈时齐马尔科夫链。下面是一个马尔可夫信源的分析实例，马尔可夫信源的信源符号XeM，x*xJ，其可能的状态5*备a，33，&，«，状态转移图及Z=P（x/e）= i矩阵如下所示：!423.401411024uOilU2203上d440001 40013 4与000014a）矩阵表示b） 一步转移矩阵图马尔可夫信源的状态转移图及相关矩阵X工，工2,X机-#百度文库-好好学习，天天向上P/（e j / e） = P（xJ 8），XL P（S 尸e jXJ xeS - = e）阶马尔可夫信源信源输出当前符号仅与前面m个符号有关的马尔可夫信源,这m个符号为 信源在当前时刻的状态。状态总数为n的m次方。信源输出长度为m+l的随机 序列转化为对应的状态序列，其组成马尔科夫链。P/（x/hxjXeX2,.xmP、Xk 1 xk xk）1 - nr+l A 1- nr的计算m阶马尔可夫信源的条件概率1 Xl-Xl .Xk Xk）= P（Xk /Xk Xk .Xk）K IT A. | K jji KKiK n K .V-A； AV .V-A/-IK NT=P（Xk I Xk Xk ）八M-l 八l 八mm阶马尔可夫信源的极限燃乩=圾 Mog2Ps，以税./XiXlXnt）m m=也？（见”）logUW4kr kbmm=则?p（wj咋2麻/丹%）， kF kAN m= ?,?用）log户以M.Jx佐以PkF k m.F= H（X,m+J XxXl-Xn）至H 2Hm+的计算力“kr鼠"p（xkJ4龙鼠户P（xJ e） = P（eJ）百度文库-好好学习，天天向上（%）= &次以=xxkrxkxkJ 建，（8）是马尔可夫信源稳定后（N-8）各状态的极限概率pkJ XkjX” =P / e）= p（ej e）m mH8 ="历+尸-1 t（，）p（e,/e）log、p（eJe） r=l y=l77各态经历定理对于有限齐次马尔科夫链，若存在正整数1。之1,对一切i, j=i,2,，n01都有X, x,x，则对每一个j都存在不依赖于I的极限Jim p（/）=尸（）0 = 1,2,.弋） LfS l称此马尔科夫链是各态历经的。其极限概率是约束方程组的解m尸匕）=ZZ P（e） p（e, / e）（J = 1,2, ./）msuch p （,）00尸如尸马氏链的各态历经定理说明：只有在转移了必然步数后各状态之间可相通 的条件下，当转移步数足够大时.，处于某一状态的概率才能稳定在某一极限值; 各状态相通，都可经历；每一个由各状态经历进程产生的序列都有一样的统计 特性，即统计均匀性。信源的相关性和剩余度讨论信源最主要的目的是为了取得高效率的信源编码，衡量信源编码效率 的尺度是什么？能够使信源编码提高效率的根本原因是什么？信源的冗余度 实际上就是信源在发出消息时无用信息量所占的百分比。初始信源的冗余度一 般是很大的，这为信源的紧缩编码提供了可能。紧缩编码的目标就是寻觅某种 编码方式，使得编码后消息序列中的冗余度趋近于0.若是将这种编码包括在 信源中，也可以说是寻觅某种能够使信源冗余度趋近于0的编码方式。冗余度 成为衡量信源编码效率的一个物理量，冗余度越低，编码效率就越高。实际离散信源熠的计算与近似表示进程：HjHA)图信源的马尔可夫建模由最大端定理：/1(X)</0(X) = log；n信源符号的相关性越强，所提供的平均信息量就越少。冗余度是编码理论 中的一个重要的概念；在信源编码中，人们老是在寻觅紧缩信源冗余度的方式 来提高传输的有效性；在信道编码中，人们乂老是采取注入冗余度的方式来提 高传输的靠得住性。信源的剩余度来自两个方面，一是信源符号间的相关性，相关程度越大, 符号间的依赖关系越长，信源的实际焙越小，另一方面是信源符号散布的不均 匀性使信源的实际端越小。为了更经济有效的传送信息，需要尽可能紧缩信源的剩余度，紧缩剩余度 的方式就是尽可能减小符号间的相关性，而且尽可能的使信源符号等概率散 布。从提高信息传输效率的观点动身，人们老是希望尽可能去掉剩余度。可是 从提高抗干扰能力角度来看，却希望增加或保留信源的剩余度，因为剩余度大 的消息抗干扰能力强。马尔科夫模型的其他应用隐马尔可夫模型是马尔可夫链的一种，它的状态不能直接观察到，但能通 过观测向量序列观察到，每一个观测向量都是通过某些概率密度散布表现为各 类状态，每一个观测向量是由一个具有响应概率密度散布的状态序列产生。最 近几年来，隐马尔可夫模型(HMM)在模式识别与随机信号处置中有着最普遍的 应用，最成功的例子如语音识别和文字识别。HMM还被引入计算机文字识别和 移动通信核心技术”多用户的检测”。-11四参考文献1周炯槃.通信原理，北京邮电大学，20052樊平毅.随机进程理论与应用M.北京：清华大学出版社,2005.3胡细宝.概率论、数理统计、随机进程，北京邮电大学，20044陆传费.工程系统中的随机进程，电子工业出版社，20005邵雅丽，夏成娇，李晓翠.J.6池秀清.J.,.7张海刚海D.山东大学,2010 .