Search strategy switching: A cost model and an analysis of backtracking

Test generation algorithms contain search strategies which are used to control decision making when the algorithm encounters a choice of signal value, or what action to perform next. Our study of traditional search strategies used in automatic test pattern generation has led us to the observation that no single strategy is superior for all faults in a circuit and all circuits. Further experimentation led to the conclusion that a combination of search strategies provides better fault coverage and/or faster ATPG for a given backtrack limit. Instead of using just one strategy up to the backtrack limit, a primary strategy is used for the first half of the backtrack limit, then a secondary strategy is used for the second half of the backtrack limit. This article presents a qualitative ATPG cost model based on the number of test generation events, uses this model to explain why search strategy switching is faster, and shows experimental evidence to verify both the cost model and search strategy switching theory. The experiments were performed with the ISCAS circuits and our implementation of the FAN algorithm.     

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

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

A hierarchical test generation methodology for digital circuits

A new hierarchical modeling and test generation technique for digital circuits is presented. First, a high-level circuit model and a bus fault model are introduced—these generalize the classical gate-level circuit model and the single-stuck-line (SSL) fault model. Faults are represented by vectors allowing many faults to be implicitly tested in parallel. This is illustrated in detail for the special case of array circuits using a new high-level representation, called the modified pseudo-sequential model, which allows simultaneous test generation for faults on individual lines of a multiline bus. A test generation algorithm called VPODEM is then developed to generate tests for bus faults in high-level models of arbitrary combinational circuits. VPODEM reduces to standard PODEM if gate-level circuit and fault models are used. This method can be used to generate tests for general circuits in a hierarchical fashion, with both high- and low-level fault types, yielding 100 percent SSL fault coverage with significantly fewer test patterns and less test generation effort than conventional one-level approaches. Experimental results are presented for representative circuits to compare VPODEM to standard PODEM and to random test generation techniques, demonstrating the advantages of the proposed hierarchical approach.     

时序电路的模糊化测试生成算法

文章提出的模糊化的时序电路测试生成算法不明确指定故障点的故障值，它将故障值模糊化，并以符号表示。本算法第一阶段通过计算状态线和原始输出端的故障值来寻找测试矢量，通过计算故障点的正常值来 寻找测试矢量对应的故障类型；第二阶段用故障点的正常值作为约束条件计算故障点的另一个测试矢量。与传统的算法不同，它不需要回退和传播的过程。实验结果表明本算法具有较高的故障覆盖率和较少的测试时间。     

On the generation of test patterns for multiple faults

This article presents a new method to generate test patterns for multiple stuck-at faults in combinational circuits. We assume the presence of all multiple faults of all multiplicities and we do not resort to their explicit enumeration: the target fault is a single component of possibly several multiple faults. New line and gate models are introduced to handle multiple fault effect propagation through the circuits. The method tries to generate test conditions that propagate the effect of the target fault to primary outputs. When these conditions are fulfilled, the input vector is a test for the target fault and it is guaranteed that all multiple faults of all multiplicities containing the target fault as component are also detected. The method uses similar techniques to those in FAN and SOCRATES algorithms to guide the search part of the algorithm, and includes several new heuristics to enhance the performance and fault detection capability. Experiments performed on the ISCAS'85 benchmark circuits show that test sets for multiple faults can be generated with high fault coverage and a reasonable increase in cost over test generation for single stuck-at faults.     

A novel automatic test pattern generator for asynchronous sequential digital circuits

A novel automatic test pattern generator (ATPG) for stuck-at faults of asynchronous sequential digital circuits is presented. The developed ATPG does not require support by any design-for-testability method nor external software tool. The shortest test sequence generation is guaranteed by breadth-first search. The contribution is unique hazard identification before the test generation process, state justification on the gate level, sequential fault propagation based on breadth-first search and stepwise composition of state graphs for sequential test generation. A new six-valued logic together with a new algorithm was developed for hazardous transition identification. The internal combinational ATPG allows to generate test patterns one by one and only if it is required by sequential test generation. The developed and implemented ATPG was tested with speed-independent and quasi-delay-insensitive benchmark circuits.     

