Synchronization and Specification Issues in Protocol Testing

Protocol testing for the purpose of certifying the implementation's adherence to the protocol specification can be done with a test architecture consisting of remote tester and local responder processes generating specific input stimuli, called test sequences, and observing the output produced by the implementation under test. It is possible to adapt test sequence generation techniques for finite state machines, such as transition tour, characterization, and checking sequence methods, to generate test sequences for protocols specified as incomplete finite state machines. For certain test sequences, the tester or responder processes are forced to consider the timing of an interaction in which they have not taken part; these test sequences are called nonsynchronizable. The three test sequence generation algorithms are modified to obtain synchronizable test sequences. The checking of a given protocol for intrinsic synchronization problems is also discussed. Complexities of synchronizable test sequence generation algorithms are given and complete testing of a protocol is shown to be infeasible. To extend the applicability of the characterization and checking sequences, different methods are proposed to enhance the protocol specifications: special test input interactions are defined and a methodology is developed to complete the protocol specifications.     

The optimistic update theorem for path delay testing in sequential circuits

For sequential circuit path delay testing, we propose a new update rule for state variables whereby flipflops are updated with their correct values provided they are destinations of at least one robustly activated path delay fault. Existing algorithms in the literature, for robust fault simulation and test generation, assign unknown values to off-path latches that have non-steady signals at their inputs in the previous vector. Such procedures are pessimistic and predict low fault coverages. They also have an adverse effect on the execution time of fault simulation especially if the circuit has a large number of active paths. The proposed update rule avoids these problems and yet guarantees robustness.     

Synchronous mirror delay for multiphase locking

A clock generation circuit having the function of multiphase locking was designed using the synchronous mirror delay (SMD) scheme. The internal clock can be synchronized to the external clock with intended phase difference. The synchronizing error of the clock generation circuit is reduced below the delay time of unit delay stage by compensation characteristics of detecting circuit in SMD. A 32-M double data rate (DDR) SRAM including the clock generation circuit is fabricated using 0.13-/spl mu/m CMOS technology. To measure the synchronizing error of the clock generation circuit, the test elements group (TEG) system is designed and fabricated with the main system. The synchronizing error of the clock generation circuit is far smaller than the delay time of unit delay stage at zero phase locking and similar to the delay time of unit delay stage at multiphase locking.     

Combining GAs and Symbolic Methods for High Quality Tests of Sequential Circuits

A symbolic fault simulator is integrated in a Genetic Algorithm (GA) environment to perform Automatic Test Pattern Generation (ATPG) for synchronous sequential circuits. In a two phase algorithm test length and fault coverage as well are optimized. Furthermore, not only the Single Observation Time Test Strategy is supported, but also test patterns with respect to the Multiple Observation Time Test Strategy are generated. However, there are circuits that are hard to test using random pattern sequences, even if these sequences are genetically optimized. Thus, deterministic aspects are included in the GA environment to improve fault coverage. Experiments demonstrate that both a priori time consuming strategies, the symbolic simulation approach and the GA, can be combined at reasonable costs: Tests with higher fault coverages and considerably shorter test sequences than previously presented approaches are obtained.     

Multiple Stuck-at Fault Testability Analysis of ROBDD Based Combinational Circuit Design

Automatic test pattern generation (ATPG) is the next step after synthesis in the process of chip manufacturing. The ATPG may not be successful in generating tests for all multiple stuck-at faults since the number of fault combinations is large. Hence a need arises for highly testable designs which have 100% fault efficiency under the multiple stuck-at fault(MSAF) model. In this paper we investigate the testability of ROBDD based 2×1 mux implemented combinational circuit design. We show that the ROBDD based 2×1 mux implemented circuit is fully testable under multiple stuck-at fault model. Principles of pseudoexhaustive testing and multiple stuck-at fault testing of two level AND-OR gates are applied to one sub-circuit(2×1 mux). We show that the composite test vector set derived for all 2×1 muxes is capable of detecting multiple stuck-at faults of the circuit as a whole. Algorithms to derive test set for multiple stuck-at faults are demonstrated. The multiple stuck-at fault test set is larger than the single stuck-at fault test set. We show that the multiple stuck-at fault test set can be derived from the Disjoint Sum of Product expression which allows test pattern generation at design time, eliminating the need of an ATPG after the synthesis stage.     

On the characterization of statistically synchronizablevariable-length codes

The authors consider statistically synchronizable variable-length codes, i.e. codes that admit decoders able to self-synchronize with high probability if the input sequence of code symbols is long enough. They show that a necessary and sufficient condition for the existence of a statistically self-synchronizing decoder and, therefore, for a code to be statistically synchronizable, is that the code has a synchronizing sequence. They also give a decision procedure to test whether a code has a synchronizing sequence. Finally, they specialize the procedure to obtain a simple and efficient algorithm to test the statistical synchronizability property of prefix codes     

