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

测试向量生成论文 SAT算法论文 数字电路论文 可满足性论文 冗余识别论文 合取范式论文 测试集约简
论文详情
随着数字电路规模与复杂度的不断提高,电路测试变得越来越困难。传统的测试生成算法已经无法适应数字电路的发展,需要不断的研究新颖的测试生成及其相关的算法。本文以测试生成算法作为主要研究对象,以提高测试算法故障覆盖率和时间效率为研究目标。主要的研究内容和研究成果如下: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-6页
目录第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页
论文购买
论文编号ABS557593,这篇论文共120页
会员购买按0.30元/页下载,共需支付36
不是会员,注册会员
会员更优惠充值送钱
直接购买按0.5元/页下载,共需要支付60
只需这篇论文,无需注册!
直接网上支付,方便快捷!
相关论文

点击收藏 | 在线购卡 | 站内搜索 | 网站地图
版权所有 艾博士论文 Copyright(C) All Rights Reserved
版权申明:本文摘要目录由会员***投稿,艾博士论文编辑,如作者需要删除论文目录请通过QQ告知我们,承诺24小时内删除。
联系方式: QQ:277865656