第二章-信息論基本概念(3)

1、3. 離散有記憶信源馬爾可夫信源離散有記憶信源馬爾可夫信源馬爾可夫信源馬爾可夫信源非平穩(wěn)離散信源中的一類特殊信源。非平穩(wěn)離散信源中的一類特殊信源。 是由信源發(fā)出的各個符號之間的關(guān)連性構(gòu)成一個整體消息。是由信源發(fā)出的各個符號之間的關(guān)連性構(gòu)成一個整體消息。這種關(guān)連性用符號的這種關(guān)連性用符號的轉(zhuǎn)移概率（條件概率）轉(zhuǎn)移概率（條件概率）表示：表示： 如：如：BOY P(B) P(O|B) P(Y|BO) 若馬爾可夫信源發(fā)出每個符號都取決于它與前面的若馬爾可夫信源發(fā)出每個符號都取決于它與前面的K個符個符號之間的關(guān)連性，也就是該信源是以轉(zhuǎn)移概率號之間的關(guān)連性，也就是該信源是以轉(zhuǎn)移概率P(Xi|Xi-k, X

2、i-k+1, , Xi-1)發(fā)出每個符號，這種信源稱作發(fā)出每個符號，這種信源稱作K階馬爾可夫信源階馬爾可夫信源。馬爾可夫過程：馬爾可夫過程： 對于任意的大于對于任意的大于2 2的自然數(shù)的自然數(shù)n n，在連續(xù)的時(shí)間，在連續(xù)的時(shí)間T T軸上有軸上有n n個不同時(shí)個不同時(shí)刻，刻，t1，t2，tn滿足，在滿足，在t tn時(shí)刻的隨機(jī)變量時(shí)刻的隨機(jī)變量Xn與其前面（與其前面（n n1 1）個時(shí)刻的隨機(jī)變量個時(shí)刻的隨機(jī)變量X1，X2，Xn1的關(guān)系可用它們之間的條件的關(guān)系可用它們之間的條件概率密度函數(shù)來表示，如果滿足下式：概率密度函數(shù)來表示，如果滿足下式： p( (Xn ，tn| Xn 1 ， tn1 ，Xn

3、2， tn2，X1，t1) ) p( (Xn ，tn| Xn 1，tn 1) ) 則這種隨機(jī)過程稱為則這種隨機(jī)過程稱為單純馬爾可夫過程單純馬爾可夫過程（一階馬爾可夫過程一階馬爾可夫過程） K K階馬爾可夫過程階馬爾可夫過程的特征為：的特征為： p( (Xn ，tn| Xn 1 ， tn1 ，Xn2， tn2，X1，t1) ) p( (Xn ，tn| Xn1，tn1 ，Xn2， tn2，Xnk，tnk) )預(yù)備知識預(yù)備知識:馬爾可夫過程、馬爾可夫鏈馬爾可夫過程、馬爾可夫鏈馬爾可夫鏈：馬爾可夫鏈： 當(dāng)馬爾可夫過程的隨機(jī)變量幅度和時(shí)間參數(shù)均取離散值時(shí)，當(dāng)馬爾可夫過程的隨機(jī)變量幅度和時(shí)間參數(shù)均取離散值

4、時(shí)，就稱作馬爾可夫鏈。就稱作馬爾可夫鏈。 設(shè)隨機(jī)過程在時(shí)間域上設(shè)隨機(jī)過程在時(shí)間域上T T t1，t2， ，tk1，tk，tn1，tn 的的n n個離散時(shí)刻上的狀態(tài)個離散時(shí)刻上的狀態(tài)Xk ( (k1 1，2 2，3 3， ，n)n)都是都是離散型的隨機(jī)變量，并且有離散型的隨機(jī)變量，并且有M M個不同的取值個不同的取值S S1 1,S,S2 2, ,S,SM M，這，這M M個取個取值便構(gòu)成一個狀態(tài)空間值便構(gòu)成一個狀態(tài)空間S S，S SSS1 1,S,S2 2, ,S,SM M.在在n n個時(shí)刻上的個時(shí)刻上的n n個個狀態(tài)構(gòu)成一個隨機(jī)序列（狀態(tài)構(gòu)成一個隨機(jī)序列（X1，X2， ，Xk1，Xk，Xn1

5、，Xn）對于這個隨機(jī)序列，若有：對于這個隨機(jī)序列，若有：則此序列稱為則此序列稱為單純馬爾可夫鏈（一階馬爾可夫鏈）。單純馬爾可夫鏈（一階馬爾可夫鏈）。一階馬爾可夫鏈在一階馬爾可夫鏈在tn時(shí)刻的取值時(shí)刻的取值Xn S Sin的概率僅與前一狀態(tài)的概率僅與前一狀態(tài)Xn-1有關(guān)，與其它時(shí)刻狀態(tài)無關(guān)，它的記憶長度為兩個時(shí)刻。若與它有關(guān)，與其它時(shí)刻狀態(tài)無關(guān)，它的記憶長度為兩個時(shí)刻。若與它前面前面K K個時(shí)刻個時(shí)刻tn-1，tn-2， ，tn-k有關(guān)，則為有關(guān)，則為K K階馬爾可夫鏈，它階馬爾可夫鏈，它的記憶長度為（的記憶長度為（K+1K+1）個時(shí)刻。）個時(shí)刻。 設(shè)一階馬爾可夫鏈在時(shí)刻設(shè)一階馬爾可夫鏈在時(shí)刻t

