信息科学基础讲义三卷16-27.doc

周次：第16次时间：2007年11月6日章节：第4章 离散信道及其容量 P98103作业：4.31，4.38提纲：五、串联信道和数据处理定理1、串联信道的数学模型2、串联信道的信道容量3、数据处理定理问候课前回顾。好，咱们开始吧。诸位同学，大家上午好！咱们这次课讲本章最后一个问题串联信道和数据处理定理，在开始新的内容之前，按照惯例咱们先把上次课的内容复习一下。上次课的内容是第4章的两个问题，多符号离散信道和独立并联信道的容量。大家需要掌握的问题有这样几个。1、多符号离散信道的数学模型是什么？2、多符号无记忆信道的信道转移概率与单符号信道转移概率的关系是？3、分三种情况：信源无记忆、信道无记忆和信源/信道都无记忆，说明多符号平均互信息量与单符号平均互信息量之间的关系是什么？ 4、离散无记忆次扩展信道的容量是多少？5、独立并联信道的数学模型是什么？6、独立并联信道的容量是多少？好，这些问题都是上次课的重点内容，希望大家能够掌握。咱们开始今天的内容。上次课程我们在单符号离散信道的基础上介绍了两种更复杂的信道：多符号离散信道和独立并联信道。这次课程我们继续介绍另一种比较复杂的情况：串联信道。串联信道上次课讲的并联信道和这次课讲的串联信道其实都属于信道组合的问题。信道组合在通信工程中有很多实际的应用价值，如果待发送的消息比较多时，可能会用到两个或多个信道并行传输，这就是并联信道。你可以把计算机的外部存储设备和计算机主板之间连接的数据线（IDE数据线）看成是若干个BSC信道的并联。有时信息在远距离通信时需要中继，这种情况可以看成是信道串联。比如，传播电视信号的电视塔或者卫星和地面站形成的覆盖全球的通信网络。我们已经讨论了独立并联信道的情况。这次课我们讨论第二种信道组合串联信道。数学模型我们首先考察一下串联信道的数学模型。串联信道的数学模型可以用下面的图示描述，整个信道是由第级信道和第级信道串联起来的。信道的特征是条件概率，信道的特征是条件概率。信道信道信道等价于串联后总的信道特征仍然是一个条件概率，这个条件概率是、还是？应该是条件概率。当然条件概率称为串联信的信道转移概率。问题是串联后总的条件概率与串联的两级信道的转移概率之间有什么关系？可以看出串联后信道的转移矩阵是被串联的两级信道转移矩阵的乘积。问题是通常我们只知道第二级信道的转移概率，如果，那么我们讨论的问题就得到简化了。我们要讨论的串联信道正是这类特殊的串联信道，X、Y、Z构成马氏链。也就是信道的转移概率满足条件：，它的含义是信道的输出Z只与它的当前输入Y有关，与更以前的输入X没有关系，就是马尔可夫过程的后无效性。我们通常把时间离散的马尔可夫过程称为马尔可夫链或马氏链。这样串联信道的转移矩阵就是两个独立信道的转移矩阵的乘积：。平均互信息量的定理下面我们先研究一下串联信道中平均互信息量的一些定理，以这个为基础再来讨论串联信道的容量问题。定理1：当且仅当时等号成立。含义：一般情况下X、Y联合关于Z的信息量大于等于Y关于Z信息量，只有在X、Y、Z构成马氏链时，X、Y联合关于Z的信息量等于Y关于Z信息量，这正反映了后无效性的特点。证明：定理说明，当X、Y、Z构成马氏链时，X、Y联合关于Z的信息量等于Y关于Z信息量，这正反映了马氏链的后无效性的特点。对于串联信道三个平均互信息量、之间又有什么关系呢？定理2：如果X、Y、Z构成马氏链，则有含义：当X、Y、Z构成马氏链时，经过第级信道的信息量和经过第级信道的信息量要大于等于经过串联后整体的信息量。通过整个串联信道的信息量一般要比经过每一级信道的信息量要小，最多保持相等。证明：同理可得：（请学生给出证明过程）证明：例题如果把定理2推广到个信道串联的情况，则有下面的结论。推论：个信道串联构成马氏链，则有：信道信道信道含义：个信道串联构成马氏链时，串联的信道越多经过整个信道的信息量可能越小，最多只能和原来一样多。这就是信息不增原理。证明：略。串联信道的容量下面我们来讨论信道容量。信道容量的定义仍然是平均互信息量的最大值。因此有：因为：所以：这说明串联的信道数量越多，串联后总的信道容量可能越小。如果串联的是无干扰信道，串联后的信道容量不减小。如果串联的是有干扰信道，串联信道的数量很大时，信道容量趋于零。例1：计算两个BSC信道串联后的信道容量。0111001110III串联信道转移矩阵信道容量II,II从上面的n级BSC信道串联的平均互信息量图可以看出，当错误概率很小时，例如，计算串联后的平均互信息量减小的非常小。所以，串联级数n足够大时，串联信道的信道容量虽然减小，但仍有一定的数量。而实际数字通信网中，BSC信道的错误概率一般在以下，所以若干次串联后信道容量的减小并不明显。但是当比较大时，例如，计算串联后的平均互信息量减小的非常明显。当串联信道的数量比较大时，信道容量就会趋于零。例2：有两个信道的转移矩阵分别为 和串联信道图如右所示：计算该串联信道的转移概率。解：串联后信道X、Y、Z构成马氏链。所以数据处理定理串联后的信道转移概率。因此。定理2非常重要，它说明通过串联信道的传输只会丢失更多的信息，如果满足，即串联信道总的信道转移概率等于第级信道的转移概率时，通过串联信道传输后不会增加信息的损失。当然如果第级信道是一个无噪无损信道，这个条件显然可以满足。上面的例2也说明了这个问题。如果第级信道是数据处理系统，定理2就表示通过数据处理后，一般只会增加信息的损失，最多保持原来获得的信息，不可能比原来获得的信息有所增加，也就是说，对接收的数据Y进行处理后，无论变量Z是Y的确定对应关系还是概率关系，绝不会减少关于X的不确定性。若要使数据处理后的关于X的平均互信息保持不变，必须满足。所以定理2也称为数据处理定理。周次：第17次时间：2007年11月8日章节：第4章 离散信道及其容量 P121125作业：无提纲：无（习题课）周次：第18次时间：2007年11月13日章节：第5章 无失真信源编码 P126131作业：无提纲：一、什么是编码二、编码的分类三、编码器的数学模型四、一些基本概念好，咱们开始吧。诸位同学，大家上午好！今天咱们开始学习第5章无失真信源编码，今天讨论三个问题，编码的分类、编码器的数学模型以及编码的一些基本概念。在开始新的内容之前，咱们还是先把以前的内容稍微总结一下，看看我们现在进展到什么位置了。从第一章概述我们就提到香农狭义信息论讨论了三个大问题，大家还记得吗？哪三个？一个是信息的度量，另一个是信道容量的计算，最后是失真的问题。通过第二章信息的统计度量和第三章离散信源的学习我们已经将信息度量的问题解决了。我们知道信息的度量是利用概率统计的方法进行间接度量的。我们通过第四章离散信道及其容量的学习，能够计算出某种信道的容量了，因此衡量不同信道的通信能力就有了标准。第三个问题是失真的问题，这个问题我们放到后面来讲，在书上的是第七章。大家现在是不是很有成就感？香农信息论的三个大问题，咱们已经解决了两个。到现在给你一个信源概率分布你可以计算信源熵以及信源冗余度，给你一个信道转移矩阵你可以计算这个信道的容量。这些是我们目前取得的成绩，是吧。从这次课开始我们学习第5章无失真信源编码，这里面有一个核心词是“编码”，无失真信源是对编码的限定，也就是说我们讨论的是信源编码，而且是无失真的。当然我们很容易就联想到应该还有信道编码，而且应该有失真的情况发生，这些内容在后面章节我们会一一的学习。因此，我们首先应该对编码有一个基本的认识，（提问）什么是编码？大家在日常生活中有这样的体验吗？你们都见过哪些编码？（举例：计算机中的ASCII码，这是我们最容易想到的，ASCII码是英文字母的编码，汉字的编码是什么？与ASCII相对的汉字机内码是GB2312编码，还有吗？我们把思维发散开，我们的身份证号码是编码吗？对，每个人的学号，对于我来说就是教师号，甚至姓名。还有很多，比如每一本书后面的条形码，吃饭用的一卡通也有编码，银行账户的号码和密码。还有很多很多，举都举不完，最后再举一个例子，往大里说，甚至我们说的汉语，写的汉字就是编码，我们上小学查的汉语字典就是码表，我们小学学习的语文课，本质就是在学习码表，这样我们才能看得懂报纸书刊，才能与人交流，你们觉得是吗？）（结论：）通过刚才我们举的大量例子，大家会发现，编码是无处不在，（提问）为什么呢？因为，信息的表示离不开编码，换句话说，任何信息总是以某种表现形式来呈现的，那这种表现形式，就是广义上的编码，当然信息是无处不在的，因此，编码也是随处可见的。编码问题所涉及的内容和领域非常广。编码本质上就是信息的表达方式，表达的方式不同，我们说编码方法不同。因此对信息论的研究离不开对编码的讨论。香农在狭义信息论中证明了三个重要的编码定理：无失真信源编码定理、信道编码定理以及限失真信源编码定理。这三个编码定理是狭义信息论中的重点内容。我们知道研究通信系统的目的在于提高通信系统的三个性能指标：效率、可靠性和安全性。提高的手段是编码，提高效率用信源编码，提高可靠性用信道编码，提高安全性用加密编码。如何编码是一个非常实际的工程问题，但是编码的好坏，或者说编码的效率有没有一个极限，在狭义信息论中通过编码定理对这个问题进行了阐述。这三个编码定理的证明意义非常重大，因为，定理给出了编码效率的极限，因此人们在研究和改进编码方法的时候就有了目标和方向，尽量向编码定理给出的极限靠拢；而且也给出了编码好坏的衡量标准，一般讲越接近编码极限的编码应该越好。虽然狭义信息论中没有给出具体如何编码的方法，但是香农本人和一些科学家以及工程技术人员一直在寻找接近编码极限的编码方法，因此产生了很多实用的编码方法。非常有名的编码方法有： Huffman码，Huffman发明的，它是一种变长无失真信源编码方法；(7,4) Hamming，Hamming发明的，它是一种线性分组纠错码，同时也是循环码。等大家对这些内容了解和掌握以后，你可以去了解，比如：WinZIP或WinRAR是如何进行压缩的，BMP格式的图片是如何存储成JPG格式，甚至WAV格式的声音文件是如何压缩成MP3格式的。我们把编码的知识体系分成三大块：基本概念、编码定理和编码方法。这三个部分中我们以基本概念和编码定理为主，对于编码方法则挑选有代表性的几种介绍一下。编码的分类下面开始介绍第五章无失真信源编码。这个章节的题目一上来就编码问题限定在无失真信源这个范畴上了，当然我们有必要从整体上看一看编码到底都包括哪些内容，这样大家对编码先有一个全局的把握，然后再分块单独介绍。分类目的手段编码信源编码无失真定长效率压缩（减小冗余）变长有失真（限失真）信道编码（也称为纠错编码）可靠性增加冗余安全编码安全性增加冗余信源编码为什么可以提高效率呢？信源信息原始编码中包含大量结构化特征，这些结构特征使得大量信息不必再进行传输，可以减小实际编码的信息量，从而实现了信息的压缩。通信系统在单位时间传输能力固定的情况下，信息量越小，传输效率就越高。互联网的网站网页中嵌入的图片大多是JPG格式的，而不是BMP格式的；互联网上的音乐大多是MP3格式的，因为这些格式在编码时进行了压缩，所以传输效率高。对离散信源的信息可以做到无失真编码，也就是说码字和信源符号是一一对应的。对于连续信源无法做到无失真编码，因为连续信源的信源符号数无穷大，连续信源的实际信息量也是无穷大，无法实现码字和信源符号一一对应。因此对于连续信源的信息编码时肯定会有失真，问题是失真的程度我们能够接受就行。定长编码和变长编码我们在后面介绍。信道编码的目的是为了提高信息传输的可靠性，信息在信道中传输可能由于干扰的作用导致某些信息位的改变，信宿收到的信息不是原来的信息。通过信道编码可以在待传输信息中增加一些校验位，信宿通过校验算法可以发现信息是否出错，甚至有能力更改差错。举一个简单例子：待传输的信息是1，传输时把它重复三遍111，如果收到110、101、011则认为发送的是1，传输中发生了干扰。在分类中我们仅介绍无失真信源编码，包括变长码和定长码两种情况，以及信道编码的内容。有失真信源编码和安全编码大家感兴趣可以课下自己学习。编码器的数学模型编码是通过编码器（Encoder）这个物理部件实现的，我们对编码器建立一个数学模型可以帮助我们理解编码的数学本质。编码器编码器的输入是信源符号集，共有个信源符号。同时存在另一符号集，称为码符号集，共有个码符号。码符号集中的元素称为码元或者码符号。编码器的作用就是将信源符号集中的符号（或者长为的信源符号序列）变换成由基本符号组成的长为的输出符号序列。输出符号序列又称为码字，并用表示，它与信源符号是一一对应关系。码字的集合称为代码组或码（Code）。即而码字（Word）其中，长度称为码字长度，简称码长。编码就是信源符号集到码字集的映射，译码就是码字集到信源符号集的映射，是编码的逆过程，。因此，若要实现无失真编码，这种映射必须是一一对应的（一一对应就可逆）。1. 二元码若码符号集为，所有码字都是二元符号序列，则称为二元码。若将信源通过一个二元信道进行传输，为使信源适合信道传输，就必须把信源符号变换成o。l符号组成的码符号序列(二元序列)，这种编码所得的码为二元码G二元码是数字通信和计算机系统中员常用的一种码。2. 等长码（或定长码固定长度码）若组码中所有码字的码长都相同，即J(*l3. 变长码（可变长度码）若组码卞所有码字的码长各不相同为变长码。4. 非奇异码若织码中所有码宇都不相同，即所有 PE Jz毒Wi乒W则称6z5(”为非奇异码。5. 奇异码 若组码巾有相同的码字即 1PE j，事W则称码(”为奇异码。6. 同价码信源符号映射到不同的码符号序列A，E 6Wr，Wf E t” 苫的符号集x：人，人、，?i中每个码符号2，所占的传输时间都相同，则所得的码t”为同价码。 般一元码是同价码。本章讨论的都是同价妈。对同价码来说，等长码中每个码宁的传榆时司都相同*而变长码中每个码字的传输时间就石一定相同。刚R小常用的英尔斯仍是非问价码、其肥符早点()和划(一)所占的传输时问不相网7. 码的次扩展码 假定策码t”、它把信源3中的符号*一一变换成码c中的码字W，则码c的川次扩展码好，咱们开始吧。诸位同学，大家上午好！咱们开始上课，在开始新的内容之前，按照惯例咱们先把上次课的内容复习一下。上次课的内容是第4章离散信道及其容量的最后一个问题，是什么？（串联信道和数据处理定理）大家需要掌握的问题有这样几个。1、串联信道的数学模型是什么？2、具有马氏链特征的串联信道的数学模型是什么？3、数据处理定理的内容是什么？要求能够证明。4、个信道串联时平均互信息量的规律。5、如何计算两个BSC信道串联的容量？好，这些问题都是上次课的重点内容，希望大家能够掌握。咱们开始今天的内容。前面课程我们介绍了狭义信息论中两大基本问题：信息如何度量以及信道容量的计算问题。狭义信息论的第三个大问题率失真函数对应于本书的第七章限失真信源编码。周次：第19次时间：2007年11月15日章节：第5章 无失真信源编码 P131140作业：5.1，5.8提纲：五、定长码1、AEP和典型序列集2、定长信源编码定理3、讨论周次：第20次时间：2007年11月20日章节：第5章 无失真信源编码 P140153作业：无提纲：六、变长码1、Kraft不等式和McMillan不等式2、唯一可译码的判别准则3、编码定理4、讨论周次：第21次时间：2007年11月27日章节：第5章 无失真信源编码 P134142作业： 5.7、5.9、5.10、5.17、5.19提纲：七、变长码的编码方法1、Shannon码2、Fano码3、Huffman码4、比较周次：第22次时间：2007年11月29日章节：第5章 无失真信源编码 P162165作业：无提纲：无（习题课）周次：第23次时间：2007年12月4日章节：第6章 有噪信道编码 P166185作业：6.1，6.3，6.5，6.7提纲：一、噪声信道的编码问题1. 编码信道2. 错误概率与信道统计特征3. 错误概率与译码规则(1) 与信道统计特征的关系(2) 译码规则定义(3) 错误概率(4) 译码规则的选取(5) Fano不等式周次：第24次时间：2007年12月6日章节：第6章 有噪信道编码 P157162作业：6.6，6.8，6.9，6.10提纲：一、噪声信道的编码问题4. 错误概率与编码方法(1) 简单重复编码(2) (5,2)线性码(3) 汉明距离和最小汉明距离二、有噪信道编码定理周次：第25次时间：2007年12月18日章节：第9章 纠错编码 P239247作业：9.1，9.2，9.3，9.4提纲：一、纠错码的基本概念二、纠错码的分类三、线性分组码1. 数学结构好，咱们开始吧。诸位同学，大家上午好！咱们开始上课，在开始新的内容之前，按照惯例咱们先把上次课的内容复习一下。上次课的内容是第6章有噪信道编码，讲了两个问题，是什么？（有噪信道编码定理和错误概率的上界）问候课前回顾。大家需要掌握的问题有这样几个。1、有噪信道编码定理和逆定理的内容是什么？2、什么是随机编码？3、有噪信道编码定理的重要意义是什么？4、错误概率的上界是什么？好，这些问题都是上次课的重点内容，希望大家能够掌握。咱们开始今天的内容。上次课我们介绍了信道编码理论中非常重要的香农第二定理，就是有噪信道编码定理。她为编码方法的研究提供了指导方向。这次课我们介绍第九章纠错编码，纠错编码是在通信系统中提高信息传输可靠性的一种编码技术，纠错编码也称为信道编码。本章主要介绍纠错编码的一些基本概念和基本方法。在通信过程中发生差错是不可避免的。对于接收到的数据序列，判断它有无差错并纠正差错是一个非常重要的问题。人们发现，在发送端根据传输信息的性质，通过编码器以一定的规则对所要传输的数据序列附加一定的数字，通常称这些附加的数字为校验(或监督)序列，使原来不相关的数据序列变为具有相关特性的新序列，然后进行传输。在接收端，由于信道中干扰的影响，新序列在传输过程中存在一定的差错。译码器根据已知的编码规则和数字序列内部的相关性发现差错，甚至纠正差错，恢复原发送的信息序列，这就是纠错编码的基本思想。香农有噪信道编码定理指出，可以用任意接近信道容量的信息传输率传输信息，且错误概率可以任意小。不过，定理的证明是建立在“随机编码”概念的基础上的，是非结构性的。首先，这种码很长，而且“随机”选的码很可能就是符合定理要求的所谓“好码”。但根据“随机”的含义就意味着没有什么规律可循，因此很难找到这类码。其次，在给定一个码后，我们如何判断该码有多好呢？这就要计算给定码的错误概率。但正是因为它是随机选取的，因此要计算这个概率是不可能的。也就是说我们难以对这种码进行分析。再者，在考虑终端设备的实现时，随机编码的方案就更不吸引人了，人们很难对这类码进行编码，特别是译码。因为“随机”就意味着无法按照计算公式进行编码和译码，所以寻找码字的工作量将非常艰巨。鉴于以上原因，我们必须寻找一些结构严密的码。这里的结构，是指码字各个信息位之间的数学结构，特别是信息位与校验位之间的数学运算关系。数学结构是纠错码的重要内容，直接影响到码字的构造方法，数学结构不同，可能形成不同的编码方法。因此，研究各种编码方法的数学结构是研究纠错码的一个非常核心和重要的内容。研究码的构造规律必须研究码的数学特性，即研究码的数学结构。例如利用生成短阵或一致监督矩阵来反映线性码和卷积码的数学结构，利用转移矩阵或递推关系反映最长线性移位寄存器序列的数学结构，利用某种多项式的形式按照求余式而得到的集来反映循环码的数学规律等。前面有关章节中所论述的香农噪声编码定理仅仅是存在性定理，并未提出使差错概率为任意小的解决方法，而我们所讨论的纠错编码就是用来纠正噪声信道中的差错。但是到目前为止，没有一种码能达到香农定理的极限。一般情况下，通信系统允许出错概率有一定的要求，并要求经济合理的实现。在给定的信息传输情况下，对编码的一般要求是：码长尽量短，信息率尽量高，纠检能力尽量强，编码规律尽量简单，实现设备简单易实现且费用合理，与信道的差错统计特性尽量匹配等。下面我们介绍纠错码的一些基本概念。1. 分组码假设信源信息是二进制数字序列，将信源编码器的输出序列构成长度为的段，记为设有，个不同的信息序列，每个不同的序列由位相继的信息数字组成。由于每个信息序列组成位二进制数字，则有个不同的信息序列，即，这个码字的集合称为分组码。2. 二元分组码对于二元符号表上的分组码，由表示消息序列的长度为的个二元序列构成的集合，称为二元分组码。3. 校验位或监督位对于个长码字全体构成的分组码，其码字中的位称为信息位，位称为校验位或监督位。例如，当时，可能的消息序列数个，可能的长为的预选序列有个。下面给出一种码：19消息序 000001010011100101110111码 字00000000011101010011101110101001110101001111010011110100对于所选定的长序列称为允许使用序列用序列，即码宇；而其他序列则是不允许使用的，即禁用序列。对于上例中，信息位为3，码长为7，监督位为4。如果用表示码字中信息位所占的比重，称为编码效率，它表明了信道的利用效率。越大，码