Improving the Transition Fault Coverage of Functional Broadside Tests by Observation Point Insertion

Functional broadside tests were defined to address overtesting that may occur due to high peak current demands when tests for delay faults take the circuit through states that it cannot visit during functional operation (unreachable states). The fault coverage achievable by functional broadside tests is typically lower than the fault coverage achievable by (unrestricted) broadside tests. A solution to this loss in fault coverage in the form of observation point insertion is described. Observation points do not affect the state of the circuit. Thus, functional broadside tests retain their property of testing the circuit using only reachable states to avoid overtesting due to high peak current demands. However, the extra observability allows additional faults to be detected. A procedure for observation point insertion to improve the coverage of transition faults is described. Experimental results are presented to demonstrate that significant improvements in transition fault coverage by functional broadside tests is obtained.     

Sequential Circuit Test Generation Using a Symbolic/Genetic Hybrid Approach

Symbolic and genetic techniques are combined in a new approach to sequential circuit test generation that uses circuit decomposition, rather than the algorithmic decomposition used in previous hybrid test generators. Symbolic techniques are used to generate test sequences for the control logic, and genetic algorithms are used to generate sequences for the datapath. The combined sequences provide higher fault coverages than those generated by existing deterministic and GA-based test generators, and execution times are significantly lower in many cases.     

Automated System-Level Test Development for Mixed-Signal Circuits

While in the digital domain, test development is primarily conducted with the use of automated tools, knowledge-based, ad hoc test methods have been in use in the analog domain. High levels of design integration and increasing complexity of analog blocks within a system necessitate automated system-level analog test development tools. We outline a methodology for specification-based automated test generation and fault simulation for analog circuits. Test generation is targeted at providing the highest coverage for each specified parameter. The flexibility of assigning analog test attributes is utilized for merging tests leading to test time reduction with no loss in test coverage. Further optimization in test time is obtained through fault simulations by selecting tests that provide adequate coverage in terms of several components and dropping the ones that do not provide additional coverage. A system-level test set target in the given set of specifications, along with fault and yield coverages in terms of each targeted parameter, and testability problems are determined through the proposed methodology.     

Scan Division Algorithm for Shift and Capture Power Reduction for At-Speed Test Using Skewed-Load Test Application Strategy

This paper discusses an automated method to divide scan chains into multiple scan segments that are suitable for power-constrained at-speed testing using the skewed-load test application strategy. By dividing a circuit into multiple partitions, which can be tested independently, both power during shift and power during capture can be controlled. Despite activating one partition at a time, we show how through conscious construction of scan segments, high transition fault coverage can be achieved, while reducing test time of the circuit and employing third party test generation tools.

Partial scan design of register-transfer level circuits

Register-transfer level designs that are derived from high-level synthesis systems generally consist of functional blocks and registers that are interconnected by multiplexers and buses to maximize resource sharing These multiplexer and bus structures have the unique ability to behave asswitches, i.e., to logically partition the circuit when their control inputs are manipulated in different ways. The presence of switches, the selection of scan registers can be influenced. This leads to an efficient partial scan methodology presented in this paper. Second, switches help set up data transfer paths calledI-paths. By employingI-paths to transport test data, the functional logic in the circuit can be separated from the switching logic for the purpose of test generation. This can lead to a reduction in test generation costs for a partial scan design. Thus the techniques presented in this paper help to minimize both testability overhead and test generation cost in bus-based circuits. This methodology is implemented in the SIESTA system for serial scan design.     

Dynamic effects in the detection of bridging faults in CMOS ICs

Dynamic effects in the detection of bridging faults in CMOS circuits are taken into account showing that a test vector designed to detect a bridging may be invalidated because of the increased propagation delay of the faulty signal. To overcome this problem, it is shown that a sequence of two test vectors < T ₀, T ₁ >, in which the second can detect a bridging fault as a steady error, can detect the fault independently of additional propagation delays if T₀ initializes the faulty signal to a logic value different from the fault-free one produced by T ₁. This technique can be conveniently used both in test generation and fault simulation. In addition, it is shown how any fault simulator able to deal with FCMOS circuits can be modified to evaluate the impact of test invalidation on the fault coverage of bridging faults. For any test vector, this can be done by checking the state of the circuit produced by the previous test vector.     

Symbolic fault modelling of MOS combinational circuits

This paper presents a new method for fault modelling of MOS combinational circuits at the transistor level. Every transistor is replaced with a conductance controlled by the gate logic value. The specific advantage of the method is use of a symbolic simulator for circuit function extraction. This function is referred as Transistor Logic Conductance Function (TLCF). Starting from a known TLCF, a simple set of rules is used for output state determination. The method is suitable for multiple fault model generation thanks to the fact that only one symbolic analysis of a circuit is sufficient for modelling different stuck-open, stuck-short and stuck-at faults of a logic gate. Moreover, the method can deal also with bridging and cut faults. Finally, the application of the TLCF for test pattern generation is considered.     