6、k1隨機(jī)序列的取值隨機(jī)序列的取值Xk1S Si，而在，而在下一時(shí)刻下一時(shí)刻tk，隨機(jī)序列的取值，隨機(jī)序列的取值XkS Sj，則條件概率為，則條件概率為: : P(j|i P(j|i) )P(P(XkS Sj| |Xk1S Si ) ) 因?yàn)橐驗(yàn)镻(j|iP(j|i) )僅取決于狀態(tài)僅取決于狀態(tài)S Sj和和S Si ，因此稱，因此稱P(j|iP(j|i) )為由狀態(tài)為由狀態(tài)S Si向向S Sj的轉(zhuǎn)移概率。的轉(zhuǎn)移概率。111111(|,.,)(|)nnnnniniininip xSxSxSp xSxS對于具有對于具有M M個不同的狀態(tài)空間，個不同的狀態(tài)空間，M M2 2個轉(zhuǎn)移概率可排成一轉(zhuǎn)移矩陣：

7、個轉(zhuǎn)移概率可排成一轉(zhuǎn)移矩陣： 每行元素代表同一起始狀態(tài)到每行元素代表同一起始狀態(tài)到M M個不同終止?fàn)顟B(tài)的轉(zhuǎn)移概率；個不同終止?fàn)顟B(tài)的轉(zhuǎn)移概率； 每列元素代表每列元素代表M M個不同起始狀態(tài)到同一終止?fàn)顟B(tài)的轉(zhuǎn)移概率；個不同起始狀態(tài)到同一終止?fàn)顟B(tài)的轉(zhuǎn)移概率； 顯然有：顯然有： P(j|iP(j|i) )1 1 （i=1,2, ,Mi=1,2, ,M） K K階馬爾可夫鏈每個狀態(tài)由階馬爾可夫鏈每個狀態(tài)由K K個符號組成個符號組成。若信源符號有。若信源符號有D D種，種，則狀態(tài)數(shù)目則狀態(tài)數(shù)目M M為：為： M MD DK K)|()| 2 ()| 1 () 2|() 2| 2 () 2| 1 () 1

