On the design of random pattern testable PLA based on weighted random pattern testing

Programmable Logic Arrays (PLAs) provide a cost effective method to realize combinational logic circuits. PLAs are often not suitable for random pattern testing due to high fao-in of gates. In order to reduce the effective fan-in of gates, previous random pattern testable (RPT) PLA designs focused on partitioning inputs and product lines. In this paper we propose a new random pattern testable design of PLAs which is suitable for built-in selftest. The key idea of the proposed design is to apply weighted random patterns to the PLA under test. The proposed design method was applied to 30 example PLAs. The performance of the RPT PLAs was measured in the size of test set, area overhead, and time overhead, and compared with two other designs in test length and fault coverage. The experimental results show that the proposed design achieve short test length and high fault coverage.     

Fault detection in programmable logic arrays

When designing fault-tolerant systems including programmable logic arrays (PLAs), the various aspects of these circuits concerning fault diagnosis have to be taken into account. The peculiarity of these aspects, ranging from fault models to test generation algorithms and to self-checking structures, is due to the regularity of PLAs. The fault model generally accepted for PLAs is the crosspoint defect; it is employed by dedicated test generation algorithms, based on the fact that PLAs implement a two-level combinational function. The problem of accessing inputs and outputs of the PLA can be alleviated by augmenting the PLA itself so as to simplify the test vectors to be applied, making them function independent in the limit. A further step consists in the addition of the circuitry required to generate test vectors and to evaluate the answer, thus obtaining a built-in self-test (BIST) architecture. Finally, high reliability can be achieved with PLAs featuring concurrent error detection.     

Fault-based ATPG for linear analog circuits with minimal size multifrequency test sets

An automatic test pattern generation (ATPG) procedure for linear analog circuits is presented in this work. A fault-based multifrequency test approach is considered. The procedure selects a minimal set of test measures and generates the minimal set of frequency tests which guarantee maximum fault coverage and, if required, maximal fault diagnosis, of circuit AC hard/soft faults. The procedure is most suitable for linear time-invariant circuits which present significant frequency-dependent fault effects.For test generation, the approach is applicable once parametric tests have determined DC behaviour. The advantage of this procedure with respect to previous works is that it guarantees a minimal size test set. For fault diagnosis, a fault dictionary containing a signature of the effects of each fault in the frequency domain is used. Fault location and fault identification can be achieved without the need of analog test points, and just in-circuit checkers with an observable go/no-go digital output are required for diagnosis.The procedure is exemplified for the case of an analog biquadratic filter. Three different self-test approaches for this circuit are considered. For each self-test strategy, a set of several test measures is possible. The procedure selects, in each case, the minimal set of test measures and the minimal set of frequency tests which guarantee maximum fault coverage and maximal diagnosis. With this, the self-test approaches are compared in terms of the fault coverage and the fault diagnosability achieved.This work is part of AMATIST ESPRIT-III Basic Research Project, funded by CEC under contract #8820.     

基于扫描链结构重组的低功耗BIST方案

设计了一种改进扫描链结构的内建自测试(BIST)方案.该方案将设计测试序列发生器(TPG)中合适的n状态平滑器与扫描链的重新排序结合起来,从而达到低功耗测试且不致丢失故障覆盖率的目的.通过对15位随机序列信号的测试,发现此TPG中的n状态平滑器在降低功耗的同时还减小了故障覆盖率,遂又设计了重组扫描链的结构来解决这一问题.实验结果表明,该设计方案对于降低平均测试功耗和提高故障覆盖率都具有显著的效果.     

A BIST TPG for Low Power Dissipation and High Fault Coverage

This paper presents a low hardware overhead test pattern generator (TPG) for scan-based built-in self-test (BIST) that can reduce switching activity in circuits under test (CUTs) during BIST and also achieve very high fault coverage with reasonable lengths of test sequences. The proposed BIST TPG decreases transitions that occur at scan inputs during scan shift operations and hence reduces switching activity in the CUT. The proposed BIST is comprised of two TPGs: LT-RTPG and 3-weight WRBIST. Test patterns generated by the LT-RTPG detect easy-to-detect faults and test patterns generated by the 3-weight WRBIST detect faults that remain undetected after LT-RTPG patterns are applied. The proposed BIST TPG does not require modification of mission logics, which can lead to performance degradation. Experimental results for ISCAS'89 benchmark circuits demonstrate that the proposed BIST can significantly reduce switching activity during BIST while achieving 100% fault coverage for all ISCAS'89 benchmark circuits. Larger reduction in switching activity is achieved in large circuits. Experimental results also show that the proposed BIST can be implemented with low area overhead.     

