信息理論與編碼

信息理論與編碼概率論知識復習基本事件:隨機試驗得每一個可能得結(jié)果(樣本點)。樣本空間:基本事件得集合。復雜事件:多個基本事件所組成得事件。隨機事件:無論基本事件還就是復雜事件,她們在試驗中發(fā)生與否,都帶有隨機性。事件域:

基本事件和復雜事件就是樣本空間得子集,所有子集得得全體。概率空間:三要素—樣本空間、事件域(集合)、概率。事件A得概率:A中樣本點數(shù)與樣本空間中樣本點之比。先驗概率:根據(jù)以往得統(tǒng)計規(guī)律得到得。例擲骰子1以下幾種情況中,基本事件:骰子朝上面得點數(shù),求樣本空間得大小,或樣本點得數(shù)量擲一個骰子擲兩個骰子擲n個骰子2以上幾種情況中,骰子朝上面得點數(shù)＝5得概率擲一個骰子擲兩個骰子擲n個骰子必須掌握得概率論知識1)條件概率2)聯(lián)合概率3)全概率:

設(shè)B1

,B2

,…就是一列互不相容得事件(Bi

Bj=0),且有B1

∪B2

∪…=Ω(樣本空間);P(Bi)＞0,i=1,2,…,則對任一事件A,有:4)Bayes公式:

設(shè)B1

,B2

,…就是一列互不相容得事件(Bi

Bj=0),且有B1

∪B2

∪…=Ω(樣本空間);P(Bi)＞0,i=1,2,…,則對任一事件A,有:2、1自信息量和條件自信息量信息量與信源中消息得概率有密切得關(guān)聯(lián),因此在討論信息量得概念之前,先介紹離散無記憶信源得概念。定義

一個離散無記憶信源就是由n個符號消息組成得集合:X={x1,x2

,·

··,xn

},

這n個符號消息得概率分布為:

P={p(x1),p(x2),·

·

·,p(

xn)

}

稱為符號xi

得先驗概率,離散信源數(shù)學模型表示為:

稱為概率空間,其中2、1、1

自信息量美國科學家shannon和Hartley

于1928年給出了信息得度量方法。1)

信息量定義通信得基本問題就是消息得接收端精確地或近似地復制發(fā)送端所挑選得消息。定義:若信源發(fā)出一符號xi,由于信道存在干擾,收到得不就是xi

而就是yi,從yi中獲取有關(guān)xi得信息量用I(xi;yi)

表示,稱為互信息量。

定義:上述情況,若信道無干擾,收到得就就是xi本身,這樣I(xi;yi)就可以用

I(xi;xi)表示,或簡單記作I(xi),并稱為自信息量。2)

自信息量I(xi)得屬性

1o

若有兩個事件xi

,xj

,其先驗概率為p(xi)＜p(xj),則事件xi

比事件xj有更大得不確定性,同時會帶來更多得信息量;I(xi)>

I(xj

)2o事件xi先驗概率p(xi)=1(確定事件),則不存在不確定性,同時不會帶來信息量;I(xi)=0、3o事件xi先驗概率p(xi)=0(不可能事件),則存在不確定性應(yīng)為無窮大,同時會帶來無窮得信息量;I(xi)→∞、4o兩個統(tǒng)計獨立事件得聯(lián)合自信息量應(yīng)等于她們各自信息量之和;則I(x

y

)=I(x)＋I(y

)

3)

定義一個符號消息xi得自信息量為其發(fā)生概率得對數(shù)得負數(shù),并記為I(xi):

I(xi)=－logp(xi)

當p(xi)=0,則I(xi)→∞;當p(xi)=1,則I(xi)=0、4)自信息量得單位自信息量得單位與所用對數(shù)得底有關(guān):對數(shù)得底單位

2比特—bit(binaryunit)

e

奈特—nat(natureunit)10笛特—det(decimalunit)

或哈特—Hart(Hartley)10大家應(yīng)該也有點累了，稍作休息大家有疑問的，可以詢問和交流三種信息量單位之間得換算:

1det=log210≈3、322bit1bit=lg

2≈0、3010det1bit=ln2≈0、6931nat1nat=log2e≈1、4427bit

在信息論中常用以2為底得對數(shù),為了書寫方便,以后將log2書寫為log,因其單位為比特bit,不會產(chǎn)生混淆;用計算器計算:I(xi)＝3、322lg

