3 布图规划表示方法及其相关算法 13

3.1 二分结构与非二分结构 13

3.2 模拟退火算法 15

3.3 线性规划算法 20

3.4 B*-tree 表示法 21

4 基于模拟退火算法与 B*-tree 的布图规划仿真 24

4.1 改进的模拟退火算法 24

4.2 实验仿真与分析 27

5 小结 30

附录 31

参考文献 40

致谢 41

图清单

图序号 图名称 页码

图 2-1 VLSI 制造流程 6

图 2-2 布图设计过程 7

图 2-3 四种平面布置图 12

图 2-4 面积违反的两种不同形式 12

图 3-1 可二分数表示 14

图 3-2 模拟退火算法流程图 18

图 3-3 版图及其 B*-tree 表示 21

图 3-4 删除操作情形一 23

图 3-5 删除操作情形二 22

图 3-6 删除操作情形三 23

图 4-1 B*-tree 的三种扰动方法 25

表清单

表序号 表名称 页码

表 1-1 模拟退火算法异于物理退火算法的方面 15

表 4-1 当 AR=1 时 SA 算法和 MSA 算法的比较 27

表 4-2 当 AR=2 时 SA 算法和 MSA 算法的比较 28

表 4-2 当 AR=3 时 SA 算法和 MSA 算法的比较 29

1 绪论

集成电路极大程度地改变了人类工作与生活的方式：从巡航导弹上的微电脑, 电脑互联网，手提无线电话，到传真机等各类家用电器，用硅等半导体材料制成 的集成电路芯片已经无所不在。

无线通信业在过去的 20 年中得到了迅猛的发展。从最初的模拟手机到第二 代(2G)的 GSM 和 CDMA，以及蓝牙、GPRS、EDGE 乃至无线局域网(WLAN) 和第三代移动通信 3G，一系列的通信制式的发展都表明,人们对移动通信的需求 已不再局限于简单的语音通信，而是能集图像、数据传输、娱乐于一体的便携式 电子设备。

先进的集成电路技术与系统集成方案的创新使得小型化、低成本、低功耗及 便携式的通信设备在无线通信系统中大量使用。可以说，先进的系统设计与集成 电路技术的结合使得任意时间任意地点的通信成为现实。近年来，国际通信市场 的核心竞争力越来越明显地体现在通信专用集成电路的开发能力上。