时序电路测试生成算法研究

论文摘要

为解决同步时序电路的测试难题,提高时序电路测试生成效率,本文进行了时序电路测试生成算法的研究。近年来,发展迅速的进化算法在组合优化等领域获得了广泛的应用,本文在对多种进化算法进行研究比较的基础上,将蚂蚁算法、遗传算法、粒子群算法等应用在时序电路的测试生成上,希望能够从中获得高效的时序电路测试生成器。首先研究了时序电路自动测试生成技术,主要是为加速测试生成采用的电路预处理和故障模拟技术。在研究蚂蚁算法和遗传算法基本原理的基础上,结合时序电路的结构特点,提出了带初始化的基于蚂蚁算法和遗传算法的自动测试生成模型,针对国际标准时序电路ISCAS’89进行了多项实验验证,与同类算法相比,均获得了较好的测试生成结果,证明了两种算法的结合是成功的。此外,为得到更加精简的测试集,采用了矢量删除的静态压缩方法对基于蚂蚁算法的测试生成结果进行了后处理。鉴于粒子群算法操作简单,可以避免复杂的遗传操作,本文利用其特有的记忆功能,将其应用在时序电路的测试生成中。针对时序电路建立了离散粒子群自动测试生成模型,并针对ISCAS’89进行了实验验证。此外,为解决粒子群算法容易出现停滞现象,搜索精度不高,进化后期收敛速度慢的缺点,结合蚂蚁算法实现时序电路的测试生成,并针对ISCAS’89进行了实验验证,给出了相关实验结果。为解决基于模拟的测试生成不能识别不可测故障的缺点,将其与确定性算法相结合实现测试生成。在基于蚂蚁算法和遗传算法的测试生成基础上再引入SAT算法。SAT算法通过将时序电路进行迭代连接构成迭代组合模型,再转换为CNF范式,调用组合SAT算法求解实现。针对ISCAS’89的实验结果表明,模拟和确定性算法的结合使得测试生成效率得到了进一步的提高。为解决MCM基板互连测试探针路径优化问题,在研究了MCM互连测试探针路径优化原理的基础上,结合MCM基板互连的结构特点,建立了ACS求解单探针路径的数学模型,给出了探针测试策略,实现了基于蚂蚁算法的探针测试路径优化,并进行了相关参数仿真实验。采用分片优化的方法,首次解决了大规模MCM基板互连的探针测试路径优化问题。针对MCNC提供的MCM Benchmark进行了实验,本文设计的算法在优化结果上均优于其它算法,从而证明了蚂蚁算法在解决探针测试路径优化问题中的有效性,其主要原因在于蚂蚁算法信息素的引入,使得蚂蚁算法能够以较稳定的速度逼近最优解,而且收敛速度较快。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 数字电路测试生成
• 1.1.1 数字电路测试生成的发展
• 1.1.2 时序电路测试分析
• 1.1.3 时序电路获取测试集的方法
• 1.2 基于模拟的时序电路ATPG 发展
• 1.3 研究目标
• 1.4 论文的研究内容与组织结构
• 第二章 时序电路测试生成的主要技术
• 2.1 系统模型
• 2.1.1 电路模型
• 2.1.2 故障模型
• 2.2 故障压缩技术
• 2.2.1 故障等价
• 2.2.2 单固定故障等价
• 2.2.3 基本门的故障压缩
• 2.2.4 故障支配
• 2.2.5 电路中的等价故障
• 2.2.6 故障压缩结果
• 2.3 可测性分析
• 2.4 故障模拟
• 2.4.1 故障模拟技术
• 2.4.2 HOPE 技术
• 2.4.3 故障模拟的统计分析
• 2.5 本章小结
• 第三章 基于蚂蚁算法和遗传算法的测试生成
• 3.1 概述
• 3.2 测试生成流程
• 3.3 蚂蚁算法和遗传算法
• 3.3.1 蚂蚁算法
• 3.3.2 遗传算法
• 3.4 基于蚂蚁算法和遗传算法的测试生成
• 3.4.1 算法描述
• 3.4.2 基于蚂蚁算法和遗传算法的初始化
• 3.4.3 基于蚂蚁算法和遗传算法的测试矢量生成
• 3.5 测试生成实现
• 3.5.1 测试生成步骤
• 3.5.2 基于蚂蚁算法的测试生成示例
• 3.6 实验结果
• 3.6.1 初始化实验结果
• 3.6.2 基于蚂蚁算法的测试生成实验结果
• 3.6.3 基于蚂蚁算法和遗传算法的测试生成结果
• 3.7 时序电路测试矢量的静态压缩
• 3.7.1 概述
• 3.7.2 基于矢量删除的静态压缩
• 3.7.3 实验结果
• 3.8 本章小结
• 第四章 基于粒子群算法的时序电路测试生成
• 4.1 粒子群优化算法
• 4.1.1 粒子群算法基本原理
• 4.1.2 粒子群算法的发展
• 4.2 基于粒子群算法的时序电路测试生成
• 4.2.1 自动测试生成粒子群模型
• 4.2.2 测试生成步骤
• 4.2.3 实验结果
• 4.3 基于粒子群算法和蚂蚁算法的时序电路自动测试生成
• 4.3.1 概述
• 4.3.2 基于粒子群算法和蚂蚁算法的时序电路自动测试生成
• 4.3.3 实验结果
• 4.4 本章小结
• 第五章 基于模拟和确定性算法的测试生成
• 5.1 概述
• 5.2 SAT 算法简介
• 5.2.1 SAT 问题概述
• 5.2.2 可满足性问题的有关定义
• 5.2.3 SAT 的算法
• 5.3 可满足性测试生成的基本原理
• 5.3.1 可满足性测试生成的基本原理
• 5.3.2 基本门的CNF 范式
• 5.4 基于模拟和SAT 的测试生成
• 5.4.1 基于SAT 的时序电路测试生成
• 5.4.2 布尔可满足性搜索算法
• 5.4.3 基于模拟和SAT 的测试生成实现
• 5.5 实验结果
• 5.6 本章小结
• 第六章 MCM 互连测试的探针路径优化研究
• 6.1 MCM 基板的互连测试方法
• 6.1.1 单探针测试
• 6.1.2 双探针测试
• 6.1.3 单双探针混合测试的原理
• 6.2 探针测试路径优化
• 6.3 基于蚂蚁算法的探针测试路径优化
• 6.3.1 定义
• 6.3.2 蚂蚁算法求解单探针路径的数学模型
• 6.3.3 基于蚂蚁算法的单探针测试路径优化实现
• 6.3.4 参数仿真试验
• 6.3.5 小结
• 6.4 MCM 基板互连的探针测试策略和路径优化
• 6.4.1 MCM 基板互连的探针测试和路径优化流程
• 6.5 大规模 MCM 基板互连的探针测试路径优化
• 6.6 探针测试路径优化算法的复杂度分析
• 6.7 本章小结
• 第七章 结束语
• 参考文献
• 致谢
• 攻读博士学位其间的研究成果