1、隨機過程綜述報告馬爾可夫過程在信源編碼中的應用院 系：專 業：姓 名：學 號：信息科學技術學院 信息與通信工程 呂成鵬1120110201摘要隨機過程是與時間相關的隨機變量，在確定的時刻它是隨機變量。隨機過程的具體取值稱作其樣本函數，所有樣本函數構成的集合稱作隨機過程的樣本函數空間，所有樣本函數空間及其統計特性即構成了隨機過程。信息論中的編碼主要包括信源編碼和信道編碼。信源編碼的主要目的是提高有效性，通過壓縮每個信源符號的平均比特數或降低信源的碼率來提高編碼效率；信道編碼的主要目標是提高信息傳輸的可靠性，在信息傳輸率不超過信道容量的前提下，盡可能增加信源冗余度以減小錯誤譯碼概率。研究編碼問題是

2、為了設計出使通信系統優化的編譯碼設備。馬爾可夫信源是一類有限長度記憶的非平穩離散信源，信源輸出的消息是非平穩的隨機序列，它們的各維概率分布可能會隨時間的平移而改變。由于馬爾可夫信源的相關性及可壓縮性，它已成為信息領域的熱點問題。隨機過程理論是研究隨機信號和信息論的數學工具，針對不同的通信系統我們可以建立相應的數學模型。馬爾可夫過程是一類非常重要的隨機過程。隨著現代科學技術的發展，很多在應用中出現的馬氏過程模型的研究受到越來越多的重視。在現實世界中，有很多過程都是馬爾可夫過程，馬爾可夫過程在研究質點的隨機運動、自動控制、通信技術、生物工程等領域中有著廣泛的應用。我們可以通過對馬爾可夫過程的研究來

3、分析馬爾可夫信源的特性。關鍵字：隨機過程、信源編碼、馬爾可夫信源、馬爾可夫過程- 1 -1.隨機過程1.1隨機過程發展簡述在當代科學與社會的廣闊天地里，人們都可以看到一種叫作隨機過程的數學模型：從銀河亮度的起伏到星系空間的物質分布、從分子的布朗運動到原子的蛻變過程，從化學反應動力學到電話通訊理論、從謠言的傳播到傳染病的流行、從市場預測到密碼破譯，隨機過程理論及其應用幾乎無所不在。一些特殊的隨機過程早已引起人們注意，例如1907年前后，馬爾可夫研究過一列有特定相依性的隨機變量，后人稱之為馬爾可夫鏈；又如1923年維納給出了布朗運動的數學定義，后人稱這種數學上的布朗運動為維納過程，這種過程至今仍是

4、重要的研究對象。雖然如此，隨機過程一般理論的研究通常認為開始于30年代。1931年，柯爾莫哥洛夫發表了概率論的解析方法；三年后，辛欽發表了平穩過程的相關理論。這兩篇重要論文為馬爾可夫過程與平穩過程奠定了理論基礎。稍后，P.萊維出版了關于布朗運動與可加過程的兩本書，其中蘊含著豐富的概率思想。1953年，杜布的名著隨機過程論問世，它系統且嚴格地敘述了隨機過程的基本理論。1951年伊藤清建立了關于布朗運動的隨機微分方程的理論，為研究馬爾可夫過程開辟了新的道路；近年來由于鞅論的進展，人們討論了關于半鞅的隨機微分方程；而流形上的隨機微分方程的理論，正方興未艾。60年代，法國學派基于馬爾可夫過程和位勢理論

5、中的一些思想與結果，在相當大的程度上發展了隨機過程的一般理論，包括截口定理與過程的投影理論等，中國學者在平穩過程、馬爾可夫過程、極限定理、隨機微分方程等方面也做出了較好的工作。1.2 隨機過程的數學描述設隨機試驗E的樣本空間，T是一個數集（T(-,)），如果對于每一個t T，都有一個定義在樣本空間上的隨機變量X(w,t)，w，則稱依賴于t的一族隨機變量X(w,t)，tT為隨機過程或隨機函數，簡記為X(t)，tT 或X(t)，其中t稱為參數，T稱為參數集。當T=0,1,2,，T=1,2,，T=,-2,-1,0,1,2,時，X(w,t)t T稱為隨機序列或時間序列。2. 馬爾可夫過程2.1 馬爾可

