（机械设计及理论专业论文）电路cad中印刷电路板自动布线的研究.pdf

西_ l t _ l 业大学颅+ 论文摘要 电路c a d 中印刷电路板自动布线的研究 摘要 本文首先介绍了计算机辅助设计的发展概况和电子电路c a d 软件的基本类 型和基本构成。接着阐述了自动布线技术的发展和分类，对自动布线理论进行综 合分析研究。通过比较有网格自动布线和无网格自动布线的优缺点，本文确定采 用一种高效快速的无网格线探索布线算法一朝向目标的线探索法。 该布线算法适用于焊盘外形尺寸不一，线宽及线间距离可变的印刷电路板布 线，其基本要素是带有预定终点的探索线，特点是线探索具有目标针对性，设计 合理的数据结构及灵活的绕障探索方式可大大提高搜索效率，所需存储量小，布 线速度快。 根据电路c a d 软件设计结构的要求，对自动布线的输入数据采用文本文件 的输入方式和链表的存储格式。为改善布线结果，本文对自动布线的优化方法进 行了初步的理论研究。 关键词：电路c a d ，自动布线，文本数据，朝向目标的线探索法，布线优化 两北一i 一业人学烦 ：论文 摘要 s t u d yo np r i n t e dc i r c u i tb o a r da u t o r o u t i n gi nc i r c u i tc a d a b s t r a c t t h i sp a p e ri n t r o d u c e st h eg e n e r a ld e v e l o p m e n t a ls i t u a t i o no ft h ec o m p u t e r a i d e d d e s i g n ( c a d ) a n d t h ec l a s sa n dp r i m a r ys t r u c t u r eo ft h ec i r c u i tc a ds o f t w a r e t h e d e v e l o p m e n t a ls i t u a t i o na n d c l a s so ft h ea u t or o u t i n ga r ea l s od e s c r i b e d ，t h et h e o r yo f a u t or o u t i n gi ss t u d i e ds y n t h e t i c a l l y c o m p a r e dg r i dr o u t i n ga n dg r i d l e s sr o u t i n g ，a l l e f f i c i e n ta n df a s tg r i d l e s sl i n e s e a r c hr o u t i n ga l g o r i t h m t a r g e t o r i e n t e dl i n es e a r c h r o u t i n gm e t h o df o ra u t o m a t i c c i r c u i t l a y o u t i sp r o p o s e d t h ea l g o r i t h mc a r lb ea p p l i e dt oc o n n e c t i o nr o u t i n gi np c b sw i t hv a r i o u sp a d g e o m e t r ya n dp a ds i z e s ，w i t hd i f f e r e n tw i r ew i d t h sa n dv a r i a b l ed i s t a n c e sb e t w e e n w i r e s t h eb a s i ce l e m e n ti nr o u t i n gi st h es e a m hl i n ew i t hag i v e nd e s t i n a t i o n t h e m a i nf e a t u r e so ft h er o u t e ra r et h et a r g e to r i e n t a t i o no ft h es e a r c hl i n e s ，t h er o u t i n g e f f i c i e n c yi sg u a r a n t e e db yr a t i o n a l l yd e s i g n e dd a t as t r u c t u r e sa n db yt h ea b i l i t yo f s e a r c h i n ga r o u n do b s t a c l e s ，t h es m a l la m o u n t o f w o r k i n gs t o r a g ea n dt h er e a s o n a b l y s h o r tr o u t i n gt i m e a c c o r d i n g t ot h ed e s i g ns t r u c t u r eo fc i r c u i tc a d s o f t w a r e ，d a t aa r ep u t t e di n t o t h er o u t i n gp r o g r a mb yt e x tf i l ea n da r es t o r e di nd a t ac h a i n i no r d e rt oi m p r o v et h e r o u t i n gp a t h s t h er e f i n e m e n t so f m u t i n g a r es t u d i e d p r e l i m i n a r i l y k e y w o r d ：c i r c u i tc a d ，a u t or o u t i n g ，t e x tf i l e ，t a r g e t - o r i e n t e dl i n es e a r c hr o u t i n g m u t i n g r e f i n e m e n t i i 西北t 业人学颂j ：论义第一章绪论 第一章绪论 1 1 计算机辅助设计概论 计算机辅助设计( c a d ：c o m p u t e r a i d e dd e s i g n ) 是随着计算机及其相关技 术的发展，而在全世界范围内兴起的一门崭新的技术。 1 1 1 计算机辅助设计的基本概念 计算机辅助设计是指以计算机系统作为主要技术手段来生成和运用各种数 字信息与图形信息，帮助设计人员从事产品的开发、修改、分析、和优化设计的 一门技术。计算机辅助设计系统主要由计算机、输入装置、显示装置、快速绘图 机、工程数据库以及软件等组成，如下图1 1 所示。 图1 1c a d 系统的基本构成 c a d 技术本身是一项综合性的、技术复杂的系统工程。涉及许多学科领域， 如计算机科学与工程、计算数学、计算力学、几何造型、计算机图形学、数据结 构和数据库、仿真技术、人工智能等。 目前，c a d 技术得到了迅速的发展，越来越多的人认识到c a d 技术所具有 的优点。其中包括：缩短设计周期，提高设计效率，降低成本；改善设计质量； 便于产品标准化、系列化、通用化；有利于计算机辅助工艺设计( c a p p ：c o m p u t e r a i d e dp r o c e s sp l a n n i n g ) 和辅助制造( c a m ：c o m p u t e r a i d e d m a n u f a c t u r e ) 的发 展：通过c a d c a m 的集成，可以实现产品设计和制造的一体化。 两北t 业大学硕士论文第一章绪论 1 1 2c a d 技术的发展概况及趋势 c a d 技术的发展历史大约可以追溯到上个世纪5 0 年代。上世纪5 0 年代末， 美国的c a l c o m p 公司开发出滚筒式绘图机，g e r b e r 公司则制成平板式绘图 机。这就为c a d 技术的发展提供了最基本的物质条件，同时，也成为c a d 技 术的起源。 1 9 5 9 年美国麻省理工学院( m i t ) 成立了一个c a d 课题小组，由此揭开了 c a d 研究的序幕。当时，他们提出的目标是： ( 1 ) 实现人机的交互式对话： ( 2 ) 以图形为媒介实现人机对话： ( 3 ) 实现计算机辅助模拟。 这三个目标直到1 9 6 3 年m i t 林肯实验室的i e s u t h e r l a n d 发表了著名的 s k e t c h p a d 系统后，才获得了初步的结果。在他的博士论文“s k e t c h p a d ：一 种人机通信的图形系统”中，首次提出了计算机图形学、交互技术、分层存储符 号的数据结构等新术语和新思想，为c a d 技术的发展打下了理论基础。表1 1 列出了c a d 技术发展的四个主要阶段。 中国的c a d 技术起步于上个世纪6 0 年代末期，当时只有为数不多的几个 产业部门( 如机械、航空、船舶等) 和几所高等院校开始研究c a d 技术，经过 2 0 多年的努力，特别是“七五”和“八五”的攻关，中国c a d 技术在硬件产生、 支撑软件的开发、应用软件的开发和应用、基地的建设以及人才培训方面，都取 得较大的进步。从整体情况来看，中国c a d 技术经历了三个阶段：科学计算和 数值计算，数控自动编程以及从7 0 年代开始到8 0 年代初期的蓬勃发展时期。 然而，中国的c a d c a m 系统无论在硬件环境，软件系统，还是应用系统 上与世界先进水平相比还有着很大的差距，主要体现在：c a d 硬件基础薄弱， 工作站、外围设备的生产尚未达到规模经营：c a d 软件商品化程度低，软件技 术水平低，可靠性差，包装与系统集成化不好等。然而，对于我们这样个具有 数百万个e l 企业的大国来说，c a d 技术的潜在市场是巨大的，这为c a d 技术 的发展提供了广阔的天地。 西北工业人学硕士论文第一章绪论 表1 。1c a d 的发展阶段 阶段时间c a d 技术发展水平 上世纪6 0 年s k e t c h p a d 系统。几何构形的基础研究取得进展 第一阶段 代- - 7 0 年代后 摇篮期 半期 上世纪7 0 年代t u mk e y 式系统问世，出现了面向中小企业的 第二阶段 后半期8 0 年c a d c a m 商品化系统，计算机绘图技术实用化，图形数 实用初期 代前半期据库应用 实现计算机过程的全部c a d 化，c a d c a m 技术从大中 企业向小企业扩展，从发达国家向发展中国家扩展，从用 于产品设计发展到用于工程设计。图形接口、图形功能e l 趋标准化，相继推出c o r e 图形标准、计算图形搂口c o l 第三阶段 ( c o m p u t e rg r a p h i c si n t e r f a c e ) 、计算机图形文件标准 上世纪8 0 年代 实用期 c g m ( c o m p u t e rg r a p h i c sm e t a f l l e ) 、计算机图形核心系 统g k s ( g r a p h i c sk e r n e ls y s t e m ) 、面向程序员的层次交 互式图形标准p h i g s ( p r o g r a m m e r sh i e r a c h i c a li n t e r c a t i v e g r a p h i c ss t a a d a r d ) 以及基本图形转换规范i g e s ( i n i t i a l g r a p h i c se x c h a n g es p e c i f i c a t i o n ) 第四阶段智能c a d 得至发展，c a d 技术集成化 上世纪9 0 年代 新发展期 建立在开放式，分布式工作网络上的c a d c a m 集成化系统将成为c a d 技 术发展的主要趋势。建立在网络局域网乃至广域网上的c a d c a m 集成化系统 将能管理起一个企业的整个生产周期的所有环节，它把企业计划、方案制定、产 品设计、工艺设计、生产组织、数控编程、组装模拟、运动仿真、测试试验和文 档编写以及销售管理等内容集成到一个统一的文件中，通过软件实现资源共享和 信息集成，这是未来若干年内对传统工业进行改造的重点。 由于工作站和微机系统价格低，性能价格比好，既可独立工作，又可联网运 行，对环境要求低，使用维修方便，因此以工程工作站和3 2 位微机为基础的c a d 系统将成为c a d 应用的主流。 西北r 业人学硕f 一论文第一章绪论 1 2 电子电路c a d 技术 1 2 1 电子电路的设计自动化( d a ) 和计算机辅助设计( c a d ) 电子电路设计的一般任务：电子电路的设计就是根据给定的功能和特性指标 要求( 设计要求) ，采取一定的方法来确定采用什么样的电路拓扑结构及电路中 的各个元器件应该采用什么样的参数，进一步将设计好的电路转换成印刷电路板 图设计。要完成这一设计任务，一般需要经过三个阶段：提出设计方案、验证 设计方案、修改设计方案，这一过程往往要经过几个反复才能最终得出比较满意 的结果。 电子电路的一般设计方法：根据在电子电路设计中采用的手段不同，可将电 子电路的设计方式分为三类。传统的设计方法即人工设计方法就是指方案的提 出、验证、修改都是人工完成。其中设计方案的验证一般都采用实际搭试验电路 的方式进行，这种方法花费高、效率低、越来越不能适应当前电子电路设计的需 要了。随着计算机技术的发展，目前对些特殊类型的电子电路，例如由可编程 逻辑阵列构成的数字电路，计算机可根据输入、输出之间的真值表关系直接给出 满足要求的电路形式，也就是整个设计全部由计算机完成，这就称之为设计自动 化( d a ：d e s i g n a u t o m a t i o n ) 。但是大部分情况下，电子电路的设计要以“人” 为主体，但需要借助计算机来帮助“人”迅速而准确地完成设计任务。这种设计 模式称之为计算机辅助设计。具体地说，由“人”根据设计要求进行总体设计并 提出具体的设计方案，然后利用计算机存储量大、运算速度快地特点，对设计方 案进行人工难以完成的模拟评价、设计检验和数据处理等工作，发现错误或方案 不理想时，一般还得由人进行修改。这就是说，由人和计算机通过c a d 这种工 作模式共同完成电子电路的设计任务。在这种模式下，离开人，计算机本身是不 能完成设计任务。同样，离开了计算机，单单由人来完成存在着相当大的难度， 难以很好的完成电路设计，特别是规模稍大的电路设计。 在电子电路设计中采用计算机辅助设计有很多优点，比如缩短了设计周期， 节省设计费用，提高设计质量，共享设计资源以及很强的数据处理能力。随着电 子技术的发展，需设计的电路越来越复杂，规模也越来越大，在这种情况下，离 开c a d 技术几乎无法完成现代的电子电路设计任务。 两北丁业人学顺士论文第一章绪论 1 2 2 电子电路c a d 软件的基本类型 根据各个电子电路c a d 软件的用途和电子电路设计任务的要求，通常在设 计过程中所用的c a d 软件系统主要包括以下几类软件： 通用逻辑模拟软件：用来对一般数字电路进行模拟验证。该软件可根据用户 提供的数字电路结构和所用基本逻辑单元的特性，模拟分析该电路的逻辑功能、 延迟特性以及电路中是否存在冒险竞争情况等。 通用电路模拟软件：用来对一般电子电路进行模拟验证。该软件可根据给出 的电路拓扑结构和电路中所用的元器件参数，模拟分析该电路的直流、交流和瞬 态等各种特性，并进而进行灵敏度分析、成品率模拟和最坏情况分析等特殊类型 的分析。 专用电路设计软件：专门用于某些特定类型电路的设计软件。例如由p a l ( 可编程阵列逻辑) 和f p g a ( 现场可编程门阵列) 等可编程器件构成的电路。 与通用模拟软件相比，这类软件适用面窄，但是在其适用范围内功能则更强，往 往还具有优化设计的功能。 印刷电路板( p c b ：p r i n t e dc i r c u i tb o a r d ) 布局布线软件：该类软件具有自 动布局布线功能，一般只需用户进行少量的人工干预就可完成印刷电路板的设计 任务。 电路图绘制和后处理软件：为了运行上述四类软件，需要提供电路的拓扑结 构。目前，常用方法是利用绘制电路图的计算机软件将电路图送入计算机，然后 再调用相应的后处理程序，生成能完全表征电路拓扑结构的连接网表文件，作为 上述几类软件的输入。同时后处理程序还可对绘出的电路图进行电连接规则检验 和各种统计报表生成等。 数据库建库软件：绘制电路图和运行印刷电路板布局布线软件时需调用多种 型号的器件符号，运行通用逻辑模拟和电路模拟软件时也需要使用不同型号的特 性参数值。这些器件符号和元器件参数值都是存放在专用的数据库中提供给用户 的。此外，电子电路c a d 软件还提供有数据库建库软件，以便于用户在使用软 件时根据需要扩展数据库内容，添加新的器件符号等。 西北工业人学硕士论文第一章绪论 1 2 3 微机级电子电路c a d 软件系统的基本构成 直到上个世纪8 0 年代，上述电子电路c a d 软件一般都需要在小型计算机 以上的计算机或专用的工作站上才能运行。当时的微机系统受运行速度、存储量 等因素的限制，无法运行上述软件。随着近2 0 年计算机的飞速发展，微机的许 多性能已接近有的甚至超过工作站，具有运行电子电路c a d 软件的能力。通常 来说，微机级电子电路c a d 软件系统如下图1 2 所示。系统中每一部分既可根 据需要单独使用，相互之间又有如图1 2 所示的联系，共同组成一个完整的电子 电路c a d 系统。其中电路图绘制软件是该系统的基础，后处理程序是系统中联 系各部分软件的纽带。 图1 。2 微机级电子电路c a d 软件系统构成 该软件系统中的主要软件具有下述功能和特点： ( 1 ) 电路图绘制程序采用人机交互、直接选择分层式菜单命令的方式，绘 制各种形式的电路原理图。 ( 2 ) 后处理程序具有很强的处理功能，可对绘制好的电路图按各元器件的 类型自动排序并进行节点编号：能将电路图的拓扑连接关系直接转换为电路模拟 程序、逻辑模拟程序及p c b 布线等3 0 余种不同c a d 软件需要格式的连接网表 6 西北t 业犬学坝上论文第一章绪论 文件，同时后处理程序还具有电连接关系检查、生成各种报表等多种功能。 ( 3 ) 电路模拟程序能定量分析所绘电路图的直流工作点、直流传输曲线、 交流放大特性、瞬态特性等。 ( 4 ) 逻辑模拟程序不但可以分析所绘数字电路的逻辑功能、延迟特性，并 且可反映出电路中可能存在的冒险竞争现象。模拟过程中可根据用户的要求显示 电路中任一节点处的信号波形。配备的数字电路特性数据库，用户可以根据需要 进行扩展。 ( 5 ) p c b 布线软件具有手工布局、布线和自动布局、布线的功能，供用户 选用，以便将绘好的电路原理图转化为印刷电路板布线图。对较复杂的电路，可 先用自动布线，然后用手工方式进行调整，解决自动布线过程中个别未能布通的 走线其次除了能进行单面的布线，还能进行多层版面的布线。 1 2 4 国内外电子电路c a d 软件概况 在国内，随着计算机的逐渐普及，电子设计自动化( e d a ：e l e c t r o n i cd e s i g n a u t o m a t i c ) 软件在电子行业的应用越来越广泛。但是和发达国家相比，我国的 电子设计水平仍然存在着相当大的差距。国内的电子工程师使用电路c a d 软件 进行电子自动化设计主要侧重于该软件的p c b 设计功能。目前，我国电子电路 c a d 软件市场的现状基本和机械c a d 软件一样，国外产品占据了大部分的市场 份额。 其中，p r o t e l 是澳大利亚p r o t e l 公司在上世纪8 0 年代末推出的e d a 软件， 在电子行业的c a d 软件中，它当之无愧地排在众多e d a 软件的前面，是电子 设计者的首选软件。它较早就在国内开始使用，在国内的普及率也最高，现在普 遍使用的版本是p r o t e l 9 9 。o r c a d 是由美国o r c a d 公司在同一时期推出的e d a 软件，它是世界上使用最广的e d a 软件，每天都有上百万的电子工程师在使用 它，相对于其它e d a 软件而言，它的功能是最强大的，由于o r c a d 软件使用 了软件狗防盗版，因此在国内它并不普及，知名度也比不上p r o t e l ，只有少数的 电子设计者使用它。国外这方面的软件还有p s p i c e 、e l e c t r o n i c s w o r k b e n c h e d a 、 w i n b o a r d 、w i n d r a f t 、i v e x - - s p i c e 和v i s i o ，他们都有自己本身的特色。其中， 很多人会认为v i s i o 不是个e d a 软件，它是v i s i o 公司在9 1 年推出的用于制 两北下业夫学硕l 沦文第一章绪诧 作图表的软件，在早期它主要用作商业图表制作，后来随着版本的不断提高，新 增了许多功能，现在可以用它制作的流程图包括电路流程图、工艺流程图、程序 流程图、组织结构图、商业行销图、办公室布局图、方位图等等，因此认为它也 算是半个e d a 软件。 在国产e d a 软件方面，e d a 2 0 0 0 是一个纯国产的e d a 软件，主要应用于 电子线路图、印刷电路板和电气工程图的计算机辅助自动化设计，该软件由厦门 超伦软件公司开发推出。另外，还有深圳联创公司的l i a t r oe l e c t r i c a ld e s i g n 。 总体来说，国内的电子电路软件和国外相比有很大的差距且存在模仿现象， 尤其在些关键技术上需要很大的提高。同时，随着印刷电路板市场的不断扩大 和电路板业不断向着更高层次的发展，我国电子电路c a d 软件的市场在不断扩 大的同时也需要不断的提高它的可用性，让它为更多的用户来服务。 1 3 研究内容 本论文主要研究内容是印刷电路板的自动布线。它是西北工业大学机电学 院制图教研室廖达雄老师正在开发的电路c a d 软件的一部分，同时也是该软件 的几个核心技术之一。由于专业知识的限制，所以在本论文的研究中不涉及电路 的电器特性分析如：瞬态分析、噪声分析、线性与非线性电路的直流分析和小信 号交流分析等。而主要是从图形角度进行研究。 目前，印刷电路板自动布线是自动化设计的研究热点，这部分内容涉及到 多个学科，综合性比较强，国内的研究并不多。国外在布线方面作了大量而突出 的工作，比如著名的李氏算法，它是典型的有网格布线，国内多采用的就是这种 李氏算法，应该说它是其它自动布线方法的基础。近年来，又提出了无网格线布 线，如以逃避线为基础的线探索法。本论文将在此基础上对p c b 自动布线进行 深入的分析和研究，努力探索出更符合实际要求和布通率更高的布线方法。 两北t 业人学硕卜沦史 第二章印刷电路板自动布线的理论研究 第二章印刷电路板自动布线的理论研究 2 1 印刷电路板自动布线在电路c a d 软件中的作用 在电子电路c a d 软件设计系统中，印刷电路板的设计系统结构图如下图2 1 所示。 l兰竺! 兰! 兰兰! 兰! ! 三! ： i 图2 1 印刷电路板设计系统结构图 其中，电路原理图绘制程序和印刷电路板布线程序可以分别作为两个独立的 软件，来完成各自对应的功能。而网络表则是联系电路原理图和印刷电路板布线 的纽带。印刷电路板的设计工序流程图如下图2 2 所示。对比两图就可以看出其 中的对应关系：电路图绘制程序是p c b 设计流程中的前段处理程序，主要是负 责绘制电路原理图、各元件属性与仿真参数的设置。电路原理图经过后处理程序 的处理产生网络表，也可以根据需要产生其他文本文件如：元件列表等，接下来 就是根据网络表所提供的数据信息和p c b 布线程序进行印刷电路板的设计其 中包括：电路板的规划、设置参数、装入网络表和元件封装外形、元件布局、自 动布线以及存盘打印等步骤。在整个印刷电路扳的设计过程中自动布线是核心技 术，也就是本论文的主要研究内容。 9 西北工业大学顺士论文 第二章印刷电路板自动布线的理论研究 图2 2 印刷电路板设计工序流程图 网络表所提供的信息主要包括两个方面：一方面是电路原理图中所有元器件 的属性信息，另一方面是元器件之间的电气连接关系。这些数据恰恰是p c b 布 线所需要的关键条件。由此也可以看出，网络表是电路原理图和印刷电路板之间 的一座桥梁，是实现p c b 自动布线的基础。 因此，在第三章中主要介绍有关网络表方面的内容，以便于建立实现自动布 线所需要的条件。在第四章及后面的章节中逐步深入的介绍本论文所采用的自动 布线算法及其具体实现过程。 1 0 西北t 业人学颂 一论文第二章印刷电路扳自动布线的理论研究 2 2 印刷电路板自动布线的基本概念和分类 2 2 1 印刷电路板的基本概念 印刷电路板是建构电路系统的基础技术，将设计电路中各元件问的电气连接 线作成实体铜膜连接线，在一层或数层绝缘板子上作出信号板层，并适当地蚀刻 成元件外形的焊点和铜膜走线来安装与连接各个电子元件。早期的绝缘板都是使 用电木为材料，现在则大多都改用玻璃纤维材料，厚度更薄，而弹性和韧度都更 好了。 所谓元件外形主要就是一群根据实际元件包装尺寸而定义好的焊点，另夕 还 附加一些属性和展示元件外观的符号。元件外形符号与属性符号主要是供人看 的，不具备特殊的电气或实体铜膜意义。 所谓焊点( 或焊盘) 就是提供外界用焊接方式来连接元件引脚与电路板走线 的铜膜接点。在p c b 制作流程中蚀刻出各焊点间的连接铜线就是铜膜走线。在 铺布铜膜走线时，如果有别的走线或是元件挡住了去向，就得在绝缘板上钻孔形 成所谓的导孔( v i a ，又称贯孔) ，然后通过导孔的连接使铜膜走线可以切换到 另外一个布线板层继续完成连接焊点得工作，如图2 3 所示。 元件外形符号 元件外形序号属性一，u i。焊点 元件外形批注属性d i p 4， 焊点元件外形符号 麓： 导孔 图2 3 元件外形、焊点、铜膜走线与导孔 两北1 二业人学硕士论文 第二章印刷电路板自动布线的理论研究 由于印刷电路板所使用的实体元件可分为针脚式和表面粘着式( s m d ： s u r f a c em o u n td e v i c e ) 两种，所以焊点的形式也可以区分为针脚式焊点和s m d 式焊点。 就印刷电路板本身而言，一方面印刷电路板是各种消费类电子产品和投资类 电子产品的基本零组件，也是现代电子构装技术的重要环节。目前，消费类电子 产品和投资类电子产品要求其所对应的电子机器具有“轻、薄、短、小”化、多 样化、多功能、高速、高可靠性、研制周期短和价廉等特点。这就促使所设计出 的印数电路板朝着小孔径，细线条，轻薄型的方向发展。另一方面在电子工业领 域，随着现代科学技术日新月异的发展，大规模、超大规模集成电路的使用使印 刷电路板的走线愈加精密和复杂。在这种情况下，传统的手工设计方式己越来越 难以适应当前的形势，因此用计算机来辅助设计电路板已成为电路板设计制作的 必然趋势。 自动布线是p c b 设计的最主要功能，印刷电路板自动布线就是让程序根据 用户设定的有关参数和布线规则，依照一定的程序算法，自动在各个元器件之间 进行连线，实现元件之间的电气连接关系，从而完成印刷电路板的布线工作。自 动布线算法是衡量p c b 设计软件好坏的标准，布线算法选择对印刷电路板布线 的布通率有很大的影响。 2 2 2 自动布线的分类 自动布线可分多种类型，按有无网格可分：网格布线( g r i d d e dr o u t e r s ) 和无 网格布线( g r i d l e s sr o u t e r s ) 。网格布线又可分两类：甲类是每次布一个接点直 到结束，乙类为甲类布线结束后，改变布线路径，引入未布通的接点，反复拆线、 布线、直到布通，这种反复布线( i t e r a t i v er o u t e r s ) 又称1 0 0 布通器分拉、挤布 线。无网格布线( 又称s h a p e b a s e dr o u t e r s ) ，这种布线方式用导线、焊盘等电 路板基本元素几何特征来描述线路板，而不是网格布线中用坐标来描述，当网格 太小，占用太多内存，网格布线无能为力时，而无网格布线却能用较少的内存布 更复杂的电路板，因此更适合超细间距布线。 布线按方式又可分模式布线、试线法、迷宫布线、s b 布线。 ( 1 ) 模式布线器( p a t t e mr o u t e r s ) 用- 3 中标准布线模式去布一些己知的线 1 2 两北工业犬学顺七论义 第二章印刷电路扳自动布线的理论研究 路结构，如用类似波浪形布线模式去布存储器总线结构，另外简单布线模式如l 、 c 、z 形。一般这种布线方式先运行，布线快，质量高，但布通率低。实际应用 时可以选择简单接点，提供高质量的布线。 ( 2 ) 试线法布线器( 1 i n e p r o b er o u t e r s ) 从两个结点出发的线段探索布线路 径，遇到障碍后线段将向旁边移动，力求找出布线通道，布线质量高且过孔少。 但这种方式缺少对布线总体分析，布线时容易走进死角，有时连简单的线路板也 布不通，结果使布线速度下降。但在如z 布线结合下能布出高难度、高质量的 线路。 ( 3 ) 迷宫布线器( m a z eo rw a v ee x p a n s i o nr o u t e r s ) 该算法就像水倒在一个 接点上，水就会向各个方向流开，绕开障碍物，到达另外一个接点，水的通道就 是布线路径，布线功能强大、方便，但布线速度慢，需较大内存，迷宫布线又分 网格和无网格。 ( 4 ) s b 布线器( s h a p e - b a s e dr o m e r s ) 即无网格布线。该布线方式能用更少 的层、更高的布通率，因此对于多层高密度电路板特别适用，但是一般需额外配 置。 以上是自动布线最常见的两种分类方式，当然也存在其他的分类方式。 2 3 自动布线算法的概况及分析 不论按照什么方式来划分自动布线，主要存在的两类布线算法是：有网格自 动布线和无网格自动布线。其中有网格布线算法出现的比较早，无网格布线算法 是在近二十几年内才出现的。 2 3 1 有网格自动布线 印刷电路板是焊盘、过孔、走线和铜区等物体的组合，每种物体可有任意形 状。单纯从电器特性、经济因素和制造关系考虑，好的p c b 设计应使走线区的 总面积和过i l 数目尽可能减少，从而可保证最少的面板完成设计，使产量得以提 高。 世界上最早的布线器当推1 9 6 1 年发布的l e e 算法 1 5 , 3 3 】，它实际上是图论中 最小路径算法在矩形网格上的种应用。本质上是一种遍历性质的逐点查找法， 西北t 业大学倾上论文第二章 印刷电路板自动布线的理论研究 属于“广探”。它把p c b 分为无数个等于网格大小的单元，在布线开始前，根 据线宽和间距对每个单元进行设定，形成布线的初始条件，例如，一个6 0 m i l 的 焊盘，当采用5 0 m i l 的网格时，它将占据3 x3 个相邻的单元，不能走其它线， 即板上相当于1 5 0 1 5 0 m i l 的地方，当采用2 5 m i i 的网格时，将影响3 3 个即 7 5 x 7 5 m i l 的地方，这种划分单元的办法能使板上有效布线区域比实际的区域少。 此外，p c b 的加工离不开光绘与数控钻，从理论上讲，加工设备的精度就是走 线最小的网格，也就是说，光绘精度限制了走线网格，数控钻精度限制了过孔网 格，任何强加的其他网格的限制都会影响p c b 的设计。 这种自动布线方法是从线的起点到终点搜索可用网格单元构成通路的过程， 要求起点和终点都必须在网格上。如果单元的尺寸大于或等于线宽加上线间距， 寻找通路的时间正比于单元个数；如果单元尺寸小于线宽加上线间距，则必须考 虑到i 临近单元，甚至临近单元的临近单元，这导致搜索通路的时间随网格的缩小 而急剧地增加。所以有的采用这种布线方式的软件有时要求网格设置一定要大予 或等于线宽加线问距。 如果不考虑c a m 加工精度的限制，一块p c b 可以说是无网格的。任何强 加于p c b 上的网格设置都可能导致本来能布通的变为布不通，或者即使能布通 也会走线非常不合理。而且，当要求布线很细时，想设定一个合适的网格就很难。 如果板上再使用其他不是双列直插的器件，网格的影响可能会更复杂甚至找不到 一个可用的网格设置。例如：假想电路板上的元器件的引脚间的间距有2 5 m i l 、 4 0 m i l 、5 0 r a i l 三种，那么唯一可用的网格就是l m i l ，若选用了公制器件( 如表面 粘装器件) ，则根本就找不到合适的网格。 再者，由于这种布线算法要求存储所有网点的信息，因此所需存储量相当可 观。网格的缩小导致了p c b 上网格点成平方倍的增长，因而存储量和计算时问 也以快于平方倍的速度在增长，即使硬件技术高度发展的今天，也大大超过实际 硬件的能力。 此后又出现了很多有网格布线算法，一般都是各种各样的变形网格、浮动网 格和可变网格布线器。但是不管怎样改变，也仅仅是使网格布线器能适应于无网 格的p c b ，并不是真正的无网格的解决办法，都是对李氏算法在某一方面的改 进。许多方案着眼于节省内存时间，例如k m i k a mi 的“线分法”【7 ，3 6 1 、k e l l 两北工业大学倾 论文 第二章印刷电路板自动布线的理论研觅 等的填数编码方案川37 1 、迷路法【2 1 等。图2 4 所示就是迷路法布线的原理。 图2 a 迷路法的原理图 图中黑格为配线禁区，空格为可配线区，s 、t 为待连接的两个端点。s t 两点间的连线过程是： ( 1 ) 确定起始单元为s ( t 为终止单元) ，图( a ) 所示； ( 2 ) 将s 点的相邻单元设为“l ”单元，再设“1 ”单元的相邻单元为“2 ”， 依此类推，直至某单元( 图中为“9 ”单元) 的相邻单元为配线终止单元为 止，图( b ) 、( c ) 所示； ( 3 ) 由终止单元开始进行逆探索，确定配线路径( t 一9 8 一2 一i s ) 。 图2 4 ( d ) 所示为s t 点的最终配线结果，并且为最短的配线路径。 i ! l i 北下业人学砸i 论文 第二章印刷电路板自动布线的理论研究 另外，j s o u k u p 提出的快速迷路法8 ，3 8 1 是线探索法与李氏算法的结合，即就 是先朝目标进行线探索，遇到障碍后，再由迷路法来绕过障碍。他的方法比李氏 算法快，内存也比较节省，但本质上仍是逐点查找，同样需要存贮所有网点信息。 由于强加给p c b 上一种网格，总会导致可布通性的损失，而且随着研究的不断 深入，新的改良手段也是越来越少了，尤其是表面粘装工艺的出现，更是给有网 格布线器以致命性的打击。 非李氏型算法都是启发性的，都没有李氏算法那样的普遍性，不能保证路径 最短，也不能保证两点之间有通路一定能布出。这方面国外做了大量的工作，提 出了如：h i t h c o o k 的细胞结构法【7 】，h a s h i m o t o 及s t e v e n s 的通道分配法7 ，39 1 ， m a b 及l s t a i m b e r g 的“拓扑类并法”，及h i g h t o w e r 提出的以逃避线( e s c a p el i n e ) 为基础的线探索法【7 3 4 1 等。其中h i g h t o w e r 的线探索法是一种无网格布线算法。 无网格布线算法的出现是自动布线的一种革命，它把自动布线带到了一个全新的 领域。 2 3 2 无网格自动布线 第一个无网格布线器是出现在1 9 8 4 年，无网格布线器采用了全新的形状搜 索算法。它的布线速度与网格设置有没有明显的比例关系，只取决于p c b 复杂 程度。无网格布线器只把p c b 看作是元件和走线等形状的集合，并不加上任何 网格。其数据结构真正记录了p c b 上元件的形状和坐标，所有这些形状构成了 一个布线的初始条件。因而其内存的需要只正比于元器件的数量和复杂程度，而 与网络设置无关，这样做很容易实现多种焊盘尺寸，多种间距设置和多种线宽， 所有这些要求可精确满足而不必限定在预定得网格上。另外一方面就是，无网格 布线器并不是把网格改小的有网格布线器，无网格布线器中唯一的“网格”就是 计算机的数据精度。有时根据用户需要，考虑到c a m 加工的能力，可以加上网 格，但这只是用户的需要而不是布线的前提。 无网格布线器借用了l e e 算法中搜索通路的算法，但搜索的不再是由网格构 成的固定“小单元”，而是从起点到终点的一个个无布线障碍的最大的矩形区域， 这些矩形构成的单元相互关联形成了一条走线通路。这种单元比由网格构成的 “单元”要大得多，因而尽管寻找这样一个矩形得时间比较长，但完成一个走线 1 6 两北1 ：= 业大学砸l 论立第二章印刷电路板自动布线的理论研兜 通路需要的时间比有网格布线器所用的时间少得多。同时，随着布线的进行，板 上可供搜索的矩形区域在减少，搜索的时间相应加快，因而每遍布线的时间越到 后面越加快。 上面提到的h i g h t o w e r 的线探索法就是一种典型的无网格自动布线算法，它 的基本思想是：从待连接的两个端点出发，交替地作逃避线，直到与对方地逃避 线相交。它只需存贮插孔及布出线段的端点坐标，所需存贮量大大减少，作逃避 线时，只需查找已布线段( 插孔点当作0 长度地线段处理) ，从而使运算速度大 大加快。但是h i g h t o w e r 方法存在的主要缺点是：当逃避线进入一个入口较窄的 区域时，无法出来，从而出现有通路而探索不出的情况。此外，还存在一些其它 的不足之处，如：做逃避线时，没有利用对方端点的坐标信息，探索带有盲目性， 探索范围较大，可能多花时间；从两端交替作逃避线，处理起来较困难：数据结 构还不完善，采用对折半查找，当布线到最后阶段，需查找的线段数大大增加。 根据k e l l y 等对李氏算法、线探索法及通道法的实验比较，线探索法的全面性 能最好。 2 4 朝向目标的线探索法 根据上面的分析和对有网格和无网格布线算法优缺点的比较，本文首先确定 采用无网格布线算法，在分析h i g h t o w e r 的线探索方法的基础上，本文采用朝向 目标的线探索法的布线思想。这种布线方法虽然也是一种线探索法，但是与 h i g h t o w e r 的线探索法相比，存在很大的不同之处，其中也不乏弥补了h i g h t o w e r 线探索法的不足。这种布线方法的基本思想是：第一，在探索的基本元素方面， 不是逃避线，而是带有预定目标( 或终点) 的探索线段，探索具有方向性和目标 性：第二，探索线不是由待连接的两个端点交替发出，而是以一个端点为起始点， 另一个端点为目标点，探索线由起始点发出，除若干特殊情况外，始终朝着目标 点前进；第三，除了一些特殊情况，探索基本上在以两个端点所确定的矩形框内 进行。 这种布线算法在探索的过程中，针对目标，采用合理的数据结构，可以缩小 查找线段的范围，缩短布线时间。另外，这种方法的布线能力较强，可以编出具 有迷路能力的程序，只要待连接的两个端点存在通路，无论这个通路如何复杂， 1 7 珥北工业大学硕上论文 第二章印刷电路板自动布线的理论研究 总可以将通路找到。就朝向目标而言，这个布线算法和快速迷路法的思想致。 但它只需要存储过7 l 、焊盘、已布连线等的数据，存贮量大大减少。 总的来说，这一算法结合了h i g h t o w e r 方法和快速迷路法的优点，弥补了其 中的不足，在后面的章节中会详细讨论和说明朝向目标的线探索法思想的编程实 现过程。然而，在这之前必须具备实现这一算法的必要条件，那就是如何依据网 络表数据建立实现自动布线算法所需要的条件：待连接点、焊盘、过孔和已布出 走线等障碍物的数据以及合理的存储它们。 两北丁业大学硕士论文第三章障碍物和待连接点的产生 第三章障碍物和待连接点的产生 由前面章节的内容可知，待连接点和焊盘、过孔等障碍物的产生与网络表 有密切的联系。也可以说，从网络表中就可以获得有关障碍物和待连点的数据。 那么，下面先介绍一下网络表的格式与内容。 3 1 网络表的作用与格式 电路原理图绘制完成后，除了要打印输出以便存档外，还有一步非常重要的 工作要完成，就是建立网络表文件。网络表通常是一个普通的文本文件，它可以 在原理图编辑器中直接由电路原理图文件生成，也可以在文本文件编辑器( t e x t d o c u m e n t ) 中手动编辑。它的作用就像在前面提到的那样，连接电路原理图和 印刷电路板，把从电路原理图中获得的布线数据提供给印刷电路板，是印刷电路 板自动布线的灵魂。 网络表的内容包含两部分：元件声明和网络定义，它们有各自固定的格式与 固定的组成部分。在本论文所属的电路c a d 软件中，已经设计好的网络表格式 与p r o t e l 9 9 中的网络表格式是一致的，目的是保证程序之间的兼容性。下面结合 个简单的网络表，来说明网络表的具体格式。 1 ，元件的声明格式 c 1 r a d 0 2 6 0 p f 2 网络定义格式 元件声明起始标志 元件序号( 或编号) 元件封装形式f o o t p r i n t 元件注释文字 元件声明结束标志 1 9 西北丁= 啦大学硕l 论立 第三蕈障碍物和待连接点的产生 n e t u 09 u o 9 u 1 4 网络定义单元起始标志 网络定义单元名称( 没有设置网络标号) 网络的连接点( 元件u 0 的第9 引脚) 网络的连接点( 元件u 1 的第4 引脚) 网络定义单元结束标志 (网络定义单元起始标志 a d o网络定义单元名称( 设置了网络标号) u 0 。1 0网络的连接点( 元件u 0 的第1 0 引脚) u 1 2网络的连接点( 元件u 1 的第2 引脚) u 1 8