信息论复习笔记

1.绪论

信息论回答了通信的两个最基本问题：

（1）数据压缩的极限；

（2）信道传输速率的极限；

彳言息、'消息、和彳言号"

蔡息：蒋息而戴醴（能被感知和理解、迤行停蟒噬取）

信息：事物^勤力犬熊或存在方式的不硅定性的描述（香晨）

先瞬概率-P（ai）

自信息：1（&）=1。gw-（冉）]；（信息接收的不硅定性）

互信息：1（&;卜）=log[pi（aj]-log[pT（a]bJ];

（信息接收的多少度量）'''

（若信道辗干攥,期互信息等於自信息等於0）

侵黑占：明碓的数擘模型、定量言十算；

缺黑占：有遹用靶圉；

信虢；

通2系统的模型

通信系统的基本要求:有效、可靠、保密、认证

2.离散信源及其信息测度

-离散信源的定义：输出信息数有限、每次只率俞出一彳固；

-自信息的定义及物理意义

事件赞生前：事件彝生的不硅定性；

事件彝生后：日寺^含有的信息量；

信息熠的定义及物理意义，信息牖的基本性质

定羲:自信息的数擘期望(H(X)=-Z[P(ai)logP(ai)])

信源的尉辨f信息测度

(1)每偃I消息所提供的平均信息量；

(2)信源输出前，信源的平均不硅定性；

性小(1)封稀性；(2)硅定性；

(3)非负性；(4)^展性(可拆；

(5)可加性；[H(XY)=H(X)+H(Y)]

(6)强可加性；[H(XY)=H(X)+H(Y|X)]

(7)遮增性；

(8)趣值性；[HguP&Pe…,p，4H(q-i,,…，q")=logq]

等概率分彳布信源的平均不碓定性最大，耦悬最大蹄散嫡定理；

-离散无记忆信源的扩展信源

-扩展信源的嫡H(X)=NH(X)

-离散平稳信源：联合概率分布与时间起点无关；

■:联合炳H(X1X2)=EEP(aiaj)logP(aiaj)

条件―H(X21X1)=-EEP(aiaj)logP(ai|aj

关系:H(X1X2)=H(X1)+H(X2|X1)

嫡率:离散平稳信源的极限燧=limH(XN|X1X2-XN.1)

-马尔可夫信源:某一时刻的输出只与此刻信源所处的状态有

父而与以前的状态及以前的输出符号都无关；

—马尔可夫信源的大商：Hm+i=H(Xm+i|X1X2…Xm)

-信源剩余度

嫡的相对率il=H极限/H。

信源剩余度(输出符号间依赖强度)Y=l-r]=l-H极限/Ho

3.离散信道及其信道容量

—H(X;Y)=H(X)-H(X|Y)

-离散信道的数学模型

.4信道.4

X=(凝%,'=(不马，…，耳，…％)

P(y|x)

“也吗、…、4]vp^y।X)=1鸟、…、匕」

7

-信道矩阵性^

(1)P(aibj)=P(ajP(bj|aJ=P(bj)P(ai|bj)；

(2)[P(b.)][P(aO]

[P(b2)]1P3)]

[P(h)]二[P(a4)](rRs)

[…][…]

[P(bs)][P(ar)]

(3)本俞出端收到的任一b一定是输人符虢a「中的某一彳固送

入信道；

信道疑义度的定义收到Y接堂寸燮量X尚存在的平均不硅定

性:

1

H(X|Y)=E[H(XIb])]=EP(xy)logP(X|Y)

物理意义:噪磬造成的影警大小；

-平均互信息的定义收到Y彳爰平均每彳固符虢攫得的是曷於X的信

息量(物理意羲：反映输人输出雨彳固随械燮量之的统言依勺束

是眠)：

I(X;Y)=H(X)-H(X|Y)=EP(xy)P(y|x)P1(y)

辗噪一一'封鹰信道中：I(X;Y)=H(X)=H(Y)=O

-信道容量的定义:信道每秒^平均停翰的信息量穗卷信息停

率俞速率，最大信息傅率俞率穗卷信道容量；

-信道容量的计算：

无噪信道(求H(X)趣值):C=logr

对称信道(信道矩睡的每一行或列是另一行或列的置换)：

C=logS-H(Pi,P2,…,pj

强对称信道:c=logr-plog(r-l)-H(p)；

准对称信道:C=logr-H(p1,p2,«--,ps)-ENklogMk

(Nk是第k/固子矩睡行元素之和，Mk是第k彳固子矩障列元素之

和)

一般离散信道(望寸所有可能的输入概率分彳布求平均互信息的最

大值)：

C=X4-loge

w：I(xi；Y)=&=F(bjIaJ*log[P(bj|aJ/P(bj)]<C

一般离散信道当LS,并且信道矩阵P是非奇异阵时，信道容量

的计算步骤如下：

力股⑷月=力%|a,)logP(b,⑷。=1,2,…,r)

/-Im

C=log2£2^

J

1.计算打0=1,2,.”)

2.计算宿道容量C

3.计算输出概率分布P(6j)0=1,2,…⑼

4.计算输入概率分布P(a,)(i=l,2,…,)

5.如果Pa)N0(i=l,2,…,s)即可结束计算，第2步计算的C即为

信道容量；否则要重新计算

离散无记忆信道容量的迭代算法

(S.Arimoto,R.E.Blahut,1972)如下：

1.选择初始概率分布R%W，PQ尸。。)3)

2.计算c(〃+l,")和C'(〃+l,〃)

尸叩4)

4=expZPS/aJln

ZP(q)P(b/a,)

C(n+l,n)=ln^P(a,)a,

C\n+1,〃)=In(maxa.

3.判断C("+l,〃)-C5+l,〃)<£,如果成立，转第5步;

否则转第4步

4.计算尸(6)，然后转第2步

P(a,)=,』,2,…,r

2.LP(q)a,

i

5.信道容量C=C(〃+1,〃)，结束

一数据处理定理

如果X、Y、Z组成一个马尔科夫链，则有

I(X;Z)<I(X;Y)

I(X;Z)<I(Y;Z)

信息不增性原理

一般的数据处理原理

I(S;Z)<I(S;Y)

I(S;Z)<I(X;Z)

I(S;Z)<I(X;Y)

-信道剩余度=C-I(X;Y)

相对剩余度=1-I(X;Y)/C

无损信道的相对剩余度=l-H(X)/logr

4.波形信源和波形信道

建^信源的相堂寸烟：h(X)A=-/Rptxjlogpfxldx

波形信源的差牖：h(x(t))A=limN_>Ji(XiX2・•-XN)

连续信源的差燧：r1

均匀分布连续信源的差炳：p(x)=Fa~x~b

0others

h(X\=\o9(h-a\

1N

N雉均匀分彳布：

口口-4)

4(X)=2Flog(b-a)1=1

N

o%史口(4一4)

高斯信源的差牖：

X)

h(X)=log飞2g2+—loge=—log27re(j2

22

%(X)=11og2〃eP

N雉高斯信源的差嫡：2

A(X)=llog(2^f|C|

乙

10=N5

差燧的性质：

(1)可加性；(2)凸性；

(3)可负性；(4)燮换性(X「＞X2,差嫡曾建化)；

(5)趣值性:

离隹散信源的信源符虢等概率分彳布日寺信源的信最大;

建^信源：

-常峰值功率受限悬阴寺(率俞出信虢的瞬日寺甯屋限制悬

±(PA)1/2)，此日寺信源输出的速燮量限制在[a,b]

fi，信源具有最大嫌：

h=log(b-a)

如果随械矢量取值受限，即各随械分量统IF褐立并均匀

分佛畤具有最大嫡；

-常信源输出信虢的平均功率被限定:MP，即J其信虢幅度

的概率密度分怖悬高斯分佛日寺，信源有最大燧：

h=l/2*log2jieP

N雉速^平稳信源如果其N雉随檄序列的愤方差矩睡C被限定，印J

N雉随檄矢量:M正太分彳布日寺信源的嫡最大。也就是Ng隹高斯信源

的牖最大，其值卷

1N

^log\C\+-log2ne

*燧功率：如果平均功率的非高斯分怖的信源的牖:Mh,m

嫡也;Mh的高斯信源的平均功率:M炳功率

P12/1

P=­e

27r

p<p

*建^信源的剩绘度P-P

2h（X+Z）、2h（X）,2h（Z）

*嫡功率不等式：e（）之e3+e-

—香农公式

意义：（1）提高信噪比能增加信道容量，趣於0日寺信道容量超

於辗蔚；（2）女合出了趣金昔^通信的僖输速率的理^^限，

香晨趣限；

—=ln2x0.6931

No

lEb\

10/^1—I=10^（/712）1.6dB

5.无失真信源编码定理

信源褊碉-u缩剩绘度

信道编礁-增加剩食余度

-编码：堂寸信源的原始符虢按一定的数擘规刖迤行燮换；

一码：（1）礁字；（2）礁元（礁符虢）；

（3）礁字■^度（石身艮）；

-码的分类：

二元礁礁符虢集只有0和1刖槿元素

等口焉

等是非奇昇礁一定是唯一可群礁；

用等晨礁堂寸信源S褊礁，必须满足q"；

燮是碉、非奇昇碣（礁字都不相同）、奇昇碣（存在相同）、

同慎礁（每彳固礁元的傅翰日寺^都相同）；

唯一可葬礁：

渐近等分割性

彳蜀立等分彳布的随檄序列S1S2…SN，有

ai=(SilSi2-SiN)€S1S2-SN

11P

-露。gP(%)=-,ogP(Si]Sq...S/TH(S)

-典型序列集的性质GEN竿-"(S)<£，

出潮既率超近1-P&N)>1-6，P&N)&S

接近等概率分彳布:2-MH⑸+6]<尸3)<2-M»]

彳固数超近2叫固:(1一b)2“(sz141G一||<2时"⑸同

—log尸(4)

—典型序列：臀”⑸<H⑸<£

N

-信源编码

IH(S)+£

等晨褊礁定理：满足后-畤,富N足多句大即J可以

IH⑸-2s

乎辗失真褊礁'反之如果后一k日寺，刖不可能^^辗失真

编礁，富N足多旬大日寺，群碣金昔^概率近似等於1；

燮形：(1)llogr>NH(SJ:只要礁字僖翰的信息量大於信

源序列搞带的信息量可以乎辗失真褊礁；

I

(2)褊礁后信源的信息僖输率：R=/。夕

(3)信息僖本俞率大於信源的嫡才能乎辗失真编礁:

I

R'=~^logr>H(S)+E

H(S)H(S)

4=R，=1H(S)

褊礁效率：胪,"(最佳等晨碣=WT7)

信源序列是度N典金昔概率的信期系:

D［/(S)。［/(幻］2

N>---=’

£S“2(S)(1一后

—克拉夫特不等式：“i=1丁-

如果礁是满足克拉夫特不等式即一定存在具有道檬礁房的r

元唯一可群礁，且一定存在一彳固具有相同礁房的即日寺礁；

—唯一可译码的判断：

没有一彳固俊女凝分解集中包含有礁字；

礁C的彼辍分解集卷6｝，So=C，Si由所有满足下面雨彳脚条件

的S系且成：

(1)Si-iSi=c；

(2)S-i=CSi；

C至有一彳固礁字是另一彳固礁字的前^)

一变长信源编码定理

礁的平均是度(平均礁是)

q

工=»区居

i=1

__H(S)_H(S)

礁率：R=H(X)=F~凡=F~(信道每秒金童的信息量)

(平均每彳固礁元揣带的信息量；编礁俊信道的信息傅率俞率)

-无失真变长信源(辗噪信道)编码定理(香农第一定理)

一个离散无记忆信源S的N次扩展信源”=｛%,。2,…,%、｝,其燧

为H(S*,并有码符号心｛a工2,…再｝。对信源梆进行编码，

总可以找到一种编码方法，构成唯一可译码，使信源S中每

个信源符号所需的平均码长满足

H(S).一1H⑸।1

logrNlogrN

limJ啦

NTOONlogr

无失真信源编码定理可以推广到平稳有记

忆信源

HISS-S)LH(S,S-S)1

---.-2-----N--S---<-----2----N---H---

NlogrNNlogrN

lim^-=—lim—=

N*NlogrN*Nlogr

如果按照/(s)=log-^—来编码，则码长/(s)对确切的概率分布

q3

尸⑸的均值满足

"(P)+。(尸丁)4昂U(s)]<〃(尸)+O(P||q)+1

。(尸im)=Zp(s)iog智

信源的信息嫡是辗失真信源微褊的趣限值

意羲罐褶遭椎怠惮翰率总被於信道容量c的情况下，名鼠能封

信源的输出暹行遹常的褊碣，是的在辗噪瓢损信道上能辗差^

地以最大信息僖翰率c僖输信息，但要令R大於c期是不可能

的；

-编码效率

”(S)

n==----

Llogr

一码的剩余度

H(S)

1F=1-n---

Llogr

6.有噪信道编码定理

费者若不等式：H(X\Y)<H(PE)+PElog(r-1)

H(PJ-接收到Y彼是否曾崖生PE金昔^的不硅定性；

PElog(r-l)-富PE彝生俊，到底是由哪偃I本俞人符虢造成的

金昔^的最大不硅定性；

富信源信道4合定日寺，信道疑羲度H(XIY)就《合定了群礁金磊吴

概率的下限；

可通谩重H樊送，使接收端接收消息畤的金昔咸小；

—信息传输率：氏=等3位畤断鞠的信息量:凡=等

码字距离：是度悬n的雨彳固礁字之^的距离隹指雨偃I礁字之

望寸J1位置上不同礁元的值［数，通常耦:M澳明距H：

n

D(q，Cj)=JX㊉葭

fc-1

51C的最小距翦隹：dmin=min{D(Ci,Cj))；

褊礁逗撵礁字畤，礁字^的距离隹越大越好；

葬礁规即J、编礁方法的逗撵：

(1)最小距离隹儒可能大；

(2)群礁招收到的序列群成典之距离隹最近的哪值I礁字；

(3)令礁是足多句是；

-联合渐近等分割性

对于任意小的正数£沙，8>0,当〃足够大时，有

(1)尸(《“(初21-5

尸(G"))21-J

P{GeSXYy)>\-8

(2)2-»t«(X)«l<p(x)<

2-»(w(n+»]<p(y)<2一"【"⑺田

2-MH(W)+*I<P(孙)<2~"lH(xr)~e,

(3)(1<||G„(X)||<2"lH(x)+t,

(1-3)2"|H“Ms||GOT(r)||s

(1-3)2"阿吁】<||G„(jry)||<

对于任意小的正数£沙，〃足够大时

(])2~nlH(Y]X^2£]<P(y|x)<2~n1H(m~2s]

2~n[H(X\Y^26]4p(x|y)42T1“(Ry)-2€]

(2)11GBl(XIy)1142m因„

11Gtl,(yIx)1142M”小皿

如果文和旷是统计独立的随机序列对，并与P(xy)有相同的边缘

分布，即

(i,y)~P(i)P(y)=P(xy)

则

P[(x,y)eG„(XY)]<2必"W"

并对于任意正数的0,当〃足够大时有

P[(i,y)eG„(AT)]2(1-力2-"<**>""

-有噪信道编码定理(香农第二定理)及其意义

有噪信道编码定理(香农第二定理)

设离散无记忆信道[X,P(y|x),Y],P(y|x)为信道传递概率，其信

道容量为C。当信息传输率H<C时，只要码长〃足够长，总可

以在输入X”符号集中找到M(=2〃R)个码字组成的一组码(2叫〃)

和相应的遥码频mil.他译码的平的槽误棚泵注音小.

设离散无记忆信道[X,P(y|x),Y],其信道容量为C当信息传输

率R>C时，则无论码长〃有多长，总也找不到一种编码

M(=2〃R,〃)，使译码错误概率任意小。

对于限带高斯白噪声加性信道，噪声功率为P〃，带宽为W,信

号平均功率受限为Ps，则

(1)当=+4]时，总可以找到一种信道编码在

信道中以信息传输率(码率)H传输信息，而使平均错误概率

任意小；

(2)当心C,找不到任何信道编码，在信道中以火传输信息而

使平均错误概率任意小。

望寸有噪信道编礁定理的^明：

•信道容量是可达的、最大的可靠信息传输

率

-信息传输率不大于信道容量时，PE以指数趋于0

-信息传输率大于信道容量时，PE以指数趋于1

•香农第二定理说明错误概率趋于0的编码方

法是存在的，但没有给出具体的构造方法。

-联合信源信道编码定理及其意义

如果S〃=(S]S2…S〃)是有限符号集的随机序列并满足渐近等分割

性，又信源S极限懈0〈C则存在信源和信道编码，其

反之，对于任意平稳随机序列，若极限腕8>C，则错误概率

远离0,即不可能在信道中以任意小的错误概率发送随机序列。

7.保真度准则下的信源编码

-失真度d(Ui,Vj)20(单个符号)

-失真矩阵

d(”)火场,匕)…"(%,匕)

d(〃2，W)或〃2，%)…>(〃2,匕)

D=

_d(3)d(“2)…4(%,%)_

-平均失真度：七个信源在某一试验信道下的失真大小；

方=Z切=££尸(%)P(,I4)d(%,4)

U,Vi={7=1

是度:MN的信源符虢序列的失真函数：

N

d(u,v)=d(q.血)=£d(%,4)

/=1

晨度悬N的信源符虢序列的平均失真度：

D(N)=£[d(u,v)]=Z?(uv)d(u,v)=£尸(u)尸(v|u)d(u,v)

uyuy

罩彳固符虢的平均失真度：

11rVs'

氏=五方(%)=^^工尸(%)尸(4阿)或%，4)

|=1j=l

信源和信道都是辗言己il的，信源序列的平均失真度:

_N_

方(N)=ZA

/=1

信源的平均失真度:

瓦=1公N”

N/=1

离散平稳信源

b（N）=Nb

保真度准则，平均失真度不大于所允许的失真

N维信源序列的保真度准则

b（N）£ND

D失真许可的试验信道，满足保真度准则的试

验信道

%={?(,|与)：)40

B0={P(fll\a,Y.b(N^ND]

信息率失真函数的定义：在满足保真度型即下，信源信息傅

输率的下限是多少；

R(D)=min{/(U；P)}

P(vj\ui)eBD

RJD)=min{7(U;V)}

P⑺1%)•万(N)4ND

信息率失真函数和信道容量具有堂寸偶性：

信息传输理论率失真理论

信道P=[P(y\x)]失真测度d(u,v)

信源P=(P(w))

信源P=（尸（源信道P=[P(v|«)]

码C:MfX"信源码CRNTC

错误概率PE平均失真度DN

信道容量率失真函数

V*Z、•，，.\、、

其他性:(1)在一定4勺束脩件下是平均互信息的趣小值；

(2)非负性，下限值卷0；

(3)常R(D)=O日寺，所望切I就是平均失真度的上

界

Dmax，

(4)R(D)是允^失真度D的凸函数；

(5)R(D)在定羲域内速；

(6)R(D)是殿格的罩遮减函数；

—保真度准则下的信源编码定理(香农第三定理)及其意义

设R(Q)为一离散无记忆平稳信源的信息率失真函数，并且有

有限的失真测度。对于任意。NO,8>0,3>0及任意足够长的

码长小则一定存在一种信源编码G其码字个数为

而编码后的平均失真度

d(C)<D+8

反之，

不存在平均失真度为。，而平均信息传输率H'vR(Q)的任何

信源码。即对任意码长为拉的信源码C,若码字个数

~■定有

d(C)>D

意羲：吉兑明在允^失真D的脩件下，信源最小的，可连的信息

傅翰率是信源的R(D)。

一联合有失真信源信道编码定理及其意义

・香晨第一定理+香晨第二定理：

(1)只要信道的信道容量大於信源的趣限嫡，就能在信道中

做到有效地、罪金昔吉吴地傅输信息；

(2)分雨步编礁理方法典一步虑理方法效果一檄好；

・香晨第三定理+香晨第二定理：

(1)如果信源的趣限嫡大於信道的信道容量，只要在允言午一

定失真的脩件下，仍能做到有效和可靠地傅输信息；

如此可1?东内出信息傅翰定理：

(1)离隹散辗言日情信源S的信息率失真函数悬R(D)，离隹散

辗言日情信道的信道容量悬C，如果满足：

C>R(D)

刖信源率俞出的信源序列能再次信道率俞出端重现，其失真

小於等於D。

(2)离隹散罪言己情信源S，其信息率失真函数悬R(D)比特

1

/信源符虢,每秒率俞出目固信源符虢；翳隹散辗言己情信道的

1

信道容量悬c比特/信道符虢，每秒停^Q固信道符虢，

如果满足•

C/?(£))

CS

即信源输出的信息能再此信道输出端重现，其失真小於

等於D。

(3)离隹散辗言己惊信源S，其信息率失真函数:MR(D)比特

1

/信源符虢,每秒输出Q固信源符虢；蹄散辗言引！信道的

1

信道容量卷c比特/信道符虢，每秒僖输Q固信道符虢，

如果:菊足•

C/?(£))

CS

即在信道输出端不能以失真小於等於D再现信源输出的

信息。

用意羲：(1)保真度型即下的信源褊礁定理是有失真信

源JS缩的理^基磁；(2)在允^一定失真度的情沆下，信

源的信息率失真函数可以作悬衡量各槿JE缩编礁方法性能侵

劣的一槿尺度；

-信息率失真函数的计算：

•对称信源（汉明失真）二元封耦信源的信息率失真函数:

H⑼一H(D)0<D<a)

R(O)=・

0D>co

r元堂寸耦信源的信息率失真函数:

0<Z)<l-i

logr-£)log(r-1)-H(D)

R(O)=(r

n>l-i

0

r

•高斯信源（平方误差失真）

—log—D＜（y2

R（O）=j26D

0D＞（T2

8.无失真的信源编码

维失真信源褊碣-熠褊礁

•信源概率分彳布是不均匀的；

•信源是由言己朦的，具有相^性；

•香晨编碣:

逗撵每彳固礁字的是度/i，满足：［/log，］（』，2,…⑼

尸6）

道檬的礁是必定满足满足克拉夫特不等式，一定存在即日寺礁；

平均石身艮不超谩上界：Lavr<%(S)+l

'llai

、P(Si)=-

常满足信源概率分彳布:M,)周日寺，香晨褊礁的平均礁是才

能逵到趣限值；一般情，兄下,香震编礁德岛的不是。

-二元哈夫曼码

•将夕个信源符号按概率分布的大小，以递减次序排列

•把0和1分别分配给概率最小的两个信源符号，并将这两

个信源管骨合并成一个新符号，新符号的概率是这两个

信源待号的概率之和，从而得到只包含1-1个符号的新

信源，称为信源s的缩减信源，

•将缩减信源S］的符号仍按概率大小以递减次序排列，再

将0和1分别芬配给其概率最小的两个符号，并将这两个

符号合并成一个新符号，得到包含q-2个符号的缩减信

源跖

•依次继续，直到缩减信源只包含两个符号为止，将0和1

分别分配给最后两个符号

・4/置患署僖翦恁需为收编码路径由后向前返回，

(fa：(1)得到的礁不是唯一；

(2)如果合彳并彼舆其他信源符虢概率相同，鹰排前；

(3)保晋登了概率大得符虢封鹰短礁，概率小堂拉I是礁，

令短礁得到充分的利用；

(4)每次缩，咸信源的最彼雨值［礁字只有最彼一彳固礁元

不同；

(5)每次缩减信源的最是雨偃I礁字的礁是相同；

-r元哈夫曼码

•每次把r个概率最小的符号合并成一个信源

符号，并分别分配0,1,(r-l)o

•最后一步的缩减信源必须有r个信源符号，

因此信源S的符号个数9必须满足

q=(r-l)0+r

对于给定分布的任何信源，存在一个最佳二元即时码(其平均

码长最短)，此码满足以下性质：

(1)如果Pj>p*，则/jW//。

(2)两个最小概率的信源符号所对应的码字必