信息論講義第六講

信息論講義第六講1第一頁，共四十四頁，編輯于2023年，星期六第三章離散信源內(nèi)容提要

3.1信源的數(shù)學(xué)模型及其分類

3.2離散無記憶信源

3.3離散無記憶信源的擴(kuò)展信源

3.4離散平穩(wěn)信源

3.5馬爾可夫信源

2第二頁，共四十四頁，編輯于2023年，星期六④

N次擴(kuò)展信源熵的性質(zhì)(1) 條件熵隨N的增加是非遞增的(2) (3) 平均符號(hào)熵隨N的增加是非遞增的。(4) 極限熵存在，且

3.4離散平穩(wěn)信源（續(xù)）對(duì)于平穩(wěn)信源，極限熵是考慮了符號(hào)相關(guān)性的最小值3第三頁，共四十四頁，編輯于2023年，星期六3.4離散平穩(wěn)信源_性質(zhì)（續(xù)）⑴條件熵H

(XL|XL-1)隨L的增加是非遞增的條件較多的熵必小于或等于條件較少的熵，而條件熵必小于或等于無條件熵。4第四頁，共四十四頁，編輯于2023年，星期六(2)

HL(X)≥H(XL/XL-1)證明:HL(X)=H(X1X2…XL)/L=[H(X1)+H(X2|X1)+…+H(XL|X1X2…XL-1)]/L

≥[LH(XL|X1X2…XL-1)]/L=H(XL/XL-1)3.4離散平穩(wěn)信源_性質(zhì)（續(xù)）5第五頁，共四十四頁，編輯于2023年，星期六(3)

HL(X)是L的單調(diào)遞減函數(shù)證明:

LHL(X)=H(X1X2…XL)=H(X1X2…XL-1)+H(XL|X1X2…XL-1)=(L-1)HL-1(X)+H(XL|XL-1)≤(L-1)HL-1(X)+HL(X)

所以

HL(X)≤HL-1(X)3.4離散平穩(wěn)信源_性質(zhì)（續(xù)）推廣：H∞(X)≤…≤H2(X)≤H1(X)≤H0(X)

H0(X):等概率無記憶信源單個(gè)符號(hào)的熵，H1(X)為一般無記憶（不等概率）信源單個(gè)符號(hào)的熵H2(X)為兩個(gè)符號(hào)組成的序列平均符號(hào)熵，依次類推。6第六頁，共四十四頁，編輯于2023年，星期六3.4離散平穩(wěn)信源_性質(zhì)（續(xù)）7第七頁，共四十四頁，編輯于2023年，星期六(4)

H∞(X)=HL(X)=H(XL|X1X2…XL-1)證明：

HL+k(X)=[H(X1X2…XL-1)+

H(XL|X1X2…XL-1)+…+H(XL+k|X1X2…XL+k-1)]≤[H(X1X2…XL-1)+H(XL|X1X2…XL-1)+…+H(XL|X1X2…XL-1)]=H(X1X2…XL-1)+H(XL|X1X2…XL-1)3.4離散平穩(wěn)信源_性質(zhì)（續(xù)）8第八頁，共四十四頁，編輯于2023年，星期六說明:(i)

如何計(jì)算極限熵是一個(gè)十分困難的問題.(ii)

在實(shí)際應(yīng)用中常取有限L下的條件熵H(XL|XL-1)作為H∞(X)的近似值。(iii)

當(dāng)平穩(wěn)離散信源輸出序列的相關(guān)性隨著L的增加迅速減小時(shí)，其序列熵的增加量H(XL|XL-1)與相關(guān)性有關(guān)，相關(guān)性很弱，則H（XL|X1X2…XL-1）

H（XL|X2…XL-1）=H（XL-1|X1…XL-2），增加量不再變小，所以平均符號(hào)熵也幾乎不再減小。3.4離散平穩(wěn)信源_性質(zhì)（續(xù)）9第九頁，共四十四頁，編輯于2023年，星期六信源發(fā)出的符號(hào)只與前面的m個(gè)符號(hào)有關(guān)，而與更前面出現(xiàn)的符號(hào)無關(guān)。用概率意義表達(dá)為

p(xt|xt-1,xt-2,xt-3,……,xt-m,……)=p(xt|xt-1,xt-2,……xt-m)則根據(jù)（4）可得

=H(Xm+1|X1X2……Xm)=Hm+1(X)3.4離散平穩(wěn)信源_性質(zhì)（續(xù)）10第十頁，共四十四頁，編輯于2023年，星期六

3.5馬爾可夫信源3.5.1馬爾可夫過程3.5.2有限狀態(tài)馬爾可夫鏈3.5.3馬爾可夫信源11第十一頁，共四十四頁，編輯于2023年，星期六3.5.1馬爾可夫過程1.定義：

