# A Discrete Event System Approach to Online Testing of Speed Independent Circuits

Authors: P. K. Biswal; K. Mishra; S. Biswas; H. K. Kapoor
Journal: VLSI Design
 (2015)

---

## Abstract

With the increase in soft failures in deep submicron ICs, online testing is becoming an integral part of design for testability. Some techniques for online testing of asynchronous circuits are proposed in the literature, which involves development of a checker that verifies the correctness of the protocol. This checker involves Mutex blocks making its area overhead quite high. In this paper, we have adapted the Theory of Fault Detection and Diagnosis available in the literature on Discrete Event Systems to online testing of speed independent asynchronous circuits. The scheme involves development of a state based model of the circuit, under normal and various stuck-at fault conditions, and finally designing state estimators termed as detectors. The detectors monitor the circuit online and determine whether it is functioning in normal/failure mode. The main advantages are nonintrusiveness and low area overheads compared to similar schemes reported in the literature.


---

## Body

## 1. Introduction

With the advancement of VLSI technology for circuit design, there is a need to monitor the operations of circuits for detecting faults [1]. These needs have increased dramatically in recent times because, with the widespread use of deep submicron technology, there is a rise in the probability of development of faults during operation. Performing tests before operation of a circuit and assuming continued fault-free behaviour may decrease the reliability of operation. In other words, there is a need foronline testing (OLT) of VLSI circuits, whereupon they are designed to verify, during normal operation, whether their output response conforms to the correct behaviour.Most of the circuits used in VLSI designs are synchronous. Compared to synchronous circuits, asynchronous designs offer great advantages such as no clock skew problem, low power consumption, and average case performances rather than the worst case performances. Testing asynchronous circuits as compared to synchronous circuits is considered difficult due to the absence of the global clock [2]. OLT has been studied for the last two decades and can be broadly classified into the following main categories:(i)
Self-checking design.
(ii)
Signature monitoring in FSMs.
(iii)
Duplication.
(iv)
Online BIST.The approach of self-checking design consists of encoding the circuit outputs using some error detecting code and then checking some code invariant property (e.g., Parity) [3–5]. Some examples are Parity codes [6], m-out-of-n codes [7], and so forth. The area overhead for making circuits self-checkable is usually not high. These techniques, termed as “intrusive OLT methodologies,” require some special properties in the circuit structure to limit the scope of fault propagation. These properties can be achieved by resynthesis and redesign of the original circuit, which may affect the critical paths in the circuit.Signature monitoring techniques for OLT [8, 9] work by studying the state sequences of the circuit FSM model during its operation. These schemes detect faults that lead to illegal paths in the control flow graph, that is, paths having transitions which do not exist in the specified FSM. To make the runtime signature of the fault-free circuit FSM different from the one with fault, asignature invariant property is forced during FSM synthesis, making the technique intrusive. Further, the state explosion problem in FSM models makes the application of this scheme difficult for practical circuits.Duplication based OLT technique works by simply replicating the original circuit and comparing the output responses [10]; a fault is detected if the outputs do not match. The major advantage of duplication based scheme is nonintrusivity; however, area overhead is more than double. To address this issue, partial duplication technique is applied [11, 12]. This scheme first generates a complete set of test vectors for all the faults possible, using Automatic Test Pattern Generation (ATPG) algorithms. After that, a subset of faults are selected (based on required coverage) and a subset of test vectors (based on tolerable latency) for the selected faults are taken and synthesized into a circuit which is used for OLT. It may be noted that ATPG algorithms are optimized to generate the minimum number of test vectors that detect all faults. As the scheme applies ATPG algorithms in a reverse philosophy, it becomes prohibitively complex for large circuits.The technique of designing circuits with additional on-chip logic, which can be used to test proper operation of the circuit before it starts, is called off-line BIST. Off-line BIST resources are now being used for online testing [13–16]. This technique utilizes the idle time of various parts of the circuit to perform online BIST. Idle times are reducing in circuits because of pipelining and parallelism techniques and so online BIST scheme is of limited utility.Motivation of the Work. From the above discussion we may state that an efficient approach for OLT should have the following metrics:(i)
The OLT scheme should be nonintrusive. This is the most important constraint as designers meet requirements, like frequency, area, power, and so forth, of the circuit to produce an efficient design and do not want the test engineers to change them.
(ii)
The OLT technique should support well accepted fault models.
(iii)
The scheme should be computationally efficient so that it can handle reasonably large circuits.Most of the papers cited in the above discussion are for OLT of synchronous circuits and only a few of them [4, 5, 10] are applicable to asynchronous circuits. Now, we elaborate on these three works on OLT of asynchronous circuits and derive motivation of the present work.Traditionally, double redundancy methods were used for OLT of asynchronous designs [10]. In this scheme, two copies of the same circuit work in parallel and the online tester checks whether they generate the same output. This scheme results in more than 100% area and power overheads. Further, both being the same circuit, they are susceptible to similar nature of failures. The schemes reported in [4, 5] basically work by checking whether the output of the asynchronous circuit maintains a predefined protocol (i.e., there is no premature or late occurrence of transitions). The checker circuit is implemented using David cells (DCs), Mutual Exclusion (Mutex) elements, C-elements, and logic gates. The checker circuit has two modes: operation-normal mode and self-test mode. In normal mode, the checker is used to detect whether there is any violation in the protocol being executed by the CUT. On the other hand, in self-test mode, the checker is used to detect faults that may occur within the checker itself. Mutex elements (component of asynchronous arbiter) were used to grant exclusive access to the shared DCs between different modes of operation. The area overhead of the Mutex blocks is high, even compared to the original circuit. So, area overhead of the online tester in this case would be much higher than that of the original circuit and even the redundancy based methods. Further, this tester only checks the protocol and so fault coverage or detection latency cannot be guaranteed.Discrete event system (DES) model based methods are used for failure detection for a wide range of applications because of the simplicity of the model as well as the associated algorithms [17]. A DES is characterized by a discrete state space and some event driven dynamics. Finite state machine (FSM) based model is a simple example of a DES. In the state based DES model, the model is partitioned according to the failure or normal condition. The failure detection problem consists in determining, in finite time after occurrence of the failure, whether the system is traversing through normal or failure subsystem. A fault is detectable by virtue of certain transitions (in the failure states) which are called fault detecting transitions (FD-transitions). FD-transition is a transition of the faulty subsystem, for which there is no corresponding equivalent transition in the normal subsystem. Using the FD-transitions, a DES fault detector is designed, which is a kind of state estimator of the system. For OLT of circuits, the detector is synthesized as a circuit which is executed concurrently with the circuit under test (CUT). Biswas et al. in [18, 19] have developed an OLT scheme for synchronous circuits using the FSM based DES theory, which satisfies most of the metrics mentioned above for an efficient online tester design. In this paper, we aim at using the theory of failure detection of DES models for OLT of SI circuits.Just like synchronous circuits, the basic FSM framework is also used to model asynchronous circuits with slight modification. In case of synchronous circuits, state changes in the FSM occur only at the active edge of the register clock, irrespective of the time of change of the inputs. On the other hand, in asynchronous circuits, state changes can occur immediately after transition in the inputs. FSM used to model asynchronous circuit is called AFSM [20]. An alternative to AFSM is burst-mode (BM) state machines [20]. AFSM and BM state machine are similar from the modeling perspective; however, in case of BM state machine transitions are labeled with signal changes rather than their explicit values, which is the case in AFSMs. AFSMs and BM state machines assume that first inputs change followed by outputs and finally new state is reached. Due to the strict sequence of signal changes, all asynchronous protocols cannot be modeled using AFSMs or BM state machines. Extended BM state machines address this modeling issue by allowing some inputs in a burst to change monotonically along a sequence of bursts rather than in a particular burst. Petri net (PN) is widely accepted modeling framework for highly concurrent systems [21]. PN models a system using interface behaviors which are represented by allowed sequence of transitions or traces. The view of an asynchronous circuit as a concurrent system makes PN based models more appropriate than AFSMs and BM state machines for their analysis and synthesis. There are several variants of PNs among which signal transition graph (STG) is generally used to model asynchronous circuits. The major reason is that the STG interprets transitions as signal transitions and specifies circuit behavior by defining casual relations among these signal transitions [22].In this paper, we aim at using the theory of failure detection of DES model for OLT of SI asynchronous circuits. Several modifications are made in the DES framework used for synchronous circuits [18, 19] when applied for SI circuits. The modifications are as follows:(i)
We first model SI circuits along with their faults as STGs and then translate them into state graphs. State graphs are similar to FSM based DES models from whichFD-transitions can be determined.
(ii)
In case of synchronous circuits, the fault detector is an FSM which detects the occurrence ofFD-transitions. A synchronous circuit can be synthesized in a straightforward way from the FSM specification [18, 19] that performs online testing. Why the same design cannot be synthesized as an asynchronous circuit will be discussed in this paper. As the use of synchronous circuit for OLT of asynchronous modules is not desirable, we propose a new technique for detector design which can be synthesized as a SI circuit. The detector is designed as state graph model which is live and has complete state coding (CSC); these properties ensures its synthesizability as a SI circuit.The paper is organized as follows. In Section2, we present some definitions and formalisms of the DES framework. Section 3 illustrates DES modeling for a speed independent circuit under normal and stuck-at faults. In Section 4, the DES detector for the SI asynchronous circuit is designed. Synthesizing the DES detector as online tester circuit is also discussed in the same section. Section 5 presents experimental results regarding area overhead and fault coverage of the DES detector based online tester. Also, comparison of area overhead of the proposed approach with other similar schemes is reported. Finally, we conclude in Section 6.


## 2. DES Modeling Framework: Definitions and Formalisms

Adiscrete event system (DES) model
G is defined as G
=
V
,
X
,
I
,
X
0 where V
=
{
v
1
,
v
2
,
…
.
,
v
n
} (In case of modeling SI circuits as DES, the state variables are values of the I/O signals. So, in this work, we will interchangeably use the terms signal and variable.) is a finite set of discrete variables assuming values from the set 0,1, called the domains of the variables, X is a finite set of states, I is a finite set of transitions, and X
0
⊆
X is the set of initial states. A state x is a mapping of each variable to one of the elements of the domain of the variable. Atransition
τ
∈
I from a state x to another state x
+ is an ordered pair x
,
x
+, where x is denoted by i
n
i
t
i
a
l
(
τ
) and x
+ is denoted as f
i
n
a
l
(
τ
).


### 2.1. Failure Modeling

The failure of the system is modeled by dividing the DES model into submodels and each submodel is used to model the system under normal or failure conditions. To differentiate between the submodels, each statex is assigned a failure label by a status variable S with its domain being equal to {
N
∪
F
1
∪
F
2
∪
⋯
∪
F
d
}, where N is normal status, F
i, 1
≤
i
≤
d, is failure status, and d is the number of possible faults.Definition 1 (normalG-state).
AG-state x is normal if x
(
S
)
=
{
N
}. The set of all normal states is denoted by X
N.Definition 2 (F
i-G-state).
AG-state x is failure state or synonymously an F
i-state, if F
i
∈
x
(
S
). The set of all F
i-states is denoted by X
F
i.Definition 3 (normalG-transition).
AG-transition x
,
x
+ is called a normal G-transition if x, x
+
∈
X
N.Definition 4 (F
i-G-transition).
AG-transition x
,
x
+ is called an F
i-G-transition if x, x
+
∈
X
F
i.Definition 5 (equivalent states).
Two statesx and y are said to be equivalent, denoted by x
E
y, if x
V
=
y
V and x
(
S
)
≠
y
(
S
).
In other words, two states are said to be equivalent if they have the same values for state variables and different value for status variable.A transitionx
,
x
+, where x
(
S
)
≠
x
+
(
S
), is called afailure transition indicating the first occurrence of some failure in the system. Since failures are assumed to bepermanent, there is no transition from any state in X
F
i to any state in X
N or from any state in X
F
i to any state in X
F
j.Definition 6 (equivalent transitions).
Two transitionsτ
1
=
x
1
,
x
1
+ and τ
2
=
x
2
,
x
2
+ are equivalent, denoted by τ
1
E
τ
2, if x
1
E
x
2, x
1
+
E
x
2
+ and they must associate with the same signal change.Suppose that there is a transition in failure DES model for which there is no corresponding equivalent transition in normal DES model, then that transition is called failure detecting transition (FD-transition). The failure is detected when the system traverses through the FD-transition. Thus, we can define FD-transition as follows.Definition 7 (F
D-transition).
AF
i-G-transition of faulty DES model τ
′
=
x
′
,
x
′
+ is an FD-transition, if there is no G-transition τ
=
x
,
x
+ in the normal DES model such that τ
′
E
τ.The motivation of failure detection using DES model is to find out suchFD-transitions and design DES detector using these transitions. In the next section, we discuss how to model SI circuits using DES.


