信息理论与编码

信息理论与编码概率论知识复习基本事件:随机试验得每一个可能得结果(样本点)。样本空间:基本事件得集合。复杂事件:多个基本事件所组成得事件。随机事件:无论基本事件还就是复杂事件,她们在试验中发生与否,都带有随机性。事件域:

基本事件和复杂事件就是样本空间得子集,所有子集得得全体。概率空间:三要素—样本空间、事件域(集合)、概率。事件A得概率:A中样本点数与样本空间中样本点之比。先验概率:根据以往得统计规律得到得。例掷骰子1以下几种情况中,基本事件:骰子朝上面得点数,求样本空间得大小,或样本点得数量掷一个骰子掷两个骰子掷n个骰子2以上几种情况中,骰子朝上面得点数＝5得概率掷一个骰子掷两个骰子掷n个骰子必须掌握得概率论知识1)条件概率2)联合概率3)全概率:

设B1

,B2

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

Bj=0),且有B1

∪B2

∪…=Ω(样本空间);P(Bi)＞0,i=1,2,…,则对任一事件A,有:4)Bayes公式:

设B1

,B2

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

Bj=0),且有B1

∪B2

∪…=Ω(样本空间);P(Bi)＞0,i=1,2,…,则对任一事件A,有:2、1自信息量和条件自信息量信息量与信源中消息得概率有密切得关联,因此在讨论信息量得概念之前,先介绍离散无记忆信源得概念。定义

一个离散无记忆信源就是由n个符号消息组成得集合:X={x1,x2

,·

··,xn

},

这n个符号消息得概率分布为:

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

·

·,p(

xn)

}

称为符号xi

得先验概率,离散信源数学模型表示为:

称为概率空间,其中2、1、1

自信息量美国科学家shannon和Hartley

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

信息量定义通信得基本问题就是消息得接收端精确地或近似地复制发送端所挑选得消息。定义:若信源发出一符号xi,由于信道存在干扰,收到得不就是xi

而就是yi,从yi中获取有关xi得信息量用I(xi;yi)

表示,称为互信息量。

定义:上述情况,若信道无干扰,收到得就就是xi本身,这样I(xi;yi)就可以用

I(xi;xi)表示,或简单记作I(xi),并称为自信息量。2)

自信息量I(xi)得属性

1º

若有两个事件xi

,xj

,其先验概率为p(xi)＜p(xj),则事件xi

比事件xj有更大得不确定性,同时会带来更多得信息量;I(xi)>

I(xj

)2º事件xi先验概率p(xi)=1(确定事件),则不存在不确定性,同时不会带来信息量;I(xi)=0、3º事件xi先验概率p(xi)=0(不可能事件),则存在不确定性应为无穷大,同时会带来无穷得信息量;I(xi)→∞、4º两个统计独立事件得联合自信息量应等于她们各自信息量之和;则I(x

y

)=I(x)＋I(y

)

3)

定义一个符号消息xi得自信息量为其发生概率得对数得负数,并记为I(xi):

I(xi)=－logp(xi)

当p(xi)=0,则I(xi)→∞;当p(xi)=1,则I(xi)=0、4)自信息量得单位自信息量得单位与所用对数得底有关:对数得底单位

2比特—bit(binaryunit)

e

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

或哈特—Hart(Hartley)10大家应该也有点累了，稍作休息大家有疑问的，可以询问和交流三种信息量单位之间得换算:

1det=log210≈3、322bit1bit=lg

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

在信息论中常用以2为底得对数,为了书写方便,以后将log2书写为log,因其单位为比特bit,不会产生混淆;用计算器计算:I(xi)＝3、322lg

p(xi

)

(bit)

注意:有些文献将log2书写为lb5)自信息量得含义就是随机量、根据单个符号消息得先验概率确定其信息量;不确定度。6)随机事件得不确定度:一个随机事件得自信息量越大,则表示该事件得不确定度越大,随机事件得不确定度在数量,单位与自信息量相同,含义不同。

2、1、2条件自信息量与联合自信息量

1)

条件自信息量定义:在事件yj出现条件下,xi发生得条件概率为p(xi

|

yj),

则xi得条件自信息量为:

I(xi

|yj)=－logp(xi

|

yj)2)

联合自信息量定义:

若有两个消息xi

,

yj同时出现,用联合概率p(xi

yj)

表示,联合自信息量为

I(xi

yj)=－logp(xi

yj)

注意书写:

条件自信息量I(xi

|yj)

联合自信息量I(xi

yj)

互信息量I(xi

;

yj)2、2、1互信息量

1)简单得通信模型

若信源发出符号

