【正文】 jjSp S H X S?=右 邊1 ( ) ( | ) .jm j jSH H p S H X S???? ?即 ，求馬爾可夫信源的熵 1 . 3 . 5 . 2 寫 出 狀 態(tài) 轉(zhuǎn) 移 矩 陣 ， 根 據(jù) 定 理 判 斷 是 否存 在 穩(wěn) 態(tài) 分 布 ；? ?1212122. .1( ) , ( ) , , ( ) ,( ) ( ) ( ) 1( ) , ( ) , , ( ) .JJJW p S p S p SW P Wp S p S p Sp S p S p S??? ? ?? ?? 根 據(jù) 定 理 求 出 穩(wěn) 態(tài) 分 布 ；令根 據(jù) ，求3 . ( ) ( | )jjjSH p S H X S? ? ? 根 據(jù) 求 出 信 源 熵 .求馬爾可夫信源熵 —— 例子 ?例 二階馬爾可夫鏈的狀態(tài)轉(zhuǎn)移圖如圖 ， 求信源熵。 0 00 10 : 0 . 51 : 0 . 51 : 0 . 80 : 0 . 8S1S21 01 1S3S41 : 0 . 2 0 : 0 . 51 : 0 . 5 0 : 0 . 2解： 1 . 3 . 5 . 2 寫 出 狀 態(tài) 轉(zhuǎn) 移 矩 陣 ， 根 據(jù) 定 理 判 斷 是 否存 在 穩(wěn) 態(tài) 分 布 ；230 .8 0 .2 0 00 0 0 .5 0 .50 .5 0 .5 0 00 0 0 .2 0 .8PP??????????????.5 .3例 已 求 出 狀 態(tài) 轉(zhuǎn) 移 矩 陣 為 ：，的 每 一 個 元 素 不 為 零 ，該 馬 氏 鏈 為 遍 歷 的 , 穩(wěn) 態(tài) 分 布 存 在 。?例 二階馬爾可夫鏈的狀態(tài)轉(zhuǎn)移圖如圖 ， 求信源熵。 ( ) ( | )5 1 1 5( 0. 8 , 0. 2) + H( 0. 5, 0. 5)+ H( 0. 5, 0. 5)+ ( 0. 8 , 0. 2 )14 73. ( ) ( | )7 140. 80 /jjjjSjSjH p S H X SH p S H X SHHbi t?????? ??根 據(jù) 求 出 信 源 熵 .符 號0 00 10 : 0 . 51 : 0 . 51 : 0 . 80 : 0 . 8S1S21 01 1S3S41 : 0 . 2 0 : 0 . 51 : 0 . 5 0 : 0 . 2解： 121 4 2 3( ) ( ) ( ) 152/ 14 , 1 / 7. 3. 5. 1rWP Wp S p S p Sp p p p?? ? ?? ?? ? ? = 根 據(jù) ， 可根 據(jù) 定 理 求 出 穩(wěn) 態(tài) 布 ；得求 得分，求馬爾可夫信源熵 —— 例子 信源的相關(guān)性和剩余度 ?即 信源輸出符號間的依賴關(guān)系使得信源熵減小 —— 信源的相關(guān)性 。 ?含義：由于信源符號間存在依賴關(guān)系，信源輸出的符號越多，越容易判斷將要輸出的符號是什么，即信源熵（不確定性）越小。 111 1 22 1 321 ( | , , ) ( | , , ) ( | , , ) ( | ) NNNNNNH X X XH X X XH X X XH X X??????????? ??對 于 平 穩(wěn) 信 源 ， 有10 ( ) l ogH X H q? ? ?0 1 2 1mH H H H H??? ? ? ? ? ?定義 信源剩余度定義為 R = 1 H?/H0 H0：每個符號帶有的最大的平均信息量 H?： 每個符號帶有 實際的 平均信息量 H?/H0：熵的相對率 ? 信源的相關(guān)性和剩余度 ?含義： 信源剩余度越大，表明信源的輸出效率不高，即信源符號之間的相關(guān)性越強；信源剩余度越小，表明信源輸出效率越高，即信源符號之間的相關(guān)性越弱。 ? 張三住院了；張三沒來上課 ? 張三住院了；李四沒來上課 ?信源編碼的目的：去除信源相關(guān)性，壓縮。 作業(yè) ? ? （ 1） ? （ 1）（ 2） ? （ 1）（ 2）只計算 H(X2) ? ? ，只畫出狀態(tài)轉(zhuǎn)移圖 ? ，只畫出狀態(tài)轉(zhuǎn)移圖 ? ，只畫出狀態(tài)轉(zhuǎn)移圖 ? ? 請談?wù)勀銓φn本 64頁定義 信息對抗技術(shù)研究所 信息對抗技術(shù)研究所 附 錄 馬爾可夫鏈性質(zhì) 1. 互通性 定義：如果從狀態(tài) i可到達狀態(tài) j，同時從狀態(tài) j也可到達狀態(tài) i，則稱狀態(tài) i和狀態(tài) j是互通的。 結(jié)論： （ 1）任何狀態(tài)的自身是互通的 ,因 為 （ 2）如果狀態(tài) i和狀態(tài) j是互通的，則狀態(tài) j和狀態(tài) i也是互通的； （ 3）如果狀態(tài) i和狀態(tài) j是互通的，且狀態(tài) j和狀態(tài) k也是互通的，則狀態(tài) i和 狀態(tài) k也是互通的。 1}{)0( 00 ???? iXiXPp ii2. 不可約性 類的概念： 根據(jù)互通的三個屬性，狀態(tài)可被分成 1個或多個獨立的類，同一類中狀態(tài)之間彼此是互通的（該類也可能只包含一種狀態(tài)）。 不可約性定義： 如果系統(tǒng)中的所有狀態(tài)被歸為一類，即所有狀態(tài)之間都是互通的，則該馬爾可夫鏈被稱為 不可約 。 3. 常返態(tài)、非常返態(tài)（瞬時態(tài)）和吸收態(tài) 非常返態(tài)定義： 如果過程一旦到達某狀態(tài)后在未來決不會再回到此狀態(tài)，則稱該狀態(tài)為非常返態(tài)或瞬時狀態(tài)。因此，當(dāng)且僅當(dāng)若存在一個狀態(tài) j（ j≠i），只能從狀態(tài) i可達該狀態(tài) j，而從狀態(tài)j不可到達狀態(tài) i，則狀態(tài) i為非常返態(tài)或瞬時狀態(tài)。 常返態(tài)定義： 如果達到某狀態(tài)的過程在未來一定會再次回到此狀態(tài)，則該狀態(tài)被稱為常返態(tài)。因此，當(dāng)且僅當(dāng) i不是非常返態(tài)時，必是常返態(tài)。 吸收態(tài)定義： 如果到達某狀態(tài)后，過程不再離開此狀態(tài)，則該狀態(tài)被稱為吸收態(tài)。狀態(tài) i是吸收態(tài)，當(dāng)且僅當(dāng) pii=1。 假設(shè)某案例的馬爾可夫鏈有如下的轉(zhuǎn)移矩陣 ： 0000103/23/100001000002/12/10004/34/1P= 01234 0 1 2 3 4 狀態(tài) 說明： （ 1）狀態(tài) 0和狀態(tài) 1都是常返態(tài)。從 P中可看出，如果過程初始狀態(tài)為 0或 1，那么該過程不會離開這兩種狀態(tài)； （ 2）狀態(tài) 2是吸收狀態(tài)（一種特殊的常返態(tài)），因為過程進入狀態(tài) 2后就不會再離開此狀態(tài)（矩陣第三行）。 （ 3）狀態(tài) 3是瞬時態(tài)，即如果過程到達狀態(tài) 3時，存在著不會再回到該狀態(tài)的大于 0的概率，概率值為 1/3（過程從狀態(tài) 3到狀態(tài) 2的概率）。一旦狀態(tài)進入狀態(tài) 2，則過程將一直處于狀態(tài) 2。 （ 4）狀態(tài) 4也是瞬時態(tài)，因為過程一到達狀態(tài) 4會立刻離開進入狀態(tài) 0，且永遠不再回到該狀態(tài)。 4. 周期性 周期性定義： 某狀態(tài) i的周期為正整數(shù) t（ t1），則對于除了 t， 2t， 3t， …以外的所有 n值， pii(n)=0，即 t是具有該屬性的最大整數(shù)值。 非周期態(tài)： 如果存在兩個連續(xù)自然數(shù) s和 s+1，過程在 s和 s+1時的狀態(tài)均為 i，即該狀態(tài)的周期為 1，則該狀態(tài)被稱為非周期態(tài)。 遍歷態(tài)： 在有限狀態(tài)的馬爾可夫鏈中，具有非周期性且常返的狀態(tài)被稱為遍歷態(tài)。如果馬爾可夫鏈的所有狀態(tài)都是遍歷態(tài)，則該鏈被稱為是遍歷的。