Self-Test Techniques for Crypto-Devices

This paper describes a generic built-in self-test strategy for devices implementing symmetric encryption algorithms. Taking advantage of the inner iterative structures of crypto-cores, test facilities are easily set-up for circular self-test of the crypto-cores, built-in pseudorandom test generation and response analysis for other cores in the host device. Main advantages of the proposed test implementation are an architecture with no visible scan chain, 100% fault coverage on crypto-cores with negligible area overhead, availability of pseudorandom test sources, and very low aliasing response compaction for other cores.      

An effective logic BIST scheme based on LFSR-reseeding and TVAC

An effective logic built-in self-test scheme aiming at reducing the area overhead of IC testing and improving the fault average is proposed, which combines strategies of linear feedback shift register (LFSR)-reseeding with test vectors applied by circuit-under-test itself (TVAC). LFSR-reseeding technology is first applied to decrease the size of test set and the number of interior feedback wires, while TVAC technology is applied to decrease the number of stored seeds. An efficient LFSR-reseeding algorithm and a modified quick judgment method for path search are proposed. Experimental results for ISCAS 85 benchmarks demonstrate that the proposed method reduces the number of interior feedback wires more than 50% on average and can achieve full fault coverage with much less groups as well as area overhead compared with previous TVACs.     

Synthesis of Native Mode Self-Test Programs

Recent studies show that at-speed functional tests are better for finding realistic defects than tests executed at lower speeds. This advantage has led to growing interest in design for at-speed tests. In addition, time-to-market requirements dictate development of tests early in the design process. In this paper, we present a new methodology for synthesis of at-speed self-test programs for microprocessors. Based on information about the instruction set, this high-level test generation methodology can generate instruction sequences that exercise all the functional capabilities of complex processors. Modern processors have large memory modules, register files and powerful ALUs with comprehensive operations, which can be used to generate and control built-in tests and to evaluate the response of the tests. Our method exploits the functional units to compress and check the test response at chip internal speeds. No hardware test pattern generators or signature analyzers are needed, and the method reduces area overhead and performance impact as compared to current BIST techniques. A novel test instruction insertion technique is introduced to activate the control/status inputs and internal modules related to them. The new methodology has been applied to an example processor much more complex than any benchmark circuit used in academia today. The results show that our approach is very effective in achieving high fault coverage and automation in at-speed self-test generation for microprocessor-like circuits.     

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.     

Dynamic X-filling for Peak Capture Power Reduction for Compact Test Sets

Excessive test power consumption is one of the obstacles which the chip industry currently faces. Peak capture power reduction typically leads to high pattern counts which increase test costs. This paper proposes a new methodology to reduce peak capture power during at-speed scan testing. In this method, a novel dynamic X-filling technique Opt-Justification-fill which uses optimization techniques to compute promising X-bits for low-power filling is proposed. This method is tightly integrated into a dynamic compaction flow to create silent test cubes with high compaction ability. By this, X-filling for fault detection and reducing switching activity is balanced. The proposed methodology can be applied during initial compact test set generation as well as during a post-ATPG stage for a previously generated test set to reduce switching activity. Experiments show a significant reduction of peak capture power. At the same time, the pattern count increase is only small which leads to reduced test costs.     

BIST Pattern Generators Using Addition and Subtraction Operations

