【作者】 许川佩；

【导师】 莫玮；

【作者基本信息】 西安电子科技大学 ， 测试计量技术及仪器， 2006， 博士

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

【Abstract】 In order to solve the hard problem of testing for synchronous sequential circuits, improve the test generation efficiency of sequential circuits, this dissertation studies the algorithms of test pattern generation for sequential circuits. In recent years, with the rapid development of evolution algorithms, they have been used widely in the field of combination optimization. After comparing several kinds of evolution algorithms, this dissertation applies the ant algorithm, genetic algorithm and particle swarm algorithm into test pattern generation of sequential circuits, so as to obtain high-efficient test pattern generators of sequential circuits.This dissertation discusses the technique of automatic test pattern generation for sequential circuits, and the pre-processing technique of circuits, fault simulation technique for accelerating the test generation.Based on the basic theory of ant algorithm and genetic algorithm, combined with the structure characteristic,this dissertation presents the automatic test generation model of sequential circuits based on ant algorithm and genetic algorithm, and performs several kinds of experiment on international benchmark sequential circuits ISCAS’89 to verify the presented method. Compared with other similar test generation algorithms, this study can achieve higher fault coverages and more compact test sets and prove the combined method is successful. Besides, in order to get more compact test vectors, vector omission, a static compaction technique, is used to do post-processing to compact the sequences generated by ant-based.Because particle swarm optimization algorithm is simple, which can avoid complicated genetic operation, this dissertation, by using its specific memory function, applies it to the test generation of sequential circuits. Discrete PSO algorithm model for sequential circuits is created and experiments for ISCAS’89 are performed.Furthermore, in order to overcome the shortcomings of PSO algorithm, i.e., getting into logjam easily, low search precision, and slow convergence speed in the latter evolution period, this dissertation combines PSO algorithm with ant algorithm to achieve test generation. Experimental results for ISCAS’89 are listed to verify the method.Because simulation-based test generation can’t identify untestable faults, the dissertation addresses the problem by combining it with deterministic algorithm. SAT algorithm is introduced into the test generation based on ant algorithm and genetic更多还原