8、|() 1 | 2 () 1 | 1 (MMPMPMPMPPPMPPPPMj 1 馬爾可夫鏈可以用香農(nóng)線圖表示。馬爾可夫鏈可以用香農(nóng)線圖表示。(a),(b),(c(a),(b),(c) )分別表示信源含兩種字母分別表示信源含兩種字母(D(D2)2)的一的一階、二階和三階馬爾可夫鏈的線圖。階、二階和三階馬爾可夫鏈的線圖。(d),(e(d),(e) )分別表示分別表示D D3 3和和D D4 4的一階馬爾可夫鏈的的一階馬爾可夫鏈的線圖。線圖。AA(A )(B )BB(a)(AB)(BA)(BB)ABBBBAA(AA)B(b)(A A A )(B B B )(A B B )(B A A )(B B

9、A )(A A B )(A B A )(B A B )ABBBAAAABBBAABBA(c)(A)A(B)BBABACC(C)C(d)(A)(B)(C)(D)ACBCBDBAAACDDBCD(e)一、概述一、概述 一般情況下，信源輸出符號之間的相關(guān)性可以一般情況下，信源輸出符號之間的相關(guān)性可以追溯到追溯到最初的一個符號最初的一個符號，而在許多信源的輸出符號，而在許多信源的輸出符號序列中，符號之間的依賴關(guān)系是有限的序列中，符號之間的依賴關(guān)系是有限的任何時(shí)任何時(shí)刻信源符號發(fā)生的概率只與前面已經(jīng)發(fā)出的若干個刻信源符號發(fā)生的概率只與前面已經(jīng)發(fā)出的若干個符號有關(guān)，而與更前面發(fā)出的符號無關(guān)符號有關(guān)，而與更

10、前面發(fā)出的符號無關(guān)。這類信源。這類信源在輸出符號時(shí)不僅與符號集有關(guān)，還與信源的狀態(tài)在輸出符號時(shí)不僅與符號集有關(guān)，還與信源的狀態(tài)有關(guān)。有關(guān)。1212121121, ,(/)1JqlllliklkliijSEE EEXAa aax xxxs ssslEap xasElElE設(shè)一般信源所處的狀態(tài)：每種狀態(tài)下可能輸出的符號：每一個時(shí)刻，信源發(fā)出一個符號后，狀態(tài)發(fā)生轉(zhuǎn)移，信源輸出的符號序列：信源所處的隨機(jī)狀態(tài)序列：第 時(shí)刻，信源處于 狀態(tài)時(shí)，輸出符號 的概率：設(shè)信源在時(shí)刻處于 ， 時(shí)刻轉(zhuǎn)移到的狀態(tài)轉(zhuǎn)移概率：11(/)(/)(/)(/)(/)(/)ljiljlilklikiljlijip EEp sEsE

11、p xasEp aEp sEsEp EEl信源狀態(tài)序列服時(shí)齊（齊次）馬爾可與時(shí)刻夫從；，鏈：無關(guān)。狀態(tài)轉(zhuǎn)移圖狀態(tài)轉(zhuǎn)移圖(香農(nóng)線圖香農(nóng)線圖) E1 E3E20:0.51:0.51:0.40:0.61【注【注】E1、E2、E3是三種狀態(tài)，箭頭是指從一個狀態(tài)轉(zhuǎn)移到另是三種狀態(tài)，箭頭是指從一個狀態(tài)轉(zhuǎn)移到另一個狀態(tài)，旁邊的數(shù)字代表發(fā)出的某符號和條件概率一個狀態(tài)，旁邊的數(shù)字代表發(fā)出的某符號和條件概率p(ak/Ei) 。這就是香農(nóng)提出的馬爾可夫狀態(tài)轉(zhuǎn)移圖，也叫香農(nóng)線圖。這就是香農(nóng)提出的馬爾可夫狀態(tài)轉(zhuǎn)移圖，也叫香農(nóng)線圖。二、馬爾可夫信源二、馬爾可夫信源 若信源輸出的符號和信源所處的狀態(tài)滿足以下兩個條若信源輸出

12、的符號和信源所處的狀態(tài)滿足以下兩個條件，則稱為馬爾可夫信源：件，則稱為馬爾可夫信源：1111(/,)(/)(/)(/)(/)1(/klklilkljlklilklikikiaAljlklp xasE xasEp xasEp xasEp aEp aElp sExas（1）某一時(shí)刻信源符號的輸出只與此刻信源所處的狀態(tài)有關(guān)，而與以前的狀態(tài)和輸出符號都無關(guān)，即：當(dāng)具有時(shí)齊性時(shí)，有：及（2）信源某 時(shí)刻所處的狀態(tài)由當(dāng)前的輸出符號和前一時(shí)刻信源的狀態(tài)唯一決定，即：，0)1iE【注【注】上述條件表明，若信源處于某一狀態(tài)上述條件表明，若信源處于某一狀態(tài)Ei，當(dāng)它發(fā)出一個符號后，所處的狀態(tài)就變了。當(dāng)它發(fā)出一個符

13、號后，所處的狀態(tài)就變了。狀態(tài)狀態(tài)的轉(zhuǎn)移依賴于所發(fā)出的信源符號的轉(zhuǎn)移依賴于所發(fā)出的信源符號，因此任何時(shí)刻，因此任何時(shí)刻信源處在什么狀態(tài)完全由前一時(shí)刻的狀態(tài)和發(fā)出信源處在什么狀態(tài)完全由前一時(shí)刻的狀態(tài)和發(fā)出的符號決定。又因條件概率的符號決定。又因條件概率p(ak/Ei)已給定，所以已給定，所以狀態(tài)之間的轉(zhuǎn)移有一定的概率分布狀態(tài)之間的轉(zhuǎn)移有一定的概率分布，并可求出狀，并可求出狀態(tài)的一步轉(zhuǎn)移概率態(tài)的一步轉(zhuǎn)移概率p(Ej/Ei)。例：例：設(shè)某信源符號設(shè)某信源符號XA=a1,a2,a3，信源所處的狀態(tài)，信源所處的狀態(tài)SE=E1,E2,E3,E4,E5。各狀態(tài)之間的轉(zhuǎn)移情況如下各狀態(tài)之間的轉(zhuǎn)移情況如下圖所示，

14、請判斷這是否是一個馬爾可夫信源？圖所示，請判斷這是否是一個馬爾可夫信源？解解：（1）信源在）信源在Ei狀態(tài)下輸出符號狀態(tài)下輸出符號ak的條件概率的條件概率p(ak/Ei)用矩陣用矩陣表示為表示為:3111124411022(/)(/)11,2,3,4,531044100111442kikikp aEp aEi，且滿足，（2）該信源在）該信源在l時(shí)刻所處的狀態(tài)由當(dāng)前的輸出符號與前一時(shí)刻時(shí)刻所處的狀態(tài)由當(dāng)前的輸出符號與前一時(shí)刻(l-1)信源的狀態(tài)唯一決定信源的狀態(tài)唯一決定:2111111122112311(/)0(/)1(/)1(/)0llllllllllllp sExasEp sExasEp s

15、ExasEp sExasE111002441100022(/)3100044000013100044jip EE 可 求 得 狀 態(tài) 的 一 步 轉(zhuǎn) 移 概 率 ： 此信源滿足馬爾可夫的此信源滿足馬爾可夫的兩個條件，所以是馬爾可夫兩個條件，所以是馬爾可夫信源，并且是齊次馬爾可夫信源，并且是齊次馬爾可夫信源。信源。三、三、 m階馬爾可夫信源階馬爾可夫信源n 一般有記憶信源：一般有記憶信源： 發(fā)出的是有關(guān)聯(lián)性的各符號構(gòu)成的整體消息，即輸出發(fā)出的是有關(guān)聯(lián)性的各符號構(gòu)成的整體消息，即輸出的是符號序列，并用的是符號序列，并用符號間的聯(lián)合概率符號間的聯(lián)合概率描述這種關(guān)系。描述這種關(guān)系。n 馬爾可夫信源：馬

16、爾可夫信源： 用符號之間的用符號之間的轉(zhuǎn)移概率（條件概率）轉(zhuǎn)移概率（條件概率）來描述這種關(guān)聯(lián)來描述這種關(guān)聯(lián)關(guān)系。即馬爾可夫信源是以轉(zhuǎn)移概率輸出每個信源符號。關(guān)系。即馬爾可夫信源是以轉(zhuǎn)移概率輸出每個信源符號。n m階馬爾可夫信源階馬爾可夫信源 在某一時(shí)刻在某一時(shí)刻l，符號出現(xiàn)的概率僅與前面已出現(xiàn)的，符號出現(xiàn)的概率僅與前面已出現(xiàn)的m個符號有個符號有關(guān)，可以把這前面關(guān)，可以把這前面m個符號序列看成信源在個符號序列看成信源在l時(shí)刻所處的狀態(tài)。時(shí)刻所處的狀態(tài)。若每符號取值若每符號取值q種，則共有種，則共有qm種狀態(tài)，每種狀態(tài)，每種狀態(tài)對應(yīng)一個種狀態(tài)對應(yīng)一個m長長(q 進(jìn)制進(jìn)制)序列序列 ，這種狀態(tài)序列符

17、合馬爾可夫鏈的性質(zhì)，可用馬氏鏈，這種狀態(tài)序列符合馬爾可夫鏈的性質(zhì)，可用馬氏鏈來描述，這種信源稱為來描述，這種信源稱為m階馬爾可夫信源。數(shù)學(xué)模型：階馬爾可夫信源。數(shù)學(xué)模型：1121121121211211 2(/)(/)11 2mmmmmqmmkkkkqkkkkmkaaaXkkkkqp aa aap aa aakkkq：， ， ， ， ，同時(shí)滿足：， ， ， ， ，【注【注】當(dāng)當(dāng)m=1時(shí)，為一階馬爾可夫信源。時(shí)，為一階馬爾可夫信源。n 馬爾可夫信源熵馬爾可夫信源熵12111111212121112112111(/)(/)(/)lim(/)lim(/)lim()log (/NmmNNN mN mN

18、mmNNNNkkkkkkkkkkkkkkNNNNNNqqkkkkkkkNkkp aa aa aap aaaap aa aaHH XX XXHH XX XXp a aap aa aa 由馬爾可夫信源定義及其齊次性：由極限熵，可得：1211211211121111111112)lim()log (/)()log (/)(/)NmmNmmmmqqkkkkkkkNkkqqkkkkkmmkkkkmp a aap aa aap a aap aa aaH XXHXXmHm 階馬爾可夫信源的極限熵就等于 階條件熵，記為這表明：設(shè)狀態(tài)設(shè)狀態(tài)12()mikkkEa aa iE1mka ,信源處于狀態(tài)信源處于狀態(tài)時(shí)

19、，再發(fā)出下一個符號時(shí)，再發(fā)出下一個符號此時(shí)，符號序列此時(shí)，符號序列 231()mkkka aa231()mjkkkEa aaiE就組成了新的信源狀態(tài)就組成了新的信源狀態(tài)，這時(shí)信源所處的狀態(tài)由，這時(shí)信源所處的狀態(tài)由轉(zhuǎn)移到轉(zhuǎn)移到 jE112111111(/)(/)(/)(/)(1 2,1 2)() (/)log (/)() (/)l()(1,2,)og (/)(/mmmmmmkkkkkikijimqqmijijiijqqikikiikjimip aa aap aEp aEp EEkqi jqHHp E p EEp EEp E p aEp aEp EEp Eiqm 是 階馬爾可夫信源穩(wěn)定后的， ，

20、， ， ，其中，狀態(tài)極限概率)是狀態(tài)之間的一步轉(zhuǎn)移概率?！咀ⅰ咀ⅰ靠梢娗蠼怦R爾可夫信源條件熵關(guān)鍵是要得到可見求解馬爾可夫信源條件熵關(guān)鍵是要得到()(1,2,)mip Eiq11(/)0lim(/)()(1,2,)()() (/)(1,2,)()0()mmljimljijlqmjijiijjli, j=1,2,.,qp EEjip EEp Ejqp Ep E p EEjqp Ep E：對于有限齊次馬爾可夫鏈，若存在一個正整數(shù)，對一切都有：則對每一個 都存在不依賴于 的極限：這種有限齊次馬爾可夫馬爾可夫鏈?zhǔn)歉鲬B(tài)遍歷的。其極限概率是方程組滿足條件，鏈的各態(tài)遍歷定理11mqj的唯一解?！咀ⅰ咀ⅰ縰 上