Configurations of adders, subtracters, or arithmetic logic units andregisters, which are available in many data paths, can be utilized togenerate patterns and to compact test responses. This paper analyzesthe pattern sequences generated by configurations with differenttypes of adders and subtracters. For many different seeds andconstant input values, these pattern generators can produce asequence of all possible patterns. Moreover, k-bit patterngenerators that take into account the overflow or underflow bit cangenerate bit sequences that all have period 2 ^k -1. Thus, theperiodicity of these pattern generators is the same as that of a k-bit linear feedback shift register with a primitivecharacteristic polynomial. Experimental results show that theproduced pattern sequences achieve similar fault coverage aspseudorandom sequences and require about the same testlength. Compared to the well-known self-test methods that insert testregisters, the approach using available arithmetic units saves theadditional gates that are needed to implement test registers, and itavoids performance degradation due to additional delays.     

一种片上网络路由测试方法研究

对片上网络路由器的结构进行了分析,建立了相应的故障模型.针对此故障模型结合内建自测试,提出了一种基于量子遗传算法的测试矢量传递路径寻优方法.该算法具有收敛速度快,精度高等优点.最后通过对测试故障覆盖率和测试时间进行分析表明这种测试方法具有较高的故障覆盖率、较少的测试时间.     

Techniques for estimating test length under random test

