信息论基础复习提纲_图文

1、第一章 绪论1、什么是信息?香农对于信息是如何定义的。答:信息是事物运动状态或存在方式的不确定性的描述(Information is a measure of one's freedom of choice when one selects a message 。2、简述通信系统模型的组成及各部分的含义。答:(1、信源:信源是产生消息的源。信源产生信息的速率-熵率。 (2、编码器:编码器是将消息变成适合于信道传送的信号的设备。包括信源编码器(提高传输效率、信道编码器(提高传输可靠性、调制器。(3、信道:信道是信息传输和存储的媒介。(4、译码器:译码是编码的逆变换,分为信道译码和信源译码

2、。 (5、信宿:信宿是消息的接收者(人或机器。3、简述香农信息论的核心及其特点。答:(1、香农信息论的核心:在通信系统中采用适当的编码后能够实现高效率和高可靠性的信息传输,并得出了信源编码定理和信道编码定理。(2、特点:、以概率论、随机过程为基本研究工具。、研究的是通信系统的整个过程,而不是单个环节,并以编、译码器为重点。 、关心的是最优系统的性能和怎样达到这个性能(并不具体设计系统。 、要求信源为随机过程,不研究信宿。第二章 信息的度量2.1 自信息和互信息1、自信息(量:(1、定义:一个事件(消息本身所包含的信息量,它是由事件的不确定性决定的。某个消息i x 出现的不确定性的大小定义为自信

3、息,用这个消息出现的概率的对数的负值来表示: (2、性质:、(i x I是(i x p 的严格递减函数。当(21x p x p <时 (21x I x I >概率越小,事件发生的不确定性越大,事件发生以后所包含的自信息量越大。、极限情况下,当(0=i x p 时(i x I ;当(1=i x p 时,(0i x I 。、两个相对独立的不同的消息所提供的信息量应等于它们分别提供的信息量之和,即自信息论满足可加性。(21212121;x I x I x x I x p x p x x p +=。(i i i x p x p x I 1loglog =-=(3、例2.1:、英文字母中“a

4、 ”出现的概率为0.064,“c”出现的概率为0.022,分别计算他们的自信息量。 、假定前后字母出现是互相独立的,计算“ac ”的自信息。、假定前后字母出现不是互相独立的,当“a”出现以后, “c ”出现的概率为0.04,计算“a ”出现以后, “c ”出现的自信息量。2、互信息:一个事件j y 所给出关于另一个事件i x 的信息定义为互信息,用(j i y x I ;表示:(j i j i j i j i j j i j i j i i j i y p x p y x p y p x y p x y I y I x p y x p y x I x I y x I =-=-=log|log

5、|log|; 2.2 平均自信息1、定义:随机变量X 的每一个可能取值的自信息(i x I 的统计平均值定义为随机变量X 的平均自信息量。2、熵函数的性质:(1、对称性: (2、确定性: (3、非负性: (4、扩展性: (5、连续性: (6、递推性: (7、极值性: (8、上凸性: 3、联合熵:联合自信息的 数学期望。它是二维随机 变量XY 的不确定性的度量。 4、条件熵:5、各类熵之间的关系:(1、联合熵与信息熵、条件熵之间的关系:/(X Y H X H XY H +=。推广:(12112121/-+=N N N X X X X H X X H X H X X X H;当二维随机变量X,Y

6、相互独立时,联合熵等于X,Y 各自熵之和。(Y H X H XY H +=。(2、条件熵与信息熵的关系:(/(X H Y XH ;(/(Y H X Y H = 。(3、联合熵与信息熵的关系:(Y H X H XY H +当X 、Y 相互独立时等号成立。推广到N 个随机变量:(N N X H X H X H X X X H+2121。21(log(qi ii i H X E I x p x p x =-21111(log (n m n mi j i j i j i j i j i j H XY p x y I x y p x y p x y =-22(/(/X Y (/X(log (/ (X /

7、(log (/i i i i j j i i j i j ijijx H Y x H Y x H Y p x y p y x H Y p x y p x y =-=-由于不同的,是变化的,对的所有可能值进行统计平均,就得出给定时,的条件熵122111(,(,(,q q q q H p p p H p p p H p p p -=(1,0(1,00(1,0,0=0H H H =,12(,0q H p H p p p =112120lim (,(,q q q q H p p p H p p p +-=121120lim (,(,q q q H p p p p H p p p -+=12121121

8、2(,(,(,m n m n n n n nq q q H p p p q q q H p p p p H p p p -=+122111(,(,log n H p p p pH nn n n=1212(1(1(f x x f x f x +-+- 6、例2.5:随机变量X ,Y 的联合概率分布如表2.1所示,求联合熵(XY H 和条件熵(X Y H |。2.3 平均互信息1、定义:从整体上表示从一个随机变量Y 所给出关于另一个随机变量X 的信息量,定义互信息(j i y x I ;在XY 的联合空间中的统计平均值为随机变量X 和Y 间的平均互信息。(Y X H X H y x p y x p

9、 x p y x p x p y x p y x p y x I y x p Y X I mj j i j i ni mj i j i ni mj i j i j i ni m j j i j i ni |1log;1log;|log ;11111111-=-=条件熵(Y X H|表示给定随机变量Y 后,对随机变量X 仍然存在的不确定度。所以Y 关于X 的平均互信息是收到Y 前后关于X 的不确定度减少的量,也就是从Y 获得的关于X 的平均信息量。2、平均互信息的性质:(1、非负性:(0;Y X I;(2、互易性(对称性:(X Y I Y X I;=;(3、平均互信息与各类熵之间的关系:( X

10、H X Y H Y H Y X H X H Y X I =-=-=/;当X,Y 统计独立时,(0;=Y X I 。(请补充完善右图(4、极值性:(Y H Y X I X H Y X I;,;(5、凸函数性:、当条件概率分布(|i j x y p给定时,平均互信息(Y X I ;是输入分布(i x p 的上凸函数。、对于固定的输入分布(i x p,平均互信息量(Y X I ;是条件概率分布(|i j x y p 的下凸函数。 3、例2.15:给定X,Y 的联合概率分布,如表所示。求: (1、H(X,H(Y; (2、H(X|Y,H(Y|X; (3、H(XY; (4、H(Y-H(Y|X;(5、I(X

11、;Y;第三章 信源及信源熵3.1信源的分类(弄清楚以下信源分类的标准(非平稳信源连续平稳信源马尔科夫信源记忆长度有限记忆长度无限离散有记忆信源离散无记忆信源离散平稳信源平稳信源波形信源随机过程: 3.3 离散多符号信源1、离散平稳信源的特征:统计特性不随时间推移而变化。2、熵率:随机变量序列中,对前N 个随机变量的联合熵求平均:(N N X X X H NX H 211=称为平均符号熵。如果当N 时上式极限存在,则(X H N N lim 称为熵率,或称为极限熵,记为(X H H N N =lim 。3、离散平稳信源的几点结论(小题: (1、条件熵(121|-N N X X X X H随N 的

12、增加是递减的(即已知条件越多,不确定性越少;(2、N 给定时平均符号熵大于等于条件熵,即(121|-N N N X X X X H X H ;(3、平均符号熵(X H N 随N 的增加是递减的;(4、如果(<1X H,则(X H H N N =lim 存在,并且(121|lim lim -=N N N N N X X X X H X H H ; 4、马尔科夫信源:信源在某一时刻发出某一符号的概率除与该符号有关外,只与此前发出的有限个符号有关。M 阶马尔可夫信源只与前面发出的m 个符号有关,1阶马尔可夫信源只与前面一个符号有关。5、例题3.3:信源X 的信源模型为输出号有记忆,条件概率(1

13、2|X X P 给出,求熵率,并比较(12|X X H 、(2121X X H 和(X H 的大小。1231411(4936xx x X P X =第五章 无失真信源编码5.1 信源编码的相关概念1、各种码的分类: (1、分组码和非分组码:、分组码:将信源符号集中的每个信源符号si 固定地射成一个码字wi 。(一个信源符号一个码字、非分组码:又称树码,编码器输出的码符号通常与编码器的所有信源符号都有关。 (2、奇异码与非奇异码:定义 若一种分组码中的所有码字都不相同,则称此分组码为非奇异码,否则称为奇异码。非奇异码是分组码能够正确译码的必要条件,而不是充分条件。 (3、唯一可译码与非唯一可译码

14、:定义 任意有限长的码元序列,如果只能唯一地分割成一个个码字,便称为唯一可译码。条件:、此码本身是非奇异的;、对于任意有限的整数N,其N 次扩展码均为非奇异的。唯一可译码首先是非奇异码,且任意有限长的码字序列不会雷同。 (4、即时码与非即时码:定义 无需考虑后续的码符号就可以从 码符号序列中译出码字,这样的唯一可译码称为即时码。 条件:、此码是唯一可译码;、不需要通过接收到后面的码字才能译出前面的码字,在收到一个完整的码字后即可以及时译出。一个唯一可译码成为即时码的充要条件是其中任何一个码字都不是其他码字的前缀。5.3、变长码及变长信源编码定理1、Kraft 不等式McMillan 不等式:(

15、1、Kraft 不等式:设信源符号集为S=s1,s2,sq,码符号集为X=x1,x2,xr,对信源进行编码,得到的码为C= w1,w2,wq,码长分别为l1,l2,lq.即时码存在的充要条件是11=-qi l ir这称为Kraft不等式(其中r 是被编码的符号个数;q 是信源个数;l i 是码的长度。这也就意味着即时码存在于二叉树的叶子节点处。(2、McMillan 不等式:判断唯一可译码的条件与即时码条件一致,都是11=-qi l ir,条件并不比即时码判断条件宽松。2、唯一可译码的判别准则:定理 一个码是唯一可译码的充要条件是F1,F2,的并集中没有C 中的码字。 设C 为码字集合,我们要

16、构造尾随后缀的集合F1,F2,和F 。(1、F1是C 中所有码字尾随后缀的集合:若C 中的码字j w 是码字i w 的前缀,即i w =A w j ,则将尾随后缀A 列为F1中的元素,所有这样的尾随后缀构成了F1;(2、考查C 和Fi 两个集合,若C 中任意码字是Fi 中元素的前缀,或者Fi 中任意元素是C 中码字的前缀,则将其相应的尾随后缀放入集合1+i F ;非及时码及时码唯一可译码非唯一可译码非奇异码奇异码分组码非分组码码(3、 ii F F=(即F 为码C 的尾随后缀集合; (4、若F 中出现了C 中的元素,则算法终止,判断C 不是唯一可译码;若出现1+i F 为空集或1+i F 中的

17、元素在F 中已经全部存在了,则算法终止,判断C 是唯一可译码。总而言之,判断一个码是唯一可译码的充要条件是F 中不含有C 中的码字。3、例5.4:设消息集合共有7个元素s1,s2,s3,s4,s5,s6,s7,他们分别被编码为a ,c ,ad ,abb ,bad ,deb ,bbcde,判断是否为唯一可译码。5.4 变长码的编码方法1、香农编码的方法:(1、信源的q 个消息概率从大到小排序,(q s p s p s p 21;(2.计算各个信源符号的累加概率(q i s p s Fi k k i ,2,111=-= ;(3.按公式(q i s p l i i,2,11log =计算第i 个消息

18、的码长i l ;(4.将累加概率(i s F变换成二进制小数得到其码字。将累加概率(i s F 变换成二进制小数,取小数点后i l 位数作为第i 个信源符号的码字。2、列5.6:参照下表按以上步骤对一个有7个信源符号的信源进行编码。例如当4=i 时,先求第四个信源符号的二元码码长4l :(3log 44=-=s p l ,因此码长取3. 3、二元霍夫曼编码的方法:(1、信源的q 个消息概率从大到小排序(q s p s p s p 21。(2、0,1码分别代表概率最小的两个信源符号,并将这两个概率最小的信源符号合并成一个,从而得到只包括q-1个符号的新信源。(3、将新信源仍按概率从大到小排序,再

19、将最后两个概率最小的信源符号分别用0和1码符号表示,合并成一个新符号,这样形成了q-2个符号的新信源。(4、依次继续下去,直至信源最后只剩下两个信源符号为止。将这最后两个信源符号用0和1表示。(5、从最后一级缩减信源开始,进行回溯,将每次标注的码符号连接起来就得到各信源符号所对应的码符号序列,即相应的码字。4、例5.7:以例5.6为例编制二元霍夫曼码。 5、费诺编码的过程:(1、信源的q 个消息概率从大到小排序。即(q s p s p s p 21。(2、将依次排列的信源符号以概率分为两组,使两组的概率和基本相等。并赋予符号0和1。 (3、再分组,使划分后的两组的概率和基本相等,并赋予符号0和

20、1。 (4、重复,直至每组只剩下一个信源符号为止。 (5、信源符号对应的码符号序列即为费诺码。6、例5.9:信源与例5.6和例5.7相同,请编制费诺码。 7、总结:霍夫曼码是即时码,他的两个特点:(1保证了概率大的信源符号对应的码长小,概率小的信源符号对应的码长大,充分利用了短码; (2每次缩减信源的最长两个码字有相同的码长,最后一位码符号不同。(码长相差的小 编码最短,传输效率最高。8、习题5.8:下面是4种不同的编码:000,10,00,11;100,101,0,11;01,100,011,00,111,1010,1011,1101;01,111,011,00,010,110; 请计算:(

21、1、此码的码长分布是否满足Kraft-McMillan 不等式?(2、此码是否为即时码?如果不是,请说明。(3、此码是否为唯一可译码?如果不是,请说明(可以画出树图说明。5.5实用的无失真编码方法各种编码的应用(小题:(1、游程编码(REL,REC 应用于:BMP TIF AVI ; (2、LZW 码应用于:GIF ZIP ARC ; (3、算术编码应用于:JPEG2000;参考答案例2.1:、 、由于前后字母出现是互相独立的,“ac ”出现的概率为0.064*0.022,所以即两个相对独立的事件的自信息量满足可加性,也就是由两个相对独立的事件的积事件所提供的信息量应等于他们分别提供的信息量之

22、和。、“a ”出现的条件下,“c ”出现的频率变大,它的不确定性变小。例2.5:(联合符号比特/231212422log 214log 422/11log 214/11log 414/11log 41=+=+=+=XY H 由联合概率分布得X 的边缘概率分布: 211,210X=X P P 和条件概率分布(i j x y p |(如表2.2所示,得到(01|,10|=X Y H X Y H 和(21021121|=+=X Y H 。注意到(X Y H H Y H|218113.041=>= =。例2.15:由X,Y 的联合概率分布求出X,Y 的边缘概率分布如下图表所示: 例3.3:(1、熵率:(符号比特/870.01|22=X X H H H ; (2、如果不