学位论文 > 优秀研究生学位论文题录展示

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

作　者: 许川佩
导　师: 莫玮
学　校: 西安电子科技大学
专　业: 测试计量技术及仪器
关键词: 时序电路测试生成蚂蚁算法遗传算法粒子群算法 SAT算法
分类号: TN706
类　型: 博士论文
年　份: 2006年
下　载: 479次
引　用: 4次
阅　读: 论文下载

内容摘要

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

全文目录

摘要  3-4
Abstract  4-9
第一章绪论  9-17
  1.1 数字电路测试生成  9-12
    1.1.1 数字电路测试生成的发展  9-10
    1.1.2 时序电路测试分析  10
    1.1.3 时序电路获取测试集的方法  10-12
  1.2 基于模拟的时序电路ATPG 发展  12-14
  1.3 研究目标  14-16
  1.4 论文的研究内容与组织结构  16-17
第二章时序电路测试生成的主要技术  17-35
  2.1 系统模型  17-21
    2.1.1 电路模型  17-18
    2.1.2 故障模型  18-21
  2.2 故障压缩技术  21-25
    2.2.1 故障等价  21
    2.2.2 单固定故障等价  21-22
    2.2.3 基本门的故障压缩  22-23
    2.2.4 故障支配  23-24
    2.2.5 电路中的等价故障  24-25
    2.2.6 故障压缩结果  25
  2.3 可测性分析  25-29
  2.4 故障模拟  29-34
    2.4.1 故障模拟技术  29-31
    2.4.2 HOPE 技术  31-34
    2.4.3 故障模拟的统计分析  34
  2.5 本章小结  34-35
第三章基于蚂蚁算法和遗传算法的测试生成  35-65
  3.1 概述  35-36
  3.2 测试生成流程  36-37
  3.3 蚂蚁算法和遗传算法  37-46
    3.3.1 蚂蚁算法  37-41
    3.3.2 遗传算法  41-46
  3.4 基于蚂蚁算法和遗传算法的测试生成  46-52
    3.4.1 算法描述  46-47
    3.4.2 基于蚂蚁算法和遗传算法的初始化  47-49
    3.4.3 基于蚂蚁算法和遗传算法的测试矢量生成  49-52
  3.5 测试生成实现  52-53
    3.5.1 测试生成步骤  52-53
    3.5.2 基于蚂蚁算法的测试生成示例  53
  3.6 实验结果  53-59
    3.6.1 初始化实验结果  53-55
    3.6.2 基于蚂蚁算法的测试生成实验结果  55-56
    3.6.3 基于蚂蚁算法和遗传算法的测试生成结果  56-59
  3.7 时序电路测试矢量的静态压缩  59-63
    3.7.1 概述  59-60
    3.7.2 基于矢量删除的静态压缩  60-62
    3.7.3 实验结果  62-63
  3.8 本章小结  63-65
第四章基于粒子群算法的时序电路测试生成  65-79
  4.1 粒子群优化算法  65-70
    4.1.1 粒子群算法基本原理  65-68
    4.1.2 粒子群算法的发展  68-70
  4.2 基于粒子群算法的时序电路测试生成  70-74
    4.2.1 自动测试生成粒子群模型  71-72
    4.2.2 测试生成步骤  72-73
    4.2.3 实验结果  73-74
  4.3 基于粒子群算法和蚂蚁算法的时序电路自动测试生成  74-78
    4.3.1 概述  74-75
    4.3.2 基于粒子群算法和蚂蚁算法的时序电路自动测试生成  75-76
    4.3.3 实验结果  76-78
  4.4 本章小结  78-79
第五章基于模拟和确定性算法的测试生成  79-91
  5.1 概述  79-80
  5.2 SAT 算法简介  80-82
    5.2.1 SAT 问题概述  80-81
    5.2.2 可满足性问题的有关定义  81
    5.2.3 SAT 的算法  81-82
  5.3 可满足性测试生成的基本原理  82-84
    5.3.1 可满足性测试生成的基本原理  82-83
    5.3.2 基本门的CNF 范式  83-84
  5.4 基于模拟和SAT 的测试生成  84-87
    5.4.1 基于SAT 的时序电路测试生成  84-85
    5.4.2 布尔可满足性搜索算法  85-86
    5.4.3 基于模拟和SAT 的测试生成实现  86-87
  5.5 实验结果  87-89
  5.6 本章小结  89-91
第六章 MCM 互连测试的探针路径优化研究  91-115
  6.1 MCM 基板的互连测试方法  91-94
    6.1.1 单探针测试  92
    6.1.2 双探针测试  92-93
    6.1.3 单双探针混合测试的原理  93-94
  6.2 探针测试路径优化  94-95
  6.3 基于蚂蚁算法的探针测试路径优化  95-107
    6.3.1 定义  96
    6.3.2 蚂蚁算法求解单探针路径的数学模型  96-99
    6.3.3 基于蚂蚁算法的单探针测试路径优化实现  99-103
    6.3.4 参数仿真试验  103-107
    6.3.5 小结  107
  6.4 MCM 基板互连的探针测试策略和路径优化  107-111
    6.4.1 MCM 基板互连的探针测试和路径优化流程  108-111
  6.5 大规模 MCM 基板互连的探针测试路径优化  111-112
  6.6 探针测试路径优化算法的复杂度分析  112-113
  6.7 本章小结  113-115
第七章结束语  115-117
参考文献  117-127
致谢  127-129
攻读博士学位其间的研究成果  129-130

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

内容摘要

全文目录

相似论文