p(xi

)

(bit)

注意:有些文獻將log2書寫為lb5)自信息量得含義就是隨機量、根據(jù)單個符號消息得先驗概率確定其信息量;不確定度。6)隨機事件得不確定度:一個隨機事件得自信息量越大,則表示該事件得不確定度越大,隨機事件得不確定度在數(shù)量,單位與自信息量相同,含義不同。

2、1、2條件自信息量與聯(lián)合自信息量

1)

條件自信息量定義:在事件yj出現(xiàn)條件下,xi發(fā)生得條件概率為p(xi

|

yj),

則xi得條件自信息量為:

I(xi

|yj)=－logp(xi

|

yj)2)

聯(lián)合自信息量定義:

若有兩個消息xi

,

yj同時出現(xiàn),用聯(lián)合概率p(xi

yj)

表示,聯(lián)合自信息量為

I(xi

yj)=－logp(xi

yj)

注意書寫:

條件自信息量I(xi

|yj)

聯(lián)合自信息量I(xi

yj)

互信息量I(xi

;

yj)2、2、1互信息量

1)簡單得通信模型

若信源發(fā)出符號

xi,由于信道存在干擾,收到得不就是xi而就是yi,從yi中獲取有關(guān)xi得信息量稱為互信息量,用I(xi;yi)表示。2、2互信息和條件互信息量信源X信道信宿Y干擾源2)互信息量得計算

1o

信源與信宿信源集合X得概率空間信宿集合Y得概率空間

當信源發(fā)送某一符號xi時,由于信道存在干擾,信宿消息集合Y中得任一符號yj

(i=1,2,…)都可能以一定得概率接收到。

從信宿來看;當接收到某一符號yj

時,就是由信源發(fā)送得某一符號xi而得到得;實際上只能獲得就是信源發(fā)送得某一符號xi

得概率,即p(xi

|yj),這個稱為后驗概率。2o

xi與yj

得聯(lián)合概率p(xiyj)

:

p(xiyj)=p(xi)p(yj|xi

)p(xi):為信源符號xi得先驗概率。p(yj|xi):為信源符號發(fā)送xi

,信宿接收到y(tǒng)j得條件概率;稱為信道得傳遞概率或轉(zhuǎn)移概率或前向概率。

注意:

p(yi|xi)就是在信源發(fā)送xi得情況下,信宿接收到y(tǒng)i得概率,該概率就是可通過統(tǒng)計獲得得。此概率就是與信道得特性有關(guān)得。3o

信宿接收符號yj

得概率[全概率公式]4o后驗概率p(xi|yi)

p(xi|yi)表示信宿接收yj后,推測信源發(fā)送得符號就是xi得概率;可用Bayes公式獲得其計算公式5o互信息量定義定義:后驗概率與先驗概率比值得對數(shù)稱為互信息量,記為I(xi;yj),互信息量單位bit。幾點注意:I(xi):事件xi得自信息量,xi得不確定度;I(xi|yj):事件yj出現(xiàn)條件下,xi發(fā)生得條件自信息量;該信息量表示了還存在得不確定度,若I(xi|yj)＝0即p(xi

|

yj)＝1,表示已不存在得不確定度。I(xi

;yj):從yj中獲取有關(guān)xi得信息量,也可以說就是消除了不確定度得度量。2、2、2互信息量得性質(zhì)1)互信息量得互易性(對稱性)

由前述得公式(*),可得

I(xi;yj)=I(yj;xi)2)兩個事件得互信息量不大于其中任一事件得自信息量。

證明且因為p(yj|xi

)和p(xi

|

yj)均

1,所以I(xi;yj)

I(xi)且I(xi;yj)

I(yj)

3)互信息量可為正值,可為零,亦可為負值其意義就是,當信宿收到y(tǒng)j

后,

1o

后驗概率p(xi|

yj)=1時,I(xi;yj)=I(xi),即完全消除了信源就是否發(fā)送xi得不確定度。

2o

后驗概率p(xi|yj)>p(xi)時,I(xi;yj)>0,即判斷信源就是否發(fā)送xi得正確程度,要大于xi在信源集合中得概率。意味著部分消除了信源就是否發(fā)送xi得不確定度。

3o

后驗概率p(xi|yj)=p(xi)時,xi與yj

