信息论基础复习提纲.docVIP

哈尔滨医科大学生物信息科学与技术学院第一章 绪论1、什么是信息？香农对于信息是如何定义的。答：信息是事物运动状态或存在方式的不确定性的描述(Information is a measure of ones freedom of choice when one selects a message)。2、简述通信系统模型的组成及各部分的含义。答：（1）、信源：信源是产生消息的源。信源产生信息的速率-熵率。（2）、编码器：编码器是将消息变成适合于信道传送的信号的设备。包括信源编码器（提高传输效率）、信道编码器（提高传输可靠性）、调制器。（3）、信道：信道是信息传输和存储的媒介。（4）、译码器：译码是编码的逆变换，分为信道译码和信源译码。（5）、信宿：信宿是消息的接收者（人或机器）。3、简述香农信息论的核心及其特点。答：（1）、香农信息论的核心：在通信系统中采用适当的编码后能够实现高效率和高可靠性的信息传输，并得出了信源编码定理和信道编码定理。（2）、特点：、以概率论、随机过程为基本研究工具。、研究的是通信系统的整个过程，而不是单个环节，并以编、译码器为重点。、关心的是最优系统的性能和怎样达到这个性能（并不具体设计系统）。、要求信源为随机过程，不研究信宿。第二章 信息的度量2.1 自信息和互信息1、自信息（量）：（1）、定义：一个事件（消息）本身所包含的信息量，它是由事件的不确定性决定的。某个消息出现的不确定性的大小定义为自信息，用这个消息出现的概率的对数的负值来表示：（2）、性质：、是的严格递减函数。当时概率越小，事件发生的不确定性越大，事件发生以后所包含的自信息量越大。、极限情况下，当时；当时，。 、两个相对独立的不同的消息所提供的信息量应等于它们分别提供的信息量之和，即自信息论满足可加性。（3）、例2.1：、英文字母中“a”出现的概率为0.064，“c”出现的概率为0.022，分别计算他们的自信息量。、假定前后字母出现是互相独立的，计算“ac”的自信息。、假定前后字母出现不是互相独立的，当“a”出现以后， “c”出现的概率为0.04，计算“a”出现以后， “c”出现的自信息量。2、互信息：一个事件所给出关于另一个事件的信息定义为互信息，用表示：2.2 平均自信息1、定义：随机变量X的每一个可能取值的自信息的统计平均值定义为随机变量X的平均自信息量。2、熵函数的性质：（1）、对称性：（2）、确定性：（3）、非负性：（4）、扩展性：（5）、连续性：（6）、递推性：（7）、极值性：（8）、上凸性：3、联合熵：联合自信息的数学期望。它是二维随机变量XY的不确定性的度量。4、条件熵： 5、各类熵之间的关系： （1）、联合熵与信息熵、条件熵之间的关系：。 推广：;当二维随机变量X,Y相互独立时，联合熵等于X,Y各自熵之和。 （2）、条件熵与信息熵的关系：; 。 （3）、联合熵与信息熵的关系：当X、Y相互独立时等号成立。推广到N个随机变量：。6、例2.5：随机变量X，Y的联合概率分布如表2.1所示，求联合熵和条件熵。表2.1 X,Y的联合概率分布YX0 1011/4 1/41/2 0 1/2 1/23/4 1/4 1表2.2 条件概率分布 YX0 1011/2 1/21 02.3 平均互信息1、定义：从整体上表示从一个随机变量Y所给出关于另一个随机变量X的信息量，定义互信息在XY的联合空间中的统计平均值为随机变量X和Y间的平均互信息。条件熵表示给定随机变量Y后，对随机变量X仍然存在的不确定度。所以Y关于X的平均互信息是收到Y前后关于X的不确定度减少的量，也就是从Y获得的关于X的平均信息量。2、平均互信息的性质：（1）、非负性：；（2）、互易性（对称性）：；（3）、平均互信息与各类熵之间的关系：；当X,Y统计独立时，。（请补充完善右图）（4）、极值性：；（5）、凸函数性：、当条件概率分布给定时，平均互信息是输入分布的上凸函数。、对于固定的输入分布，平均互信息量是条件概率分布的下凸函数。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)；第三章 信源及信源熵3.1信源的分类（弄清楚以下信源分类的标准） 3.3 离散多符号信源1、离散平稳信源的特征：统计特性不随时间推移而变化。2、熵率：随机变量序列中，对前N个随机变量的联合熵求平均：称为平均符号熵。如果当时上式极限存在，则称为熵率，或称为极限熵，记为。3、离散平稳信源的几点结论（小题）：（1）、条件熵随N的增加是递减的（即已知条件越多，不确定性越少）；（2）、N给定时平均符号熵大于等于条件熵，即；（3）、平均符号熵随N的增加是递减的；（4）、如果，则存在，并且；4、马尔科夫信源：信源在某一时刻发出某一符号的概率除与该符号有关外，只与此前发出的有限个符号有关。M阶马尔可夫信源只与前面发出的m个符号有关，1阶马尔可夫信源只与前面一个符号有关。5、例题3.3：信源X的信源模型为输出符号序列中，只有前后两个符号有记忆，条件概率给出，求熵率，并比较、和的大小。第五章 无失真信源编码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.即时码存在的充要条件是这称为Kraft不等式（其中r是被编码的符号个数；q是信源个数；li是码的长度）。这也就意味着即时码存在于二叉树的叶子节点处。（2）、McMillan不等式：判断唯一可译码的条件与即时码条件一致，都是，条件并不比即时码判断条件宽松。2、唯一可译码的判别准则：定理 一个码是唯一可译码的充要条件是F1,F2,的并集中没有C中的码字。设C为码字集合，我们要构造尾随后缀的集合F1，F2，和F。（1）、F1是C中所有码字尾随后缀的集合：若C中的码字是码字的前缀，即=，则将尾随后缀A列为F1中的元素，所有这样的尾随后缀构成了F1；（2）、考查C和Fi两个集合，若C中任意码字是Fi中元素的前缀，或者Fi中任意元素是C中码字的前缀，则将其相应的尾随后缀放入集合；（3）、（即F为码C的尾随后缀集合）；（4）、若F中出现了C中的元素，则算法终止，判断C不是唯一可译码；若出现为空集或中的元素在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个消息概率从大到小排序，；（2）.计算各个信源符号的累加概率 ；（3）.按公式计算第个消息的码长；（4）.将累加概率变换成二进制小数得到其码字。将累加概率变换成二进制小数，取小数点后位数作为第个信源符号的码字。2、列5.6：参照下表按以上步骤对一个有7个信源符号的信源进行编码。例如当时，先求第四个信源符号的二元码码长：，因此码长取3.香农编码信源符号概率累加概率码长 二元码S1S2S3S4S5S6S70.200.190.180.170.150.100.0100.200.390.570.740.890.992.342.412.482.562.743.346.663333347000001011100101111011111103、二元霍夫曼编码的方法：（1）、信源的q个消息概率从大到小排序。（2）、0，1码分别代表概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个，从而得到只包括q-1个符号的新信源。（3）、将新信源仍按概率从大到小排序，再将最后两个概率最小的信源符号分别用0和1码符号表示，合并成一个新符号，这样形成了q-2个符号的新信源。（4）、依次继续下去，直至信源最后只剩下两个信源符号为止。将这最后两个信源符号用0和1表示。（5）、从最后一级缩减信源开始，进行回溯，将每次标注的码符号连接起来就得到各信源符号所对应的码符号序列，即相应的码字。4、例5.7：以例5.6为例编制二元霍夫曼码。霍夫曼编码码字信源符号编码过程码长101100000101001100111S1s2s3s4s5s6s70.20 0.20 0.26 0.35 0.39 0.61 00.19 0.19 0.20 0.26 0.35 0 0.39 10.18 0.18 0.19 0.20 0 0.26 10.17 0.17 0.18 0 0.19 10.15 0.15 0 0.17 10.10 0 0.11 10.01 122333445、费诺编码的过程：（1）、信源的q个消息概率从大到小排序。即。（2）、将依次排列的信源符号以概率分为两组，使两组的概率和基本相等。并赋予符号0和1。（3）、再分组，使划分后的两组的概率和基本相等，并赋予符号0和1。（4）、重复，直至每组只剩下一个信源符号为止。（5）、信源符号对应的码符号序列即为费诺码。6、例5.9：信源与例5.6和例5.7相同，请编制费诺码。费诺码信源符号概率第1次分组第2次分组第3次分组第4次分组二元码码长S10.2000002S20.19100103S30.1810113S40.1710102S50.15101103S60.101011104S70.011111147、总结：霍夫曼码是即时码，他的两个特点：（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；请计算：（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，所以 即两个相对独立的事件的自信息量满足可加性，也就是由两个相对独立的事件的积事件所提供的信息量应等于他们分别提供的信息量之和。 、“a”出现的条件下，“c”出现的频率变大，它的不确定性变小。例2.5：由联合概率分布得X的边缘概率分布： 和条件概率分布（如表2.2所示），得到和。注意到。例2.15：由X,Y的联合概率分布求出X,Y的边缘概率分布如下图表所示：例3.3：（1）、熵率：；（2）、如果不考虑符号间的相关性，则信源熵为由此可见，这是由于之间存在统计依赖关系，在已知的情况下，的不确定性减少，即条件熵小于无条件熵。因此在考虑序列符号之间相关性之后，序列的熵减小。如果信源输出的符号序列看成是分组发出的，每两个符号作为一组，这样可以把符号序列看成是由