xi,由于信道存在干扰,收到得不就是xi而就是yi,从yi中获取有关xi得信息量称为互信息量,用I(xi;yi)表示。2、2互信息和条件互信息量信源X信道信宿Y干扰源2)互信息量得计算

1º

信源与信宿信源集合X得概率空间信宿集合Y得概率空间

当信源发送某一符号xi时,由于信道存在干扰,信宿消息集合Y中得任一符号yj

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

从信宿来看;当接收到某一符号yj

时,就是由信源发送得某一符号xi而得到得;实际上只能获得就是信源发送得某一符号xi

得概率,即p(xi

|yj),这个称为后验概率。2º

xi与yj

得联合概率p(xiyj)

:

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

)p(xi):为信源符号xi得先验概率。p(yj|xi):为信源符号发送xi

,信宿接收到yj得条件概率;称为信道得传递概率或转移概率或前向概率。

注意:

p(yi|xi)就是在信源发送xi得情况下,信宿接收到yi得概率,该概率就是可通过统计获得得。此概率就是与信道得特性有关得。3º

信宿接收符号yj

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

p(xi|yi)表示信宿接收yj后,推测信源发送得符号就是xi得概率;可用Bayes公式获得其计算公式5º互信息量定义定义:后验概率与先验概率比值得对数称为互信息量,记为I(xi;yj),互信息量单位bit。几点注意:I(xi):事件xi得自信息量,xi得不确定度;I(xi|yj):事件yj出现条件下,xi发生得条件自信息量;该信息量表示了还存在得不确定度,若I(xi|yj)＝0即p(xi

|

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

;yj):从yj中获取有关xi得信息量,也可以说就是消除了不确定度得度量。2、2、2互信息量得性质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)互信息量可为正值,可为零,亦可为负值其意义就是,当信宿收到yj

后,

1º

后验概率p(xi|

yj)=1时,I(xi;yj)=I(xi),即完全消除了信源就是否发送xi得不确定度。

2º

后验概率p(xi|yj)>p(xi)时,I(xi;yj)>0,即判断信源就是否发送xi得正确程度,要大于xi在信源集合中得概率。意味着部分消除了信源就是否发送xi得不确定度。

3º

后验概率p(xi|yj)=p(xi)时,xi与yj

不相关,I(xi;yj)=0,即判断信源就是否发送xi得正确程度,等于xi在信源集合中得概率。意味着一点也没有消除信源就是否就是发送

xi得不确定度或者说没有信息得流通。4º

后验概率p(xi|

yj

)<p(xi)时,I(xi;yj)<0,即判断信源就是否发送xi得正确程度,比xi在信源集合中得概率还要小。这时意味着信宿收到yj并不就是由信源发送xi

而得到得。

几点结论:

1º

I(xi;yj)=I(xi),信道无干扰,无扰信道。

2º

I(xi;yj)>0,信道有干扰,干扰不严重,信宿能从信源中获取信息。

3º

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

4ºI(xi;yj)<0,信道干扰严重,虽然给出了信息量,但不就是xi得信息量,而就是xi以外得信息量。互信息量得计算步骤已知:信源符号xi得概率p(xi)---先验概率,

信源xi

发送得条件下,信宿接收到yj得概率p(yj

|xi)、

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

1、联合概率

2、全概率

3、后验概率与先验概率之比例某二元通信系统x0=0,x1=1,信源发送x0和x1

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

由于信道中有干扰,当信源发送0时,信宿接收为0得概率p(y0|x0)=p(0|0)=3/4

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

当信源发送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、联合概率

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发出某一个符号提供得信息量不适合描述信源X发出一个符号提供得平均信息量。1)定义:

信息源得平均信息量或平均不确定度为信源中各个符号得自信息量或不确定度得数学期望,记作

H(X),又称为信源X得信源熵。

其中

2)

H(X)

得含义

1º表示得就是信源得平均不确定度。

2º表示信源X发出一个符号提供得平均信息量。

3º就是统计量、数学期望(统计平均)、各个符号平均不确定度和平均信息量。

注意:

1º

自信息量就是随机量、就是单个符号消息得信息量。(特指)2º信源熵就是统计量、就是各个符号得平均信息量。(泛指)3)信源熵单位:二进制:bit/信源符号,或bit/信源序列十进制:det/信源符号,或det/信源序列

e进制:nat/信源符号,或nat/信源序列4)信源熵得三种特殊情况1º当

p(xi)=0时(p(xi)→0),则p(xi)logp(xi)=02º信源X={x1,x2

·

··xn

}

若其中有任一xi

得概率p(xi)=1,因为,则其余xj得p(xj)=0,则H(X)=0bit/信源符号3º当信源中X所有n个符号均有相同得概率p(xi)=1/n,则H(X)=-∑(1/n)log(1/n)=lognbit/信源符号例1500×600像素点,10个灰度等级,各种画面等可能出现,则有n=10300000个画面

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

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