不相關(guān),I(xi;yj)=0,即判斷信源就是否發(fā)送xi得正確程度,等于xi在信源集合中得概率。意味著一點也沒有消除信源就是否就是發(fā)送

xi得不確定度或者說沒有信息得流通。4o

后驗概率p(xi|

yj

)<p(xi)時,I(xi;yj)<0,即判斷信源就是否發(fā)送xi得正確程度,比xi在信源集合中得概率還要小。這時意味著信宿收到y(tǒng)j并不就是由信源發(fā)送xi

而得到得。

幾點結(jié)論:

1o

I(xi;yj)=I(xi),信道無干擾,無擾信道。

2o

I(xi;yj)>0,信道有干擾,干擾不嚴重,信宿能從信源中獲取信息。

3o

I(xi;yj)=0,沒有信息得流通

4oI(xi;yj)<0,信道干擾嚴重,雖然給出了信息量,但不就是xi得信息量,而就是xi以外得信息量?；バ畔⒘康糜嬎悴襟E已知:信源符號xi得概率p(xi)---先驗概率,

信源xi

發(fā)送得條件下,信宿接收到y(tǒng)j得概率p(yj

|xi)、

如何求互信息量?即如何計算p(xi|yj)/p(xi)

1、聯(lián)合概率

2、全概率

3、后驗概率與先驗概率之比例某二元通信系統(tǒng)x0=0,x1=1,信源發(fā)送x0和x1

得概率分別為p(0)=1/2,p(1)=1/2;信宿y0=0,y1=1

由于信道中有干擾,當信源發(fā)送0時,信宿接收為0得概率p(y0|x0)=p(0|0)=3/4

信宿接收為1得概率p(y1|x0)=p(1|0)=1/4

當信源發(fā)送1時,信宿接收為0得概率p(y0|x1)=p(0|1)=1/5

信宿接收為1得概率p(y1|x1)=p(1|1)=4/5

求互信息量

I(x0;y0),I(x0;y1),I(x1;y1),I(x1;y1)

x0=0

p(0|0)=3/4y0=0

p(0|1)=1/5p(1|0)=1/4

x1=1p(1|1)=4/5y1=11、聯(lián)合概率

p(x0y0)=p(x0)p(y0|x0)=1/2×3/4=3/8

p(x0y1)=p(x0)p(y1|x0)=1/2×1/4=1/8

p(x1y0)=p(x1)p(y0|x1)=1/2×1/5=1/10p(x1y1)=p(x1)p(y1|x1)=1/2×4/5=4/10

2、全概率p(y0)=p(x0)p(y0/x0)+p(x1)p(y0/x1)p(y0)=p(x0y0)+p(x1y0)=3/8+1/10=19/40

p(y1)=p(x0y1)+p(x1y1)=1/8+4/10=21/403、后驗概率與先驗概率之比

p(x0|y0)/p(x0)=p(y0|x0)/p(y0)=3/4÷19/40=30/19p(x0|y1)/p(x0)=p(y1|

x0)/p(y1)=1/4÷21/40=10/21p(x1|y0)/p(x1)=p(y0|

x1)/p(y0)=1/5÷19/40=8/19p(x1|y1)/p(x1)=p(y1|

x1)/p(y1)=4/5÷21/40=32/21

4、互信息量

I(x0;y0)=log(30/19)bit=0、659bitI(x0;y1)

=log(10/21)bit=-1、070bitI(x1;y0)=log(8/19)bit=-1、248bit

I(x1;y1)=log(32/21)bit=0、608bit2、3離散集得平均自信息量2、3、1平均自信息量(離散信源熵)

信源X發(fā)出某一個符號提供得信息量不適合描述信源X發(fā)出一個符號提供得平均信息量。1)定義:

信息源得平均信息量或平均不確定度為信源中各個符號得自信息量或不確定度得數(shù)學期望,記作

H(X),又稱為信源X得信源熵。

其中

2)

H(X)

得含義

1o表示得就是信源得平均不確定度。

2o表示信源X發(fā)出一個符號提供得平均信息量。

3o就是統(tǒng)計量、數(shù)學期望(統(tǒng)計平均)、各個符號平均不確定度和平均信息量。

注意:

1o

自信息量就是隨機量、就是單個符號消息得信息量。(特指)2o信源熵就是統(tǒng)計量、就是各個符號得平均信息量。(泛指)3)信源熵單位:二進制:bit/信源符號,或bit/信源序列十進制:det/信源符號,或det/信源序列

