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,一系列的通信制式的发展都表明,人们对移动通信的需求 已不再局限于简单的语音通信,而是能集图像、数据传输、娱乐于一体的便携式 电子设备。
先进的集成电路技术与系统集成方案的创新使得小型化、低成本、低功耗及 便携式的通信设备在无线通信系统中大量使用。可以说,先进的系统设计与集成 电路技术的结合使得任意时间任意地点的通信成为现实。近年来,国际通信市场 的核心竞争力越来越明显地体现在通信专用集成电路的开发能力上。