設(shè){X(t),tT}是隨機(jī)過程，任取0t1<t2<···<tn，tiT,i=1,2,···n,若t1,t2,···,tn時(shí)刻,取值分別為x1,x2,···,xn，并有注：

k=0時(shí)，稱為零階馬爾可夫過程。零階馬爾可夫過程=白噪聲過程。12第十二頁，共四十四頁，編輯于2023年，星期六3.5.2有限狀態(tài)馬爾可夫鏈

1.定義：

設(shè){xn,nN+

}為一隨機(jī)序列，時(shí)間參數(shù)集N+={0,1,2,…},其狀態(tài)空間S={S1,S2,…SJ}有限或可數(shù)，若對(duì)所有nN+

，有則稱,{xn,nN+

}為有限狀態(tài)一階馬爾可夫鏈。例：蛙跳13第十三頁，共四十四頁，編輯于2023年，星期六3.5.2有限狀態(tài)馬爾可夫鏈解釋：

(1)

S={S1,S2,…SJ}是狀態(tài)空間即xn所有可能取值

14第十四頁，共四十四頁，編輯于2023年，星期六3.5.2有限狀態(tài)馬爾可夫鏈(2)轉(zhuǎn)移概率

m時(shí)刻狀態(tài)Si，經(jīng)(n-m)步后轉(zhuǎn)移到狀態(tài)Sj的概率15第十五頁，共四十四頁，編輯于2023年，星期六3.5.2有限狀態(tài)馬爾可夫鏈

基本轉(zhuǎn)移概率（即一步轉(zhuǎn)移概率） 一步轉(zhuǎn)移概率pij(m,m+1)記成pij(m)16第十六頁，共四十四頁，編輯于2023年，星期六3.5.2有限狀態(tài)馬爾可夫鏈

k步轉(zhuǎn)移概率

k步轉(zhuǎn)移概率pij(m,m+k)記成p(k)ij(m)17第十七頁，共四十四頁，編輯于2023年，星期六3.5.2有限狀態(tài)馬爾可夫鏈

k步轉(zhuǎn)移矩陣

m時(shí)刻的k步轉(zhuǎn)移矩陣每行之和都為118第十八頁，共四十四頁，編輯于2023年，星期六states:sunny,cloudy,rainy.statetransitionmatrix:Theprobabilityoftheweathergiventhepreviousday'sweather.3.5.2有限狀態(tài)馬爾可夫鏈例：19第十九頁，共四十四頁，編輯于2023年，星期六3.5.2有限狀態(tài)馬爾可夫鏈(3)K階馬爾可夫鏈20第二十頁，共四十四頁，編輯于2023年，星期六3.5.2有限狀態(tài)馬爾可夫鏈(4)時(shí)齊馬爾可夫鏈（齊次馬爾可夫鏈） 若pij(m)=P(xm+1=Sj|xm=Si)于時(shí)刻m無關(guān)。即pij(m)=pij

，則稱為時(shí)齊馬爾可夫鏈（齊次馬爾可夫鏈）一步轉(zhuǎn)移矩陣P為21第二十一頁，共四十四頁，編輯于2023年，星期六例+TXrYr101qqpp3.5.2有限狀態(tài)馬爾可夫鏈22第二十二頁，共四十四頁，編輯于2023年，星期六輸入的碼Xr(r=1,2,…)是相互獨(dú)立的，取值0或1，且已知p(X=0)=p，p(X=1)=1-p=q，輸出的碼是Yr，顯然有

Y1=X1，Y2＝X2Y1…

其中表示模2加，那么Yr就是一個(gè)馬氏鏈，因Yr確定后，Yr+1分布只與Yr有關(guān)，與Yr-1、Yr-2…等無關(guān)，且知Yr序列的條件概率為3.5.2有限狀態(tài)馬爾可夫鏈23第二十三頁，共四十四頁，編輯于2023年，星期六p00=p(Y2=0|Y1=0)=p(X=0)=p

p01=p(Y2=1|Y1=0)=p(X=1)=q

p10=p(Y2=0|Y1=1)=p(X=1)=q

p11=p(Y2=1|Y1=1)=p(X=0)=p

說明:轉(zhuǎn)移矩陣為，它與r無關(guān)，因而是齊次的。3.5.2有限狀態(tài)馬爾可夫鏈24第二十四頁，共四十四頁，編輯于2023年，星期六3.5.2有限狀態(tài)馬爾可夫鏈2.切普曼—科爾莫哥洛夫方程（C-K方程）命題：設(shè)P(n)是時(shí)齊馬爾可夫鏈的n步轉(zhuǎn)移矩陣

