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.     

Sequential Circuits with Combinational Test Generation Complexity under Single-Fault Assumption

We show that the test generation problem for all single stuck-at faults in sequential circuits with internally balanced structures can be reduced into the test generation problem for single stuck-at faults in combinational circuits. In our previous work, we introduced internally balanced structures as a class of sequential circuits with the combinational test generation complexity. However, single stuck-at faults on some primary inputs, called separable primary inputs, corresponded to multiple stuck-at faults in a transformed combinational circuit. In this paper, we resolve this problem. We show how to generate a test sequence and identify undetectability for single stuck-at faults on separable primary inputs.     

FIRE: a fault-independent combinational redundancy identificationalgorithm

FIRE is a novel Fault-Independent algorithm for combinational REdundancy identification. The algorithm is based on a simple concept that a fault which requires a conflict as a necessary condition for its detection is undetectable and hence redundant. FIRE does not use the backtracking-based exhaustive search performed by fault-oriented automatic test generation algorithms, and identifies redundant faults without any search. Our results on benchmark and real circuits indicate that we find a large number of redundancies (about 80% of the combinational redundancies in benchmark circuits), much faster than a test-generation-based approach for redundancy identification. However, FIRE is not guaranteed to identify all redundancies in a circuit     

Determination of combinational logic circuit reliability through generation of fault diagnosis tests

This paper investigates the relationships between a given set of excitation vectors and the test sets for faults occuring in combinational circuits, in order to obtain new conditions for determining the redundant cubes of terminal states. The analysis presented is concluded with two new algorithms for the evaluation of combinational logic circuit reliability.     

Design of testable sequential circuits by repositioning flip-flops

This paper presents a technique to enhance the testability of sequential circuits by repositioning flip-flops. A novel retiming for testability technique is proposed that reduces cycle lengths in the dependency graph, converts sequential redundancies into combinational redundancies, and yields retimed circuits that usually require fewer scan flip-flops to break all cycles (except self-loops) as compared to the original circuit. Our technique is based on a new minimum cost flow formulation that simultaneously considers the interactions among all strongly connected components (SCCs) of the circuit graph to minimize the number of flip-flops in the SCCs. A circuit graph has a vertex for every gate, primary input and primary output. If gatea has a fanout to gateb, then the circuit graph has an arc from vertexa to vertexb. Experimental results on several large sequential circuits demonstrate the effectiveness of the proposed retiming for testability technique in reducing the number of partial scan flip-flops.     

A switch-level test generation system for synchronous and asynchronous circuits

A switch-level test generation system for synchronous and asynchronous circuits has been developed in which a new algorithm for fully automatic switch-level test generation and an existing fault simulator have been integrated. For test generation, a switch-level circuit is modeled as a logic network that correctly models the behavior of the switch-level including bidirectionality, dynamic charge storage, and ratioed logic. The algorithm is able to generate tests for combinational and sequential circuits. BothnMOS and CMOS circuits can be modeled. In addition to the classical line stuck-at faults, the algorithm is able to handle stuck-open and stuck-closed faults on the transistors of the circuit.In synchronous circuits, the time-frame based algorithm uses asynchronous processing within each clock phase to achieve stability in the circuit and synchronous processing between clock phases to model the passage of time. In asynchronous circuits, the algorithm uses asynchronous processing to reach stability within and between modules. Unlike earlier time-frame based test generators for general sequential circuits, the test generator presented uses the monotonicity of the logic network to speed up the search for a solution. Results on benchmark circuits show that the test generator outperforms an existing switch-level test generator both in time and space requirements. The algorithm is adaptable to mixed-level test generation.     

Functional versus random test generation for sequential circuits

