離散信源

第三章 離散信源 北京郵電大學 信息工程學院 離散信源的分類與數(shù)學模型 離散無記憶信源的熵 離散平穩(wěn)信源的熵 有限狀態(tài)馬爾可夫鏈 馬爾可夫信源 信源的相關(guān)性與剩余度 本章內(nèi)容 3.1 離散信源的分類與數(shù)學模型 信源離散信源的分類 離散信源的數(shù)學模型 3.1.1 離散信源的分類 根據(jù)信源符號取值 連續(xù) /離散 根據(jù)輸入符號間的依賴關(guān)系 無記憶 /有記憶 有限離散信源 /無限離散信源 平穩(wěn)信源 /非平穩(wěn)信源 3.1.2 離散無記憶信源的數(shù)學模型 niiinnapapapapaaPX1111)(,0)()()( 注釋 A=a1， ， an 信源的符號集 n 符號集的大小 ai 隨機變量的取值 p(ai) X= ai的概率。 單符號離散無記憶信源的數(shù)學模型： 3.1.1 qpPX 10一個二元無記憶信源，符號集 A=0,1, p為X=0的概率 ,q為 X=1的概率， q=1-p；寫出信源的模型。 解： 信源的模型： 例 單符號離散無記憶信源 多維離散無記憶信源 數(shù)學模型 : )()( 11MMNppPX3.1.2 離散無記憶信源的數(shù)學模型 信源 X的 N次擴展源 ：設(shè)信源為 X，由 X構(gòu)成的 N維隨機矢量集合 信源與其擴展源的關(guān)系： )(,21 同分布與 XXXXXX iNN 離散無記憶信源的 N次擴展源 NN XXXX ,21X N個連續(xù)輸出的符號合并 )()()()()11()10()01()00()( 432143212 pppppX243221 )1()(),()1()(,)( pppppppp 11,10,01,00:,: 212 符號集二次擴展源 XXX :2的模型X3.1.2 求 例 3.1.1 中信源的二次擴展模型。 解： 二元信源 X的符號集為 0,1 :2 各符號的概率為X例 離散無記憶信源的 N次擴展源 馬氏鏈是隨機過程，因此可看成信源，即馬爾可夫信源；這種信源是有記憶信源。 有限記憶的系統(tǒng)可以用有限狀態(tài)機來描述。在有限狀態(tài)機中，既包含狀態(tài)之間的轉(zhuǎn)移關(guān)系，也包含輸出與狀態(tài)之間的關(guān)系。 可以從有限狀態(tài)機的概念出發(fā)定義馬爾可夫信源。 3.1.3 離散有記憶信源的數(shù)學模型 離散馬爾可夫信源 3.2 離散 無 記憶信源的 熵 單符號離散無記憶信源的熵 離散無記憶信源 N次擴展源的熵 3.2.1 qqppXH l o gl o g)( 3.2.1 單符號離散無記憶信源的熵 寫出例 3.1.1 中的二元無記憶信源的熵的表達式。 解： )1l o g()1(l o g pppp )( pH例 具有熵的一切性質(zhì) 對 p的導函數(shù)為 p=0.5時 ,H(p)達到最大值 1bit H(p)是 p的上突函數(shù) 0)1( 1)( l o g)( ppepH 0.5 1 1 )(pH0 p pppH 1lo g)(H(p)的主要性質(zhì)： 3.2.1 單符號離散無記憶信源的熵 )()( XHNXH N )()(1niiN XHXH3.2.2 離散無記憶信源 N次擴展源的熵 定理 3.2.1 離散無記憶信源 X的 N次擴展源 的熵等于信源 X熵的 N倍，即 證明： NX熵的可加性 無記憶信源 互相獨立且分布相同iX)( XNH3.2.2 給定離散無記憶信源模型： 求其二次擴展源熵。 解： 4/14/12/1321 aaaPX)( 2XH 2)41l o g41(21l o g212 5.12 )(2 XH符號/3 b it例 3.2.2 離散無記憶信源 N次擴展源的熵 3.3 離散平穩(wěn)信源 的熵 離散平穩(wěn)信源 離散平穩(wěn)有記憶信源的熵 信源 X具有有限符號集 信源產(chǎn)生隨機序列 對所有 有 , 21 naaaA ix ,2,1,iXxjjhii iNN 及, 11 ),(),( 22112211 NNNN jhijhijhijijiji axaxaxpaxaxaxp 3.3.1 離散平穩(wěn)信源 (1) 定義： 則稱信源為離散平穩(wěn)信源，所產(chǎn)生的序列為平穩(wěn)序列 ),(),( 2121 hihihiiii NN xxxpxxxp ),(),( 11 NjjjNiii xxxpxxxp 平穩(wěn)序列的統(tǒng)計特性與時間的推移無關(guān) 3.3.1 離散平穩(wěn)信源 (2) 3.3.1 一平穩(wěn)信源 X的符號集 A=0， 1，產(chǎn)生隨機序列，其中 P(x1=0)=p, 求 P(xn=1)（ n 1）的概率。 解： 例 平穩(wěn)性 pxP n )0(pxP n 1)1(3.3.1 離散平穩(wěn)信源 (3) 3.3.1續(xù) 對同一信源，若 P(x1=0， x2=1)=b 求 P(x4=1/x3=0)。 解： 例 平穩(wěn)性 bxxPxxP )1,0()1,0( 2143pbxPxxPxxP /)0(/)1,0()0/1( 34334 pbxPxxPxxP /)0(/)1,0()0/1( 12112 3.3.1 離散平穩(wěn)信源 (4) 對于平穩(wěn)信源，條件概率也是平穩(wěn)的。一般地，有 平穩(wěn)信源的熵與時間起點無關(guān)，即 11( ) ( )i i i N j j j NH X X X H X X X LL),/(),/( 1111 NjjjNjNiiiNi XXXXHXXXXH ),/1(),/1( 1111 NjjjNjNiiiNi xxxxPxxxxP3.3.1 離散平穩(wěn)信源 (5) 根據(jù)平穩(wěn)性和熵的不增原理 對于 X的 N次擴展源 , 定義平均符號熵為： 。，XHNXH N 成立僅當無記憶信源時等式)()( 1)(1)(1)( 1 NNN XXHNXHNXH 3.3.2 離散平穩(wěn)有記憶信源的熵 (1) )(1lim)(1lim)( 1 NNNNXXHNXHNXH 信源 X的極限符號熵： 簡稱：符號熵 /熵率 3.3.2 離散平穩(wěn)有記憶信源的熵 (2) 1） 不隨 N而增加 2） 3） 不隨 N而增加 4） 存在，且 )/( 11 NN XXXH )/()( 11 NNN XXXHXH )( XH N)( XH )/(lim)(11 NNN XXXHXH 說明：有記憶信源的符號也可通過計算極限條件熵得到 定理 3.3.1： 任意離散平穩(wěn)信源，若 )(1 XH3.3.2 離散平穩(wěn)有記憶信源的熵 (3) )/()/()/( 112111 NNNNNN XXXHXXXHXXXH 1） 信源的平穩(wěn)性 熵的不增原理 這說明對于平穩(wěn)信源，條件越多，條件熵越不增加 3.3.2 離散平穩(wěn)有記憶信源的熵 (4) 2） 只要證明 N個 的和不小于 )( XH N )/( 11 NN XXXHN )/()/()/()()()(11111211NNNNNNXXXHNXXXHXXHXHXXHXNH)/()( 11 NNN XXXHXH 平均符號熵不小于條件熵 3.3.2 離散平穩(wěn)有記憶信源的熵 (5) )()()1()/()()1()(1111XHXHNXXXHXHNXHNNNNNNN )()( 1 XHXH NN 3） )( XNH N )/()( 1111 NNN XXXHXXH 由于 平均符號熵不隨序列的長度而增加 根據(jù)平均符號熵的定義和 2）的結(jié)果，有 3.3.2 離散平穩(wěn)有記憶信源的熵 (6) )()()(0 11 XHXHXH NN )()(lim0 1 XHXH NN 存在即 )( XH )()() 11)( jNNNjN XXXXHXHjN 計算（)/()/()11111 NNjNjN XXXHXXXH，的結(jié)果與平穩(wěn)性利用)/()1()()() 1111)( NNNjN XXXHjXXHXHjN （)/(1)(1)( 1111)( NNNjN XXXHjN jXXHjNXH 4） 通過以上證明可得， )/()/()( 111111 jNjNNNN XXXHXXXHXXH 3.3.2 離散平穩(wěn)有記憶信源的熵 (7) 先令 ，后令 ，得 另外，由（ 2）的結(jié)果，當 時 ,有 所以 證畢。 j N )/(l i m)(11 NNN XXXHXH N)/(l i m)( 11 NNN XXXHXH )/(l i m)( 11 NNN XXXHXH 3.3.2 離散平穩(wěn)有記憶信源的熵 (8) 該定理提供了通過計算極限條件熵得到信源符號熵的方法；這樣，當信源為有限記憶時，極限條件熵的計算要比極限平均符號熵的計算容易得多。 極限熵等于最小的平均符號熵。 定理 3.3.1的注釋： 3.3.2 離散平穩(wěn)有記憶信源的熵 (9) 馬氏鏈的基本概念 齊次馬氏鏈 馬氏鏈狀態(tài)分類 馬氏鏈的平穩(wěn)分布 3.4 有限狀態(tài)馬爾可夫鏈 隨機序列 每個隨機變量 僅依賴于 0, nx n)1( nx n 1nx定義： 3.4.1 馬氏鏈的基本概念 (1) 隨機變量 ：馬氏鏈在 n時刻的狀態(tài) ：狀態(tài) 的集合 S：狀態(tài)集合 nxJ,1 J,1 /,/ 1021 ixjxpmxkxixjxp nnnnn 1) 一階馬氏鏈的當前狀態(tài)只與前一個狀態(tài)有關(guān) 2) n階馬氏鏈的當前狀態(tài)只與前 n個狀態(tài)有關(guān) 3) 馬氏鏈是時間離散，狀態(tài)也離散的隨機過程 4) 狀態(tài)集合為有限集 有限狀態(tài)馬氏鏈 狀態(tài)集合為無限集 無窮狀態(tài)馬氏鏈 3.4.1 馬氏鏈的基本概念 (2) 描述馬氏鏈的最重要的參數(shù)：狀態(tài)轉(zhuǎn)移概率 對于離散時刻 m、 n，相應(yīng)的狀態(tài)轉(zhuǎn)移概率可表示為： 表示從時刻 m的 i狀態(tài)轉(zhuǎn)移到時刻 n的 j狀態(tài)的概率， m-n表示轉(zhuǎn)移的步數(shù)。 是經(jīng) 步轉(zhuǎn)移的概率。 ),()/( nmpixjxp ijmn ),( nmp ij )( mnmn 3.4.1 馬氏鏈的基本概念 (3) 一步轉(zhuǎn)移概率 K步轉(zhuǎn)移概率 0步轉(zhuǎn)移概率 系統(tǒng)在任何時刻必處于 S中某一狀態(tài) )()/()1,( 1 mpixjxpmmp ijmmij Sj，i，m ,為起始時刻其中)/()()( ixjxpmp mkmkij jijipij 01)0(；Sjinmp ij ,),( 10 jij nmp ；1),(轉(zhuǎn)移概率的主要性質(zhì)： 3.4.1 馬氏鏈的基本概念 (4) 轉(zhuǎn)移概率與起始時刻無關(guān) K步轉(zhuǎn)移概率也與起始時刻無關(guān)，寫成 jijij pp 1,0)(kijp3.4.2 齊次馬氏鏈 (1) ijmmij pixjxpmp )/()( 1JJJJJJijppppppppppP2122221112113.4.2 齊次馬氏鏈 (2) 齊次馬氏鏈的表示方法 轉(zhuǎn)移概率矩陣 狀態(tài)轉(zhuǎn)移圖 由狀態(tài) j 轉(zhuǎn)移到狀態(tài) 2 的概率； 非負 =1 網(wǎng)格圖 狀態(tài)轉(zhuǎn)移圖與矩陣有一一對應(yīng)關(guān)系 每時刻的網(wǎng)格節(jié)點與馬氏鏈的狀態(tài)一一對應(yīng) 2/14/14/14/12/14/13/13/13/1 p3.4.2 齊次馬氏鏈 (3) 3.4.1 一個矩陣，驗證此矩陣對應(yīng)一個齊次馬氏鏈的轉(zhuǎn)移概率矩陣并確定此馬氏鏈的狀態(tài)數(shù) 解： 例 元素非負 狀態(tài)數(shù) =3 每行和為 1 =1 =1 =1 3.4.1續(xù) 畫出此馬氏鏈的網(wǎng)格圖。 解： 例 3.4.2 齊次馬氏鏈 (4) 1 / 31 / 31 / 31 / 31 / 41 / 41 / 41 / 41 / 41 / 21 / 21 / 2m m + 1 m + 2s1s2s33.7.1續(xù) 畫出此馬氏鏈的狀態(tài)轉(zhuǎn)移圖 解： 例 3.4.2 齊次馬氏鏈 (5) 1 3 2 1 3 1 4 1 3 1 4 1 4 1 4 1 3 1 2 1 2 3.7.1續(xù) 求從狀態(tài) 3到狀態(tài) 2的 2步轉(zhuǎn)移概率 解： 例 S 2 1/4 1/3 S 2 S 3 S 3 S 1 1/2 1/2 1/4 1/4 3.4.2 齊次馬氏鏈 (6) 1) 計算從 m時刻從 s3經(jīng) m+1時刻某狀態(tài) sk到 m+2時刻s2的轉(zhuǎn)移概率 2) 對 1）中計算的經(jīng) m+1時刻的所有狀態(tài) sk（ k=1， 2，3）概率相加，得到所求結(jié)果。計算得 31412121413141/322 sxsxp mm下面分兩步來計算 : 3.4.2 齊次馬氏鏈 (7) 1) 計算從狀態(tài) i到狀態(tài) j的 2步轉(zhuǎn)移概率可通過下式 : Kolmogorov-Chapman方程 (1) 由此例可以看出 : kkjikij ppp)2(2) 是 的第 (i,j)個元素 )2(ijp2P3) 是 的 m次冪 的第 (i,j)個元素 )(mijp PmP4) knkjmiknmijnmnm pppPPP )()()(, )0()0(2)0(1)0( Jpppp , )()(2)(1)( kJkkk pppp mkmkk PpPpP )()0()(Kolmogorov-Chapman方程 (2) 5) 設(shè)馬氏鏈的初始狀態(tài)概率分布為 其中 J為狀態(tài)數(shù)，經(jīng) k步轉(zhuǎn)移后的狀態(tài)概率分布為，則有 : 因此，一個齊次馬氏鏈，當初始狀態(tài)概率分布給定后，可計算轉(zhuǎn)移后任何時刻的狀態(tài)概率分布。 3.4.2 設(shè)例 3.4.1中馬氏鏈的初始狀態(tài)的概率分布為 1/2、 1/4、 1/4，分別求 1步轉(zhuǎn)移后和 2步轉(zhuǎn)移后的狀態(tài)的概率分布。 解： 例 Kolmogorov-Chapman方程 (2) 2/14/14/14/12/14/13/13/13/14/14/12/1)0()1( Ppp 48/1748/1724/7 48/193/148/133/148/1948/1336/1336/1318/54/14/12/12)0()2( Ppp 5 7 6/2 0 95 7 6/2 0 92 8 8/793.4.3 馬氏鏈狀態(tài)分類 (1) 若對某一 n1，有 ，則稱狀態(tài) j可由狀態(tài)i到達，記為 i j 如果 ，且 ，則稱狀態(tài) i與狀態(tài) j可互通，記為 定義每個狀態(tài)都與該狀態(tài)本身互通，即互通關(guān)系滿足自反性 互通關(guān)系還滿足對稱性和傳遞性 0)( nijpji ji ij S8S1 0S1 1S9S7S6S4S5S3S2S13.4.3 馬氏鏈狀態(tài)分類 (2) 3.4.3 按互通性將狀態(tài)分成若干類（子集） 解： 例 11 sC 22 sC , 765433 sssssC , 1110984 ssssC 3.4.3 馬氏鏈狀態(tài)分類 (3) 常返態(tài) 過渡態(tài) 周期的 非周期 0,1: )( niipnn最大公約數(shù) id1 id 1 id3.4.3 馬氏鏈狀態(tài)分類 (4) 對任何馬氏鏈（有限或無限可數(shù)狀態(tài)），同一類中所有狀態(tài)都有相同周期。 定理 3.4.1： 非周期的常返態(tài)稱為遍歷態(tài) 定義 : 若對任意整數(shù) m,n,馬氏鏈的狀態(tài)分布滿足 則稱 為平穩(wěn)分布，或穩(wěn)態(tài)分布 其中， 為平穩(wěn)分布行矢量 inm ixPixP )()( i iijij Jjp ),2,1( 3.4.4 馬氏鏈 的平穩(wěn)分布 (1) (3.4.11) TT P 12, , , TJ Llim eP kk的矩陣都等于是一個每行都相同 ）（P kk lim 3.4.4 馬氏鏈 的平穩(wěn)分布 (2) 平穩(wěn)馬氏鏈 定理 3.4.2 如果一個遍歷有限狀態(tài)馬氏鏈的轉(zhuǎn)移概率矩陣為 P，那么 為平穩(wěn)分布行矢量維列矢量為其中 ,111 。J，e， t, )0()0(2)0(1)0( Jpppp )( np(3.4.12) 對于遍歷馬氏鏈，無論初始分布如何，當轉(zhuǎn)移步數(shù)足夠大時，狀態(tài)概率分布總是趨于穩(wěn)定值，與初始狀態(tài)概率分布無關(guān) 。 , )()(2)(1)( nJnnn pppp )0(p limlim 21)0()0()( JkkkkepPpp 3.4.4 馬氏鏈 的平穩(wěn)分布 (3) nPnP3.4.4 馬氏鏈 的平穩(wěn)分布 (4) 對于有限狀態(tài)馬氏鏈，穩(wěn)態(tài)分布恒存在 如果馬氏鏈中僅存在一個常返類，則方程 (3.4.11)的解是唯一的；如果存在 r個常返類，則具有 r個線性獨立的矢量解 如果馬氏鏈中僅存在一個常返類而且是非周期的（即遍歷的），則 (3.4.12)式成立；如果有多個常返類，但都是非周期的，則 也收斂，但矩陣的每行可能不同；如果馬氏鏈具有一個或多個周期常返類，則 不收斂 02/12/16/13/12/1100 P3.4.4 馬氏鏈 的平穩(wěn)分布 (5) 3.4.4 一馬氏鏈的轉(zhuǎn)移概率矩陣如下，問此馬氏鏈是否具有遍歷性并求平穩(wěn)分布和 的值 解： 例 kk P lim 1 2 3 1 2 1 3 1 2 1 2 1 6 1 )02/12/16/13/12/1100 321321 1321 21/87/23/13213.4.4 馬氏鏈 的平穩(wěn)分布 (6) 21/87/23/121/87/23/121/87/23/1limkkP一馬氏鏈的狀態(tài)轉(zhuǎn)移矩陣如下，確定它的 n次冪是否收斂并求其平穩(wěn)分布 0110 P01 10 2121 121 2121 不收斂有唯一平穩(wěn)分布nP )1()2(2 周期返類馬氏鏈包含一個周期常 ，3.4.4 馬氏鏈 的平穩(wěn)分布 (7) 3.4.5 解： 例 1 1 1 2 kP 2 12 kP 馬氏源的基本概念 馬氏源的產(chǎn)生模型 馬氏源 N次擴展源熵的計算 馬氏源符號熵的計算 3.5 馬爾可夫信源 111 / , 0l l k lp s i x a s j 當前時刻輸出符號的概率僅與當前時刻的信源狀態(tài)有關(guān) 當前時刻的信源狀態(tài)由前一時刻信源狀態(tài)和前一時刻輸出符號唯一確定。 馬氏源的定義： ,/ 11 lllkllkl sxjsaxpjsaxp3.5.1馬氏源的基本概念 (1) 給定二階馬氏源符號集 A=0， 1，轉(zhuǎn)移概率分別為： p(0/00)=p(1/11)=0.8，p(1/00)=P(0/11)=0.2，p(0/01)=p(0/10)=p(1/01)=p(1/10)=0.5，確定該馬氏源的狀態(tài)，寫出狀態(tài)轉(zhuǎn)移矩陣，畫出信源的狀態(tài)轉(zhuǎn)移圖。 3.5.1 例 3.5.1馬氏源的基本概念 (2) 解： 8.02.000005.05.05.05.000002.08.0 PS3S2S11 :0 . 50 ：0. 51: 0 .2S01 ：0. 80 ：0. 50 ：0. 81 ：0. 5 0 ：0. 23.5.1馬氏源的基本概念 (3) 1) m階馬氏鏈的符號轉(zhuǎn)移概率已給定 2) 做 m長符號序列到信源狀態(tài)的映射 ， 取遍， i=1,m； 狀態(tài)取自 ， 為狀態(tài)數(shù)； 3) 符號轉(zhuǎn)移概率轉(zhuǎn)換成狀態(tài)轉(zhuǎn)移概率 其中 4) 得到一階馬氏源模型： )/( 11 mm xxxp 1inx A a a L其 中 取 自jm sxx ）（ 1 ix1nA a a Lmnjs 12 , , mm nA L1 1 1( / ) ( / )m m j jp x x x p s s Ljm sxx ）（ 12 1 1mjx x sL（）12( / ) , 1 , . . . ,mnmlkp k l n Lm階馬氏源的處理方法 3.5.2 馬氏源的產(chǎn)生模型 (1) 設(shè)獨立隨機序列 ， ， ， ， 隨機序列 與 的關(guān)系為 其中 為模 2加；問：（ 1）隨機序列 是否為馬氏鏈？（ 2）如果是馬氏鏈，那么求狀態(tài)轉(zhuǎn)移概率并畫狀態(tài)轉(zhuǎn)移概率圖。 3.5.2 例 3.5.2 馬氏源的產(chǎn)生模型 (2) nx ( 0 )np x p ( 1 )np x q 1pq ny nx 12n n n ny x y y 解： 3.5.2 馬氏源的產(chǎn)生模型 (3) 序列 為有記憶序列，在 n時刻的取值僅與 n-1時刻與 n-2時刻有關(guān)，而與以前的時間無關(guān)，因此 構(gòu)成二階馬氏鏈。 ny ny00111001pppqqqpq有一個二元馬氏鏈 X，符號集為 0， 1，其中符號轉(zhuǎn)移概率為 ， ；計算該信源三次擴展源的所有符號的概率。 3.5.3 例 3.5.3 馬氏鏈 N次擴展源的熵的計算 (1) ( 0 / 0 ) 0 . 8p (1 / 1 ) 0 . 7p 解： 首先求平穩(wěn)分布 0 1 0 1 0 . 8 0 . 20 . 3 0 . 7p p p p 01 1pp 013 / 5 , 2 / 5pp3.5.3 馬氏鏈 N次擴展源的熵的計算 (2) 類似得到 0( 0 0 0 ) ( 0 / 0 ) ( 0 / 0 ) 0 . 6 0 . 8 0 . 8 0 . 3 8 4p p p p ( 0 0 1 ) 0 . 6 0 . 8 0 . 2 0 . 0 9 6p ( 1 0 ) 0 . 6 0 . 2 0 . 3 0 . 0 3 6p ( 0 1 1 ) 0 . 6 0 . 2 0 . 7 0 . 0 8 4p ( 1 0 0 ) 0 . 4 0 . 3 0 . 8 0 . 0 9 6p ( 1 0 1 ) 0 . 4 0 . 3 0 . 2 0 . 0 2 4p ( 1 1 0 ) . 4 0 . 7 0 . 3 0 . 0 8 4p ( 1 1 1 ) 0 . 4 0 . 7 0 . 7 0 . 1 9 6p 做映射 ， i = 0,N-m，其中 i為時間標號， j為狀態(tài)序號。 H(X1X2XN) = H(Sm+1Sm+2SN+1) 其中， Si=Xi-mXi-m+1Xi-1 利用熵的可加性，將上式展開，并利用馬氏性得 )(11 jsxx imimi ）（ H(X1X2X N) = H(Sm+1)+ H(Sm+2/Sm+1)+H(S N+1 /Sm+1Sm+2S N) 3.5.3 馬氏鏈 N次擴展源的熵的計算 (3) = H(Sm+1)+ H(Sm+2/Sm+1)+H(S N+1 /SN) = H(Sm+1)+ )/(11Nmiii SSH )/(11Nmiii SSH )(/)(l og)(/)()( 11111jskspjskspjsp iiNmiiinkinjmm NmijinjHjspm1 1)()(/)(l o g)(/)( 111 jskspjskspH iinkiijm3.5.3 馬氏鏈 N次擴展源的熵的計算 (4) 該項由狀態(tài)轉(zhuǎn)移概率矩陣 P的第 j行所確定。寫成矩陣形式 111( / ) ( ) NNti i ii m i mH S S p s h 11 2 1 10( ) ( ) ( ) NmitN m miH X X X H S p s P h L其中， ,為第 i狀態(tài)概率分布行矢量 ; ,為行矢量 ,其中每個元素由 P的每一行所確定。 )()2()1()( miiii nspspspSp 12 mnh H H H L3.5.3 馬氏鏈 N次擴展源的熵的計算 (5) 如果起始狀態(tài)概率為平穩(wěn)分布 , 則 N次擴展源的平均符號熵為 : tN hmNHXXXH )()()( 21 )()(1)(1)( 21 tNN hmNHNXXXHNXH 3.5.3 馬氏鏈 N次擴展源的熵的計算 (6) 當信源從某一狀態(tài)轉(zhuǎn)移到另一狀態(tài)時 , 輸出符號唯一 , 則一個 m階馬氏源的符號熵為 : m階馬氏源符號熵僅由平穩(wěn)分布和狀態(tài)轉(zhuǎn)移概率矩陣所決定。 )(l i m)( tNN hXHXH 3.5.4 馬氏源符號熵的計算 (1) 計算方法 1： 當信源從某一狀態(tài)轉(zhuǎn)移到另一個新狀態(tài)時，存在多個信源序列對應(yīng)一個狀態(tài)。這樣由狀態(tài)轉(zhuǎn)移概率矩陣不能確定信源的熵，而只能以狀態(tài)條件下信源的輸出符號的概率求信源的熵。 給定當前信源狀態(tài)條件下信源的輸出符號熵為： )(l o g)()/(1ijniij apapjsXH 為信源符號集其中 ，AaaA，a ni ),( 1 計算方法 2： 3.5.4 馬氏源符號熵的計算 (2) 在給定某特殊狀態(tài) s1=j和以前的輸出 X1,X2,Xm-1條件下當前輸出符號 Xm的熵滿足： 對 S1取平均 )/()/(),/( 11111 isXHjsispXXjsXHJimmm )/()()/()/()(),/(11111111isXHispisXHjsispjspXXSXHJimJimJjmm引理 3.5.1： 3.5.4 馬氏源符號熵的計算 (3) 對于平穩(wěn)信源，狀態(tài)概率與時間起點無關(guān)，所以 對于 m階平穩(wěn)馬氏源的符號熵為 利用平穩(wěn)性及馬氏性，有 )/()(),/(1111 isXHispXXSXHJimm )/(lim 11 NNNXXXHH )/( 11 mm XXXH 1 mHH3.5.4 馬氏源符號熵的計算 (4) 當 給定條件下， 與以前的狀態(tài)無關(guān) 為狀態(tài)平穩(wěn)分布行矢量 h的各分量由狀態(tài)轉(zhuǎn)移概率矩陣的每一行得出的條件熵 mXX 1 1mX),/()/( 11111 mmmm XXSXHXXXH )/()(1isXHispJi th 3.5.4 馬氏源符號熵的計算 (5) 3.5.4 馬氏源符號熵的計算 (6) 定理 3.5.2： 平穩(wěn)馬氏源的符號熵為 ()HX1( / )JiiH X s i幾點注釋 ： 1)定理 3.5.2給出了馬氏源符號熵的計算方法： 先求每個狀態(tài)下的條件符號熵，再用狀態(tài)的概 率平均； 2)計算符號熵要用狀態(tài)的平穩(wěn)分布； 3)單位為比特 /符號。 3.5.4 馬氏源符號熵的計算 (7) thXH )( 求信源的極限符號熵 3.5.1 續(xù) 解： 例 25.0l og5.05.0l og5.07122.0l og2.08.0l og8.014 5 符號/80 1.0 bi t3.5.4 馬氏源符號熵的計算 (8) 3.6 信源的相關(guān)性與剩余度 信源的相關(guān)性 信源剩余度（冗余度） 自然語言的相關(guān)性和剩余度 信源的相關(guān)性就是信源符號間的依賴程度。設(shè)信源有 m個符號，那末對于不同情況可以分別計算信源的熵為： （符號獨立等概） （獨立信源） （一階馬氏源） （ n-1階馬氏源） 由平穩(wěn)性與熵的不增原理，有： 可見，符號相關(guān)程度越大，熵越小，反之亦