## 2.1. Failure Modeling

The failure of the system is modeled by dividing the DES model into submodels and each submodel is used to model the system under normal or failure conditions. To differentiate between the submodels, each statex is assigned a failure label by a status variable S with its domain being equal to {
N
∪
F
1
∪
F
2
∪
⋯
∪
F
d
}, where N is normal status, F
i, 1
≤
i
≤
d, is failure status, and d is the number of possible faults.Definition 1 (normalG-state).
AG-state x is normal if x
(
S
)
=
{
N
}. The set of all normal states is denoted by X
N.Definition 2 (F
i-G-state).
AG-state x is failure state or synonymously an F
i-state, if F
i
∈
x
(
S
). The set of all F
i-states is denoted by X
F
i.Definition 3 (normalG-transition).
AG-transition x
,
x
+ is called a normal G-transition if x, x
+
∈
X
N.Definition 4 (F
i-G-transition).
AG-transition x
,
x
+ is called an F
i-G-transition if x, x
+
∈
X
F
i.Definition 5 (equivalent states).
Two statesx and y are said to be equivalent, denoted by x
E
y, if x
V
=
y
V and x
(
S
)
≠
y
(
S
).
In other words, two states are said to be equivalent if they have the same values for state variables and different value for status variable.A transitionx
,
x
+, where x
(
S
)
≠
x
+
(
S
), is called afailure transition indicating the first occurrence of some failure in the system. Since failures are assumed to bepermanent, there is no transition from any state in X
F
i to any state in X
N or from any state in X
F
i to any state in X
F
j.Definition 6 (equivalent transitions).
Two transitionsτ
1
=
x
1
,
x
1
+ and τ
2
=
x
2
,
x
2
+ are equivalent, denoted by τ
1
E
τ
2, if x
1
E
x
2, x
1
+
E
x
2
+ and they must associate with the same signal change.Suppose that there is a transition in failure DES model for which there is no corresponding equivalent transition in normal DES model, then that transition is called failure detecting transition (FD-transition). The failure is detected when the system traverses through the FD-transition. Thus, we can define FD-transition as follows.Definition 7 (F
D-transition).
AF
i-G-transition of faulty DES model τ
′
=
x
′
,
x
′
+ is an FD-transition, if there is no G-transition τ
=
x
,
x
+ in the normal DES model such that τ
′
E
τ.The motivation of failure detection using DES model is to find out suchFD-transitions and design DES detector using these transitions. In the next section, we discuss how to model SI circuits using DES.


## 3. DES Model of a Speed Independent Circuit: Normal and Faulty

As already discussed, the first step to design a DES based online tester is to obtain the normal and faulty state based model of the CUT. However, the traditional state based DES paradigm cannot be directly used for modeling SI circuits. So in this case we will start with signal transition graph (STG), which is a type of Petri net based DES, to specify fault-free and faulty conditions. The STGs will be converted into state graphs (similar to FSMs) using the concept presented in [22].We first discuss fault modelling at the STG level using an example and concepts from [22]. In addition to the models (i.e., faults in transistors of the C-elements) given in [22], we have also modeled stuck-at faults on all wires (i.e., input/output of gates).


### 3.1. Fault Modeling

The SI asynchronous CUT example being considered to illustrate the proposed scheme is shown in Figure1 (taken from [22]). Traditionally, synchronous circuits consist of blocks of combinational logic connected with clocked latches or registers, while, in case of SI circuit designs, we basically have logic gates as building blocks with C-elements, which act as storage elements. Transistor level diagram of C-element is shown in Figure 2; logic function of the C-element can be described by the Boolean equation C
=
A
B
+
A
C
′
+
B
C
′, where C is the next state and C
′ is the old state value [22, 23]. The output of C-element becomes logically high (low) when both the inputs are logically high (low); otherwise it keeps its previous logic value. There are two types of C-elements used in SI circuits: static C-element and dynamic C-element. The static version of C-element promises that the information inside it can be stored for unbounded periods. However, dynamic versions of C-element provide gains in terms of area, power, and delay [23–26]. Since the circuits having high operating speed, low area, and power consumption are preferred in modern days, we have chosen SI circuits with dynamic C-elements instead of static ones.Figure 1
Example of speed independent asynchronous CUT.Figure 2
Transistor diagram of dynamic C-element.Figure3 shows the STG for the CUT being considered. Rising (falling) transitions on signals, indicated by + (−), are shown in the STG. The dark circles along the arcs are called tokens. The token indicates one of possibly a set of signals that enable transition to fire. If all input arcs for a signal transition have tokens then that signal transition is said to be enabled. For example, when signal R
in goes high (denoted by R
in
+) and R
out goes high (denoted by R
out
+), only then A
out
+ transition can take place. Upon firing A
out
+, a token is placed on each of its outgoing arcs, thus enabling R
in
-. Note that R
out
- is enabled after A
out
+ and A
in
+.Figure 3
Signal transition graph of sample circuit.In this paper, we have considered SI circuits that contain C-elements (we assumed dynamic version) and logic gates. For the logic gates, the most popular fault model is the stuck-at fault model, which is at the gate level. However, for the C-elements stuck-on and stuck-off faults for each transistor are an accepted fault model [22]. So we have chosen a mixed gate/transistor level description for modeling the faults. To illustrate fault modeling at both C-elements and basic gates, we consider the circuit example from [22] which is shown in Figure 1.


#### 3.1.1. STG Based Modeling

In this work, we model single stuck-at faults in the gates and transistors (for the C-elements) and map them to STGs of the circuit. For the analysis, the signals attached to the inputsA and B of the C-elements are also indicated in the gate level circuit diagram of Figure 1. Now, we consider some of these faults (one at a time), analyze their effects, and finally modify the STG to model the faults.Consider the C-element C2 of Figure1 and refer to transistor level circuit of Figure 2. The C-element C2 has R
out and R
in as inputs and A
out as output. If the transistor n
1 has a stuck-on fault, this leads to error in the circuit that it needs to wait for only n
2 to be enabled to generate output. When n
2 turns on, then a path to ground via n
1 and n
2 gets established, which makes p
3 on and n
3 off, making C high. So C2 has to wait only for n
2 (i.e., R
in
+ which corresponds to input B of C2 to become 1) to turn on and change the output. In other words, it has to wait for only R
in
+ (and not also for R
out
+, which is the requirement under normal condition) before it can generate A
out
+. Thus, the fault in n
1 leads to premature firing of the A
out
+ transition. We represent this by including a token on the arc connecting R
out
+ to A
out
+. Availability of this token will enable A
out
+ to fire as soon as R
in
+ arrives, without waiting for R
out
+. This token is denoted by a “1” shown on the arc in Figure 4.Figure 4
STG level model of stuck-on faultn
1 of C2 [22].Now, consider C-element C1 producing outputR
out, with transistor p
1 having stuck-on fault. As p
1 is on, the gate has to wait for p
2 to turn on before it can change the output. When p
2 turns on (by virtue of B
=
0) then there is no path to ground as n
2 is off, which makes p
3 off and n
3 on, making C low. Here, C1 has to wait for the input B
=
0 to generate R
out
-. Referring to Figure 1, for B to become 0, we need either A
out to become 1 (the same as R
in becoming 0) or A
in to become 1. Thus, as soon as we have either A
out
+ or A
in
+, R
out
- would fire. It may be noted that, under normal condition, for R
out
- to fire, we also require A
=
0, which mandates both A
out
+ and A
in
+. This failure condition is indicated in the STG by adding a “1” to the input arcs of R
out
-, which is shown in Figure 5. To elaborate, Figure 5(a) (Figure 5(b)) shows that R
out
- can be fired as soon as A
in
+ (A
out
+) fires and does not wait for A
out
+ (A
in
+).Figure 5
STG level model of stuck-on fault inp
1 of C1 [22].
(a)
R
out
- does not wait for A
out
+
(b)
R
out
- does not wait for A
in
+As the third fault, let C1 have stuck-on fault atn
2. The stuck-on fault at n
2 enforces the circuit to wait only for n
1 to be enabled for generating output R
out
+. As n
1 is connected to input A, which is logical ORing of A
out
- and A
in
-, transition R
out
+ can fire after A
out
- or A
in
- (without requiring to wait for R
in
+). This premature firing of transition R
out
+ is indicated in the STG by adding a “1” to R
in
+, which is shown in Figure 6.Figure 6
STG level model of stuck-on faultn
2 of C1 [22].For the gates, stuck-at-0 and stuck-at-1 faults are considered at their inputs and output nets. Let Line 2 of the AND gate from Figure1 have a stuck-at-0 fault. This makes Line 6 stuck-at-0 fault. As Line 6 is connected to the B input of the C-element C1, we have transistor p
2 on and transistor n
2 off. Note that as n
2 is always off, there is no path to the ground. So the output R
out can never become 1 because p
3 can never turn on. In other words, we will never have the R
out
+ transition. This is indicated by adding a “0” on the output arcs of R
out
+ in Figure 7.Figure 7
STG level model of stuck-at-0 fault in Line 2.If Line 9 gets stuck at 1, this will lead to Lines 3 and 5 being stuck at 0, further leading to Line 6 being stuck at 0. As Line 6 is connected to theB input of the C-element, we will have the fault manifestation similar to the case of Line 2 stuck at 0. Now, we consider a stuck-at-0 fault at Line 13. As this line is connected to the B input of the C-element C2, it will lead to output A
out never becoming 1. The effect is shown by adding a “0” to the output arcs of A
out
+ in Figure 8.Figure 8
STG level model of stuck-at-0 fault in Line 13.Now, we consider an example of a redundant fault; that is, no logical difference is observed in the operation of the circuit after fault. An instance of such a fault isn
1 stuck-on fault in C1. This fault enforces the circuit to wait only for n
2 to be enabled (i.e., B to be 1) for generating output R
out
+. As n
2 is connected to input B, which is logical ANDing of R
in
+, A
out
-, and A
in
-, R
out
+ can fire only after three transitions, namely, R
in
+ and A
out
- and A
in
- fire. It may be noted that A
out
- and A
in
- also imply that input A (connected to n
1) of C1 is 1, which in turn implies condition for n
1. As fault and normal condition both imply n
1 to be on, stuck-on fault at n
1 of C1 does not generate any behavioral difference. Obviously, such faults cannot be detected and under the single stuck-at fault assumption do not cause significant reliability issues.For the fault model considered, the total number of faults in a SI circuit having dynamic C-elements is equal to 12 times the number of C-elements (each C-element consists of 6 transistors and each transistor can have stuck-on and stuck-off faults) plus twice the number of I/O lines of the gates (each line has either stuck-at-0 or stuck-at-1 fault). So the number of faults in case of the circuit considered in Figure1 is not too small and listing them all would make a tabular representation long. So a partial list of faults and their effects on the STG is given in Table 1.Table 1
A partial list of faults and their effects on STG.
Fault type
Effect of fault on the transitions
Transistorn
1 stuck-on fault for C1
R
out+ can only be fired after R
in+, A
out−, and A
in− (the same as normal condition)
Transistorn
2 stuck-on fault for C1
R
out+ can be fired after either A
out− or A
in−
Transistorp
1 stuck-on fault for C1
R
out− can be fired after either A
out+ or A
in+
Transistorp
2 stuck-on fault for C1
R
out− can only be fired after A
out+ and A
in+
Transistorn
1 stuck-on fault for C2
A
out+ can be fired after R
in+
Transistorn
2 stuck-on fault for C2
A
out+ can be fired after R
out+
Transistorp
1 stuck-on fault for C2
A
out− can be fired after R
in−
Transistorp
2 stuck-on fault for C2
A
out− can be fired after R
out−
Transistorn
1 stuck-off fault for C1
All arcs fromR
out+ are always 0
Transistorn
2 stuck-off fault for C1
All arcs fromR
out+ are always 0
Transistorp
1 stuck-off fault for C1
All arcs fromR
out− are always 0
Transistorp
2 stuck-off fault for C1
All arcs fromR
out− are always 0
Transistorn
1 stuck-off fault for C2
All arcs fromA
out+ are always 0
Transistorn
2 stuck-off fault for C2
All arcs fromA
out+ are always 0
Transistorp
1 stuck-off fault for C2
All arcs fromA
out− are always 0
Transistorp
2 stuck-off fault for C2
All arcs fromA
out− are always 0
Transistorn
3 stuck-on fault for C1Transistor p
3 stuck-off fault for C1
All arcs fromR
out+ are always 0
Transistorp
3 stuck-on fault for C1Transistor n
3 stuck-off fault for C1
All arcs fromR
out− are always 0
Transistorp
3 stuck-on fault for C2 Transistor n
3 stuck-off fault for C2
All arcs fromA
out− are always 0
Transistorn
3 stuck-on fault for C2 Transistor p
3 stuck-off fault for C2
All arcs fromA
out+ are always 0
Stuck-at-0 fault at Line 1 or Line 2 or Line 3Stuck-at-0 fault at Line 6 or Line 7 Stuck-at-1 fault at Line 9 or Line 10
All arcs fromR
out+ are always 0
Stuck-at-0 fault at Line 4 and Line 5
All arcs fromR
out+ are always 0
Stuck-at-1 fault at Line 4 or Line 5Stuck-at-1 fault at Line 6 or Line 7Stuck-at-0 fault at Line 9 or Line 10
All arcs fromR
out− are always 0
Stuck-at-0 fault at Line 8
All arcs fromR
out+ are always 0 and all arcs from A
out+ are always 0
Stuck-at-1 fault at Line 8
All arcs fromR
out− are always 0 and all arcs from A
out− are always 0
Stuck-at-0 at Line 11
All arcs fromR
out− are always 0 and all arcs from A
out+ are always 0
Stuck-at-1 fault at Line 11
All arcs fromR
out+ are always 0 and all arcs from A
out− are always 0
Stuck-at-0 fault at Line 12 or Line 13
All arcs fromA
out+ are always 0
Stuck-at-1 fault at Line 12 or Line 13
All arcs fromA
out− are always 0