21、述定理說明，有限齊次、遍歷馬爾可夫鏈信源，上述定理說明，有限齊次、遍歷馬爾可夫鏈信源，在初始時(shí)刻可以處在任意狀態(tài)，然后狀態(tài)之間可以在初始時(shí)刻可以處在任意狀態(tài)，然后狀態(tài)之間可以轉(zhuǎn)移，經(jīng)過足夠長時(shí)間之后，信源處于什么狀態(tài)已轉(zhuǎn)移，經(jīng)過足夠長時(shí)間之后，信源處于什么狀態(tài)已與初始狀態(tài)無關(guān)。與初始狀態(tài)無關(guān)。u 狀態(tài)極限概率方程組可寫為：狀態(tài)極限概率方程組可寫為：112( )1,( )0 (), (),., ()mmqiqWPWW iW iWWp Ep Ep EP，其中為狀態(tài)極限概率分布矢量：為狀態(tài)一步轉(zhuǎn)移矩陣。例例1 設(shè)有二元二階馬爾可夫信源：設(shè)有二元二階馬爾可夫信源：(0)1/3(1)2/3(0/00)(

22、1/11)0.8(1/00)(0/11)0.2(0/01)(0/10)(1/01)(1/10)0.5pppppppppp信源符號集為0,1，初始概率大小為，；條件概率為：畫出信源狀態(tài)轉(zhuǎn)移圖？信源熵？信源穩(wěn)定后符號0、1的概率分布？21234114421343223421324(/)(/)0.8(/)(/)0.2(/)(/)(/)(/)0.50mqEEEEp EEp EEp EEp EEp EEp EEp EEp EE解 ： 由 題 意 得 ：信 源 任 何 時(shí) 刻 發(fā) 出 什 么 符 號 只 與 前 面 兩 個 符 號 有 關(guān) ，與 前 面 得 符 號 無 關(guān) 。 信 源 就 有種 可 能 的

