基于蚁群算法和粒子群算法的数字集成电路测试生成研究

论文摘要

随着电子技术的发展,集成电路的规模越来越大,结构也越来越复杂,这使得数字电路的测试生成变得越发困难。近几年,仿生学算法的研究进展非常迅速,该类算法可以有效地解决组合优化问题,而测试生成问题的本质就是组合优化问题,因此,很多算法被用到了数字电路测试当中来,例如,遗传算法、蚁群算法和粒子群算法等。将仿生学算法引入测试生成当中,能使测试生成问题的复杂性得到简化。本文以数字电路的测试生成为研究对象,采用单固定型故障模型,以提高算法的故障覆盖率和缩小测试生成时间为目标,对蚁群算法和粒子群算法进行了改进,并将二者有机的结合起来,应用在数字电路的测试生成当中。首先,将蚁群算法的信息素更新机制进行改进,使其免于陷入局部最优,并应用于数字电路的测试生成中,与基于遗传算法的测试生成算法相比,提高了故障的覆盖率;其次,又对粒子群算法的参数进行了改进,使其具有较好的收敛性,并将其应用到数字电路测试生成中,与蚁群算法相比得到较短的测试时间;最后,根据蚁群和粒子群算法的各自优势,将二者结合起来生成新的测试生成算法,实验结果表明,测试时间和故障覆盖率都得到了提高。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究的背景及意义
• 1.2 测试生成的发展史及国内外研究现状
• 1.3 测试生成模式
• 1.4 本论文的工作及论文结构
• 第2章 基于模拟的测试生成
• 2.1 基本原理
• 2.2 基本概念
• 2.3 故障模型
• 2.4 性能评价指标
• 2.5 典型的测试生成的方法
• 2.5.1 代数方法
• 2.5.2 二叉判定树（BDD）
• 2.5.3 结构化方法
• 2.5.4 G-F算法
• 2.6 基于模拟的测试生成
• 2.7 本章小结
• 第3章 基于蚁群算法的数字电路测试生成
• 3.1 蚁群算法简介
• 3.2 蚁群算法基本原理
• 3.3 算法模型
• 3.3.1 数学模型
• 3.3.2 算法描述
• 3.4 基于蚁群算法的数字电路测试生成
• 3.5 基本蚁群算法的改进
• 3.5.1 基本定义
• 3.5.2 模型改进
• 3.6 基于改进的蚁群算法的故障检测
• 3.6.1 算法描述
• 3.6.2 实验结果及比较
• 3.7 本章小结
• 第4章 基于粒子群算法的数字电路测试生成
• 4.1 粒子群算法简介
• 4.2 粒子群算法的基本原理
• 4.3 算法模型
• 4.3.1 数学模型
• 4.3.2 算法描述
• 4.4 基于粒子群算法的数字电路测试生成算法
• 4.5 基本粒子群算法的改进
• 4.6 基于改进的粒子群算法的故障检测
• 4.6.1 算法描述
• 4.6.2 实验结果及比较
• 4.7 本章小结
• 第5章 基于蚁群算法和粒子群算法相结合的数字电路测试生成
• 5.1 蚁群算法和粒子群算法的比较
• 5.2 蚁群和粒子群相互结合的算法
• 5.3 基于蚁群和粒子群算法相互结合的数字电路测试生成
• 5.3.1 数学模型
• 5.3.2 算法描述
• 5.3.3 实验结果及比较
• 5.4 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间发表的论文和取得的科研成果
• 致谢
• 个人简历