A novel approach to automatic generation of diagnostic memory tests based on fault decomposition and output tracing is described. Fault decomposition allows fault models that precisely describe the fault effects of a specific technology to be considered during test generation; therefore, overtesting of the memory-under-test is avoided. Output tracing of failing memory cells allows for distinguishing of all memory faults of the fault model. An extended greedy-based set-cover algorithm is utilized to generate the march tests that detect all basic fault effects and distinguish among them. The effectiveness of the generated tests is verified using simulation. Test generation time is on the order of a few seconds, while the lengths of the generated tests are only 1N to 3N higher than those of known optimal tests for the same fault models.

Systems-on-Chips often contain a large amount of embedded memory. In order to obtain sufficiently high yield, efficient diagnosis and repair facilities are needed for the memories. A novel and efficient approach for collecting complete failure data during on-chip memory testing is proposed that can be combined with a row/column reconfiguration algorithm for complete on-chip memory repair. A sequence of diagnostic tests of linear order is utilized that detects and localizes all cells involved in single-cell faults and two-cell coupling faults, such as idempotent coupling faults, and provides this information to on-chip circuitry for memory repair. Failure data are collected at the operating speed of the memory-under-test so that tests can be applied at speed. The data acquisition circuitry evaluates the test results and classifies faults as column failures, coupling faults, or single-cell faults for near-optimal allocation of spare resources. The proposed test and data acquisition algorithm can be realized as compact Built-In Self-Test (BIST) circuitry using standard design libraries.

We present a new clock-control DFT technique for sequential circuits, based on clock partitioning and selective clock freezing, and we use it to break the global feedback loops and to generate clock waves to test the resulting sequential circuit with self-loops. Clock waves allow us to significantly reduce the complexity of sequential ATPG. Unlike scan, our non-intrusive DFT technique does not introduce any delay penalty; the generated tests may be applied at speed, have shorter application time, and dissipate less power.

In order to reduce the time-to-market and simplify gate-level test generation for digital integrated circuits, GA-based functional test generation techniques are proposed for behavioral and register transfer level designs. The functional tests generated can be used for design verification, and they can also be reused at lower levels (i.e. register transfer and logic gate levels) for testability analysis and development. Experimental results demonstrate the effectiveness of the method in reducing the overall test generation time and increasing the gate-level fault coverage.

Biased random instruction generators are commonly used in architectural verification of microprocessors, with biases specified manually by designers. As the complexity of processors grows, so does the complexity of specifying biases. Automatic bias generation speeds up the verification flow and may lead to better coverage of potential design errors. In this work, we present a genetic algorithm based framework to automatically generate biases. We target utilization of specific buffers for a new version of the PowerPC architecture. Our results show that the GA is effective in achieving high buffer utilization. Also, in targeting multiple objectives, the best approach to use depends on whether the objectives are related.

We present a new approach to built-in self-test (BIST) for logic circuits that achieves comparable fault coverages to scan BIST with less hardware overhead and no impact on performance. We combine clock partitioning to create independent clocks with a selective freezing of clock signals to form various pipeline configurations during testing. Since no scan operations are performed, tests can be applied at the operational speed of the circuit. Experimental results are presented for several benchmark circuits to demonstrate the effectiveness of the approach.

A new approach to automatically generating diagnostic memory tests of linear order (/spl Oscr/(N)) is presented. The resulting March tests provide complete detection and distinguishing of all single-cell and two-cell fault models. The approach is based on state transition graph modelling, decomposition of functional memory faults into basic fault effects, and output tracing. For each of the targeted basic fault effects, all possible March sequences are generated. A fast greedy-based algorithm is then used to compose diagnostic March tests from the set of March sequences. The proposed test generation algorithm was implemented in C. The results show that automatic generation can compete with hand-optimization of diagnostic March tests.

