Differential fault simulation for sequential circuits

A new fast fault simulation algorithm called differential fault simulation, DSIM, for synchronous sequential circuits is described. Unlike concurrent fault simulation, for every test vector, DSIM simulates the good machine and each faulty machine separately, one after another, rather than simultaneously simulating all machines. Therefore, DSIM dramatically reduces the memory requirement and the overhead in the memory management in concurrent fault simulation. Also, unlike serial fault simulation, DSIM simulates each machine by reprocessing its differences from the previously simulated machine. In this manner, DSIM is more efficient than serial fault simulation. Experiments have shown that DSIM runs 3 to 12 times faster than an existing concurrent fault simulator. In addition, owing to the simplicity of this algorithm, DSIM is very easy to implement and maintain. An implementation consists of only about 300 lines of C language statements added to the event-driven true-value simulator in an existing sequential circuit test generator program, STG3. Currently DSIM uses the zero-delay timing model. The addition of alternative delay models is under development.     

Reliable VLSI sequential controllers

A VLSI architecture for synchronous sequential controllers is resented that has attractive qualities for roducing reliable circuits. In these circuits, one hardware implementation can realize any flow table with a maximum of 2n internal states and m inputs. A real time fault detection means is resented along with a strategy for verifying the correctness of the checking hardware. This self-check feature can be employed with no increase in hardware. The architecture can be modified to achieve fail-safe designs. With no increase in hardware, an adaptable circuit can be realized that allows replacement of faulty transitions with fault-free transitions     

Fault detection in sequential machines with increased fault coverage

This letter develops an approach for fault detection and checking sequence design of sequential machines based on the principle of machine modification through augmentation of extra input and extra outputs, taking into consideration the case where faults occurring in a machine may cause an increase in its number of states.     

Self-timed is self-checking

Self-checking circuits detect (at least some of) their own faults. We describe self-timed circuits, including combinational logic and sequential machines, which either halt or generate illegal output if they include any single stuck-at faults. The self-timed circuits employ dual rail data encoding to implement ternary logic of 0, 1, andundefined states; the fourth state is used to signal illegal output and is shown to result only from certain circuit faults. The self-timed circuits also employ four-phase signaling according to a well-defined protocol of communications between the circuit and its environment; failures due to certain faults prevent the circuit from communicating properly, thus causing the circuit to halt. We show that any single stuck-at fault falls in either the first or the second category, thus providing complete fault coverage through self checking. No hardware needs to be added to our circuits to achieve the complete self-checking property; further, the circuit is guaranteed to never generate a legal but erroneous output if it contains a fault. Minimal hardware is needed to detect that a circuit has either halted or has generated an illegal output.     

Enhancing reliability of RTL controller-datapath circuits via Invariant-based concurrent test

We present a low-cost concurrent test methodology for enhancing the reliability of RTL controller-datapath circuits, based on the notion of path invariance. The fundamental observation supporting the proposed methodology is that the inherent transparency behavior of RTL components, typically utilized for hierarchical off-line test, renders rich sources of invariance within a circuit. Furthermore, additional sources of invariance are obtained by examining the algorithmic interaction between the controller, and the datapath of the circuit. A judicious selection & combination of modular transparency functions, based on the algorithm implemented by the controller-datapath pair, yields a powerful set of invariant paths in a design. Compliance to the invariant behavior is checked whenever the latter is activated. Thus, such paths enable a simple, yet very efficient concurrent test capability, achieving fault security in excess of 90% while keeping the hardware overhead below 40% on complicated, difficult-to-test, sequential benchmark circuits. By exploiting fine-grained design invariance, the proposed methodology enhances circuit reliability, and contributes a low-cost concurrent test direction, applicable to general RTL circuits.     

Principles and methods of testing finite state machines-a survey

With advanced computer technology, systems are getting larger to fulfill more complicated tasks: however, they are also becoming less reliable. Consequently, testing is an indispensable part of system design and implementation; yet it has proved to be a formidable task for complex systems. This motivates the study of testing finite stare machines to ensure the correct functioning of systems and to discover aspects of their behavior. A finite state machine contains a finite number of states and produces outputs on state transitions after receiving inputs. Finite state machines are widely used to model systems in diverse areas, including sequential circuits, certain types of programs, and, more recently, communication protocols. In a testing problem we have a machine about which we lack some information; we would like to deduce this information by providing a sequence of inputs to the machine and observing the outputs produced. Because of its practical importance and theoretical interest, the problem of testing finite state machines has been studied in different areas and at various times. The earliest published literature on this topic dates back to the 1950's. Activities in the 1960's mid early 1970's were motivated mainly by automata theory and sequential circuit testing. The area seemed to have mostly died down until a few years ago when the testing problem was resurrected and is now being studied anew due to its applications to conformance testing of communication protocols. While some old problems which had been open for decades were resolved recently, new concepts and more intriguing problems from new applications emerge. We review the fundamental problems in testing finite state machines and techniques for solving these problems, tracing progress in the area from its inception to the present and the stare of the art. In addition, we discuss extensions of finite state machines and some other topics related to testing     

