SAT数据结构与组合测试生成

有效的布尔可满足性算法必然包括有效的数据结构。本文深入地分析了用于回溯搜索SAT算法的数据结构，指出了它们各自所具有的优势和不足。并将SAT应用于组合电路的测试生成中。根据应用的特点和在分析的基础上，设计并实现了一个主要是针对组合测试生成的SAT算法，初步的实验结果证明了它在测试生成应用中的有效性。     

基于改进型SAT求解器算法的组合电路等价性检查研究

随着工艺节点的缩小,集成电路规模的增加,集成电路设计过程中逻辑等价性检查在确保设计功能正确性方面起着重要作用。文章研究了组合电路逻辑等价性检查技术,针对该领域常用的DPLL和CDCL算法存在的问题,提出了一种基于蒙特卡洛树搜索的改进算法。通过对ISCAS85测试集的一个子集的实验,证实该算法对CDCL算法有一定的改进,应用于组合电路等价性检查的平均运行时间减少了20%。     

组合电路桥接故障诊断的测试生成及优化

在利用划分等价类的方法来诊断组合电路中桥接故障的基础上,本文提出了一种基于门特性的IDDQ测试集生成算法及对测试集排序筛选的优化方法.实验结果表明,将此方法应用于组合电路桥接故障的诊断可缩减测试集的大小,提高诊断的故障覆盖率.     

集成电路测试原理和向量生成方法分析

测试向量生成是集成电路测试的一个重要环节。在此从集成电路基本测试原理出发,介绍了一种ATE测试向量生成方法。通过建立器件模型和测试平台,在仿真验证后,按照ATE向量格式,直接生成ATE向量。以一种实际的双向总线驱动电路74ALVC164245为例,验证了此方法的可行性,并最终得到所需的向量文本。该方法具有较好的实用性,对进一步研究测试向量生成,也有一定的参考意义。     

基于混沌搜索的组合电路测试生成算法

基于组合电路测试生成的离散Hopfield神经网络模型，将混沌搜索与Hopfield网络的梯度算法相结合，利用混沌搜索的内随机性及遍历性来克服梯度算法易于陷于局部极小的缺点，形成一种具有全局搜索能力的测试生成有效算法。该算法综合了随机性和确定性算法的优点，其性能优于一般的随机性算法。实验结果验证了该测试生成算法的有效性。     

一种基于神经网络的组合电路测试生成算法

介绍了一种基于神经网络的组合电路测试生成算法。利用Hopfield神经网络模型将组合电路表示成对应的神经网络,通过建立被测电路的约束网络,构造神经网络的能量函数,使组合电路的测试矢量对应神经网络能量函数的最小值点,使得测试生成问题数学化,并使用遗传算法求解能量函数的最小值点得到故障电路的测试矢量。通过在一些标准电路的实验表明,该测试生成算法有效可行。     

基于硬件可编程逻辑(FPGA)的SAT算法的综述

可满足性问题(简称SAT问题)作为第一个被证明的NP完全问题,是计算机科学的核心问题之一。本文系统总结了基于硬件可编程逻辑(FPGA---Field Programmable Gate Array)的SAT算法研究。将基于FPGA的SAT算法研究分为了实例型(instance-speci-ed solver)和应用型(application-speci-ed solver)两种类型。通过对各种方法的深入分析,指出了它们的优点和缺陷,进而提出未来研究的思路。     

基于VHDL语言的数字电路测试码自动生成

本文提出了一种新的基于VHDL语言的组合数字电路测试码自动生成方法。在VHDL语言描述组合数字电路的基础上,建一VHDL语言的编译器,并输入为描述被测电路的VHDL语言,输出结果为描述被测电路功能的一系列逻辑表达式。针对这些逻辑表达式,本文详细地介绍了一种能直接产生电路测试码的算法。     

基于故障插入的电路抗老化输入矢量生成研究

