第3講信源模型資料

1、第3講信源模型信源（in formation source ）,也稱消息源，是通信系統(tǒng)中發(fā)送消息的一方。信源所產(chǎn)生或者輸出的消息（message）是一個符號序列。任何產(chǎn)生符號序列的事物都可視為信源。報社、廣播電臺是信源；一個的人表情、行為是信源；我們所說的漢語是一個信源；一本英文小說也構(gòu)成一個信源； 息。水面波紋、天空的云等等萬事萬物都是信源，都在傳遞著各自的信這一講我們介紹離散信源的幾種基本的和常用的模型。1. 隨機(jī)過程隨機(jī)過程是一個帶時間參數(shù)的隨機(jī)變量，其取值的統(tǒng)計特性可隨時間不斷變化，用以機(jī)變量描述狀態(tài)不斷變化的物理系統(tǒng)或者隨機(jī)現(xiàn)象。定義1.1隨機(jī)過程 是定義在同一個樣本空間上一族隨機(jī)變

2、量X（t）,tT，其中t為時間參數(shù)，T是參數(shù)集合。對于任何t T ,隨機(jī)變量X（t）的值稱為隨機(jī)過程在時刻t的狀態(tài)。為表達(dá)方便，可將隨機(jī)過程 x（t）,r T簡記為x或x（t）。定義1.2當(dāng)隨機(jī)過程的參數(shù)集合為實數(shù)區(qū)間（-：，：）或者0,：）時，該隨機(jī)過程稱為時間連續(xù)的。當(dāng)隨機(jī)過程的參數(shù)集合為整數(shù)集或者非負(fù)整數(shù)集時，該隨機(jī)過程稱為時間離散的。 時間離散的隨機(jī)過程稱為 隨機(jī)序列。若X為隨機(jī)序列，則X在時刻t的狀態(tài)X（t） 一般記為Xn。實例：熱噪聲電壓的樣本函數(shù)隨機(jī)過程的更多知識在后面需要的這里我們主要學(xué)習(xí)關(guān)于隨機(jī)序列的基本概念和性質(zhì), 地方再作介紹。隨機(jī)序列的概率分布 隨機(jī)序列的統(tǒng)計特性用其中

3、各隨機(jī)變量的概率分布和聯(lián)合概率分布進(jìn)行描述。一維分布：對于R(x)二PrXt二x這是隨機(jī)序列在時刻 t處于狀態(tài)x的概率。二維分布：對于任何狀態(tài) x1與x2，隨機(jī)序列從t時刻開始所經(jīng)歷的狀態(tài)序列為x1x2的概率記為p (xix2)= Pr XtXt 1 二 X1X2 = Pr Xt = Xi, Xt 1 二 x2則函數(shù)Pt稱為該隨機(jī)序列在 t時刻的二維分布。n維分布：t時刻的n維分布定義為，對于任何狀態(tài)序列x| xn，Pt(NX2l“Xn)二 PrXt1 Xt 2 |Xt n = XiXj|Xn=PrXt i 二 Xi，Xt 迄二 X2，|i,Xt “ = Xn其中事件Xt iXt j|Xt X