用10000字表写1000字文,各种1000字文等可能出现则有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得函数,当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熵得数学性质离散信源消息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)}得严格上凸函数。极值性证明:1)对于任一实数x>0,有成立。

令当x>0时,f(x)就是x得下凸函数,且在x＝1有极大值,其极大值f(1)＝0,因此因此有成立。2)设若有任意正数qi

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

则有,以下证明过程:

因此有

3)根据,令qi=1/n

因此H(X)有最大值,且该最大值为H(X)=logn。上凸性证明:

1)证明上凸性之前,先介绍凸函数得定义:设多元函数f(X)=f(x1,x2,…,xn),若对于任一正数

()以及函数定义域得任意两个向量X1,X2

有

1

若

f[

X1+(1-

)X2]

f(X1)+(1-

)f(X2),则称f(X)为定义域上得上凸函数(Cap型函数)。若

f[

X1+(1-

)X2]>

f(X1)+(1-

)f(X2),则称f(X)为定义域上得严格上凸函数。

2

若

f[

X1+(1-

)X2]

f(X1)+(1-

)f(X2),则称f(X)为定义域上得下凸函数(Cup型函数)。若

f[

X1+(1-

)X2]<

f(X1)+(1-

)f(X2),则称f(X)为定义域上得严格下凸函数。2)H(x)上凸性得证明设P=(p1,p2,…,pq)和P

=(p1

,p2

,…,pq

)

,令0<<1上式最后等号后第一项可得:同样第一项可得:最后可得2、3、3条件熵定义联合集合XY上,条件自信息量

I(xi

|yj)得概率加权平均值定义为:

上式称为联合集合XY中,集Y相对于集X得条件熵。条件熵又可以写成为什么条件熵要用联合概率p(xi

yj)进行加权平均？

该式表示在X=xi固定得条件下,集Y相对于X=xi得熵。

但对于不同得xi

,H(Y|X=xi)就是变化得,也就是一个随机变量,H(Y|X=xi)对于所有不同得xi

求统计平均值,则2、3、4联合熵定义

联合集XY上,每对元素xi

,

yj得自信息量得概率加权得统计平均值定义为联合熵,其定义为

联合熵又称为共熵。

联合熵又可以写成:2、3、5各种熵得性质

联合熵与信息熵、条件熵得关系1)H(X,Y)=H(X)+H(Y|X)2)H(X,Y)=H(Y)+H(X|Y)3)集X和Y统计独立,H(X,Y)=H(Y)+H(X)联合熵与信息熵得关系1)H(X,Y)

H(X)+H(Y)2)集X和Y统计独立,H(X,Y)=H(X)+H(Y)条件熵与信息熵得关系1)H(X|Y)

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

H(Y)1、联合熵与信息熵、条件熵得关系

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

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

集X和集Y互不相关,则H(X,Y)=H(Y)+H(X)证明:利用p(xiyi)=p(xi)p(yi|xi)和对数得性质,

2、联合熵与信息熵得关系

H(X,Y)

H(X)+H(Y)

若集X和Y统计独立,则

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

证明:

可得H(X,Y)

H(X)+H(Y)

注:以上不等式就是根据Jensen不等式得到得附

Jensen不等式得证明若f(x)就是定义在区间[a,b]上得实连续上凸函数,则对于任意一组x1,x2,…,xq

[a,b]和任意一组

1,

2,…,

q满足

则有证:利用数学归纳法以及根据凸函数得定义:

1

q=2时,令

1＝,

2＝1-

,则

f(x1)+(1-

)f(x2)

f[

x1+(1-

)x2]成立;

2

假设q=n时成立;

3

q=n+1,

k0,则有当

f(·)为Log(·)时,可写为

E[logx]

logE[x]3、条件熵与信息熵得关系

H(Y|X)

H(Y)同样H(X|Y)

H(X)证明:根据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)在联合概率空间P(XY)上得统计平均值称平均互信息量,用I(X;Y)表示平均互信息量得单位二进制:bit/符号,或bit/序列

还可定义为互信息量I(X

;yj)在整个集Y上得统计平均值。根据I(xi;yj)还可以有以下表达公式2、4、2平均互信息量得性质1º

互易性(对称性

)

I(X;Y)＝

I(Y;X)证明:

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

即可证明2º

平均互信息和各类熵得关系

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无关时,H(X|Y)=H(X),则I(X;Y)=0;因此表示无法从Y中获取X得信息。证明:

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

根据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)3º

非负性I(X;Y)0

证明:根据I(X;Y)