#### 3.1.2. State Graph Based Fault Modeling andFD-Transitions

As already discussed, the first step of DES based OLT design is to generate the normal and faulty models. For SI circuits, first the STGs under normal and faulty conditions are obtained and then converted into state based models. In this subsection, we explain the concept using the example circuit of Figure1 under normal condition and two faults, namely, stuck-on fault in n
1 of C2 and stuck-on fault in p
1 of C1.The state based DES model for the normal circuit is shown in Figure9. It may be noted that in the circuit there are 4 I/O signals, namely, R
in, R
out, A
in, and A
out. In the DES model corresponding to each signal, there is a discrete variable: v
1
=
R
in
,
v
2
=
R
out
,
v
3
=
A
in
,
v
4
=
A
out which assumes values from the set {
0,1
}. The set of states are X
0 to X
13 and X
0 is the initial state. State mappings and transitions are shown in Figure 9; for example, state X
0 maps variables R
in
,
R
out
,
A
in
,
A
out to 1,1
,
0,0. In states X
0 and X
1 mappings are 〈
1,1
,
0,0
〉 and 〈
1,1
,
0,1
〉, respectively. So transition from X
0 to X
1 changes A
out from 0 to 1; this is indicated by transition A
out
+. Now, if we look at the STG for the normal circuit in Figure 3 we note that A
out
+ can fire if R
in
+ and R
out
+ have a token (i.e., R
in
=
1 and R
out
=
1). In state X
0 as R
in
=
1and R
out
=
1, A
out
+ can fire. Similarly, the whole DES can be constructed.Figure 9
DES model for normal circuit (STG of Figure3).The state based DES model for the circuit undern
1 stuck-on fault in C2 is shown in Figure 10. The set of states are X
′
0 to X
′
13 and X
′
0 is the initial state. The transitions and state mapping are shown in the figure. As discussed in the previous subsection, n
1 stuck-on fault in C2 results in premature firing of A
out
+ (i.e., it need not wait for R
out
+ and can fire only if R
in
+ holds). If we observe the failure DES model in Figure 10, we note that there are two dotted transitions, which correspond to the failure condition, that is, premature firing of A
out
+. One dotted transition is between X
′
11 and X
′
6. It may be noted that in X
′
11 we have R
in
=
1, R
out
=
0, A
in
=
1, and A
out
=
0, where even though R
out
+ is not enabled, because R
in
+ is enabled, A
out
+ fires. A similar premature firing of A
out
+ occurs between X
′
13 and X
′
8. So, for the fault n
1 stuck-on fault in C2, there are two FD-transitions, namely, 〈
X
′
11
,
X
′
6
〉 and 〈
X
′
13
,
X
′
8
〉.Figure 10
DES model for circuit withn
1 stuck-on fault in C2 (STG of Figure 4).The state based DES model for the circuit underp
1 stuck-on fault in C1 is shown in Figure 11. The set of states are X
′′
0 to X
′′
13 and X
′′
0 is the initial state. As discussed in the previous subsection, p
1 stuck-on fault in C1 results in premature firing of R
out
- triggered by either A
in
+ or A
out
+. This is captured by the dotted transitions 〈
X
′′
2
,
X
′′
11
〉 and 〈
X
′′
1
,
X
′′
8
〉 in failure DES model in Figure 11. The transition 〈
X
′′
2
,
X
′′
11
〉 represents firing of R
out
- by A
in
+ in spite of A
out
+ not being enabled and the transition 〈
X
′′
1
,
X
′′
8
〉 represents firing of R
out
- by A
out
+ in spite of A
in
+ not being enabled. Thus, for this fault there are two FD-transitions, namely, 〈
X
′′
2
,
X
′′
11
〉 and 〈
X
′′
1
,
X
′′
8
〉.Figure 11
DES model for circuit withp
1 stuck-on fault in C1 (STGs of Figure 5).The set ofFD-transitions is shown in Table 2.Table 2
FD-transitions.
FD-transitions
Start state
Final state
Effect
1
0001
0101
Premature fire ofR
out+ before R
in+ (by A
in−)
2
0000
0100
Premature fire ofR
out+ before R
in+ (by A
in−)
3
1110
1010
Premature fire ofR
out− before A
out+ (by A
in+)
4
1010
1011
Premature fire ofA
out+ before R
out+ (by R
in+)
5
1000
1001
Premature fire ofA
out+ before R
out+ (by R
in+)
6
0111
0110
Premature fire ofA
out− before R
out− (by R
in−)
7
0101
0100
Premature fire ofA
out− before R
out− (by R
in−)
8
1011
1010
Premature fire ofA
out− before R
in− (by R
out−)
9
1001
1000
Premature fire ofA
out− before R
in− (by R
out−)
10
1101
1001
Premature fire ofR
out− before A
in+ (by A
out+)In the next section, we will discuss the procedure for design of the DES detector fromFD-transitions and its synthesis as a SI circuit.


## 3.1. Fault Modeling

The SI asynchronous CUT example being considered to illustrate the proposed scheme is shown in Figure1 (taken from [22]). Traditionally, synchronous circuits consist of blocks of combinational logic connected with clocked latches or registers, while, in case of SI circuit designs, we basically have logic gates as building blocks with C-elements, which act as storage elements. Transistor level diagram of C-element is shown in Figure 2; logic function of the C-element can be described by the Boolean equation C
=
A
B
+
A
C
′
+
B
C
′, where C is the next state and C
′ is the old state value [22, 23]. The output of C-element becomes logically high (low) when both the inputs are logically high (low); otherwise it keeps its previous logic value. There are two types of C-elements used in SI circuits: static C-element and dynamic C-element. The static version of C-element promises that the information inside it can be stored for unbounded periods. However, dynamic versions of C-element provide gains in terms of area, power, and delay [23–26]. Since the circuits having high operating speed, low area, and power consumption are preferred in modern days, we have chosen SI circuits with dynamic C-elements instead of static ones.Figure 1
Example of speed independent asynchronous CUT.Figure 2
Transistor diagram of dynamic C-element.Figure3 shows the STG for the CUT being considered. Rising (falling) transitions on signals, indicated by + (−), are shown in the STG. The dark circles along the arcs are called tokens. The token indicates one of possibly a set of signals that enable transition to fire. If all input arcs for a signal transition have tokens then that signal transition is said to be enabled. For example, when signal R
in goes high (denoted by R
in
+) and R
out goes high (denoted by R
out
+), only then A
out
+ transition can take place. Upon firing A
out
+, a token is placed on each of its outgoing arcs, thus enabling R
in
-. Note that R
out
- is enabled after A
out
+ and A
in
+.Figure 3
Signal transition graph of sample circuit.In this paper, we have considered SI circuits that contain C-elements (we assumed dynamic version) and logic gates. For the logic gates, the most popular fault model is the stuck-at fault model, which is at the gate level. However, for the C-elements stuck-on and stuck-off faults for each transistor are an accepted fault model [22]. So we have chosen a mixed gate/transistor level description for modeling the faults. To illustrate fault modeling at both C-elements and basic gates, we consider the circuit example from [22] which is shown in Figure 1.


### 3.1.1. STG Based Modeling

