信息論與編碼第二章

1、 從有效而可靠地傳輸信息的觀點(diǎn)出發(fā)，對組成信息傳輸系統(tǒng)的各個(gè)部分分別進(jìn)行討論。 本章首先討論信源，重點(diǎn)是其統(tǒng)計(jì)特性和數(shù)學(xué)模型，以及離散信源的信息測度熵及其性質(zhì)。引入信息理論的一些基本概念和重要結(jié)論。第二章 離散信源2.1 信源的數(shù)學(xué)模型及分類 只研究信源的輸出，以及信源輸出各種可能消息的不確定性。離散信源離散信源：信源可能發(fā)出的不同符號數(shù)是有限的，或是無限可列的；連續(xù)信源連續(xù)信源：消息的取值是連續(xù)的，即可能出現(xiàn)的消息數(shù)是不可數(shù)的無限值。 樣本空間樣本空間：信源輸出所有消息的集合信源空間信源空間：樣本空間+概率 （概率空間概率空間）完備性描述完備性描述： 用離散型隨機(jī)變量或隨機(jī)矢量來描述信源輸出

2、的消息 qiap11)()(),(),(,: )(:,2121qqapapapaaqxpxpx離散信源 的數(shù)學(xué)模型用連續(xù)型隨機(jī)變量來描述這些消息 )(),(: )(:,xpbaxpxpx)(xpRbaRdxxpdxxp1)()(連續(xù)信源 的數(shù)學(xué)模型 離散信源的簡單情形是信源發(fā)出的消息是由單個(gè)符號構(gòu)成的。擲骰子的結(jié)果作為信源消息，則就構(gòu)成了一個(gè)這樣的信源，其概率空間為： 箱中有赤、橙、黃、青、蘭、紫六種顏色的32只彩球，其中赤16球，澄8球，黃4球，青2球，藍(lán)、紫各1球。有放回抽取： 6/16/16/16/16/16/1)(654321aaaaaaxpx32/132/116/18/14/12/1

3、)(紫藍(lán)青黃橙赤xpx2.2離散信源的自信息和信息熵2.2.1 自信息問題問題：信源發(fā)出某一符號ai后，能提供多少信息量？ 信息如何進(jìn)行度量？ 收到某消息獲得的信息量=不確定性減少的量=收到bj前、后對某事件ai存在的不確定性消除的量=收信前關(guān)于某事件的不確定性（先驗(yàn)不定度）收信后關(guān)于某事件發(fā)生的不確定性（后驗(yàn)不定度） 信息量與事件發(fā)生的不確定性有關(guān)，不確定性與事件發(fā)生的概率有關(guān)，應(yīng)是一個(gè)函數(shù)關(guān)系 。 自信息量 ： ：事件ai發(fā)生的先驗(yàn)概率 )()(iiapfaI)(iap四條公理1、概率大，發(fā)生的可能性大，不確定性小， 是先驗(yàn)概率的單調(diào)遞減函數(shù)；2、必然事件，不含信息量；3、不可能事件發(fā)生了

4、，剌激大，沖擊函數(shù)4、獨(dú)立事件的聯(lián)合信息量，應(yīng)等于它們各自信息量之和。)()(21apap12()()f pf p1)(iap0)(ipf0)(iap)(ipf)()()(log)(log)()(log)(log)(),(jijijijijijibIaIbpapbpapbapbapfbaI自信息的表達(dá)式自信息的單位取決于對數(shù)的底 ：2為底，bit；e為底，nat；10為底，Hart I(ai)有兩層含義：第一事件ai發(fā)生前，收信者對ai存在的先驗(yàn)不確定性；第二事件ai發(fā)生后，ai所含有的（提供的）全部信息量。二進(jìn)制的一位能提供的最大信息量為1bit bitnat44. 11bitHart32.

5、 31)(/1log)(iiapaI2.2.2 信息熵問題：不同的符號有不同的自信息量 自信息量I(ai)在概率空間中的統(tǒng)計(jì)平均值 信息單位信源符號 信源每發(fā)一個(gè)符號所提供的權(quán)平均信息量，稱為“信息熵”。當(dāng)對數(shù)的底為r時(shí)，可記為： 以2為底時(shí)，常簡記H(x)。qiiiapapXH1)(log)()()(XHr物理含義。 (1) H(X)表示信源每發(fā)一個(gè)符號所提供的平均信息量； (2) H(X)表示信源X輸出前，信源的平均不確定性；（3）H(X)表征隨機(jī)性的大小。 一般情況下它并不等于平均獲得的信息量，只是在信道無噪時(shí)，兩者才相等。 需要注意需要注意：1.盡管小概率事件如發(fā)生會提供很大的自信息量

6、，但由于其發(fā)生的概率非常小，所以不會對熵值產(chǎn)生特別的影響。2.當(dāng)樣本空間增大時(shí)，信源的熵值將增大，既平均每條消息所含的信息量增大（可能的結(jié)果越多，隨機(jī)性越大）。 2.2.3 熵的基本性質(zhì)（1）對稱性（2）確定性 （3）非負(fù)性 （4）擴(kuò)展性 （5）可加性（6）強(qiáng)可加性（7）極值性 2.3 離散無記憶的擴(kuò)展信源離散無記憶N次擴(kuò)展信源熵為：證明：qqppaaxpx.)(11)()()()()()()()(1131121111131121112121qqqqqqqqaaapaaapaaapaaapaaaaaaaaaaaappppNNxxNqiiiNNXNHppXXXHXH121)()(log)().(

7、)(NqiiiNapapXH1)(log)()( qiqiiNiiiNiiNaaapaaap1121211).(log).(. qiqiiNiiiNiiNapapapaaap1121211)().()(log).(. qiqiqiqiiiNiiiiNiiNNapaaapapaaap111122112111)(log).(.)(log).(. qiqiiNiNiiNapaaap11211)(log).(.qiiNiNqiiiNapapNapap1111)(log)(.1) 1()(log)(1)()()(21NXHXHXH2.4 離散平穩(wěn)信源一般情況下，t不同，概率分布也不同 假定隨機(jī)矢量 中各

8、維聯(lián)合概率分布均不隨時(shí)間的推移而變化，即統(tǒng)計(jì)性質(zhì)與時(shí)間無關(guān)，稱為離散平穩(wěn)信源。 平穩(wěn)信源發(fā)出的平穩(wěn)隨機(jī)序列前后的依賴關(guān)系與時(shí)間起點(diǎn)無關(guān)。換句話說，任何時(shí)刻發(fā)出什么符號只與前N個(gè)符號有關(guān)，與t無關(guān) )()(jixpxp)|()|(2121NjjjjNiiiixxxxpxxxxp321xxxx )|()|()|(1101111NNNjjjNjNiiiNixxxxpxxxxpxxxxp 條件熵與無條件熵之間的關(guān)系 )()|(YHXYH2.5 離散平穩(wěn)信源的極限熵 問題：問題：時(shí)間域上一個(gè)無限長的符號序列，又因?yàn)樾旁从杏洃?，符號間依賴的關(guān)系會延伸至無窮，這種情況下，信源每輸出一個(gè)符號平均提供多大的信息

