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

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

作　者: 黄越
导　师: 须文波
学　校: 江南大学
专　业: 轻工信息技术与工程
关键词: 测试向量生成 SAT算法数字电路可满足性冗余识别合取范式测试集约简
分类号: TN431.2
类　型: 博士论文
年　份: 2012年
下　载: 6次
引　用: 0次
阅　读: 论文下载

内容摘要

随着数字电路规模与复杂度的不断提高,电路测试变得越来越困难。传统的测试生成算法已经无法适应数字电路的发展,需要不断的研究新颖的测试生成及其相关的算法。本文以测试生成算法作为主要研究对象,以提高测试算法故障覆盖率和时间效率为研究目标。主要的研究内容和研究成果如下:1)通过介绍VLSI集成电路实现的基本流程,阐述测试生成在集成电路实现中的作用和地位。文中还介绍了集成电路测试的基本流程,综述了当前数字电路测试生成的发展及研究状态。2)较详细地介绍了可满足性问题的基本概念和代数基础,以及可满足性算法的基本分类、发展历史以及研究与应用状态。3)提出一个与传统组合电路测试生成算法不同的无回溯并行多路径搜索测试向量生成算法(NBMP)。算法在生成测试向量过程中生成基于原始输入端的奇异立方和与原始输出端关联的传输立方,并利用生成的奇异立方和传输立方生成测试向量。实现过程无须回溯,采用规模控制和多路径探索策略。算法对ISCAS85基准电路进行实验,将实验结果与传统算法结果进行比较,实验表明NBMP算法故障覆盖率优于传统算法。通过分析和实验结果证明算法时间复杂度近似为线性。4)本文提出一个时序电路测试生成算法——基于SAT分级处理增量式测试生成算法(HISAT)。在第一级,以算法提出的无分支路径为单位,向输出端进行故障敏化。用隐含分支敏化通路树存放备选路径,采用路径冲突预判策略提高路径选择速度。在敏化路径过程中生成的约束CNF及故障激活CNF,被第二级增量式SAT算法所使用。在第二级,对于冲突节点进行蕴含学习以预防未来冲突的发生。在蕴含学习规则中,增加了基于电路结构的学习规则。当输入端不为原始输入端时,需回到前一帧搜索可满足解,一个可观察参数指导算法向原始输入端搜索。输出端不为原始输出端时,需向后一帧敏化,算法同样提供一个可观察参数指导算法向原始输出端敏化。算法对ISCAS89基准电路进行实验,且与其它算法结果进行了比较和分析。实验表明HISAT算法的故障覆盖率高。5)提出一个基于带路径布尔函数的电路冗余识别(RDIBP)算法。RDIBP算法能够发现数字电路中的冗余故障。本文提出了带中间节点信息,基于SOP形式的布尔函数表示方法。为了便于发现冗余故障改进了传统的布尔函数化简。根据电路节点相关性,将电路节点分组以提高算法效率,防止内存爆炸。通过调整控制参数确保算法在合理的时间内完成。算法对ISCAS85,ISCAS89和ITC99基准电路进行实验,且与其它算法结果进行了比较和分析。实验表明RDIBP算法能够有效地识别电路冗余故障。6)本文又提出一个多目标启发式集成电路测试集约简算法(Priority-Selected)。集成电路故障测试集往往含有大量的冗余,造成集成电路测试效率降低。本文对已有的贪婪算法、GE算法、GRE算法和Harrold提出的基于测试用例重要性的启发式算法进行了分析,提出一个依据必不可少用例和最大故障需求用例的启发式集成电路测试集约简算法(Priority-Selected)。Priority-Selected算法通过计算测试向量权值选择需要的测试用例,并去除测试集中的所有的冗余,因此选择策略更加合理,效率也更高。两个系列的测试用例集用来测试贪婪算法、GE算法、GRE算法、H算法和Priority-Selected算法的效率。实验表明Priority-Selected算法是有效的。7)论文最后对所做工作进行了总结,并提出了进一步研究的方向。

全文目录