随着CMOS工艺特征尺寸的不断缩小,晶体管的老化效应严重影响了电路的可靠性,负偏置温度不稳定性(NBTI)是造成晶体管老化的主要因素之一。提出了一种基于固定故障插入的电路抗老化输入矢量生成方法,在电路的合适位置插入固定故障,通过自动测试向量生成(ATPG)工具获取较小的备选抗老化矢量集合,再从中筛选出最优矢量。由该方法生成的输入矢量可以使电路在待机模式下处于最大老化恢复状态,同时具有较小的时间开销。在ISCAS85电路中的仿真结果表明,与随机矢量生成方法相比,在电路待机模式下加载本文方法生成的输入矢量,可以达到最高17%的电路老化时延改善率。     

基于探索式分区和测试向量生成的硬件木马检测方法

本文提出基于分区和最优测试向量生成的硬件木马检测方法.首先,采用基于扫描细胞分布的分区算法将电路划分为多个区域.然后,提出测试向量重组算法,对各区域依据其自身结构生成近似最优的测试向量.最后,进行分区激活和功耗分析以检测木马,并采用信号校正技术消减制造变异和噪声的影响.优点是成倍提高了检测精度,克服了制造变异的影响,解决了面对大电路的扩展性问题,并可以定位木马.在基准电路上的验证实验表明检测性能有较大的提升.     

基于分布估计算法的组合电路测试生成

基于遗传算法生成的测试矢量集的故障覆盖率要低于确定性方法．本文分析指出造成这种现象的一个可能原因在于，组合电路测试生成过程中存在高阶、长距离模式，从而导致遗传算法容易陷人局部极值或早熟收敛．为此，本文首次提出使用分布估计算法生成测试矢量．该方法使用联合概率分布捕捉电路主输人之间的关联性。从而避免了高阶、长距离模式对算法的影响，缓解了算法早熟收敛问题．针对ISCAS-85国际标准组合电路集的实验结果表明，该方法能够获得较高的故障覆盖率．     

Functional Fault Equivalence and Diagnostic Test Generation in Combinational Logic Circuits Using Conventional ATPG

Fault equivalence is an essential concept in digital design with significance in fault diagnosis, diagnostic test generation, testability analysis and logic synthesis. In this paper, an efficient algorithm to check whether two faults are equivalent is presented. If they are not equivalent, the algorithm returns a test vector that distinguishes them. The proposed approach is complete since for every pair of faults it either proves equivalence or it returns a distinguishing vector. The advantage of the approach lies in its practicality since it uses conventional ATPG and it automatically benefits from advances in the field. Experiments on ISCAS’85 and full-scan ISCAS’89 circuits demonstrate the competitiveness of the method and measure the performance of simulation for fault equivalence.     

Distributed Test Pattern Generation for Stuck-At Faults in Sequential Circuits

Automatic test pattern generation (ATPG) remains one of themost complex CAD tasks. Therefore, numerous methods were proposed tospeed up ATPG by using parallelism. In this paper, we focus onparallelizing ATPG for stuck-at faults in sequential circuits bycombining fault and search space parallelism. Fault parallelism isapplied to so-called easy-to-detect faults. The main task of thisapproach is to find a best-suited partitioning of the fault list,based on dependencies between faults. For hard-to-detect faultsleft by fault parallelism, search space partitioning is applied,integrating depth-first and breadth-first search. Since a smalltest set size is mandatory for a cheap test and fault parallelismincreases the number of test patterns, test set compaction is donein a post-processing phase. Results show that our approach is notonly capable of achieving potentially superlinear speedups, but alsoimproves test set quality. The parallel environment we use consistsof a network of 100 workstations connected via ethernet.     

论有限回溯测试模式产生方法

本文首先剖析了有限回溯测试模式产生(FBTPG)方法的实质,然后在深入分析三种ATPG系统的C-B曲线的实验数据的基础上,提出故障模拟对测试生成的综合调节效应,为FBTPG方法的有效性提供了理论依据.最后以ISCAS-85和ISCAS-89电路为基础,给出了FBTPG与随机测试生成、确定性测试生成和商用ATPG系统FlexTest的实验比较结果,从而论证了FBTPG方法处理超大规模时序电路的有效性.     