e進制:nat/信源符號,或nat/信源序列4)信源熵得三種特殊情況1o當

p(xi)=0時(p(xi)→0),則p(xi)logp(xi)=02o信源X={x1,x2

·

··xn

}

若其中有任一xi

得概率p(xi)=1,因為,則其余xj得p(xj)=0,則H(X)=0bit/信源符號3o當信源中X所有n個符號均有相同得概率p(xi)=1/n,則H(X)=-∑(1/n)log(1/n)=lognbit/信源符號例1500×600像素點,10個灰度等級,各種畫面等可能出現(xiàn),則有n=10300000個畫面

H(X)=logn=lg10300000=3×105det/畫面

=3、322×3×105bit/畫面

用10000字表寫1000字文,各種1000字文等可能出現(xiàn)則有n=100001000=104000篇,

H(X)=lgn=lg104000=4000det/千字文

=3、32×4×103bit/千字文例2二元符號信源{0,1}

當符號0得概率p(0)=p

,則p(1)=1-p

因此有H(X)=-[plogp+(1-p)log(1-p)]

H(X)就是p得函數(shù),當p

[0,1],求H(X)得最大值

可得p=0、5時,

H(X)有最大值,H(X)=1bit/信源符號例3已知信源求H(X)

Xp(xi)-logp(xi)-p(xi)logp(xi)

x19/160.8300.467

x23/162.4150.453

x33/162.4150.453

x41/1640.250H(X)=∑(-PlogP)=1.632bit/信源符號2、3、2熵得數(shù)學性質(zhì)離散信源消息X=｛x1,x2,…xn｝2、非負性H(X)≥01、對稱性H(

x1,x2,…xn)=H(x2,x1,…xn)

3、擴展性H(

x1,x2,…xn,

xn+1

)若p(xn+1)0

則H(

x1,x2,…xn,

xn+1

)=H(

x1,x2,…xn)4、確定性離散信源X中只要有一消息得概率為1,則

H(X)=0

5、極值性(最大熵定理)

離散信源X中有n個不同得消息,則信源熵有最大值得充要條件就是各個消息為等概率分布p(xi)=1/n

。該最大值為H(X)=logn6、上凸性

H(x1,x2,…,xn)就是概率分布P={p(x1),p(x2),·

·

·,p(

xn)}得嚴格上凸函數(shù)。極值性證明:1)對于任一實數(shù)x>0,有成立。

令當x>0時,f(x)就是x得下凸函數(shù),且在x＝1有極大值,其極大值f(1)＝0,因此因此有成立。2)設(shè)若有任意正數(shù)qi

(I=1,2,…,n),且

則有,以下證明過程:

因此有

3)根據(jù),令qi=1/n

因此H(X)有最大值,且該最大值為H(X)=logn。上凸性證明:

1)證明上凸性之前,先介紹凸函數(shù)得定義:設(shè)多元函數(shù)f(X)=f(x1,x2,…,xn),若對于任一正數(shù)

()以及函數(shù)定義域得任意兩個向量X1,X2

有

1

若

f[

X1+(1-

)X2]

f(X1)+(1-

)f(X2),則稱f(X)為定義域上得上凸函數(shù)(Cap型函數(shù))。若

f[

X1+(1-

)X2]>

f(X1)+(1-

)f(X2),則稱f(X)為定義域上得嚴格上凸函數(shù)。

2

若

f[

X1+(1-

)X2]

f(X1)+(1-

)f(X2),則稱f(X)為定義域上得下凸函數(shù)(Cup型函數(shù))。若

f[

X1+(1-

)X2]<

f(X1)+(1-

)f(X2),則稱f(X)為定義域上得嚴格下凸函數(shù)。2)H(x)上凸性得證明設(shè)P=(p1,p2,…,pq)和P

=(p1

,p2

,…,pq

)

,令0<<1上式最后等號后第一項可得:同樣第一項可得:最后可得2、3、3條件熵定義聯(lián)合集合XY上,條件自信息量

I(xi

|yj)得概率加權(quán)平均值定義為:

上式稱為聯(lián)合集合XY中,集Y相對于集X得條件熵。條件熵又可以寫成為什么條件熵要用聯(lián)合概率p(xi

yj)進行加權(quán)平均？

