第2章信源熵--馬爾科夫信源及極限熵

1、信源嫡借恵論導(dǎo)論通借與信恵工程學(xué)院楊海芬yanghf 2013年8月單符號離散信源聯(lián)合炳 多苻號離散借源聯(lián)合炳;條件炳離散平穩(wěn)借源、聯(lián)合炳離散平穩(wěn)天/記憶借源、聯(lián)合炳口馬爾科夫信源及其極限炳 I冗余度與結(jié)構(gòu)借息I信源嫡信源嫡馬爾科夫信源及其極限炳信源嫡信源嫡 安德雷馬爾可夫(Andrei Markov 1856 1922),俄國 數(shù)學(xué)家。 1874年馬爾可夫入圣彼得堡大學(xué). 師從切比婦夫,信源嫡 開創(chuàng)了隨機過程這個新的領(lǐng)域， 以他的名字命名的旦 爾可夫鏈在現(xiàn)代工程、自然科學(xué)和社會科個領(lǐng)域 都有很廣狂的應(yīng)用。馬爾可夫性:一個過程的 “將來” 僅依賴 “現(xiàn)在” 而不依 馬爾可夫鏈的應(yīng)用 排隊理論和

2、統(tǒng)計學(xué)中的建模，還可作為信號棋型用 于炳編碼技術(shù).如蘇術(shù)編碼 著名的蚩數(shù)據(jù)壓縮算法就使用了 馬爾可夫鏈與 類似于蘇術(shù)編碼的區(qū)間編：生物學(xué)應(yīng)用， 人口過程. 可以翔助模擬生物人 口過程的班模。 隱蔽馬爾可夫棋型還被用 于生物借息學(xué).用以編 碼區(qū)域或基因預(yù)測。 馬爾可夫鏈最近的應(yīng)用捷在地理統(tǒng)計學(xué)(geostatistics)中，被稱為是“馬扳可夫鏈地理 統(tǒng)計學(xué)”。仍在發(fā)展過程中。“基于馬爾可夫鏈的我國城鄉(xiāng)居民收入演進(jìn)分析”馬爾科夫借源及其極限螞1、馬爾科夫信源定義N維離散平穩(wěn)信源符號序列中第N個符號只與前m （SN1）個符號相關(guān)，該信源為m階馬爾科夫信源。馬爾科夫信源是離散平穩(wěn)有限記憶信源，其記憶