采用基本门单元完全测试矢量的测试生成算法

文章介绍了一种采用基本逻辑门单元的安全测试矢量集生成测试矢量的方法，该方法可以将搜索空间限制在2(n 1）种组合内。它采用故障支配和故障等效的故障传播、回退等技术，建立了一套从局部到全局的测试生成新方法。同时，利用基本门单元安全测试矢量的规律性，可以实现最小的内存容量要求。在一些基准电路的应用实例中，得到了满意的结果。     

One-stage one-sided rearrangeable switching networks

Switching networks consisting of subscriber lines and crosswires connected by switches are considered. A connection between two subscribers is made along one crosswire via two switches. The minimum number of switches necessary for such a switching network to be rearrangeably nonblocking is determined and a switching arrangement which achieves this minimum for any (even) number of subscriber lines is constructed. Two procedures for assignment of crosswires to subscriber line pairs are described. One makes the correct choice of connection route without backtracking provided all connections are known beforehand; the other determines a rearrangement of existing assignments when a new connection is required. The switching networks which have the minimum number of switches for networks with up to eight subscriber lines and give nonisomorphic solutions for larger networks are characterized     

Guaranteed fault detection sequences for single transition faults in finite state machine models using concurrent fault simulation

This paper presents a new algorithm for the generation of test sequences for finite state machines. Test sequence generation is based on the transition fault model, and the generation of state-pair distinguishing sequences. We show that the use of state-pair distinguishing sequences generated from a fault-free finite state machine will remain a distinguishing sequence even in the presence of a single transition fault, thus guaranteeing complete single transition fault coverage. Analysis and experimental results show that the complexity of the test sequence generation algorithm is less than those of the previous algorithms. The utility of the transition fault model, and the generated test sequences is shown by their application to sequential logic circuits. These results show more than a factor of 10 improvement in the test generation time and some reduction in test length while maintaining 100% transition fault coverage.Now with Intel Corporation, FM5-161, 1900 Prairie City Road, Folsom, CA 95630.Now with Chrysalis Symbolic Design, 101 Billerica Ave., North Billerica, MA 01862.     

A new fault independent test generation algorithm for combinational logic circuits

In order to improve the performance of fault independent test generation algorithms, two strategies are proposed: a critical lines maximization strategy (CLM) and a critical primary inputs flipping strategy (CPF). CLM is used to maximize the number of detected faults while generating a test pattern. CPF is used to derive new test pattern(s) from a generated test pattern with little additional effort. A new fault independent test generation algorithm (MAX) based on these strategies is introduced and illustrated.     

网格中基于最小连接块的启发式容错路由算法

矩形无效块模型可以用来解决网格下的容错路由问题,最小连接块(MCC)模型是它的一个改良模型.本文在MCC基础上,建立MCC 重叠图,当发现不存在曼哈顿路径的时候,给出一套算法,来计算出一条避免无效块的尽可能短的路径.模拟试验表明,通过这种算法找到的路径,与最短路径相差很小.比起花费更多的时间去找寻最短路径,这种启发式容错算法无疑是更好的选择.     

基于指定元分析的多级相对微小故障诊断方法

 设备运作过程中可能出现的微小故障,往往会因其呈现的异常征兆较小而被淹没在显著故障或噪声中,从而现有的方法难以很好地对其进行监控.本文在DCA空间投影框架下建立了观测空间的多级分解思想,并在此基础上提出一种多级相对微小故障诊断算法.将观测数据关于显著指定模式进行DCA分析,并移除显著变化模式的影响,以提高微小故障信号的信噪比.根据其向故障子空间投影能量的显著性判断残差数据中是否还包含仍未被诊断出、且具有一定影响的微小故障;根据各故障方向上投影能量的显著性进行微小故障诊断;重复以上过程,直到各级微小故障均被诊断出来.包含四种共存故障的观测数据的仿真研究,验证了该算法的有效性.     

An Effective Test and Diagnosis Algorithm for Dual‐Port Memories

This paper proposes a test algorithm that can detect and diagnose all the faults occurring in dual‐port memories that can be accessed simultaneously through two ports. In this paper, we develop a new diagnosis algorithm that classifies faults in detail when they are detected while the test process is being developed. The algorithm is particularly efficient because it uses information that can be obtained by test results as well as results using an additional diagnosis pattern. The algorithm can also diagnose various fault models for dual‐port memories.     

Fault diagnosis algorithm based on switching function for boost converters

A fault diagnosis algorithm, which is necessary for constructing a reliable power conversion system, should detect fault occurrences as soon as possible to protect the entire system from fatal damages resulting from system malfunction. In this paper, a fault diagnosis algorithm is proposed to detect open- and short-circuit faults that occur in a boost converter switch. The inductor voltage is abnormally kept at a positive DC value during a short-circuit fault in the switch or at a negative DC value during an open-circuit fault condition until the inductor current becomes zero. By employing these abnormal properties during faulty conditions, the inductor voltage is compared with the switching function to detect each fault type by generating fault alarms when a fault occurs. As a result, from the fault alarm, a decision is made in response to the fault occurrence and the fault type in less than two switching time periods using the proposed algorithm constructed in analogue circuits. In addition, the proposed algorithm has good resistivity to discontinuous current-mode operation. As a result, this algorithm features the advantages of low cost and simplicity because of its simple analogue circuit configuration.     

基于子空间投影的复杂水下环境运动小目标检测前跟踪方法

针对复杂水下环境运动小目标检测中存在的目标信号强度弱、信杂比低等问题,该文提出基于子空间投影的检测前跟踪(TBD)算法:对原始图像数据截取序列片段,将3维时空片段中的短时运动航迹投影到2维子空间平面;利用2维投影图中平面航迹的形态特征进行初步筛选,提取目标的有效运动区域;将2维平面中的目标短时航迹在局部区域重建3维时序,在3维航迹回溯过程中利用目标运动特征再次筛选目标短时航迹。通过上述分级检测机制,可实现快速高精度的目标短时航迹检测。结合前景检测以及基于层次凝聚聚类(HAC)的长时航迹检测算法,构建了针对运动小目标的完整检测前跟踪方法。最后使用实测声呐图像数据验证了算法的检测精度和检测速度。     

Generation and Verification of Tests for Analog Circuits Subject to Process Parameter Deviations

The paper presents a test stimulus generation and fault simulation methodology for the detection of catastrophic faults in analog circuits. The test methodology chosen for evaluation is RMS AC supply current monitoring. Tests are generated and evaluated taking account of the potential fault masking effects of process spread on the faulty circuit responses. A new test effectiveness metric of probability of detection is defined and the application of the technique to an analog multiplier circuit is presented. The fault coverage figures are therefore more meaningful than those obtained with a fixed threshold.     

基于相似度的双搜索多目标识别算法

在分析远距离多目标特性的基础上，提出了一种基于相似度的粗精双搜索多目标识别算法。在粗搜索阶段，首先利用圆形形态学模板在滤波后的二值化图像中快速搜索候选目标，再利用“距离相似度”原则进行候选目标的聚类分析，以同一目标内各候选目标点的形心位置作为局部熵处理区域中心。在精搜索阶段，以最大熵值点为种子点进行目标区域生长。为了减少运算量，提高实时性，还采用基于熵相似度、简单连接法与子区合并法相结合的改进型区域生长法，重构单个目标。仿真结果表明该算法可快速、准确地实现对5个目标的识别。     

基于穷举和回溯的自反馈测试生成算法的实现

提出了一种基于穷举和回溯的自反馈测试生成算法,并在Xilinx Virtex-ⅡPro开发环境下实现了测试生成算法.穷举和回溯算法用软件设计实现.算法中状态矩阵的计算和检测用硬件设计实现.系统的整体设计在型号为XC2VP30的实验板上进行了验证.