4、iXjHXn表示隨機(jī)序列從t時刻開始所連續(xù)經(jīng)歷的狀態(tài)為XiXjljXn。記號：我們將隨機(jī)序列 X在t時刻的n維分布也記為P(XtJHXtn)初始分布：對于任何正整數(shù)n,初始時刻的n維分布p1(xix2hlxn)稱為初始分布。高維分布蘊(yùn)含低維分布由t時刻的n維分布可以確定t時刻的(n-i)維分布，即Pt(XiX2l|XnJ 八 Pt(X|Xn)Xn因此，由t時刻的n維分布可以確定t時刻的所有低維分布。隨機(jī)序列的平穩(wěn)性 定義1.3若隨機(jī)序列各時刻的n維分布p相同，即對于任何n維狀態(tài)序列XoXjllXn/和任 何時刻t,有Pt(X xlll X)= Pl( XIX nX則稱該隨機(jī)序列是 n維平穩(wěn)的。

5、若對于任何正整數(shù) n，隨機(jī)序列都是n維平穩(wěn)的，則稱該隨 機(jī)序列為 平穩(wěn)的(stationary)。平穩(wěn)隨機(jī)序列的n維分布記為p(XI Xn)或者p(x川|xn)。定義1.4若隨機(jī)序列中各隨機(jī)變量是相互獨立并且具有相同的概率分布，則稱該隨機(jī)序列為獨立同分布的，記為i.i.d.。獨立同分布序列是最簡單的一類隨機(jī)序列。獨立同分布序列是平穩(wěn)的：(1 )由同分布性可得，對于任何時刻t和任何狀態(tài)X，有Pt (x)二 Pt 1 (X)等價地，Pt(x)二 p1(x)(2)由相互獨立性可得，對于任何時刻和任何狀態(tài)序列X1X2H!xn，有Pt(XiX2 IllXn) =Pt(Xi)Pt 1(X2)III P n

6、(Xn)再由(1)可得，Pt(X1X2 1嘆)二 R(X1)P1(X2)Hg(Xn)從而有&必2川人)二P 1&必2|人)2. 波形信源與離散信源波形信源 使用波形信號，例如電磁波的信號，調(diào)頻電磁波的信號是其不同的頻率， 調(diào)幅電磁波的信號是不同的振幅。這些信號是在一段連續(xù)時間內(nèi)高低連續(xù)變化的物理量，用以模擬聲音、圖像的變化，故也稱為模擬信號。因此，波形信源的可以用時間參數(shù)連續(xù)的隨機(jī)過程進(jìn)行建模和描述。波形信源的模型：波形信源可以用連續(xù)參數(shù)的隨機(jī)過程X(t),t. T表示，其中參數(shù)集合T =(-二，：)或者0,：)，隨機(jī)變量X(t)表示波形信源在時刻t所輸出的信號(例如，一個振幅或者一個頻率)。

7、波形信源在任何一段時間內(nèi)輸出的波形信號稱為該信源的消息，它是隨機(jī)過程限制在該段時間上的樣本函數(shù)。形信源的離散化：摸數(shù)轉(zhuǎn)換(A/D transformation)將連續(xù)的模擬量通過取樣和量化兩個步驟轉(zhuǎn)換為離散的數(shù)字量。例如，對一幅圖像掃描，將它轉(zhuǎn)換為像素陣列，其中每個像素由色彩和亮度組成，再對每個像素進(jìn)行量化，即從指定的數(shù)值列表中選取最接近像素本身值的整數(shù)值作為像素值的近似表示。這樣原來的圖像就轉(zhuǎn)換為數(shù)字圖像。波形信源產(chǎn)生的波形信號經(jīng)過離散化后變?yōu)閿?shù)字信號，從而形成離散信源。離散信源產(chǎn)生的符號是離散的，例如漢字、字母都是離散符號，所以漢語和英語是離散信源。 數(shù)字線路中傳遞的數(shù)字信號，所以發(fā)送這些

8、數(shù)字信號的設(shè)備是離散信源。離散符號可以編碼為等長的整數(shù)，例如ASCII碼，漢字國家標(biāo)準(zhǔn)碼，等等。因此，我們將離散信源的符號統(tǒng)一視為整數(shù)。若某離散信源共有n個符號，則該離散信源的符號集記為0,1丄，n-1離散信源可以用隨機(jī)序列進(jìn)行建模和描述。離散信源的數(shù)學(xué)模型：具有離散時間參數(shù)和離散狀態(tài)的隨機(jī)序列。X(t),t U其中隨機(jī)變量Xt表示離散信源在時刻t所輸出的符號，即狀態(tài)集0,1,111, n-1中任意整數(shù)。該隨機(jī)序列在一段時間內(nèi)產(chǎn)生符號序列就是離散信源的消息。最簡單的離散信源是離散無記憶信源，其定義如下：定義2.1獨立同分布序列所表示的離散信源稱為離散無記憶信源，記為DMS。這種信源的符號序列是