3、 喪度為m。*m階馬爾科夫信源符號序列的長度N=m+loxm+1/x1x2-.xmP(Xm+1/X,X2.Xm)alPJa2P(a2)anm+,P(a+J其中，坷二/%吋i二1,2,!T 也,叮廣1,2,n0<P(ai) = P(xim+i/xixi2.xiJ<ln且£p(x扁/Xi如二1'm+1 二 1信源嫡曲6信源嫡曲6爾科夫信源可以用狀態(tài)轉(zhuǎn)移圖表示嗎？信源嫡256引入狀態(tài)s過態(tài)S取值于集合他爪2,sjip 29 * * * ，nSi 二 x»Xi2 Xim i = l,2,十現(xiàn)態(tài)S取值于集合s1,s2,-,snmSj=X- X-x； = X. X-

4、x；Jl J2Jm12 X3】m+lj = l,2,十 j"，,h =l，2,n信源嫡256x3/x1x2P(X3/X!X2)玖坷）二 P（XiJXj兀xj 二 Pxj-Xg/XN xj 二阻兀Xjm/x/i2丿二卩（小）用狀態(tài)表示的m階馬爾科夫信源等效于用狀態(tài)轉(zhuǎn)移 圖描述的馬爾科夫鏈。0/001/000/011/010/101/100/111/110.80.20.50.5 0.50.50.20.8狀態(tài)轉(zhuǎn)移圖設(shè)狀態(tài)S=00、s2=01P(O/OO) = P(OO/OO) 二 P(S / S) = 0.8P(l/00)二 P(01/00) 二 P(s2/S)二 0.2P(0/01) =

5、 P(10/01) 二 P(s3 /s2)二 0.5P(l/01) = P(ll/01)二 P(&4 /勺)=0 5信源爛 SjX0 > sXI信源爛P(0/10) = P(00/10)二 P(S / s3) =0.5P(l/10) = P(01/10)=P(s? / s3) = 0.5P(0/ll) = P(10/ll) 二 P(s3 / s4)二 0.2P(1/11) = P(11/11)= P(s4/s4) = 0.82560.80.° /02信源嫡2、馬爾科夫鏈的遍歷定理馬爾科夫鏈的遍歷從任何一個狀態(tài)出發(fā)，可以通過有限步到達(dá)任何If其他狀態(tài)，該馬爾科夫鏈?zhǔn)潜闅v的

6、。 非遍歷的馬爾科夫鏈存在吸收態(tài)。非遍歷馬爾科夫鏈的例子馬爾科夫鏈的遍歷定理P(Sj)二工P(sJP(Sj/sJj 二 1,2,i二 10WP(Sj)51,且fp(Sj) = lj二 13、馬爾科夫1皆源的極限炳信源嫡信源嫡極限炳定理itN->oo時，N維離散平穩(wěn)信源平均符號爛的極限存 在且等于N階條件爛的極限值，稱為N維離散平穩(wěn) 信源的極限爛，用Hg表示。Hg = lim Hn(X/2XQ = lim HCXX.-.X)NtqoNts即使N-oo, m階馬爾科夫信源符號序列的有效長 度只有m+1。=H(Xn /X&2 XnJ 二 H(Xm+1 /XtX2-XJNts信源嫡曲6H

7、s = lim!j(XN/X|X2XN_J 二Haw/XiXz.XJn nn二HlP(Xi"2 九丿10gP(Xim/X“Xi2Xj11 二 1】2=1 ljn+1 二 1n nnXPgXi2叭少血丸趙玖九/強乜 i=li2=l im+i=l其中 P(Xi“2 xj 二 P(sJP(x. /x. x.x； ) = P(x. x.x；/x. x.x；)lm+1 】1】2Im】2】3m+】1】2】m二 P(Xj0j2 Xjm/Xi®2 Xim)=P(Sj/Si)強調(diào)m階馬爾科夫信源的長度特征，一般其極限爛 兀記為Hm+inm n皿H® =兔+嚴(yán)P（s JPG/ s J

8、 log P（s/）i=l j=l求m階條件圖示二元二階馬爾科夫信源的極限爛信源嫡遍歷定理P(S) = P(S)P(S/SJ + P(S2)P(S/S2) + P(s3)P(s1/s3) + P(s4)P(s1/s4) = O.8P(S) + O.5P(S3)P(s2) = P(s1)P(s2/s1) + P(s2)P(s2/s2)+ P(s3)P(s2/s3) + P(s4)P(s2/s4)= 0.2P(sJ+0.5P(S3)信源嫡P(s3) = P(s1)P(s3/s1) + P(s2)P(s3/s2)+ P(s3)P(s3/s3)+ P(s4)P(s3/s4)二 O.5P(S2)+ O.

9、2P(S4)P(s=P(S )P(S4 /S) + P(S2)P(S4 / S2)+ P(s3)P(s4 / S3) + P(s4)P(s4/s4)= 0.5P(s2) + 0.8P(s4)信源嫡02P(sJ_05P(S3)二 0u.zr(sj - e(s2) +0.5F(s3) = 0 0.5P(s2)-P(s3)+0.2P(s4)-0 0.5P(s2)-0.2P(s4) = 0完備性P(S1) + P(S2) + P(S3) + P(S4)=lP（S1）= P（S=令PG2）= Pg=右信源嫡曲644入二出+產(chǎn)比二-P(* )P(s/ s) log P(s/ 6) i=l j=l二-(0.

10、81og 0.8 + 0.21og 0.2) +£(0.51og 0.5+ 0.5 log 0.5) + £(0.51og 0.5 + 0.5 log 0.5) + £(0.2k)g 0.2 + 0.81og 0.8) = 0.8(bit/symbol)五、冗余度與結(jié)構(gòu)信息1.冗余度信源編碼 信息論的創(chuàng)始人Sha n non提出扌巴數(shù)據(jù)看作是信，電和 冗余度(redundancy)的組合。 如在一份計算機文件中，某些符號會重復(fù)出現(xiàn).某些符號比其他 符號出現(xiàn)得更頻繁.某些字符總是在各數(shù)據(jù)塊中可預(yù)見的位置上 出現(xiàn)等，這些冗余部分便可在數(shù)據(jù)編碼中 除去或減少。 相鄰的數(shù)

11、據(jù)之間存在著相關(guān)性。如圖片中常常有色彩均勻的背影, 電視信號的相鄰兩幀之間可能只有少量的 變化影物是不同的，聲 音信號有時"具有一定的規(guī)律生和周期4生等等。 人們由于耳.目 對信號的時間變化和幅度變化的感受能力都有一 定的極限 可利用一些編碼的方法刪去它們，從而達(dá)到減少冗余壓 縮數(shù)據(jù)的目的。 圖像壓縮編碼(1)無損壓縮編碼(2)有損壓縮編碼(3) 混合編碼，如H261, JPEG, MPEG等技術(shù)標(biāo)準(zhǔn) 簡單地說，如果沒有數(shù)據(jù)壓縮技術(shù)，我們就沒法用 WinRAR為 Email中的附件瘦身；如果沒有數(shù)據(jù)壓縮 技術(shù)，市場上的數(shù)碼錄音筆就只能記錄不到 20 分鐘的 語音；如果沒有數(shù)據(jù)壓縮技術(shù)

12、，從Internet上下載一 部電影也許要花半年的時間衡量一個壓縮編碼方法優(yōu)劣的重要指標(biāo)(1)壓縮比要高; (2)算法簡單，硬件實現(xiàn)容易；(3)解壓縮的圖像質(zhì)量 要好。信源嫡信源嫡信道編碼信源嫡信源嫡:也借道前向糾錯編碼(FEC)技術(shù)通過在傳輸碼列中 加入冗余糾錯碼，在一定條件下；通過解碼可以 自動糾正傳輸誤碼，降低接收信號的誤碼車 (BER) o 衡量FEC糾錯能力的指標(biāo)稱為 “FEC編 碼增益”,該增益越強表示糾 錯性能越強。漢明碼、奇偶校驗碼、RS碼、Turbo碼、LDPC夸 糾錯性能、碼事、實現(xiàn)復(fù)雜度信源嫡256信源嫡曲6抽象描述實際信源抽象為N維離散平穩(wěn)信源，H®是其爛率,

13、 即從理論上看，只要傳送H8就可以了。但是這必須掌握信源的全部統(tǒng)計特性，這顯然是 不現(xiàn)實的。實際中，只能掌握有限記憶長度m, 其爛率用!近似，即需要傳送卅叭】 與理論值相比，多傳送了珥+廣兀 由于Hm+pHg,表現(xiàn)在信息傳輸上存在冗余。信源嫡曲6信源嫡曲6信源的m階極限爛+1與N1階極限爛兀的相對差為該信源的冗余度，也叫剩余度。信源嫡曲6信源嫡曲6Hm+1Hm+1-Hw信源的冗余度表示信源可以被壓縮 的程度信源嫡曲6信源嫡曲6或者定義H°-Hg%Ho：相同符號數(shù)的最大值信源嫡曲6信源嫡曲6 正是由于信源存在冗余度，所以存在著進(jìn)一步壓縮的可育邑性。冗余度越大，壓縮潛力越大。它是信源 編

14、碼、數(shù)據(jù)壓縮的畑提與基礎(chǔ)。英文信源的爛率假定源消息含有26個字母和1個空格，忽略標(biāo)點符號和大小寫字母出現(xiàn)的概率是不同的，E最大（13%） , Q和Z最?。ù蠹s0.1%）兩個字母的組合也是非等概的，TH出現(xiàn)最頻繁（3.7%）由此，我們可以構(gòu)建高階的概率轉(zhuǎn)移模型，但是實際上這是不可行的cP（x.Xi,莎2兀3）有27531441個項,為了準(zhǔn)確估計每一個概率，需耍大量的文本分析信源嫡曲6英文信源用m階馬爾可夫信源近似，最大爛及各 階極限爛（1）近似為無記憶信源（零階馬爾可夫信源）且字 母等概率分布最大爛Ho = log 27 « 4.76（bit/symbol）（2）近似為無記憶信源，字母

15、的概率分布零階極限爛(無條件爛)Hj « 4.03(bit/symbol)英文字母前后存在一定的依賴關(guān)系，如t后出現(xiàn)h、 r的可能性較大。(3) 近似為一階馬爾可夫信源，考慮字母的一階 條件概率分布一階極限爛H2« 3.32(bit/symbol)(4) 近似為二階馬爾可夫信源，考慮字母的二階 條件概率分布，二階極限爛H3 «3.10(bit/symbol)(5)近似為全記憶信源(香農(nóng)以m=100估計)，N-1 階極限爛Hs «1.40(bit/symbol)實際信源為全記憶信源，爛率為Hq考慮到可實 現(xiàn)性，一般取有限記憶長度m,爛率用Hm+i近似, 在

16、信息傳輸上存在冗余。信源嫡英文信源的冗余度的計算英文信源近似為無記憶信源且等概時，冗余度Hp-H,Ho4.76-1.404.76= 0.71信源的冗余度表示信源可以被壓縮的程度英文信源近似為無記憶信源但概率分布已知時, 冗余度H廠氏4.03-1.404.03= 0.65英文信源近似為一階馬爾可夫信源，冗余度3.32-L403.32信源嫡英文信源近似為二階馬爾可夫信源，冗余度信源嫡信源嫡比-比h33.10-1.40= 0.55信源嫡幾種主要語言的儲率英語法語徳語西班牙語log2k4.704.704.704.70H(")4.1243.9844.0954.015H(A)1.653.021.081.97冗余度3.051.683.622.73漢語：劉秉偉等（ 2000年）統(tǒng)計了4年以來的人民曰報的語料，得出結(jié)論；零 階嫡、一階嫡、二階爛分別為9.62, 6.1 8和4.89比特2.結(jié)構(gòu)借息定義信源的m階極限爛珥+i與N1階極限爛兀之差為該 信源的結(jié)構(gòu)信息。表示【m+1,8 Hm+1 - Hg信源嫡英文信源近似為無記憶信源且等概時，結(jié)構(gòu)信息Io,s 二 H° -