This article describes a diagnostic fault simulator for stuck-at faults in sequential circuits that is both time and space efficient. The simulator represents indistinguishable classes of faults as memory efficient lists. The use of lists reduces the number of output response comparisons between faults and hence speeds up the simulation process. The lists also make it easy to drop faults when they are fully distinguished from other faults. Experimental results on the ISCAS89 circuits show that the simulator runs significantly faster than an earlier work based on distinguishability matrices, and for large circuits is faster and more memory efficient than a recent method based on lists of indistinguishable faults. The paper provides the first reports on pessimistic and optimistic diagnostic measures for all faults of the large ISCAS circuits with known deterministic tests. The diagnostic fault simulator has also been modified to diagnose defects, given the output responses of failing devices. Results on simulated bridging defects show that the diagnosis time is comparable to the time for fault simulation with fault dropping.

The increasing use of large embedded memories in systems-on-chips requires automatic memory reconfiguration to avoid the need for external accessibility. In this work, effective diagnostic memory tests of linear order O(N) are proposed that enable memory reconfiguration, and their diagnostic capabilities are analyzed. In particular, these tests allow single-cell faults to be distinguished from multiple-cell faults, such as coupling faults. In contrast to conventional O(N) tests, all cells involved in a fault are detected and localized, which allows complete reconfiguration using minimal-area BIST hardware that compares favorably with other BIST designs.

Efficient diagnosis of faults in VLSI circuits requires high quality diagnostic test sets. In this work novel techniques for diagnostic test generation are proposed that require significantly less time than previous methods. The set of fault pairs left undistinguished by a detection-oriented test set is first filtered to target only testable faults. Then diagnostic test generation is performed using a genetic algorithm (GA) combined with a diagnostic fault simulator. A new fitness metric is proposed for the GA that accurately measures the quality of candidate sequences while requiring a limited amount of CPU time. Experimental results illustrate the effectiveness of the approach for sequential circuits.

A new diagnostic fault simulator is described that diagnoses both feedback and nonfeedback bridge faults in combinational circuits while using information from fault simulation of single stuck-at faults. A realistic fault model is used which considers the existence of the Byzantine Generals problem. Sets representing nodes possibly involved in a defect are partitioned based on logic and fault simulation of failing vectors. The approach has been demonstrated for two-line bridge faults on several large combinational benchmark circuits containing Boolean primitives and has achieved over 98% accuracy for nonfeedback bridge faults and over 85% accuracy for feedback bridge faults with good diagnostic resolution.

A new method for state justification is proposed for sequential circuit test generation. The linear list of states dynamically obtained during the derivation of test vectors is used to guide the search during state justification. State-transfer sequences that drive the circuit from the current state to the target state may already be known. Otherwise, genetic engineering of existing state-transfer sequences is required. In both cases, genetic-algorithm-based techniques are used to generate valid state justification sequences for the circuit in the presence of the target fault. This approach achieves extremely high fault coverages, and thus outperforms previous deterministic and simulation-based techniques.

New measures of peak power are proposed in the context of sequential circuits, and an efficient automatic procedure is presented to obtain very good lower bounds on these measures, as well as providing the actual input vectors that attain such bounds. Automatic generation of a functional vector loop for near-worst case power consumption is also attained. Experiments show that vector sequences generated give much more accurate estimates of peak power dissipation and are generated in significantly shorter execution times than estimates made from randomly generated sequences for four delay models.

Test application time is an important factor in the overall cost of VLSI chip testing. We present a new ATPG approach for generating compact test sequences for sequential circuits. Our approach combines a conventional ATPG algorithm, a technique based on the frozen clock testing strategy, and a dynamic compaction method based on a genetic algorithm. The frozen clock strategy temporarily suspends the sequential behavior of the circuit by stopping its clock and applying several vectors to increase the number of faults detected without changing the circuit state. Results show that test sets generated using the new approach are more compact than those generated by previous approaches for many circuits.

A new fault list reduction approach is proposed for use in the first stage of a two-stage bridge fault diagnosis procedure. Modified structural analysis and layout extraction procedures are performed to obtain a reduced realistic bridge fault list that can be used in the second stage, which employs diagnostic fault simulation. The fault list reduction approach can reduce the final candidate bridge fault list by 92% to 99% compared with the diagnosis results achieved by the diagnostic fault simulator alone.