This article presents a test generation method for sequential circuits based on their synthesis specifications as finite state machines (FSM) and provides comparison with random test generation. The finite state machines are represented by their state transition graph (STG). The test generation method is performed in two phases. The first phase is functional. It generates a test sequence which is one of the shortest input sequences going through all the transitions of the state transition graph machine. This sequence provides a high fault coverage of stuck-at faults on the synthesized circuit compared to a randomly generated test sequence. This fault coverage is very close to the ones of other sequences derived by fault-oriented test generation approaches [9], [10], although these latter sequences are much longer.The trend of the fault coverage curve for different test sequences including progressively the transitions of the test sequence defined in the first phase is similar to the one of the fault coverage curve of a random sequence but for same lengths the first curve gives larger fault coverage. Both curves grow rapidly until a given ratio of faults is detected then continue to grow very slowly exhibiting low efficiency.The second phase of the test generation method is fault-oriented. It uses a fault simulation based approach in order to compute the test sequence for the remaining faults not detected by the first phase. At the end of this phase the test sequence for all the nonredundant faults is derived and, the combinationally redundant faults and the sequentially redundant faults are distinguished.     

A finite state machine based fault tolerance technique for sequential circuits

With technology advancement at the nanometer scale, systems became more subjected to higher manufacturing defects and higher susceptibility to soft errors. Currently, soft errors induced by ion particles are no longer limited to a specific field such as aerospace applications. This raises the challenge to come up with techniques to tackle soft errors in both combinational and sequential circuits. In this work, we propose a finite state machine (FSM) based fault tolerance technique for sequential circuits. The proposed technique is based on adding redundant equivalent states to protect few states with high probability of occurrence. The added states guarantee that all single faults occurring in the state variables of highly occurring states or in their combinational logic are tolerated. The proposed technique has minimal area overhead as only few states need protection.     

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.     

Sequential circuit test generation using dynamic justification equivalence

Automatic test pattern generation (ATPG) for sequential circuits involves making decisions in the search decision spaces bounded by a sequential circuit. The flip-flops in the sequential circuit determine the circuit state search decision space. The inputs of the circuit define the combinational search decision space. Much work on sequential circuit ATPG acceleration focused on how to make ATPG search decisions. We propose a new technique to improve sequential circuit ATPG efficiency by focusing on not repeating previous searches. This new method is orthogonal to existing deterministic sequential circuit ATPG algorithms.A common search operation in sequential circuit ATPG is justification, which is to find an input assignment to justify a desired output assignment of a component. We have observed that implications in a circuit resulting from prior justification decisions form an unique justification decomposition. Since the connectivity of a circuit does not change during ATPG, test generation for different target faults may share identical justification decision sequences represented by identical decision spaces. Because justification decomposition represents the collective effects of prior justification decisions, it is used to identify previously-explored justification decisions. Preliminary results on the ISCAS 1989 circuits show that our test generator (SEST) using justification decompositions, on average, runs 2.4 and 4.5 times faster than Gentest and Hitec, respectively. We describe the details of justification equivalence and its application in ATPG accompanied with step-by-step examples.     

时序机的功能验证

本文介绍了时序电路（时序机）功能验证的基本概念和发展，分析了验证中存在的问题以及冗余故障的性质．提出基于ＳＴＧ的功能验证方法。最后，提出了采用动态任务调度策略的并行验证技术以解决状态遍历问题。     

Logical redundancies in irredundant combinational circuits

Some new types of logical redundancies that can occur in a combinational network are investigated. Three kinds of redundancy, namely a-redundancy, b-redundancy and c-redundancy are already well-known. This article presents two new types of redundancy called p-redundancy and n-redundancy in combinational networks which are otherwise known to be irredundant. A combinational circuit is calledp-redundant (n-redundant), if it is possible to realize the same function by permuting (inverting) some input terminals, in the presence of certain stuck-at faults in the circuit.     

基于概率转移矩阵的时序电路可靠度估计方法

传统的概率转移矩阵(Probabilistic Transfer Matrix,PTM)方法是一种能够比较精确地估计软差错对门级电路可靠度影响的方法,但现有的方法只适用于组合逻辑电路的可靠度估计.本文提出基于PTM的时序电路可靠度估计方法(reliability estimation of Sequential circuits based on PTM,S-PTM),先把待评估时序电路划分为输出逻辑模块和次态逻辑模块,然后用本文提出的时序电路PIM计算模型得到电路的PIM,最后根据输入信号的概率分布计算出时序电路的可靠度.用ISCAS 89基准电路为对象进行实验和验证,实验表明所提方法是准确和合理的.     

Testability and test generation for majority voting fault-tolerant circuits