New Non-Scan DFT Techniques to Achieve 100% Fault Efficiency

This paper suggests three techniques on non-scan DFT of sequential circuits. The proposed techniques guarantee 100% fault efficiency by using combinational ATPG tool. In all the techniques, an additional circuit called CRIS is proposed to reach unreachable states on the state register of a machine. The second and third techniques use an additional hardware DL to uniquely identify a state appearing in a state register. The design of DL is universal. Test length and hardware overhead outperform the similar approaches.     

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.     

A test methodology for finite state machines using partial scan design

This paper presents an efficient automatic test pattern generation technique for loop-free circuits. A partial scan technique is used to convert a sequential circuit (finite state machine) with arbitrary feedback paths into a pipelined circuit for testing. Test generation for these modified circuits can be performed with a modified combinational automatic test pattern generator (ATPG), which is much faster than a sequential ATPG. A combinational model is obtained by replacing all flipflops by buffers. It is shown that a test vector for a fault in this model obtained by a combinational test generator can be expanded into a sequence of identical vectors to detect the same fault in the original sequential circuit. This technique may abort a few faults which can then be resolved with a sequential ATPG. Experiments on the ISCAS89 circuits show that only 30% to 70% of flipflops require scanning in larger circuits and 96% to 100% fault coverage for almost all the circuits without resorting to a sequential ATPG.This research was sponsored by the Semiconductor Research Corporation, Contract 90-DP-142.     

Partial Reset Methodology and Experiments for Improving Random-Pattern Testability and BIST of Sequential Circuits

Partial reset has been shown to have significant impact on test generation for sequential circuits in a stored-pattern test application environment. In this paper, we explore the use of partial reset in fault-independent testing and built-in self-test (BIST) of non-scan sequential circuits. We select a subset of flip-flops in the circuit to be resetable to logic one or zero during the application of the test vectors. The resetting is performed with random frequency. The selection of the flip-flops and the reset polarity is based on fault-propagation analysis, which determines the impact of a selected flip-flop on fault propagation from the circuits structure. Application of partial reset as described above yields an average improvement of 15% in fault-coverage for sequential circuits resistant to random pattern testing. To further enhance testability, we also present a methodology for selecting observable test points based on propagation of switching activity. Overall, high fault coverages (about 97%) are obtained for many of the ISCAS89 benchmark circuits. Thus, partial reset BIST provides a low cost alternative for testing sequential circuits when scan design is unacceptable due to area and/or delay constraints. The routing overhead for implementing BIST is seen to be about 6%.     

Design of concurrent test Hardware for Linear analog circuits with constrained hardware overhead

Concurrent detection of failures in analog circuits is becoming increasingly more important as safety-critical systems become more widespread. A methodology for automatic design of concurrent failure detection circuitry for linear analog systems is discussed in this paper. The desired hardware bound is specified as a constraint; the methodology aims at providing coverage in terms of all the circuit components while minimizing the loading overhead by reducing the number of internal circuit nodes that need to be tapped. Parameter tolerances are incorporated through either statistical or mathematical analysis to determine the threshold for failure alarm.     

Synthesis of Circuits with Low-Cost Concurrent Error Detection Based on Bose-Lin Codes

This paper presents a procedure for synthesizing sequential machines with concurrent error detection based on Bose-Lin codes. Bose-Lin codes are an efficient solution for providing concurrent error detection as they are separable codes and have a fixed number of check bits, independent of the number of information bits. Furthermore, Bose-Lin code checkers have a simple structure as they are based on modulo operations. Procedures are described for synthesizing circuits in a way that their structure ensures that all single-point faults can only cause errors that are detected by a Bose-Lin code. This paper presents an efficient scheme for concurrent error detection in sequential circuits with no constraint on the state encoding. Concurrent error detection for both the state bits and the output bits is based on a Bose-Lin code and their checking is combined such that one checker suffices. Results indicate low area overhead. The cost of concurrent error detection is reduced significantly compared to other methods based on other codes.     

Redundancies and don't cares in sequential logic synthesis

The relationships between redundant logic and don't care conditions in combinational circuits are well known. Redundancies in a combinational circuit can be explicitly identified using test generation algorithms or implicitly eliminated by specifying don't cares for each gate in the combinational network and minimizing the gates, subject to the don't care conditions.In this article, we explore the relationships between redundant logic and don't care conditions in sequential circuits. Stuck-at faults in a sequential circuit may be testable in the combinational sense, but may be redundant because they do not alter the terminal behavior of a nonscan sequential machine. These sequential redundancies result in a faulty State Transition Graph (STG) that is equivalent to the STG of the true machine.We present a classification of redundant faults in sequential circuits composed of single or interacting finite state machines. For each of the different classes of redundancies, we define don't care sets which if optimally exploited will result in the implicit elimination of any such redundancies in a given circuit. We present systematic methods for the exploitation of sequential don't cares that correspond to sequences of vectors that never appear in cascaded or interacting sequential circuits. Using these don't care sets in an optimal sequential synthesis procedure of state minimization, state assignment, and combinational logic optimization results in fully testable lumped or interacting finite state machines. We present experimental results which indicate that medium-sized irredundant sequential circuits can be synthesized with no area overhead and within reasonable CPU times by exploiting these don't cares.     