When a circuit is tested using random or pseudorandom patterns, it is essential to determine the amount of time (test length) required to test it adequately. We present a methodology for predicting different statistics of random pattern test length. While earlier methods allowed estimation only of upper bounds of test length and only for exhaustive fault coverage, the technique presented here is capable of providing estimates of all statistics of interest (including expected value and variance) for all coverage specifications.Our methodology is based on sampling models developed for fault coverage estimation [1]. Test length is viewed as awaiting time on fault coverage. Based on this relation we derive the distribution of test length as a function of fault coverage. Methods of approximating expected value and variance of test length are presented. Accuracy of these approximations can be controlled by the user. A practical technique for predicting expected test length is developed. This technique is based on clustering faults into equal detectability subsets. A simple and effective algorithm for fault clustering is also presented. The sampling model is applied to each cluster independently and the results are then aggregated to yield test lengths for the whole circuit. Results of experiments with several circuits (both ISCAS '85 benchmarks and other practical circuits) are also provided.This work was done while the author was with the Department of Electrical Engineering, Southern Illinois University, Carbondale, IL 62901.     

Observation-Oriented ATPG and Scan Chain Disabling for Capture Power Reduction

Eliminating the excessive test power for integrated circuits is a strict challenge within the nanometer era. This method combines test pattern generation with the scan chain disabling technique to achieve low capture power testing under the single stuck-at fault model. Testability analysis is exploited to assist in the test pattern generation process to generate the observation-oriented test patterns. In order to direct fault effects to the frequently-used circuit outputs, unbalanced observability costs are purposely assigned to circuit outputs to introduce unequal propagation probability. Observation-aware scan chain clustering is then performed through a weighted compatibility analysis to densely cluster the frequently-used scan cells into scan chains. Consequently, more scan chains can be disabled in the capture cycle and significant power reduction can be achieved without affecting the fault coverage. To simultaneously consider the reduction in large test data volume and capture power, the power-aware test vector compaction algorithm is also performed. Experimental results for the large ISCAS’89 benchmark circuits show that significant improvements can be simultaneously achieved including 71.7 % of capture power reduction, 43.7 % of total power reduction, 24.3 % of peak power reduction and 98.0 % of test data compaction ratios averagely. Results for three large ITC’99 benchmark circuits also demonstrate the effectiveness of the proposed method for the practical-scale circuits.     

On-chip signature analyser for analogue circuit testing

The authors propose a technique for on-chip analogue response compaction to implement self-test capabilities in analogue circuits. The integration function is identified as a powerful analogue compression scheme and op-amp-based implementations are proposed for both single and multiple-input analysers. Validations show that an improved fault coverage can be achieved     

A synthesis-based test generation and compaction algorithm for multifaults

Because of its inherent complexity, the problem of automatic test pattern generation for multiple stuck-at faults (multifaults) has been largely ignored. Recently, the observation that multifault testability is retained by algebraic factorization demonstrated that single fault (and therefore multifault) vector sets for two-level circuits could give complete multifault coverage for multilevel circuits constructed by algebraic factorization. Unfortunately, in using this method the vector set size can be much larger than what is really required to achieve multifault coverage, and the approach has some limitations in its applicability.In this article we first present a multifault test generation and compaction strategy for algebraically factored multilevel circuits, synthesized from two-level representations. We give a basic sufficiency condition for multifault testability of such networks.We next focus on the relationship between hazard-free robust path-delay-fault testability and multifault testability. We show that the former implies the latter for arbitrary multilevel circuits. This allows the use of previously developed composition rules that maintain path-delay-fault testability for the synthesis of multifault testable circuits.We identify a class of multiplexor-based networks and prove an interesting property of such networks—if the networks are fully single stuck-at fault testable, or made fully single stuck-at fault testable, they are completely multifault testable. We give a multifault test generation and compaction algorithm for such networks.We provide experimental results which indicate that a compacted multifault test set derived using the above strategies can be significantly smaller than the test set derived using previously proposed procedures. These results also indicate the substantially wider applicability of our procedures, as compared to previous techniques.     

循环移位可编程序逻辑阵列的可测试性设计

本文研究了一种“芯片内部自测式”可编程序逻辑阵列(Built-in Sclf Tcst PLA)的设计方法:循环移位PLA(简称CS-PLA)法.CS-PLA与其他PLA可测试性设计方法相比,具有故障覆盖率高、对电路速度影响小、测试生成简单等特点,当PLA嵌入在芯片内部时,不需要单独的测试状态。其芯片面积成本随PLA的规模增大而降低,因此CS-PLA特别适用于大规模“嵌入式”PLA.     

Test Set and Fault Partitioning Techniques for Static Test Sequence Compaction for Sequential Circuits

We propose a new static test set compaction method based on a careful examination of attributes of fault coverage curves. Our method is based on two key ideas: (1) fault-list and test-set partitioning, and (2) vector re-ordering. Typically, the first few vectors of a test set detect a large number of faults. The remaining vectors usually constitute a large fraction of the test set, but these vectors are included to detect relatively few hard faults. We show that significant compaction can still be achieved by partitioning faults into hard and easy faults, and compaction is performed only for the hard faults. This significantly reduces the computational cost for static test set compaction without affecting quality of compaction. The second key idea re-orders vectors in a test set by moving sequences that detect hard faults to the beginning of the test set. Fault simulation of the newly concatenated re-ordered test set results in the omission of several vectors so that the compact test set is smaller than the original test set. Experiments on several ISCAS 89 sequential benchmark circuits and large production circuits show that our compaction procedure yields significant test set reductions in low execution times.     

Efficient Concurrent Self-Test with Partially Specified Patterns

Structural on-line self-test may be performed to detect permanent faults and avoid their accumulation in the system. This paper improves existing techniques for concurrent BIST that are based on a deterministic test set. Here, the test patterns are specially generated with a small number of specified bits. This results in very low test length and fault detection latency, which allows to frequently test critical faults. As a consequence, the likelihood of fault accumulation is reduced. Experiments with benchmark circuits show that the hardware overhead is significantly lower than the overhead of the state of the art. Moreover, a case-study on a super-scalar RISC processor demonstrates the feasibility of the method.     

A Ring Architecture Strategy for BIST Test Pattern Generation

This paper presents a new effective Built-In Self Test (BIST) scheme that achieves 100% fault coverage with low area overhead, and without any modification of the circuit under test (CUT), i.e., no test point insertion. The set of patterns generated by a pseudo-random pattern generator, e.g. a Linear Feedback Shift Register (LFSR), is transformed into a new set of patterns that provides the desired fault coverage. To transform these patterns, a ring architecture composed by a set of masks is used. During on-chip test pattern generation, each mask is successively selected to map the original pattern sequence into a new test sequence. We describe an efficient algorithm that constructs a ring of masks from the test cubes provided by an automatic test pattern generator (ATPG) tool. Moreover, we show that rings of masks are implemented very easily at low silicon area cost, without requiring any logic synthesis tool; a combinational mapping logic corresponding to the masks is placed between the LFSR and the CUT, together with a looped shift register that acts as a mask selecting circuit. Experimental results are given at the end of the paper, demonstrating the effectiveness of the proposed approach in terms of area overhead, fault coverage and test sequence length. Note that this paper is an extended version of [1].