9、量？ 的幾個(gè)特性：（1）證：由熵的定義：).(lim211NNNXXXHH).(21NXXXH).(21NXXXH)|()|()(121121NNXXXXHXXHXHNqiiiNapapxxHXH11)(log)()()(N個(gè)分量統(tǒng)計(jì)關(guān)聯(lián)的隨機(jī)矢量 的聯(lián)合熵 ，等于起始時(shí)刻的無條件熵與各階條件熵之和，并不隨時(shí)間的推移而變化。 qiqiiNiiiNiiiiNiiNaaaapaapapaaap1112112121|()|()(log)( qiqiqiqiiiiNiiiNiiNNaapaapapaaap11111211211)/(log)()(log)( qiqiiNiiNiNiNNaaapaap1

10、1111)|(log)(qiqiqiiiiiiiaapaapapap111122111112)./(log)()(log)(1122111()log(/)NqqiiiNiNiiNiip a aap aaa )|()|()(121121NNXXXXHXXHXH21Nxxxx)(1NXXH（2）條件熵隨N的增加是非遞增的證明： 類似， ， 因?yàn)樾旁词瞧椒€(wěn)的，所以有 推廣平均符號熵 ：)|()()(12112XXHXHXXH)()|(212XHXXH)|()|(23213XXHXXXH)()|()|(112213XHXXHXXXH)|()|(21111NNNNXXXHXXXH)|(312NNXXXH

11、)()|()|(112213XHXXHXXXH)()(211NNNXXXHXH根據(jù)右端每項(xiàng)全用最小項(xiàng)代替 ，有即平均熵大與N階條件熵 )|()|()()(111211NNNXXXHXXHXHXXH)|()(11NNNXXXHXH（3）).()(11NNNXXHXH 的極限值存在，且為零與H（X）之間的某一有限值 )|()()(1211211NNNNXXXXHXXXHXXH)|()()()(111211NNNNNXXXHXXXHXXHXNH).|()() 1(111NNNXXXHXHN)()() 1()(1XHXHNXNHNNN 移項(xiàng)得)() 1()()(1XHNXHXNHNNN)()(1XHX

12、HNN得即HN隨N非遞增。反復(fù)運(yùn)用上式并考慮到， 可得： 其中： ， 表明，平均符號熵HN（X）的最大值就是原始信源X p的熵，而且它隨N的增加是非遞增的。HN（X）由熵的非負(fù)性亦具非負(fù)性，所以HN（X）的極限 HN(X)一定存在，且是處于零和H（X）之間的某一有限值。下面求此極限熵。0)(XHN)()()()(0121XHXHXHXHNNN)()(1xHXH設(shè)一整數(shù) ,有： 根據(jù)條件熵的遞減性和平穩(wěn)性有： k)(1)(1kNNkNXXXHkNXH)|()|()(1111111kNkNNNNXXXHXXXHXXHkN)/()|()|()(1)(11111111NNNNNNNkNxxxHXXXH

13、XXXHXXHkNXH)|(1)(11111NNNXXXHkNkXXHkNk，固定N ,N)(11NXXH和)|(11NNXXXH為定值，所以前一項(xiàng)01 kN )/()(lim11NNkNkXXXHXH)(1lim)(lim1NNNNXXHNXHHHXHXXxHXHNNN)()|()(11再令N，因極限存在 HXHNN)(lim)|(lim)(lim)(11NNNNNXXXHXHXH即：2.6 馬爾柯夫信源2.6.1 馬氏鏈的基本概念和主要特性 設(shè)序列 的取值是整數(shù)， ， ，若對任意非負(fù)整數(shù), 有： 馬爾柯夫性（無后效性）馬爾柯夫性（無后效性） 一旦“現(xiàn)在”已知，“將來”只決定于“現(xiàn)在”而與“

14、過去”無關(guān)。 “Markov鏈” 2 , 1 , 0),(nnxllitx)(jtx)(ttttr210)(,)(,(2211rritxitxitxp)|()|(21rrijpiiijp 馬氏鏈的最基本的統(tǒng)計(jì)特性 這個(gè)條件概率稱為馬氏鏈在時(shí)刻m的狀態(tài)一步轉(zhuǎn)移概率。 定義馬氏鏈在時(shí)刻m的k步轉(zhuǎn)移概率 : 使用全概率公式， )()(|) 1(mpimxjmxpij)()(/)()(mpimxjkmxpkij并規(guī)定： jijimpijij, 0, 1)()0()()()()()()(kmpmpmplsjIskislkij)2()() 1()()()2(1) 1() 1()(1mppmpmpmpmpn

15、jsIsmssIsIsisnsjisnijIsjsssisIsIsnnnmpmpmp1111) 1() 1()(馬氏鏈x(n)的統(tǒng)計(jì)特性可由起始概率和各時(shí)刻的一步轉(zhuǎn)移概率得到完整描述。如果馬氏鏈?zhǔn)瞧椒€(wěn)的，即, 2 , 1 , 0),(nnx的起始概率和一步轉(zhuǎn)移概率與時(shí)刻m無關(guān)，則多步轉(zhuǎn)移概率和聯(lián)合概率同樣與時(shí)間無關(guān)。稱時(shí)齊馬氏鏈。, 2 , 1 , 0),(nnx2.6.2 馬爾柯夫信源 信源當(dāng)前輸出的符號與前面的符號相關(guān)聯(lián) ，但可以考慮將記憶割斷 ，如果在任何時(shí)刻其符號發(fā)生的概率只與前面已經(jīng)發(fā)生的m個(gè)符號有關(guān)，而與更前面發(fā)生的符號無關(guān)，則稱該信源為m價(jià)馬爾柯夫信源，其數(shù)學(xué)模型為： 將前面m個(gè)

16、符號看作為m階M信源在此時(shí)刻所處的狀態(tài)。 )|(,21121mmkkkkqaaaapaaaqkkkkkmmmaaaap112111)|(qkkkkmm2 , 1,121)|()|()|(111ikikmkmkkmsapsapaaap將信源發(fā)出一串二進(jìn)制序列轉(zhuǎn)換成狀態(tài)的序列，此狀態(tài)序列構(gòu)成時(shí)齊馬爾柯夫鏈 遍歷的馬可夫信源：狀態(tài)序列是遍歷的馬爾可夫鏈所對應(yīng)的信源。 遍歷（各態(tài)歷經(jīng)性），各態(tài)相通，均可經(jīng)歷。狀態(tài)空間A= 構(gòu)成的集合組成一個(gè)不可約閉集（不可再分出另一個(gè)閉集） 對于時(shí)齊、遍歷的馬可夫鏈，一定存在一個(gè)極限的概率 Q（si）滿足： rSS ,.1)(lim)|(lim)(ljiljlilli

17、psssspsQEs 1EsiSSijiijijijjsQspsspEsisQsspsQ1)()()()()/()( Q(si)表示當(dāng)轉(zhuǎn)移步數(shù)l足夠長以后，狀態(tài)的l步轉(zhuǎn)移概率與初始狀態(tài)無關(guān)。它意味著信源在初始時(shí)刻可以處在任意狀態(tài)，然后狀態(tài)之間可以互相轉(zhuǎn)移。經(jīng)過足夠長時(shí)間后，信源處于什么狀態(tài)已與初始狀態(tài)無關(guān)信源處于什么狀態(tài)已與初始狀態(tài)無關(guān)，這時(shí)穩(wěn)定后處于每種狀態(tài)出現(xiàn)的概率已達(dá)到一種穩(wěn)定分布 時(shí)齊、遍歷時(shí)齊、遍歷的m階馬可夫信源，時(shí)間足夠長后，可作為平穩(wěn)平穩(wěn)信源處理，信源發(fā)出的符號只與前m個(gè)符號有關(guān)，其極限熵為： 即m階M信源的極限熵就等于m階條件熵 )|(lim11NNNxxxHH qkqkkN

18、kkNkNkNnaaapaap111111)|(log)(limqkqkNkmkkmkNkNaaapaap111111)|(log)(limqkqkmkmkkmkmkaaapaap11111111)|(log)(1211)/(mmmHxxxxH)|()|()|(211ijikkmkkkmsspsapaaaap)|()()|()()(111ikiikkmkkmksapsQsapaapaap11( ) (/)log(/)mqqmikikiijHHQ s p asp as 例：某二進(jìn)制二階M信源x符號集0，1，起始概率（一維分布）為： ，下一單位時(shí)間的R、V，x2與x1的依賴關(guān)系由條件概率 決定： p (00)0.3 p (10)0.7 p (01)0.4 p (110.6 再下一單位時(shí)間， x3與x1 x2有依賴關(guān)系，且由二維條件概率： p (000)p (0s1)0.4, p (100)p (1s1)0.6 p (001)p (0s2)0.2, p (101)p (1s2)0.8 p (010)p (0s3)0.3, p (