(n1)，P=P(1)是基本轉(zhuǎn)移矩陣，則從而有元素注意：P(n)是經(jīng)過n步的轉(zhuǎn)移矩陣。25第二十五頁，共四十四頁，編輯于2023年，星期六3.5.2有限狀態(tài)馬爾可夫鏈3.初始分布定義：設(shè)P(X0=Si)=pi,且則稱它為馬爾可夫鏈的初始分布26第二十六頁，共四十四頁，編輯于2023年，星期六3.5.2有限狀態(tài)馬爾可夫鏈例120.90.20.10.8機(jī)床的狀態(tài)轉(zhuǎn)移已知本月機(jī)床的狀態(tài)向量

預(yù)測(cè)機(jī)床兩個(gè)月后的狀態(tài)27第二十七頁，共四十四頁，編輯于2023年，星期六3.5.2有限狀態(tài)馬爾可夫鏈兩個(gè)月后機(jī)床的狀態(tài)向量28第二十八頁，共四十四頁，編輯于2023年，星期六3.5.2有限狀態(tài)馬爾可夫鏈4.平穩(wěn)分布

定義：若齊次馬爾可夫鏈對(duì)所有i,j存在不依賴于i的極限 且滿足則稱其具有遍歷性，pj稱為平穩(wěn)分布29第二十九頁，共四十四頁，編輯于2023年，星期六3.5.2有限狀態(tài)馬爾可夫鏈

解釋：

當(dāng)n充分大時(shí)，可用常數(shù)pj作為pij(n)的近似值30第三十頁，共四十四頁，編輯于2023年，星期六3.5.2有限狀態(tài)馬爾可夫鏈31第三十一頁，共四十四頁，編輯于2023年，星期六3.5.2有限狀態(tài)馬爾可夫鏈(1)定理一：穩(wěn)態(tài)分布唯一性 設(shè)齊次馬爾可夫鏈轉(zhuǎn)移矩陣為P={pij},i,j=1,2,···,r,穩(wěn)態(tài)分布為Wj,j=1,2,···,r，則

a.

b.W={W1W2···Wr}是穩(wěn)態(tài)分布矢量，有W=WP c.當(dāng)初始分布W(0)=W時(shí)，對(duì)于所有的n有

W(n)=W d.W是唯一穩(wěn)態(tài)分布5.穩(wěn)態(tài)分布存在定理32第三十二頁，共四十四頁，編輯于2023年，星期六3.5.2有限狀態(tài)馬爾可夫鏈(2)定理二：穩(wěn)態(tài)分布存在 設(shè)P是齊次馬爾可夫鏈轉(zhuǎn)移矩陣，則 該鏈穩(wěn)態(tài)分布存在存在一個(gè)正整數(shù)N,使矩陣PN

中所有元素均大于零33第三十三頁，共四十四頁，編輯于2023年，星期六馬氏鏈可約性:

若對(duì)所有k，都有p(k)ij=0，就意味著一旦出現(xiàn)Si以后不可能到達(dá)Sj,也就是不能各態(tài)遍歷，或者狀態(tài)中應(yīng)把Sj取消，這樣就成為可約的了。馬氏鏈不可約性:

對(duì)任意一對(duì)i和j，都存在至少一個(gè)k使p(k)ij＞0，這就是說從Si開始，總有可能到達(dá)Sj.3.5.2有限狀態(tài)馬爾可夫鏈34第三十四頁，共四十四頁，編輯于2023年，星期六香農(nóng)線圖

S1S3S21/21/21/21/21S4S51/21/2可約馬氏鏈1/21/23.5.2有限狀態(tài)馬爾可夫鏈35第三十五頁，共四十四頁，編輯于2023年，星期六注意:

(1)S1,S2,S3是三種狀態(tài)，箭頭是指從一個(gè)狀態(tài)轉(zhuǎn)移到另一個(gè)狀態(tài)，旁邊的數(shù)字代表轉(zhuǎn)移概率。這就是香農(nóng)提出的馬爾可夫狀態(tài)圖，也叫香農(nóng)線圖。

(2)由狀態(tài)S3轉(zhuǎn)移到S1的轉(zhuǎn)移概率p(k)31=0，因?yàn)橐贿M(jìn)人狀態(tài)S3就一直繼續(xù)下去，而不會(huì)再轉(zhuǎn)移到其他狀態(tài)。P(k)41=0也是明顯的，因S4和S1之間沒有連接箭頭，因此這種鏈就是可約的。3.5.2有限狀態(tài)馬爾可夫鏈36第三十六頁，共四十四頁，編輯于2023年，星期六馬氏鏈周期性

非周期性，就是所有p(k)ii＞0的k中沒有比1大的公因子。

S1S4S21/21/2周期性馬氏鏈S31/21/21/21/21/21/23.5.2有限狀態(tài)馬爾可夫鏈37第三十七頁，共四十四頁，編輯于2023年，星期六注意:(1)上圖周期為2.因?yàn)閺腟1出發(fā)再回到S1所需的步數(shù)必為2，4，6，…，.(2)

p(n)