In this work, we model single stuck-at faults in the gates and transistors (for the C-elements) and map them to STGs of the circuit. For the analysis, the signals attached to the inputsA and B of the C-elements are also indicated in the gate level circuit diagram of Figure 1. Now, we consider some of these faults (one at a time), analyze their effects, and finally modify the STG to model the faults.Consider the C-element C2 of Figure1 and refer to transistor level circuit of Figure 2. The C-element C2 has R
out and R
in as inputs and A
out as output. If the transistor n
1 has a stuck-on fault, this leads to error in the circuit that it needs to wait for only n
2 to be enabled to generate output. When n
2 turns on, then a path to ground via n
1 and n
2 gets established, which makes p
3 on and n
3 off, making C high. So C2 has to wait only for n
2 (i.e., R
in
+ which corresponds to input B of C2 to become 1) to turn on and change the output. In other words, it has to wait for only R
in
+ (and not also for R
out
+, which is the requirement under normal condition) before it can generate A
out
+. Thus, the fault in n
1 leads to premature firing of the A
out
+ transition. We represent this by including a token on the arc connecting R
out
+ to A
out
+. Availability of this token will enable A
out
+ to fire as soon as R
in
+ arrives, without waiting for R
out
+. This token is denoted by a “1” shown on the arc in Figure 4.Figure 4
STG level model of stuck-on faultn
1 of C2 [22].Now, consider C-element C1 producing outputR
out, with transistor p
1 having stuck-on fault. As p
1 is on, the gate has to wait for p
2 to turn on before it can change the output. When p
2 turns on (by virtue of B
=
0) then there is no path to ground as n
2 is off, which makes p
3 off and n
3 on, making C low. Here, C1 has to wait for the input B
=
0 to generate R
out
-. Referring to Figure 1, for B to become 0, we need either A
out to become 1 (the same as R
in becoming 0) or A
in to become 1. Thus, as soon as we have either A
out
+ or A
in
+, R
out
- would fire. It may be noted that, under normal condition, for R
out
- to fire, we also require A
=
0, which mandates both A
out
+ and A
in
+. This failure condition is indicated in the STG by adding a “1” to the input arcs of R
out
-, which is shown in Figure 5. To elaborate, Figure 5(a) (Figure 5(b)) shows that R
out
- can be fired as soon as A
in
+ (A
out
+) fires and does not wait for A
out
+ (A
in
+).Figure 5
STG level model of stuck-on fault inp
1 of C1 [22].
(a)
R
out
- does not wait for A
out
+
(b)
R
out
- does not wait for A
in
+As the third fault, let C1 have stuck-on fault atn
2. The stuck-on fault at n
2 enforces the circuit to wait only for n
1 to be enabled for generating output R
out
+. As n
1 is connected to input A, which is logical ORing of A
out
- and A
in
-, transition R
out
+ can fire after A
out
- or A
in
- (without requiring to wait for R
in
+). This premature firing of transition R
out
+ is indicated in the STG by adding a “1” to R
in
+, which is shown in Figure 6.Figure 6
STG level model of stuck-on faultn
2 of C1 [22].For the gates, stuck-at-0 and stuck-at-1 faults are considered at their inputs and output nets. Let Line 2 of the AND gate from Figure1 have a stuck-at-0 fault. This makes Line 6 stuck-at-0 fault. As Line 6 is connected to the B input of the C-element C1, we have transistor p
2 on and transistor n
2 off. Note that as n
2 is always off, there is no path to the ground. So the output R
out can never become 1 because p
3 can never turn on. In other words, we will never have the R
out
+ transition. This is indicated by adding a “0” on the output arcs of R
out
+ in Figure 7.Figure 7
STG level model of stuck-at-0 fault in Line 2.If Line 9 gets stuck at 1, this will lead to Lines 3 and 5 being stuck at 0, further leading to Line 6 being stuck at 0. As Line 6 is connected to theB input of the C-element, we will have the fault manifestation similar to the case of Line 2 stuck at 0. Now, we consider a stuck-at-0 fault at Line 13. As this line is connected to the B input of the C-element C2, it will lead to output A
out never becoming 1. The effect is shown by adding a “0” to the output arcs of A
out
+ in Figure 8.Figure 8
STG level model of stuck-at-0 fault in Line 13.Now, we consider an example of a redundant fault; that is, no logical difference is observed in the operation of the circuit after fault. An instance of such a fault isn
1 stuck-on fault in C1. This fault enforces the circuit to wait only for n
2 to be enabled (i.e., B to be 1) for generating output R
out
+. As n
2 is connected to input B, which is logical ANDing of R
in
+, A
out
-, and A
in
-, R
out
+ can fire only after three transitions, namely, R
in
+ and A
out
- and A
in
- fire. It may be noted that A
out
- and A
in
- also imply that input A (connected to n
1) of C1 is 1, which in turn implies condition for n
1. As fault and normal condition both imply n
1 to be on, stuck-on fault at n
1 of C1 does not generate any behavioral difference. Obviously, such faults cannot be detected and under the single stuck-at fault assumption do not cause significant reliability issues.For the fault model considered, the total number of faults in a SI circuit having dynamic C-elements is equal to 12 times the number of C-elements (each C-element consists of 6 transistors and each transistor can have stuck-on and stuck-off faults) plus twice the number of I/O lines of the gates (each line has either stuck-at-0 or stuck-at-1 fault). So the number of faults in case of the circuit considered in Figure1 is not too small and listing them all would make a tabular representation long. So a partial list of faults and their effects on the STG is given in Table 1.Table 1
A partial list of faults and their effects on STG.
Fault type
Effect of fault on the transitions
Transistorn
1 stuck-on fault for C1
R
out+ can only be fired after R
in+, A
out−, and A
in− (the same as normal condition)
Transistorn
2 stuck-on fault for C1
R
out+ can be fired after either A
out− or A
in−
Transistorp
1 stuck-on fault for C1
R
out− can be fired after either A
out+ or A
in+
Transistorp
2 stuck-on fault for C1
R
out− can only be fired after A
out+ and A
in+
Transistorn
1 stuck-on fault for C2
A
out+ can be fired after R
in+
Transistorn
2 stuck-on fault for C2
A
out+ can be fired after R
out+
Transistorp
1 stuck-on fault for C2
A
out− can be fired after R
in−
Transistorp
2 stuck-on fault for C2
A
out− can be fired after R
out−
Transistorn
1 stuck-off fault for C1
All arcs fromR
out+ are always 0
Transistorn
2 stuck-off fault for C1
All arcs fromR
out+ are always 0
Transistorp
1 stuck-off fault for C1
All arcs fromR
out− are always 0
Transistorp
2 stuck-off fault for C1
All arcs fromR
out− are always 0
Transistorn
1 stuck-off fault for C2
All arcs fromA
out+ are always 0
Transistorn
2 stuck-off fault for C2
All arcs fromA
out+ are always 0
Transistorp
1 stuck-off fault for C2
All arcs fromA
out− are always 0
Transistorp
2 stuck-off fault for C2
All arcs fromA
out− are always 0
Transistorn
3 stuck-on fault for C1Transistor p
3 stuck-off fault for C1
All arcs fromR
out+ are always 0
Transistorp
3 stuck-on fault for C1Transistor n
3 stuck-off fault for C1
All arcs fromR
out− are always 0
Transistorp
3 stuck-on fault for C2 Transistor n
3 stuck-off fault for C2
All arcs fromA
out− are always 0
Transistorn
3 stuck-on fault for C2 Transistor p
3 stuck-off fault for C2
All arcs fromA
out+ are always 0
Stuck-at-0 fault at Line 1 or Line 2 or Line 3Stuck-at-0 fault at Line 6 or Line 7 Stuck-at-1 fault at Line 9 or Line 10
All arcs fromR
out+ are always 0
Stuck-at-0 fault at Line 4 and Line 5
All arcs fromR
out+ are always 0
Stuck-at-1 fault at Line 4 or Line 5Stuck-at-1 fault at Line 6 or Line 7Stuck-at-0 fault at Line 9 or Line 10
All arcs fromR
out− are always 0
Stuck-at-0 fault at Line 8
All arcs fromR
out+ are always 0 and all arcs from A
out+ are always 0
Stuck-at-1 fault at Line 8
All arcs fromR
out− are always 0 and all arcs from A
out− are always 0
Stuck-at-0 at Line 11
All arcs fromR
out− are always 0 and all arcs from A
out+ are always 0
Stuck-at-1 fault at Line 11
All arcs fromR
out+ are always 0 and all arcs from A
out− are always 0
Stuck-at-0 fault at Line 12 or Line 13
All arcs fromA
out+ are always 0
Stuck-at-1 fault at Line 12 or Line 13
All arcs fromA
out− are always 0


### 3.1.2. State Graph Based Fault Modeling andFD-Transitions

As already discussed, the first step of DES based OLT design is to generate the normal and faulty models. For SI circuits, first the STGs under normal and faulty conditions are obtained and then converted into state based models. In this subsection, we explain the concept using the example circuit of Figure1 under normal condition and two faults, namely, stuck-on fault in n
1 of C2 and stuck-on fault in p
1 of C1.The state based DES model for the normal circuit is shown in Figure9. It may be noted that in the circuit there are 4 I/O signals, namely, R
in, R
out, A
in, and A
out. In the DES model corresponding to each signal, there is a discrete variable: v
1
=
R
in
,
v
2
=
R
out
,
v
3
=
A
in
,
v
4
=
A
out which assumes values from the set {
0,1
}. The set of states are X
0 to X
13 and X
0 is the initial state. State mappings and transitions are shown in Figure 9; for example, state X
0 maps variables R
in
,
R
out
,
A
in
,
A
out to 1,1
,
0,0. In states X
0 and X
1 mappings are 〈
1,1
,
0,0
〉 and 〈
1,1
,
0,1
〉, respectively. So transition from X
0 to X
1 changes A
out from 0 to 1; this is indicated by transition A
out
+. Now, if we look at the STG for the normal circuit in Figure 3 we note that A
out
+ can fire if R
in
+ and R
out
+ have a token (i.e., R
in
=
1 and R
out
=
1). In state X
0 as R
in
=
1and R
out
=
1, A
out
+ can fire. Similarly, the whole DES can be constructed.Figure 9
DES model for normal circuit (STG of Figure3).The state based DES model for the circuit undern
1 stuck-on fault in C2 is shown in Figure 10. The set of states are X
′
0 to X
′
13 and X
′
0 is the initial state. The transitions and state mapping are shown in the figure. As discussed in the previous subsection, n
1 stuck-on fault in C2 results in premature firing of A
out
+ (i.e., it need not wait for R
out
+ and can fire only if R
in
+ holds). If we observe the failure DES model in Figure 10, we note that there are two dotted transitions, which correspond to the failure condition, that is, premature firing of A
out
+. One dotted transition is between X
′
11 and X
′
6. It may be noted that in X
′
11 we have R
in
=
1, R
out
=
0, A
in
=
1, and A
out
=
0, where even though R
out
+ is not enabled, because R
in
+ is enabled, A
out
+ fires. A similar premature firing of A
out
+ occurs between X
′
13 and X
′
8. So, for the fault n
1 stuck-on fault in C2, there are two FD-transitions, namely, 〈
X
′
11
,
X
′
6
〉 and 〈
X
′
13
,
X
′
8
〉.Figure 10
DES model for circuit withn
1 stuck-on fault in C2 (STG of Figure 4).The state based DES model for the circuit underp
1 stuck-on fault in C1 is shown in Figure 11. The set of states are X
′′
0 to X
′′
13 and X
′′
0 is the initial state. As discussed in the previous subsection, p
1 stuck-on fault in C1 results in premature firing of R
out
- triggered by either A
in
+ or A
out
+. This is captured by the dotted transitions 〈
X
′′
2
,
X
′′
11
〉 and 〈
X
′′
1
,
X
′′
8
〉 in failure DES model in Figure 11. The transition 〈
X
′′
2
,
X
′′
11
〉 represents firing of R
out
- by A
in
+ in spite of A
out
+ not being enabled and the transition 〈
X
′′
1
,
X
′′
8
〉 represents firing of R
out
- by A
out
+ in spite of A
in
+ not being enabled. Thus, for this fault there are two FD-transitions, namely, 〈
X
′′
2
,
X
′′
11
〉 and 〈
X
′′
1
,
X
′′
8
〉.Figure 11
DES model for circuit withp
1 stuck-on fault in C1 (STGs of Figure 5).The set ofFD-transitions is shown in Table 2.Table 2
FD-transitions.
FD-transitions
Start state
Final state
Effect
1
0001
0101
Premature fire ofR
out+ before R
in+ (by A
in−)
2
0000
0100
Premature fire ofR
out+ before R
in+ (by A
in−)
3
1110
1010
Premature fire ofR
out− before A
out+ (by A
in+)
4
1010
1011
Premature fire ofA
out+ before R
out+ (by R
in+)
5
1000
1001
Premature fire ofA
out+ before R
out+ (by R
in+)
6
0111
0110
Premature fire ofA
out− before R
out− (by R
in−)
7
0101
0100
Premature fire ofA
out− before R
out− (by R
in−)
8
1011
1010
Premature fire ofA
out− before R
in− (by R
out−)
9
1001
1000
Premature fire ofA
out− before R
in− (by R
out−)
10
1101
1001
Premature fire ofR
out− before A
in+ (by A
out+)In the next section, we will discuss the procedure for design of the DES detector fromFD-transitions and its synthesis as a SI circuit.


