数字集成电路测试生成算法研究

论文摘要

随着现代科技的快速发展,数字集成电路已经被广泛应用于各行各业,于此同时数字集成电路的测试问题也就越来越受到人们的重视。数字集成电路设计、生产、应用的各个必要阶段都离不开测试,设计者为了验证其设计的正确性要进行测试;生产者为了保证产品的合格率要进行测试;用户为了实现正确的功能要进行测试。因此数字集成电路测试生成方法的研究在科技迅速发展的今天具有十分重要的意义。尽管国内外学者不断提出各种数字集成电路的测试生成方法,但测试耗费在电路生产过程中仍占很大比重。从现有关于测试生成的研究来看,测试生成的主要困难在于难测故障的测试、得到的测试集尺寸较大、时序电路在测试前需要进行初始化。为此,本文在并行故障模拟的基础上,研究了基于模拟的数字集成电路测试生成方法,将新型的智能优化算法应用于电路的测试生成、测试集优化和时序电路初始化,降低了测试复杂度,减少了需要的存储空间,提高了测试效率。首先,针对组合电路测试生成方法的研究现状,提出利用粒子群优化算法、混沌粒子群算法和文化粒子群算法实现组合电路的测试生成。整个测试算法由两部分组成:以易测故障为目标的多故障测试和以难测故障为目标的单故障测试,定义了新的适应度函数。同时提出采用半随机产生初始群体、反矢量故障模拟、逻辑相关的故障分组和排序等加速方法。分别实现了粒子群优化算法、混沌粒子群算法、文化粒子群算法在采用加速方法和不采用加速方法时ISCAS’85组合电路的测试生成。实验结果表明,这3种算法都能得到文献最好水平的故障覆盖率,同时加速方法大大提高了测试效率,其中基于加速方法的文化粒子群算法得到了最好结果。其次,针对时序电路在测试前必须进行初始化使触发器到达确定的状态,提出利用粒子群优化算法、混沌粒子群算法和文化粒子群算法实现时序电路的逻辑初始化。并在初始化的基础上实现时序电路的测试生成,定义了新的适应度函数。以ISCAS’89时序电路为实验电路进行仿真,实验结果表明,这3种算法能生成较短的初始化序列、达到较高的故障覆盖率,其中混沌粒子群算法的故障覆盖率最高。再次,针对常规测试方法得到的测试集尺寸较大问题,提出利用粒子群算法、混沌粒子群算法和文化粒子群算法实现电路测试集的静态优化。先对测试集进行预处理,如果测试集含有冗余矢量,则进行测试集优化。算法实现时可以采用两种编码方式:针对测试矢量编码和针对故障编码,相应地有两种适应度函数定义形式,并提出利用混沌搜索产生初始群体、对测试集进行倒序排列模拟。利用这3种算法针对不同电路进行了3个仿真实验。仿真结果表明,这3种算法均能不同程度地减小完备测试集的尺寸,其中基于故障编码的文化粒子群算法能得到最小尺寸的完备测试集。最后,针对现有的可测性设计方法需要施加额外硬件问题,研究只需已知电路逻辑表达式、不需要施加额外硬件的基于多元症候群的组合电路可测性设计,指出它不适用于具有对于所有原始输入都对称的逻辑函数的电路。提出故障值直接前向进行逻辑运算来识别时序电路的冗余故障。利用实例证明了它们的可行性。综上所述,本论文研究了基于智能优化算法的数字集成电路的测试矢量生成、测试集优化和可测性设计。主要采用粒子群优化算法、混沌粒子群算法和文化粒子群算法,并提出了几种加速方法。仿真实验证实,本文所应用的算法和提出的加速方法能够获得很好的效果。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题的背景和意义
• 1.2 测试生成概述
• 1.2.1 测试生成原理
• 1.2.2 测试生成相关概念
• 1.2.3 故障和故障模型
• 1.2.4 性能评价指标
• 1.3 测试生成算法的发展及国内外研究现状
• 1.3.1 组合电路测试生成算法的发展及研究现状
• 1.3.2 时序电路测试生成算法的发展及研究现状
• 1.3.3 测试生成算法分类
• 1.4 可测性设计的研究现状
• 1.5 本文主要研究内容
• 第2章 优化算法理论
• 2.1 引言
• 2.2 粒子群优化算法
• 2.2.1 基本原理
• 2.2.2 进化规则
• 2.2.3 参数分析
• 2.2.4 算法实现
• 2.3 混沌优化
• 2.3.1 混沌运动特性
• 2.3.2 混沌优化理论
• 2.4 混沌粒子群算法
• 2.5 文化算法
• 2.5.1 文化算法理论
• 2.5.2 文化算法的群体空间和信念空间
• 2.6 文化粒子群算法
• 2.7 本章小结
• 第3章 基于模拟的组合电路测试生成
• 3.1 引言
• 3.2 故障压缩
• 3.2.1 等价压缩
• 3.2.2 支配压缩
• 3.2.3 压缩方法的实现
• 3.3 故障模拟方法
• 3.4 基于进化算法的组合电路测试生成
• 3.4.1 测试生成过程描述
• 3.4.2 加速方法
• 3.4.3 基于粒子群算法的组合电路测试生成
• 3.4.4 基于混沌粒子群算法的组合电路测试生成
• 3.4.5 基于文化粒子群算法的组合电路测试生成
• 3.4.6 仿真结果及分析
• 3.5 本章小结
• 第4章 基于模拟的时序电路测试生成
• 4.1 引言
• 4.2 时序电路的初始化研究
• 4.2.1 基于进化算法的时序电路逻辑初始化
• 4.2.2 仿真结果及分析
• 4.3 基于模拟的时序电路测试生成
• 4.3.1 算法描述
• 4.3.2 实验结果及分析
• 4.4 本章小结
• 第5章 电路测试集的静态优化
• 5.1 引言
• 5.2 静态优化测试集
• 5.2.1 测试矩阵
• 5.2.2 基于进化算法的测试集静态优化
• 5.2.3 基于粒子群算法的测试集优化
• 5.2.4 基于混沌粒子群算法的测试集优化
• 5.2.5 基于文化粒子群算法的测试集优化
• 5.2.6 应用实例
• 5.3 仿真结果及分析
• 5.3.1 仿真实验1
• 5.3.2 仿真实验2
• 5.3.3 仿真实验3
• 5.4 本章小结
• 第6章 可测性设计方法研究
• 6.1 引言
• 6.2 可测性度量
• 6.2.1 可测性度量的定义
• 6.2.2 SCOAP测度
• 6.3 可测性设计方法
• 6.3.1 组合电路的可测性设计
• 6.3.2 时序电路的可测性设计
• 6.4 本章小结
• 结论
• 参考文献
• 攻读博士学位期间发表的论文和取得的科研成果
• 致谢