信息论与编码

1、弟一早1、信息，信号，消息的区别信息：是事物运动状态或存在方式的不确定性的描述消息是信息的载体，信号是消息的运载工具。2、1948年以通信的数学理论"(Amathematicaltheoryofcommunication)为题公开发表，标志着:信息论的正式诞生。信息论创始人：C.E.Shannon香农)弟早1、自信息量：一个随机事件发生某一结果后所带来的信息量称为自信息量，简称自信息。I(aJ=-logp(aj(2.1.3)单位：比特(2为底)、奈特、笛特(哈特)2、自信息量的性质(1) 是非负值(2) =1时，=0,=1说明该事件是必然事件。(3) =0时，=,=0说明该事件是不可

2、能事件。(4) 是的单调递减函数。3、信源嫡：各离散消息自信息量的数学期望，即信源的平均信息量。1nH(X)=印(马)=Elog2p(ai)10g2p(a)p(a)一单位：比特/符号。(底数不同，单位不同)信源的信息嫡；香农嫡；无条件嫡；嫡函数；嫡。4、信源嫡与信息量的比较嫡信息量有限值可无穷大确定值一般为随机量与信源是否输出有美接收后才得到信息信源的平均不确定度消除不定度得到信息（书14页例2.2.2）5、信源嫡的意义(含义)：(1)信源嫡H(X)表示信源输出后，离散消息所提供的平均信息量。(2)信源嫡H(X)表示信源输出前，信源的平均不确定度。(3)信源嫡H(X)反映了变量X的随机性。6、

3、条件嫡:nmH(X|Y)=EI(aJbj)-'、p(aibj)l(ai|bj)ij1(书15页例2.2.3)7、联合嫡：nmnmH(XY)；二：p(aibj)I(aQj)-%p(aibj)logp(aRj)(2.2.10)i4j4i4jS8、信源嫡，条件嫡，联合嫡三者之间的关系：H(XY)=H(X升H(Y/X)H(XY)=H(Y升H(X/Y)条件嫡小于无条件嫡，H(Y/X户H(Y)0当且仅当y和x相互独立p(y/x)=p(y),H(Y/X)=H(Y)两个条件下的条件嫡小于一个条件下的条件嫡H(Z/X,Y户H(Z/Y)。当且仅当p(z/x,y)=p(z/y)时取等号。联合嫡小于信源嫡之和