23、 狀 態(tài) ，即 為 00、 01、 10、 11， 分 別 用、符 號 表 示 。同 時(shí) 可 求 得 狀 態(tài) 轉(zhuǎn) 移 概 率 ：除 此 之 外 ， 其 它 狀 態(tài) 轉(zhuǎn) 移 概 率 為 ， 狀 態(tài) 轉(zhuǎn) 移 圖 如 下 所 示 ：0.80.200000.50.5(/)0.50.500000.20.8jip EE 狀態(tài)的一步轉(zhuǎn)移概率矩陣為：111321332442441142()() (/)(1,2,)()0.8 ()0.5 ()()0.2 ()0.5 ()()0.5 ()0.2 ()()0.5 ()0.8 ()()15()()14()(mqmjijiijjp Ep E p EEjqp Ep Ep

24、Ep Ep Ep Ep Ep Ep Ep Ep Ep Ep Ep Ep Ep Ep由有限齊次馬爾可夫鏈的各態(tài)遍歷定理：可得：求得穩(wěn)定狀態(tài)下的狀態(tài)極限概率：32)14E443111( ) (/)log (/)5225(0.80.2)(0.50.5)(0.50.5)(0.80.2)141414140.8/( )( ) (/)0152251(0) 0.80.50.50.21414141425(1) 0.2014mijijiijqkikiiHHp E p E Ep E EHHHHp ap E p a Epp，比特 符號根據(jù)可求得符號、 的概率分布：2251.50.50.81414142【結(jié)論【結(jié)論】l

25、 信源達(dá)到穩(wěn)定后，信源符號的概率分布與初始概率不同，信源達(dá)到穩(wěn)定后，信源符號的概率分布與初始概率不同，因此一般馬爾可夫信源并非是平穩(wěn)信源。但當(dāng)時(shí)齊、遍歷的馬因此一般馬爾可夫信源并非是平穩(wěn)信源。但當(dāng)時(shí)齊、遍歷的馬爾可夫信源達(dá)到穩(wěn)定后，就可看成一個穩(wěn)定信源。爾可夫信源達(dá)到穩(wěn)定后，就可看成一個穩(wěn)定信源。l 計(jì)算信源的信息熵，對于平穩(wěn)信源須知道信源的各維概率計(jì)算信源的信息熵，對于平穩(wěn)信源須知道信源的各維概率分布，而對于分布，而對于m階馬爾可夫信源，只要知道與前面階馬爾可夫信源，只要知道與前面m個符號有個符號有關(guān)的條件概率，因此一般信源可用關(guān)的條件概率，因此一般信源可用m階馬爾可夫信源來近似。階馬爾可夫

26、信源來近似。 例例2：有一個馬爾可夫信源，已知有一個馬爾可夫信源，已知 試畫出該信源的香農(nóng)線圖，并求出信源熵。試畫出該信源的香農(nóng)線圖，并求出信源熵。 解：該信源的香農(nóng)線圖為：解：該信源的香農(nóng)線圖為： 在計(jì)算信源熵之前，先用轉(zhuǎn)移概率求穩(wěn)定狀態(tài)下二個狀態(tài)在計(jì)算信源熵之前，先用轉(zhuǎn)移概率求穩(wěn)定狀態(tài)下二個狀態(tài)x1和和 x2 的概率的概率 和和 可得：可得： 馬爾可夫信源熵馬爾可夫信源熵 3211)(xxp3112)(xxp1)(21xxp0)(22xxp1/3(x2)(x1)2/31)(2xp)(1xp)()()(21321xpxpxp)(0)()(21312xpxpxp1)()(21xpxp4/ 3)