## 3.1.1. STG Based Modeling

In this work, we model single stuck-at faults in the gates and transistors (for the C-elements) and map them to STGs of the circuit. For the analysis, the signals attached to the inputsA and B of the C-elements are also indicated in the gate level circuit diagram of Figure 1. Now, we consider some of these faults (one at a time), analyze their effects, and finally modify the STG to model the faults.Consider the C-element C2 of Figure1 and refer to transistor level circuit of Figure 2. The C-element C2 has R
out and R
in as inputs and A
out as output. If the transistor n
1 has a stuck-on fault, this leads to error in the circuit that it needs to wait for only n
2 to be enabled to generate output. When n
2 turns on, then a path to ground via n
1 and n
2 gets established, which makes p
3 on and n
3 off, making C high. So C2 has to wait only for n
2 (i.e., R
in
+ which corresponds to input B of C2 to become 1) to turn on and change the output. In other words, it has to wait for only R
in
+ (and not also for R
out
+, which is the requirement under normal condition) before it can generate A
out
+. Thus, the fault in n
1 leads to premature firing of the A
out
+ transition. We represent this by including a token on the arc connecting R
out
+ to A
out
+. Availability of this token will enable A
out
+ to fire as soon as R
in
+ arrives, without waiting for R
out
+. This token is denoted by a “1” shown on the arc in Figure 4.Figure 4
STG level model of stuck-on faultn
1 of C2 [22].Now, consider C-element C1 producing outputR
out, with transistor p
1 having stuck-on fault. As p
1 is on, the gate has to wait for p
2 to turn on before it can change the output. When p
2 turns on (by virtue of B
=
0) then there is no path to ground as n
2 is off, which makes p
3 off and n
3 on, making C low. Here, C1 has to wait for the input B
=
0 to generate R
out
-. Referring to Figure 1, for B to become 0, we need either A
out to become 1 (the same as R
in becoming 0) or A
in to become 1. Thus, as soon as we have either A
out
+ or A
in
+, R
out
- would fire. It may be noted that, under normal condition, for R
out
- to fire, we also require A
=
0, which mandates both A
out
+ and A
in
+. This failure condition is indicated in the STG by adding a “1” to the input arcs of R
out
-, which is shown in Figure 5. To elaborate, Figure 5(a) (Figure 5(b)) shows that R
out
- can be fired as soon as A
in
+ (A
out
+) fires and does not wait for A
out
+ (A
in
+).Figure 5
STG level model of stuck-on fault inp
1 of C1 [22].
(a)
R
out
- does not wait for A
out
+
(b)
R
out
- does not wait for A
in
+As the third fault, let C1 have stuck-on fault atn
2. The stuck-on fault at n
2 enforces the circuit to wait only for n
1 to be enabled for generating output R
out
+. As n
1 is connected to input A, which is logical ORing of A
out
- and A
in
-, transition R
out
+ can fire after A
out
- or A
in
- (without requiring to wait for R
in
+). This premature firing of transition R
out
+ is indicated in the STG by adding a “1” to R
in
+, which is shown in Figure 6.Figure 6
STG level model of stuck-on faultn
2 of C1 [22].For the gates, stuck-at-0 and stuck-at-1 faults are considered at their inputs and output nets. Let Line 2 of the AND gate from Figure1 have a stuck-at-0 fault. This makes Line 6 stuck-at-0 fault. As Line 6 is connected to the B input of the C-element C1, we have transistor p
2 on and transistor n
2 off. Note that as n
2 is always off, there is no path to the ground. So the output R
out can never become 1 because p
3 can never turn on. In other words, we will never have the R
out
+ transition. This is indicated by adding a “0” on the output arcs of R
out
+ in Figure 7.Figure 7
STG level model of stuck-at-0 fault in Line 2.If Line 9 gets stuck at 1, this will lead to Lines 3 and 5 being stuck at 0, further leading to Line 6 being stuck at 0. As Line 6 is connected to theB input of the C-element, we will have the fault manifestation similar to the case of Line 2 stuck at 0. Now, we consider a stuck-at-0 fault at Line 13. As this line is connected to the B input of the C-element C2, it will lead to output A
out never becoming 1. The effect is shown by adding a “0” to the output arcs of A
out
+ in Figure 8.Figure 8
STG level model of stuck-at-0 fault in Line 13.Now, we consider an example of a redundant fault; that is, no logical difference is observed in the operation of the circuit after fault. An instance of such a fault isn
1 stuck-on fault in C1. This fault enforces the circuit to wait only for n
2 to be enabled (i.e., B to be 1) for generating output R
out
+. As n
2 is connected to input B, which is logical ANDing of R
in
+, A
out
-, and A
in
-, R
out
+ can fire only after three transitions, namely, R
in
+ and A
out
- and A
in
- fire. It may be noted that A
out
- and A
in
- also imply that input A (connected to n
1) of C1 is 1, which in turn implies condition for n
1. As fault and normal condition both imply n
1 to be on, stuck-on fault at n
1 of C1 does not generate any behavioral difference. Obviously, such faults cannot be detected and under the single stuck-at fault assumption do not cause significant reliability issues.For the fault model considered, the total number of faults in a SI circuit having dynamic C-elements is equal to 12 times the number of C-elements (each C-element consists of 6 transistors and each transistor can have stuck-on and stuck-off faults) plus twice the number of I/O lines of the gates (each line has either stuck-at-0 or stuck-at-1 fault). So the number of faults in case of the circuit considered in Figure1 is not too small and listing them all would make a tabular representation long. So a partial list of faults and their effects on the STG is given in Table 1.Table 1
A partial list of faults and their effects on STG.
Fault type
Effect of fault on the transitions
Transistorn
1 stuck-on fault for C1
R
out+ can only be fired after R
in+, A
out−, and A
in− (the same as normal condition)
Transistorn
2 stuck-on fault for C1
R
out+ can be fired after either A
out− or A
in−
Transistorp
1 stuck-on fault for C1
R
out− can be fired after either A
out+ or A
in+
Transistorp
2 stuck-on fault for C1
R
out− can only be fired after A
out+ and A
in+
Transistorn
1 stuck-on fault for C2
A
out+ can be fired after R
in+
Transistorn
2 stuck-on fault for C2
A
out+ can be fired after R
out+
Transistorp
1 stuck-on fault for C2
A
out− can be fired after R
in−
Transistorp
2 stuck-on fault for C2
A
out− can be fired after R
out−
Transistorn
1 stuck-off fault for C1
All arcs fromR
out+ are always 0
Transistorn
2 stuck-off fault for C1
All arcs fromR
out+ are always 0
Transistorp
1 stuck-off fault for C1
All arcs fromR
out− are always 0
Transistorp
2 stuck-off fault for C1
All arcs fromR
out− are always 0
Transistorn
1 stuck-off fault for C2
All arcs fromA
out+ are always 0
Transistorn
2 stuck-off fault for C2
All arcs fromA
out+ are always 0
Transistorp
1 stuck-off fault for C2
All arcs fromA
out− are always 0
Transistorp
2 stuck-off fault for C2
All arcs fromA
out− are always 0
Transistorn
3 stuck-on fault for C1Transistor p
3 stuck-off fault for C1
All arcs fromR
out+ are always 0
Transistorp
3 stuck-on fault for C1Transistor n
3 stuck-off fault for C1
All arcs fromR
out− are always 0
Transistorp
3 stuck-on fault for C2 Transistor n
3 stuck-off fault for C2
All arcs fromA
out− are always 0
Transistorn
3 stuck-on fault for C2 Transistor p
3 stuck-off fault for C2
All arcs fromA
out+ are always 0
Stuck-at-0 fault at Line 1 or Line 2 or Line 3Stuck-at-0 fault at Line 6 or Line 7 Stuck-at-1 fault at Line 9 or Line 10
All arcs fromR
out+ are always 0
Stuck-at-0 fault at Line 4 and Line 5
All arcs fromR
out+ are always 0
Stuck-at-1 fault at Line 4 or Line 5Stuck-at-1 fault at Line 6 or Line 7Stuck-at-0 fault at Line 9 or Line 10
All arcs fromR
out− are always 0
Stuck-at-0 fault at Line 8
All arcs fromR
out+ are always 0 and all arcs from A
out+ are always 0
Stuck-at-1 fault at Line 8
All arcs fromR
out− are always 0 and all arcs from A
out− are always 0
Stuck-at-0 at Line 11
All arcs fromR
out− are always 0 and all arcs from A
out+ are always 0
Stuck-at-1 fault at Line 11
All arcs fromR
out+ are always 0 and all arcs from A
out− are always 0
Stuck-at-0 fault at Line 12 or Line 13
All arcs fromA
out+ are always 0
Stuck-at-1 fault at Line 12 or Line 13
All arcs fromA
out− are always 0


## 3.1.2. State Graph Based Fault Modeling andFD-Transitions