6、夫過程簡介馬爾科夫過程(MarKov Process)是一個典型的隨機過程。設X(t)是一隨機過程，當過程在時刻t0所處的狀態為已知時，時刻t(tt0)所處的狀態與過程在t0時刻之前的狀態無關，這個特性成為無后效性。無后效的隨機過程稱為馬爾科夫過程。馬爾科夫過程中的時同和狀態既可以是連續的，又可以是 - 2 -離散的。2.2 馬爾可夫過程的數學描述 2.2.1 馬爾可夫過程馬爾可夫過程是下述這樣的一種過程：在已經時刻t0系統所處狀態的條件下，在時刻t0以后系統到達的情況與時刻t0以前系統所處的狀態無關，完全取決于時刻t0系統所處的狀態。這個特性稱為無后效性，也稱為“馬爾可夫性”。 馬爾可夫過程

7、數學定義如下：設X(t),tT 為隨機過程，如果對于任意正整數n及t1t2.0,并且xn|X(t1)=x,X(t12)=x2,.,X(tn-1)=n-1=PX(tn)xn|X(tn-1)=xn-1則稱X(t),tT為馬爾可夫過程，或稱該過程具有馬爾可夫性。 按照時間和狀態的離散、連續情況馬爾可夫過程可分為三類：(1) 時間與狀態（空間）都離散的過程，稱為馬爾可夫鏈；(2) 時間連續與狀態（空間）離散的過程，稱為連續時間的馬爾可夫過鏈； (3) 時間與狀態（空間）都連續的馬爾可夫過程。 2.2.2 馬爾可夫鏈馬爾可夫鏈的數學定義:設有隨機過程Xn，nT，若對于任意的整數nT和任意的i0，i1，i

8、n+1I，條件概率滿足PXn+1=in+1|X=i0,X1=i1,.,Xn=in=PXn+1=in+1|Xn=in則稱Xn,nT為馬爾科夫鏈，簡稱馬氏鏈。 2.3 馬爾可夫過程的發展20世紀50年代以前，研究馬爾可夫過程的主要工具是微分方程和半群理論；1936年前后就開始探討馬爾可夫過程的軌道性質，直到把微分方程和半群理論的分析方法同研究軌道性質的概率方法結合運用，才使這方面的研究工作進一步深化，并形成了對軌道分析必不可少的強馬爾可夫性概念。1942年，伊藤清用他創立的隨機積分和隨機微分方程理論來研究一類特殊而重要的馬爾可夫過程擴散過程，開辟了研究馬爾可夫過程的又一重要途徑。 出于擴大極限定理

9、應用范圍的目的，馬爾科夫在20世紀初開始考慮相依隨機變量序列的規律，并從中選出了最重要的一類加以研究。1906年他在大數定律關于相依變量的擴展一文中，第一次提到這種如同鎖鏈般環環相扣的隨機變量序列，其中某個變量各以多大的概率取什么值，完全由它前面的一個- 3 -變量來決定，而與它更前面的那些變量無關。這就是被后人稱作馬爾科夫鏈的著名概率模型。也是在這篇論文里，馬爾科夫建立了這種鏈的大數定律。 馬爾科夫鏈的引入，在物理、化學、天文、生物、經濟、軍事等科學領域都產生了連鎖性的反應，很快地涌現出一系列新的課題、新的理論和新的學科，并揭開了概率論中一個重要分支隨機過程理論蓬勃發展的序幕。3. 馬爾可夫