27、(1xp4/ 1)(2xp符號/.689. 01log14131log3132log3243)(log)()(bitxxpxxpxpHIJijiji例例3：一階馬爾可夫信源的狀態(tài)圖如下，信源的符號集為一階馬爾可夫信源的狀態(tài)圖如下，信源的符號集為0,1,2，并定義，并定義p+q=1。 (1) 求信源平穩(wěn)后的狀態(tài)極限概率分布求信源平穩(wěn)后的狀態(tài)極限概率分布; (2) 求此信源的熵；求此信源的熵； (3) 近似認(rèn)為信源無記憶時(shí)，符號的概率分布等于平近似認(rèn)為信源無記憶時(shí)，符號的概率分布等于平 穩(wěn)分布。穩(wěn)分布。求近似信源的熵求近似信源的熵H(X) ，并與，并與H進(jìn)行比較；進(jìn)行比較； (4) 對一階馬爾可夫

28、信源對一階馬爾可夫信源p取何值時(shí)取何值時(shí)H取最大值？又當(dāng)取最大值？又當(dāng)p=0或或p=1時(shí)結(jié)果如何？時(shí)結(jié)果如何？012p/2p/2qp/2p/2p/2p/2qq例例4：設(shè)有一信源，它在開始時(shí)以設(shè)有一信源，它在開始時(shí)以p(a)=0.6、p(b)=0.3、p(c)=0.1的概率發(fā)出符號的概率發(fā)出符號X1，如果，如果X1為為a時(shí)，則時(shí)，則X2為為a、b、c的概率均為的概率均為1/3；如果；如果X1為為b時(shí)，則時(shí)，則X2為為a、b、c的概率均為的概率均為1/3；如果；如果X1為為c時(shí)，則時(shí)，則X2為為a、b的概率的概率均為均為1/2，為，為c的概率為的概率為0。而且后面發(fā)出。而且后面發(fā)出Xi的概率只的概

29、率只與與Xi-1有關(guān)。又有關(guān)。又p(Xi| Xi-1)= p(X2| X1)，i3。利用馬爾。利用馬爾可夫信源的圖示畫出狀態(tài)轉(zhuǎn)移圖，并計(jì)算信源熵可夫信源的圖示畫出狀態(tài)轉(zhuǎn)移圖，并計(jì)算信源熵H 。n 馬氏鏈的可約性馬氏鏈的可約性馬氏鏈可約性馬氏鏈可約性: 若對所有若對所有 k，都有，都有k步轉(zhuǎn)移概率步轉(zhuǎn)移概率p(k)ij=0，就意味，就意味著一旦出現(xiàn)著一旦出現(xiàn) Si以后不可能到達(dá)以后不可能到達(dá)Sj, 也就是不能各態(tài)也就是不能各態(tài)遍歷，或者狀態(tài)中應(yīng)把遍歷，或者狀態(tài)中應(yīng)把Sj取消，這樣就成為可約的取消，這樣就成為可約的了。了。k步轉(zhuǎn)移概率：步轉(zhuǎn)移概率：經(jīng)過經(jīng)過k個時(shí)刻后狀態(tài)的轉(zhuǎn)移概率。個時(shí)刻后狀態(tài)的轉(zhuǎn)

30、移概率。 p(k)ij=p(sl+k=Ej |sl=Ei)馬氏鏈不可約性馬氏鏈不可約性: 對任意一對對任意一對i和和j，都存在至少一個，都存在至少一個k使使p(k)ij0，這就是說從這就是說從Si開始，總有可能到達(dá)開始，總有可能到達(dá) Sj. S1S3S21/21/21/21/21S4S51/21/2可約馬氏鏈可約馬氏鏈1/21/2 由狀態(tài)由狀態(tài)S3轉(zhuǎn)移轉(zhuǎn)移到到S1的轉(zhuǎn)移概率的轉(zhuǎn)移概率p(k)31=0，因?yàn)橐?，因?yàn)橐贿M(jìn)人狀態(tài)進(jìn)人狀態(tài)S3就一直繼續(xù)下去，而不會再轉(zhuǎn)移到就一直繼續(xù)下去，而不會再轉(zhuǎn)移到其他狀態(tài)其他狀態(tài)。P(k)41=0也是明顯的，因也是明顯的，因S4和和S1之間之間沒有連接箭頭，因此這

31、種鏈就是可約的。沒有連接箭頭，因此這種鏈就是可約的。 小結(jié)小結(jié) 兩種有記記憶信源比較兩種有記記憶信源比較類型類型 m階馬爾可夫過程階馬爾可夫過程 m長有記憶信源長有記憶信源 依賴關(guān)系依賴關(guān)系(相當(dāng)于相當(dāng)于)記憶長度為記憶長度為mm個符號為一組個符號為一組組內(nèi)相關(guān)，組間無關(guān)組內(nèi)相關(guān)，組間無關(guān)描述描述 狀態(tài)轉(zhuǎn)移狀態(tài)轉(zhuǎn)移(條件條件)概率概率 聯(lián)合概率聯(lián)合概率 每符號每符號平均熵平均熵 極限熵極限熵Hm+1 Hm(X)=lim(1/m)H(X1X2Xm) 總結(jié)總結(jié): :各種離散信源的熵各種離散信源的熵 (1) (1) 發(fā)出單個符號消息的離散無記憶信源熵發(fā)出單個符號消息的離散無記憶信源熵 若信源發(fā)出若信