As already discussed, the first step of DES based OLT design is to generate the normal and faulty models. For SI circuits, first the STGs under normal and faulty conditions are obtained and then converted into state based models. In this subsection, we explain the concept using the example circuit of Figure1 under normal condition and two faults, namely, stuck-on fault in n
1 of C2 and stuck-on fault in p
1 of C1.The state based DES model for the normal circuit is shown in Figure9. It may be noted that in the circuit there are 4 I/O signals, namely, R
in, R
out, A
in, and A
out. In the DES model corresponding to each signal, there is a discrete variable: v
1
=
R
in
,
v
2
=
R
out
,
v
3
=
A
in
,
v
4
=
A
out which assumes values from the set {
0,1
}. The set of states are X
0 to X
13 and X
0 is the initial state. State mappings and transitions are shown in Figure 9; for example, state X
0 maps variables R
in
,
R
out
,
A
in
,
A
out to 1,1
,
0,0. In states X
0 and X
1 mappings are 〈
1,1
,
0,0
〉 and 〈
1,1
,
0,1
〉, respectively. So transition from X
0 to X
1 changes A
out from 0 to 1; this is indicated by transition A
out
+. Now, if we look at the STG for the normal circuit in Figure 3 we note that A
out
+ can fire if R
in
+ and R
out
+ have a token (i.e., R
in
=
1 and R
out
=
1). In state X
0 as R
in
=
1and R
out
=
1, A
out
+ can fire. Similarly, the whole DES can be constructed.Figure 9
DES model for normal circuit (STG of Figure3).The state based DES model for the circuit undern
1 stuck-on fault in C2 is shown in Figure 10. The set of states are X
′
0 to X
′
13 and X
′
0 is the initial state. The transitions and state mapping are shown in the figure. As discussed in the previous subsection, n
1 stuck-on fault in C2 results in premature firing of A
out
+ (i.e., it need not wait for R
out
+ and can fire only if R
in
+ holds). If we observe the failure DES model in Figure 10, we note that there are two dotted transitions, which correspond to the failure condition, that is, premature firing of A
out
+. One dotted transition is between X
′
11 and X
′
6. It may be noted that in X
′
11 we have R
in
=
1, R
out
=
0, A
in
=
1, and A
out
=
0, where even though R
out
+ is not enabled, because R
in
+ is enabled, A
out
+ fires. A similar premature firing of A
out
+ occurs between X
′
13 and X
′
8. So, for the fault n
1 stuck-on fault in C2, there are two FD-transitions, namely, 〈
X
′
11
,
X
′
6
〉 and 〈
X
′
13
,
X
′
8
〉.Figure 10
DES model for circuit withn
1 stuck-on fault in C2 (STG of Figure 4).The state based DES model for the circuit underp
1 stuck-on fault in C1 is shown in Figure 11. The set of states are X
′′
0 to X
′′
13 and X
′′
0 is the initial state. As discussed in the previous subsection, p
1 stuck-on fault in C1 results in premature firing of R
out
- triggered by either A
in
+ or A
out
+. This is captured by the dotted transitions 〈
X
′′
2
,
X
′′
11
〉 and 〈
X
′′
1
,
X
′′
8
〉 in failure DES model in Figure 11. The transition 〈
X
′′
2
,
X
′′
11
〉 represents firing of R
out
- by A
in
+ in spite of A
out
+ not being enabled and the transition 〈
X
′′
1
,
X
′′
8
〉 represents firing of R
out
- by A
out
+ in spite of A
in
+ not being enabled. Thus, for this fault there are two FD-transitions, namely, 〈
X
′′
2
,
X
′′
11
〉 and 〈
X
′′
1
,
X
′′
8
〉.Figure 11
DES model for circuit withp
1 stuck-on fault in C1 (STGs of Figure 5).The set ofFD-transitions is shown in Table 2.Table 2
FD-transitions.
FD-transitions
Start state
Final state
Effect
1
0001
0101
Premature fire ofR
out+ before R
in+ (by A
in−)
2
0000
0100
Premature fire ofR
out+ before R
in+ (by A
in−)
3
1110
1010
Premature fire ofR
out− before A
out+ (by A
in+)
4
1010
1011
Premature fire ofA
out+ before R
out+ (by R
in+)
5
1000
1001
Premature fire ofA
out+ before R
out+ (by R
in+)
6
0111
0110
Premature fire ofA
out− before R
out− (by R
in−)
7
0101
0100
Premature fire ofA
out− before R
out− (by R
in−)
8
1011
1010
Premature fire ofA
out− before R
in− (by R
out−)
9
1001
1000
Premature fire ofA
out− before R
in− (by R
out−)
10
1101
1001
Premature fire ofR
out− before A
in+ (by A
out+)In the next section, we will discuss the procedure for design of the DES detector fromFD-transitions and its synthesis as a SI circuit.


## 4. DES Detector Based Online Tester

A DES detector is basically a state estimator which predicts whether the Circuit Under Test (CUT) traverses through normal or faulty states/transitions. Broadly speaking, the detector is constructed using transitions which can manifest the fault effects. In other words, such a transition is a faulty transition for which there is no corresponding equivalent normal transition. As already mentioned, we call such transitions failure detecting transitions (i.e.,FD-transitions). In the circuit under consideration, comparing the normal (Figure 9) and n
1 stuck-on fault at C2 DES models (Figure 10), we may note that there are two transitions (dotted) X
′
11
,
X
′
6 and X
′
13
,
X
′
8 which manifest the fault effect. Corresponding to these transitions, there are no equivalent transitions in the normal model. These two transitions are FD-transitions for the fault and are used in DES detector construction.If the CUT is a synchronous circuit then obviously the online tester is also a synchronous circuit that can be designed from theFD-transitions using straightforward FSM synthesis philosophy [18, 19]. The detector FSM has three classes of states, namely, initial, intermediate, and final. The detector measures the I/O signals of the CUT (i.e., variables) to determine whether the following happens.On startup the detector is in its initial state and it checks whether the CUT is in the initial state of anyFD-transition. For example, if we consider only two faults in the circuit under consideration, stuck-on fault in n
1 of C2 and stuck-on fault in p
1 of C1, then the FD-transition set is X
′
11
,
X
′
6
,
X
′
13
,
X
′
8
,
X
′′
2
,
X
′′
11. So in the initial state the detector checks whether the signals R
in, R
out, A
in, and A
out are 1, 0, 1, and 0 or 1, 0, 0, and 0 or 1, 1, 1, and 0. If so, the detector moves to an intermediate state (in the next clock edge) corresponding to the value matched. For each of the FD-transitions, there is a corresponding intermediate state in the detector. For example, if R
in, R
out, A
in, and A
out are measured to be 1, 0, 1, and 0 in the initial state of the detector, the detector moves to the intermediate state corresponding to FD-transition X
′
11
,
X
′
6. However, if the signals do not match initial state of any FD-transition the detector loops in the initial state. In the intermediate state whether the values of the signals of the CUT match with the final state of the corresponding FD-transition is checked; if so, the fault is detected and the detector moves to the final state and is deadlocked there. Otherwise, it moves to the initial state. Continuing with the example, if the values of R
in, R
out, A
in, and A
out are 1, 0, 1, and 1 from the intermediate state, FD-transition X
′
11
,
X
′
6 is detected (i.e., stuck-on fault in n
1 of C2) and detector moves to final state in the next clock edge. Otherwise, if R
in, R
out, A
in, and A
out are 1, 0, 0, and 0 then CUT is normal and the detector moves to the initial state.The above mentioned philosophy of constructing the detector and then synthesizing it into a synchronous system is widely used in the DES theory [17] and has been applied for OLT of synchronous circuits [18, 19]. Obviously, if the CUT is an asynchronous circuit and so must be the detector circuit. However, it may be noted that the same philosophy cannot be directly used in the case of SI circuits. The reason is that the FSM of the detector designed above has liveness issue in the final state and has complete state coding (CSC) violations in the intermediate states.Now we propose a new technique for detector design which can be synthesized as a SI circuit. The detector is designed as state graph model which is live and has complete state encoding, that ensures its synthesizability as a SI circuit. Before formalizing the algorithm for the design of the state graph of the detector, we first introduce the basic philosophy of its working using the examples from the previous section.AnFD-transition in SI circuit design paradigm can be stated as, “under failure, a signal s can change in the presence of signals y
1
,
y
2
,
…
,
y
n, (1
≤
n) which is not possible under normal condition.” For example, in the case of n
1 of C2 stuck-on fault, X
′
11
,
X
′
6 is an FD-transition which changes signal A
out from 0 to 1 (i.e., A
out
+) and the other signals are R
in
=
1, R
out
=
0, and A
in
=
1 (Figure 10). It may be noted that in normal condition for changing A
out from 0 to 1 we need R
in
=
1, R
out
=
1, and A
in
=
0 (Figure 9). Comparing with the faulty condition we may state that, “under n
1 of C2 stuck-on fault, signal A
out can change from 0 to 1 in presence of signals R
in
=
1, R
out
=
0, and A
in
=
1 which is not possible under normal condition.” So, to detect whether FD-transition X
′
11
,
X
′
6 has occurred, the detector needs to tap lines R
out, A
in, and A
out (R
in is not required to be monitored as its value is same under normal and faulty case) of the CUT and determine whether A
out
+ has fired and at that time whether R
out
=
0 or A
in
=
1 or both; if so, a status output line is made 1. For optimization of the detector in terms of number of states, tap lines, and so forth, without loss of fault detection capability, we may consider checking A
out
+ in presence of either R
out
=
0 or A
in
=
1 but not both. If we consider the other FD-transition X
′
13
,
X
′
8 for the fault, it can be detected by checking whether A
out
+ has fired and at that time whether R
out
=
0; R
in and A
in are not required to be monitored as their values are the same under normal and faulty case. So, it may be stated that to detect the fault by FD-transitions X
′
11
,
X
′
6 and X
′
13
,
X
′
8 we need to check whether A
out
+ has fired and at that time whether R
out
=
0. The design and flow of the detector for these two FD-transitions are as follows:(
1
)
The state encoding tuple isR
out
,
A
out
,
S
t
a
t
u
s. The initial state of the detector d
0 is encoded as 100. The first two bits represent the complement of R
out
=
0 and A
out
=
1, that is, complement of value of R
out in state X
′
11 and complement of change of A
out by the FD-transition. The third bit represents S
t
a
t
u
s output of the detector which is 0 until FD-transition is detected.
(
2
)
The detector waits for signalR
out to become 0 and if so it moves to state d
1  say, which is encoded as 〈
000
〉. However, from state d
0, if A
out becomes 1, FD-transition cannot be detected because this is normal situation (state X
0 in Figure 9) where A
out
+ fires when R
out
=
1; detector moves to state d
5 having encoding  110. When A
out becomes 0 in state d
5, the detector moves back to d
0 from where it again waits to detect whether the FD-transition occurs.
(
3
)
From stated
1 the following may happen:
(
a
)
IfR
out becomes 1, then FD-transition cannot be detected and so the detector moves back to d
0.
(
b
)
IfA
out becomes 1, then FD-transition and hence fault are detected. The detector moves to state d
2 having encoding  010. Following that detector makes S
t
a
t
u
s output high and moves to state d
3 with encoding 011.
Onces
t
a
t
u
s line is 1, that is, fault is detected online, the system should switch to an alternative backup circuit, as under the single stuck-at fault model faults are assumed to be permanent [22]. By that logic, the detector should stop or loop in d
3 indefinitely; however, it would lead to deadlock and is nonsynthesizable as a SI circuit. To avoid this deadlock, a simple modification is made in the detector state graph without affecting the fault detection performance. We wait at state d
3 for any signal to change (i.e., R
out from 0 to 1 or A
out from 1 to 0) and we move to state d
4; let us select R
out for this purpose. State encoding of d
4 is 111. From state d
4 we have a transition to state d
3 on change of R
out from 1 to 0.Figure12 illustrates the state graph for detecting n
1 stuck-on fault at C2 by FD-transitions X
′
11
,
X
′
6 and X
′
13
,
X
′
8.Figure 12
State graph for detectingFD-transitions X
′
11
,
X
′
6 and X
′
13
,
X
′
8.In similar way we can design detectors for the otherFD-transitions shown in Table 2. However, it may be noted that different circuits may be required for the other FD-transitions because merging all FD-transitions in a single detector state graph will lead to CSC problems. As shown in the example above, some FD-transitions can be merged into a single state graph maintaining CSC. Figures 13–16 illustrate the SGs for all the FD-transitions shown in Table 2. Also, the FD-transitions which could be merged are mentioned in the figures.Figure 13
State graph for detectingFD-transitions–Sl. numbers 1 and 2 of Table 2.Figure 14
State graph for detectingFD-transition–Sl. numbers 5 of Table 2.Figure 15
State graph for detectingFD-transitions–Sl. numbers 6 and 7 of Table 2.Figure 16
State graph for detectingFD-transitions–Sl. numbers 8 and 9 of Table 2.Before discussing the algorithm for generating the detector for a set ofFD-transitions we introduce the notion of compatible FD-transitions.Definition 8 (compatibleF
D-transitions).
TwoFD-transitions τ
′
1
=
X
′
1
,
X
′
1
+ and τ
′
2
=
〈
X
′
2
,
X
′
2
+
〉 are compatible if the following holds: (i)
Ifs
1 is the signal change by τ
′
1 and s
2 is the signal change by τ
′
2, then s
1 is the same as s
2. In other words, signal change by both FD-transitions is the same.
(ii)
LetV
′
1
⊆
V (for FD-transition τ
′
1
=
〈
X
′
1
,
X
′
1
+
〉) be the set of variables whose values at X
′
1 are different compared to state(s) X
i, where X
i is any state under normal condition (normal DES) from which s
1 is the signal change. Similarly, the set V
′
2
⊆
V is calculated for FD-transition τ
′
2
=
〈
X
′
2
,
X
′
2
+
〉. Then, V
′
1
∩
V
′
2
≠
∅. In other words, there exists at least one signal (i.e., a variable) whose value is the same in initial state of both FD-transitions and that is different compared to the initial state(s) of the corresponding transition(s) under normal condition.For example, consider two FD-transitions X
′
11
,
X
′
6 (=
τ
′
1, say) and X
′
13
,
X
′
8 (=
τ
′
2, say). We calculate V
′
1 for τ
′
1 as follows. The value of variables at initial state X
′
11 is {
R
in
=
1
,
R
out
=
0
,
A
in
=
1
,
A
out
=
0
}. The signal change for =
τ
′
1 is A
out
+. We get two states (X
0
=
{
R
in
=
1
,
R
out
=
1
,
A
in
=
0
,
A
out
=
0
} and X
2
=
{
R
in
=
1
,
R
out
=
1
,
A
in
=
1
,
A
out
=
0
}) in normal condition from which the signal change A
out
+ occurs. Thus, V
′
1
=
{
R
out
(
=
0
)
} because R
out is the only variable that is different in X
′
11 compared to normal states X
0 and X
2. Similarly, we calculate V
′
2 for τ
′
2 as V
′
2
=
{
R
out
(
=
0
)
}. Since V
′
1
∩
V
′
2
≠
∅
=
{
R
out
(
=
0
)
}, thus, these two transitions are compatible and can be merged (as shown in state graph of Figure 12).Algorithm 9.
Algorithm for construction of detectors given the set ofFD-transitions.
Input. I
FD is set of FD-transitions.Output. Detectors for determining occurrence of FD-transitions are as follows:(1)
PartitionI
FD into equivalence classes. Let I
1
FD
,
I
2
FD
,
…
,
I
l
FD be the sets generated.
(2)
For each of these sets (I
i
FD, (
1
≤
i
≤
l
)), generate a detector state graph using Step (
3
) to Step (
10
).
(3)
s is the signal changed by τ
′
∈
I
i
FD and y is any signal whose value is the same in initial states of all τ
′
∈
I
i
FD. Further, signal y is different in the initial state of the corresponding normal transition which also makes the same change in s.
(4)
Let state encoding of the detector be the tupley
,
s
,
S
t
a
t
u
s.
(5)
Create the initial stated
0. The values of the variables in d
0 are as follows: (i) y in the tuple for d
0 is complement of the value of the variable y in i
n
i
t
i
a
l
(
τ
′
), τ
′
∈
I
i
FD, (ii) s in the tuple for d
0 is complement of the value of the variable s after its change by τ
′
∈
I
i
FD, and (iii) S
t
a
t
u
s in d
0 is 0.
(6)
Create stated
1, with transition from d
0 to d
1 labeled as y
+ (y
-) if value of y in d
0 is 0 (1). Also, create a transition from d
1 to d
0 labeled with inverse of the signal change as in transition from d
0 to d
1. Accordingly, encode state d
1.
(7)
Create stated
2, with transition from d
1 to d
2 labeled as s
+ (s
-) if value of s in d
1 is 0 (
1
). Accordingly, encode state d
2.
(8)
Create stated
3, with transition from d
2 to d
3 labeled as S
t
a
t
u
s
+. Accordingly, encode state d
3.
(9)
Create stated
4, with transition from d
3 to d
4 labeled as y
+ (y
-) if transition from d
0 to d
1 is y
- (y
+). Add a transition from d
4 to d
3 with inverse of the signal change as in transition from d
3 to d
4. Accordingly, encode state d
4.
(10)
Create stated
5, with transition from d
0 to d
5 labeled as s
+ (s
-) if transition from d
1 to d
2 is s
+ (s
-). Add a transition from d
5 to d
0 with inverse of the signal change as in transition from d
0 to d
5. Accordingly, encode state d
4.


