网络树自动生成系统中布局布线算法的分析

《网络树自动生成系统中布局布线算法的分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、南开大学学位论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集体，均己在文中以明确方式标明。本学位论文原创性声明的法律责任由本人承担。学位论文作者签名：0为文<杀7庐6年争月≯6日第一章引言1．1研究背景及意义在复杂的电路、气路和液路系统中由于设计缺陷难免存在一些潜在的通路，这些潜通路的出现会抑制期望功能或产生非

2、期望功能。由于其特有的潜藏性质，这种系统设计中所固有的状态，在其发生前很难用常规的可靠性分析手段予以识别。但其一旦出现，往往表现出出人预料的突然性和巨大的破坏性。潜通路分析的目的就是在假定组成系统的所有元部件均正常工作的情况下，分析并找出那些能引起系统功能异常或抑制正常功能实现的潜通路。它是其它常用可靠性设计分析方法的有益补充，能为改进可靠性设计提供依据。目前潜通路分析是用来规范地和系统地识别出大型复杂电气和电子系统全部潜通路的唯一有效的分析方法。航空航天系统是潜通路分析技术开发和应用的主要领域，也是最具潜

3、力和应用价值的领域，从航空航天系统本身的复杂性以及航天事业的高投入、高风险性考虑，必须在系统可靠性设计过程中进行潜通路分析，以完善系统安全性和可靠性。以多级火箭或导弹的测试、发射、控制系统为例，由于大量采用以开关／继电器电路为特征的供配电、程序、时序系统，硬软件状态切换频繁，人工操作与自动操作并存又进一步增加了系统状态的复杂性；多部门协作、多学科综合的特点使得系统界面异常复杂，很容易出现潜在问题。这种状况与航天系统极高的安全性和可靠性要求极不适应。潜通路分析技术首次应用即取得巨大成功。1975年，波音公司在

4、执行APOLLO／ASTP潜在分析任务时，共发现潜在电路208个，设计缺陷13个，设计图错误1500个，有力的保证了APOLLO／ASTP的安全性和可靠性。但这种思想被保密了近二十年，直至80年代末才在西方各国广泛研究。如美国采用潜通路分析技术分析了F一4C飞机飞行控制系统，揭露出了4个潜通路和14个设计错误，并提出修改措施。美国国家宇航局在用潜通路分析技术分析了运载火箭控制技术后指出：20％-40％的故障与复杂系统潜通路有关。一系列惊人的成果使得美国已将潜通路分析技术作为航空航天飞行器可靠性检测的一个重要

5、环节。许多先第一章引言进的国家对潜通路技术都十分重视，已普遍应用于复杂的电子电气系统、动力输送系统、软件、化工、港口指挥调度系统、核装置控制系统等关键系统的设计和可靠性分析中。由于潜通路分析技术能够预先发现潜通路及潜在问题，从而具有有效避免巨大损失的特殊功效。另外还由于这种技术的高难度性，潜通路分析技术一直被各个国家严格保密，一度被称为“黑色艺术’’。潜通路分析一般包含如下的四个基本步骤：1)电路数据的收集和分析；2)电路的简化；3)网络树电路图的绘制；4)电路图拓扑图形的识别及应用线索表进行潜通路分析。其

6、中，网络树的绘制是一个关键环节，为后面进行拓扑图形的识别提供可能。由于潜通路分析技术所面对的系统一般都十分复杂，若靠人工分析，工作量巨大、周期长，且容易发生错误和漏判，如何最大限度的提高包括网络树绘制技术在内的潜通路分析技术的智能化和自动化，是当前的一个前沿课题。中国航天标准化研究所可靠性与安全性研究中心已经投入使用的网络树自动布图系统对含有多引脚元器件和含圈、非平面的网络树的布图，需要人工操作，不能满足准确性和效率的需要，急需开发一套能够解决含多引脚元器件、含圈、非平面的网络树自动布图系统。该系统的算法设

7、计和系统开发具有相当的难度和挑战性，目前国际上也少有十分完善和稳定的解决方案。而且由于涉及机密，现在所能查到的基本上是上世纪90年代初期及以前的文献，所以只能走自主研发的道路。在上述背景下，南开大学组合数学中心与中国航天标准化研究所合作，开展了网络树电路图自动布图系统的研发工作。通过对需求的分析和研究，我们提出了网络树电路图自动布图的初步解决方案，并在此基础上开发了网络树自动布图系统(简称NTGS)。该系统能够对含有多引脚的元器件和含圈、非平面的网络树进行布图。测试表明，该系统布局合理、走线清晰、成图迅速，

8、具有较好的实用价值。1．2电路原理图自动布图概述电路原理图作为表达电路设计思想的一种有力工具长期以来为众多设计人员广泛使用。在电路的设计过程中，设计人员通过信号线将标准的元器件图形2第一章引言符号连接成电路原理图，借以直观表达电路的功能信息。电路原理图可以说是设计人员交流思想的一种最方便和自然的媒介。然而另一方面，随着集成电路的集成度越来越高，结构日趋复杂，要求由设计人员完成从电路的网表结构来人工绘制电路原理图是