9、獨立同分布的，即當(dāng)前符號不影響下一個符號的概率分布，并且所有符號的出現(xiàn)概率在各時刻都是相同的。當(dāng)我們不考慮信源符號之間的統(tǒng)計關(guān)系時，就可將它粗略地近似為無記憶信源。 無損壓縮編碼的目標(biāo)就是將信源改造為均勻分布的無記憶信源。離散無記憶信源可以表征為一個其符號集的概率分布：X01n-1PxPoP1Pn定義2.2平穩(wěn)隨機(jī)序列所表示的離散信源稱為離散平穩(wěn)信源。平穩(wěn)信源特點是，它在任何時刻產(chǎn)生同一條消息的概率是相同的。當(dāng)我們研究一個信源時，一般假設(shè)它是平穩(wěn)的。 平穩(wěn)性大大方便了我們的統(tǒng)計工作，例如，為了估計一個 3-漢字組合的概率，我們可以統(tǒng)計該組合在書本中任何位置上的出現(xiàn)。當(dāng)然現(xiàn)實的信源可能漸近平穩(wěn)的

10、。即在初始階段可能并不具有平穩(wěn)性，但隨著時間的推移，變得越來越平穩(wěn)。因此，在統(tǒng)計時可以回避不平穩(wěn)的初始階段。例如，統(tǒng)計一本書中3-漢字組合的出現(xiàn)次數(shù)時，可以跳過開頭的幾行或者幾段文字。3. 時齊馬爾科夫鏈離散信源常用的模型是時齊馬爾科夫鏈，其定義如下。定義3.1若隨機(jī)序列X在任何時刻t的t階條件概率等于1階條件概率，即p(Xt1|XJ|Xtp(Xt1|Xt)則稱該隨機(jī)序列滿足 馬爾科夫性(Markov property)，稱為馬爾科夫序列。馬爾科夫性也稱為無后效性。這個性質(zhì)表明：在給定當(dāng)前狀態(tài)的條件下，下一狀態(tài)與以前所有狀態(tài)是相互獨立的。定義3.2狀態(tài)離散的馬爾科夫序列稱為馬爾科夫鏈。 若馬爾

11、科夫鏈的一階條件概率P(Xt!|XJ 不隨時間t改變，則稱該馬爾科夫鏈為時齊的(homogeneous),也稱為 時不變的 (time-invariant)。注：與平穩(wěn)性相比較，時齊性的要求較弱。前者蘊(yùn)含后者，后者并不蘊(yùn)含前者。約定：在以后設(shè)計馬爾科夫鏈的例題習(xí)題中，若無特別聲明，就默認(rèn)其中馬爾科夫鏈為時齊的。時齊馬爾科夫鏈有兩種表征:（1 ）轉(zhuǎn)移矩陣：馬爾科夫鏈的所有一階條件概率p（Xt1|Xt）構(gòu)成的矩陣稱為該馬爾科夫鏈的轉(zhuǎn)移矩陣。轉(zhuǎn)移矩陣是一個方陣， 記錄時齊馬爾科夫鏈各狀態(tài)之間的轉(zhuǎn)移概率。下列矩陣共有兩行，表明時齊馬爾科夫鏈共有2個狀態(tài)，姑且稱為狀態(tài) 1和狀態(tài)2。矩陣第1行是狀態(tài)1轉(zhuǎn)移

12、到狀態(tài)2的概率分布，第o o_.10.30.92行是狀態(tài)2轉(zhuǎn)移到狀態(tài)1的概率分布。（2）狀態(tài)轉(zhuǎn)移圖： 上述矩陣表示的時齊馬爾科夫鏈也可直觀地表示為如下狀態(tài)轉(zhuǎn)移圖，其 中兩個結(jié)點分別表示兩個不同狀態(tài)，有向邊稱為狀態(tài)間的轉(zhuǎn)移，有向邊上的標(biāo)記稱為轉(zhuǎn)移概率。定理3.3令P為時齊馬爾科夫鏈 X的轉(zhuǎn)移矩陣，則t+n時刻的概率分布為P（X n戶 P（X）nP其中概率分布p（Xt）都表示為行向量。根據(jù)上述定理，我們稱 Pn為n-步轉(zhuǎn)移矩陣。命題若時齊馬爾科夫鏈?zhǔn)且痪S平穩(wěn)的，則它是任意維平穩(wěn)的。證明：請讀者完成。證畢一些特殊的初始分布會使得時齊馬爾科夫鏈具有平穩(wěn)性，這就是所謂平穩(wěn)分布。定義3.4令時齊馬爾科夫鏈

13、（的轉(zhuǎn)移概率矩陣）為P,若存在分布二，使得二P =理，則稱二為平穩(wěn)分布?？梢钥闯觯?dāng)馬爾科夫鏈的初始分布為平穩(wěn)分布，則該馬爾科夫鏈?zhǔn)瞧椒€(wěn)的。時齊馬爾科夫鏈的漸近平穩(wěn)性定義3.5 （漸近平穩(wěn)性） 隨機(jī)序列X稱為漸近平穩(wěn)的，當(dāng)且僅當(dāng)其各維分布存在極限分布, 即對于任何n _ 1，存在極限lm Pt（Xi 川 Xn）二 PdJIlXn）t.0其中p（xji|xn）稱為n-維極限分布。實際意義：隨著時間推移，隨機(jī)序列的統(tǒng)計特性越來越近似平穩(wěn)序列。命題：時齊馬爾科夫鏈?zhǔn)菨u近平穩(wěn)的，當(dāng)且僅當(dāng)它存在一維極限分布。命題:極限分布一定是平穩(wěn)分布，而反之未必成立。時齊馬爾科夫鏈存在極限分布的充分條件：（1）不可約

