NOIP初赛数学知识点ppt课件.ppt

NOIPNOIP初赛数学知识点初赛数学知识点初赛试题形式初赛试题形式 初赛：初赛全部为笔试，满分初赛：初赛全部为笔试，满分100分。试题由四部分组成：分。试题由四部分组成：1、选择题：共、选择题：共20题，每题题，每题1.5分，共计分，共计30分。每题有分。每题有5个备选答案，前个备选答案，前10个题为单选题个题为单选题(即每题有且只有一个正确答案，选对得分即每题有且只有一个正确答案，选对得分)，后，后10题为不定项选题为不定项选择题择题(即每题有即每题有1至至5个正确答案，只有全部选对才得分个正确答案，只有全部选对才得分)。2、问题求解题：共、问题求解题：共2题，每题题，每题5分，共计分，共计10分。试题给出一个叙述较为简分。试题给出一个叙述较为简单的问题，要求学生对问题进行分析，找到一个合适的算法，并推算出问题的解。单的问题，要求学生对问题进行分析，找到一个合适的算法，并推算出问题的解。考生给出的答案与标准答案相同，则得分：否则不得分。考生给出的答案与标准答案相同，则得分：否则不得分。3、程序阅读理解题：共、程序阅读理解题：共4题，每题题，每题8分，共计分，共计32分。题目给出一段程序分。题目给出一段程序(不不一定有关于程序功能的说明一定有关于程序功能的说明)，考生通过阅读理解该段程序给出程序的输出。输出，考生通过阅读理解该段程序给出程序的输出。输出与标准答案一致，则得分；否则不得分。与标准答案一致，则得分；否则不得分。4、程序完善题：共、程序完善题：共2题，每题题，每题14分，共计分，共计28分。题目给出一段关于程序功分。题目给出一段关于程序功能的文字说明，然后给出一段程序代码，在代码中略去了若干个语句或语句的一能的文字说明，然后给出一段程序代码，在代码中略去了若干个语句或语句的一部分并在这些位置给出空格，要求考生根据程序的功能说明和代码的上下文，填部分并在这些位置给出空格，要求考生根据程序的功能说明和代码的上下文，填出被略去的语句。填对则得分；否则不得分。出被略去的语句。填对则得分；否则不得分。信息学竞赛中的数学知识信息学竞赛中的数学知识 集合的运算 排列与组合2 2、容斥原理、容斥原理在计数时，为了使重叠部分不被重复计算，人们研在计数时，为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：究出一种新的计数方法，这种方法的基本思想是：先先不考虑重叠不考虑重叠的情况，把包含于某内容中的的情况，把包含于某内容中的所有对所有对象的数目象的数目先计算出来，然后再把计数时先计算出来，然后再把计数时重复计算的数目重复计算的数目排斥出去，排斥出去，使得计算的结果既无遗漏又无重复，这种计使得计算的结果既无遗漏又无重复，这种计数的方法称为数的方法称为容斥原理容斥原理。对有限集合对有限集合S S，用表示，用表示S S的元素个数的元素个数 容斥原理的第一形式：容斥原理的第一形式：设设A A，B B是有限集合，则是有限集合，则容斥原理的第二形式：设容斥原理的第二形式：设A A、B B、C C是有限集合，则是有限集合，则 1 1、（、（NOIP10NOIP10）7575名儿童到游乐场去玩。他们可以骑名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其中旋转木马，坐滑行铁道，乘宇宙飞船。已知其中2020人这三种东西都玩过，人这三种东西都玩过，5555人至少玩过其中的两人至少玩过其中的两种。若每样乘坐一次的费用是种。若每样乘坐一次的费用是5 5元，游乐场总共收元，游乐场总共收入入700700，可知有，可知有 10 10 名儿童没有玩过其中任何一名儿童没有玩过其中任何一种。种。2 2、某学校足球队有球衣、某学校足球队有球衣3030件，篮球队有球衣件，篮球队有球衣1515件，件，排球队有球衣排球队有球衣1818件，三队队员总数为件，三队队员总数为5050人，其中人，其中有有2 2人同时参加人同时参加3 3个队，那么同时个队，那么同时只只参加两个队的参加两个队的队员有多少？队员有多少？9 9、分母是、分母是10011001的最简分数一共有多少个？的最简分数一共有多少个？只是玩过其中两种的有55-20=35人只是玩过其中一种人所花费用700-20*（5*3）-35*（5*2）=50元只是其中一种的人数505=10人没有玩过其中任何一种的人数75-20-35-10=10人容斥原理A+B+C-（A与B重合-A与C重合-B与C重合）+A、B、C重合=总数30+15+18-（A与B重合-A与C重合-B与C重合）+2=50（A与 B重 合-A与 C重 合-B与 C重 合）=30+15+18+2-50=15人15-2*3=9人1001=71113分子中不能含有质因数7、11、13即1至1001中，不能被7、11、13整除的数有多少个？10017=143100111=91100113=7710017,11=13,7,11-7和11的最小公倍数10017,13=11,-100111,13=7,-10017,11,13=1143+91+77-(13+11+7)+1=281个不能被7，11，13整除的数有1001-281=720个排列与组合排列与组合1.1.排列的定义排列的定义:从从n n个不同元素中个不同元素中,任取任取m m个元素个元素,按照一定的顺序排成一按照一定的顺序排成一列列,叫做从叫做从n n个不同元素中取出个不同元素中取出m m个元素的一个排列个元素的一个排列.排列数公式排列数公式:全排列问题：全排列问题：n n个不同的元素排成一排，排列方法有：个不同的元素排成一排，排列方法有：=n*(n-1)*(n-2)*2*1=n!=n*(n-1)*(n-2)*2*1=n!2.2.组合的定义组合的定义:从从n n个不同元素中个不同元素中,任取任取m m个元素个元素,并成一组并成一组,叫做从叫做从n n个个不同元素中取出不同元素中取出m m个元素的一个组合个元素的一个组合.组合数公式组合数公式:排列与组合的区别与联系排列与组合的区别与联系:与顺序有关的为排列问题与顺序有关的为排列问题,与顺序与顺序无关的为组合问题无关的为组合问题.加法原理和乘法原理加法原理和乘法原理从从A到到C共有多少中走法？共有多少中走法？ABC例例1 1 :学校师生合影，共学校师生合影，共8 8个学生，个学生，4 4个老师，要个老师，要求老师在学生中间，且老师互不相邻，共有多求老师在学生中间，且老师互不相邻，共有多少种不同的合影方式？少种不同的合影方式？解解 先排学生共有先排学生共有 种排法种排法,然后把老师插入学生之然后把老师插入学生之间的空档，共有间的空档，共有7 7个空档可插个空档可插,选其中的选其中的4 4个空档个空档,共有共有 种选法种选法.根据乘法原理根据乘法原理,共有的不同坐法为共有的不同坐法为 种种.结论结论1 1 插入法插入法:对于某两个元素或者几个元素要求不对于某两个元素或者几个元素要求不相邻的问题相邻的问题,可以用插入法可以用插入法.即先排好没有限制条件的即先排好没有限制条件的元素元素,然后将有限制条件的元素按要求插入排好元素然后将有限制条件的元素按要求插入排好元素的空档之中即可的空档之中即可.例例2:2:5 5个男生个男生3 3个女生排成一排个女生排成一排,3,3个女生要排在一起个女生要排在一起,有多少种不同的排法有多少种不同的排法?解解 因为女生要排在一起因为女生要排在一起,所以可以将所以可以将3 3个女生看成是个女生看成是一个人一个人,与与5 5个男生作全排列个男生作全排列,有有 种排法种排法,其中女生内其中女生内部也有部也有 种排法种排法,根据乘法原理根据乘法原理,共有共有 种不同的排种不同的排法法.结论结论2 2 捆绑法捆绑法:要求某几个元素必须排在一起的问题要求某几个元素必须排在一起的问题,可以用捆绑法来解决问题可以用捆绑法来解决问题.即将需要相邻的元素合并即将需要相邻的元素合并为一个元素为一个元素,再与其它元素一起作排列再与其它元素一起作排列,同时要注意合同时要注意合并元素内部也可以作排列并元素内部也可以作排列.例例3 3:袋中有不同年份生产的袋中有不同年份生产的5 5分硬币分硬币2323个个,不同年份生产的不同年份生产的1 1角硬币角硬币1010个个,如果从袋中取如果从袋中取出出2 2元钱元钱,有多少种取法有多少种取法?解解 把所有的硬币全部取出来把所有的硬币全部取出来,将得到将得到 0.0523+0.1010=2.150.0523+0.1010=2.15元元,所以比所以比2 2元多元多0.150.15元元,所所以剩下以剩下0.150.15元即剩下元即剩下3 3个个5 5分或分或1 1个个5 5分与分与1 1个个1 1角角,所以所以共有共有 种取法种取法.结论结论3 3 剩余法剩余法:在组合问题中在组合问题中,有多少取法有多少取法,就有多少就有多少种剩法种剩法,他们是一一对应的他们是一一对应的,因此因此,当求取法困难时当求取法困难时,可可转化为求剩法转化为求剩法.分析分析 此题是一个组合问题此题是一个组合问题,若是直接考虑取钱的问题若是直接考虑取钱的问题的话的话,情况比较多情况比较多,也显得比较凌乱也显得比较凌乱,难以理出头绪来难以理出头绪来.但是如果根据组合数性质考虑剩余问题的话但是如果根据组合数性质考虑剩余问题的话,就会很就会很容易解决问题容易解决问题.例例4 4 学校安排考试科目学校安排考试科目9 9门门,语文要在数学之前考语文要在数学之前考,有有多少种不同的安排顺序多少种不同的安排顺序?解解 不加任何限制条件不加任何限制条件,整个排法有整个排法有 种种,“语文安排语文安排在数学之前考在数学之前考”,与与“数学安排在语文之前考数学安排在语文之前考”的排法的排法是相等的是相等的,所以语文安排在数学之前考的排法共有所以语文安排在数学之前考的排法共有 种种.结论结论4 4 对等法对等法:在有些题目中在有些题目中,它的限制条件的肯定与它的限制条件的肯定与否定是对等的否定是对等的,各占全体的二分之一各占全体的二分之一.在求解中只要求在求解中只要求出全体出全体,就可以得到所求就可以得到所求.分析分析 对于任何一个排列问题对于任何一个排列问题,就其中的两个元素来讲的就其中的两个元素来讲的话话,他们的排列顺序只有两种情况他们的排列顺序只有两种情况,并且在整个排列中并且在整个排列中,他们出现的机会是均等的他们出现的机会是均等的,因此要求其中的某一种情况因此要求其中的某一种情况,能够得到全体能够得到全体,那么问题就可以解决了那么问题就可以解决了.并且也避免了并且也避免了问题的复杂性问题的复杂性.例例5 5 某个班级共有某个班级共有4343位同学位同学,从中任抽从中任抽5 5人人,正、副班正、副班长、团支部书记至少有一人在内的抽法有多少种长、团支部书记至少有一人在内的抽法有多少种?解解 4343人中任抽人中任抽5 5人的方法有人的方法有 种种,正副班长正副班长,团支部团支部书记都不在内的抽法有书记都不在内的抽法有 种种,所以正副班长所以正副班长,团支部书团支部书记至少有记至少有1 1人在内的抽法有人在内的抽法有 种种.结论结论5 5 排异法排异法:有些问题有些问题,正面直接考虑比较复杂正面直接考虑比较复杂,而它而它的反面往往比较简捷的反面往往比较简捷,可以先求出它的反面可以先求出它的反面,再从整体中再从整体中排除排除.分析分析 此题若是直接去考虑的话此题若是直接去考虑的话,就要将问题分成好几就要将问题分成好几种情况种情况,这样解题的话这样解题的话,容易造成各种情况遗漏或者重容易造成各种情况遗漏或者重复的情况复的情况.而如果从此问题相反的方面去考虑的话而如果从此问题相反的方面去考虑的话,不不但容易理解但容易理解,而且在计算中也是非常的简便而且在计算中也是非常的简便.这样就可这样就可以简化计算过程以简化计算过程.圆周排列：圆周排列：从从n n个不同的元素中取个不同的元素中取r r个沿一圆周排列，排列的方案：个沿一圆周排列，排列的方案：/rN N个元素的圆周排列：个元素的圆周排列：/n=（n-1n-1）!有重复元素的排列问题：有重复元素的排列问题：如：如：n n1 1个个a a，n n2 2个个b b，n n3 3个个c c，排成一排，有多少种排列方法。，排成一排，有多少种排列方法。1.1.（NOIP7NOIP7）平面上有三条平行直线，每条直线上分别有）平面上有三条平行直线，每条直线上分别有7 7，5 5，6 6个点，且不同直线上三个点都不在同一条直线上。个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同四边形？问用这些点为顶点，能组成多少个不同四边形？225022502 2、（NOIP10NOIP10）由）由3 3个个a a，5 5个个b b和和2 2个个c c构成的所有字符串中，构成的所有字符串中，包含子串包含子串“abc”abc”的共有（的共有（）个。）个。A.40320 B.39600A.40320 B.39600由由3 3个个a a，5 5个个b b和和2 2个个c c构成的所有构成的所有字符串中，包含子串字符串中，包含子串“abc”abc”的共有的共有C.840 C.840 D D.780 .780 E.60E.60当abc在第一位时,后面一共有105种排列(7!/(2!*4!)=105)当abc在第二位时,也是105种.当abc在第八位时,也是105.105*8=840种里面有重复的减去有2个字字串abc的.一共60种(6!/(2!*3!)=60)所以840-60=780种1 1(NOIP8)(NOIP8)在书架上放有编号为在书架上放有编号为1 1，2 2，n n的的n n本书。本书。现将现将n n本书全部取下然后再放回去，当放回去时要求每本书全部取下然后再放回去，当放回去时要求每本书都不能放在原来的位置上。例如：本书都不能放在原来的位置上。例如：n=3n=3时：时：原来位置为：原来位置为：1 2 31 2 3 放回去时只能为：放回去时只能为：3 1 2 3 1 2 或或 2 3 1 2 3 1 这两种这两种 问题：求当问题：求当n=5n=5时满足以上条件的放法共有多少时满足以上条件的放法共有多少种？（不用列出每种放法）种？（不用列出每种放法）4444错排问题：错排问题：n n个不同元素的错排问题：个不同元素的错排问题：如：如：1 1，2 2，3 3，。，。，n n 的错排问题，的错排问题，i i不在第不在第i i个位置的排列方法。个位置的排列方法。分析：分析：设设f(n)f(n)为为n n个不同元素的错排方案。个不同元素的错排方案。第一部分：第一部分：n n先不动，把另外的先不动，把另外的n-1n-1个数错排，方案是：个数错排，方案是：f f（n-1n-1），然后），然后n n和和另外的另外的n-1n-1个每一个交换，共有个每一个交换，共有(n-1)*f(n-1)(n-1)*f(n-1)种方案。种方案。第二部分：第二部分：n n和其他的和其他的n-1n-1个之一交换，其余的个之一交换，其余的n-2n-2个错排，共有个错排，共有 （n-1n-1）*f f（n-2n-2）种方案。）种方案。由加法原理：由加法原理：f(n)=(n-1)*(f(n-1)+f(n-2)f(n)=(n-1)*(f(n-1)+f(n-2)f(1)=0;f(2)=1;f(1)=0;f(2)=1;错排的计算公式：错排的计算公式：几类重要的递推关系：几类重要的递推关系：一、第二类一、第二类Stirling数数 问题一：放置小球问题一：放置小球n个有区别的球放到个有区别的球放到m个相同的盒子中，要求无一空盒，其不同的方案数用个相同的盒子中，要求无一空盒，其不同的方案数用S(n,m)表示，称为第二类表示，称为第二类Stirling数数设有设有n个不同的球，分别用个不同的球，分别用b1,b2,bn表示。从中取出一个球表示。从中取出一个球bn，bn的放法有以下两种：的放法有以下两种：1)bn独自占一个盒子；那么剩下的球只能放在独自占一个盒子；那么剩下的球只能放在m-1个盒子中，方案数为个盒子中，方案数为 S(n-1,m-1)2)bn与别的球共占一个盒子；那么可以事先将与别的球共占一个盒子；那么可以事先将b1,b2,bn-1这这n-1个球放入个球放入m个盒个盒子中，然后再将球子中，然后再将球bn可以放入其中一个盒子中，方案数为可以放入其中一个盒子中，方案数为 m*S(n-1,m)S(n,m)=m*S(n-1,m)+S(n-1,m-1)(n1,m1)边界条件：边界条件：S(n,1)=1；S(n,n)=1；S(n,k)=0(kn)问题二：集合划分问题。问题二：集合划分问题。设设S是一个包含是一个包含n个元素的集合，个元素的集合，S=b1,b2,b3,bn,现需要将现需要将S集集合划分为合划分为m个满足如下条件的集合个满足如下条件的集合S1,S2,Sm。Si;SiSj=;S1 S2 Sm=S;(1=I,j=m)则称则称S1,S2,Sm是是S的一个划分。的一个划分。编程：输入编程：输入n和和m的值，输出不同的划分方案数。的值，输出不同的划分方案数。要求：输入数据有一行，第一个数是要求：输入数据有一行，第一个数是n,第二个数第二个数m。样例：样例：输入：输入：4 3 输出：输出：6noip131给定给定n 个有标号的球，标号依次为个有标号的球，标号依次为1，2，n。将。将这这n 个球放入个球放入r 个相同的盒子里，不允许有空盒，其个相同的盒子里，不允许有空盒，其不同放置方法的总数记为不同放置方法的总数记为S(n,r)。例如，。例如，S(4,2)=7，这，这7 种不同的放置方法依次为种不同的放置方法依次为(1),(234),(2),(134),(3),(124),(4),(123),(12),(34),(13),(24),(14),(23)。当。当n=7,r=4 时，时，S(7,4)=_350_递推公式递推公式S(n,r)=S(n-1,r)*r+S(n-1,r-1).因为把因为把n个球放入个球放入r个个箱子箱子,相当于先把相当于先把n-1个球放好再放最后一个个球放好再放最后一个.最后一个有两种最后一个有两种放法：放入前面已经有球的箱子或者独占一个箱子放法：放入前面已经有球的箱子或者独占一个箱子.前者对应前者对应S(n-1,r)*r(放入每一个不同的箱子都是一种不同的放法放入每一个不同的箱子都是一种不同的放法,因为因为箱子内原来的球不同箱子内原来的球不同),后者对应后者对应S(n-1,r-1).二、二、Catalan数数问题一：凸问题一：凸n边形的三角形剖分边形的三角形剖分在一个凸在一个凸n边形中，通过不相交于边形中，通过不相交于n边形内部的对角线，把边形内部的对角线，把n边形拆分成若边形拆分成若干三角形，不同的拆分数目用干三角形，不同的拆分数目用f(n)表之，表之，f(n)即为即为Catalan数。例如五边形数。例如五边形有如下五种拆分方案，故有如下五种拆分方案，故f(5)=5。求对于一个任意的凸。求对于一个任意的凸n边形相应的边形相应的f(n)。区域区域是一个凸是一个凸k边形，区域边形，区域是一个凸是一个凸n-k+1边形，边形，区域区域的拆分方案总数是的拆分方案总数是f(k)；区域区域的拆分方案数为的拆分方案数为f(n-k+1)；故包含故包含P1PkPn的的n 边形的拆分方案数为边形的拆分方案数为f(k)*f(n-k+1)种种 F(n)=问题二：二叉树数目问题二：二叉树数目问题描述：求问题描述：求n个结点能构成不同二叉数的数目。个结点能构成不同二叉数的数目。【问题分析问题分析】：设设F(n)为为n个结点组成二叉树的数目。个结点组成二叉树的数目。容易知道：容易知道：f(1)=1;f(2)=2,f(3)=5选定其中选定其中1个结点为根，左子树结点的个数为个结点为根，左子树结点的个数为i，二叉树数目，二叉树数目f（i）种；右子树结点数目为种；右子树结点数目为n-i-1，二叉树数目，二叉树数目f（n-i-1）种，）种，I的可取范的可取范围围0，n-1。所以有：。所以有：F(n)=为了计算的方便：约定为了计算的方便：约定f（0）=1问题三：出栈序列问题三：出栈序列问题描述：问题描述：N个不同元素按一定的顺序入栈，求不同的出栈序列数目。个不同元素按一定的顺序入栈，求不同的出栈序列数目。【问题分析问题分析】：设设f（n）为）为n个元素的不同出栈序列数目。个元素的不同出栈序列数目。容易得出：容易得出：f（1）=1；f（2）=2。第第n个元素可以第个元素可以第i（1=i=n）个出栈，前面已出栈有）个出栈，前面已出栈有i-1个元素，出栈方个元素，出栈方法：法：f（i-1）；后面出栈）；后面出栈n-i 个元素，出栈方法为：个元素，出栈方法为：f（n-i）。所以有：）。所以有：F(n)=三、集合取数问题三、集合取数问题1、设、设f(n,k)是从集合是从集合1，2，。，。，n中能够选择的中能够选择的没有没有两个连续两个连续整数的整数的k个元素子集的数目，求递归式个元素子集的数目，求递归式f(n,k)。【问题分析问题分析】：N有两种情况：有两种情况：当当n在子集时，则在子集时，则n-1一定不在子集中，即在一定不在子集中，即在1，2，。，。，。，n-2中选中选k-1个元素，数目为个元素，数目为f(n-2,k-1)。当当n不在子集中时，则在不在子集中时，则在1，2，。，。，n-1中选中选k个元素，数目为个元素，数目为f(n-1,k)。所以：所以：f(n,k)=f(n-2,k-1)+f(n-1,k)边界条件：边界条件：F(n,1)=n,f(n,k)=0 (n=k)四、整数划分问题四、整数划分问题 1、将整数、将整数n分成分成k份，且每份不能为空，任意两种分法不能相同份，且每份不能为空，任意两种分法不能相同(不考不考虑顺序虑顺序)。例如：例如：n=7，k=3，下面三种分法被认为是相同的。，下面三种分法被认为是相同的。1，1，5;1，5，1;5，1，1;问有多少种不同的分法。问有多少种不同的分法。输入：输入：n，k(6n=200，2=k=2，可以先那出，可以先那出j个个1分到每一分到每一份，然后再把剩下的份，然后再把剩下的i-j分成分成j份即可，分法有：份即可，分法有：f(i-j,j).2):j份中至少有一份为份中至少有一份为1的分法，可以先那出一个的分法，可以先那出一个1作为单独的作为单独的1份，剩下份，剩下的的i-1再分成再分成j-1份即可，分法有：份即可，分法有：f(i-1,j-1).所以所以：f(i,j)=f(i-j,j)+f(i-1,j-1)边界条件：边界条件：f（i，1）=1，f（i，j）=0，（ij）2、自然数、自然数n的拆分方案。的拆分方案。n=5,拆分数拆分数6n=6,拆分数拆分数10n=7,拆分数拆分数141:5=1+42:5=1+1+33:5=1+1+1+24:5=1+1+1+1+15:5=1+2+26:5=2+3用母函数法：用母函数法：当当n=5时：时：构造母函数如下：构造母函数如下：F(x)=(x0+x1+x2+x3+x4+x5)(x20+x21+x22)(x30+x31)(x40+x41)(x50+x51)=(1+x+x2+x3+x4+x5)(1+x2+x4)(1+x3)(1+x4)(1+x5)=1+x+2x2+3x3+5x4+7x5+项项aiXi的系数的系数ai，ai-1即自然数即自然数i的拆分数的拆分数.减减1是因为包含了是因为包含了i=i的一种拆分方案。的一种拆分方案。采用采用a,b,c三个数组，三个数组，a：被乘数，：被乘数，b：乘数，：乘数，c：乘积。：乘积。多个多项式采用逐次相乘的方法。每次借助多个多项式采用逐次相乘的方法。每次借助k从从b中取中取项。项。3、将整数、将整数n分成分成k份，且每份不能为空，且最大值不份，且每份不能为空，且最大值不超过超过m的分法的分法。任意两种分法不能相同。任意两种分法不能相同(不考虑顺序不考虑顺序)。重复元素的组合问题：重复元素的组合问题：从从n n种不同的元素中取种不同的元素中取r r个的元素的组合，允个的元素的组合，允许有重复元素的组合：许有重复元素的组合：典型模型：典型模型：r r个相同的小球，放到个相同的小球，放到n n个不同的盒子里，所有个不同的盒子里，所有的放置方法。的放置方法。r个相同的球放入个相同的球放入n个不同的盒子个不同的盒子,条件可以变成条件可以变成:n+r个球放入个球放入n个盒子个盒子,每个盒子最少放每个盒子最少放1个球个球.用插空法用插空法:n+r个球之间有个球之间有n+r-1个空个空,插插n-1个隔板进去个隔板进去,有有C(n-1,n+r-1)=C(r,n+r-1）个组合）个组合现代数字通信技术202教研室 熊华钢1/10/2023451 概述1.1 通信系统的组成和分类1.2 数字通信及主要技术1.3 数字通信的主要特点 l.4 数字通信系统的主要性能指标 1.5 数字通信的发展趋势 本课程的主要内容 参考书目 1/10/2023461.1 通信系统的组成和分类 通信的最终目的是为了有效和可靠地获取、传递和交换信息。信息可以有多种多样表现形式，如语音、文字、数据、图像等。传递或交换信息所需的一切技术设备的总和称为通信系统。1/10/202347通信系统组成1/10/2023481信源和收信者（信宿）n信源是发出信息的源，信宿是传输信息的归宿点。n信源可以是离散的数字信源，也可以是连续的模拟信源。1/10/2023492发送设备 发送设备的基本功能是将信源信源和传输传输媒介匹配媒介匹配起来，即将信源产生的消息信号变换为便于传送的信号形式，送往传输媒介。变换方式是多种多样的变换方式是多种多样的，在需要频谱搬移的场合，调制调制是最常见的变换方式。发送设备还包括为达到某些特殊要求而进行的种种处理，如多路复用、保密处多路复用、保密处理、纠错编码理、纠错编码处理等等。1/10/2023503信道 信道是指传输信号的通道，从发送设备到接收设备之间信号传递所经过的媒介，可以是无线的，也可以是有线的，有线和无线均有多种传输媒介。信道既给信号以通路通路，也要对信号产生各种干扰和噪声干扰和噪声，传输媒介的固有特性和干扰直接关系到通信的质量。1/10/2023514接收设备 接收设备的基本功能是完成发送发送设备的反变换设备的反变换，即进行解调、译码、解调、译码、解码解码等等。它的任务是从带有干扰的信号中正确恢复出原始消息来，对于多路复用信号，还包括解除多路复用，实现正确分路。1/10/202352 多数情况下，信源兼为信宿，通信的双方需要随时交流信息，因而要求双向通信。双向通信。通信双方都要有发送设备和接收设备，如果两个方向有各自的传输媒介，则双方都可独立进行发送和接收。但若共用一个传输媒介，则用频率或时间分割的办法来共享。此外通信系统除了完成信息传递之外，还必须进行信息的交换。传输系统传输系统和交换系交换系统统共同组成一个完整的通信系统，乃至通信通信网络网络。1/10/202353通信系统的分类 n按通信的业务和用途分类 常规通信-话务通信/非话务通信控制通信n按调制方式分类基带传输，调制传输n按传输信号的特征分类模拟通信系统，数字通信系统n按传送信号的复用方式分类频分复用、时分复用、码分复用n按传输媒介分类有线：明线、电缆、光缆信道无线：短波电离层传播、微波视距传播、卫星中继1/10/20235412 数字通信及其主要技术 1/10/2023551信源编码与解码 n将信源的模拟信号转变成数字信号，即模数变换；n降低数字信号的数码率，即数据压缩。1/10/2023562加密与解密 数字信号比起模拟信号来易于加密，且效果也好。加密器可以产生密码，人为地人为地将输人明文数字序列进行扰乱将输人明文数字序列进行扰乱。编码可以采用周期非常长的伪随机序列，甚至采用完全无规律的噪声码。在接收端对接收到的数字序列进行解密，恢复明文。1/10/2023573信道编码与解码 数字信号在信道传输时，由于噪声、衰落以及人为干扰等，将会引起差错。信道编码的目的就是提高通信抗干扰能力，尽可能地控制差错。n波形编码：波形编码：改善波形检测性能。双极性波形、正交波形、多元波形、双正交波形等。n差错控制编码：差错控制编码：对传输的原始信息按一定编码规则进行编码，在接收端按一定的规则进行解码，看其编码规则是否遭到破坏，从解码过程中发现错误或纠正错误。线性分组码，循环码、汉明码、格雷码、BCH码、RS码等卷积码，主要特点是有记忆特性。卷积码的著名译码算法有：序列译码、Viterbi最大似然译码。1/10/2023584调制与解调 调制是把各种数字信息脉冲转换成适于信道传输的调制信号波形。解调是对收到的信号转换成原始数字信息脉冲。数字调制技术可分为幅度键控（幅度键控（ASK）、频移键频移键控（控（FSK）、相移键控（相移键控（PSK）、连续相位调制连续相位调制（CPM），以及它们的各种组合。在接收端可以进行相干解调或非相干解调，前者需要知道载波的相位才能检测，后者则不需要。对高斯噪声下信号的检测，一般用相关接收机或匹配滤波器。各种不同的调制方式具有不同的检测性能。标志各种调制方式的性能指标为比特差错概率，它是比特能量与噪声功率谱密度之比的函数。1/10/2023595.多路与多址 为了充分利用通信资源和增加总的数据通信量，可以采用多路技术，使多用户能够固定分配通信资源，采用多址技术可以远程或动态变化地共享通信资源。基本的方法有频分、时分、码分、空分和极化波分。1/10/2023606信道与噪声 通常数字信号可以在数字信道传输，也可以经过调制变成频带信号通过模拟信道传输。信道既给传输数字信号以通路，又给传输的数字信号以限制和影响。当数字信号通过信道时，信号的功率也由于信道的损耗而下降，而且信号还会受到信道噪声的损害。信道中的噪声归纳起来可分为两种：一种是高斯噪声；另一种是脉冲噪声。数字通信系统设计的目标，一方面是设法消除或补偿信道引起的信号失真，另一方面是尽可能地抑制和减小噪声的不良影响。1/10/2023617同步与数字复接 n位（比特）同步n载波同步n帧同步n网同步n数字复接是依据时分复用原理完成数码流合并的技术1/10/2023621.3 数字通信的主要特点 1抗干扰能力强，无噪声积累，保证较高的通信质量2便于加密处理，且保密强度高3数字信号便于直接与计算机接口，形成智能网4高度的灵活性和通用性5设备便于集成化、微型化 1/10/202363但是数字通信的许多优点都是用比模拟通信占据更宽的系统频带为代价而换取的。n数字通信的频带利用率不高n同步要求高，系统设备比较复杂然而，随着社会生产力的发展，信息越来越宝贵和重要，保密要求也越来越高，因而实际中往往宁可牺牲系统频带而采用保密数字通信，至于在系统频带富裕的场合，如毫米波通信、光通信等场合，数字通信几乎成了唯一的选择。1/10/202364l4 数字通信系统的主要性能指标 n有效性：在给定信道内能传输的信息内容的多少，主要性能指标是传输速率、频带利用率。n可靠性：接收信息的准确程度，主要指标是误码率。1/10/2023651传输速率（l）码元传输速率（）简称传码率，表示单位时间（每秒）内传输的码元（符号）个数，单位为波特。（2）信息传输速率（）简称传信率，表示单位时间（每秒）内传送数据信息的比特数，单位为比特秒。二进制传输时，传输速率和信息速率一致。对N进制传输时，其传输速率和信息速率可以通过下述公式来换算：1/10/2023662 频带利用率频带利用率 （B/Hz）对二进制传输时可表示为（B/Hz）1/10/2023673可靠性指标衡量数字通信系统可靠性的主要指标是误码率误码率。在传输过程中发生误码的码元个数与传输的总码元数之比1/10/2023684.性能极限性能极限 Shannon定理指出：如果信息源的信息速率 小于或者等于一个所谓的信道容量C，那么，在理论上存在一种方法可使信息源能够以任意小的差错率通过信道传输。如果 C，则没有任何办法传输这样的信息，或者说传输二进制信息的差错率为12 信道容量C是信道的极限传输能力 1/10/202369可以证明，在被高斯白噪声干扰的信道中，传送的最大信息速率C，由Shannon公式确定：（bit/s）另一形式：1/10/202370（l）信道容量极限可见，=0 或 S=，均能使C=。=0意味着无噪声，S=意味着发送功率要达到无穷大。若要提高信道容量C，则应减小噪声或者提高发射功率。n信道容量C还与带宽B有关，带宽对信道容量有何影响呢？1/10/202371B=0，显然无法传输信息，C=0上式表明，即使信道带宽B趋于无穷大，信道容量C也是一个定值，称为信道容量极限。1/10/202372（2）频带利用率的极限）频带利用率的极限 当 =C 时，由Shannon公式得：上式为系统可能的最最高高频频带带利利用用率率,。即频带利用率极限频带利用率极限。1/10/202373（3）带宽与信噪比的互换）带宽与信噪比的互换由式 可见，当信道容量C保持不变时，带带宽宽B与与信信噪比可以进行互换噪比可以进行互换。带带宽宽较较小小的的改改变变将将会会导导致致信信号号功功率率较较大大的的改改变。变。带宽和信号功率的互换，通常可由编码和调带宽和信号功率的互换，通常可由编码和调制来实现制来实现。1/10/2023741.5 数字通信的发展趋势n短波通信n微波通信n移动通信n卫星通信n光纤通信1/10/202375l数字短波通信 未来战争中通信卫星易于被击毁，短波通信经过被冷落一段时间后又出现了“复苏”现象，重新引起各方面的重视。为了克服严重的码间干扰，采用了系列自适应技术，包括：自适应实时选频、自适应信道均衡、自适应干扰对消，以及由它们组合而成的自适应通信系统。此外尚有功率自适应、速率自适应、天线调谐自适应和自组织自适应通信网等。此外，在短波数字通信中采用扩频跳频技术，自适应接收和瞬时快速通信技术等研究都在进行中。1/10/2023762数字移动通信 近十年来，各国已研制出多种新的系统，如宽带或窄带TDMA制式，及在此基础上制定的泛欧GSM系统标准等。数字移动通信的新技术特点是：采用智能网络的原理、与ISDN相结合、部件高度集成化。这些特点使数字移动通信系统成为高技术密集的产品。移动通信的发展方向是数字化、微型化和标准化。第三代移动通信系统正是向这个方向努力，目前世界上有多种技术体制，互不兼容，标准化成为当务之急。数字化的关键是调制、纠错编码和话音编码方式的确定和实现。微型化的目标是研制重量非常轻的手机。1/10/2023773数字微波通信 大容量数字微波的发展遭遇到数字短波通信同样的技术难题，即微波在地面传播也存在多径效应和衰落现象。数字微波也需要采用一整套自适应技术来抗多径衰落引起的码间干扰。第三代数字微波设备的研制，其技术特点为：采用256QAM或1024QAM调制、自适应均衡、有效的分集接收合成技术等先进的自适应抗多径衰落技术措施，采用双重极化等频率重用技术，并开辟10GHZ以上新的频段，以及新的电路和工艺。1/10/2023784数字卫星通信 早期的时分多址卫星系统就是数字式的。从体制上看，目前已有单路单载波（SCPC）的SPADE系统、时分多路频分多址系统、时分多址数字卫星通信系统。近年来甚小口径终端（VSAT）数据卫星通信系统取得了很大的进展和广泛的应用。大量的个人计算机通过卫星通信连接成卫星数据网，其造价低廉、安装容易、使用灵活，受到广大用户的欢迎。近年来，我国已引进VSAT技术，并在许多部门建立了VSAT通信网。我国卫星通信的发展也将以数字卫星通信为主。1/10/2023795数字光纤通信 光纤通信具有频带极宽、通信容量极大、传输损耗小、保密性好、不易被窃听，以及能抗电磁干扰、且体积小、重量轻等一系列优点，已在国内外得到极大发展和应用。光纤通信的宽频带特性，为实现宽带ISDN创造了十分有利的条件。当前的主要矛盾是应大力研制和开发数字通信终端及交换设备，以便与光