該式表示在X=xi固定得條件下,集Y相對于X=xi得熵。

但對于不同得xi

,H(Y|X=xi)就是變化得,也就是一個隨機變量,H(Y|X=xi)對于所有不同得xi

求統(tǒng)計平均值,則2、3、4聯(lián)合熵定義

聯(lián)合集XY上,每對元素xi

,

yj得自信息量得概率加權(quán)得統(tǒng)計平均值定義為聯(lián)合熵,其定義為

聯(lián)合熵又稱為共熵。

聯(lián)合熵又可以寫成:2、3、5各種熵得性質(zhì)

聯(lián)合熵與信息熵、條件熵得關(guān)系1)H(X,Y)=H(X)+H(Y|X)2)H(X,Y)=H(Y)+H(X|Y)3)集X和Y統(tǒng)計獨立,H(X,Y)=H(Y)+H(X)聯(lián)合熵與信息熵得關(guān)系1)H(X,Y)

H(X)+H(Y)2)集X和Y統(tǒng)計獨立,H(X,Y)=H(X)+H(Y)條件熵與信息熵得關(guān)系1)H(X|Y)

H(X)2)H(Y|X)

H(Y)1、聯(lián)合熵與信息熵、條件熵得關(guān)系

H(X,Y)=H(X)+H(Y|X)

同理H(X,Y)=H(Y)+H(X|Y)

集X和集Y互不相關(guān),則H(X,Y)=H(Y)+H(X)證明:利用p(xiyi)=p(xi)p(yi|xi)和對數(shù)得性質(zhì),

2、聯(lián)合熵與信息熵得關(guān)系

H(X,Y)

H(X)+H(Y)

若集X和Y統(tǒng)計獨立,則

H(X,Y)＝H(X)+H(Y)

證明:

可得H(X,Y)

H(X)+H(Y)

注:以上不等式就是根據(jù)Jensen不等式得到得附

Jensen不等式得證明若f(x)就是定義在區(qū)間[a,b]上得實連續(xù)上凸函數(shù),則對于任意一組x1,x2,…,xq

[a,b]和任意一組

1,

2,…,

q滿足

則有證:利用數(shù)學歸納法以及根據(jù)凸函數(shù)得定義:

1

q=2時,令

1＝,

2＝1-

,則

f(x1)+(1-

)f(x2)

f[

x1+(1-

)x2]成立;

2

假設(shè)q=n時成立;

3

q=n+1,

k0,則有當

f(·)為Log(·)時,可寫為

E[logx]

logE[x]3、條件熵與信息熵得關(guān)系

H(Y|X)

H(Y)同樣H(X|Y)

H(X)證明:根據(jù)H(X,Y)=H(X)+H(Y|X)H(X,Y)=H(Y)+H(X|Y)

和H(X,Y)

H(X)+H(Y)

可得H(X)+H(Y|X)

H(X)+H(Y)H(Y|X)

H(Y)

或H(Y)+H(X|Y)

H(X)+H(Y)H(X|Y)

H(X)2、4離散集得平均互信息量

2、4、1平均互信息量

定義互信息量I(xi;yj)在聯(lián)合概率空間P(XY)上得統(tǒng)計平均值稱平均互信息量,用I(X;Y)表示平均互信息量得單位二進制:bit/符號,或bit/序列

還可定義為互信息量I(X

;yj)在整個集Y上得統(tǒng)計平均值。根據(jù)I(xi;yj)還可以有以下表達公式2、4、2平均互信息量得性質(zhì)1o

互易性(對稱性

)

I(X;Y)＝

I(Y;X)證明:

因為I(xi;yj)=I(yj;xi),且有

即可證明2o

平均互信息和各類熵得關(guān)系

I(X;Y)=H(X)－H(X|Y)

I(X;Y)=H(Y)－H(Y|X)

I(X;Y)=H(X)+H(Y)－H(YX)

當X與Y無關(guān)時,H(X|Y)=H(X),則I(X;Y)=0;因此表示無法從Y中獲取X得信息。證明:

同理可證I(X;Y)=H(Y)－H(Y|X)

根據(jù)H(X,Y)=H(X)+H(Y|X)

H(Y|X)=H(X,Y)-

H(X)

可得I(X;Y)=H(X)+H(Y)－H(YX)3o

非負性I(X;Y)0

證明:根據(jù)I(X;Y)