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

摘要

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

目录

文摘

英文文摘

独创性声明及关于论文使用授权的说明

第一章绪论

第二章时序电路测试生成的主要技术

第三章基于蚂蚁算法和遗传算法的测试生成

第四章基于粒子群算法的时序电路测试生成

第五章基于模拟和确定性算法的测试生成

第六章MCM 互连测试的探针路径优化研究

第七章结束语

参考文献

致谢

攻读博士学位其间的研究成果