10、過程在信源編碼中的應用3.1通信中研究隨機過程的重要性在通信、雷達探測、地震探測等領域中，都有傳遞信號與接收信號的問題。傳遞信號時會受到噪聲的干擾，為了準確地傳遞和接收信號，就要把干擾的性質分析清楚，然后采取辦法消除干擾。這是信息論的主要目的。噪聲本身是隨機的，所以概率論是信息論研究中必不可少的工具。信息論中的濾波問題就是研究在接收信號時如何最大限度地消除噪聲的干擾，而編碼問題則是研究采取什么樣的手段發射信號，能最大限度地抵抗干擾。在空間科學和工業生產的自動化技術中需要用到信息論和控制理論，而研究帶隨機干擾的控制問題，也要用到馬爾可夫隨機過程。圖3.1是通信系統模型。從信息論的角度來說，通信的

11、過程就是不確定度減小的過程。而不確定性就是過程的隨機性，所以從這個角度來說通信過程的研究可以歸結到對于隨機過程特性的研究過程。圖3.1 通信系統模型從圖中可以看到，通信系統中用于表示信息的信號不可能是單一的確定的，而是具有不確定性和隨機性的。這種具有不確定性，隨機性的信號即稱為隨機信號。同時通信系統中存在各種干擾和噪聲，這些干擾和噪聲的波形更具有隨機性，是不可預測的,我們稱其為隨機噪聲。盡管隨機信號和隨機噪聲都是不可預測的，但是它們具有一定的統計規律性。在通信系統中，編碼過程分為信源編碼和信道編碼兩種，信源編碼是為了壓縮信息之間的相關性，最大限度提高傳信率，目的在于提高通信效率；而信 - 4

12、-道編碼則相反，通過引入相關性，使信息具有一定的糾錯和檢錯的能力從而提高傳輸信息的可靠性。對于信源編碼，實現降低相關性有兩種途徑，一種是信源概率分布均勻化，另一種是信源獨立化。從概率論和隨機過程的角度來說，概率分布均勻化就是每個事件發生的概率大致相同，這樣就會使每個信源攜帶的信息量基本相同，那么不確定性就達到最大，即傳輸過程中產生的信息量就最大；類似的信源獨立化是通過對信源進行擴展達到的，通過信源的高次擴展，是擴展信源中每個符號出現的概率大致相同，這樣也實現信息量最大化。對于信道編碼，由于信道中存在隨機噪聲，或者隨機干擾，使得經過信道傳輸后所接收到的碼元與發送碼元之間存在差異，這種差異就是傳輸

13、產生的差錯。一般信道噪聲干擾越大，碼元產生差錯的概率也就越大。所以信道編碼的任務就是構造出以最小冗余度代價換取最大抗干擾性能的碼字組合。從信道編碼的構造方法看，其基本思路是根據一定的規律在待發送的信息碼中加入一些人為多余的碼字。這些碼字的引入時信息之間具有相關性，雖然降低了信息所能攜帶的信息量，但是通過相關性可以克服由于隨機噪聲引入的誤碼情況。3.2 馬爾可夫信源3.2.1馬爾可夫信源概述馬爾可夫信源是一類相對簡單的有記憶信源，信源在某一時刻發出某一符號的概率除與該符號有關外，只與此前發出的有限個符號有關。圖3.2 馬爾可夫信源模型- 5 -我們把前面若干個符號看作一個狀態，可以認為信源在某一

14、時刻發出某一符號的概率除了與該符號有關外，只與該時刻信源所處的狀態有關，而與過去的狀態無關。信源發出一個符號后，信源所處的狀態即發生改變，這些狀態的變化組成了馬氏鏈。馬爾可夫信源有記憶的特點：有限記憶長度；信源輸出不僅與符號集有關，而且與狀態有關；每發一個符號狀態要發生轉移。所謂狀態，是指有限的相關符號組構成的序列。信源的狀態集：在每一狀態下可能輸出的符號：輸出隨機符號序列：X1信源基本符號集： X2.Xl-1Xl.輸出隨機狀態序列：S1S2.Sl-1Sl.設l時刻信源處于ei，輸出xk的概率為在l時刻，其前一時刻的狀態ei之下而轉移到ej的狀態轉移概率為稱為一步狀態轉移概率信源輸出的隨機狀態