A Formal Approach to On-Line Monitoring of Digital VLSI Circuits: Theory,Design and Implementation

This work is concerned with the development of algorithms and CAD tools for the design of digital circuits with on line monitoring capability. The Theory of Fault Detection and Diagnosis available in the literature on Discrete Event Systems has been adopted for on-line detection of stuck-at faults in Digital Circuits. Efficient computational techniques to deal with very large state spaces based on Ordered Binary Decision Diagrams and Abstraction have been proposed. Based on these a CAD tool has been developed that can provide a fully automated flow for design of circuits with on-line test capability without the requirement of any modification to the core. The tool can handle generic digital circuits with cell count as high as 15,000 and having the order of 2⁵⁰⁰ states. This is believed to be an improvement of an order of magnitude over results presented in the literature. This methodology enables the designer to tradeoff fault coverage and detection latency against area and power overhead. The design flow using the CAD tool developed is described and results for design of on-line detectors for various ISCAS89 benchmark circuits are provided. The methodology is further validated by design, fabrication, and testing of an ASIC in 0.18 μ technology.     

A built-in self-test method for diagnosis of synchronous sequentialcircuits

We propose an approach for built-in fault diagnosis of synchronous sequential circuits. The proposed approach distinguishes faults based on their detection by modified versions of a fault detection test sequence generated on-chip. The modified versions are defined by one-bit-wide auxiliary sequences, also generated on-chip. The auxiliary sequences indicate which test vectors of the fault detection test sequence need to be applied to the circuit. Experimental results presented indicate that the proposed on-chip test generation method is effective in achieving high levels of diagnostic-resolution     

State and Fault Information for Compaction-Based Test Generation

We present a new test generation procedure for sequential circuits using newly traversed state and newly detected fault information obtained between successive iterations of vector compaction. Two types of techniques are considered. One is based on the new states a sequential circuit is driven into, and the other is based on the new faults that are detected between consecutive iterations of vector compaction. These data modify an otherwise random selection of vectors, to bias vector sequences that cause the circuit to reach new states, and cause previously undetected faults to be detected. The biased vectors, when used to extend the compacted test set, provide a more intelligent selection of vectors. The extended test set is then compacted. Repeated applications of state and fault analysis, vector generation and compaction produce significantly high fault coverage using relatively small computing resources. We obtained improvements in terms of higher fault coverage, fewer vectors for the same coverage, or smaller number of iterations and time required, consistently for several benchmark circuits.     

A novel ASIC design approach based on a new machine paradigm

A novel design methodology for rapid implementation of cheap high-performance ASICs (application-specific integrated circuits) is introduced. The method derives from high-level algorithm specifications or from high-level source programs not only the target hardware, but (in contrast to silicon compilers) also the machine code to run it. The method is based on a novel sequential machine paradigm where execution is used (being orders of magnitude more efficient) instead of simulation and where programmers may do the design job, rather than real hardware designers. It is shown that, for a very large class of commercially important algorithms (DSP, graphics, image processing and many others), this paradigm is orders of magnitude more efficient that the von Neumann paradigm. Compared to von-Neumann-based implementations, acceleration factors of up to more than 2000 have been obtained experimentally. The performance of ASICs obtained by this methodology is mostly competitive with ASIC designs obtained in the much slower and much more expensive traditional way. As a by-product the new methodology also supports the automatic generation of universal accelerators for coprocessor use in workstations     

转动惯量测量电路与实现

为了实现在线测量回转机械传动系统的转动惯量,采用了以ADuC812单片机为核心,并结合其他外围芯片的控制电路和实现方法。硬件重点设计了单片机采集与处理信号电路及继电器控制电路的实现;软件给出了主程序流程图的设计。经过硬件实测,该电路可以方便快捷地完成对转动惯量的实时测量,且电路结构简单,使用灵活方便,并具有线性度高,噪声系数小等特点。     

Path delay fault simulation of sequential circuits

A differential algorithm for concurrent simulation of path delay faults in sequential circuits is presented. The simulator analyzes all three conditions, namely, initialization, signal transition propagation through the path, and fault effect observation at a primary output for vector pairs and considers the hazard states occurring between vectors. The main contribution is in methods of propagating signals between time frames. An optimistic method assumes that all nondestination flip-flops are not affected by delays. The pessimistic method converts all nondestination flip-flops with nonsteady values to the unknown state before these values are propagated beyond the time frame in which a path is activated. A 13-valued algebra is shown to improve the efficiency of fault simulation