32、源發(fā)出N N個不同符號個不同符號X1，X2，Xi，XN , 代表代表N N種不種不同的符號，各個符號的概率分別為同的符號，各個符號的概率分別為 P P1 1， P P2 2， P Pi，P PN N 因?yàn)檫@些符號相互獨(dú)立，所以該信源熵為：因?yàn)檫@些符號相互獨(dú)立，所以該信源熵為： H H（X X） P PiloglogP Pi bit/ bit/符號符號 (2)(2)發(fā)出符號序列消息的離散無記憶信源熵發(fā)出符號序列消息的離散無記憶信源熵 發(fā)出發(fā)出K K重符號序列消息的離散無記憶信源熵為共熵重符號序列消息的離散無記憶信源熵為共熵H(XH(XK K) )，它與，它與單個符號消息信源熵單個符號消息信源熵H

33、(X)H(X)有如下關(guān)系：有如下關(guān)系： H(XH(XK K) )KH(X)KH(X)KK P PiloglogP Pi bit/ bit/符號序列符號序列 Ni 1Ni 1 (3)(3)發(fā)出符號序列消息的離散有記憶信源熵發(fā)出符號序列消息的離散有記憶信源熵 發(fā)出發(fā)出K K重符號序列消息的離散有記憶信源熵也為共熵重符號序列消息的離散有記憶信源熵也為共熵H(XH(XK K) ) 當(dāng)當(dāng)K K2 2時(shí)時(shí) H(XH(X2 2) )H(X)H(X)H(X|X)H(X|X) H(X|X) H(X) H(X|X) H(X) H(XH(X2 2) 2H(X) 2H(X) 推廣到推廣到K K重重 H(XH(XK K

34、) )H(X)H(X)H(X|X)H(X|X)H(X|XXX) H(X|XXX) bit/bit/符號序列符號序列 (K1)個個 (4) (4) 發(fā)出符號序列消息的馬爾可夫信源熵發(fā)出符號序列消息的馬爾可夫信源熵 馬爾可夫信源熵是條件熵馬爾可夫信源熵是條件熵 若從前一狀態(tài)若從前一狀態(tài)E Ei轉(zhuǎn)移到后一狀態(tài)轉(zhuǎn)移到后一狀態(tài)E Ej有多種可能性，則信源由有多種可能性，則信源由狀態(tài)狀態(tài)E Ei發(fā)出一個符號的發(fā)出一個符號的H Hi為為 H Hi P(j|i)logP(j|iP(j|i)logP(j|i) ) 再進(jìn)一步對前一狀態(tài)再進(jìn)一步對前一狀態(tài)E Ei的全部可能性作統(tǒng)計(jì)平均，就得馬的全部可能性作統(tǒng)計(jì)平均，

35、就得馬爾可夫信源熵爾可夫信源熵 H H 為為 H H P(i)HP(i)Hi P(i) P(j|i)logP(j|iP(i) P(j|i)logP(j|i) bit/) bit/符符號號 JJII4. 各種離散信源的時(shí)間熵各種離散信源的時(shí)間熵 信源的時(shí)間熵信源的時(shí)間熵在單位時(shí)間內(nèi)信源發(fā)出的平均信息量，單位在單位時(shí)間內(nèi)信源發(fā)出的平均信息量，單位 為為s(s(秒秒) )或其他特定的時(shí)間單位或其他特定的時(shí)間單位 發(fā)出單個符號消息的離散無記憶信源的時(shí)間熵發(fā)出單個符號消息的離散無記憶信源的時(shí)間熵 已知離散無記憶信源各符號的概率空間已知離散無記憶信源各符號的概率空間 由于發(fā)出各符號所占有時(shí)間是不同的由于發(fā)

36、出各符號所占有時(shí)間是不同的 可設(shè)符號可設(shè)符號X1的長度為的長度為b b1 1，X2為為b b2 2，Xi為為b bi，XN為為b bN 單位均為單位均為s(s(秒秒) ) 則信源各符號的平均長度是各個的概率加權(quán)平均值，即則信源各符號的平均長度是各個的概率加權(quán)平均值，即 X XP(X)P(X)X1，X2， ，Xi，XNP P1 1， P P2 2， P Pi， P PNNiiibPb1s/符號 則信源的時(shí)間熵則信源的時(shí)間熵 H Ht t為：為： 若各符號時(shí)間長度相同，均為若各符號時(shí)間長度相同，均為b(sb(s) )，則可直接得，則可直接得 又若信源每秒平均發(fā)出又若信源每秒平均發(fā)出 n n個符號，

37、有個符號，有 此時(shí)，信源時(shí)間熵此時(shí)，信源時(shí)間熵 H Ht t為：為：NiiiNiiitbPPPbXHH11log)(bit/sbit/sbb bn1符號符號/sNiiitPPnXnHH1log)(bit/sbit/s 發(fā)出符號序列消息的離散無記憶信源的時(shí)間熵發(fā)出符號序列消息的離散無記憶信源的時(shí)間熵 對對K K重符號序列的離散無記憶信源的信源熵為：重符號序列的離散無記憶信源的信源熵為： H(XH(XK K) ) KH(X) bit/KH(X) bit/符號序列符號序列 K K重符號序列消息的平均長度為信源各符號平均長度的重符號序列消息的平均長度為信源各符號平均長度的K K倍，即倍，即 這種信源的

38、時(shí)間熵這種信源的時(shí)間熵 H Ht t為：為： 可見，它在數(shù)值上與上面一種信源的時(shí)間熵相同可見，它在數(shù)值上與上面一種信源的時(shí)間熵相同NiiibPKbKB1s/s/符號序列符號序列 NiiiNiiiKtbPPPbXHbKXKHBXHH11log)()()(bit/sbit/s 若該信源每秒內(nèi)平均發(fā)出若該信源每秒內(nèi)平均發(fā)出n n個個K K重符號序列消息，則有：重符號序列消息，則有： 此時(shí)此時(shí) HtHt為：為： 發(fā)出符號序列消息的離散有記憶信源的時(shí)間熵發(fā)出符號序列消息的離散有記憶信源的時(shí)間熵 計(jì)算方法與發(fā)出符號序列無記憶信源的時(shí)間熵一致，但計(jì)算方法與發(fā)出符號序列無記憶信源的時(shí)間熵一致，但 H(XH(X

39、K K) ) KH(X) KH(X) 同樣若信源在每秒內(nèi)平均發(fā)出同樣若信源在每秒內(nèi)平均發(fā)出n n個個K K重符號序列消息，有重符號序列消息，有 bKBn11 符號序列符號序列/s/s)()(XnKHXnHHKtbit/sbit/sbKXHBXHHKKt)()(bit/sbit/sbKBn11 符號序列符號序列/s/s)(KtXnHHbit/s5.信源的冗余度信源的冗余度 信源熵信源熵 表示信源輸出每一個符號所攜帶的信息表示信源輸出每一個符號所攜帶的信息量。量。 對于一個具體信源，它所具有的總信息量是一定的對于一個具體信源，它所具有的總信息量是一定的 信息熵越大（每個信源符號所承載的信息量越大）

40、信息熵越大（每個信源符號所承載的信息量越大） 輸出全部信源信息所需傳送的符號就越少輸出全部信源信息所需傳送的符號就越少 通信效率越高通信效率越高 這是我們研究信息熵的目的這是我們研究信息熵的目的 離散無記憶信源：離散無記憶信源： 信源符號間彼此無依賴、等概率分布，信源熵最大信源符號間彼此無依賴、等概率分布，信源熵最大（最大熵定理最大熵定理） H Hmaxmax ，攜帶信息的效率最高。，攜帶信息的效率最高。離散有記憶信源：離散有記憶信源： 信源輸出符號間彼此依賴、相關(guān)，信源熵減?。l信源輸出符號間彼此依賴、相關(guān)，信源熵減?。l件熵?zé)o條件熵），輸出符號間相關(guān)長度越長，信源件熵?zé)o條件熵），輸出符號間