Two fast algorithms for static test sequence compaction are proposed for sequential circuits. The algorithms are based on the observation that test sequences traverse through a small set of states and some states are frequently revisited throughout the application of a test set. Subsequences that start and end on the same states may be removed if necessary and if sufficient conditions are met for them. Contrary to the previously proposed methods, where multitudes of fault simulations are required, the techniques described in this paper require only two fault simulation passes and are applied to test sequences generated by various test generators, resulting in significant compactions very quickly for circuits that have many revisited states.

Dynamic test sequence compaction is an effective means of reducing test application time and often results in higher fault coverages and reduced test generation time as well. Three simulation-based techniques for dynamic compaction of test sequences are described. The first technique uses a fault simulator to remove test vectors from the test sequence generated by a test generator if the vectors are not needed to detect the target fault, considering that the circuit state may be known. The second technique uses genetic algorithms to fill the unspecified bits in a partially-specified test sequence in order to increase the number of faults detected by the sequence. The third technique uses test sequences provided by the test generator as seeds in a genetic algorithm, and better sequences are evolved that detect more faults. Significant improvements in test set size, fault coverage, and test generation time have been obtained over previous approaches using combinations of the three techniques.

A new approach for sequential circuit test generation is proposed that combines software based testing techniques at the high level with test enhancement techniques at the gate level. Several sequences are derived to ensure 100% coverage of all statements in a high-level VHDL description, or to maximize coverage of paths. The sequences are then enhanced at the gate level to maximize coverage of single stuck-at faults. High fault coverages have been achieved very quickly on several benchmark circuits using this approach.

This paper proposes a method to enhance topological ATPG algorithms by exploiting some information computed through symbolic techniques. Since symbolic techniques can only be applied to small circuits, suitable circuit portions (named macros) are first selected, and then symbolic techniques are used to analyze their state graphs. The topological ATPG algorithm benefits from this analysis to bound its search tree. Experimental results show that the proposed approach is effective in reducing the required CPU time and increasing both the Fault Coverage and the Fault Efficiency. When high-level information about the circuit behavior and structure is available, it can be fruitfully exploited for macro selection.

New methods for fault-effect propagation and state justification that use finite-state-machine sequences are proposed for sequential circuit test generation. Distinguishing sequences are used to propagate the fault effects from the flip-flops to the primary outputs by distinguishing the faulty machine state from the fault-free machine state. Set, clear, and pseudoregister justification sequences are used for state justification via a combination of partial state justification solutions. Reengineering of existing finite-state machine sequences may be needed for specific target faults. Moreover, conflicts imposed by the use of multiple sequences may need to be resolved. Genetic-algorithm-based techniques are used to perform these tasks. Very high fault coverages have been obtained as a result of this technique.

Previous work has shown that maximum switching density at a given node is extremely sensitive to a slight change in the delay at that node. However, when estimating the peak power for the entire circuit, the powers estimated must not be as sensitive to a slight variation or inaccuracy in the assumed gate delays because computing the exact gate delays for every gate in the circuit during simulation is expensive. Thus, we would like to use the simplest delay model possible to reduce the execution time for estimating power, while making sure that it provides an accurate estimate, i.e., that the peak powers estimated will not vary due to a variation in the gate delays. Results for four delay models are reported for the ISCAS85 combinational benchmark circuits, ISCAS89 sequential benchmark circuits, and several synthesized circuits.

New measures of peak power in the context of sequential circuits are proposed.This paper presents an automatic procedure to obtain very good lower bounds on these measures as well as the actual input vectors that attain such bounds.The initial state of the circuit is an important factor in determining the amount of switching activity in sequential circuits and is taken into account.A peak power estimator tool K2 was developed using genetic techniques.Experiments show that vector sequences generated by K.2 give much more accurate estimates for peak power dissipation than the estimates made from randomly generated sequences.

Dynamic test sequence compaction is an effective means of reducing test application time and often results in higher fault coverages and reduced test generation time as well. A new algorithm for dynamic test sequence compaction is presented that uses genetic techniques to evolve test sequences. Test sequences provided by a test generator and previously evolved sequences already included in the test set are used as seeds in the genetic population. Significant improvements in test set size, fault coverage, and test generation time have been obtained over previous approaches.