Energy minimization and design for testability

The problem of fault detection in general combinational circuits is NP-complete. The only previous result on identifying easily testable circuits is due to Fujiwara who gave a polynomial time algorithm for detecting any single stuck fault inK-bounded circuits. Such circuits may only contain logic blocks with no more thanK input lines and the blocks are so connected that there is no reconvergent fanout among them. We introduce a new class of combinational circuits called the (k, K)-circuits and present a polynomial time algorithm to detect any single or multiple stuck fault in such circuits. We represent the circuit as an undirected graphG with a vertex for each gate and an edge between a pair of vertices whenever the corresponding gates have a connection. For a (k, K)-circuit,G is a subgraph of ak-tree, which, by definition, cannot have a clique of size greater thank+1. Basically, this is a restriction on gate interconnections rather than on the function of gates comprising the circuit. The (k, K)-circuits are a generalization of Fujiwara'sK-bounded circuits. Using the bidirectional neural network model of the circuit and the energy function minimization formulation of the fault detection problem, we present a test generation algorithm for single and multiple faults in (k, K)-circuits. This polynomial time aggorithm minimizes the energy function by recursively eliminating the variables.     

Fault simulation of linear analog circuits

Research in the areas of analog circuit fault simulation and test generation has not achieved the same degree of success as its digital counterpart owing to the difficulty in modeling the more complex analog behavior. This article presents a novel approach to this problem by mapping the good and faulty circuits to thediscrete Z-domain. An efficient fault simulation is then performed on this discretized circuit for the given input test wave form. This simulator provides an order of magnitude speedup over traditional circuit simulators. An efficient fault simulator and the formulation of analog fault models opens up the ground for analog automatic test generation.     

On methods to match a test pattern generator to acircuit-under-test

Autonomous circuits such as linear feedback shift registers (LFSRs) and cellular automats are used as low-cost test pattern generators for circuits testable by pseudo-random patterns. We demonstrate that different LFSRs of the same degree, started from different initial states, may yield significantly different fault coverages and test lengths when used as test pattern generators for a given circuit, especially when the circuit has faults which are hard to detect by a practical number of pseudo-random patterns. Methods to tailor an LFSR to a circuit-under-test are proposed, that attempt to select the most effective LFSR and initial state for the circuit. The first method is based on a learning process that can be applied directly to certain types of circuits. The learning process is also used to establish a collection of (primitive and nonprimitive) LFSRs and initial states, effective for arbitrary circuits. This collection can then be used as a starting point for a genetic optimization procedure aimed at improving the selected LFSR and initial state. The use of an LFSR that can apply complemented as well as uncomplemented test patterns is shown to significantly improve the fault coverage, at the cost of a small area overhead. Experimental results demonstrate the applicability of the proposed approaches to stuck-at faults and to transition faults     

Hybrid Fault Simulation for Synchronous Sequential Circuits

We present a fault simulator for synchronous sequential circuits that combines the efficiency of three-valued logic simulation with the exactness of a symbolic approach. The simulator is hybrid in the sense that three different modes of operation—three-valued, symbolic and mixed—are supported. We demonstrate how an automatic switching between the modes depending on the computational resources and the properties of the circuit under test can be realized, thus trading off time/space for accuracy of the computation. Furthermore, besides the usual Single Observation Time Test Strategy (SOT) for the evaluation of the fault coverage, the simulator supports evaluation according to the more general Multiple Observation Time Test Strategy (MOT). Numerous experiments are given to demonstrate the feasibility and efficiency of our approach. In particular, it is shown that, at the expense of a reasonable time penalty, the exactness of the fault coverage computation can be improved even for the largest benchmark functions.     

Fault simulation using small fault samples

This article emphasizes simulation-based sampling techniques for estimating fault coverage that use small fault samples. Although random testing is considered to be the primary area of application of the technique it is also suitable for estimating the fault coverage of nonrandom tests based on specific fault models. Especially for fault coverages exceeding 95%, it is shown that a precise estimate can be obtained using a fault sample of only 500 faults. The estimation is based on a binomial approximation of the probability density of the sample fault coverage. Using Bayes statistics an estimate is obtained whose accuracy is a linear function of the sample size if the fault coverage approaches 100%. The sample size is independent of the circuit size, thus making fault sampling particularly interesting for the fault simulation of ULSI designs due to the resulting reduction of the time complexity of fault simulation from O(N ₂) to O(N).This work was performed while Dr. Daehn was with the Laboratorium fuer Informationstechnologie at the university of Han- nover, Germany.