41、相關(guān)長度越長，信源熵越小。熵越小。 所有有記憶信源、非等概率離散無記憶信源熵所有有記憶信源、非等概率離散無記憶信源熵 H Hmaxmax 信源的冗余度信源的冗余度R R 1 1減去熵的相對率。減去熵的相對率。 maxmaxmax1HHHHHR 熵的相對率熵的相對率 信源的實(shí)際信息熵與具有信源的實(shí)際信息熵與具有同樣符號集的最大熵的比值。同樣符號集的最大熵的比值。 =maxHH【注【注】u 信源符號間依賴關(guān)系越大，信源冗余度越大。信源符號間依賴關(guān)系越大，信源冗余度越大。u 信息論研究目的提高信息傳輸?shù)男畔⒄撗芯磕康奶岣咝畔鬏數(shù)挠行浴⒖煽啃?、有效性、可靠性、保密性保密性。u 從提高信源輸出有效性

42、的觀點(diǎn)出發(fā)，希望從提高信源輸出有效性的觀點(diǎn)出發(fā)，希望減少或去減少或去掉冗余度掉冗余度。 u 冗余度大的信源冗余度大的信源具有較強(qiáng)的抗干擾能力具有較強(qiáng)的抗干擾能力，當(dāng)干擾使，當(dāng)干擾使信息在傳輸過程中出現(xiàn)錯誤時(shí)，可從它的上下關(guān)聯(lián)信息在傳輸過程中出現(xiàn)錯誤時(shí)，可從它的上下關(guān)聯(lián)中糾正錯誤，因此從提高信息傳輸可靠性觀點(diǎn)出發(fā)，中糾正錯誤，因此從提高信息傳輸可靠性觀點(diǎn)出發(fā)，總是希望總是希望增加信源冗余度增加信源冗余度。u 信源編碼就是通過信源編碼就是通過減少或消除信源冗余度減少或消除信源冗余度來提高通來提高通信的傳輸效率，即提高通信的信的傳輸效率，即提高通信的有效性有效性。u 信道編碼則是通過信道編碼則是通過增加信源的冗余度增加信源的冗余度來提高通信的來提高通信的抗干擾能力，即提高通信的抗干擾能力，即提高通信的可靠性可靠性。連續(xù)信源的