14、性：若時齊馬爾科夫鏈的所有狀態(tài)是相互連通的，則稱該馬爾科夫鏈為不可約 的（irreducible）。（2） 非周期性：從狀態(tài)i出發(fā)再回到i的所有循環(huán)路徑長度的最大公約數(shù)稱為狀態(tài)i的周期。 周期等于1的狀態(tài)稱為非周期的（asperiod）。若時齊馬爾科夫鏈的所有狀態(tài)都是非周期的， 則稱該馬爾科夫鏈為非周期的。定理3.6 （時齊馬爾科夫鏈的漸近平穩(wěn)性）若時齊馬爾科夫鏈 P是不可約的和非周期的，則P是漸近平穩(wěn)的，并且其極限分布是唯一的平穩(wěn)分布。因此，若時齊馬爾科夫鏈P具有不可約性和非周期性，則其極限分布n是下列方程的解：7： P = :等價地，二（P _ E） =0定理3.7 （正則性蘊(yùn)含漸近平穩(wěn)性

15、）若時齊馬爾科夫鏈 P是正則的，即存在正整數(shù)n,使得n-步轉(zhuǎn)移矩陣Pn不含0項，則P是漸近平穩(wěn)的，并且其極限分布是唯一的平穩(wěn)分布。注：n-步轉(zhuǎn)移矩陣Pn不含0項的含義是，從任何狀態(tài)出發(fā)經(jīng)過n-步轉(zhuǎn)移都可達(dá)到其它任何狀態(tài)。練習(xí)判斷下列馬爾科夫鏈?zhǔn)欠翊嬖跇O限分布。若存在試求出該極限分布。練習(xí)設(shè)任意相繼的兩天中，雨天轉(zhuǎn)晴天的概率為1/3,晴天轉(zhuǎn)雨天的概率為1/2，任一天晴或者雨是互為逆事件。以0和1分別表示晴天和雨天這兩種狀態(tài)，Xn表示第n天的狀態(tài)（0或1 ）。試寫出馬氏鏈Xn, n_1的轉(zhuǎn)移矩陣。又若已知 5月1日為晴天，問5月3日為晴天，5月4日為雨天的概率各等于多少？4. 馬爾科夫信源定義4.

16、1若隨機(jī)序列X在任何時刻t的t階條件概率等于 m階條件概率（其中 mt）, 即卩 則稱該隨機(jī)序列具有 m-階馬爾科夫性，并稱該序列為m階馬爾科夫序列m階馬爾科夫序列所表示的離散信源稱為 m階馬爾科夫信源。m階馬爾科夫性表明隨機(jī)序列具有有限的記憶性，我們稱其記憶長度為m+1.根據(jù)定義，馬爾科夫鏈?zhǔn)?階馬爾科夫序列，其記憶長度等于2。漢語、英語等自然語言都具有這種有限記憶性。 在漢語文章中，一個漢字僅與前幾個漢 字的關(guān)系比較密切，而與更前面的漢字的關(guān)系較弱，可以忽略不計。根據(jù)實際需要，我們可以構(gòu)造漢語的 1-階馬爾科夫模型、2-階馬爾科夫模型，等等。 模型的階數(shù)越大，則該模型的條件概率矩陣越龐大，