15、序列：S1S2.Sl-1Sl.構成一個馬爾可夫鏈一般與時刻l相關如果上述條件概率與時刻l無關，稱隨機過程為時齊的。即有：- 6 -此時，信源輸出的隨機狀態序列：S1S2.Sl-1Sl.構成時齊馬爾科夫鏈 馬爾可夫信源：以信源輸出符號序列內各符號間條件概率來反映記憶特性的一類信源，其滿足下列條件：（1） 某時刻輸出符號僅與此刻信源所處的狀態有關；P(Xl=x/Skl=e,Xil-1=xk,S1l-1=ej,.)=p(x/e)lki當具有時齊性時，滿足p(x/e)=lkip(xk/ei)（2）某時刻所處狀態由當前輸出符號與前一時刻信源狀態唯一確定。馬爾可夫信源輸出的狀態序列呈時齊馬爾科夫鏈。下面是

16、一個馬爾可夫信源的分析實例，馬爾可夫信源的信源符號Xx1,x2,x3，其可能的狀態Se1,e2,e3,e4,e5，狀態轉移圖及矩陣如下所示：a）狀態轉移圖 b）矩陣表示- 7 -c）一步轉移矩陣圖3.3 馬爾可夫信源的狀態轉移圖及相關矩陣3.2.2 m階馬爾可夫信源信源輸出當前符號僅與前面m個符號有關的馬爾可夫信源，這m個符號為信源在當前時刻的狀態。狀態總數為n的m次方。信源輸出長度為m+1的隨機序列轉化為對應的狀態序列，其構成馬爾科夫鏈。nkm+1=1m階馬爾可夫信源的條件概率 P(xkm+1/xk.xk1m)=1;k1,k2,.,km,km+11,2,.,n- 8 -m階馬爾可夫信源的極限

17、熵Hm+1的計算：(xk1xk.xk2) me;xki m+1xk;(xk2.xkmxk)m+1ejp(ei)是馬爾可夫信源穩定后（N）各狀態的極限概率3.2.3 各態歷經定理對于有限齊次馬爾科夫鏈，若存在正整數l01,對一切i，j=1,2，n都有- 9 - m，則對每一個j都存在不依賴于i的極限稱此馬爾科夫鏈是各態歷經的。其極限概率是約束方程組的解馬氏鏈的各態歷經定理說明：只有在轉移了一定步數后各狀態之間可相通的條件下，當轉移步數足夠大時，處于某一狀態的概率才能穩定在某一極限值；各狀態相通，均可經歷；每個由各狀態經歷過程產生的序列都有同樣的統計特性，即統計均勻性。3.2.4 信源的相關性和剩

18、余度討論信源最主要的目的是為了得到高效率的信源編碼，衡量信源編碼效率的尺度是什么？能夠使信源編碼提高效率的根本原因是什么？信源的冗余度實際上就是信源在發出消息時無用信息量所占的百分比。初始信源的冗余度通常是很大的，這為信源的壓縮編碼提供了可能。壓縮編碼的目標就是尋找某種編碼方法，使得編碼后消息序列中的冗余度趨近于0.如果將這種編碼包含在信源中，也可以說是尋找某種能夠使信源冗余度趨近于0的編碼方法。冗余度成為衡量信源編碼效率的一個物理量，冗余度越低，編碼效率就越高。 實際離散信源熵的計算與近似表示過程： HHN(X)- 10 -圖3.4 實際信源的馬爾可夫建模由最大熵定理：H1(X)H0(X)=log2n，log2n=H0H1H2.Hm+1H信源符號的相關性越強，所提供的平均信息量就越少。冗余度是編碼理論中的一個重要的概念；在信源編碼中，人們總是在尋找壓縮信源冗余度的方法來提高傳輸的有效性；在信道編碼中，人們又總是采取注入冗余度的方法來提高傳輸的可靠性。信源的剩余度來自兩個方面，一是信源符號間的相關性，相關程度越大，符號間的依賴關系越長，信源的實際熵越小，另一