信息论基础复习提纲

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

哈尔滨医科大学生物信息科学与技术学院信息论基础第-1-页共10页第一章绪论1、什么是信息?香农对于信息是如何定义的。答:信息是事物运动状态或存在方式的不确定性的描述(Informationisameasureofone'sfreedomofchoicewhenoneselectsamessage)。2、简述通信系统模型的组成及各部分的含义。答:(1)、信源:信源是产生消息的源。信源产生信息的速率---熵率。(2)、编码器:编码器是将消息变成适合于信道传送的信号的设备。包括信源编码器(提高传输效率)、信道编码器(提高传输可靠性)、调制器。(3)、信道:信道是信息传输和存储的媒介。(4)、译码器:译码是编码的逆变换,分为信道译码和信源译码。(5)、信宿:信宿是消息的接收者(人或机器)。3、简述香农信息论的核心及其特点。答:(1)、香农信息论的核心:在通信系统中采用适当的编码后能够实现高效率和高可靠性的信息传输,并得出了信源编码定理和信道编码定理。(2)、特点:①、以概率论、随机过程为基本研究工具。②、研究的是通信系统的整个过程,而不是单个环节,并以编、译码器为重点。③、关心的是最优系统的性能和怎样达到这个性能(并不具体设计系统)。④、要求信源为随机过程,不研究信宿。第二章信息的度量2.1自信息和互信息1、自信息(量):(1)、定义:一个事件(消息)本身所包含的信息量,它是由事件的不确定性决定的。某个消息ix出现的不确定性的大小定义为自信息,用这个消息出现的概率的对数的负值来表示:(2)、性质:①、ixI是ixp的严格递减函数。当21xpxp时21xIxI概率越小,事件发生的不确定性越大,事件发生以后所包含的自信息量越大。②、极限情况下,当0ixp时ixI;当1ixp时,0ixI。③、两个相对独立的不同的消息所提供的信息量应等于它们分别提供的信息量之和,即自信息论满足可加性。21212121;xIxIxxIxpxpxxp。iiixpxpxI1loglog哈尔滨医科大学生物信息科学与技术学院信息论基础第-2-页共10页(3)、例2.1:①、英文字母中“a”出现的概率为0.064,“c”出现的概率为0.022,分别计算他们的自信息量。②、假定前后字母出现是互相独立的,计算“ac”的自信息。③、假定前后字母出现不是互相独立的,当“a”出现以后,“c”出现的概率为0.04,计算“a”出现以后,“c”出现的自信息量。2、互信息:一个事件jy所给出关于另一个事件ix的信息定义为互信息,用jiyxI;表示:jijijijijjijijiijiypxpyxpypxypxyIyIxpyxpyxIxIyxIlog|log||log|;2.2平均自信息1、定义:随机变量X的每一个可能取值的自信息ixI的统计平均值定义为随机变量X的平均自信息量。2、熵函数的性质:(1)、对称性:(2)、确定性:(3)、非负性:(4)、扩展性:(5)、连续性:(6)、递推性:(7)、极值性:(8)、上凸性:3、联合熵:联合自信息的数学期望。它是二维随机变量XY的不确定性的度量。4、条件熵:5、各类熵之间的关系:(1)、联合熵与信息熵、条件熵之间的关系:)/()()(XYHXHXYH。推广:12112121//NNNXXXXHXXHXHXXXH;当二维随机变量X,Y相互独立时,联合熵等于X,Y各自熵之和。)()()(YHXHXYH。(2)、条件熵与信息熵的关系:)()/(XHYXH;)()/(YHXYH。(3)、联合熵与信息熵的关系:)()()(YHXHXYH当X、Y相互独立时等号成立。推广到N个随机变量:NNXHXHXHXXXH2121。21()[()]()log()qiiiiHXEIxpxpx21111()()()()log()nmnmijijijijijijHXYpxyIxypxypxy22(/)(/)XY(/X)()log(/)(X/)()log(/)iiiijjiijijijijxHYxHYxHYpxypyxHYpxypxy由于不同的,是变化的,对的所有可能值进行统计平均,就得出给定时,的条件熵122111(,,)(,,)(,,)qqqqHpppHpppHppp(1,0)(1,00)(1,0,0)=0HHH,12()(,,)0qHpHppp112120lim(,,,)(,,)qqqqHpppHppp121120lim(,,,)(,,)qqqHppppHppp121211212(,,,,)(,,)(,,)mnmnnnnnqqqHpppqqqHppppHppp122111(,,)(,,)lognHppppHnnnn1212[(1)]()(1)()fxxfxfx哈尔滨医科大学生物信息科学与技术学院信息论基础第-3-页共10页6、例2.5:随机变量X,Y的联合概率分布如表2.1所示,求联合熵XYH和条件熵XYH|。2.3平均互信息1、定义:从整体上表示从一个随机变量Y所给出关于另一个随机变量X的信息量,定义互信息jiyxI;在XY的联合空间中的统计平均值为随机变量X和Y间的平均互信息。YXHXHyxpyxpxpyxpxpyxpyxpyxIyxpYXImjjijinimjijinimjijijinimjjijini||1log;1log;|log;;;;11111111条件熵YXH|表示给定随机变量Y后,对随机变量X仍然存在的不确定度。所以Y关于X的平均互信息是收到Y前后关于X的不确定度减少的量,也就是从Y获得的关于X的平均信息量。2、平均互信息的性质:(1)、非负性:0;YXI;(2)、互易性(对称性):XYIYXI;;;(3)、平均互信息与各类熵之间的关系:XYHYHXHXYHYHYXHXHYXI//;;当X,Y统计独立时,0;YXI。(请补充完善右图)(4)、极值性:YHYXIXHYXI;,;;(5)、凸函数性:①、当条件概率分布}|{ijxyp给定时,平均互信息YXI;是输入分布}{ixp的上凸函数。②、对于固定的输入分布}{ixp,平均互信息量YXI;是条件概率分布}|{ijxyp的下凸函数。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;Y);表2.1X,Y的联合概率分布XYPYX01ixp011/41/41/201/21/2jyp3/41/41表2.2条件概率分布XYP|YX01011/21/210哈尔滨医科大学生物信息科学与技术学院信息论基础第-4-页共10页第三章信源及信源熵3.1信源的分类(弄清楚以下信源分类的标准)非平稳信源连续平稳信源马尔科夫信源记忆长度有限记忆长度无限离散有记忆信源离散无记忆信源离散平稳信源平稳信源波形信源随机过程:3.3离散多符号信源1、离散平稳信源的特征:统计特性不随时间推移而变化。2、熵率:随机变量序列中,对前N个随机变量的联合熵求平均:NNXXXHNXH211称为平均符号熵。如果当N时上式极限存在,则XHNNlim称为熵率,或称为极限熵,记为XHHNNlim。3、离散平稳信源的几点结论(小题):(1)、条件熵121|NNXXXXH随N的增加是递减的(即已知条件越多,不确定性越少);(2)、N给定时平均符号熵大于等于条件熵,即121|NNNXXXXHXH;(3)、平均符号熵XHN随N的增加是递减的;(4)、如果1XH,则XHHNNlim存在,并且121|limlimNNNNNXXXXHXHH;4、马尔科夫信源:信源在某一时刻发出某一符号的概率除与该符号有关外,只与此前发出的有限个符号有关。M阶马尔可夫信源只与前面发出的m个符号有关,1阶马尔可夫信源只与前面一个符号有关。5、例题3.3:信源X的信源模型为输出符号序列中,只有前后两个符号有记忆,条件概率12|XXP给出,求熵率,并比较12|XXH、2121XXH和XH的大小。1231411()4936xxxXPX哈尔滨医科大学生物信息科学与技术学院信息论基础第-5-页共10页第五章无失真信源编码5.1信源编码的相关概念1、各种码的分类:(1)、分组码和非分组码:①、分组码:将信源符号集中的每个信源符号si固定地射成一个码字wi。(一个信源符号→一个码字)②、非分组码:又称树码,编码器输出的码符号通常与编码器的所有信源符号都有关。(2)、奇异码与非奇异码:定义若一种分组码中的所有码字都不相同,则称此分组码为非奇异码,否则称为奇异码。非奇异码是分组码能够正确译码的必要条件,而不是充分条件。(3)、唯一可译码与非唯一可译码:定义任意有限长的码元序列,如果只能唯一地分割成一个个码字,便称为唯一可译码。条件:①、此码本身是非奇异的;②、对于任意有限的整数N,其N次扩展码均为非奇异的。唯一可译码首先是非奇异码,且任意有限长的码字序列不会雷同。(4)、即时码与非即时码:定义无需考虑后续的码符号就可以从码符号序列中译出码字,这样的唯一可译码称为即时码。条件:①、此码是唯一可译码;②、不需要通过接收到后面的码字才能译出前面的码字,在收到一个完整的码字后即可以及时译出。一个唯一可译码成为即时码的充要条件是其中任何一个码字都不是其他码字的前缀。5.3、变长码及变长信源编码定理1、Kraft不等式McMillan不等式:(1)、Kraft不等式:设信源符号集为S={s1,s2,…sq},码符号集为X={x1,x2,…xr},对信源进行编码,得到的码为C={w1,w2,…wq},码长分别为l1,l2,…lq.即时码存在的充要条件是11qilir这称为Kraft不等式(其中r是被编码的符号个数;q是信源个数;li是码的长度)。这也就意味着即时码存在于二叉树的叶子节点处。(2)、McMillan不等式:判断唯一可译码的条件与即时码条件一致,都是11qilir,条件并不比即时码判断条件宽松。2、唯一可译码的判别准则:定理一个码是唯一可译码的充要条件是F1,F2,…的并集中没有C中的码字。设C为码字集合,我们要构造尾随后缀的集合F1,F2,…和F。(1)、F1是C中所有码字尾随后缀的集合:若C中的码字jw是码字iw的前缀,即iw=Awj,则将尾随后缀A列为F1中的元素,所有这样的尾随后缀构成了F1;(2)、考查C和Fi两个集合,若C中任意码字是Fi中元素的前缀,或者Fi中任意元素是C中码字的前缀,则将其相应的尾随后缀放入集合1iF;非及时码及时码唯一可译码非唯一可译码非奇异码奇异码分组码非分组码码哈尔滨医科大学生物信息科学与技术学院信息论基础第-6-页共10页(3)、iiFF(即F为码C的尾随后缀集合);(4)、若F中出现了C中的元素,则算法终止,判断C不是唯一可译码;若出现1iF为空集或1iF中的元素在F中已经全部存在了,则算法终止,判断C是唯一可译码。总而言之,

1 / 10
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功