图论算法理论、实现及应用.pdf
图论算法理论、实现及应用.pdf清华大学前言、图论研究及图论教学0图论( Graph Theory)是数学的一个分支,它以图为研究对象。图论中的图是由若干个给定的顶点、及若干条连接两个顶点的边所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用顶点代表事物,用连接两个顶点的边表示相应两个事物间具有这种关系。这种图提供了一个很自然的数据结构,可以对自然科学和社会科学中许多领域的问题进行恰当的描述或建模,因此图论研究越来越得到这些领域的专家和学者的重视。图论最早的研究源于瑞士数学家莱昂哈德·欧拉( Leonhard euler,1707~1783),他在1736年成功地解决了哥尼斯堡(Kω nigsberg)七桥问题,从而开创了图论的研究。哥尼斯堡七桥问题。东普鲁士哥尼斯堡市(今俄罗斯加里宁格勒)有一条布格( Pregel)河,如图1白a)所示。布格河横贯哥尼斯堡城区,它有两条支流,在这两条支流之间夹着一块岛形地带,这里是城市的繁华地区。全城分为北、东、南、岛四个区,各区之间共有七座桥梁联系着。人们长期生活在河畔、岛上,来往于七桥之间。有人提出这样一个问题:能不能一次走遍所有的七座桥,而每座桥只准经过一次?问题提出后,很多人对此很感兴趣,纷纷进行试验,但在相当长的时间里,始终未能解决。(B)东(D)C南C)(a)(b)图1七桥问题欧拉在1736年解决了这个问题,他将这个问题抽象为一个图论问题:把每一块陆地用一个顶点来代替,将每一座桥用连接相应两个顶点的一条边来代替,从而得到一个图(如图1(b)所示)欧拉证明了这个问题没有解(详见本书5.1节),并且推广了这个问题,给出了“对于一个给定的图,能否用某种方式走遍所有的边、且没有重复”的判定法则。这项工作使欧拉成为图论及拓扑学的创始人。在此后的两百多年时间里,图论的研究从萌芽阶段,逐渐发展成为数学的一个新分支。特别是从20世纪初期开始,在生产管理、交通运输、计算机和通讯网络等方面涌现了许多离散性问题,这极大地促进了图论的发展。20世纪70年代以后,由于高性能计算机的出现,使大规模的图论问题的求解成为可能。现在,图论理论广泛应用在运筹学、计算机科学、电子学、信息论、控制论、网络理论、经济管理等领域。由于图论的重要性,越来越多的大学将图论单独作为一门课程来开设,把它作为数学、计算本文中关于图论课程教学改革的一些思想,已经发表在《计算机教育》2009年第20期上,论文题目为《计算机专业图论课程教学改革探索》,即参考文献[20获得《计算机教育》杂志社举办的“英特尔杯”20090年全国计算机教育优秀论文评比二等奖)。图论算法理论、实现及应用杋科学、电子学、管理学等专业本科生和硏究生的必修课或选修课。很多其他课程的内容也都涉及到图论知识,如离散数学、运筹学、拓扑学等。介绍图论理论的教材逐渐增多,其中也不乏优秀的教材,如文献[。这些课程和教材或者是侧重于完整的图论知识体系介绍、以及复杂的图论定理的数学证明,或者是侧重于从应用数学的角度研究图论在各领域的应用。另外,为了实现用计算杋程序求解各种应用问题,计算机科学家抽象岀许多数据结构,如栈队列、堆、树及二叉树、图等,其中图是最重要的数据结构之一,也是应用得最广的数据结构之。数据结构课程是专门硏究这些数据结枃的描述、实现及应用的课程。数据结构课程讲到图论部分时,侧重于图结构的描述、图结构的存储、少量基本的图论算法的实现等等许多学生(特别是计算机专业的学生)在学习图论时,都不满足于图论算法的手工和草稿纸演算,迫切地想知道如何用程序实现图论中的算法,以及如何将这些算法思想用来求解实际问题据作者调査统计,市面上侧重于用程序实现图论算法、并通过例题阐述图论算法思想及其应用的教材少之又少。本教材希望能弥补这一缺憾。所以本书立足于图论算法理论和思想的描述及程序实现,并以大量的 ACM/ICPC竞赛题目来阐述图论算法思想在求解这些题目中的应用。接下来简要地介绍 ACMICPC程序设计竞赛。、 ACM/ICPC程序设计竞赛1.ACMIICPCACM/ICPO( ACM International Collegiate Programming Contest,国际大学生程序设计竞赛)是由美国计算机协会ACM( Association for Computing Machinery)主办的,世界上公认的规模最大、水平最高的国际大学生程序设计竞赛,其目的旨在使大学生运用计算机来充分展示自己分析问题和解决问题的能力。该项竞赛从1977年第一次举办世界总决赛以来,至今已连续举办30多届了。该项竞赛一直受到国际各知名大学的重视,并受到全世界各著名计算机公司的高度关注。ACM/ICPC竞赛分区域预赛和总决赛两个阶段进行,各预赛区第一名自动获得参加世界总决赛的资格。世界总决赛安排在每年的3~4月举行,而区域预赛安排在上一年的9~12月在各大洲举行。ACMICPC竞赛以组队方式进行比赛,每支队伍由不超过3名队员组成,比赛时每支队伍只能使用一台计算机。在5个小时的比赛时间里,参赛队伍要解答610道指定的题目。排名时,首先根据解题数目来排名,如果多支队伍解题数量相同,则根据队伍的总用时进行排名(用时越少,排名越靠前)。每支队伍的总用时为每道解答正确的题目的用时总和。每道解答正确的题目的用时为从比赛开始计时到该题目解答被判定为正确的时间,其间每一次错误的提交运行将被加罚20分钟时间。最终未正确解答的题目不记入总时间,其提交也不加罚时间。ACMICPC竞赛在公平竞争的前提下,提供了一个让大学生充分展示用计算机解决问题的能力与才华的平台。 ACMICPC竞赛鼓励创造性和团队协作精神,鼓励在编写程序时的开拓与创新,它考验参赛选手在承受相当大的压力下所表现出来的非凡能力。竞赛所触发的大学生的竞争意识为加速培养计算机人才提供了最好的动力。竞赛中对解决问题的苛刻要求和标准使得大学生对解决问题的深度和广度展开最大程度的追求,也为计算机科学的研究和发展作了一个最好的导向。2.在线评判网站随着 ACMICPC程序设计竞赛的推广,各种程序在线评判( Online judge,简写为OJ)网站也应运而生,这为程序设计爱好者提供了一种新的程序实践方法:在线程序实践。①作者对互动出版网站(www.china-pub.com)和卓越亚马逊网站(www.amazon.cn)上列出的全部图论相关书目及目录进行了仔细的分析,从而得出的结论在线程序实践是指由OJ网站提供题目,用户在线提交程序,OJ网站的在线评判系统实时评判并反馈评判结果。这些题目一般具有较强的趣味性和挑战性,评判过程和结果也公正及时,因此能引起用户的极大兴趣。用户在解题时编写的解答程序通过网页提交给在线评判系统称为提交运行,每一次提交运行会被判为正确或者错误,判决结果会及时显示在网页上用户从评判系统收到的反馈信息包括:" Accepted程序通过评判!Compile error"—程序编译出错。" Time limit exceeded"—程序运行超过该题的时间上限还没有得到输出结果。" Memory Limit Exceeded-内存使用量超过题目里规定的上限。"outpυ ut Limit exceeded"—输出数据量过大(可能是因为陷入死循环了)。" Presentation error"—输出格式不对,可检査空格、空行等等细节。" Run Time error"—程序运行过程中出现非正常中断,如数组越界等。Wrong Answer"—用户程序的输出错误。等等。用户可以根据OJ系统反馈回来的评判结果反复修改程序,直到最终收获 Accept(程序正确)。这个过程不仅能培养用户独立分析问题、解决问题的能力,而且每成功解决一道题目都能给用户带来极大的成就感。、本书安排本书共分9章,每章内容安排如下:第1章介绍图论的一些基本概念,以及图的两种重要存储表示方法:邻接矩阵和邻接表,并初步讨论了存储方式对图论算法复杂度的影响。第2章讨论了图的遍历,遍历是很多图论算法的基础。本章介绍了两种重要的遍历方法:深度优先搜索和广度优先搜索,并对这两种遍历算法的思想、程序实现、算法复杂度作了详细的分析和讨论。本章还讨论了活动网络,包括AOV网络与拓扑排序问题、AOE网络和关键路径问题。第3章讨论树与生成树问题,主要介绍求无向连通图最小生成树的三个算法:克鲁斯卡尔( Kruskal)算法、 boruvka算法和普里姆(Prin)算法,并对这三个算法的思想、程序实现、算法复杂度作了详细的分析和讨论。另外,本章还讨论了判断生成树是否唯一的方法。第4章讨论了有向网(或无向网)中一个典型的问题:最短路径问题。本章介绍了求解最短路径问题的4个算法:Dsa算法、 Bellman-FoH算法、SPH算法和Fod算法,这4个算法分别适用于有向网(或无向网)中各边权值的取值的不同情形及问题求解的不同需要。本章着重对这4个算法的思想、递推过程、算法复杂度作了详细的讨论,并对这4个算法作了详细的对比分析。本章还介绍了求最短路径的算法思想在求解差分约束系统中的应用。第5章讨论了可行遍性问题,包括欧拉回路、汉密尔顿回路以及中国邮递员问题。前两个概念容易混淆,欧拉回路要求经过每条边一次且仅一次并回到出发点,而汉密尔顿回路要求经过每个顶点一次且仅一次并回到出发点。本章介绍这相关概念及定理,并讨论这两种回路及中国邮递员问题的求解方法和应用。第6章讨论了网络流问题。许多系统包含了流量问题,例如,公路系统中有车辆流,控制系统中有信息流,供水系统中有水流,金融系统中有现金流等等。从问题求解的需求出发,网络流问题可以分为:网络最大流,流量有上下界的网络的最大流和最小流,最小费用最大流,流量有图论算法理论、实现及应用上下界的网络的最小费用最大流等。本章介绍各种网络流问题的求解方法。第7章讨论了点支配集、点覆盖集、点独立集、边覆盖集、边独立集(匹配),这些概念之间存在一定的联系,也容易混淆。本章主要讨论了各种匹配问题,以及求解二部图最大匹配的算法程序实现和应用。第8章讨论图的连通性,这是图论中一个重要的概念。本章介绍了无向连通图和非连通图无向图的点连通性(包括割顶集、割点、顶点连通度、点双连通图等)、边连通性(包括割边集、割边、边连通度、边双连通图等)、有向图的强连通性(包括强连通、弱连通和单连通)。本章着重介绍上述概念及求解算法。第9章讨论平面图和着色问题。本章介绍了平面图和非平面图的概念、平面图的判定方法,以及图的顶点着色、边着色、平面图的面着色等概念和求解算法。四、本书读者对象及本书特点本书的读者对象为计算机专业学生或对 ACM/ICPC竞赛感兴趣的学生,可以作为高等院校计算机(或相关专业)的图论等相关课程的主教材,也可作为 ACMICPO竞赛的辅导教材。学生或读者应该具备CC艹语言知识,已经掌握了一定的程序设计思想和方法,具备一定的算法分析与设计能力,并能熟练使用数据结构。本书在内容取材、描述上具有如下特点。1)许多图论教材对图论概念的描述不一致,造成读者的阅读困难,本书试图改变这一现状。在每个概念的表述上作者査阅了大量的图论著作并进行比较分析。在本书中,作者对每个概念采用大多数图论教材采用(或约定)的名词、定义方法等。2)本书对图论算法思想的描述尽可能采用浅显易懂的语言来描述。3)本书忽略所有图论定理的证明,着重分析图论算法的思想,重点在于这些图论算法的程序实现。对图论算法的程序实现是以 ACMICPC例题来阐述的。上下两册书共收录了130余道ACMICPC竞赛题目,例题和练习题各约占一半。本书附录列出了本书所有例题和练习题在ZOJ、POJ及UVA上的题号。4)本书图表内容丰富。全书共绘制了270余幅图表,为此在目录后专门列出了本书的图录5)为方便读者阅读和使用,作者对本书中出现的图论术语、符号、图论算法及应用分别作了索引,列在本书后面五、致谢本书收录了130余道 ACMICPC竞赛题目,这些题目在阐述图论算法思想、演示图论算法应用等方面起着重要的作用,部分例题的解答程序也参考了网络上发布的一些源代码。同时,本书在编写过程中还参考了国内外多本优秀的图论教材(详见参考文献)。在此,编者对这些题目、源代码和图论教材的作者一并表示忠心的谢意。本书的编写和岀版得到了2010年浙江省教育科学规划研究课题“以大学生学科竞赛为契机推动课程群的规划与建设”(编号:SCG156)的支持,在此表示感谢。另外,本书的岀版得到了北京大学出版社的大力支持,在此表示衷心的感谢。由于作者水平有限,在编写本书时难免出错,欢迎读者指正,或者读者有什么好的建议,都可以联系编者:wguiping@163.com。不胜感激!!!编者2010年1月目录第1章图的基本概念及图的存储3.1.1树11基本概念1113.1.2森林5551.1.1有向图与无向图32生成树及最小生成树1.1.2完全图、稀疏图、稠密图321生成树1.1.3顶点与顶点、顶点与边的关系…3322最小生成树1.14顶点的度数及度序列33克鲁斯卡尔()算法1.1.5二部图与完全二部图3.3.1算法思想116图的同构332等价类与并查集1.17子图与生成树3.3.3 Kruskal算法实现118路径56778993.34Boruvka.951.19连通性3.35例题解析1.1.10权值、有向网与无向网34普里姆(Pim)算法图的存储表示341Prim算法思想106121邻接矩阵……342Prim算法实现1071.2.2邻接表15343关于普里姆算法的进一步讨论.11012.3关于邻接矩阵和邻接表的进一步344例题解析111讨论5判定最小生成树是否唯120第2章图的遍历与活动网络问题3.5.1最小生成树不唯一的原因分析.1202.1DFS遍历3.52判定最小生成树是否唯一的方法12122.1DFS算法思想4443.53例题解析212DFS算法的实现及复杂度分析……25第4章最短路径问题1272.1.3例题解析284.1边上权值非负情形的单源最短路径问题22BFS遍历Dijkstra算法12722.1BFS算法思想4.1.1算法思想12722.2BFS算法的实现及复杂度分析…414.1.2算法实现1292.2.3关于DFS算法和BFS算法的说明.434.1.3关于 Dijkstra算法的进一步讨论.1322.2.4例题解析.…434.14例题解析13323活动网络一AOV网络614.2边上权值为任意值的单源最短路径问题2.3.1AOV网络与拓扑排序61一 Bellman-Ford算法…1432.3.2拓扑排序实现方法42.1算法思想1432.3.3关于拓扑排序的进一步说明….6742.2算法实现1452.34例题解析42.3关于 Bellman-Ford算法的进一步24活动网络一AOE网络78讨论1482.4.1AOE网络与关键路径4.24例题解析2.42关键路径求解方法794.3 Bellman-Ford算法的改进一SPFA算法.161第3章树与图的生成树4.3.1算法思想….163.1树与森林…4.32算法实现图论算法理论、实现及应用4.3.3关于SPFA算法的进一步讨论…16564.1基本概念3244.34例题解析……166642最小费用最大流算法32544所有顶点之间的最短路径一Foyd算法…175644例题解析3274.4.1算法思想176第7章支配集、覆盖集、独立集与匹配3404.42算法实现…1777.1点支配集、点覆盖集、点独立集34044.3关于Foyd算法的进一步分析….1807.1.1点支配集3404.44例题解析1807.1.2点覆盖集3414.5差分约束系统7.1.3点独立集4.5.1差分约東系统与最短路径7.1.4点支配集、点覆盖集、点独立集4.52例题解析之间的联系第5章可行遍性问题2087.2点支配集、点覆盖集、点独立集的求解.34551欧拉回路2087.2.1逻辑运算34551.1基本概念及定理2087.22极小点支配集的求解34551.2欧拉回路的判定2117.2.3极小点覆盖集、极大点独立集的52欧拉回路的求解219求解52.1DFS搜索求解欧拉回路21973边覆盖集与边独立集.347522 Fleury(佛罗莱)算法.7.3.1边覆盖集….34753中国邮递员问题2337.32边独立集(匹配)54汉密尔顿回路2347.3.3最大边独立集(最大匹配)与最541基本概念及定理235小边覆盖集之间的联系5.42汉密尔顿回路求解74匹配问题350第6章网络流问题242741完美匹配3516.1网络最大流242742二部图的完备匹配与完美匹配..35161.1基本概念24274.3最佳匹配3526.1.2最大流最小割定理2477.44匹配问题求解的基本概念及思路3526.1.3网络最大流的求解2487.5二部图最大匹配问题的求解3536.1.4般增广路方法7.5.1网络流解法353Ford- Fulkerson算法2487.42匈牙利算法3556.1.5最短增广路算法2567.4.3例题解析6.16连续最短增广路算法- Dinic算法260第8章图的连通性问题.380617一般预流推进算法2628.1基本概念3806.1.8最高标号预流推进算法26581.1连通图与非连通图.3806.1.9网络最大流算法总结2668.1.2无向图的点连通性3816.1.10例题解析2668.1.3无向图的边连通性38262最小割的求解8.14无向图顶点连通性和边连通性的6.3流量有上下界的网络的最大流和最小流.300联系3846.3.1流量有上下界的容量网络8.1.5有向图的连通性6.3.2流量有上下界的网络的最大流.30382无向图点连通性的求解及应用6.3.3流量有上下界的网络的最小流.3048.21关节点的求解6.34例题解析310322重连通分量的求解64最小费用最大流323顶点连通度的求解2目录83无向图边连通性的求解及应用40192.1欧拉公式440831割边的求解401922欧拉公式的应用4418.32边双连通分量的求解4059.3平面图的判定445833边连通度的求解41294图的着色问题44684有向图强连通性的求解及应用416941地图染色与四色猜想4468.41有向图强连通分量的求解算法416942图的着色447842有向图强连通分量的应用418943图着色的应用449第9章平面图及图的着色问题4379.44图着色求解算法及例题解析…..4509.1基本概念…437索引91.1平面图与非平面图437、图论术语索引91.2区域与边界、符号索引4599.1.3极大平面图与极小非平面图.…438、图论问题及算法索引….46914平面图的对偶图439附录本书例题和练习题目录…91.5关于平面图的一些定理439参考文献92欧拉公式及其应用440
- 2020-12-08下载
- 积分：1
锁相环技术原理及FPGA实现
高清扫描版PDF，含章节书签。本书既有锁相环原理又有工程实现，值得一看。尤其是关注数字锁相环的同学，可以了解一下。内容简介本书全面阐述了典型锁相环技术的工作原理及FPGA设计方法,结合 System View仿真实例,详细分析了锁相环技术的基本概念。按照从理论到实践,再从实践到理论的思路,以 Altera公司的FPGA器件为开发平台,采用 MATLAB及 Verilog HDL语言为开发工具,详细阐述了锁相环技术的FPGA实现原理及仿真测试过程,逐步深入地讲解锁相环技术在工程应用中的技术细节。本书思路清晰、语言流畅、分析透彻,在简明阐述设计原理的基础上,追求对工程实践的指导性,力求使读者在较短的时间内掌握锁相环技术的FPGA设计知识和技能。本书的配套网络光盘收录了完整的 System View、 MATLAB及 Verilog HDL实例工程代码,有利于技术人员参考学习,读者可登录华信教育资源网(www.hxedu.com.cn)免费注册后下载。本书适合从事数字通信和数字信号处理领域的设计工程师、科研人员,以及相关专业的研究生、高年级本科生使用未经许可,不得以任何方式复制或抄袭本书之部分或全部内容版权所有,侵权必究。图书在版编目(C|P)数据锁相环技术原理及FPGA实现/杜勇编著.一北京:电子工业出版社,2016.6ISBN978-7-121-28738-1I.①锁…ⅡI.①杜…Ⅲ①锁相环一研究Ⅳ.①TN9118中国版本图书馆CIP数据核字(2016)第095248号责任编辑:田宏峰印刷:北京京师印务有限公司装订:北京京师印务有限公司出版发行:电子工业出版社北京市海淀区万寿路173信箱邮编10006开本:787×10921/16印张:18.25字数:465千字版次:2016年6月第1版印次:2016年6月第1次印刷印数:3000册定价:6800元凡所购买电子工业出版社图书有缺损问题,请向购买书店调换。若书店售缺,请与本社发行部联系,联系及邮购电话:(010)88254888,88258888质量投诉请发邮件至zs@Dphei.com.cn,盗版侵权举报请发邮件至dbq@phei.com.cn本书咨询联系方式:tianhf@phei.com.cn。前言为什么要写这本书1965年,英特尔联合创始人戈登·摩尔( Gordon moore)预测,计算机芯片的处理能力每两年就会翻一番。尽管已经过去50多年,摩尔定律仍然有效。半导体行业的发展速度,以及摩尔定律的精准性预测一度连摩尔本人都感到无比惊奇!2015年6月1日,英特尔宣布将以每股54美元的价格收购 Altera,以此计算,此交易总价将达到167亿美元,创造了英特尔并购历史上金额最大的纪录。一时间,传闻四起,业内专家和媒体开始讨论,FPGA计算机是否将成为可能?无论你是否愿意,只要从事的是与电子及信息处理相关的行业,FPGA的地位已显得越来越重要,它已成为电子行业的基本设计平台之一!无论多么高大上的技术,工程师要能够熟练应用到自己的工程项目中,都必须深入了解每一个技术实现细节。所谓“九层之台,起于垒土:合抱之木,生于毫末”。对于繁杂的技术实现方法,“各个击破”是有效学习应用的不二法门。自作者于4年前开始陆续出版数字通信技术的FPGA实现相关著作以来,通过邮件或博客的方式收到了广大读者的很多反馈意见。一些读者直接通过邮件告知书中的内容对工作中提供的直接或间接的帮助;一些读者提出了很多中肯的、有建设性的意见和建议;更多的读者通过邮件或博客交流书中的相关设计问题。归纳起来,不少读者的问题集中在数字锁相环技术的设计及实现方面。在前几本著作中,限于书中内容编排,对通信系统中最困难的锁相环技术阐述得还不够系统全面。目前市场上讲解锁相环技术的图书,主要集中在讲解锁相环的基本工作原理,或介绍一些专门的锁相环集成芯片,因此,将锁相环的工作原理与FPGA实现结合起来讨论,显得十分必要作者在写作本书的过程中,兼顾锁相环技术的理论,以及工程设计过程的完整性,重点突出FPGA设计方法、结构、实现细节,以及仿真测试方法。在讲解理论知识的时候,结合 System View、 MATLAB软件仿真实例,重点从工程应用的角度进行介绍,主要介绍工程设计时必须掌握和理解的知识点,便于读者尽快地找到理论与工程实现之间的结合点。在讲解实例的FPGA实现时,不仅对所有实例给出了完整的程序代码,并且从思路和结构上进行了详细的分析和说明。根据作者的理解,针对一些似是而非的概念,结合工程实例的仿真测试加以阐述,希望能对读者提供更多有用的参考。相信读者按照书中讲解的步骤完成一个个工程实例时,会逐步感觉到理论与工程实现之间完美结合的畅快。随着读者掌握的工程实现技能的提高,对锁相环理论知识的理解也必将越来越深刻,当重新阅读以前学过的原理时,头脑里就更容易构建起理论知识与工程实践之间的桥梁。前言Ⅲ本书的内容安排第1章首先介绍了FPGA的基本知识,以及 Altera公司的主要器件。本章在介绍了FPGA的发展历程、结构及工作原理等基本知识后,对本书所用到的设计语言及工具软件进行了简要介绍,主要包括 Verilog ldl语言、 Quartus、 MATLAB和 System View软件。所谓“工欲善其事,必先利其器”。之所以说是简要介绍,因为这些开发工具本身的功能十分强大,每一种工具都有种类繁多的专门著述进行阐述。随着工程师设计经验的积累,设计水平的提高,越能更全面地掌握设计工具的特点,从而更好地发挥设计工具的性能,以最小的代价设计出理想的产品。好比一把宝剑,只有握在高手的手中才能发挥出最大的威力。第2章介绍了FPGA数字信号处理基础知识。数字信号在FPGA等硬件系统中实现时,因受寄存器长度的限制,不可避免地会产生有效字长效应。设计工程师必须了解字长效应对数字系统可能带来的影响,并在实际设计中通过仿真来确定最终的量化位数、寄存器长度等内容。本章在详细分析了字长效应在FPGA设计中的影响后,对几种常用的运算模块P核进行介绍,讨论了各P核控制参数的设置方法。IP核在FPGA设计中的应用十分普遍,尤其是在数字滤波器等信号处理领域,采用设计工具提供的IP核进行设计,不仅可以提高设计效率,而且可以保证设计的性能第3章从锁相环的组成讲起,深入细致地探讨锁相环关注的信号特性,全面阐述VCO和乘法鉴相器的工作方式。随后借用最简单的反馈电路等基础知识,逐步揭开锁相环跟踪信号相位的神秘面纱。最后通过 System View软件工具,详细仿真分析了一阶锁相环的工作过程,全方位地了解锁相环的工作机理。第4章讨论了一阶锁相环的FPGA实现方法。根据作者的学习经验,这个阶段最期望的一定不是再去理解什么原理公式,学习什么方法思路。好比初次接触到羽毛球时,在网上看了一段中规中矩的教学视频,又刚好买回一支炫丽的球拍,走进球场,实在没有心情再听老师讲什么挥拍动作和击球技巧,只想痛痛快快地上球场打上几拍了。这一章,我们将完成一个完整的一阶锁相环电路的FPGA设计及仿真测试过程第5章又回到理论知识上来。学习的过程通常是学习(理论)一实践(工程)一学习理论)一实践(工程)的循环反复过程,每一次循环都会带来一次提高。前几章,我们主要从环路基本概念的角度,对环路进行了分析和仿真,从而初步建立起对锁相环路工作机理的认识。要深入硏究锁相环技术,必须建立环路的系统模型,而后采用数学方法对模型进行精确的分析。这一章我们从最基本的线性时不变系统知识开始,逐步建立起锁相环路的数学模型,为后续的分析打下坚实的基础。在建立模型的过程中,我们会发现,所有的知识,所有的公式其实都是在大学的一些基础课程中学习过的。第δ章深入讨论锁相环中最关键的组成电路——环路滤波器。我们从最简单的环路滤波器——RC低通滤波器开始,逐步理解环路滤波器对锁相环路性能的决定性作用,并引出本书所研究的重点——由有源积分滤波器组成的理想二阶环路。为了直观说明环路滤波器对锁相环路性能的影响,以及锁相环路参数的设计方法,我们再次采用 System View搭建了锁相环路模型,并通过翔实的仿真数据来说明一些看似深奥的理论知识。第7章开始讨论工程上应用最多的理想二阶环路的FPGA实现。前两章讲了一大堆枯燥的锁相环原理,本质是说理想二阶环具有相当优异的性能。我们在第4章已经对一阶锁Ⅳ锁相环技术原理及FPGA实现相环的FPGA实现进行了详细的讨论,有了前面章节的基础,就可以开始设计二阶环的FPGA电路了,并且要通过FPGA设计后的仿真来验证理论的正确性。二阶锁相环路相比一阶环路来讲,仅仅是多了一个环路滤波器。正是这个环路滤波器,尤其是理想环路滤波器,极大地改善了锁相环路的性能。当我们深刻理解了环路的工作原理,并动手设计出传说中的理想二阶锁相环电路时,会发现整个设计过程原来如此!第8章再次回过头来,静心硏究前面设计过程中还没有解决的一些问题。经过第7章的学习,我们己经可以完成一个完整的理想二阶锁相环路的设计。但在设计过程中,仍有一些参数的取值没有明确的依据,例如环路的固有振荡频率ωn该如何取值?环路的捕获带宽与捕获时间如何设计?当环路中存在噪声时(前面章节的设计都还没有涉及这个问题,但噪声又是电子系统中无法避免的),又该如何设计并计算环路的抗干扰性能呢?因此,在完成数字二阶环的FPGA初步设计之后,我们需要再回过头来更深入分析一下锁相环路性能,最终找到锁相环路参数的设计依据。第9章是一个完整的应用锁相环实现信号解调的工程应用实例。经过前面章节的讨论,我们对锁相环的理论知识、仿真、设计及FPGA实现都有了比较充分的认识。在无线通信技术中,在接收端,应用锁相环获取相干载波是最为广泛的应用之一。本章以锁相环解调PSK调制信号为例,应用前面章节讨论得出的结论,完整地给出锁相环的参数设计、仿真测试,以及FPGA实现过程关于FPGA开发环境的说明众所周知,目前两大商 Xilinx和 Altera的产品占据全球90%以上的FPGA市场。可以说,在一定程度上正是由于两家FPGA公司的相互竞争态势,有力地推动了FPGA技术的不断发展。虽然HDL的编译及综合环境可以采用第三方公司所开发的产品,如 Modelsim、Synplify等,但FPGA器件的物理实现必须采用各自公司开发的软件平台,无法通用。 Xilinx公司目前最新的开发工具为 Vivado Design Suite套件, Altera公司目前的主流开发平台是Quartus系列套件。与FPGA开发平台类似,HDL也存两种难以取舍的选择:VHDL和Verilog hdl。如何选择开发平台以及HDL语言呢?其实,对于有志于从事FPGA技术开发的技术人员,选择哪种平台及HDL语言并不重要,因为两种平台具有很多相似的地方,精通一种HDL语言后,再学习另一种HDL语言也不是一件困难的事。通常来讲,可以根据周围同事朋友、同学或公司的主要使用情况进行选择,这样在学习的过程中,可以很方便地找到能够给你指点迷津的专业人士,从而加快学习进度。本书采用的是Aera公司的FPGA器件作为开发平台,采用 QuartusⅡ2.1作为开发环境,采用 Verilog hDl语言作为实现手段。由于 Verilog hdl语言并不依赖于某家公司的FPGA产品,因此本书的 Verilog HDL程序文件可以很方便地移植到 Xilinx公司的FPGA产品上。如果程序中应用了P核资源,两家公司的P核通常是不能通用的,这就需要根据IP核的功能参数,在另外一个平台上重新生成IP核,或编写 Verilog HDl代码来实现。有人曾经说过,“技术只是一个工具,关键在于思想。”将这句话套用过来,对于本书来讲,具体的开发平台以及HDL语言只是实现数字通信技术的工具,关键在于设计的思路和方法。因此,读者完全不必要过于在意开发平台的差别,相信只要掌握本书所讲述的设前言计思路和方法,加上读者已经具备的FPGA开发经验,采用任何一种FPGA平台都可以很快地设计出满足用户需求的产品。如何使用本书木书在讨论锁相环的基木概念及工作原理时,主要用到了 System View5.0版本软件。关于 System View5.0软件的特点及使用方法在本书第1章进行了简要介绍。 System View软件使用起来非常简单,书中的实例也只用到了一些基本功能。如果读者以前没有使用过这款软件的话,建议先用几个小时了解一下其基本用法,这样就可以动手对本书提供的实例程序运行仿真。当然,由于 System View仅用来说明锁相环的工作原理,因此,读者也可以完全不去运行这些实例程序,只要理解书中提供的仿真结果即可。相信大部分工科院校的学生和电子通信的从业人员对 MATLAB软件都会有一个基本的了解。由于它的易用性及强大的功能,已经成为数学分析、信号仿真、数字处理必不可少的工具。由于 MATLAB具有大量专门针对数字信号处理的常用函数,如滤波器函数、傅里叶分析函数等,十分有利于对一些通信的概念及信号进行功能性仿真,因此,在具体讲解某个实例时,通常会采用 MATLAB作为仿真验证工具。虽然书中的 MATLAB程序相对比较简单,主要应用一些数字信号处理函数进行仿真验证,如果读者没有 MATLAB的知识基础,建议最好还是先简单学习一下 MATLAB的编程概念及基本语法。考虑到程序及函数的兼容性,书中所有 MATLAB程序的开发验证平台均为 MATLAB R2014a版软件。在讲解具体的FPGA工程应用实例时,通常会先采用 MATLAB对所需设计的工程进行仿真,一方面仿真算法过程及结果,另一方面生成FPGA仿真所需要的测试数据;然后在QuartusⅡ平台上编写 Verilog hDL程序对实例进行设计实现,为便于讲述,通常会先讨论程序的设计思路,或者先给出程序清单,再对程序代码进行分析说明;完成程序编写后,需要编写 Test Bench测试激励文件,根据所需产生输入信号的种类,可以直接在 TestBench文件中编写代码来产生输入信号,也可以通过读取外部文本文件的方式来产生输入信号;接下来就可以采用 Modelsim工具对 Verilog HDL程序进行仿真,查看 Modelsim仿真波形结果,并根据需要将仿真数据写入外部文本文件中,通常还会对仿真波形进行讨论,分析仿真结果是否满足要求;如果 Modelsim波形不便于精确分析测试结果,则需要再次编写MATLAB程序,对 Modelsim仿真结果数据进行分析处理,最终验证FPGA设计的正确性。本书主要以工程应用实例的方式讲解锁相环技术的原理及FPGA实现方法和步骤。书中所有实例均给出了完整的程序清单,限于篇幅,不同工程实例中的一些重复或相似的代码没有完全列出,随书配套的网络光盘上收录了本书所有实例的源程序及工程设计资源并按章节序号置于光盘根目录下。本书在编写工程实例时,程序文件均放置在“D: PllPrograms”的文件夹下,读者可以先在本地硬盘下建立“D: PllPrograms”文件夹,而后将配套网络光盘中的程序压缩包解压至该文件夹下,大部分程序均可直接运行。需要说明的是,在部分工程实例中,需要由 MATLAB产生FPGA测试所需的文本数据文件,或者由 MATLAB读取外部文件进行数据分析,同时FPGA仿真的 TestBench文件通常也需要从指定的路径下读取外部文件数据,或将仿真结果输出到指定的路径下。对于 Modelsim仿真来讲,作为测试输入的文本文件必须放置在当前FPGA工程目录下的“ simulationmodelsim”路径下。因此,读者在用 MATLAB生成测试数据后,需要将生成的文件复制到指定的路径Ⅵ|锁相环技术原理及FPGA实现下,以获取正确的仿真结果。致谢有人说,每个人都有他存在的使命,如果他的使命迷失了,也就失去了他存在的价值。不只是每个人,每件物品也都有其存在的使命。对于一本书来讲,其存在的使命就是被阅读,并给阅读者带来收获作者在写作本书的过程中查阅了大量的资料,在此对资料的作者及提供者表示衷心的感谢。由于写作本书的缘故,重新阅读一些经典的数字通信理论书籍时,再次深刻感受到前辈们严谨的治学态度和细致的写作作风。在此,感谢父母,多年来一直陪伴在我的身边,由于他们的默默支持,使得我能够在家里专心致志地写作;感谢我的妻子刘帝英女士,她不仅是一位尽心尽职的优秀母亲,也是一位严谨细致的科技工作者,同时也是本书的第一位读者,在工作之余对本书进行了详尽而细致的校对;四年前初次编写数字通信的FPGA设计与实现系列图书时,女儿才刚上小学,转眼她已经上五年级了,她最爱看书和画画,小脑袋里装着越来越多的她自己的想法。FPGA技术博大精深,本书虽尽量详细讨论了锁相环技术的原理及FPGA实现相关内容,仍感觉到难以详尽阐述所有技术细节。相信读者在实际工程应用中经过不断的实践、思考及总结,一定可以快速掌握其工程设计方法,提高应用FPGA进行工程设计的能力。由于作者水平有限,不足之处在所难免,敬请读者批评指正。欢迎大家就相关技术问题进行交流,或对本书提出改进意见及建议为便于读者交流,并及时发布相关资料及信息,本书特开设了交流博客,读者也可以通过邮件与作者进行技术交流。交流空间:http://duyongcn.blog163.com,作者邮箱:duyongcn@sina.cn。杜勇2016年4月前言目录Contents第1章设计环境及开发平台介绍1.1FPGA基础知识····+1.1.基本概念及发展历程……………·,··,,2241.1.2FPGA的结构和工作原理……1.1.3FPGA在数字信号处理中的应用“·““““““………121.2 Altera器件简介…1213 Verilog HDL语言简介………………………………………151.3.1HDL语言简介…………151.3.2 Verilog HDL语言特点161.3.3 Verilog HDL程序结构…卡““为“节“““”““牛……………………1714 QuartusⅡ开发套件…………1814. I Quartus I开发套件简介……………………………………………………1814.2 Quartus II软件的用户界面191.5 Modelsim仿真软件…221.6 MATLAB软件……………………………………………………·241.6.1 MATLAB软件介绍………2416.2 MATLAB工作界面………………………………………241.6.3 MATLAB的特点及优势……251.64 MATLAB与 Quartus的数据交互………2717 System View软件…2817.1 System View简介……281.7.2 System View工作界面……291.8小结——欲善其事先利其器…32第2章FPGA数字信号处理基础……332.1FPGA中数的表示…2.1.1莱布尼兹与二进制……………………………………………………………342.1.2定点数表示352.1.3浮点数表示…………·444,4·,,+3622FPGA中数的运算……02.2.1加/减法运算…………………………………4022.2乘法运算……4322.3除法运算22.4有效数据位的计算目录IX23有限字长效应4723.1字长效应的产生因素4723.2AD转换的字长效应4823.3系统运算中的字长效应………………………………………………4924FPGA中的常用处理模块24.1加法器模块…………………………………………………5124.2乘法器模块……2.4.3除法器模块……4.44444、562.4.4浮点运算模块572.5小结—四个过桥人………59第3章锁相环为什么能够跟踪相位613.1锁相环的组成…………623.1.1关注信号的相位分量……………………………………623.1.2VCO是一个积分器件3.1.3正弦鉴相器还是余弦鉴相器653.1.4环路滤波器的作用…………683.2从负反馈电路理解锁相环…693.2.1反馈电路的概念3.2.2负反馈电路的控制作用703.2.3锁相环与基本负反馈电路的区别…………………………………713.2.4分析锁相环的工作状态…33最简单的锁相环………………………1733.3.1一阶锁相环的 System View模型733.3.2确定VCO输出的同相支路434锁相环的基本性能参数………………………………………………773.4.1捕获及跟踪过程3.4.2环路的基本性能要求..,…………………………783.5分析一阶环的基本参数…3.5.1数学方法求解一阶环…………………………793.5.2图解法分析一阶环工作过程……813.53工程设计与理论分析的差异…3.54遗忘的参数一鉴相滤波器截止频率……………………3.6小结——千条路与磨豆腐87第4章一阶锁相环的FPGA实现4.1一阶环的数字化模型…………4.1.1工程实例需求……………………………………………………………904.1.2数字鉴相器914.1.3数控振荡器…4.1.4计算环路增益…………944.2数字鉴相滤波器设计………………………………X锁相环技术原理及FPGA实现
- 2021-05-06下载
- 积分：1