Two fast algorithms for static test sequence compaction are proposed for sequential circuits. The algorithms are based on the observation that test sequences traverse through a small set of states, and some states are frequently re-visited throughout the application of a test set. Subsequences that start and end on the same states may be removed if necessary and sufficient conditions are met for them. The techniques require only two fault simulation passes and are applied to test sequences generated by various test generators, resulting in significant compactions very quickly for circuits that have many revisited states.

We propose three synchronous parallel algorithms for scalable parallel test set partitioned fault simulation. The algorithms are based on a new two-stage approach to parallelizing fault simulation for sequential VLSI circuits in which the test set is partitioned among the available processors, The test set partitioning inherent in the algorithms overcomes the good circuit logic simulation bottleneck that exists in traditional fault partitioned approaches to parallel fault simulation. The implementations were done on a shared memory multiprocessor and on a network of workstations. Two of the algorithms show a small degree of pessimism in a few cases, with respect to the fault coverage as compared with a uniprocessor run, while the third algorithm provides the same results as in a uniprocessor run. All algorithms provide excellent speedups and perform much better than a traditional fault partitioned approach, on both shared and distributed memory parallel platforms.

This paper presents a new static logic implication algorithm. An improved implication procedure that fully takes advantage of the special context of static implication, the iterative method, and set algebra is described. The algorithm discovers at low cost many indirect implications which are not discovered by dynamic learning without tremendous time cost. The experimental results show that a very large number of indirect implications are found by our algorithm. The static implication procedure has many useful applications, one of which is static redundancy identification. Use of the static implications obtained from the algorithm in static redundancy identification for ISCAS85 combinational circuits resulted in a larger number of redundant faults identified than in previous methods.