The testability of majority voting based fault-tolerant circuits is investigated and sufficient conditions for constructing circuits that are testable for all single and multiple stuck-at faults are established. The testability conditions apply to both combinational and sequential logic circuits and result in testable majority voting based fault-tolerant circuits without additional testability circuitry. Alternatively, the testability conditions facilitate the application of structured design for testability and Built-In Self-Test techniques to fault-tolerant circuits in a systematic manner. The complexity of the fault-tolerant circuit, when compared to the original circuit can significantly increase test pattern generation time when using traditional automatic test pattern generation software. Therefore, two test pattern generation algorithms are developed for detecting all single and multiple stuck-at faults in majority voting based circuits designed to satisfy the testability conditions. The algorithms are based on hierarchical test pattern generation using test patterns for the original, non-fault-tolerant circuit and structural knowledge of the majority voting based design. Efficiency is demonstrated in terms of test pattern generation time and cardinality of the resulting set of test patterns when compared to traditional automatic test pattern generation software.     

Finite state machine synthesis with fault tolerant test function

According to a recent synthesis for testability proposal, a test function specified as a finite state machine with the same number of state variables as the given object machine, is incorporated into the state diagram prior to synthesis. Since a complete verification of the test machine is not practical, an often used heuristic sets and observes each state variable. The two machines share logic and a fault can result in partial or total loss of the test function. We show that the tests generated under the assumption that the entire test function is intact can become invalid. We propose a new method of synthesizing PLA-based finite state machines with fault tolerant test machines. Our approach eliminates testing of the test function. A constrained logic minimization phase insures that faults have predictable effect on the state diagram of the composite machine (object machine embedded with the test function). This allows effective use of the test function during test generation even in the presence of faults that effect both object and test machines. Only a combinational test generator is required for test generation. Each combinational vector is augmented by appropriate initialization and propagation sequences. Unlike prior approaches, ourO(log₂ n) length test sequence isguaranteed to detect any targeted crosspoint fault. Experimental results on the MCNC Logic Synthesis Workshop finite state machine benchmark set are given as evidence of practicality of the proposed approach.Supported by C&C Research Laboratories, NEC USA, during summer 1991.     

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.     

Synthesis of Sequential Circuits by Redundancy Removal and Retiming

In this paper we propose a method for synthesizing sequentialcircuits to reduce the number of gates and flip-flops by removingboth combinationally and sequentially redundant faults. In order toremove sequentially redundant faults these faults are converted intocombinationally redundant faults by using retiming techniques and thecombinationally redundant faults can be removed by using a testpattern generation method for combinational circuits. To simplify agiven circuit retiming is utilized for two purposes in thismethod. One is to find sequentially redundant faults and another is toreduce the number of flip-flops and gates. Before and after eachretiming the combinationally redundant faults are removed.Experimental results for ISCAS 89 benchmark circuits show that thismethod can remove many of sequentially redundant faults and canreduce a large number of gates and flip-flops.     

Improving path delay testability of sequential circuits

We analyze the causes of low path delay fault coverage in synchronous sequential circuits and propose a method to improve testability. The three main reasons for low path delay fault coverage are found to be: (A) combinationally false (nonactivatable) paths; (B) sequentially nonactivatable paths; and (C) unobservable fault effects. Accordingly, we classify undetected faults in Groups A, B, and C. Combinationally false paths ran be made testable by modifying the circuit or resynthesizing the combinational logic as discussed by other researchers. A majority of the untestable faults are, however found in Group B, where a signal transition cannot be functionally propagated through a combinational path. A test requires two successive states necessary to create a signal transition and propagate it through the target path embedded in the sequential circuit. We study a partial scan technique in which flip-flops are scanned to break cycles and shun that a substantial increase in the coverage of path delay faults is possible     

PREST: a system for logic partitioning and resynthesis fortestability

The authors propose a heuristic procedure for partitioning a circuit into several blocks so that after the resynthesis of each block and subsequent reconnection there is a near-minimal number of redundant faults in the circuit. A probabilistic technique is used to estimate the size of a don't care set, and the partitioning approach tries to reduce the don't care size across the partitions. The approach, called PREST (for Partitioning and RESynthesis for Testability), has been applied on various MCNC and ISCAS benchmark circuits, and excellent results in terms of the size and testability of the synthesized circuit have been obtained     

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.