摘  要

 

随着柔性电路板(FPC)应用的广泛普及以及相关产业的高速发展，FPC电路的逻辑设计已经成为越来越重要的研究方向之一。FPC的逻辑设计中核心是布线设计，该部分需要将布局完成后电路板的元器件之间进行连接。传统的FPC布线基本由人工完成，但人工设计存在众多的缺点和不足，例如：周期长、效率低下，技术调整修改不易、难以遍历最优路径。因此，通过借助计算机技术，设计出相关的自动布线算法，可以较好地解决人工布线中存在的各种问题。自动布线算法与图论中的路径优化算法有一定联系，通过对图论中路径优化算法的研究，设计出相应的自动布线算法，并将其应用于FPC的布线问题中。该算法通过对线路中待连接触点进行位置分析，将触点密集程度高的区域首先进行布线。对于触点分布较稀疏的区域，采用贪心算法，每次将距离已布线网最近的触点加入线网，直到完成布线为止。基于该算法的系统模型，通过实际应用、理论分析表明此算法在提高布线速度、最短化布线线长上具有较好的作用。

 

关键词：FPC，自动布线算法，图论，路径优化算法，触点

目  录

 

第一章 绪论 1

1.1 引言 1

1.1.1 FPC简介 1

1.1.2 传统FPC布线中的问题以及现代自动布线简介 1

1.2 研究的主要内容和意义 2

1.3 论文的组织结构 2

第二章 自动布线技术基础 3

2.1布线基础概念 3

2.2布线技术指标 3

2.3 图论中的路径寻优算法 4

2.3.1 图论知识简介 4

2.3.2 最常见的路径寻优算法——迷宫算法 4

2.3.3  深度优先搜索在迷宫算法中的应用 5

2.4 本章小结 7

第三章 自动布线算法 8

3.1 自动布线算法的实现功能 8

3.2 自动布线算法的总体描述 8

3.3 已布线网外的触点到已布线网的最短路径构造算法 9

3.3.1线网外触点到线网中的一个触点的距离的算法 10

3.3.2线网外触点到线网中的一条导线的距离的算法 10

3.3.3 线网外触点到线网中最小距离触点的路径构造算法 10

3.3.4 线网外触点到线网中最小距离导线的路径构造算法 10

3.4 本章小结 11

第四章 软件设计与测试结果 12

4.1 自动布线算法中的数据结构 12

4.1.1 触点的数据结构 12

4.1.2 通道的数据结构 13

4.2 自动布线算法的界面设计 14

4.3 自动布线算法的实现 14

4.4算法的结果展示与分析 16

4.5 本章小结 18

第五章 总结 19

参考文献 20

致  谢 21