### 4.1. Circuit Synthesis for DES Detector

It is clear from the construction of the state graphs of detectors that they have complete state coding [27, 28] and are live. So they can be synthesized as SI circuits using C-elements and logic gates by applying standard asynchronous circuit synthesis procedures [29, 30].Figure17 illustrates some snapshots regarding the steps of synthesizing the state graph of the detector shown in Figure 14 using CAD tool Petrify [31]; Figure 17(a) is the description of the state graph that is input to Petrify, Figure 17(b) illustrates the output of Petrify showing CSC and no liveness issues, and Figure 17(c) shows the equations obtained from Petrify. The circuit schematic (of the DES detector) that is synthesized for this state is shown in Figure 18.Figure 17
Screenshot showing the synthesis of DES detector from state graph using Petrify.
(a)
State graph
(b)
Output of Petrify
(c)
Output equations of PetrifyFigure 18
DES detector circuit for state graph shown in Figure14.Now, we explain some details of the Petrify equations.I
N
O
R
D
E
R is a keyword of Petrify to represent all I/O signals of the corresponding state graph. O
U
T
O
R
D
E
R is the keyword to represent the output signals of the state graph. Each subsequent line (denoted by [
0
,
1
]
…) represents a gate of the circuit in terms of the function it implements. In case of the circuit of Figure 18, I
N
O
R
D
E
R
=
A
out, R
out, S
t
a
t
u
s and O
U
T
O
R
D
E
R
=
S
t
a
t
u
s. The equations [
0
]
=
A
out
′
R
out
′ and [
1
]
=
0 represent the logic expressions of the internal Gate 4 and Gate 3, respectively. The equation [
S
t
a
t
u
s
]
=
1
′
(
[
0
]
+
S
t
a
t
u
s
)
+
S
t
a
t
u
s
[
0
] represents the output of the circuit.In similar way, all state graphs for theFD-transitions have been synthesized into different circuits. Then, the final DES detector circuit for CUT is constructed by simply ORing the outputs of these circuits. The output of the detector circuit becomes high when output of at least one individual detector becomes high, thereby detecting the fault.


## 4.1. Circuit Synthesis for DES Detector

It is clear from the construction of the state graphs of detectors that they have complete state coding [27, 28] and are live. So they can be synthesized as SI circuits using C-elements and logic gates by applying standard asynchronous circuit synthesis procedures [29, 30].Figure17 illustrates some snapshots regarding the steps of synthesizing the state graph of the detector shown in Figure 14 using CAD tool Petrify [31]; Figure 17(a) is the description of the state graph that is input to Petrify, Figure 17(b) illustrates the output of Petrify showing CSC and no liveness issues, and Figure 17(c) shows the equations obtained from Petrify. The circuit schematic (of the DES detector) that is synthesized for this state is shown in Figure 18.Figure 17
Screenshot showing the synthesis of DES detector from state graph using Petrify.
(a)
State graph
(b)
Output of Petrify
(c)
Output equations of PetrifyFigure 18
DES detector circuit for state graph shown in Figure14.Now, we explain some details of the Petrify equations.I
N
O
R
D
E
R is a keyword of Petrify to represent all I/O signals of the corresponding state graph. O
U
T
O
R
D
E
R is the keyword to represent the output signals of the state graph. Each subsequent line (denoted by [
0
,
1
]
…) represents a gate of the circuit in terms of the function it implements. In case of the circuit of Figure 18, I
N
O
R
D
E
R
=
A
out, R
out, S
t
a
t
u
s and O
U
T
O
R
D
E
R
=
S
t
a
t
u
s. The equations [
0
]
=
A
out
′
R
out
′ and [
1
]
=
0 represent the logic expressions of the internal Gate 4 and Gate 3, respectively. The equation [
S
t
a
t
u
s
]
=
1
′
(
[
0
]
+
S
t
a
t
u
s
)
+
S
t
a
t
u
s
[
0
] represents the output of the circuit.In similar way, all state graphs for theFD-transitions have been synthesized into different circuits. Then, the final DES detector circuit for CUT is constructed by simply ORing the outputs of these circuits. The output of the detector circuit becomes high when output of at least one individual detector becomes high, thereby detecting the fault.


## 5. Experimental Evaluation

To validate the efficacy of the scheme, we analyze the area overhead ratio of the online tester circuit to that of the circuit under test. Further, we also compare the overhead with other techniques reported in the literature. In our experiments, we have considered some standard SI benchmark circuits [32]. Further, for comparison, we have also implemented our scheme on the circuits used in [5].The algorithm discussed in previous section is used to design a CAD tool OLT-ASYN which generates detectors for OLT given an asynchronous circuit specification. The design procedure includes the following steps.(i)
First, the behavior description of the SI circuit is represented using STG.
(ii)
The STG representation of the SI circuit is converted into its corresponding state graph using Petrify.
(iii)
Using Petrify, the state graphs are implemented as SI circuits using generalized C-element.
(iv)
s-a-0 and s-a-1 faults are inserted in all the nets of the gates and stuck-on and stuck-off faults are inserted in the transistors of the C-elements of the circuit (one at a time) and the corresponding faulty state graphs are generated.
(v)
FD-transitions are generated for all the faults using the DES theory.
(vi)
Using Algorithm9 state graphs of the detector(s) are generated.
(vii)
The state graphs are implemented as SI circuits using generalized C-element implementation using Petrify.Area overhead ratio of the online tester circuit to that of the circuit under test is computed using the formula(1)
Area
overhead
ratio
=
Combined
area
of
the
Detector
circuits
Area
of
the
CUT
.Area of gates and C-elements are considered in terms of number of transistors used in their CMOS implementation. For example, a two-input NAND gate has four transistors (two PMOS and two NMOS). Fault coverage is calculated as ratio of number of faults detected by the tester to the total number of faults.Table3 shows the number of gates, number of faults, fault coverage, area overhead ratio, and execution time of the proposed approach for the different SI circuits being considered.Table 3
Fault coverage, area overhead ratio, and execution time for the online detector designed using the proposed approach.
CUT
Number of gates
Number of faults
Fault coverage (%)
Area overhead
Execution (sec)∗
Circuit 1
3
22
95
0.8
0.12
Circuit 2
5
32
96
1.5
0.23
Circuit 3
5
54
98
1.2
0.34
2 David cells [5]
6
44
94
1.6
0.22
4 David cells [5]
12
88
93
1
0.40
chu172
9
47
96
0.24
0.36
alloc-outbound
15
130
98
0.13
0.42
sbuf-read-ctl
19
152
95
0.12
0.51
sbuf-send-ctl
18
140
94
0.087
0.47
ram-read-sbuf
23
197
93
0.025
0.56
∗Executed in AMD Phenom IIX3 710 Processor with 4 GB RAM in Linux OS.The first three circuits in the table are simple examples whose gate level designs are shown in Figures19, 20, and 21. The fourth and fifth circuits have been used in [5]. The others are standard asynchronous benchmarks [32] which are complex in terms of area, states, and signal compared to first five circuits in the table.Figure 19
Circuit 1.Figure 20
Circuit 2.Figure 21
Circuit 3.Broadly speaking, it can be observed from Table3 that area overhead decreases with the increase of the size of the circuit. In [12], Drineas and Makris have identified that the area overhead ratio for partial replication based OLT for stuck-at faults is approximately α
+
1
/
β, where α is the fraction of test patterns incorporated in detector design (α
=
1 when all FD-transitions are incorporated in detector design) and β is the number of state bits required for circuit representation (i.e., proportion to circuit size). In this work, we have taken all possible FD-transitions and the obtained area overhead ratio acts (approximately) in accordance with the fact mentioned above.From the discussion in the last section regarding design of the detector from theFD-transitions, it may appear that a large number of such detectors may be required for complex circuits. In the worst case, the number of detectors may be equal to the number of FD-transitions. Further, in case of large circuits as the number of nets and C-elements are high the number of FD-transitions may be proportionally large. However, interestingly, the experiments illustrated reverse trends. Large circuits have larger number of possible stuck-at faults; however, many of them are mapped to similar effects and hence the same FD-transitions; this can be observed from Table 1 for the running example. Further, using the principle of compatible of FD-transitions, it was found that multiple FD-transitions fall in the same clusters thereby resulting in the fact that a single detector suffices for more than one FD-transition. To conclude, it was observed that a few detectors are actually required to cover all the faults. To the best of our knowledge, such facts regarding OLT of asynchronous circuits were not reported in the literature.It may be noted that percentage of fault coverage is more than 95% in average. The number of faults that could not be detected was found to be redundant.


