【文章內(nèi)容簡介】 1 112111121???????????????? ?? ??qiqjiiijijiqqqqaaPaaPaPaaPaaaaaaaaxxPXX ?聯(lián)合熵 ? ? ? ? ? ?? ?? ???qiqjjiji aaPaaPXXH1 121 l o g 表示原來信源 X輸出任意一對可能的消息的共熵，可用 1/2H(X1X2)作為二維離散平穩(wěn)信源 X的信息熵的近似值 條件熵 ? 符號之間有依賴性，可以求得已知前面一個(gè)符號 X1=ai時(shí)，信源輸出下一個(gè)符號的平均不確定性 ? 已知前面符號為 X1=ai時(shí)，信源再輸出一個(gè)符號的平均不確定性應(yīng)是對全部可能的符號 aj的不確定性求統(tǒng)計(jì)平均。 ? ? ? ? ? ?ijqjiji aaPaaPaXXH l o g112 ?????續(xù) ? 前面一個(gè)符號有 q種選擇，對某一個(gè) ai存在一個(gè)平均不確定性 H（ X2︱ X1=ai ） ? 對所有的 ai的可能值進(jìn)行統(tǒng)計(jì)平均就得當(dāng)前面一個(gè)符號已知時(shí)，再輸出后面一個(gè)符號的總的平均不確定性 ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ?ijqiqjjiijijqiqjiiqiiaaPaaPaaPaaPaPaXXHaPXXHl o gl o g1 11 112112? ?? ??? ?? ????????例題 ? 某一二維離散平穩(wěn)信源 并設(shè)輸出的符號只與前一 個(gè)符號有關(guān)，可用聯(lián)合概率 P（ ai aj ）給出他們的關(guān)聯(lián)程度，如表所示。 可以計(jì)算得出聯(lián)合熵、條件熵、平均符號熵。 ? ? ? ??? ???????????????? 31141943611210iiaPxPX 且計(jì)算結(jié)果 1 ? ? ? ? ? ? )/(54 og31符號比特??? ??iii aPaPXH? ? ? ? ? ? )/(8 7 o g313112 符號比特??? ? ?? ?iji jji aaPaaPXXH? ? ? ? ? ? )/( o g313121 兩個(gè)符號比特??? ? ?? ?jii jji aaPaaPXXH? ? ? ? ? ? )/( 兩個(gè)符號比特????? XXHXHXXH ，說明了符號之間有依賴性 ? ? ? ?XHXXH ?12計(jì)算結(jié)果 2 ? ? ? ? )/(2 0 212 符號比特?? XXHXH問題：在聯(lián)合熵和條件熵中到底哪一個(gè)值更能接近實(shí)際二維離散平穩(wěn)信源的熵？ ? ? ? ? ? ? )/( 兩個(gè)符號比特????? XXHXHXXH? ? ? ?XHXH ?2擴(kuò)展 N維離散平穩(wěn)有記憶信源 存在一個(gè) N維離散平穩(wěn)有記憶信源 X=X1X2…X N，且Xi∈ {x1x2…x q} 對于上述 N維離散平穩(wěn)有記憶信源 X，可以得出如下一些結(jié)論： X P（ x） ＝ x1 x2 … x q P(x1) P(x2) … P(x q) 離散平穩(wěn)信源性質(zhì) 聯(lián)合熵 /序列熵 H(X) = H(X1X2…X N) = H(X1) + H(X2 / X1) + H(X3 / X1X2) + … + H(X N / X1X2…X N1)。 N長的信源符號序列中平均每個(gè)信源符號所攜帶的信息量為平均符號熵： ? 若信源退化為無記憶時(shí)，有 H(X) = H(X1) + H(X2) + … + H(XN) 。 ? 若進(jìn)一步滿足平穩(wěn)性，則有 ∴ 。無記憶信源是有記憶信源的一種特例。 1 2 NNH ( X X X )H ( )H ( )NN??XXH ( ) N H ( X )?XNH ( )H ( )N?XX續(xù) 離散平穩(wěn)信源 具有以下性質(zhì)： ? 條件熵 H(XN / X1X2…X N1)隨 N的增加而遞減，即： H(XN / X1X2…X N1) ≤ H(XN1 / X1X2…X N2) ≤ H(XN2 / X1X2…X N3) … ≤ H(X3 / X1X2) ≤ H(X2 / X1) ≤ H(X2) ＝ H(X1) 離散平穩(wěn)信源的極限熵 ? N給定時(shí)，平均符號熵 ≥條件熵：即 HN(X) ≥ H(XN / X1X2…X N1) ? 平均符號熵 HN(X)隨 N的增加而遞減 ? 存在，且： 我們稱 H∞為離散平穩(wěn)有記憶信源的 極限熵 或極限信息量，也稱為平穩(wěn)信源的熵率。 ? H0(X) ≥ H1(X) ≥ H2(X) ≥ … ≥ H ∞(X) 其中： H0(X)為等概率無記憶信源的單個(gè)符號的熵； H1(X)為一般（不等概率）無記憶信源的單個(gè)符號的熵； … 依次類推。 l im ( )NnH H X? ???1 2 1l im ( ) l im ( / )N N N NnnH H X H X X X X??? ? ? ???結(jié)論 ? 離散平穩(wěn)信源的極限熵等于有限記憶長度 m的條件熵。 ? 對于有限記憶長度的離散平穩(wěn)信源可用有限記憶長度的條件熵對離散平穩(wěn)信源進(jìn)行信息測度。 ? ?? ?? ? ? ? ? ?mmmmm mm iiiiiii i iiimmNNNaaaPaaaPaaPXXXXHXXXXHH. . .l o g. . .. . .. . .. . .. . .lim11111 111 1 1211121???? ? ?? ? ?????????? 馬爾可夫信源 ? 在非平穩(wěn)離散信源中有一類特殊的信源。這類信源輸出的符號序列中符號之間的依賴關(guān)系是有限的，它滿足馬爾可夫鏈的性質(zhì)，因此可用馬爾可夫鏈來處理。 m階馬爾可夫信源的定義 ? 若信源輸出的符號序列和信源所處的狀態(tài)滿足下列兩個(gè)條件： （ 1） 某一時(shí)刻信源符號的輸出只與此刻信源所處的狀態(tài)有關(guān)，而與以前的狀態(tài)及以前的輸出符號都無關(guān)， 即 P(xl=ak|sl=Ei,xi1=ak1,sl1=Ej,… )=P(xl=ak|sl=Ei) 當(dāng)具有時(shí)齊性時(shí)，有 P(xl=ak|sl=Ei)=P(ak|Ei)及 ? ? 1EaPAa ikk???（ 2） 信源某 l時(shí)刻所處的狀態(tài)由當(dāng)前的輸出符號和前一時(shí)刻（ l1）信源的狀態(tài)唯一決定。 即： P(sl=Ej|xl=ak sl1=Ei)= 則此信源稱為 馬爾可夫信源 。 ?????Aa 1EE,E 0kji? 定義中 P(xl=ak|sl=Ei)是在第 l時(shí)刻，信源處于狀態(tài) Ei時(shí)，輸出符號 ak的概率。 ? Pij(l)=P(sl=Ej|sl1=Ei)是假設(shè)第 (l1)時(shí)刻信源處于 Ei狀態(tài)，在下一時(shí)刻狀態(tài)轉(zhuǎn)移到 Ej的狀態(tài)轉(zhuǎn)移概率。 ? 一般情況下，狀態(tài)轉(zhuǎn)移概率和已知狀態(tài)輸出符號的概率均與時(shí)刻 l有關(guān)，若這些概率與時(shí)刻 l無關(guān)時(shí)，即滿足 P(xl=ak|sl=Ei)=P(ak|Ei)和Pij=P(Ej|=Ei)時(shí)，則稱為時(shí)齊的或齊次的。 ? 條件（ 2）表明，若信源處于某一狀態(tài) Ei，當(dāng)它輸出一個(gè)符號后，所處的狀態(tài)就變了，一定從狀態(tài) Ei轉(zhuǎn)移到另一狀態(tài)。 ? 狀態(tài)的轉(zhuǎn)移依賴于輸出的信源符號，因此任何時(shí)刻信源處在什么狀態(tài)完全由前一時(shí)刻的狀態(tài)和輸出的符號決定。又因 條件概率 P(ak|Ei)已給定，所以狀態(tài)之間的轉(zhuǎn)移有一定的概率分布，并可求得狀態(tài)的一步轉(zhuǎn)移概率 P(Ej|Ei)。 ? 這種信源的狀態(tài)序列在數(shù)學(xué)模型上可以作為時(shí)齊馬爾可夫鏈來處理，可以用馬爾可夫鏈的狀態(tài)轉(zhuǎn)移圖來描述信源。 見例 ? 例題 a3=1/4 a1=1/4 a3=1/2 a2=1/2 a3=1/4 a2=1/4 a1=1/2 E1 E2 E3 E4 E5 a2=3/4 a1=1 a2=1/4 a3=1/2 ? P(a1︱ E1)=1/2, P(a2︱ E2)=1/2 ? P(a1︱ E5)=1/4, P(a2︱ E1)=1/4 ? P(a3︱ E2)=1/2, P(a2︱ E5)=1/4 ? P(a3︱ E1)=1/4, P(a2︱ E3)=3/4 ? P(a3︱ E5)=1/2, P(a1︱ E4)=1 ? P(a3︱ E3)=1/4,其他 P(ak︱ Ei)=0 ? 可見，滿足 （ i=1,2,3,4,5） ? ? 131???kik EaP續(xù) ? 圖中可得： 滿足條件（ 2） ? ?? ?? ?? ??????????????????????????????. . . . . .01101132112211111112EsaxEsPEsaxEsPEsaxEsPEsaxEsPllllllllllll根據(jù)已知可得： ? 狀態(tài)的一步轉(zhuǎn)移概率 P（ E1︱ E1） =1/2 ， P（ E2︱ E2） =1/2 P（ E3︱ E3） =1/4， P（ E2︱ E1） =1/4 P（ E3︱ E2） =1/2， P（ E5︱ E4） =1 P（ E4︱ E1） =1/4， P（ E2︱ E3） =3/4 P（ E5︱ E5） =1/4， P（ Ej︱ Ei） =0 P（ E4︱ E5） = P（ a2︱ E5)+P（ E3︱ E5） = 190。 信源滿足條件（ 1）和（ 2），所以是馬爾可夫信源 m階馬爾可夫信源的定義 若隨機(jī)變量序列 X中的任一時(shí)刻第 m+1個(gè)隨機(jī)變量 Xm+1只依賴于它前面已發(fā)生的 m個(gè)隨機(jī)變量 X1…X m，而與更前面的隨機(jī)變量無關(guān)，則稱這種信源為 m階馬爾可夫信源（簡寫為 m階 M信源）， 依賴長度 （也稱記憶長度）為m+1。 P(xkN|xk1xk2…x k(N－ 1)) = P(xkN|xk(N－ m) xk(N－ m+1) …x k(N－ 1)) （ m階 M信源） = P(xk(m+1)|xk1xk2 …x km) 其中： k1, k2, … , k m, … , k N = 1, 2, …, q m階馬爾可夫信源 ? 對 m階 M信源的數(shù)學(xué)描述為： 當(dāng) m=1時(shí)，任何時(shí)刻信源符號發(fā)出的概率只與前面一個(gè)符號有關(guān)，則稱為一階馬爾可夫信源。 ? m階 M信源任何時(shí)刻符號發(fā)生的概率只與前面 m個(gè)符號有關(guān)，我們把這 m個(gè)符號序列看作信源在此時(shí)刻所處的狀態(tài)。由于信源符號集合 X＝ {x1, x2, …, x q}共有 q個(gè)符號，因此信源的狀態(tài)共有 qm個(gè)，信源輸出依賴長度為 m+1的隨機(jī)序列就可轉(zhuǎn)換成對應(yīng)的狀態(tài)隨機(jī)序列。 X P ＝ x1 , x2 , … , x q P(xk(m+1) / xk1, xk2, … x km) 例題 ? 有一個(gè)二元二階馬爾可夫信源，其信源符號集為 [0,1]，條件概率定為 P（ 0︱ 00） = P（ 1︱ 11） = P（ 1︱ 00） = P（ 0︱ 11） = P（ 0︱ 01） = P（ 0︱ 10） = P（ 1︱ 01） = P（ 1︱ 10） = 信源任何時(shí)刻輸出什么符號只與前兩個(gè)符號有關(guān)，與更前面的符號無關(guān)。 續(xù) ? 根據(jù)給定的條件概率，可以求得狀態(tài)之間的轉(zhuǎn)移概率（一步轉(zhuǎn)移概率） P（ E1︱ E1） = P（ E4︱ E4） = P（ E2︱ E1） = P（ E3︱ E4） = P（ E3︱ E2） = P（ E2︱ E