17、 從而構(gòu)造和應(yīng)用該條件概率矩陣所需的 統(tǒng)計和計算工作量越大。最常用的是 3-單詞模型。5. 構(gòu)造英語的馬爾科夫模型在研究實際信源時，可根據(jù)實際需要，選擇合適的信源模型。我們介紹英語信源模型的構(gòu)造方法。這個方法是香農(nóng)在 1948年的論文 A mathematical theory of communication 中給 出的。它通過統(tǒng)計一本書中英文字符間的條件概率而構(gòu)造英文的幾種馬爾科夫模型。（本教材此處內(nèi)容參考自 Cover與Thomas的教材信息論基礎(chǔ)第 2版第96頁。）首先，確定英文字母表：為簡化統(tǒng)計和計算的工作量，假設(shè)英文字母表僅包括27個符號，即26個字母和常見的空格符號，忽略標(biāo)點和大

18、小寫。討論：英語符號簡化為27個符號對于估計其熵率的影響大嗎？ 其次，任意選取一本足夠厚重的英文著作。按下列方法統(tǒng)計條件概率。無記憶模型：這個模型假設(shè)英文是無記憶信源。更加該假設(shè)，做如下統(tǒng)計工作。選擇一本英文書，統(tǒng)計出其中各符號出現(xiàn)頻率p（x），構(gòu)成英文字符的一維分布列，其形式如下：Xabz空格PxP(a)P(b)p(z)p（空格）一階馬爾科夫模型：從所選的英文書中， 統(tǒng)計出英語符號的一階條件概率，構(gòu)成一個轉(zhuǎn)移矩陣，這個轉(zhuǎn)移矩陣就是英文的一階馬爾科夫模型。統(tǒng)計方法如下。第1步，隨機(jī)地打開書本中的某頁，并隨機(jī)地選定一個符號，作為該序列的第1個符號。第2步，隨機(jī)地打開某頁，找到當(dāng)前選定的符號X，將

19、緊隨其后的符號選定為下一個符號。第3步，重復(fù)第2步，直到所構(gòu)造的序列足夠長時為止。這種隨機(jī)跳躍式的統(tǒng)計方法可以構(gòu)造出具有一階馬爾科夫性的符號序列。只要所構(gòu)造的符號序列足夠長，則足以代表英語字符序列的一階馬爾科夫性。第4步從所構(gòu)造的符號序列中統(tǒng)計出相鄰符號間的條件概率，構(gòu)成一階馬爾科夫模型的轉(zhuǎn) 移矩陣。m階馬爾科夫模型：類似地，從最初隨機(jī)選定的連續(xù) m個符號開始，隨機(jī)跳躍若干行符號后,找該符號組的第1次出現(xiàn)，從而將該符號組之后的第1個符號選定下一個符號。依次類推,構(gòu)造出一個足夠長的符號序列。該序列可以反映英語的m階馬爾科夫性。從該序列中統(tǒng)計出所有m分組與緊跟其后的下一個符號之間的條件概率。 是英

20、語的m階馬爾科夫模型。所有的這些概率構(gòu)成一個矩陣，這就上述構(gòu)造的是以英文字符為符號的馬爾科夫模型，稱為馬爾科夫字符模型。香農(nóng)在1948年的文章中還介紹了以單詞為符號的馬爾科夫模型,稱為馬爾科夫單詞模型，其構(gòu)造方法與上述介紹的方法類似。英語的馬爾科夫模型中最常用的是三單詞模型，即2階馬爾科夫單詞模型，在語音識別系 統(tǒng)中起到關(guān)鍵的作用，獲得了驚人的效果。6. 隱馬爾可夫鏈對于m-階馬爾科夫信源，我們將信源符號的所有m-分組視為新的信源符號，從而可將該信源轉(zhuǎn)化為1-階馬爾科夫信源，即馬爾科夫鏈。令X =X“X2丨H為m-階馬爾科夫序列。令Y=Y Y III，其中3X2X3 Xm1Yn 二 XnXn 川 |Xn