### 5.1. Mutex Approach to Testing

Now, we will discuss, in brief, the Mutex approach for online testing proposed in [5] and compare its area overhead ratio with our scheme. In [5], the scheme is demonstrated on the following specification of a handshaking protocol:(2)
r
e
q
+
⟶
a
c
k
+
⟶
r
e
q
-
⟶
a
c
k
-
.Online testing is performed using checkers which verify that sequencing of the signals as per the protocol is maintained; that is, there is no premature or late firing of signals, no signal is stuck-at-0/stuck-at-1 fault, and so forth. All the protocol signals are used as the input for the checker. The checker has two functionalities, namely, self-checking and online testing of the handshaking protocol. The signal “mode” decides this selection. The block diagram of the checker is given in Figure 22. A part of the checker circuit is shown in Figure 23 which will be used to present the basic working of the checker. The full circuit diagram and functionality can be found in [5]. As shown in Figure 23, there are two Mutex components; one is used for the arbitration between r
e
q
- and a
c
k
-, while the other is used to arbitrate between m
o
d
e
+, g
a
11
+, and g
a
11
e
+; the details of the signals g
a
11
+ and g
a
11
e
+ are given below.Figure 22
Block diagram of the checker.Figure 23
A part of the checker circuit [5].The initial state is 11 (both req and ack are high). This is guaranteed by the previous state. In the previous cycle of operation,r
e
q
+ occurs before a
c
k
+, which sets g
r
11
=
1, thus providing the appropriate initial condition for the given cycle. The next signal change should be r
e
q
- (as per the handshaking protocol). So, once r
e
q
- occurs, g
a
11 signal is set to 1 (left Mutex), as a
c
k signal is still high. As a result, the checker goes to next state 01 indicating no errors. If there is an error in the protocol under test, then a
c
k
- precedes r
e
q
-, and g
a
11
e is set to 1. This moves the checker along the fault branch.When the mode signal is set to logic 1, the three-input arbiter (right Mutex in Figure23) is used to arbitrate m
o
d
e
+, g
a
11
+, and g
a
11
e
+. This Mutex is used for self-testing of the checker.The asynchronous circuit under test (which realizes the above handshaking protocol) is implemented using David cells [5]. The partial checker circuit illustrated in Figure 23 basically tests the handshake protocol between a pair of David cells and performs self-checking. Along with the partial circuit shown in Figure 23, there are four David cells (not shown), which together test the handshaking protocol (between a pair of David cells) and self-testing of the checker. Among the two Mutex blocks and four David cells, half of them are used for handshaking protocol and the other half is used for self-testing. The logic gates are shared resources for both types of testing. In [5], both the circuit under test and the checker circuity are implemented using David cells, using the flow of converting a Petri net model to asynchronous circuits based on David cells [33].


### 5.2. Comparison with the Mutex Approach

The proposed DES based approach for online testing does not involve self-testing of the detector. So, for comparison of area overhead of the proposed scheme with [5], we require only half of the resources used in [5]. Table 4 shows area overhead ratio of the checker (for online testing only) for two circuits implementing handshaking protocols involving two and four David cells, respectively. The table also reports the number of David cells, Mutex elements, and logic gates involved in the checker (for online testing). From Tables 4 and 3 (fourth and fifth circuit), we can deduce that the area overhead requirement for the Mutex method is higher compared to that of the purposed scheme. The advantages of the proposed method over the Mutex approach are as follows:(1)
The area overhead for the online tester circuit is less as compared to that of the Mutex approach by about 50%.
(2)
There is flexibility to trade off area overhead, by reducing fault coverage depending upon the testability requirements. Such flexibility is not easy to be achieved by the Mutex approach. It may be noted that the proposed scheme verifies that there are no stuck-at faults while the Mutex approach verifies a protocol. In particular, it checks for the correct sequencing of the outputs. Fault coverage can be easily traded off with area overhead in our approach, while it is difficult to achieve something like “partial verification of protocol,” avoiding checking certain incomplete output sequences.
(3)
In the detector of the proposed scheme, there is no dependency on Mutex elements. The Mutex element itself can undergo a metastable state which needs to be handled by the metastability detector, adding to area overhead.Table 4
Area ratio for the Mutex approach.
CUT
Circuits for OLT
Area overhead  ratio for  Mutex method
2 David cells
2 David cells + 2 Mutex elements + gates
3.3
4 David cells
4 David cells + 4 Mutex elements + gates
4.9In this work, we could not compare fault coverage of our approach with the Mutex approach. The Mutex approach verifies online whether the output of the CUT follows the specified handshaking protocol. So, the Mutex approach basically follows functional testing. The scheme proposed in our paper works on structural testing and hence fault coverage can be given, while it is not possible for functional testing.It may be noted that the circuits considered in the Mutex-based OLT scheme [5] were simple. For comparison with our scheme, we have done manual implementation of Mutex-based tester design on those circuits.


## 5.1. Mutex Approach to Testing

Now, we will discuss, in brief, the Mutex approach for online testing proposed in [5] and compare its area overhead ratio with our scheme. In [5], the scheme is demonstrated on the following specification of a handshaking protocol:(2)
r
e
q
+
⟶
a
c
k
+
⟶
r
e
q
-
⟶
a
c
k
-
.Online testing is performed using checkers which verify that sequencing of the signals as per the protocol is maintained; that is, there is no premature or late firing of signals, no signal is stuck-at-0/stuck-at-1 fault, and so forth. All the protocol signals are used as the input for the checker. The checker has two functionalities, namely, self-checking and online testing of the handshaking protocol. The signal “mode” decides this selection. The block diagram of the checker is given in Figure 22. A part of the checker circuit is shown in Figure 23 which will be used to present the basic working of the checker. The full circuit diagram and functionality can be found in [5]. As shown in Figure 23, there are two Mutex components; one is used for the arbitration between r
e
q
- and a
c
k
-, while the other is used to arbitrate between m
o
d
e
+, g
a
11
+, and g
a
11
e
+; the details of the signals g
a
11
+ and g
a
11
e
+ are given below.Figure 22
Block diagram of the checker.Figure 23
A part of the checker circuit [5].The initial state is 11 (both req and ack are high). This is guaranteed by the previous state. In the previous cycle of operation,r
e
q
+ occurs before a
c
k
+, which sets g
r
11
=
1, thus providing the appropriate initial condition for the given cycle. The next signal change should be r
e
q
- (as per the handshaking protocol). So, once r
e
q
- occurs, g
a
11 signal is set to 1 (left Mutex), as a
c
k signal is still high. As a result, the checker goes to next state 01 indicating no errors. If there is an error in the protocol under test, then a
c
k
- precedes r
e
q
-, and g
a
11
e is set to 1. This moves the checker along the fault branch.When the mode signal is set to logic 1, the three-input arbiter (right Mutex in Figure23) is used to arbitrate m
o
d
e
+, g
a
11
+, and g
a
11
e
+. This Mutex is used for self-testing of the checker.The asynchronous circuit under test (which realizes the above handshaking protocol) is implemented using David cells [5]. The partial checker circuit illustrated in Figure 23 basically tests the handshake protocol between a pair of David cells and performs self-checking. Along with the partial circuit shown in Figure 23, there are four David cells (not shown), which together test the handshaking protocol (between a pair of David cells) and self-testing of the checker. Among the two Mutex blocks and four David cells, half of them are used for handshaking protocol and the other half is used for self-testing. The logic gates are shared resources for both types of testing. In [5], both the circuit under test and the checker circuity are implemented using David cells, using the flow of converting a Petri net model to asynchronous circuits based on David cells [33].


## 5.2. Comparison with the Mutex Approach

The proposed DES based approach for online testing does not involve self-testing of the detector. So, for comparison of area overhead of the proposed scheme with [5], we require only half of the resources used in [5]. Table 4 shows area overhead ratio of the checker (for online testing only) for two circuits implementing handshaking protocols involving two and four David cells, respectively. The table also reports the number of David cells, Mutex elements, and logic gates involved in the checker (for online testing). From Tables 4 and 3 (fourth and fifth circuit), we can deduce that the area overhead requirement for the Mutex method is higher compared to that of the purposed scheme. The advantages of the proposed method over the Mutex approach are as follows:(1)
The area overhead for the online tester circuit is less as compared to that of the Mutex approach by about 50%.
(2)
There is flexibility to trade off area overhead, by reducing fault coverage depending upon the testability requirements. Such flexibility is not easy to be achieved by the Mutex approach. It may be noted that the proposed scheme verifies that there are no stuck-at faults while the Mutex approach verifies a protocol. In particular, it checks for the correct sequencing of the outputs. Fault coverage can be easily traded off with area overhead in our approach, while it is difficult to achieve something like “partial verification of protocol,” avoiding checking certain incomplete output sequences.
(3)
In the detector of the proposed scheme, there is no dependency on Mutex elements. The Mutex element itself can undergo a metastable state which needs to be handled by the metastability detector, adding to area overhead.Table 4
Area ratio for the Mutex approach.
CUT
Circuits for OLT
Area overhead  ratio for  Mutex method
2 David cells
2 David cells + 2 Mutex elements + gates
3.3
4 David cells
4 David cells + 4 Mutex elements + gates
4.9In this work, we could not compare fault coverage of our approach with the Mutex approach. The Mutex approach verifies online whether the output of the CUT follows the specified handshaking protocol. So, the Mutex approach basically follows functional testing. The scheme proposed in our paper works on structural testing and hence fault coverage can be given, while it is not possible for functional testing.It may be noted that the circuits considered in the Mutex-based OLT scheme [5] were simple. For comparison with our scheme, we have done manual implementation of Mutex-based tester design on those circuits.


## 6. Conclusion

In the present paper, a method for the online testing of SI circuits has been proposed. We start by obtaining the STG of the SI circuit under test using the tool Petrify. After that, effects of stuck-at faults were modeled in the STGs. The normal and faulty STGs were transformed into state graphs and a DES detector was designed. The detector is capable of determining, online, whether any of the modeled stuck-at faults have occurred in the circuit. Finally, the detector is synthesized as a SI circuit with C-elements which is to be placed on chip. Several circuits were considered as case study and area overhead ratio of the detector was studied for these circuits. Results illustrated that area requirement of the detector of the proposed scheme is less than that of the Mutex approach [5] by about 50% on the average. Apart from this, there are several other advantages of the proposed approach, namely, independence of circuit functionality, nonintrusiveness, liveness, and CSC of the detector to ensure synthesizability and so forth.The present scheme is applicable only for SI circuits with dynamic implementation of C-elements. As a further direction of research, this technique can be extended for other types of asynchronous circuits like Delay Insensitive (DI) circuits. It is required to verify whether this proposed DES based OLT scheme can be directly applied for DI circuits or some modifications would be needed.Also, in case of SI circuits, the present scheme can be extended for static C-elements. OLT of static C-elements may be comparatively more complex than that of dynamic C-element because the dynamic C-element comprises less number of transistors than that of static C-element. Additionally, in the present work, it is found that transistor stuck-off or stuck-on faults lead to premature/nonoccurrence of a transition in the STG. Whether similar fault manifestation remains for static C-elements or there is a change needs to be verified. Clearly further research is required to solve these issues.



---

*Source: 651785-2015-04-30.xml*