Test generation using deterministic fault-oriented algorithms is highly complex and time consuming. New approaches are needed to augment the existing techniques, both to reduce execution time and to improve fault coverage. Genetic algorithms (GA's) have been effective in solving many search and optimization problems. Since test generation is a search process over a large vector space, it is an ideal candidate for GA's. In this work, we describe a GA framework for sequential circuit test generation. The GA evolves candidate test vectors and sequences, using a fault simulator to compute the fitness of each candidate test. Various GA parameters are studied, including alphabet size, fitness function, generation gap, population size, and mutation rate, as well as selection and crossover schemes. High fault coverages were obtained for most of the ISCAS'89 sequential benchmark circuits, and execution times were significantly lower than in a deterministic test generator in most cases.

In this study, we present a controllability measure for high-level circuit descriptions and a high-level synthesis-for-testability technique. Unlike many studies in the area of high-level synthesis for testability that focus on improving the testability of data paths, the objective of our approach is to improve the testability of synthesized circuits by enhancing the controllability of the control flow. Experimental results on several high-level synthesis benchmarks show that when this approach is used prior to logic synthesis, a shorter ATPG time, a smaller test set, and better fault coverage and ATPG efficiency are often achieved. Implementation of this technique requires minimal logic and performance overheads and allows test vectors to be applied at clock-speed.

Simulation-based techniques for dynamic compaction of test sequences are proposed. The first technique uses a fault simulator to remove test vectors from the partially-specified test sequence generated by a deterministic test generator if the vectors are not needed to detect the target fault, considering that the circuit state may be known. The second technique uses genetic algorithms to fill the unspecified bits in the partially-specified test sequence in order to increase the number of faults detected by the sequence. Significant reductions in test set sizes were observed for all benchmark circuits studied. Fault coverages improved for many of the circuits, and execution times often dropped as well, since fewer faults had to be targeted by the computation-intensive deterministic test generator.

During fault simulation, an approximation frequently used in practice is to declare a fault to be detected after it has been potentially detected a predetermined number of times. This approximation may lead to declaring a fault detected when in fact the fault will not be detected during a standard test application process. We propose an alternative measure of fault detection for potentially detected faults, that is easy to compute, yet its accuracy is significantly higher than the measure based on the number of times a fault is potentially detected. Experimental results are shown to support the accuracy of the new measure.

A fault-oriented sequential circuit test generator is described in which various types of distinguishing sequences are derived, both statically and dynamically, to aid the test generation process. A two-phase algorithm is used during test generation. The first phase activates the target fault, and the second phase propagates the fault effects (FE's) from the flip-flops with assistance from the distinguishing sequences. This strategy improves the propagation of FE's to the primary outputs, and the overall fault coverage is greatly increased. In our new test generator, DIGATE, genetic algorithms are used to derive both activating and distinguishing sequences during test generation. Our results show very high fault coverages for the ISCAS89 sequential benchmark circuits and several synthesized circuits.

An efficient automatic test pattern generator for I/sub DDQ/ current testing of CMOS digital circuits is presented. The complete two-line bridging fault set is considered. An adaptive genetic algorithm (GA) is used to generate compact test sets. Experimental results for ISCAS85 and ISCAS89 benchmark circuits are presented. The results show that GA-based test generators are very well suited for generating compact test sets for I/sub DDQ/ testing of bridging faults.

Mixed analog and digital mode simulators have been available for accurate /spl alpha/-particle-induced transient fault simulation. However, they are not fast enough to simulate a large number of transient faults on a relatively large circuit in a reasonable amount of time. In this paper, we describe a gate-level transient fault simulation environment which has been developed based on realistic fault models. Although the environment was developed for /spl alpha/-particle-induced transient faults, the methodology can be used for any transient fault which can be modeled as a transient pulse of some width. The simulation environment uses a gate level timing fault simulator as well as a zero-delay parallel fault simulator. The timing fault simulator uses logic level models of the actual transient fault phenomenon and latch operation to accurately propagate the fault effects to the latch outputs, after which point the zero-delay parallel fault simulator is used to speed up the simulation without any loss in accuracy. The environment is demonstrated on a set of ISCAS-89 sequential benchmark circuits.

Abstract|A hybrid sequential circuit test generator is described which combines deterministic algorithms for fault excitation and propagation with genetic algorithms for state justi cation.Deterministic procedures for state justi cation are used if the genetic approach is unsuccessful, to allow for identi cation of untestable faults and to improve the fault coverage.High fault coverages were obtained for the ISCAS89 benchmark circuits and several additional circuits, and in many cases the results are better than those for purely deterministic approaches.

This paper describes a diagnostic fault simulator for stuck-at faults in sequential circuits that is both time and space efficient. The simulator represents indistinguishable classes of faults as memory efficient lists. The use of lists reduces the number of output response comparisons between faults and hence speeds up the simulation process. The lists also make it easy to drop faults when they are fully distinguished from other faults. Experimental results on the ISCAS89 circuits show that the simulator runs significantly faster than an earlier work based on distinguishability matrices and is faster and more memory efficient than a recent method based on lists of indistinguishable faults. The paper provides the first reports on pessimistic and optimistic diagnostic measures for all faults of the large ISCAS circuits. 1 Introduction The aim of fault location or diagnosis is to locate device failures. Diagnosis may be intended for identification and replacement of a faulty sub-circui...

Recent studies show that a stuck-at test applied at the operational speed of the circuit identifies more defective chips than a test having the same fault coverage but applied at a lower speed. Design-for-testability approaches based on full scan, partial scan, or silicon-based solutions such as CrossCheck achieve very high stuck-at fault coverage. However, in all these cases, the tests have to be applied at speeds lower than the operation speed. In this work, we investigate various design-for-testability (DFT) techniques for sequential circuits that permit at-speed application of tests while providing for very high fault coverage. The method involves parallel loading of flip-flops in test mode for enhanced controllability combined with probe point insertion for enhanced observability. Fault coverage and ATG effectiveness improved to greater than 96% and 99.7%, respectively, for the ISCAS89 sequential benchmark circuits studied when these nonscan DFT techniques were used. The average area overhead for the nonscan DFT enhancements was 9.9% for standard cell implementations of three circuits synthesized from high-level descriptions, compared to 20.2% for full scan. ATG effectiveness improved to greater than 99.3% for all three circuits with the nonscan DFT enhancements.>

Abstract|T est generation using deterministic faultoriented algorithms is highly complex and time-consuming.New approaches are needed to augment the existing techniques, both to reduce execution time and to improve fault coverage.In this work, we describe a genetic algorithm (GA) framew ork for sequential circuit test generation.The GA evolves candidate test vectors and sequences, using a fault simulator to compute the tness of each candidate test.Various GA parameters are studied, including alphabet size, tness function, generation gap, population size, and mutation rate, as well as selection and crossover schemes.High fault coverages were obtained for most of the IS-CAS89 sequential benchmark circuits, and execution times were signi cantly lower than in a deterministic test generator in most cases.

Some recent studies show that an at-speed sequential or functional test is better than a test executed at lower speed. Design-for-testability approaches based on full scan, partial scan or silicon-based solutions such as Crosscheck achieve very high stuck-at fault coverage. However, in all these cases, the tests have to be applied at speeds lower than the operation speed of the circuit. In this paper, a design-for-test method that permits at-speed testing is introduced. The method is based on probe point insertion for improved observability, and it requires enhancements to an existing sequential circuit fault simulator. Faults that can be activated but not detected at existing primary outputs are targeted. A minimal set of probe points is selected to detect these faults, and the probe points are compressed to one or two output pins using exclusive-OR trees. The issue of aliasing of fault effects is addressed. Improvements in fault coverage were made for all 17 of the ISCAS89 sequential benchmark circuits studied. Fault coverages between 99% and 100% were obtained for seven circuits, and 100% ATG effectiveness was achieved on all but two circuits.>

Article Free Access Share on Non-scan design-for-testability techniques for sequential circuits Authors: Vivek Chickermane View Profile , Elizabeth M. Rudnick View Profile , Prithviraj Banerjee View Profile , Janak H. Patel View Profile Authors Info & Claims DAC '93: Proceedings of the 30th international Design Automation ConferenceJuly 1993 Pages 236–241https://doi.org/10.1145/157485.164686Published:01 July 1993Publication History 49citation329DownloadsMetricsTotal Citations49Total Downloads329Last 12 Months43Last 6 weeks19 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

In this work we describe a diagnostic fault simulator for sequential circuits which evaluates the effectiveness of a given test set in distinguishing between faults. Diagnostic fault simulation is performed on several ISCAS89 sequential benchmark circuits using two different deterministic test sets for each circuit. Several diagnostic measures are reported, including the diagnostic resolution, the diagnostic power, and the sizes of the indistinguishable fault classes. In addition, lists of indistinguishable faults are generated. Use of the diagnostic fault simulator to diagnose faults, given the output responses of failing devices, is also described.

Some recent studies show that an at-speed sequential or functional test is better than a test executed at lower speed. Design-for-testability approaches based on full scan, partial scan, or silicon-based solutions like Crosscheck achieve very high stuck-at fault coverage. However, in all these cases, the tests have to be applied at speeds lower than the operation speed. In this paper, a design-for-test method which permits at-speed testing is introduced. The method is based on probe point insertion for improved observability. Improvements in fault coverage were made for all 16 of the ISCAS-80 benchmark circuits studied. Fault coverages between 99% and 100% were obtained for six circuits, and 100% ATG efficiency achieved on all but two circuits.>

Methods are investigated for reducing events in sequential circuit fault simulation by reducing the number of faults simulated for each test vector. Inactive faults, which are guaranteed to have no effect on the output or the next state, are identified using local information from the fault-free circuit in one technique. In a second technique, the Star-algorithm is extended to handle sequential circuits and provides global information about inactive faults, based on the fault-free circuit state. Both techniques are integrated into the PROOFS synchronous sequential circuit fault simulator. An average 28% reduction in faulty circuit gate evaluations is obtained for the 19 ISCAS-89 benchmark circuits studied using the first technique, and 33% reduction for the two techniques combined. Execution times decrease by an average of 17% when the first technique is used. For the largest circuits, further improvements in execution time are made when the Star-algorithm is included.>