4、，H(YX户H(Y)+H(X)当两个集合相互独立时得联合嫡的最大值H(XY)nax=H(X)+H(Y)9、信息嫡的基本性质：(1)非负性；(2)确定性；(3)对称性；(4)扩展性(5)可加性(H(XY)=H(X)+H(Y)X和Y独立H(XY)=H(X)+H(Y/X)H(XY)=H(Y)+H(X/Y)(6)(重点)极值性(最大离散嫡定理):信源中包含n个不同离散消息时，信源嫡H(X)有H(X)£log2n(2.2.12)当且仅当X中各个消息出现的概率全相等时，上式取等号。(7)条件嫡不大于无条件嫡；(8)上凸性10、多符号的离散无记忆信源就是把单符号进行N次扩展，扩展N次后，每个符号的

5、宽度为Np(i);p(ai1，ai24l|,然)NH(X)=H(X)=ip(:i)logp(：i)序列信息的嫡为H(Xn);NH(X)(书22页例2.3.1),H一Ho一H.11、信源的冗余度t=1_n=1_-9=0无H0Ho极限嫡Hg=1flimeHXN/XXX2-XNJLj实际上是一个条件嫡对离散信源，信源符号等概率分布时嫡最大，其平均自信息量记为：Ho=logq由于信源符号间的依赖关系使信源的嫡减小，使下式成立：logq=Ho_H1_H2一一Hmd一一H二信源符号之间依赖关系越强，每个符导提供的平均信息量越小。为此，引入信源的冗余度来衡量信源的相关程度(有时也称为多余度)。课后习题：2.

6、6、无条件概率、条件概率、联合概率之间的关系(11页)代*弟二早1、通信系统的模型：(33页图3.1.1)2、信源编码的目的是提高有效性，信道编码的目的是提高可靠性3、信源编码的分类：(第三个、第四个比较重要)(1)二元码和r元码(2)基本源编码和N次扩展源编码(3)无失真编码和有失真编码数学上称为非奇异码和奇异码，若信源符号和码字是一一对应的，则该码为非奇异码。反之为奇异码。(4)惟一可译码和非惟一可译码唯一可译和非唯一可译：若任意一串有限长的码符号序列只能被惟一地译成所对应的信源符号序列，则此码称为惟一可译码(或称单义可译码)。否则就称为非惟一可译码或非单义可译码。(5)定长码和变长码4、

7、唯一可译码可分为即时码和延时码即时码：如果一个码的任何一个码字都不是其他码字的前缀，则称该码为前缀码、异前置码、异字头码、逗点码，也称为即时码克拉夫特不等式r元长度为li的异前置码存在的充要条件是nqriM1i=1Kraft不等式是惟一可译码存在的充要条件，必要性表现在如果码是惟一可译码，则必定满足Kraft不等式；充分性表现在如果满足Kraft不等式，则这种码长的惟一可译码一定存在，但并不表示所有满足Kraft不等式的码一定是惟一可译码。因此，克拉夫特不等式是惟一可译码存在的充要条件，而不是惟一可译码的充要条件。如果一个码是即时码，它一定满足克拉夫特不等式如果一个码满足这个不等式，它不一定是

8、即时码奇异码与唯一可译之间的关系：奇异码一定非唯一可译唯一可译码与非奇异之间的关系：唯一可译码一定是非奇异码，但非奇异码不一定唯一可译5、香农第一定理：无失真变长信源编码定理，即香农第一定理。定理(无失真变长信源编码定理，即香农第一定理)离散无一记忆信源s的X次扩展，；源药0分,其烯为H(/),并行他符弓X=Qj对储源窑用进行编码，总可以找到种编码方法,构成唯灯十%使信源S中每个信源符号所需的平均码长满足方1以丹(S)=+,logvNNlog:或拧与2m(5,vs)当.vi%n寸，则得_k返二凡(S)15.kv'式中_产£*=E严9/马15.80)/=J二是无记忆扩展佶源5&

9、quot;中每个符匕%的平均码岛萼仍是佶源S中年JV一单个信源符号所需的平均码长6、香农编码(书38页)7、费诺编码(书39页)8、赫夫曼编码(书40页)9、这三种码中编码方法唯一的是：香农码费诺码是最理想化的编码第四章1、互信息量关于它的定义有三个：定义1:我们将从bj中获取有关ai的信息量称为互信息量P(aibj)P(ai)定义2:将互信息表达式展开得：I(ai；bj)=-logp(ai)logp(abj)=Ig)-1(a/bj)同样道理，我们可以定义ai对bj的互信息量为p(bjai).I(bj；ai)=logI(bj)-I(bj.a)P(bj)(2.1.9)(i=1,2,n;j=1,2

10、,口定义3通信后流经信道的信息量，等于通信前后不定度的差I(a;bj)=I(aQj)-I(aibj),1,1二log-logp(a)p(Q)p(M)p(aib).=log(i=1,2,n;j=1,2,m)p(a)p(bj)2、互信息量的性质:(1)对称性I(q;bj)=I(")(2)当X和Y相互独立时，互信息为0(3)互信息量可为正值或负值3、平均互信息量(重点)平均互信息量的定义(三个)及其物理意义(53页)关于式子的证明过程(式子之间的转换，很重要)4、平均互信息的性质：(1)非负性(2)极值性I(X;Y)£H(X)I(Y;X)<H(Y)(3)对称性(4)凸函数性

11、(最重要)定理1对于固定的信道，平均互信息I(X;Y尾信源概率分布p(x)的上凸函数定理2对于固定的信源，平均互信息I(X;Y)(言道传递方率分布p(y|x)的下凸函数(5)数据处理定理5、各种嫡之间的关系(62页表4.1.1)6、信道容量：信道中最大的传输速率，C,单位：比特/信道符号单位时间的信道容量，比特/秒-1C=maxR=-maxI(X;Y)P(ai)tP(ai)信道容量的计算C=maxI(X;Y)p(ai)=maxH(X)-H(XY)1P(ai)=maxH(Y)-H(Y,X)1P(a。7、怎么样去判断信道：第一类：离散无噪信道(1)对应的无噪信道X、Y对应，此时H(X/Y)=0,H

12、(Y/X)=0,=logn(p(ai)=1/n即等概)(2)具有扩展功能的无噪信道一个输入对应多个输出，此时，H(X/Y)=0,H(Y/X)0,且H(X)<H(Y)所以，C=H(X)=logn(p(ai)=1/n即等概)(3)具有归并性的无噪信道多个输入变成一个输出，H(X/Y)丰、0H(Y/X)=0,C=H(Y)=logm第二类：对称信道：如果信道转移矩阵满足下列性质：(1)每行都是第一行的某种置换；(2)每列都是第一列的某种置换。则称该信道为对称信道。(1)对称信道的信道容量：C=maxI(X,Y)=logm-H(qa,qm)P(a)(2)准对称信道：如果信道转移矩阵按列可以划分为几

13、个互不相交的对称信道的子集，则称该信道为准对称信道。准对称信道的信道容量(重点)：C=(1-q)log(1-q)+(1-q)log-2-=1-q比特/符号1-q(书69页例421)第五章1、线性分组码差错控制的方式：向前纠错方式(FE。、反馈重传方式(ARQ)、混合纠错方式(HE。2、香农第二定理：若有一离散无记忆平稳信道，其容量为C,输入序列长度为L,只要待传送的信息率R<C,总可以找到一种编码，当L足够长时，译码差错概率Pe<£,£为任意大于零的正数。反之，当R>C时，任何编码的Pe必大于零；当L-时，H1。3、线性分组码：通过预定的线性运算将长为k位的信息码组变换成n长的码字(n>k)由2k个信息码组所编成的2k个码字集合，称为线性分组码。码矢:一个n长的码字可以用矢量来表示C=(Cn-1,Cn-2,"Ci,C0)所以码字又称为码矢。（n,k）线性码:信息位长为k,码长为n的线性码编码效率/编码速率/码率:R=k/n。它说明了信道的利用效率，R是衡量码性能的一个重要参数。4、线性分组码的特点（性质）：在码集中存在全0码字满足封闭性定理：线性分组码的最小距离等于最小非零码字重量。do=minw（c） 汉明重量：码字中非0码的个数。 最小汉明重量：码集中非0码字汉明重量的最小值。 汉明距离：两个等