摘要  3-5
Abstract  5-7
目录  7-10
第一章绪论  10-18
  1.1 课题研究背景  10-13
    1.1.1 VLSI 实现的基本流程  10-11
    1.1.2 集成电路的测试成本  11-13
    1.1.3 集成电路的测试基本流程  13
  1.2 数字电路测试生成方法概述  13-14
  1.3 本文课题的主要研究工作  14-15
  1.4 论文的组织结构  15-18
第二章数字电路测试生成相关概念和原理  18-42
  2.1 测试生成基本原理和概念  18-32
    2.1.1 基本概念  18-19
    2.1.2 缺陷、失效和故障  19-20
    2.1.3 基本故障模型  20-22
    2.1.4 故障等效与压缩  22-24
    2.1.5 自动测试向量生成（ATPG）  24-30
    2.1.6 测试向量生成算法评价  30-31
    2.1.7 故障冗余的识别  31
    2.1.8 测试集优化  31-32
  2.2 数字电路测试生成算法研究现状  32-40
    2.2.1 组合电路测试生成算法  32-36
    2.2.2 时序电路测试生成算法  36-40
  2.3 本章小结  40-42
第三章无回溯组合电路测试生成算法  42-52
  3.1 引言  42
  3.2 相关定义  42-43
  3.3 无回溯并行多路径搜索测试向量生成算法（NBMP）  43-48
    3.3.1 NBMP 算法思想  43-45
    3.3.2 NBMP 算法效率分析  45-46
    3.3.3 NBMP 算法的实现  46-48
  3.4 实验结果与分析  48-51
  3.5 结论  51-52
第四章可满足性测试生成算法  52-66
  4.1 可满足性相关概念  52-57
    4.1.1 基本概念  52-53
    4.1.2 可满足性相关代数定义  53-56
    4.1.3 数字电路基本逻辑门的布尔表达式的CNF 范式表达  56-57
  4.2 SAT 算法简介  57-60
    4.2.1 完备的SAT 算法  57-59
    4.2.2 不完备的SAT 算法  59-60
  4.3 DPLL 算法  60-64
    4.3.1 DP 算法  61-62
    4.3.2 DPLL 算法（递归形式）  62-63
    4.3.3 DPLL 算法（迭代形式）  63-64
    4.3.4 BCP 算法  64
  4.4 本章小结  64-66
第五章基于SAT 分级处理增量式测试生成  66-80
  5.1 算法提出背景  66-67
  5.2 基于增量式SAT 测试生成算法  67-68
  5.3 基于SAT 分级处理增量式测试生成（HISAT）相关概念  68-70
    5.3.1 电路无分支路径  68
    5.3.2 支配故障压缩  68-69
    5.3.3 路径冲突处理和路径冲突预测  69-70
  5.4 基于SAT 分级处理增量式测试生成算法思想  70-74
    5.4.1 分级处理  70-72
    5.4.2 增量式SAT  72-74
    5.4.3 时序处理  74
  5.5 基于SAT 分级处理增量式测试生成算法实现  74-76
  5.6 实验结果与分析  76-78
  5.7 结论  78-80
第六章基于带路径布尔函数的电路冗余识别  80-92
  6.1 基本概念  80-81
    6.1.1 冗余故障  80-81
    6.1.2 布尔代数系统  81
  6.2 数字电路逻辑冗余识别算法（RDIBP）  81-84
    6.2.1 带路径的数字电路布尔函数的表示  81-82
    6.2.2 带路径的布尔函数化简规则及公式  82-83
    6.2.3 实例分析  83
    6.2.4 分组策略和规模控制策略  83-84
  6.3 RDIBP 算法实现  84-88
    6.3.1 测试集合组生成(TGSEK)  85
    6.3.2 布尔函数项的化简(BIS)  85-86
    6.3.3 布尔函数的化简(BFS)  86-87
    6.3.4 冗余路径选择  87-88
  6.4 实验结果与分析  88-89
  6.5 结论  89-92
第七章一个多目标启发式集成电路测试集约简算法  92-102
  7.1 引言  92
  7.2 相关定义  92-93
  7.3 现存算法分析  93-94
  7.4 一个启发式测试集约简算法（Priority-Selected）  94-96
  7.5 实验结果与分析  96-101
  7.6 结论  101-102
第八章结束语  102-106
致谢  106-108
参考文献  108-120
附录  120

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

内容摘要

全文目录

相似论文