第3講信源模型資料

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

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

3、各隨機(jī)變量的概率分布和聯(lián)合概率分布進(jìn)行描述。一維分布：對(duì)于R(x)二PrXt二x這是隨機(jī)序列在時(shí)刻 t處于狀態(tài)x的概率。二維分布：對(duì)于任何狀態(tài) x1與x2，隨機(jī)序列從t時(shí)刻開始所經(jīng)歷的狀態(tài)序列為x1x2的概率記為p (xix2)= Pr XtXt 1 二 X1X2 = Pr Xt = Xi, Xt 1 二 x2則函數(shù)Pt稱為該隨機(jī)序列在 t時(shí)刻的二維分布。n維分布：t時(shí)刻的n維分布定義為，對(duì)于任何狀態(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時(shí)刻開始所連續(xù)經(jīng)歷的狀態(tài)為XiXjljXn。記號(hào)：我們將隨機(jī)序列 X在t時(shí)刻的n維分布也記為P(XtJHXtn)初始分布：對(duì)于任何正整數(shù)n,初始時(shí)刻的n維分布p1(xix2hlxn)稱為初始分布。高維分布蘊(yùn)含低維分布由t時(shí)刻的n維分布可以確定t時(shí)刻的(n-i)維分布，即Pt(XiX2l|XnJ 八 Pt(X|Xn)Xn因此，由t時(shí)刻的n維分布可以確定t時(shí)刻的所有低維分布。隨機(jī)序列的平穩(wěn)性 定義1.3若隨機(jī)序列各時(shí)刻的n維分布p相同，即對(duì)于任何n維狀態(tài)序列XoXjllXn/和任 何時(shí)刻t,有Pt(X xlll X)= Pl( XIX nX則稱該隨機(jī)序列是 n維平穩(wěn)的。

5、若對(duì)于任何正整數(shù) n，隨機(jī)序列都是n維平穩(wěn)的，則稱該隨 機(jī)序列為 平穩(wěn)的(stationary)。平穩(wěn)隨機(jī)序列的n維分布記為p(XI Xn)或者p(x川|xn)。定義1.4若隨機(jī)序列中各隨機(jī)變量是相互獨(dú)立并且具有相同的概率分布，則稱該隨機(jī)序列為獨(dú)立同分布的，記為i.i.d.。獨(dú)立同分布序列是最簡(jiǎn)單的一類隨機(jī)序列。獨(dú)立同分布序列是平穩(wěn)的：(1 )由同分布性可得，對(duì)于任何時(shí)刻t和任何狀態(tài)X，有Pt (x)二 Pt 1 (X)等價(jià)地，Pt(x)二 p1(x)(2)由相互獨(dú)立性可得，對(duì)于任何時(shí)刻和任何狀態(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. 波形信源與離散信源波形信源 使用波形信號(hào)，例如電磁波的信號(hào)，調(diào)頻電磁波的信號(hào)是其不同的頻率， 調(diào)幅電磁波的信號(hào)是不同的振幅。這些信號(hào)是在一段連續(xù)時(shí)間內(nèi)高低連續(xù)變化的物理量，用以模擬聲音、圖像的變化，故也稱為模擬信號(hào)。因此，波形信源的可以用時(shí)間參數(shù)連續(xù)的隨機(jī)過程進(jìn)行建模和描述。波形信源的模型：波形信源可以用連續(xù)參數(shù)的隨機(jī)過程X(t),t. T表示，其中參數(shù)集合T =(-二，：)或者0,：)，隨機(jī)變量X(t)表示波形信源在時(shí)刻t所輸出的信號(hào)(例如，一個(gè)振幅或者一個(gè)頻率)。

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

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

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

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

11、科夫鏈的一階條件概率P(Xt!|XJ 不隨時(shí)間t改變，則稱該馬爾科夫鏈為時(shí)齊的(homogeneous),也稱為 時(shí)不變的 (time-invariant)。注：與平穩(wěn)性相比較，時(shí)齊性的要求較弱。前者蘊(yùn)含后者，后者并不蘊(yùn)含前者。約定：在以后設(shè)計(jì)馬爾科夫鏈的例題習(xí)題中，若無(wú)特別聲明，就默認(rèn)其中馬爾科夫鏈為時(shí)齊的。時(shí)齊馬爾科夫鏈有兩種表征:（1 ）轉(zhuǎn)移矩陣：馬爾科夫鏈的所有一階條件概率p（Xt1|Xt）構(gòu)成的矩陣稱為該馬爾科夫鏈的轉(zhuǎn)移矩陣。轉(zhuǎn)移矩陣是一個(gè)方陣， 記錄時(shí)齊馬爾科夫鏈各狀態(tài)之間的轉(zhuǎn)移概率。下列矩陣共有兩行，表明時(shí)齊馬爾科夫鏈共有2個(gè)狀態(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)移圖： 上述矩陣表示的時(shí)齊馬爾科夫鏈也可直觀地表示為如下狀態(tài)轉(zhuǎn)移圖，其 中兩個(gè)結(jié)點(diǎn)分別表示兩個(gè)不同狀態(tài)，有向邊稱為狀態(tài)間的轉(zhuǎn)移，有向邊上的標(biāo)記稱為轉(zhuǎn)移概率。定理3.3令P為時(shí)齊馬爾科夫鏈 X的轉(zhuǎn)移矩陣，則t+n時(shí)刻的概率分布為P（X n戶 P（X）nP其中概率分布p（Xt）都表示為行向量。根據(jù)上述定理，我們稱 Pn為n-步轉(zhuǎn)移矩陣。命題若時(shí)齊馬爾科夫鏈?zhǔn)且痪S平穩(wěn)的，則它是任意維平穩(wěn)的。證明：請(qǐng)讀者完成。證畢一些特殊的初始分布會(huì)使得時(shí)齊馬爾科夫鏈具有平穩(wěn)性，這就是所謂平穩(wěn)分布。定義3.4令時(shí)齊馬爾科夫鏈

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

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

15、）若時(shí)齊馬爾科夫鏈 P是正則的，即存在正整數(shù)n,使得n-步轉(zhuǎn)移矩陣Pn不含0項(xiàng)，則P是漸近平穩(wěn)的，并且其極限分布是唯一的平穩(wěn)分布。注：n-步轉(zhuǎn)移矩陣Pn不含0項(xiàng)的含義是，從任何狀態(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在任何時(shí)刻t的t階條件概率等于 m階條件概率（其中 mt）, 即卩 則稱該隨機(jī)序列具有 m-階馬爾科夫性，并稱該序列為m階馬爾科夫序列m階馬爾科夫序列所表示的離散信源稱為 m階馬爾科夫信源。m階馬爾科夫性表明隨機(jī)序列具有有限的記憶性，我們稱其記憶長(zhǎng)度為m+1.根據(jù)定義，馬爾科夫鏈?zhǔn)?階馬爾科夫序列，其記憶長(zhǎng)度等于2。漢語(yǔ)、英語(yǔ)等自然語(yǔ)言都具有這種有限記憶性。 在漢語(yǔ)文章中，一個(gè)漢字僅與前幾個(gè)漢 字的關(guān)系比較密切，而與更前面的漢字的關(guān)系較弱，可以忽略不計(jì)。根據(jù)實(shí)際需要，我們可以構(gòu)造漢語(yǔ)的 1-階馬爾科夫模型、2-階馬爾科夫模型，等等。 模型的階數(shù)越大，則該模型的條件概率矩陣越龐大，

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

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

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

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