【作者】 黄越；

【导师】 须文波；

【作者基本信息】 江南大学 ， 轻工信息技术与工程， 2012， 博士

【摘要】 随着数字电路规模与复杂度的不断提高,电路测试变得越来越困难。传统的测试生成算法已经无法适应数字电路的发展,需要不断的研究新颖的测试生成及其相关的算法。本文以测试生成算法作为主要研究对象,以提高测试算法故障覆盖率和时间效率为研究目标。主要的研究内容和研究成果如下: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)论文最后对所做工作进行了总结,并提出了进一步研究的方向。更多还原

【Abstract】 With the scale and complexity growing, digital Circuit testing is becoming more and more difficult. Traditional test pattern generations are no longer meeting the actual development demand of digital circuit. Novel test pattern generation and related algorithms need to be proposed constantly.Test pattern generations are chosen as objects, and fault coverage and time complexity are aimed in this dissertation. The major research contents and results are as follows:1) The Role and Status of test pattern generation is realized by introducing basic implementing process of VLSI. The main flow of IC testing is described too. Meanwhile the development and current study status of test pattern generation for digital circuits is summarized.2) This dissertation introduces basic concepts and algebra of satisfiability in detail. At same time, satisfiability algorithms are expatiated on classification, history, present research, and applications.3) A Non-backtracking Multipath Algorithm For Test Pattern Generation (NBMP) which different from traditional test pattern generation is proposed. A Non-backtracking Multipath AlgorithmsNBMP constructs singular cubes which only contain primary inputs and fault driving cubes which only connect with primary outputs. Then, NBMP produces test patterns using singular cubes and fault driving cubes. NBMP not backtrack during processing. It adopts scope restricting and multi-path searching strategy.The fault coverages of test pattern involving ISCAS85 benchmarks show that NBMP algorithm is superior to the traditional test pattern generation. Moreover, the time complexity is proved approximate linearity by the time complexity analysis and experimental results4) A test pattern generation algorithm for sequential circuits, Hierarchical andIncremental SAT-based Test Pattern Generation (HISAT), is shown in this dissertation. At the first stage, faults are sensitized to output in unit of non-branching path gradually. Optional branches are put into an implicit sensitized branch tree. The prediction strategy for conflicting paths speeds path selection. After that, CNF of Constraints and activation of faults generated in this stage are used for the incremental SAT executed in the second stage.At the second stage, Implication learning is implemented while values of nodes conflict. A new learn rule based on circuit structure is added into implication rules. Algorithm returns to preceding frame for searching satiable solution when the input is not primal input. An observable parameter helps searching along the direction of primal input. By the same way, algorithm goes to following frame for fault sensitization when the output is not primal output. An observable parameter helps sensitizing towards primal output too.The fault coverages involving ISCAS89 benchmarks show that HISAT algorithm is good at the fault coverage.5) Circuits redundancy identification on Boolean functions with paths (RDIBP) is proposed in this dissertation. The RDIBP algorithm which bases on Boolean functions with paths can identify redundancy nodes of digital circuits. Boolean function representations with intermediate nodes expressed as SOP are provided by RDIBP. Moreover, the traditional Boolean function simplifications are improved for finding redundant faults more easily. The circuit nodes are divided into groups according to correlation for increasing algorithm efficiency and preventing memory explosion. So RDIBP is ensured within a reasonable time by adjusting the control parameters.RDIBP experimental results on ISCAS85 ISCAS89 and ITC99 benchmark circuits are compared and analyzed with other algorithms. The experimental results indicate that it can identify redundancy efficiently.6) In this dissertation, a multi-objective heuristic for ICs test suite reduction is also given.The time efficiency of ICs test is reduced greatly because large numbers of redundant test cases exist in test suites. Four test suite reduction algorithms, which are Greedy algorithm, GE, GRE and H heuristic based on the importance of test cases, are compared and analyzed.Furthermore, a new heuristic (Priority-Selected) based on the essential cases and maximal fault coverage is presented for test suite reduction. Priority-Selected algorithm selects essential cases and deletes redundancy by computing test cases weights. Therefore, selection strategies are more reasonable and efficient.Two groups of test suits are used for efficiency of Greedy, GE, GRE, H heuristic and‘Priority-Selected’.‘Priority-Selected’is proved effective in test suite reduction. 7) Finally, the work of this dissertation is summarized and the prospective research is discussed.更多还原