基于变周期重播种LFSR的测试生成

基于重播种的LFSR结构的伪随机测试生成中包含的冗余测试序列较多,因而其测试序列长度仍较长,耗费测试时间长,测试效率不高。针对此状况,提出基于变周期重播种的LFSR结构的测试生成方法。该方法可以有效地跳过伪随机测试生成中的大量冗余测试序列。在保证电路测试故障覆盖率不变的条件下,缩短总测试序列的长度。分析结果表明,同定长重播种方法相比,该方法能以较少的硬件开销实现测试序列的精简,加快了测试的速度,提高了电路测试诊断的效率。     

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

为解决同步时序电路的测试难题,提高时序电路测试生成效率,进行了时序电路测试生成算法的研究,将粒子群优化算法应用在时序电路的测试生成中。为验证PSO算法性能,首先将其用于函数优化,能获得较好的优化结果。之后建立自动测试生成离散粒子群速度—位置模型,针对国际标准时序电路的验证结果表明,与同类算法相比,该算法可以获得较高的故障覆盖率和较小的测试矢量集。     

Fast Test Pattern Generation for Sequential Circuits Using Decision Diagram Representations

The paper presents a novel hierarchical approach to test pattern generation for sequential circuits based on an input model of mixed-level decision diagrams. A method that handles, both, data and control parts of the design in a uniform manner is proposed. The method combines deterministic and simulation-based techniques. On the register-transfer level, deterministic path activation is combined with simulation based-techniques used for constraints solving. The gate-level local test patterns for components are randomly generated driven by high-level constraints and partial path activation solutions. Experiments show that high fault coverages for circuits with complex sequential structures can be achieved in a very short time by using this approach.     

Enhancing SAT-Based Test Pattern Generation

This paper presents modeling tools based on Boolean satisfiability (SAT) to solve problems of test generation for combinational circuits. It exploits an added layer to maintain circuit-related information and value justification relations to a generic SAT algorithm. It dovetails binary decision graphs (BDD) and SAT techniques to improve the efficiency of automatic test pattern generation (ATPG). More specifically, it first exploits inexpensive reconvergent fanout analysis of circuit to gather information on the local signal correlation by using BDD learning, then uses the above learned information to restrict and focus the overall search space of SAT-based ATPG. Its learning technique is effective and lightweight. The experimental results demonstrate the effectiveness of the approach.     

Test Generation and Fault Simulation for Cell Fault Model using Stuck-at Fault Model based Test Tools

Cell Fault Model (CFM) is a well-adopted functional fault model used for cell-based circuits. Despite of the wide adoption of CFM, no test tool is available for the estimation of CFM testability. The vast majority of test tools are based on the single stuck-at fault model.In this paper we introduce a method to calculate the CFM testability of a cell-based circuit using any single stuck-at fault based test tool. Cells are substituted by equivalent cells and Test Generation and Fault Simulation for CFM are emulated by Test Generation and Fault Simulation for a set of single stuck-at faults of the equivalent cells. The equivalent cell is constructed from the original cell with a simple procedure, with no need of knowledge of gate-level implementation, or its function. With the proposed methodology, the maturity and effectiveness of stuck-at fault based tools is used in testing of digital circuits, with respect to Cell Fault Model, without developing new tools.     

Sequential Circuits with Combinational Test Generation Complexity under Single-Fault Assumption

We show that the test generation problem for all single stuck-at faults in sequential circuits with internally balanced structures can be reduced into the test generation problem for single stuck-at faults in combinational circuits. In our previous work, we introduced internally balanced structures as a class of sequential circuits with the combinational test generation complexity. However, single stuck-at faults on some primary inputs, called separable primary inputs, corresponded to multiple stuck-at faults in a transformed combinational circuit. In this paper, we resolve this problem. We show how to generate a test sequence and identify undetectability for single stuck-at faults on separable primary inputs.