‘...

 

 

 

...V.....

 

"H...”

 

.
«

 

 

V

rum (0.

 

u...”-

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

_ . .V V V V
V VV . V. . V I V > V V
. . V ..VV . V V.... .. .
. ‘ .V V V .. V . . V
.V .. .. VV. VV...... . .V V V V .V
. . . V .V V .V . V... VVVV AV. . . . - V V
. . V V.V V. . V. V V . . V V .. .
.. 1 V . .VVV. V . V .. V .. . .VV.
.V V\_ -.VVV. . 5 . A V V _ . . V
VV V VV V . V~V V VV .. . . V .. . .
V. iv 1 .V . -. V - VV - V
V V. V V. V .V . .V.V - VV . V .V V c
. V. V r V VV.V V V . . .V V
V. . . . . . . . .V VV. .
V i - V IV . AV . V V V . V . V .
V . .. . V V V V V.V V V
V. u. V V. V V VV .V .. .V. .
. . V V.. .V . . y .. V . . V. V. .. . V..V V .. n. .
. a . . V .V .. V a. V V V. v .V .V V.
VV .. V .V V. .V V V .. V._ . . .. V
. n . .. ... .V. V V V . . . . V
V . . V V .V .v‘ . . V . .V. ..V .
. V VVV. .. V VV V. .V. . . V.. V .V QVV.
V V . . .V .. . . V. V
V 4’ . V . » V .VV . V
a I . V. .V V . .V . .VI .
. V .. V; V . H
V V V V. .V VV . . .. . n .
V V - V VV VV...V . V
V V . V. V VV. .
;

 

 

 

 
 

 

 
 
 
 

 
 

 

 
 
 
 
 

 

 
 

 

 

 

 

 

 

 
 

 
 

 

 
 

 
 

 
 
 
 
 

 

 

 

 
 
 
 

 

 
 

 

 

 
 

 
  

 

 

 

 
 
 

 
 
 

 

 

 

 

 
 

 

 

 

 
 

 

 
 
 

 

 

 

 

 
 
 

 
 

V. V . V . V . V: .H
V . . . . . V ._ V .. . VVVVVV VVV..
V V - V . V .V. ..
. . V . .. .V.. V .V
V . . . .VV . V . . . fl. . VV V V...
. V . V . . ..V. . V . V .V V...
... V V .. . V. . V . V V V V V. . V.
V V V . V V V... V V. VV . .4; . V. . .V V . a .
V . . V V V. VV .. V . V .. V .VV. VV V
V. . . V V V . V . V V. V V V V
V: V . .. V V .V . .V.. V. V .V V V.
V . V V... V V ‘ VV . ..V.~ I V V . V V. V V
V V . V V V . . .V V . V V I VVV V
V. VV V . V. .V V V .. V .V . V . V V. V V V .V..V.. V:
. . V . . . V .. V VV V .V V
. V ~ V VV V V V . V;

 

MICHIGAN STATEU

mu u mg; infill/ll ll! Illlylllltl L

 

 

 

 

 

 

 

 

 

 

 

 

 

~\
'I‘Tfi

This is to certify that the

dissertation entitled

DESIGN AND SYNTHESIS OF
TESTABLE ASYNCHRONOUS SEQUENTIAL
LOGIC CIRCUITS

presented by
Ming-Der Shieh

has been accepted towards fulfillment
of the requirements for

Ph.D. degree in Electrical Engineering

Major professor

 

 

 

Date d z;

MSU L1 an Affirmative Action/Equal Opportunity Institution 0- 12771

 

 

‘ n,;#

P .

f f ‘p—Af

DESIGN AND SYNTHESIS OF TESTABLE
ASYNCHRONOUS SEQUENTIAL LOGIC CIRCUITS

By

Ming—Der Shieh

A DISSERTATION

submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY

Department of Electrical Engineering

1993

ABSTRACT

DESIGN AND SYNTHESIS OF TESTABLE
ASYNCHRONOUS SEQUENTIAL LOGIC CIRCUITS

By

Ming-Der Shieh

Test generation is much more difficult for ASLCs than for CSLCs because of
races, hazards, and state oscillations. Often a designer does not know whether or not all
transitions in a circuit are free of races and hazards. The situation is even more uncertain if
a fault is present. Even though fault-free circuits can be designed to be free of races,
hazards, and state oscillations, they may occur as a result of faults. And even though the
fault-free circuit can be designed to change one state variable at a time during a state
transition to avoid races, the condition cannot be guaranteed in the presence of faults.
Based on the single stuck-at fault model, fault effects such as redundant faults and state
oscillation faults for both Huffman-modeled and STG-modeled ASLCs have been
presented in this research. With the observed fault effects, numerous synthesis properties
have also been described for both Huffman-modeled and STG-modeled ASLCs with or
without SR—latches. Those properties can be implemented to reduce the complexity of the
test generation process.

The similarities and differences between the Huffman-modeled ASLC and the

STG—modeled ASLC have been presented in this research. A STG-modeled ASLC

without input/output concurrency can be viewed as a special Huffman-modeled ASLC.
The input/output concurrency is a special feature in STG which resolves the fundamental
mode problem in Huffman model. Due to such a salient feature, asynchronous control
circuits have been successfully designed and implemented using STG. However, with the
input/output concurrency, a test input that must be applied at the same time when the
output changes is obvious not an easy task. This study shows that the faults due to the
input/output concurrency cannot be tested without scan structure.

Due to the lack of controllability and observability of state variables, testing of
sequential circuits has been recognized as a very difficult task. This research presents the
development of the ASLCScan method, a scan design structure for ASLCs. The scan
structure is free of races and hazards in both normal Operation and test modes, and
achieves full testability for all single stuck-at faults. With the ASLCScan design, the test
generation problem of ASLCs is reduced to one of just testing the combinational logic and

the introduced races in the combinational circuit of ASLC can be identified easily.

ACKNOWLEDGNIENTS

The author wishes to express his sincere gratitude to his major advisors, Dr. Chin-
Long Wey and Dr. P. David Fisher, for the guidance, support and encouragement given in
the course of this study. Gratitude is also extended to his committee members, Dr. David
Yen and Dr. Diane Rover. In particular, the author wishes to express his deep appreciation

to his family for their support, understanding and exemplary patience.

TABLES OF CONTENTS

LIST OF TABLES ............................................................................................... vii
LIST OF FIGURES .............................................................................................. viii
Chapter 1: Introduction ..................................................................................... 1
1.1 Problem Statement .......................................................................... 2

1.2 Research Tasks ............................................................................... 4

1.3 Organization .................................................................................... 4
Chapter 2: Background ..................................................................................... 5
2.1 Synthesis Procedures for ASLCs ................................................... 5

2.1.1 Huffman-Modeled ASLCs .............................................. 6

2.1.2 STG-Modeled ASLCs ..................................................... 10

2.1.3 Self-Timed AFSMs ......................................................... 13

2.2 Testing Problems in CLSCs ........................................................... 16

2.2.1 Fault Model ...................................................................... 17

2.2.2 Synthesis for Testability .................................................. 17

2.2.3 Design for Testability ...................................................... 22

Chapter 3: Fault Effects and Testability Synthesis Properties in ASLCs ........ 28
3.1 Huffman-Modeled ASLCs with Line Feedback ............................ 28

3. 1.1 Fault Effects ..................................................................... 29

3.1.2 Testability Synthesis Pr0perties ...................................... 48

3.2 Huffman-Modeled ASLCs with SR-Latches ................................. 56

3.2.1 Fault Effects ..................................................................... 56

3.2.2 Testability Synthesis Properties ...................................... 67

3.3 STG-Modeled ASLCs .................................................................... 73

3.4 Discussion ....................................................................................... 79
Chapter 4: ASLCScan - A Scan Design for ASLCs ....................................... 80
4.1 Level-Sensitive Scan Design ........................................................ 81

4.2 ASLCScan Method for ASLCs ...................................................... 85

4.2.1 Basic Components ........................................................... 86

4.2.2 Scan Path ......................................................................... 88

4.2.3 Polarity-Hold Shift Register Latch ................................. 90

4.2.4 Operation Modes .............................................................. 98

4.3 Examples ........................................................................................ 99

4.4 Discussion ...................................................................................... 100
Chapter 5: Conclusions ..................................................................................... 103
5.1 Summary ......................................................................................... 103

5.2 Contributions ................................................................................... 106

5.3 Future Research ............................................................................. 106

LIST OF REFERENCES .................................................................................... 108

vi

Table 3.1
Table 4.1
Table 4.2

LIST OF TABLES

SR-Latch Excitation Table. .............................................................
Fault Simulation Results for Scan Path. .........................................
Fault Simulation Results for Modified SR-Latch. ..........................

vii

Figure 2.1

Figure 2.2
Figure 2.3

Figure 2.4
Figure 2.5
Figure 2.6

Figure 2.7
Figure 2.8
Figure 2.9
Figure 2.10
Figure 2.11

Figure 2.12

Figure 3.1
Figure 3.2

Figure 3.3

Figure 3.4
Figure 3.5

LIST OF FIGURES

A Huffman-modeled ASLC with next-state generator (NSG) and
output generator (OG). ....................................................................
Geometric representation of a 4-NWD. ..........................................
An STG representation (a) Initial marking with x+ enabled; and (b)
The marking after x+ fired. ..............................................................
An AFSM with data and control signals. .......................................
A self-timed SR—latch. ....................................................................
SRFs in CSLCs (a) State Transition Graph (C_STG); (b) Logic
implementation of (a); (c) The complete C_STG for (b); ((1) Valid!
valid equivalent-SRF; and (e) Valid/invalid equivalent-SRF. ..........
Invalid-SRF (a) Fault-free C_STG; and (b) Faulty C_STG. .........
Isomorph-SRF. ................................................................................
(a) A sequential circuit; and (b) Iterative array model. ..................
Test generation iterative array model for ASLCs. ..........................
LSSD scan design (a) Polarity—hold latch and its corresponding K-
map; and (b) Polarity-hold Shift Register Latch. .............................
Double-latch LSSD implementation. ..............................................
Partitioned ASLC without shared logic. .........................................
An ASLC for Example 1 (a) Merged flow table and output table; (b)
STT-generated ASLC; (c) UDC-generated ASLC; and (d)&(c)
Transition tables of the corresponding faulty circuits. ....................
An ASLC for Example 2 (a) Flow table; (b) Transition table with
don’t cares; (c) Transition table without don’t cares and its two—
level logic realization; and (d)&(e) Transition tables of the corre-
sponding faulty circuits. ..................................................................
State oscillation due to critical races [9]. .......................................
Example 3 (a) Transition table of the corresponding faulty circuit
for SIT-generated ASLC and K-map for Y1; and (b) Transition

viii

11
15
15

19
21
21
23
23

26

27
29

32

36
38

Figure 3.6

Figure 3.7
Figure 3.8

Figure 3.9
Figure 3.10

Figure 3.11
Figure 3.12
Figure 3.13
Figure 3.14
Figure 3.15
Figure 3.16

Figure 4.1

Figure 4.2
Figure 4.3

Figure 4.4

Figure 4.5

Figure 4.6

Figure 4.7
Figure 4.8

table of the corresponding faulty circuit for UDC-generated ASLC
and K-map for Y2. ...........................................................................
An ASLC example (a) Partial flow table; (b)&(c) Transition table;
(d) Connected path; (e) Transition table of the corresponding faulty
circuit; and (f) Connected paths form an oscillation loop. ..............
Transition tables for Example 5. .....................................................
(a) Operation of SR-latch; (b) NOR-gate implementation; and (c)
NAND- gate implementation. ..........................................................
SR-latches implementation without shared logics. .......................
An ASLC example (a) Merged flow table and output table; (b) STT-
generated ASLC; and (c) Logic implementation for (b). ................
SR-latches implementation for Figure 3.3(c). ................................
SR-latches implementation for Figure 3.3(b). .................................
Block diagram of next-state logic (a) Yi-variable; and (b) Combina-
tional logic block (CLB). .................................................................
An STG-modeled ASLC (a) Four-phase handshaking protocol; (b)
Logic implementation; and (c) Equivalent concurrent flow table.

The transformation from SR-latch to C-element. ............................
Example 10 (a) Rom; (b) Am"; and (c) Maps for Rom in the presence
of a stuck-at-l fault at the Amt-input of Gate A2; and (d) Equiva-
lent concurrent flow table of (c). .......................................................
Potential hazard condition in the case of storing a “1” (a) K-map
representation; and (b) Logic implementation. ...............................
Polarity-hold latch in [52]. ..............................................................
Polarity-hold latch with hazard protection (a) K-map representa-
tion; and (b) Enhanced PH. .............................................................
Clocked SR-latch (a) Truth table; (b) Truth table for modified SR-
latch; and (c) NAND gate realization. ............................................
(a) Cross-coupled NAND latch; (b) Truth table with (MSR)=(-00)
specified as don’t cares; and (c) The corresponding NAND gate
implementation. ..............................................................................
(a) Concatenated NAND SMSR-latches; and (b) Simplified imple-
mentation of (a). .............................................................................
(a) ASLCScan scan path; and (b) Alternative scan path. ..............
Modified polarity-hold SRL. .........................................................

39

46

55

57
58

60

63

66

68

74

75

77

82
83

84

87

88

89
92
94

Figure 4.9 Node assignment for the MSR-latch. ............................................ 96

Figure 4.10 Double-latch ASLCScan design. ................................................... 98
Figure 4.11 Example 1 (a) STG representation; (b) Logic implementation; and

(c) Rearrange the combinational part and C-elements. ................... 101
Figure 4.12 Example 2 (a) Behavior description; and (b) Flow table and excita-

tion table; and (c) Logic implementation. ....................................... 102

Chapter 1

Introduction

 

Sequential logic circuits may be implemented either as clocked sequential logic
circuits (CSLCs) or asynchronous sequential logic circuits (ASLCs). CSLCs require a
global clock to synchronize the internal transition, while ASLCs do not have to wait for
the arrival of a clock pulse before effecting a transition. Thus, ASLC implementation may
provide faster operation than CSLC implementation. Due to the simplicity of clock
synchronization, however, CSLC implementation has been extensively used in today’s
LSI/VLSI system designs. Moreover, as the speed of the computing system is increased,
the distribution and synchronization of a global clock will soon become a bottleneck to
system throughput [1] and, thus, ASLC implementation is an obvious solution. On the
other hand, ASLCs also provide the capability of modular design for complex system
which greatly facilitates system integration.

Two main models of operations for ASLCs are conventionally used: Hufi‘man
model and Muller model. The Huffman-modeled circuit [2,3] is decomposed into a
combinational circuit and a set of feedback paths, where both wire and gate delay are
bounded. In addition, the circuit assumes the fundamental mode of Operation, i.e., input
cannot change until the circuit stabilizes, with the constraint of single input change. The
Muller-modeled circuit [4] is decomposed into gates with an arbitrary interconnection and

assumes that the wire delays are zero and the gate delays are unbounded, but finite. In

2

general, the Muller—modeled circuits are referred to as speed-independent circuits.
Recently, an alternative design approach using a graph model, Signal Transition Graph
(STG) [1,5-7], has been presented to synthesize asynchronous controllers. Based on these
models, many automated synthesis systems have been developed [1,26,39].

Test generation is much more difficult for ASLCs than for CSLCs because of
races, hazards, and state oscillations. Often a designer does not know whether or not all
transitions in a circuit are free of races and hazards. The situation is even more uncertain if
a fault is present. Even though fault-free circuits can be designed to be free of races,
hazards, and state oscillations, they may occur as a result of faults. And even though the
fault-free circuit can be designed to change one state variable at a time during a state
transition to avoid races, the condition cannot be guaranteed in the presence of faults. This

has motivated the deveIOpment of synthesizing testable ASLCS.

1.1 Problem Statement

When a fault is presented in an ASLC, one of two fault effects occurs [8]: (l) the
circuit remains in a transition path and becomes stable, but not in the proper stable state; or
(2) the circuit is out of the correct transition path. Theoretically speaking, when a circuit
becomes stable, it can be checked whether or not the stable state is proper. If not, a fault
has occurred. In practice, however, the state variables are unobservable during the off-line
testing unless a scan structure is applied. Therefore, by observing the primary outputs of a
non-scan structure the following effects may occur due to a fault: (1) the outputs are stable
and proper; (2) the outputs are stable, but imprOper; and (3) outputs are unstable (the
duration exceeds a predetermined time period for the worst case). The latter two cases
imply that the fault effects are obviously observable at the primary outputs and thus the
faults are detectable. On the other hand, the first case results in that the faulty circuit is
equivalent to the fault-free circuit and thus detecting such fault effects becomes rather

difficult. Such fault effects are generally caused by either logic redundancy or state

oscillation.

Redundancy is sometimes desirable for hazard protection in ASLCs. However, it
may also be introduced unintentionally due in part to the implementation of an improper
synthesis procedure, such as improperly encoded state variables or improper assignment
of the don’t care terms. Since redundant circuits cannot be tested, fault detection can then
be a formidable problem. State oscillations do not occur in CSLCs because the clock
prevents the state variable values from being used to generate excitations until they
become stable, thus effectively ensuring that they appear to change simultaneously [9].
However, state oscillations may occur in ASLCs in the presence of hazards and/or races.
They may be avoided by either adding extra delay elements, or eliminating hazards and
races. But, they may occur as a result of faults. If the resultant outputs associated with the
oscillating states are different in the presence of faults, then the unstable outputs indicate
the existence of faults. However, if the resultant outputs are the same as desired values, the
faulty circuit is interpreted to be fault-free. As a result, the indeterminate stable state and
the unpredictable next state make the test generation process rather complicated.
Therefore, in order to simplify the test generation process, while still increasing fault
coverages, for ASLCs, it is necessary to identify and eliminate redundant faults and to
avoid state oscillations in the presence of faults.

Due to the lack of controllability and observability, testing of sequential circuits
has been recognized as a very difficult task. In order to reduce the complexity of the test
generation problem, scan designs [20-24] have been proposed and successfully
implemented for CSLCs. With scan structures, all state variables of a sequential circuit are
completely controllable and observable from primary inputs and outputs. Thus, the test
generation problem is reduced to one of just testing the combinational logic. In other
words, scan structures can be used to further improve the controllability and observability
of the synthesized ASLCs.

Recently, research efforts have successfully and extensively dealt with test

4

generation, design for testability, and synthesis for testability of CSLCs [10-14]. Little
emphasis, however, has been devoted to their ASLC counterparts [15-19]. Since CSLCs
may be considered to be a special case of ASLCs with certain constraints on input
changes, the fault effects that occur in CSLCs will also occur in ASLCs. If an ASLC is
synthesized such that each fault can be tested without generating critical races, then the
circuit is testable. Otherwise, state oscillations may result during testing, and some faults

may not be properly detected.

1.2 Research Tasks

This research achieves the following two tasks: (1) fault effects and synthesis
properties for both Huffman—modeled and STG-modeled ASLCs; and (2) asynchronous
scan design methodology.

Based on the single stuck-at fault model, this study investigates the fault effects
such as redundant faults and state oscillations in ASLCs. Based on those fault effects,
several synthesis properties are presented to synthesize testable ASLCs. Both Huffman-
modeled and STG-modeled ASLCs are considered. In order to reduce the complexity of
the testing process, while still increasing testability of a synthesized ASLC, an
asynchronous scan design methodology, ASLCScan, is developed for both Huffman and

STG modeled circuits, in which a race-free and hazard-free scan structure is implemented.

1.3 Organization

This thesis is organized as follows: Chapter 2 reviews the previous works that
achieved these research tasks. Chapter 3 describes the fault effects and synthesis
properties in both Huffman-modeled and STG-modeled ASLCs. The scan design
methodology, ASLCScan, is presented with some design examples in Chapter 4. Finally,

conclusions and future research topics are given in Chapter 5.

Chapter 2

Background

 

This chapter briefly reviews the existing models for designing and synthesizing
ASLCs. Two models have been commonly implemented. In addition to the conventional
Huffman model, a signal transition graph (STG) model has been recently developed for
designing control circuits. Taking advantage of these two models, the development of a
self-timed model for designing asynchronous finite state machines (AFSMs) is also
described. The major problems in each synthesis model which are related to this thesis
research are also discussed. In Section 2.2, the single stuck-at fault model commonly used
in CSLCs is presented. Based on the fault model, fault effects and techniques for

testability design and synthesis are discussed.

2.1 Synthesis Procedures for ASLCs

In this section, the synthesis procedure of Huffman model [2,3] is first presented.
Those problems such as the state assignments and hazards are discussed. This is followed
by the discussion of the STG model [1,5-6] and its synthesis procedure. The issues on how
to generate a realizable circuit and how to avoid hazards are also addressed. Finally, the

self-timed model for AFSMs developed in this study is presented.

2.1.1 Huffman-modeled ASLCs

A Huffman-modeled ASLC is generally described by a quintuple (S,I,O,8,co),
where S is a finite set of internal states; I is a finite set of inputs; 0 is a finite set of outputs;
the mapping 8 is the next-state function, 8: IXS —) S; and the mapping (0 is the output
firnction, co: IXS —> O (Mealy machine) or (r): S —) 0 (Moore machine). Figure 2.1 shows
the block diagram of a Huffman-modeled ASLC, where the input state I=(x1,x2, ..,x,), the
present state y=(y1,y2,..,yn), the next state Y=(Y1,Y2,..,Yn), and the output state

O=(Zl,Z2,..,Zm). A Huffman-modeled ASLC is generally defined in terms of a flow table

 

ASLC

 

 

 

 

~\

 

 

 

 

 

 

 

Figure 2.1: A Huffman-modeled ASLC with next-state generator
(N SG) and output generator (0G).

in which each column of the flow table represents an input state and each row represents
an internal state.The combination of the internal state y and the input state I is called the
total state. The entries of the flow table represent the next internal states of the circuit.
When the next internal state Y is the same as the present state y, the total state is said to be
stable, otherwise it is an unstable state. In a normal-mode flow table, any state transition

leads directly to a stable state and no output is required to change more than once during

7

the transition. The Huffman-modeled ASLC assumes that the line and gate delays are
bounded with no restrictions imposed on their relative magnitude and it is operated in the
fundamental mode, i.e., the input state cannot change until the circuit stabilizes, with only
one input allowed to change at a time. Design procedure for ASLCs is generally
comprised of five major steps [3,25]: (1) map a functional design specification into a
primitive flow table; (2) derive the merged fiow table; (3) encode the internal state
variables to avoid critical races; (4) generate the state transition table and output table; and
(5) eliminate static hazards and implement the circuit using two-level logic. Among these
five steps, the state assignments and hazard problems are of major concern in this study.
SI I 3 . |

The state assignment problem is to encode the internal states with a set of binary
vectors. In CSLCs, l—logan =50 state variables are necessary and sufficient for representing
n states. State assignments can be arbitrary without affecting the proper operations, as long
as no coding is assigned to more than one state. However, in ASLCs, a race occurs when
two or more state variables are to change at the same time. When a race condition exists in
a circuit, the unequal transmission delays may cause the circuit to reach stable state other
than the one intended. The race is called critical; otherwise the races are non-critical.
Therefore, 30 state variables may not be sufficient to encode the internal states in an ASLC
for avoiding critical races. Races can naturally be classified as being either an intrinsic
race (IR), or a generated race (GR) [26]. A GR is caused by encoding the states, while an
IR results when the minimum possible Hamming distance is greater than 1. A GR can be
either critical or non-critical. The necessary, but not sufficient, condition for making race-
free state assignments is that all the link degrees in a given flow table must be less than or
equal to the number of state variables. Note that the reason why so many state assignment
algorithms exist is that it is not always possible to derive an unicode state assignment in
which each state transition only requires a single state variable to change. Among the

existing algorithms, the following two commonly used algorithms are employed in this

8

study: the totally sequential state assignment [26-28], which is also referred to as an unit-
distance code (UDC) state assignment, and the single transition time (811') state
assignment [29-33].

In the UDC state assignment, the internal state variables are assigned in such a way
that each inter-row transition is represented by a set of adjacent states (two states differ in
only one single variable) and only one state variable is excited at any time during a state
transition. Races in ASLCs with the UDC state assignment can always be eliminated by
creating cycles, i.e., directing the circuit through intermediate unstable states before it
reaches its final desirable stable state with or without additional internal states. A node-
weight diagram (NWD), a variation of a binary n-cube connection diagram, as shown in
Figure 2.2, has been implemented to facilitate the UDC state assignment [26]. The level
simply represents the weight of a code, i.e., the number of 1’s in that code. It is obvious
that the Hamming distance between two codes in the same level is always greater than or

equal to 2.

Level 1 w w

‘> <b:.4k

e o‘fiifefgie

‘7' 7"»<

I...” ® ® @

Figure 2.2: Geometric representation of a 4-NWD.

 

 

9

A direct transition from an internal state Si to Sj, denoted as [Si,Sj], is a transition
whereby all internal state variables that are to undergo a change of state are
simultaneously excited. A K-set exists in a single column of a flow table and consists of all
(k-l) unstable state entries leading to the same stable state, together with that stable state.
A pair of states consisting of one unstable state and the stable state of a K-set is called a
transition pair. The S'IT state assignment generally implements a partitioning scheme to
distinguish the transition pairs [30,34]. Based on Tracey’s Theorem, the state transitions
with different stable states in the same column of the flow table can be distinguished by at
least one state variable. As a result, all the state transitions are direct and all the races are
non-critical. In other words, such a state assignment avoids all critical races and, as its
name implies, each state transition is executed within a single transition time. Results in
[26] have shown that the ASLC design implementation with the UDC state assignment

requires fewer states than that with the S'I'I‘ state assignment.

Hm

Any physical switching circuit has delays associated with gates and
interconnecting lines which are usually called stray delays. Delays are not important in
CSLCs due to the existence of clock synchronization. However, in ASLCs, delays may
cause hazard problems and result in an incorrect operation. A hazard condition exists if
there exist some possible combinations of values of stray delays which will produce a
glitch for some input changes. The hazards can be further classified into two categories:
combinational and sequential hazards [3,35,36]. The static and dynamic hazards are
combinational hazards, while the essential hazard is a sequential hazard. The hazards are
generally avoided by either adjusting the path delays or adding the delay elements in the
feedback lines of the internal state variables. Techniques have been reported in [3.28.37]

that identify the hazard conditions and design ASLCs which are free of delay elements.

10

2.1.2 STG-Modeled ASLCS

ASLCs are traditionally designed by using the FSM model. Two modifications to
the Huffman model have been suggested [7]: (1) the use of total states instead of input,
output, and state variables; (2) the use of a signaling protocol to alleviate the problems due
to controlled changes of inputs. A total state s E S (a set of state variables) is a binary
vector representing the state of all signals in a circuit, where the signals are the input and
output terminals Of the logic components. A set of the signal transitions T = M X{+,-},
where M is all the I/O terminals Of a circuit. Therefore, a machine behavior can be
represented simply by (S,T,N), where N is the next-state function and N: S X T —-> S.
Using the signal protocol, the signal changes can be controlled if the request/acknowledge
protocol is used at the input and output ports of a signal.

The signal transition graph (STG) is an event-based specification for ASLCs
[1,5,38]. It specifies the behavior of both the circuit and the environment where it
Operates. Further, the STGs can be viewed as interpreted free-choice Petri-nets, where the
transitions in nets are interpreted as the value changes on input/output signals of a
specified circuit, and the places in nets are specified by causal relations. A place can be
marked with one or more tokens, meaning that the corresponding condition holds in the
circuit. The causal relations joining pairs of transitions represent how the circuit and its
environment can react to signal transitions. Note that the STG treats the set of input and
non-input signal transitions in the same way. The fundamental difference between the
transitions of input and non-input signals is that the former are caused by the external
environment while the latter are caused by the system. The firing rules can be specified as
follows [38,39]: ( 1) When all the pre-conditions Of a transition are marked, the transition
may fire, i.e. the transition is enabled; (2) When the transition is fired, tokens are removed
from its pre-conditions and added to its post-conditions. The firing rules specify the
desired operation sequences which are independent of the time metric, therefore the

concurrency and ordering of signal changes can be easily specified.

11

For simplicity, places with exactly one predecessor and one successor can be
omitted. However, if a place has more than one successor, then the free-choice place must
be presented in the nets. Therefore, for the STG without choices [5], it can be represented
by a directed graph with a triple (T, R, TED), where T = M X{+,-} is a set of the signal
transitions in which the rising transition, 0—)], of a signal x is denoted as x" and a falling
transition, 1—)0, as x', R Q TXT is the causal relation which specifies the relation over the
set of transitions, and T50 is the set Of transitions which are enabled in the initial state of
the circuit. For example, Figure 2.3(a) shows a STG representation, where a signal
transition is represented by a vertex, arcs between transitions represent the causal relation,
the circle represents the token, and x+ is enabled in this making. Based on the firing rules,
after x” is fired, a token is removed from each of the incoming arcs, y‘—>x+, and adds to

each outgoing arc, x“--)z+ and x+—)y+, as shown in Figure 2.3(b). Further, since x"’

‘<l
N. k—x.<——N+‘—— >4+
'~<
+
‘<I
N. ‘—><l‘——N+
‘<
+

(a) (b)

Figure 2.3: An STG representation (a) Initial marking with x" enabled;
and (b) The marking after x+ fired.

12

causes transitions 2+ and y” to be enabled, therefore x+ and 2+ (y‘) are ordered. However,
transitions z+ and y+ do not share any pre-condition, so they can fire in any order, i.e. 2+
and y+ can be Operated concurrently. This process can be continued by considering all
possible token flows in the STG.

Two problems of concern in this study are how to achieve a realizable STG-
modeled ASLC and how to avoid hazards.
W

A realizable STG [1,39] must first satisfy the conditions of liveness and safeness.
A marking is live if every transition can be enabled through some sequence of firing
transition. Safeness means that no more than one token can be present in a place in any
reachable marking. Further, for a free-choice net, if a place has more than one successor.
then it must be the only predecessor of those transition. In addition, since each marking in
the STG implies a value of each signal, two more conditions must also be satisfied for
being a realizable STG: consistent labeling and unique state coding (USC) [5.39.40].
More specifically, the current state in a STG is given by the concatenation of all current
input and output values, and the value label attached to each marking must be consistent
across different firing sequences. For example, the current states (xyz) are (000) and (100)
in Figures 2.3(a) and 2.3(b). respectively. A signal t is said to be consistent for the current
state. if the transition t+ (t') is enabled in the current state. then the value of t in this state
must be 0 (1). For consistent labeling, every signal in the current state must be consistent.
The USC property implies that two markings must enable the same set of transitions. if
they have the same label. Otherwise, the behavior Of the circuit will be unpredictable. An
immediate solution to satisfy the USC property is to add an extra internal signal to
distinguish different behavior with the same label.

The synthesis procedure for STG-modeled ASLCs is comprised of (l)
constructing a STG which satisfies the five conditions discussed above; and (2) deriving

the next state values for the current state. The next state values can be derived by the

13

following rules: (1) For a signal t in the current state, if there is no signal transition
labelled t*, where t*e {t+,t'}. from this current state, then the next value of t is unchanged;
and (2) If there exists a signal transition labelled t* from this current state, then the next
value of t is complemented [39]. Therefore, by an exhaustive simulation of all reachable

markings, the logic implementation can be achieved.

Hazards

Although the implementations of STG-modeled ASLCs are straightforward.
hazards may still occur due to the unbalanced path delays. Hazards in STG-modeled
ASLCs can be simulated by applying all possible allowed input sequences. By checking
all the l-set and O-set covers in the realized logic of the input sequences. the relative
delays among different paths can be identified. If hazards occur, delay elements may be
added to compensate the path delays [39.41]. The tool, astg in sis, developed by
University Of California at Berkeley can be used to produce hazard-free ASLCs. However,
it is a time-consuming process and the resultant circuit always degrades in speed due to

the added delay elements.

2.1.3 Self-Timed AFSMs

Since Huffman-modeled ASLCs assume the fundamental mode Operation with
single input change. the design of asynchronous finite state machines (AFSMs) has been
limited because multiple-input changes are not allowed. Self-timed logic provides a
method for designing ASLCs such that their correct behavior depends neither on the speed
of their components nor on the delay along communication wires. Various self-timed
ASLC designs have been reported [3,42-45] in which input spacer words or encoded input
and output data are used tO generate completion signal. The completion signal is generated
whenever both outputs and internal states are stable. The completion-signal concept has
been presented for the design of a parallel binary adder which is an iterative combinational

circuit [46]. It was realized that, depending on the numbers being added, the time required

14

for the outputs to respond varies over a wide range. When a carry bit must “ripple”
through the entire circuit, the delay is maximum. Cases in which there are no carry, the
delay may be less than the maximum value by a factor of about n for an n-bit adder.
Results have shown that, if the numbers are randomly chosen, the average time required
varies approximately as log2(5nl4). However, if the adder does not retum some signals
indicating when it has completed each computation, then it is necessary to allow the
maximum time in every case.

Since conventional Huffman-modeled ASLCs cannot handle unrestricted input
changes [7], it is necessary to impose certain restrictions on the input changes [47]. By
nature, datum signals can assume a large number of states and one datum may follow
another in a random order. In contrast, timing or control signals have a limited number of
states and a limited number of sequences of states changed. Therefore. datum signals can
make unrestricted changes while control signals can be specified such that they change in
a predictable and orderly manner. Based on this concept, the model for self-timed AFSM
can be generalized as shown in Figure 2.4 [48]. The environment supports the input data I
and a control signal Rt,q tO trigger the Operation of an AFSM. After the AFSM completes
its task, it produces the output values 0 associated with a completion signal Cp to the
environment such that the next Operation can be processed. In addition, the controller is
used to guarantee a correct operation sequence between the AFSM and the environment.

By taking advantage Of the design procedures of both the Huffman-modeled and
STG-modeled ASLCs, a self-timed AFSM is designed as follows [48]: The operating
ASLC is a Huffman-modeled ASLC with a self-timed SR-latch as shown in Figure 2.5
[3.49], in which the signal CZi is used to indicate the status of the SR-latch, while the

controller can be synthesized with a STG-modeled circuit.

 

 

AFSM

 

’0

Operating \
\ ' ASLC "

 

 

 

 

 

ll \ Internal
\ ‘ control
V s_ignal

 

 

 

v9

 

 

ll

 

 

 

 

 

 

 

 

 

 

 

 

Figure 2.4: An AFSM with data and control signals.

 

Szr

 

 

Zi
R21 I

Czr

 

 

Figure 2.5: A self-timed SR—latch.

l6

Hazards

When designing self-timed circuits, the problem of delay hazards [3,42] must be
considered. The delay hazard results from the fact that several of the OR- gate inputs go on
during the course Of a transition. Once one of them goes on, it is impossible to determine
from the output signal whether or not another one is on. If the circuit is designed to be that
only one input to each OR gate is energized during a given transition, then we are able to
tell from the output when the circuit has reached a stable state after an input change. Under
the unbounded gate delay assumption and the use of SR-latches to implement the logic
circuit as shown in [42], we only need to consider the problem caused by delay hazards
and to eliminate them. The strategy is to design the circuit such that no more than one

input to any OR gate is 1 at any time.

2.2 Testing Problems in CSLCs

The testability of a logic circuit has a great effect on the cost Of generating and
applying tests for the circuit. The greater the testability of a circuit is, the easier the testing
will be. The problem Of test generation is in general NP-complete and thus very intractable
for very large circuits. This demonstrates the necessity of designing easily testable
circuits. With the advent of VLSI circuits. the need for methods of design for testability
becomes more and more urgent. Many methods for measuring testability in logic circuits
have been proposed [35,50]. These methods in common introduce two measures.
controllability and observability, to estimate testability. Controllability is defined as a
measure of how easily the internal logic of the circuit can be controlled from its primary
inputs. Observability is defined as a measure Of how easily the internal logic of the circuit
can be observed at its primary outputs. The process of test generation consists of the tasks
Of controlling and observing internal logic values. Representatives Of controlling and
observing tasks in test generation are the consistency and D-drive operations Of the D-

algorithm [50,51], respectively. Therefore, the main issue for the testability of CSLCs is

17

strongly related to the controllability and observability of internal state variables.

2.2.1 Fault Model

A fault in a circuit is a physical defect of one or more components. Faults can be
classified as logical or parametric. A logical fault is one that causes the logic function of a
circuit element or an input signal to be changed to some other logic function; a parametric
fault alters the magnitude of a circuit parameter, causing a change in some factors such as
circuit speed, currents. or voltages [50,51].

Fault models serve two purposes. First. they help generate tests, and second. they
help evaluate test quality defined in terms of coverage of modeled faults. Stuck-at faults
are only the simplest faults to analyze, but they also have been proven to be very effective
in representing the faulty behavior of actual devices. In this study, single stuck-at faults

are assumed, i.e., only one stuck-at-0(1) fault occurs at a gate input or output at a time.

2.2.2 Synthesis for Testability

The techniques of synthesis for testability in CSLCs are to improve the
controllability and observability of internal state variables without extra input and output
pins. Therefore, the strategy is to identify all the redundant faults in the circuit and then to
eliminate them.

W

In a CSLC, a fault may be redundant [ll-l4], i.e., untestable. Redundant faults
may be combinationally redundant (CRFs) or sequentially redundant (SRFs). The effect
of a CRF cannot be propagated to the primary outputs or the next state lines, beginning
from any state, with any input vector. Three SRFs are classified: (1) Invalid-state faults;
(2) Isomorphic faults; and (3) Equivalent-state faults.

A CSLC can be generally represented by a state transition graph (C_STG to

distinguish from the STG for signal transition graph in ASLCs), where an edge joins si

18

and sj if there is any vector of primary input values that causes the circuit to evolve from
state si to state sj. A state which can be reached from the reset state via some input vector
sequence is called a valid state in the C_STG; otherwise, it is an invalid state. An edge is
said to be corrupted by a fault if either the fan-out state or an output of this edge is
changed because of the existence of the fault. The invalid-state fault does not corrupt any
fan-out edge of a valid state in the C_STG, but does corrupt the fan-out edge of an invalid
state [1 1].

An isomorphic fault results in a faulty machine that is isomorphic (with different
encoding) to the original machine. In [11], it was shown that stuck-at faults in a sequential
machine implemented by a two-level combinational network could not cause
isomorphism. A differentiating sequence for states 31 and 32 in a machine is a sequence of
inputs i1, i2, .., iN such that if the machine begins in state 51. the output associated with
input iN differs from that if the machine begins in state 32. Two states in a C_STG are
equivalent if they do not have a differentiating sequence. The equivalent-state faults cause

the interchange/creating of equivalent states in a C_STG.

Example I: (Equivalent-State Sequential Redundant Faults)

Consider a C_STG of a FSM, as shown in Figure 2.6(a), consisting of three states.
Figure 2.6(b) shows its next-state and output equations where the invalid state (11) is used
as don’t care for logic minimization. Figure 2.6(c) illustrates the complete C_STG for this
circuit. Assume that a stuck-at-O fault occurs at the x-input of the AND gate, xylyo, of Y0.
the corresponding faulty C_STG is shown in Figure 2.6(d). Starting from state (00) any
test sequence will produce the same output sequence for both fault-free and faulty
C_STGs, where states (00) and (01) are equivalent. Since the equivalent states are all valid
states, the fault is referred to as a valid/valid equivalent-state fault. Similarly, assume that
a stuck-at-l fault occurs at the x-input of the AND gate. xfio, of Y0, the faulty C_STG is
illustrated in Figure 2.6(e). where states (00) and (11) are equivalent. Since state (11) is an

invalid state, the fault is referred to as a valid/invalid equivalent-state fault.

l9

Y1=;§1
Y0 = X Y1 + XYrYo
Z=Y1

 

 

 

(a) (b) (C)

 

 

 

 

 

 

 

 

Figure 2.6: SRFs in CSLCs (a) State Transition Graph (C_STG); (b)
Logic implementation of (a); (c) The complete C_STG for
(b); (d) Valid/valid equivalent-SRF; and (e) Valid/invalid
equivalent-SRF.

20

Example 2: (Invalid-State Sequential Redundant Faults)

Invalid—state SRFs may occur as a result of improperly assigning the don’t care
states. Consider the invalid state (11). Suppose that its next state. a don’t care entry, is
assigned to state (00) and output is 0. Figure 2.7(a) shows the logic implementation and
the complete C_STG. Assume that a stuck-at—l fault occurs at the yo-input of the AND
gate, xylyo, of Y0, the corresponding faulty C_STG is illustrated in Figure 2.7(b). The
fault can be excited by state (11), but the invalid state (11) cannot be reached from any

valid state. Thus, the fault is an invalid-state redundant fault.

Example 3: (Isomorphic Sequential Redundant Faults)

The isomorphic fault results in a faulty machine that is isomorphic (with different
encoding) to the original machine. Figure 2.8 illustrates such a fault effect. where states
(01) and (10) are interchanged in the presence of a fault. It has been shown that stuck-at
faults in a sequential machine implemented by a two-level combinational network could

not cause states to be isomorphic [11].

CRFs can be eliminated via combinational logic optimization alone [10-14].
General methods for eliminating the above SRFs have been introduced in [14]. Isomorph-
SRFs can be eliminated if the combinational part of a sequential circuit is irredundant and
implements either a two-level logic or an inversion-parity invariant multi-level logic. One
solution to eliminating equivalent-SRFs and invalid-state SRFs is to expand the original
circuit so that 2n reachable and distinguishable states are all assigned properly, where n is
the number of flip-flops. An alternative solution is to implement a state minimization
process eliminating valid/valid equivalent-SRFs and invalid-state SRFs. or to carefully
assign the invalid states eliminating valid/invalid equivalent-SRFs. However, the latter

approach is a time-consuming process.

21

 

 

 

 

Y1 = 3 I1 Y0 = 8 ero + X3750
Z = Yryo
(a) (b)

Figure 2.7: Invalid-SRF (a) Fault-free C_STG; and (b) Faulty C_STG.

 

Figure 2.8: Isomorph-SRF.

22

W

Figure 2.9 shows the conventional iterative array model used for the test
generation in CSLCs. Each identical cell in this array represents a different time frame
from 1 to n. The symbols P1. P0, PS, and NS correspond to primary input, primary output,
present state, and next state. respectively. Based on this model, the sequential test
generation [10] is decomposed into two steps. First, an input sequence. T1 = (PIi, PF”, ...,
PI“), and an initial state SO. that excites and propagates the effect of the fault to the POD
are found. This step is called fault excitation and propagation and T1 is called the fault
propagation sequence. Next, state justification on SO is performed; i.e. a path from reset
state to SO is found consisting of another sequence of input vectors, T0 = (P11, P12, ...,
Pli‘l). T0 is called the justification sequence. Finally, the test sequence is the
concatenation of T0 and T1.

Similar concepts have been implemented for test generation of ASLCs [15,16].
Since each state transition in the ASLCs may take more than one time step before
stabilizing. each cell in Figure 2.9(b) is again represented by iterative arrays as shown in
Figure 2.10. The number of repeated arrays p in each time frame i depends on the number

of state transition steps.

2.2.3 Design for Testability

Design for testability techniques are divided into two categories [21,35]: ad hoc
techniques and structured approaches. Ad hoc techniques consist of heuristic methods to
solve testing problems for specific designs, but not directed at solving the general
sequential problem. This is contrasted with the second category of structured approaches
which are trying to solve the general problem with a design methodology. The structured
designs are generally applicable and usually involve a set of design rules for which
designs are implemented. Due to the lack of controllability and observability. testing of

sequential circuits has been recognized as a very difficult task. In order to reduce the

23

 

(PI) X0 ‘ xn-lJ. X/Y $20 " Zr-l (PO)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(PS) YO'Ym-l m ‘9 Yo-Ym,1(NS)
(a)
P11 P12 PI“ PI“
1 2 - n- n
LX/YNS XIYES. LX/Y‘IS X/Y S
l 2 O O O l1.1 n
—>
PS1 —| P82 1 P53!f —|PS“
to1 P02 P0"'1 P0“
(b)

Figure 2.9: (a) A sequential circuit; and (b) Iterative array model.

 

PI‘ 18‘

give

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

i i i '
PI X/Y RINSIL X/Y N82 L X/Y _——NSl
. . 1 . 2 l o o o . .
PSI 1( ) . 1( ) + 10’) PO!
PS5 —| P3},
P0{ Poi2

 

 

 

Figure 2.10: Test generation iterative array model for ASLCs.

24

complexity of test generation problem, scan designs have been proposed and successfully
implemented for CSLCs [20-24,55]. Vlfrth scan structures, all state variables of a
sequential circuit are completely controllable and observable from primary inputs and
outputs. Thus, the test generation problem is reduced to one of just testing the
combinational logic. In this subsection. a scan design, namely. Level—Sensitive Scan

Design (LSSD) is discussed.

I I-5 .l. S D .

Level Sensitive Scan Design (LSSD) is a technique developed by IBM to deal with
the testability issues [20]. The LSSD method, coupling a level-sensitive design concept
with scan operation, ensures race-free system operation as well as race-free testing. The
term level sensitive refers to the fact that the steady-state response of a circuit to any
allowable input change is independent of delays within the circuit. Also, the steady-state
response of the circuit must be independent of the order of input-value changes in the
event of simultaneous multiple changes. The key elements in the LSSD methodology are
the Polarity-Hold latch (PH) and polarity-hold Shift Register Latch (SRL) shown in
Figures 2.11(a) and 2.11(b). The SRL shown in Figure 2.ll(b) is simply a master-slave, D-
type flip-flop that is provided with an extra input stage for signals I and A. During normal
operation, the test input stage of the flip-flop is disabled and the circuit performs as a
normal master-slave, D-type flip-flop. During testing, the normal input stage is disabled to
allow the flip-flop to be loaded with the test inputs and scan out the values of the internal
state variables by connecting all the SRLs to form one or more independent shift registers.
Figure 2.12 shows the double-latch LSSD implementation [20]. Race conditions are
avoided by using separate, non-overlapping clocks for the master-slave flip-flops, thereby
providing the level-sensitive operation.

The LSSD methodology requires that the designer adheres to a set of basic design
rules [20]. The purpose of the LSSD rules is to improve the testability of the resulting

design. There are two fundamental constraints to the LSSD design [52]: (1) The value of

25

input datum should last for a long enough time when the pulse of storing signal returns to
its inactive value; (2) The pulse width of the storing signal must be larger than the
minimum time for regeneration in the feedback loop to take over control and maintain the
new value. Without satisfying these two constraints, races and hazards are unavoidable.
When these two constraints are satisfied, a key factor in the design of LSSD polarity-hold
latches is that the hazard may occur during clock turns off when storing a “1 A variety of
latch design techniques have been presented in [52.53] that solve the hazard problem. As
shown in Figure 2.11(a), the problems of this hazard are eliminated by adding the hazard
protection term. Dq. so that reliable operation can be achieved. Further, the correct
shifting responses have been verified by a set of test patterns proposed by Bottorff et. al.
[54]. referred to as BF GO test patterns. Basically, the test, referred to as BF GO test,
consists of two parts: a flush test, in which all shift clocks are turned on and a signal is
flushed through the register from the scan input to the scan output; and a shift test, in

which a 00110011 pattern is shifted through each register.

26

 

 

 

 

 

 

 

 

 

 

 

 

 

Q==DC+Cq+Dq

(a)

 

 

 

+L1

 

 

 

    
   
 

 

 

 

 

 

 

 

 

 

..O" '0:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

w
3"

 

(b)

Figure 2.11: LSSD scan design (a) Polarity-hold latch and its corresponding
K-map; and (b) Polarity-hold Shift Register Latch.

27

Network N

 

Scan Out

2
B Shift

Figure 2.12: Double-latch LSSD implementation.

Chapter 3

Fault Effects and Testability Synthesis Properties in ASLCs

 

An ASLC can be implemented either with asynchronous SR-latches for its state
variables, or without SR-latches [3,35]. The latter has also been referred to as with line
feedback [35]. In Section 3.1, the fault effects and testability synthesis properties of the
Huffman-modeled ASLCs implemented with line feedback is first discussed. Then, the
Huffman-modeled ASLCs implemented with SR-latches are described in Section 3.2. In
Section 3.3. the similarities and differences between Huffman-modeled and STG-modeled

ASLCs are presented.

3.1 Huffman-Modeled ASLCs with Line Feedback

In this section, the Huffman-modeled ASLCs are synthesized with the following
assumptions: (1) The circuits are operated and tested in the normal fundamental mode with
single input change; (2) Each circuit has a reset state and all input test sequences begin from
the reset state; (3) The circuits are implemented with two-level logic which consists of only
prime and irredundant implicants except the redundant logic for static hazard protection,
and there exist no shared logic for the next state equations and output equations; and (4)
The single stuck-at fault model is employed. The assumptions (3) and (4) imply that a
single stuck-at fault only affects either one next-state equation or one output equation at a

time. This simplifies the testing problem significantly. For state assignments. this chapter

28

29

considers two commonly used algorithms: critical-race-free Single- Transition-Time (S TI)
state assignment [3,30], and race-free Unit-Distance-Code (UDC) state assignment. also
referred to as totally sequential state assignment [26,27]. For simplicity. the ASLC encoded
with the STT (UDC) state assignment is referred to as the SIT-generated ( UDC-generated)
ASLC.

Based on assumption (3). Figure 3.1 illustrates the block diagram of an ASLC
implemented with line feedback, where 0L and NSL represent the output logic and the next

state logic, respectively.

 

 

 

 

 

 

Inputs

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Figure 3.1: Partitioned ASLC without shared logic.

3.1.1 Fault Effects

CSLCs can be considered as a special case of ASLCs with certain constraints on
input changes. Thus, the fault efl‘ects such as redundant faults that occur in CSLCs may also

occur in ASLCs. In addition, the state oscillation is a special fault effect in ASLCs due to

3O

critical races.

3.1.1.1 Redundant Faults

Similar to CSLCs, combinationally and sequentially redundant faults [10-14] may
also occur in ASLCs. However, since stuck-at faults could not cause isomorphism in a
circuit with two-level logic implementation, the sequentially redundant faults encountered

here are equivalent-state faults and invalid-state faults.

W

Two states are inequivalent if there exists at least a differentiating sequence for them
[10]. Equivalent states are generally eliminated by state minimization process. However,
equivalent states may occur as a result of faults. Equivalent-state redundant faults in ASLCs
may be generated due to (l) the constraint of single input change, (2) the non-critical races,
or (3) delays. In the CSLC implementations. the inputs can be any arbitrary combination.
Thus, two states are equivalent if they are indistinguishable with all input combinations.
Under the constraint of single input change in an ASLC, however, two states are equivalent
if they are indistinguishable with the current input and its adjacent inputs. The fault that
causes the equivalent states is redundant. On the other hand. a non-critical race generally
causes more than one transition paths to stabilize at the same stable state. If the effect of a
fault causes one of the transition paths to stabilize at a state that can be distinguished from
the corresponding fault-free stable state, (of course, the current state must be reachable
from the reset state), then the fault is detectable. However, if the fault effect forces the
circuit to take one of the transition paths for the non-critical race, then the faulty circuit will
end up with stabilizing at the same stable state as the fault-free circuit. Thus, it is also an
equivalent-state redundant fault.

Equivalent-state redundant faults may also occur due to delays. More specifically,
suppose that there exists a non-critical race between yl and y2. and suppose also that the

fault effect is detectable only through a transition path in which the change of y2 is faster

31

than y1. If the change of y2 becomes slower than y1 in the presence of fault, i.e. the fault
propagation path is blocked. the fault is then an equivalent-state fault. In order to
demonstrate the fault effects in ASLCs. Figure 3.2(a) shows a flow table of an ASLC.
Figures 3.2(b) and 3.2(c) respectively illustrate the SIT-generated ASLC and the UDC—
generated ASLC, where the circled entries in the table represent the stable states, and the
boldfaced terms in the final equations indicate the redundant terms for static hazard

protection.

Example I:

Consider the STE-generated ASLC shown in Figure 3.2(b). Assume that a stuck-at-
1 fault occurs at the xz-input of the AND gate. xlxzyl. of Y2. Figure 3.2(d) illustrates the
transition table of the corresponding faulty circuit, where the entries with asterisks
represent the contaminated entries caused by this fault and the boldfaced bits indicate the
bit change due to the fault. The fault causes the entries (xlxz-y1y2y3)=(00-000), (00-001).
(00-010), and (00-011), to change from (000) to (010). Assume that the current state is
(011) and the current input is (10). When the input is changed from (10) to (00), the next
state will stabilize at (000) in the fault-free circuit and at (010) in the faulty circuit. With
single input change constraint. the next applicable input is either (01) or (10). However,
both faulty and fault-free circuits result in stabilizing at the same state (011). for the input
(01), or (110), for the input (10). Thus, the fault is an equivalent-state redundant fault which
is due to the single input change.

Consider a stuck-at-l fault that occurs at xz-input of the AND gate, x2y1y2, of Y1.
Figure 3.2(c) shows the transition table of the corresponding faulty circuit. There are two
essential prime entries (xlxz-y1y2y3)=(00-110) and (10-11 1), as indicated by asterisks, that
can be used to detect such a fault. The fault causes the entry (xlxz-y1y2y3)=(00-110) to
change from (000) to (100) and the entry (x1x2-y1y2y3)=(10-111) to change from (011) to
(111). We first consider the entry (00-110). Assume that the current state is (110) and the

current input is (10). When the input is changed from (10) to (00), the state is changed from

 

 

 

@—
1991 ..

 

 

 

 

 

DJ
p—I
A
“(9
O
y—A
O
p—a

 

 

 

 

 

 

 

 

 

(a)

Y1Y2Y3 Present Input (xlxz) Present Input (xlxz)
\00011110 00011110

000—l011.|110 O 1 l 1 (1)

001 000 011 000 011 0 l 1 0

 

 

 

 

 

 

 

 

”*1 o- o- 1 2
g 000 ® 110 fit 0 o o ()
2;? 010 000 011 110 110 o 1 o 1

S —r t

m

E. 110 000 101 o 1 0 1 (3)
g 111 101 110 011 1 o o

 

 

101”|000 011 1 1 1 0 (4)

100 000 101l000 110 0 1 l l

 

 

 

 

 

 

 

 

 

 

 

Y1 = 3;mm + ;new + x11‘21’2 + X18233 + Kin-3:3 + x2Y1Y2
Y2 = i1x2§1 + Xryz + x182 + X5132
Y3 = §1Y1Y3 + g1x2 + X1§2Y3 + 8-2313?)

Z = 551an + i1"‘2 + x2§2 + 1"155235 + X553

0))

Figure 3.2: An ASLC for Example 1 (a) Merged flow table and output table;
(b) SIT-generated ASLC; (c) UDC- generated ASLC; and (d)&(c)
Transition tables of the corresponding faulty circuits.

Y1Y2Y3

Present State (Y1Y2Y3)

Present State (Y1Y2Y3)

000

001

011

010

110

111

101

100

001

011

010

110

111

101

100

33

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Present Input (x1x2) Y1Y2Y3 Present Input (x1x2)
00011_110 00011_110
001 .IOIO (1) 000. 001 .IOIO
O 'O O _j
0001011 (2) 001 000 .1011 .1
m m 010 --- 011 000 110 010 000
000 110 ”1 (3) 010 000 110 ”1
--- 100 -—- --- 110 100 100 000 101
111 100 100 010 001
m --- --- 001 101 100 100 011 001
1.. .L
”[1000 101 (4) 100 ”IIOOO 101
Y1=§1YI+32Y1§3+81X2Y2 _ _
Y2 = min + mm + X1X2ym + X13132)?»
Y3 = erm + x1X2Y1Y2 + X1Y2Y3 + X2Y1Y2g'3_ __
Z = X1X2 + X2Y2Y3 + X1X2Y1Y3 + x1Y1 + 1"13'13'23'3
(C)
Present Input (xlxz) Present Input (x1x7)
00011410 3011110
41
010 011 110(1) 000 011.|110
:1:
010 011 000 011 001 000 011 000 011
:11 r —‘ 1:, ’ —
1 on 012 on o-
0 1: O 0 O U :3 000 O 0 O
010 011 110 110 53 010 000 011 110 110
‘ 53 :11 T j_l
U)
000 101(3) E 110 100 101..l
W ill
101 101 110 011 3‘13 111101 101 110 111
u. 000 011 (4) 101..|1000 011
000 101 000 110 100 000|101 000 110

 

 

 

 

 

 

 

 

 

 

 

Figure 3.2: (Cont’d).

(1)

(2)

(3)

(4)

34

(110) to (000) in the fault-free circuit, as shown in Figure 3.2(b). Due to the non-critical
race, the change may follow either one of these two paths: 110—)010-9000 or
llO—-)100—>000. and the circuit stabilizes at the stable state (000) in the fault-free circuit.
On the other hand. in the presence of such a fault with input changed from (10) to (00), the
state is changed from (110) to (100). This fault forces the faulty circuit to take the transition
path 110—9100—-)000 and to stabilize at the stable state (000). Thus. both faulty and fault-
free circuits stabilize at the same stable state. This equivalent-state redundant fault is caused
by the non-critical race.

Consider the entry (10-111) for the above stuck-at-l fault. Assume that the current
state is (101) and the input is (00). When the input is changed from (00) to (10), the state is
changed from (101) to (011). The transition may take either 101—>001—)011. if the change
ofyl is faster than yz, or 101—>111—>01 1, if the change ofy2 is faster than yl, and the circuit
is finally stabilized at the stable state (011). On the other hand, in the presence of such a
fault, the transition path 101—>111-)011 is changed as 101—>lll-—)lll. This implies that,
if the change of y2 is faster than yl and the stable states (011) and (111) are distinguishable,
then this fault can be detected. However. the fault is an equivalent-state redundant fault due

to the delay if the change of y1 is faster than y2. 9

Equivalent states, under the single input change assumption. are inherently allowed
in the fault-free STT-generated ASLCs. For example, states (001) and (011), in Figure
3.2(b). have the same state entries and output entries at the input columns (00), (01), and
(10), i.e.. both states are equivalent if the current input is (00). The existence of such
equivalent states is because that non-critical race conditions are allowed in the STT state
assignment Thus, the race-free UDC-generated ASLCs generally have less equivalent—

state redundant faults than the SIT-generated ASLCs.

MEWS

A state that cannot be reached from the reset state via some input sequences is

35

called an invalid state. The invalid-state redundant fault does not corrupt any fan-out edge
of a valid state in the state transition diagram, but does corrupt the fan-out edge of an invalid
state, i.e.. the fault may only be excited by an invalid state. In CSLC implementations, the
invalid-state redundant faults are caused by the existence of invalid state(s). The invalid-
state redundant faults in ASLCs are caused not only by the existence of invalid states, but

also by improperly assigning the don’t care terms in the flow table.

Example 2:

Consider the transition table of a STT-generated ASLC shown in Figure 3.3(c).
Since only one state variable is changed during every state transition. it is also an UDC-
generated ASLC. Assume a stuck-at-O fault that occurs at the output of the AND gate, yly'z,
of Y1. Figure 3.3(d) illustrates the transition table of the corresponding faulty circuit. The
essential prime entries indicated by asterisks can be used as test patterns for fault detection.
This fault causes the entry (xlxz-y1y2y3)=(10-101) to change from (101) to (001) and the
entries (10-100) and (1 1-100) to change from (100) to (000). Suppose that the current state
is (101) and the input is (00). When the input is changed from (00) to (10), the fault-free
circuit stabilizes at the state (101) with an output (11), but the faulty circuit will stabilize at
the state (001) with an output (00). Sine the faulty and fault-free states are distinguishable,
the fault is detectable. However. the current state (101) is an invalid state, as shown in
Figure 3.3(b). and is not reachable from the reset state. Thus, the fault is an invalid-state
redundant fault.

On the other hand, assume a stuck-at-l fault that occurs at the xz-input of the AND
gate, Eli‘zylyg, of Y2. Figure 3.3(e) shows the transition table of the corresponding faulty
circuit. The fault causes the entry (x1x2-y1y2y3)=(01-001) to change from (001) to (011).
Since both stable states (001) and (011) produce the outputs (00) and (01), respectively,
they are distinguishable. Unfortunately, the entry is a don’t care entry, as shown in Figure
3.3(b). and is not reachable from the reset state. Thus, the fault is also an invalid-state

redundant fault. O

36

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Present Input (xlxz)
P I ( 2) 00 01 11 10
resent nput xlx - L J
00 01 11 10 000”] .lOOI 00
1G®2®01 001011 ---000.100
_ _ A @1
--- A >~ A
2 3@1 011.5: é"_.‘011...11101§1H
N >5 N
3@@3 1.10.3 §0101000900O .3
. 9‘ ”3 511
4 5 5 @® 105 E 110 01-0 010 105
5 @®@- 6 00 g 111 11069011 01
6 1 5 ® 00 101 --
(a)
(1))
Present Input (x1x2)
£0 01 11 10
000 O.‘ 001 00
- '1
001 011 000 @1 00
’3 i . — Y =- + - + +
3 011 11 @1 013 1 X1311 mz X1"2Y2Y3_:2Y1Y3
5 010 000 000 1091 Y2=Y1Y2+X1Y2+Y2Y3+X1X2Y1Y3
g i ' g Y3=§1Y2Y3 +Y1372Y3+571§1Y3 +82% +
m110..010 010 109‘ ___
g _ 5 x17‘2)’1Y2 + X1Y2Y3
101 ® 11 712=Y1§2+Y2Y3
100 11

 

 

 

 

(C)

Figure 3.3: An ASLC for Example 2 (a) Flow table; (b) Transition table with
don’t cares; (c) Transition table without don’t cares and its two-level
logic realization; and (d)&(e) Transition tables of the corresponding
faulty circuits.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Present Input (XIX?) Present Input (x1x2)
00011110 00011110
00000000000000100 00000000000000100
001 011 001 000 001 00 001 011 01? 000 001 00
§011 011 011 111 011 013 $5011 011 011 111 011 01$
E010 000 000 010 010 10% E010 000 000 010 010 10%
g 110 110 110 010 010 10%“ 2110 110 110 010 010 10%
£111 111 110 111 011 01 £111 111 110 111 011 01C
101 101 101 101 00? 11 101 101 101 101 101 11
100 100 100 000* 000711 100 100 100 100 100 11
(d) (e)

Figuer 3.3: (Cont’d).

3.1.1.2 State Oscillatlons

Consider a flow table and its state assignment and realization shown in Figure 3.4
[9]. Let the circuit be stable in State 2 (represented by y1=—0, y2=1) and input x=1. For the
state transition when x changes value from 1 to 0, G2 will begin to change to 1 and both Y1
and Y2 will begin to change their values. If y2 changes to 0 before yl changes to 1, 02 will
change to O and the variable y] may oscillate, i.e., the circuit causes a state oscillation
between State 1 and State 3, or even stabilizes at y1=0 instead of y1=1 if the delay
associated with G4 is sufficiently large. The resultant state oscillation or undesired stable
state is caused by the presence of critical-race from State 2 (01) to State 3 (10). In practice,
implementing a critical-race-free state assignment can avoid such a problem. However, the
state oscillations may occur as a result of faults. The following example is to show that, in

the presence of fault, both UDC- and SIT-generated circuits suffer from state oscillations.

38

 

X
0 1 YIYZ ‘*‘[>°—yl_3__
1©2 ..
4 C12
l 4 Y y
2390‘ DREW“

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

.@. . .
4 ”‘3—
1 ® 1 1 Y V2
2. Da—
(a) (b)

Figure 3.4: State oscillation due to critical races [9].

Example 3:

Consider the S'IT- generated ASLC shown in Figure 3.2(b). Assume that a stuck-at-
O fault occurs at the output of the AND gate, ilxzyl, of Y1. Figure 3.5(a) shows the
transition table of the corresponding faulty circuit. The fault causes the entry (x1x2-
y1y2y3)=(Ol-100) to change from (101) to (001) and a critical-race condition results.
According to the Karnaugh-map (K-map) for Yl-expressions shown in Figure 3.5(a),
(xlxz-y1y2y3)=(Ol-100) is the only essential prime entry which can be used to detect such
a fault. Thus, a state oscillation may occur if the change of y2 is faster than those of y] and
y3. Similarly, consider the UDC-generated ASLC shown in Figure 3.2(c). Suppose that a
stuck-at—O fault occurs at the AND gate, xzy'lyz, of Y2. Figure 3.5(b) shows the transition
table of the corresponding faulty circuit. The fault causes the entries (xlxz-y1y2y3)=(01-
011) and (OI-010) to change from (110) to (100) and critical-race conditions result.

Similarly, state oscillations may occur if the change of y1 is slower than that of y2. O

001
011
010
110

111

Present State (YlY2Y3)

101

100

Present Input (x1x2)

1_1

10

 

0007

011

®

110

 

000

011

000

011

 

000

110

—

 

000

011

110

110

 

000

101

—

00'

 

101

110

011

 

 

CI

000

011

 

000

 

 

0011000

110

 

 

 

Present Input (xlxz)

00

01

11

10

 

001

010

 

001

000

.1

011

 

011

000

4:

100

 

010

110

111

000

a:
100

 

100

100

 

100

100

 

101

100

100

—

001

 

 

 

 

120
I.

101

 

 

 

39

Present State (YIY2Y3)

(a)

Present State (Y1Y2Y3)

(b)

        

Present Input (x1x2)

00 01 11 10

000 0 0 l

001 0 0 0
011
010
110
111
101
100

i-IXZYI

00 01 ll 10

 

 

 

 

 

0010 01 0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

011 0 1* 1 | 0
010 0 1* 1 1

‘%=
110 0 0 0 0
111 0 0 1 0

 

101 0 0 1 0

 

1000 0 0 0

 

 

 

 

 

 

 

—X2§ 1Y2

Figure 3.5: Example 3 (a) Transition table of the corresponding faulty circuit for
SIT-generated ASLC and K-map for Y1; and (b) Transition table of
the corresponding faulty circuit for UDC-generated ASLC and 1(-
map for Y2.

40

Example 3 has shown that both state assignment schemes suffer from the state
oscillation due to the critical races that occur as a result of fault. An interesting problem that
naturally arises is whether or not the circuit is free of state oscillations if its faulty circuit is
race-free.

Let Si be a state of a fault-free UDC-generated ASLC, and Sui and Sfi be its next
states with the application of an input to the fault-free and faulty circuits, respectively. In
the fault-free circuit, Sni=Si if Si is a stable state, and the Hamming distance dH(Sni,Si)=l
if Si is unstable. On the other hand, for the affected next-state entry in the presence of a
stuck-at fault, dH(Sfi,Si)=l if Si is stable, and Sfi=Si or dH(Sfi,Si)=2 if Si is unstable. Note
that dH(Sfi,Si)=2 implies the existence of a race condition in the faulty circuit which
contradicts to the assumption of race-free faulty circuit. Also, Sfi=Si concludes that Si is
stable in the faulty circuit and no oscillation occurs. In other words, no state oscillations
occur when a stuck-at fault affects the unstable state Si. By a fault that affects the state Si,
we mean that the fault causes the next state to be SޢSm, i.e., both fault-free and faulty
circuits have different next states. Otherwise, the fault does not affect that state. Therefore,
the state oscillation may occur only when the fault affects those stable states S is such that
dH( S fl, S ,-)=1 . Note that, state oscillations may not occur in some cases even though a stuck-
at fault affects a stable state. For example, consider a transition pair (81, Sz) [30], where
81 is unstable, 82 is stable, and Sn1=Sn2. In the logic implementation, both Snl and Snz are
generally realized by the same gate. As a result, a fault that affects the stable state 82 will
definitely affect the unstable state 81. Thus, state oscillations will never occur in such a
case.

An oscillation loop is defined as a set of states Si’s, i=1,2,.., r, r22, where Sni=Si+b
i=1,2,.., r-l, and Stu—=81. If i=2, the oscillation loop is referred to as a two-state oscillation.
Otherwise, it is a multi-state oscillation.

Based on the above conclusion, we first consider the two-state oscillations.

41

Property 1: Two-state oscillations will never occur in a race-free faulty circuit.

2m: [By Contradiction]. Let SI and 82 be any two states of a fault-free circuit. Assume
that they form an oscillation loop in the presence of fault, i.e., Sfl=82, SQ=SI and
dH(Sl,Sg)=1, referred to as Condition A. Without loss of generality, we let

S1= (Yb-“YIN:YIFZ’YKH’H’Yn), and

52= (YI’--’YR-I’Yk=-i’)'k+1v-’Yn)a
where z is either 0 or 1, and E is the complement of 2. Three cases can be identified for SI
and 82: (a) both are stable; (b) both are unstable; and (0) one is stable and the other is
unstable.

For case (a), since 81 and 82 are stable, we have Sn1=Sl and 8112:82. If a stuck-at
fault affects S] (or, 82) at the state variable yt, tack, then Sf1¢82 (or, SfZ¢SI) which
contradicts to Condition A. On the other hand, A stuck-at—z (or, 'z') fault at yk causes
Sfl=Sn1=Sl¢Sz (or, Sa=Sn2=Sz¢Sl) which also contradicts to Condition A. For case (b),
a fault that affects the unstable states will never cause any state oscillation.

Finally, for case (c), without loss of generality, let 81 be unstable and 82 be stable.
No oscillations occur if the fault affects the unstable state 81, or if the fault affects the stable
state 82 and Sn1=Sn2 which makes (81,82) as a transition pair. Thus, we only consider the
case that the fault affects 82, but not 81, and Sn1¢Sn2. However, since Sn2=Sz, for stable
state 82, and Sfl=Sn1, for unstable state SI, we conclude that Sfl=Sn1¢Sn2=SZ which

contradicts to Condition A. Q.E.D.

Property 1 has shown that two-state oscillations will never occur in a race-free
faulty circuit. The next question that arises is whether or not multi-state oscillations will
occur in a race—free faulty circuit.

Races in UDC- generated ASLCs can always be eliminated by creating cycles, i.e.,
directing the circuit through intermediate unstable states before it reaches its final stable

state. For a UDC- generated ASLC, each column of the flow table represents an input state

42

and each row represents an internal state with the corresponding output state. In each
column, the states may be either stable or unstable, but each unstable state will transit to a
stable state at the same input column. In other words, there always exists a connected path,
denoted as Pa , from the current state, Sa, to the next stable state, Sb, where
Sa==sl—>sz—)..—)sk=Sb—)Sb and sj’s are the intermediate states with dH(sj,sJ-+1)=l,
j=1,2,..,k—1, and dH(sj,Sb)22, j=1,2,..,k-2, for any integer k. The connected path with a
length of k is referred to as k—connected path and Pab=(Sa,Sb) denotes the connected pair.
It is obvious that the single stable state in an input column is a I-connected path and a
connected path consisting of two states is a 2-connected path. For example, consider the
left flow table in Figure 3.2(c). In the input column 00, the state (100) is a stable state and
forms a l-connected path. The connected pair (000,001) is a 2-connected path in column
01. Similarly, the connected pair (001,010) in column 11 forms a 3-connected path.

Based on the above definitions, a sufficient, but not necessary, condition of

synthesizing a multi-state oscillation-free circuit is given in the following property.

Property 2: If each input column contains either
(1) at most one k-connected path, k > 3, or
(2) k-connected paths, k S 3,

then no multi-state oscillation occurs in a race-free faulty circuit.
Prior to the proof of Property 2, we first consider the following lemmas.

Lemma 1 : Any states in a k-connected path will never form an oscillation loop.

2:991: Consider a k-connected path Pab=(Sa,Sb). By definition, all states sj's, except Sb, are
unstable and dH(Sb,sJ-)22, j=1,2,..,k-2. Since no oscillations occur when a fault affects
unstable states, we only consider the case that the fault affects the stable state Sb, i.e., the
only possibility of forming an oscillation 100p is that the fault causes Sb to loop with sj’s,

j=l,2,..,k-1. However, since dH(Sb,sj)22, for j=1,2,..,l(-2, implies that Sfb¢Sj, hence, Sb will

43

never form an oscillation loop with these sj's. On the other hand, by Property 1, two states,
SIM and Sb, will never form an oscillation loop even though dH(Sb,sk-1)=l. This concludes
the lemma. Q.E.D.
Lemma 1 shows that any states in a k-connected path will never form an oscillation
loop. The question is whether or not the k-th connected path Pab=( Sa, S b) forms an
oscillation loop with any other states which are not included in that path. Apparently, the
necessary condition should be that there exist two states Sp, Sq e Pab: Sazslasz—xrasla
Sb-asb, such that dH(Sp,Si)=l, Sie Pab, and dH(Sb,Sq)=1, where Sp is stable, but Sq can be
either stable or unstable. For forming an oscillation loop, it is necessary that a stuck-at fault
affects all the stable states, but not the unstable states. Thus, in the presence of fault, the
conditions for forming an oscillation loop are
dH(Sp,Si)=1, Sie Pat» dH(sj,sj+1)=l, j=l,2,..,k-1, and dH(Sb,Sq)=l;
sfizsnjz j+1, for unstable states sj’s, j=1,2,..,k-1; and Condition B
Sfp=Si and Sfb=Sq.

Based on Condition B, the following lemma examines the possibility of forming oscillation

loops.

Lemma 2: In each input column, any k-connected path, k ._<. 3, will never form an oscillation

loop with any other states in the same column.

Bmf: [By Contradiction] For k=1, i.e., the connected path consists of only a stable state
Sb. Assume that the connected path forms an oscillation loop with any other states.
According to Condition B, we have the following conditions, referred to Condition 81:
dH(Sp,Sb)=dH(Sb,Sq)=1, Sp¢Sb, SqatSb, SfP=Sb, and Sm=Sq. Based on the first condition,
without loss of generality, we assume that Sp and Sb differ at the state variable ykl, while
Sb and Sq differ at ykz. So, their binary codes are
Sp=(Y10’2,"-’Ykl-I’YKl=zleItl-+l’--vYK2-l’YI<2=z2’Yk2+1w’Yn)’

Sb=(YI9Y2t“’tYkl-ltYkl=-z-I”kl-+1"°’yk2-I’YK2=229YK2+IW’YD)’ and
Sq=(YI 0'2”"”kl-l’YK1=21’YK1+1""YK2-1’YK2=22’yk2+1""yn)’

44

where 2], z2 6 {0,1}. Note that Snp=Sp and Snb=Sb for stable states SI) and Pb. Suppose that
a stuck-at fault affects Sp and Sb at the state variable yt, t¢k1. Since both sub and Sup differ
only at ykl, we have SfpatSb which contradicts to Condition B1. Suppose that the fault
occurs at ykl, a stuck-at-zl (or, 21) fault causes Sfp=Sp¢Sb (or, Sfb=Sb¢Sq) which also
contradicts to Condition Bl. This concludes that l—connected path will never form an
oscillation loop with any other states.

For k=2, the connected path Pab=(Sa,Sb). Suppose that the connected path forms an
oscillation loop with any other states. Connecting two states SI) and Sq to the path, two
possible oscillation loops may be formed: (1) Sp connects to Sa, i.e., Sp—>Sa—)Sb—->Sq—>...;
or (2) SI) connects to Sb, i.e., Sp—)Sb—>Sq—)... The latter 100p is similar to the case of k=1
which will never form an oscillation. Thus, we only consider case (1). According to
Condition B, we have the following conditions, referred to as Condition BZ:
dH(Sp,Sa)=dH(Sa,Sb)=dH(Sb,Sq)=l; Sp, Sq e {Sash}; and Sfp=sa, Sfa=Sna=Sb, and

Sm=Sq. Without loss of generality, we assume the following binary codes for these

variables
Sp=(y1,...,yk1=zl,...,yk2=zz,...,yk3=23,...,yn),
Sa=(y1,...,yk1=zl,...,yk2=22,...,yk3=z3,...,yn),
Sb=(y1,...,yk1=zl,...,yk2=22,...,yk3=23,...,yn), and
Sq=(YIv-~’Yk1=-z-l’---»YR2=22’---’Yk3=-z—3v--’Yn)’ 0r (ql)
Sq=(Y1’-~9Yl(1=zlv---’Yk2=22v--’YI(3=Z3’°--’yn)s (qZ)

where 2], z2, z3 6 {0,1 }. Similar to the proof for k=1, a stuck-at fault at yt, t¢k1, or a stuck-
at-zl at ykl, results in Sfp=Sp¢Sa, regardless of implementing with (ql) or (q2), which
contradicts to Condition B2. On the other hand, the stuck-at-zl at ykl forces
Sfb=Snb=Sb¢Sq, in (ql), which also contradicts Condition B2. This concludes the Lemma
for k=2.

Similarly, for k=3, the connected path Pab=(Sa,Sb):Sa—>Sc—>Sb. Connecting the
states Sp and Sq may result in three possible loops: (1) Sp—)Sa—)Sc—)Sb-)Sq—>...; (2)

Sp—>SC—>Sb—-)Sq—)...; or (3) Sp—>Sb—>Sq—).... The latter two cases are similar to k=2 and

45

k=1, respectively. Thus, we only consider case (1). The same procedure in the proof for k=2

can be used to prove for k=3. Q.E.D.

W. Based on Lemmas l and 2, n0 multi-state oscillations occur in a race-

free faulty circuit. Q.E.D.

The following discussion will show that the conditions in Property 2 are sufficient,
but not necessary. Consider a 4-c0nnected path Pab=(Sa,Sb):Sa—>Sc—>Sd—>Sb and there

exist two states SD and Sq with the following binary codes

Sp=()'1.....yk1=21..--.Yk2=22r--’Yk3=z3""’yn) ’

Sa=(y1,...
Sc=(YI~---
Sd=()'1w-
Sb=(Yl’---
sq=(yl,..

Jkl=21w~
,yk1=21,...
,yk1'—’Zl,...
.yk1=zi.---
.,yk1=21,...

,ykzzzzw.
,yk2=22,...
,yk2=22,...
,yk2=22,...
,yk2=22,...

38:23,...
00:13:13,»-
,yk3=23,...
33:23,...
,yk3='z'3,...

.yn).
.yn).
,yn).
’Yn)’ and

’Yn)’

where zl, 22, and 23 are either 0 0r 1. Apparently, dH(Sp,Sa)=dH(Sa,Sc)=dH(Sc,Sd)=
dH(Sd,Sb)=dH(Sb,Sq)=l, and Sp, Sq e {Sa,SC,Sd,Sb}; On the other hand, in the presence of
a stuck-at-zl at ykl, it is easy to verify that Sfa=Sna=Sc, Sfc=Snc=Sd, Sfd=Snd=Sb, Sfa=Sa,
and Sfb=sq. Thus, these binary codes satisfy Condition B and, thus, state oscillation may
occur. The following example illustrates the detailed encoding and state assignment, where

the circuit contains an input which consists of two 4-c0nnected paths.

Example 4:

Consider the partial flow table of a given ASLC shown in Figure 3.6(a). The
boldfaced states, as shown in Figure 3.6(b), indicate races. Since States 1, 3, and 5 have the
same next state 4, the UDC state assignment creates cycles by modifying the entries of
states 1 and 2 as intermediate states to form a connected path 3(011)-—)1(001)-—)
5(101)—)4(100). Similarly, the other connected path, 0(000)—>2(010)—-)6(110)—)7( 111), is
also generated. Both paths are illustrated by the boldfaced arrows in Figure 3.6(d). Suppose

that a stuck-at-O fault occurs at the output of the AND gate, yllp, of Y1, Figure 3.6(e) shows

46

 

 

 

IP IP IP

0 7 (0)000 111 000 010
1 4 22(1)001 100 1:. es. 001 101 I;
>« a >~
2 7 a(3)011 100 N ,>~_ 011 001 N
a >. >~
:3 3 3) '-° b >7
m 3 4 g 93 (2)010 111 2:, 3 010 110 v
g 4 Q.) E r§(6)110 111 g g 110 111 g
m 5 4 §(7)111@g g 111®§
6 7 5 (5)101 100 z 53 101 100 Z

7 (D (4)100 100

Y1 = yilp + Y23731p + §2Y31p

(a) (b) (C)

0‘0 0 333 333:: @t® o
"‘ ‘3 010 110 E "4
“WW” :1? 2:13 ®‘@fl®

 

(d) (e) (4)

Figure 3.6: An ASLC example (a) Partial flow table; (b)&(c) Transition table; ((1)
Connected path; (e) Transition table of the corresponding faulty circuit;
and (f) Connected paths form an oscillation loop.

47

the partial transition table of the corresponding faulty circuit which does not have races.
However, in the presence of such a fault, both connected paths form an oscillation loop,

011—>001-)101—9100—) 000—)010—>110—9111—-)011, in Figure 3.6(f). 0

An alternative sufficient, but not necessary, condition for synthesizing oscillation-
free circuit is also given as follows. Two connected paths are disjoint if they have different

final stable states.

Property 3: If there exist two disjoint k-connected paths, k>3, and dH(Sx,Sy)>l for all SK
and Sy in different connected paths, then no multi-state oscillations occur in the race-free

faulty circuit.

m: By Lemma 2, the k-th connected paths, 1:53, will never form an oscillation with any
other states. Thus, the only possible multi-state oscillation loop is formed by these two 1(-
th connected paths, k>3. However, since dH(Sx,Sy)>l for all SK and Sy in different

connected paths, Condition B will not be satisfied. Thus, no oscillation will occur. Q.E.D.

Properties 2 and 3 provide simple mles for synthesizing oscillation-free UDC-
generated ASLCs if the faulty circuit is race-free. although races in the UDC-generated
ASLCs can always be eliminated by creating cycles, Properties 2 and 3 guarantee that no
state oscillations occur in a race-free faulty circuit if the circuit is synthesized in such a way
that each input column allows to have either only a long connected path, or two connected
paths, with k>3, and dH(Sx,Sy)>1 for all SK and Sy in different connected paths.

For detecting a fault, it may need one or more test sequence. If a circuit is
synthesized by the rules provided in Properties 2 and 3, and the faulty circuit is race-free
with the application of such the test sequences, we guarantee that the faulty circuit is free
of state oscillation. On the other hand, if the faulty circuit is not free of races with the
application of all possible test sequences for detecting a fault, state oscillations may occur.

In such a case, detecting such a fault is rather a difficult task due to the unpredictable

48

“stable” states.

3.1.2 Testability Synthesis Properties

This section discusses the testability properties for synthesizing both SIT-generated
ASLCs and UDC-generated ASLCs. Here, the combinational circuit of an ASLC is
optimized with prime and irredundant implicants except the redundant logic for static
hazard protection.

A fault is detectable if its fault effects can be excited and pr0pagated to the primary
outputs and the fault site can be reached from the initial state. Thus, a fault is detected by
applying a test sequence which is comprised of a fault propagation sequence and a
justification sequence. Let Si be a state of a UDC- or SIT-generated ASLCs. Let Tpil and
Tpio denote the fault propagation sequence and justification sequence for the faulty next—
state entry of Si in the input column Ip, respectively. As defined in Section 3.1.1.2, Sui and
Sfi are the next states of Si in fault-free and faulty circuits, respectively. Spni and Spfl are
denoted as the Sm and Sfi in the input column 1p, respectively. A fault is detectable if there
exists a state Si such that (1) SpniatSpfi; and (2) there exist the sequences T9“ and Tpio. For
simplicity of discussion, the first condition is referred to as Condition C.) , while the second
as Condition C.2. Note that no critical races are allowed when both sequences T9“ and Tpio
are applied.

For simplicity, State Si is represented by a n-tuple binary vector (y1,y2,..,yn), and Sij
denotes as the yj bit of Si. DH(SI,SZ)=j means that 311:521 for all i except j, i.e., SI and 82
differ in one bit which is the yj bit. When a state transition occurs, some bits may be
changed. Let Xu(Si,Sj)={Sileik=SJ-k, k=l,2,..,n} and Xc(Si,Sj)={Sik|Sik¢SJ-k, k=1,2,..,n}
denote the sets of unchanged and changed bits in a state transition from Si to Sj.

Based on Condition C, the testability synthesis pr0perties are derived. Moveover,
a state S] is said to be distinguishable from another state 82 in the input column Ip if there

exist an input sequence such that the output sequence starting from Spa is different from

49

that starting from Spa.

Watches

As defined in Section 2.1, a K-set in a single column of a flow table consists of all
(k-l) unstable entries leading to the same stable state, together with the stable state [30,34].
A pair of states [Si,Sj] consisting of one unstable state Si and the stable state Sj of a K-set
is called a transition pair. In generally, a K-set may contain one or more transition pairs and
each input column may contain one or more K-sets. The set of states which the circuit may
assume in undergoing a transition between the states of a transition pair [Si,Sj] is called the
transition path (TP) of [Si,Sj] and denoted as TPij. For example, if Si=(1000) and
Sj=(1110), then TPij=(1--0)={(1000), (1010), (1100), (1110)}, where Xu(Si,SJ-)={1,4} and
Xc(Si,Sj)={ 2,3 }. Therefore, if yk in Xu(Si,Sj), then yk=0 or 1 in TPi-; if yk in Xc(Si,Sj), then

H ’9

yk= (don’t care).

For a STT state assignment, every state transition between a transition pair is direct
[30]. The S'l'l‘ state assignment was developed based on the theory of partitions. A partition
It on a set S is a collection of the subsets of S such that their pairwise intersection is the null
set and the disjoint subsets are called the blocks of 7:. Each state variable is determined by
a partition by assigning 1 to a block and 0 to another block. An internal state variable which

partitions one transition path from another is called a partition variable.

Tracey’s Theorem [30]: A state assignment alloting one y-state per state can be used for the
realization of STT flow tables without critical races if, and only if the following conditions
hold for every transition pair [Si,Sj], Sj a stable state.
(1) If [Sm,Sn] is another transition pair, j¢n, in the same column, then at least one
partition partitions the pair [Si,Sj] and the pair [Sm,Sn] into separate blocks;
(2) If Sk is a stable state in the same column j¢k, then at least one partition partitions
the pair [Si,SJ-] and the state Sk into separate blocks; and

(3) For iij, Si and Sj are in separate blocks of at least one partition.

50

During the state transition of a transition pair, some state variables are changed and
some others are unchanged. Conditions (1) and (2) show that Xu(Si,Sj)¢¢ (null set), while
Condition (3) implies XC(Si,SJ-)¢¢. That is, the conditions imply that bot Xu-set and Xc-set
are non-empty sets.

It should be mentioned that, using the K-sets instead of transition pairs, Tracey’s
Theorem can be expressed as follows [30,34]: A direct transition in a K-set k1 does not race
critically with a direct transition in a K-set k2 if an assignment has been made such that at
least one y-variable partitions the elements of k1 and the elements of k2 into separate
blocks. Apparently, this theorem keeps the first two conditions in Tracey’s Theorem, but it
might not generate minimum number of state variables.

Consider a transition pair [Si,Sk] in a K-set and in input column 1p. Faults may occur
at the bits in Xc(Si,Sk) or in Xu(Si,Sk). We first consider the former case, where the bit is

changed during the state transition.

Lemma 3: If Sj in TPik and a stuck—at fault occurs at yr in Xc(Si,Sk), then Spnj in TPik and
spa in “rpm.
M: According to the STI‘ state assignment, Spnj=Sk in TPik. On the other hand, yr in

Xc(Si,Sk), hence yr=”-” in TPik. Thus, in the presence of a stuck—at fault at yr bit, 896 in

Tpik With 611.116! 86:8,“ 01' 85:6,“. QWED
Based on Lemma 3, the following theorem results.

Theorem 1: A stuck-at fault that occurs at yr in Xc(Si,Sk) is detectable if (1) Spfk¢spnk,
where Sk is the stable state in a K-set; (2) there exists a state Sj such that Si in T'Pik and
DH(Sj,Sk)=r, Si is distinguishable from Sk in the input column 1p; and (3) [Si,Sk] is

reachable from the reset state.

m: Since Sj in TPik, it implies that Spnj=Sk. By condition (1) and DH(Sj,Sk)=r, this fault

will cause spfsj. Two cases can be distinguished: Case 1: If Spfi=Spnj=Sk, it will result

51

in state oscillation between Sk and Sj. However, from the result of Property 1, this case will
not occur. Case 2: Spfifipnj, it implies that the Sj will become a stable state in the presence
of fault and it satisfied Condition C]. Further, for an unstable state S“, where Su in TPik
and Su¢Sj, either dH(Su,Sk)22 or DH(Su,Sk)=m with m¢r. A stuck-at fault at yr bit will not
result in Su to become a stable state. As a result, Sj is the only stable state in TPik in the
presence of faults. By Lemma 3, the state transition will also be in TPik. Conditions (2) and
(3) imply ijl and ij0 exists respectively. Therefore, Condition C.2 is also satisfied and
this fault is detectable. Q. E.D.

The condition SpflatSpnk in Theorem 1 implies that the redundant faults as shown
in Example 1 will not occur in the presence of faults. Now, consider the stuck-at fault that
occurs at yr in Xu(Si,Sk). If such a fault occurs and there exist no other transition pairs
which satisfy the conditions in Theorem 1, then critical races may occur as a result of faults.
The following lemma is used to guarantee that the introduced races are non-critical such

that the stuck-at fault can be detected.

Lemma 4: Let [Si,Sk1] be a transition pair in a Kl-set, in an input column 1p. A stuck-at
fault that occurs at yr in Xu(Si,Sk1) is detectable, if (1) SpfklatSpnkland C is the minimal
cube that contains all the states St’s in TPikl with SpmaeSpfl; (2) A cube D in Tij2, the TP
of a Kz-set, where K2¢K1, and DH(D,C)=r; (3) SH is distinguishable from Skz in the input

column Ip; and (4) [Si,Sk1] is reachable from the reset state.

m: By SpmaeSpnkl, Condition C.) is satisfied. Further, when a stuck-at fault occurs yr
in Xu(Si,Sk1), a critical-race condition results in the cube C. Let E=C U D. The introduced
races in C will become non.critical in E. Since SptklaeSpnkl, the faulty circuit will finally
stabilize at the state Sn. By conditions (3) and (4), both sequences Tpku and Tpklo exist

and satisfy Condition C.2. Thus, the fault is detectable. Q.E.D.

52

Similar to the results of Theorem 1, if the stable state of the transition pair is not
affected, then critical races may result and the behavior of a faulty circuit is unpredictable.
Note that a K-set may contain one or more transition pairs and each input column may

contain one or more K-sets. Similar to Lemma 4, the following theorem results.

Theorem 2: Let yr be the bit to distinguish Kl-set from other K-sets. A stuck-at fault that
occurs at yr is detectable if (1) SpmatSpnkland C is the minimal cube contains that all the
states St’s in Wild with SpntvtSpfi; (2) A cube D in TPJ-kz, the TP of a K2-set, where K2¢K1,
and DH(D,C)=r; (3) Sn is distinguishable from 51:2 in the input column 1p; and (4) [Si,Sk1]

is reachable from the reset state.

2:991: A fault is detectable if there exists a test sequence which can distinguish the

behavior of fault—free and faulty circuits. Therefore, by Lemma 4, this fault is detectable.

Q. E. D.

For an ASLC implementation, Theorem 1 can be first used to check whether or not

a stuck-at fault is detectable. If not, then Theorem 2 is applied.

W

Those synthesis properties for STT-generated ASLCs can be further modified for
UDC-generated ASLCs. Races in a UDC-generated ASLC can always be eliminated by
creating cycles. Thus, for a connected pair (Sash), where S3 is the current state and Sb is
the next stable state with the application of the input Ip, there always exists a connected path
Sa=so-—>sl—> ..—)sk=Sb —9 Sb, where sj’s are the intermediate states with dH(s-,sj+1)=l for
each adjacent pair (s-,sj+1), j=0,1,..,k-l, and k is an arbitrary integer. Further, two connected
paths with different stable states must be disjoint. Let Xu(Si,Sni)={ 5195115311110 k=1,2,..,n}
and Xc(Si,Sni)={ Siklsik¢snikv k=1,2,..,n} denote the sets of unchanged and changed bits in
a state transition from Si to its next state Sm. In UDC state assignments, the cardinality

lXc(Si,Sni)l $1. If IXC(Si,Sni)I=0, si is a stable state. If IXc(Si,Sni)l=l, si is unstable

53

Theorem 3: A stuck-at fault that occurs at yr in Xc(Si,Sni) is detectable if (1) Si in Pab,
where Si is an unstable state in the input column 1p, and Spfitspni; (2) Si is distinguishable

from the state Sb in the input column Ip; and (3) Tpio exists.

m: For a UDC-generated ASLC with DH(Si,Sni)=r, the first condition satisfies
Condition C] and results in Spfi=Si in the presence of fault at yr-bit. The second and third

conditions satisfy Condition C.2. Thus, this fault is detectable. Q. E.D.

Consider a connected path Pab in the input column 1p, if a stuck-at fault occurs at yr
in Xu(Sb,Snb) with Spfb¢spn , Sb will become an unstable state and no critical races occur.
On the other hand, if a stuck-at fault occurs at yr in Xu(Si,Sni) with SpfiatSpni, where Si is
an unstable state in Pab, critical races may occur. The following theorem considers the
testability synthesis property when a stuck-at fault occurs at yr in Xu(Si,Sni) in the UDC-
generated ASLCs.

Theorem 4: A stuck-at fault that occurs at yr is detectable if (1) SpfbatSpnb and Ptbe Pa ,
where St is either the stable state or the first intermediate state with SpftatSpm and yr in
Xu(St,Sm); (2) a path P, which is part of another disjoint connected path Pcd, differs from

Pa, in yr-bit; (3) Sd is distinguishable from Sb; and (4) Pab is reachable from the reset state.

Em: Similar to the proof of Theorem 2. With SpfbatSpnb, whenever races occur in Pa, in
the presence of fault, condition (2) ensures that the races will force the state transition to
enter one of the states in Pod and finally stabilize at Sd. Together with conditions (3) and

(4), this fault is detectable. Q.E.D.

In general, a fault may or may not result in race conditions in the faulty circuit.
Without race conditions, either the affected unstable state become stable or the affected
stable state become unstable. Theorem 3 deals with the affected unstable state without races
and Theorem 4, with St=Sb, is concerned with the affected stable state without races. On

the other hand, when S. is the intermediate state, Theorem 4 consists of testable conditions

54

for the faulty circuit with races. Condition (2) in Theorem 4 is needed for avoiding state
oscillations and eliminating equivalent-state redundant faults. However, to find a disjoint
connected path that includes the path P may not be practical, particularly for a long
connected path P“). As discussed previously, multi-state oscillations can be avoided if the
length of the connected path is limited (Property 3). Similarly, if the length of the connected
path is limited during the state assignment phase, then synthesizing testable circuit can be
easier. To have a better understanding of previous Lemmas and Theorems, the following
example is used to demonstrate those results for STT-generated ASLCs. Similar concepts

can also be applied to UDC-generated ASLCs.

Example 5:

Consider the ASLC used in Example 1. There exist two K-sets in input (11) column,
where Kl-set consists of only one transition pair [101,000] with transition path TP101,000
={(101),(100),(001),(000)} and KZ-set consists of one transition pair [011,110] with
TP011,110={(011),(010),(111),(110)}. Both transition pairs (or sets) are partitioned and
distinguished by yz-bit, where y2=0 for [101,000]and y2=1 for [011,110] with Sk1=(000)
and Sk2=(110)- Assume that a stuck-at-l fault occurs at yl-input of the AND gate, x1x2y2,
of Y1. Figure 3.7(a) shows the transition table of the corresponding faulty circuit, where the
yl-bit of the states in TPIOLOOO are all changed from 0 to 1 as indicated by asterisks. It is
obvious that the affected states are still in the same transition path. Consider the state (100)
in TP101,000, which is adjacent to the stable state (000). If states (100) is distinguishable
from (000) and the state (101) can be reached from the reset state, by Theorem 1, such a
fault is detectable. Assume that a stuck-at-l fault occurs at the xz-input of the AND gate,
x553, of Y1. Figure 3.7(b) shows the transition table of the corresponding faulty circuit.
By Theorem 1, since the stable state is also affected, the fault is detectable if states (100) is
distinguishable from (000) and state (101) is reachable from the reset state. Consider the
input (01) column which consists of two K-sets, where Kl-set consists of only one

transition pair [000,011] with TP000,011={(000),(010)’(001)’(011)} and Kz-set consists of

Present State (YIYZY 3)

Present State()’1)’2)’3)

Present Input (xlxz)

_09

01

ll

10

 

011

*
100

110

 

001

000

011

3|!

100

011

 

011

000

.1110

 

010

000

011

110

 

110

000

101

0'

 

111

101

101

110

 

101

u

1100

*

 

100

000

 

101

a:

100

 

 

 

 

 

001
011
010
110

111

101

100

(a)

Present Input (x1x2)

_‘10

01

11

10

 

111

*0

110

 

000

a:
111

000

011

_

 

000

a):
111

110

.1

 

000

q.
111

110

110

 

000

101

1.

 

101

110

011

 

1.

l 000

011

 

101
000

 

101

000

 

 

110

 

 

 

(C)

55

Present State (Y1Y2Y3)

Present State(Y1Y2Y3)

Present Input (x1x2)

00

01

ll

10

 

011

41
100

110

 

001

011

000

 

011

.' 110

 

010

011

110

_¥

 

110

101

”-

 

111

101

101

110

 

101

1000

 

100

 

000

101

 

*

100

 

 

 

 

001
011
010
110

111

101

100

0))

Present Input (xlxz)

l0

01

1_1

10

 

011

@

110

 

000

011

000

011

 

000

:1:
111

110

91

 

000

:1:
111

110

110

 

000

101

6

 

101

110

011

 

l.l 000

011

 

101
000

101

 

 

000

 

110

 

 

 

((1)

Figure 3.7: Transition tables for Example 5.

56

one transition pair [110,101] with TP110’101={(110),(111),(100),(101)}. Both transition
pairs are partitioned and distinguished by yl-bit, where y1=0 for [000,011] and y1=l for
[110,101]. Figure 3.7(c) shows the transition table for a stuck-at-l fault that occurs at the
yl-input of the AND gate, xlxzyl, of Y1. By Theorem 2, such a fault is detectable if the
state (000) can be reached from the reset state. Similarly, Figure 3.7(d) shows the transition
table for a stuck-at—l fault that occurs at the yl-input of the AND gate xlxzyl, of Y1. The
states (011) and (010) in TPOOODII are affected, where this subset includes the stable state
(011). Moreover, both states, (111) and (110), are included in the TP of the transition pair
[110,101] in another K-set. Thus, the fault is detectable if the affected state (000) can be

reached from the reset state. 0

3.2 Huffman-Modeled ASLCs with SR-Latches

Figure 3.8(a) illustrates the truth table of a SR-latch, where (QQ) are undetermined
when (S,R)=( 1,1). The values will be assigned when the SR-latch is implemented either
with NOR or NAND gates, as shown in Figures 3.8(b) and 3.8(c), respectively. Note that
when the inputs (S,R) are changed from (1,1) to (0,0), the next state, which is either (0,1)
or (1,0), is determined by the race between the signals S and R. For a reliable design,
(S,R)=(l,l) has been avoided. However, it may occur as a result of faults.

This section describes the fault effects for Huffman-modeled ASLCs implemented

with SR-latches where the excitation table for the latch is shown in Table 3.1.

3.2.1 Fault Effects

Let 3Y1 and Ry, respectively denote as the set (S) and reset (R) inputs of a SR-latch
for the state variable Yi. Suppose that the ASLCs under consideration, as shown in Figure
3.9, are synthesized under the assumptions described in Section 3.1, where each CLB
(combinational logic block) does not share any logic with any other CLBs. Because the

output values of the SR-latch remain unchanged when S=R=0, no static logic l-hazard

57

 

S . G 8—0 Q
..,;

 

 

 

 

 

 

 

S R Q 0 R ’ Q R—c Q
0 0 No changes _
0 1 0 1 5 R Q Q S R Q G
l 0 l 0 0 0 No changes 0 0 No changes
1 l undetermined 0 1 0 l 0 l 0 1
1 O 1 0 1 0 1 0
(a) 1 1 0 0 1 1 l 1
(b) (C)

Figure 3.8: (a) Operation of SR-latch; (b) NOR-gate implementation;
and (c) NAND-gate implementation.

protection terms are needed [37]. This section describes the fault effects such as redundant

faults and state oscillations.

3.2.1.1 Redundant Faults

Based on the assumptions described in Section 3.1 with no hazard protection terms,
the logical functions S“ and RYi are implemented with two-level logics which are prime
and irredundant. Thus, there exist no combinationally redundant faults in that circuit. Two

types of sequential redundant faults are discussed.

W

The following example demonstrates the equivalent-state redundant faults that may
occur due to (1) the constraint of single input change, (2) the non-critical races, or (3)

delays.

58

Inputs
—1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Figure 3.9: SR-latches implementation without shared logics.

Table 3.1: SR-Latch Excitation Table

 

Q(t) Q(t+1) S R
0 0 0 -
0 1 1 0
1 0 0 1
l 1 - 0

 

59

Example 6:

Consider the STT-generated ASLC shown in Figure 3.10. The circuit is realized
with the SR-latches and its logical equations for 8y, and RYi are shown in Figure 3.10(c).
Assume that a stuck-at-O fault occurs at the output of the AND gate, xlxzyz, of 5Y1- The
fault causes the entry (xlxz-y1y2y3) =(11-011) to change from (110) to (010) and the entry
(xlxz-y1y2y3)=(ll-010) to change from (110) to (010). Assume also that the current state
is (011) and the current input is (10). When the input is changed from (10) to (11), the next
state will stabilize at (110) in the fault-free circuit and at (010) in the presence of this fault.
With the single input change constraint, the next applicable input is either (01) or (10). As
a result, both faulty and fault-free circuits will stabilize at the same state (000) for the input
(01), or at (110) for the input (10). This is an equivalent-state redundant fault due to the
constraint of single input change.

Consider a stuck-at-O fault that occurs at output of the AND gate, xlxz, of Syz. The
fault causes the entry (x1x2-y1y2y3)=(10-101) to change from (011) to (001) and the entry
(xlxz-y1y2y3)= (10- 100) to change from (110) to (100). We first consider the entry (10— 101)
and assume that the current state is (101) and the current input is (00). When the input is
changed from (00) to (10), the state is changed from (101) to (011) in the fault-free circuit
as shown in Figure 3.10(b). Due to the non-critical race, the change may follow either one
of these two paths: 101—>001—9011 or 101—>111—-)011, and the circuit stabilizes at the
stable state (011) in the fault-free circuit. On the other hand, in the presence of such a fault
with input changed from (00) to (10), the state is changed from (101) to (001) and the fault
forces the faulty circuit to take the transition path 101—>001—9011 and to stabilize at the
stable state (011). Thus, both faulty and fault-free circuits stabilize at the same stable state.
This is an equivalent-state redundant fault due to the non-critical race.

Consider the entry (10-100) for the above stuck-at-O fault. Assume that the current
state is (000) and the current input is (11). When the input is changed from (11) to (10), the
state is changed from (000) to (110). The transition may take either 000—->010—)110, if the

60

x1x2 x1x2
00011110 00011110

 

 

 

 

(9
16°)3

 

 

U)
A
1—1
G)
1—
O
O
1—1

 

 

 

 

 

 

 

 

 

 

 

 

A
p—g
N
H
p—r
p—r
O

 

 

(a)

Y1Y2Y3 Present Input (X1x2) Present Input (x1x2)
00011110 00011110

000 011..I 110 1 0 l 1 (l)
000

 

 

 

 

 

 

 

 

 

 

 

 

001 011 000 011 1 0 1 0
<1... 0 2
g $1 000 110 @1 1 0 0 0 ()
339 010 011 000 110 110 1 0 0 1
8 ! _

m
.5 110 101 000.. 1 0 0 1 (3)
g 111 101 110 011 1 - 0 0

 

 

 

 

101..11000 011 1 1 1 0 (4)
000

100 101 000 110 l 0 1 l

 

 

 

 

 

 

 

 

 

 

 

 

(b)

Figure 3.10: An ASLC example (a) Merged flow table and output table; (b)
STT-generated ASLC; and (c) Logic implementation for (b).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

SYlRYl Present Input (x1x2)
01 11 10
0000- 0- 0- 10
001 0- 0- 0- 0-
$1.: 011 0- 0- 10 0-
a:
23 010 0- 0- 10 10
s
2 110 -0 01 -0 -0
0)
£111 -0 -- -0 01
101 -0 -0 01 01
100 -0 01 01 -0
SY3RY3 Present Input (x1x2)
00 01 11 10
00010*0- 0- 0-
3;, 001 -0 01 01 -0
(>4
>5
5 011 -0 0101 -0
s
a 01010 0- 0- 0-
m
§ 11010 0- 0- 0-
A: 111 -0 -- 01 -0
101 -0 -0 01 -0
100 10 0- 0- 0-

 

 

 

 

 

 

61

3112sz

Present State (Y1Y2Y3)

(C)

001

011

010

110

111

101

100

Present Input (x1x2)

00

01

ll

10

 

10

0-

0-

10

 

10

0-

0-

10

 

01

-0

-0

 

01

-0

-0

 

01

-0

-0

 

-0

 

10

 

 

 

 

 

10

 

5Y1 = xrxzyz + x182%

RY] = x17‘2)’3 + x1X2)’2 + x1x230

SY2 = x2Y1 + x1X2
RY2 = x1x2 + xlyl

SY3 = x1x2

Ry3 = X29} + X1X2

 

62

change of y1 is faster than y2, or 000—)100—)110, if the change of y2 is faster than y1, and
the circuit finally stabilizes at the stable state (110). On the other hand, in the presence of
such a fault, the transition path 000—)100—>110 is changed as 000—>100—>100. This
implies that if the change of y2 is faster than yl and the states (110) and (100) are
distinguishable, then the fault is detectable. However, if the change of y1 is faster than y2,

then the fault is an equivalent—state redundant fault due to the delay. 0

Examples 1 and 6 show that the equivalent-state redundant fault occur in the STT-

generated ASLCs with and without SR-latch implementations.

MW

The following example demonstrates the invalid-state redundant faults that may
occur due to either the existence of invalid states or improperly assign the don’t care terms

in the flow table.

Example 7:

Consider the UDC-generated ASLC in Figure 3.3(c) for Example 2. The transition
table in Figure 3.3(c) is realized with SR-latches and its logical equations for the SYi’s and
RYi’s are shown in Figures 3.11. Assume that a stuck-at-l fault occurs at the yz-input of the
AND gate, xlxzyz of RYl- This fault causes the entry (xlxz-y1y2y3)=(10-101) to change
from (101) to (001) and the entry (10-100) to change from (100) to (000). Suppose that the
current state is (101) and the current input is (00). When the input is changed from (00) to
(10), the fault-free circuit will stabilize at the state (101) with an output (11), but the faulty
circuit will stabilize at the state (001) with an output (00). Since the faulty and fault-free
states are distinguishable, the fault is detectable. However, as shown in Figure 3.3(b), the
current state (101) is an invalid state which is not reachable from the reset state. Thus, the
fault is an invalid-state redundant fault.

On the other hand, assume that a stuck-at-l fault occurs at the xz-mput of the AND

gate, 551251”, of 8Y2. The fault causes the entry (x1x2-y1y2y3)=(01-001) to change from

SYIRYI

Present State (Y1Y2Y3)

001

011

010

110

111

101

100

SY3RY3

Present State (YIYZY 3)

Present Input (xlxz)

00

01

ll

10

 

0-

0..

O-

0-

 

O-

 

 

 

 

 

 

 

 

 

 

 

 

Present Input (x1x2)

00

01

11

10

 

001

011

010

110

111

101

100

0-

0-

O-

10

 

-0

-0

01

-0

 

-0

-0

-0

 

O-

0-

0-

 

O-

0..

0-

 

01

 

 

 

 

 

 

 

 

63

Present State(Y1Y2Y3)

5112sz

000
001
011
010
110
111
101

100

Present Input (xlxz)
00 01 11 10

 

0- 0- 0- 0-

 

10 0- 0- 0-

 

-0 -0 —0 -0

 

0101 -0 -0

 

-0 —0 -0 -0

 

-0 -0 -0 -0

 

0- 0- 0- 0-

 

0- 0- 0- 0—

 

 

 

 

 

 

SYl = x1X2Y2Y3
RY] = x17‘23’2 + x1)’2)’3

SY2 = x17(23'13'3

RYZ = x1Yr)’3

SY3 = X1§2§1§2
RY3 = x1"2)’1>’2 + x1"2>’1)’2

Figure 3.11: SR-latches implementation for Figure 3.3(c).

64

(001) to (011). Since both stable states (001) and (011) produce the outputs (00) and (01),
respectively, they are distinguishable. However, the entry is a don’t care entry as shown in
Figure 3.3(b), and is not reachable from the reset state. Thus, the fault is also an invalid-

state redundant fault. 0

Examples 2 and 7 show that the invalid-state redundant fault occurs in the STT-

generated or UDC-generated ASLCs with and without SR-latch implementations.

3.2.1.2 State Oscillations

Critical races in a fault-free circuit can always be eliminated with a pr0per state
assignment. However, they may occur as a result of faults. Two types of critical races may
occur: Intrastate races and Interstate races.

When inputs (SYi.RYi) are changed from (1,1) to (0,0), the output value of the latch
is determined by the race between Sy, and R“. Due to delays, both 835 and RYi are unlikely
changed simultaneously. If the change of 8Y1 is faster than that of R“, the output value is
0, otherwise an output 1 is obtained. Such a critical race is referred to as intrastate race at
Yi. On the other hand, if a critical race occurs between two or more states, it is called a
interstate race.

The following examples demonstrate both intrastate and interstate races.

Example 8: Intrastate Races

Consider the UDC-generated ASLC in Figure 3.3(b), but it is realized with SR-
latches. Figure 3.12 shows the logic implementations for 8y, and RYi- Assume that a stuck-
at-l fault occurs at the y3-input of the AND gate, x1x2y2y3, of 8Y1. The fault causes
Sy1=RY1=l and the entries (x1x2-y1y2y3)=(ll-010) and (ll-110) to change from (010) to
(u10), where u represents the undetermined value. In cases that SYizRyl=1 occurs in the
presence of fault, four cases can be identified: (1) Yi=0; (2) Yi=l; (3) Yizunchanged; and
(4) Yi=changed.

65

For Yi=0, i.e. (u10)=(010), the faulty circuit has the same behavior as the fault-free
one. Thus, the fault is redundant. However, when further changing input from (11) to (01),
it results in the intrastate race at Y1 and the fault detectability is determined by the relative
delays between Sn and RY].

For Yi=1, i.e. (u10)=(110), if the current state is (010) and the input is changed from
(10) to (11), the next state will stabilize at (010) in the fault-free circuit and at (110) in the
faulty circuit According to Figure 3.3(b), these two different stable states can be
distinguished by further changing the input from (11) to (01). However, when the input
changes from (11) to (01), (Sy1,RY1) is changed from (1,1) to (0,0). As a result, it causes
an intrastate race at Y1. Note that the situation can only be verified by the fault simulation,
but not by the transition table of the faulty circuit.

For Yi=unchanged, the entry (xlxz-y1y2y3)=(11-1 10) is changed from (010) to
(110). Assume that the current state is (110) and the current input is (01). When the input
changes from (01) to (11), the next state will stabilize at (010) in the fault-free circuit and
at (110) in the faulty circuit. Similar to Case 2, an intrastate race occurs.

For Yi=changed, the entry (x1x2-y1y2y3) =(l 1-010) is changed from (010) to (110).

This results in a state oscillation between (x1x2-y1y2y3)=(11-010) and (ll-110). 0

Example 9: Interstate Races

Consider the same ASLC in Example 8. Assume that a stuck-at-l fault occurs at the
yz-input of the AND gate, x1x2y2y3, of 3Y1- The fault causes the entry (x1x2-y1y2y3)=(1 1-
001) to change from (000) to (100), and results in a critical race between Y1 and Y3.
Therefore, state oscillations may occur in this faulty circuit. In addition, the invalid state

(100) may cause the fault behavior unpredictable. O

The interstate races can be avoided by choosing SR-latch whose output value is
unchanged when Syl=RYi=L This type of SR-latch is equivalent to the C-element [1] which
is commonly used in STG-modeled ASLCs.

SYIRYI

Present State (Y1Y2Y3)

001

011

010

110

111

101

100

SYBRY3

Present State(Y1Y2)’3)

001

011

010

110

111

101

100

Present Input (xlxz)

00

01

ll

10

 

O-

O-

O-

0-

 

0-

O-

O-

 

O-

10

0..

 

0-

0-

0-

 

01

01

 

01

 

 

 

 

 

 

 

 

Present Input (x1112)

00

01

11

10

 

O-

O-

O-

10

 

01

 

-0

 

0-

 

0..

 

 

 

 

 

 

 

 

 

66

S11211112

Present State()’1Y2Y3)

000

001

011

010

110

111

101

100

Present Input (x1x2)

00

01

11

10

 

0-

O-

0-

O-

 

10

O-

O-

 

-0

-0

 

01

-0

 

-0

 

 

 

 

 

 

 

 

SYl = x1X2)’2)'3

er = X52 + x1373

3Y2 = 551%

RY2 = 3313753

SY3 = X52372
RY3 = x2Y2 + x1Y1

Figure 3.12: SR-latches implementation for Figure 3.3(b).

 

67

Property 4 : Intrastate and interstate races will never occur in a faulty circuit in the presence

of stuck-at-O fault.

m: A stuck-at-O fault will not cause SYi=RYi=1, thus no intrastate race occurs at Yi.
Also, the unchanged state variables will remain unchanged in the presence of stuck-at—O

faults. Therefore, no interstate race occurs. Q. ED.

By Property 4, no critical races occur in the presence of stuck-at-O faults such that
state oscillations will not occur. Note that if a circuit is free of intrastate and interstate races,

then Properties 1,2 and 3, are also applied for ASLCs implemented with SR-latches.

3.2.2 Testability Synthesis Properties

In this section, the testability synthesis properties for ASLCs implemented with SR-
latches are described. If the output functions are synthesized with the prime and irredundant
logic, then the output logics are fully testable. Thus, we only consider the stuck—at faults at
the circuit for the next-state logics.

The logic implementation of internal state variable, Yi, is shown in Figure 3.13,
where the CLB represents the combinational logic block. First, consider the stuck-at fault

at the primary inputs Xi and the feedback line Yi.

Property 5. A stuck-at fault at the primary input xi or feedback line Yi is detectable.

Emf: [By Contradiction] Consider the behaviors of fault-free and faulty circuits, the fault
is undetectable if and only if the circuit have the same behavior in both circuits. As a result,
the value of primary input xi has no effect on the behavior of the circuit, therefore this input
is redundant and can be removed from the input lines. The same conclusion applies to the

stuck—at fault at the feedback line Yi. Q. E.D.

68

 

 

 

 

 

 

+1

 

 

 

 

 

 

  

SYi (Ran)

 

 

(b)

Figure 3.13: Block diagram of next-state logic (a) Yi-variable; and (b)
Combinational logic block (CLB).

By Property 5, only the stuck-at fault within the CLB needs to be considered. A
fault in a CLB is testable only if its faulty behavior can be propagated to the output of the
CLB. If a CLB is synthesized with prime and irredundant logic, there always exists at least
one state which can propagation fault behavior to the output of the CLB. Since each AND
gate contains at least one essential-I which is not shared by other AND gates, therefore
there always exists at least one state q where a stuck-at-O fault will be propagated to the
output of a CLB. Similarly, the effect of a stuck-at-l fault at the output of AND gate will
be seen as long as the expected output of the CLB is 0.

These conditions are necessary but not sufficient to detect the fault. For a fault to be
testable, three constraints must be satisfied: (1) Constraint 1: the fault effect must be
propagated to the output of a SR-latch, i.e., the value of Yi must be changed. Otherwise,
this fault is “unobservable” from the internal state variable and the fault effect cannot be
excited. (2) Constraint 2: the exciting state q must be reachable from the reset state. (3)
Constraint 3: the state transition must stabilize at another stable state which is

distinguishable from the fault-free circuit. Otherwise, it is a redundant fault as shown in

69

Examples 6 and 7. Constraints 2 and 3 are the same constraints for ASLCs without latches,
but constraint 1 is the condition that only applies to ASLCs with latches. Nevertheless,
Condition C, described in Section 3.1.2, can still be applied to ASLCs with latches. Further,
for SR-latches, only the stuck-at faults at the two inputs S and R and the output are

considered.

Watches

Consider the testability synthesis properties in the presence of stuck-at-O faults. By
Property 4, in the presence of stuck-at-O faults, no races occur in STT-generated ASLCs
with SR-latched and the unchanged state variables will never be affected during the state
transition due to the stuck-at—O fault. Therefore, only the changed bit, y, in XC(Si,Sk), of the

[Si,Sk] in a K-set needs to be considered.

Lemma 5: A stuck-at-O fault that occurs at yr in Xc(Si,Sk) is detectable if (1) the K-set
contains an unstable state Sj with DH(Sj,Sk)=r and spfiespnj; (2) Sj is distinguishable from

Sk in the input column 1p; and (3)T p10 exists.

Emf: Since DH(Sj,Sk)=r and Spfifipnj, Sj satisfies Condition C.) and becomes a stable
state in the presence of this fault in the input column 1p. By conditions (2) and (3),

Condition C.2 is also satisfied.Thus, this fault is detectable. Q.E.D.

For the stuck-at-l fault, the testability synthesis properties will be much more
complicated than that of the stuck-at-O fault. Since the stable state may also be affected in
the presence of stuck-at-l faults, both the unstable and stable states need to be considered.
First, consider the synthesis property for the affected unchanged bit, yr in Xu(Si,Sk) of the
[Si,Sk] in a K-set. Similar to Section 3.1.2, when a fault affects yr in Xu(Si,Sk), in order to
avoid state oscillations, the transition paths of [Si,Sk] should be directed to stabilize at the
same stable state in the faulty circuit. Therefore, Theorem 2, in Section 3.1.2, can also be
applied for ASLCs implemented with SR-latches as long as there is no critical race between

5Y1 and RYi in the presence of stuck-at-l faults.

70

Second, we investigate the testable properties when the stuck-at-l fault affects the
yr in Xc(Si,Sk) of the [Si,Sk] in a K-set. For a stuck-at-l fault, if it affects the SYr or RYp
then it will result in (SYpRYr)=(111)- For example, in Figures 3.10(b) and 3.10(c), since the
yl-bit is a changed bit of the transition pair [011,110] in the input (11) column, the term
x1x2y2 will be covered by at least one prime irnplicant of 8Y1 in the prime and irredundant
implementations. In other words, it implies Sy1=1 for those states in the TP of [011,110].
If a stuck-at-l fault occurs at yl-bit and some states in this transition path are affected,
(SYl,RY1)=(l,1) will occur in the presence of this fault. Therefore, whether this fault is
detectable or not highly depends on the excitation function of SR-latches chosen. The
requirement is that the constraint 1 must be satisfied.

As a result, if the changed bit of a transition pair is affected, the condition
(S,R)=(l,1) is unavoidable. Similar to Example 8, four cases are investigated when
(SYvRYi)=(111)- Case 1: For Yi=0, if the stuck-at-l fault affects the S“ and the next value
of Yi is 0, it is a redundant fault. This is due to the fact that when SYFRYFI occurs, the
next value of Y; is still 0 such that the behavior of both fault-free and faulty circuits is the
same. (violating Constraint 1). Case 2: For Yi=1, it is also a redundant fault, if the stuck-
at-l fault affects the RYi and the next value of Yi is 1. (violating Constraint 1 ). Case 3: For
Yi=unchanged, it will always cause the yr in Xc(Si,Sk) become unchanged. Therefore, if the
affected state is reachable from the reset state and the affected state can stabilize at a
distinguishable stable state, then this fault is detectable. Case 4: For Yi=changed, it is likely
to create unstable states, therefore state oscillations may occur as shown in Example 8.
Based on above discussions, Case 3 is obvious a good choice for the excitation function of
SR-latches.

In addition to the S=R=l in the presence of stuck-at-l faults, the testability
synthesis property for the stuck-at-l fault that affects the yr in Xc(Si,Sk) is the same as
Theorem 1. Based on Theorem 1 and the above discussion for Cases 1 and 2, two

corollaries can be derived.

71

Corollary 1: Assume that the excitation function of SR-latches is assumed Yj=0 when
Syj=RYj=l, and a stuck-at-l fault affects the yj in XC(Si,Sk). Then, this fault is undetectable

from those states in TPik, if the value of yj-bit of its corresponding stable state Sk is 0.

Corollary 2: Assume that the excitation function of SR-latches is assumed Yj=1 when
Syj=RYj=l, and a stuck-at-l fault affects the yj in Xc(Si,Sk). Then, this fault is undetectable

from those states in TPik, if the value of yj-bit of its corresponding stable state Sk is l.

Weber.

Similarly, those synthesis properties for STT- generated ASLCs with SR-latches can
be further modified for UDC—generated ASLCs with SR-latches. Based on the UDC state
assignment, only one internal state variable is changed at a time, therefore a stuck-at-O fault
can only cause the affected unstable state to become stable. It should be noted that no stable

state will be affected in the presence of stuck-at-O faults.

Lemma 6: A stuck-at-O fault is detectable if (1) Su in Pa , where Su is an unstable state in
the input column 1p, and SpfuatSpnu; (2) S“ is distinguishable from Sb in input column I ;

and (3) T puo exists.

m: A stuck-at-O fault can only result in an unstable state to become stable. By
SpfuatSpnu, Su satisfies Condition C] and becomes a stable state in the input column 1p.
Moreover, no race condition will occur in the presence of this fault. Similar to Lemma 5,

this fault is detectable. Q.E.D.

By Lemma 6, it is easy to check whether a stuck-at-O fault is detectable or not. It
should be noted that the affected unstable state in the STT-generated ASLCs with latches

may be still an unstable state in the presence of stuck-at-O faults.

Consider the stuck-at-l fault in UDC-generated ASLCs with SR-latches and a

connected path Pab in the input column 1p. If the stuck-at fault affects the yi in Xu(Sb,Snb),

72

where Sb is a stable state in fault-free circuit, the state Sb will become an unstable state but
no critical races occur. On the other hand, if a stuck-at fault affects the yi in Xu(Sj,S“J-),
where Sj is an unstable state in Pab, then critical races may occur. In general, the affected
unstable state will either become a stable state or introduce the race condition in the
presence of stuck-at-l faults. Therefore, in order to reduce the race conditions among
internal state variables in UDC-generated ASLCs with SR-latches, the better way is to
choose the SR-latches with the characteristic: When SYFRYFI» the output value of this
latch is unchanged. However, the Constraint 1 must also be satisfied in order to excite this
fault. Similarly, in the case of Syl=RYi=l, whether the fault can be excited or not depending
on the excitation function of the SR-latches chosen.

It should be mentioned that, based on UDC state assignments, a stuck-at-l fault that
affects the yi in Xu(Sx,Snx) may or may not create the condition Syq=RY1=L Moreover, if a
stuck-at-l fault affects the yj in XC(Sx,Snx), then the condition Syj=RYj=1 occurs at Yj. But
it does not mean that the other states, within the same connected path, encounter the same
condition Syj=Ryj=L Therefore, the fault may be still detectable from the other states.

In general, a fault may or may not result in race conditions in the faulty circuit.
Without race conditions, either the affected unstable state become stable or the affected
stable state become unstable. In the former case, if the affected unstable state is reachable
from the reset state and is distinguishable from its corresponding stable state in the fault-
free circuit, then this fault is detectable. In the latter case, if a fault causes the stable state
to become unstable and it finally stabilize at another distinguishable stable state, then this
fault is detectable. On the contrary, if race conditions occur, in order to avoid critical races,
it should be guaranteed that the race conditions will always stabilize at a unique and
distinguishable stable state. Thus, it is concluded that the stable state should be also
affected. Therefore, Theorems 3 and 4 are also applied for UDC-generated ASLCs with
latches as long as the stuck-at-l fault satisfies the Constraint 1. Theorem 3 is to deal with

the affected unstable state without race. When St is the stable state Sb in Theorem 4, it is

73

concerned with the affected stable state without race. On the other hand, when St is the

intermediate state in Theorem 4, it is the testable condition for the faulty circuit with races.

3.3 STG-Modeled ASLCs

The previous sections have presented the fault effects and synthesis properties of
Huffman-modeled ASLCs with and without SR-latches. Prior to the discussion of the fault
effects and synthesis properties of STG-modeled ASLCs, the similarities and differences
between these two models are described in this section.

In STGs, two or more input/output signal transitions can be enabled simultaneously.
Thus, three different types of concurrency can be identified: input concurrency, input/
output concurrency, and output concurrency. A STG-modeled circuit without input/output
concurrency can be viewed as a special Huffman-modeled circuit. More Specifically, as
discussed in Section 2.1.1, the output function of a Moore-type Huffman-modeled ASLC
is (0:3 -—> O. The STG-modeled ASLC is equivalent to the Moore-type Huffman-modeled
ASLC with a unity function, i.e. (0:1. The unity function implies S=O, i.e. the output
variables are the same as state variables. In addition, the signal transition graph is
equivalent to the flow table, in Huffman-modeled ASLCs, with concurrency, referred to as
a concurrent flow table (CFT).

For example, consider a four-phase handshaking circuit [1,19], where its STG
representation is shown in Figure 3.14(a) and the logic implementation is illustrated in
Figure 3.14(b), where the equations for both S and R terminals in each C-element are also
shown. A C-element, as shown in Figure 3.15, is a modified SR-latch which defines the
output to be unchanged when (S,R)=(l,1). The STG representation can be transformed to
a flow table shown in Figure 3.14(c), where the entries are the next state variables which
are the same as the output variables, Rom and A0,“. It is easily to see the input concurrency
in STG, as shown in Figure 3.14(a), where the input signal transitions, Rh,“ and Ain', can

be fired simultaneously. The concurrency can also be presented in the concurrent flow table.

74

- N - Circuit
Aout<--Rout 3

SRout

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ou ut
Environment
Rin Ain S Aout = 1:001 SROllt = KinxoutRin
RAout = Rin RRout = AinAout
(a) (b)
Rin Am
00 01 11 10
RoutAout
°° m1 1°
11 0° 0° “I
.. ® 11 m |®
10 - - - — 11 l 11
(C)

Figure 3.14: An STG-modeled ASLC (a) Four-phase handshaking protocol; (b)
Logic implementation; and (c) Equivalent concurrent flow table.

75
As shown in Figure 3.14(c), when (RimAin) is changed from (0,1) to (1,0) with the present
state (Rout,Aom)=(0,0), it will reach the same destination regardless of the firing sequence.
The STG also shows an input/output concurrency, where the input signal transition Am”
and the output signal transition Aom" are fired. The same concurrency can be described
from the concurrent flow table. Consider the present state is (Rout,Aou0=( 1,0) and the
current input is (Rin,Ain)=(1,0), when the Am” input is enabled, i.e. the input is changed to
(1,1), the next state is (1,1) and further changes to (0,1) when Am“+ is enabled. On the other
hand, if the output Amt“ is enabled, the next state is also (1,1) and further changes to (0,1)
when Am“ is enabled. This implies that no matter which signal is enabled earlier or both
are enabled at the same time, it will reach the same destination. This STG does not include

any output concurrency.

 

-—-—1 S Q—-- S Q
__ R $ R:S:

Figure 3.15 The transformation from SR-latch to C-element.

 

 

 

The question that naturally arises is what is the difference between the Hufi‘man-
modeled ASLCs and STG-modeled ASLCs as far as the concurrency is concerned. For the
output concurrency, since the output variables in the STG are the state variables, the output
concurrency means that two or more state variables are changed simultaneously. Thus, a
STG-modeled ASLC is equivalent to a Huffman-modeled ASLC with the STT state
assignment. On the other hand, if the output variables in the STG-modeled ASLC are
changed one at a time, then it is equivalent to the Huffman-modeled ASLC with the UDC

76

state assignment. For input concurrency, a STG-model ASLC is equivalent to a Huffman-
modeled ASLC with multiple input changes. For the input/output concurrency, this is the
special feature of STGs which resolves the fundamental mode problem in Huffman model.
Due to the input/output concurrency in a STG, asynchronous control circuits have been
successfully designed and implemented. The next question is whether or not the STG-
modeled ASLCs with input/output concurrency is testable. If not, such a greater feature will
be useless for a practical ASLC design which must be testable.

The following example demonstrates that given a STG-modeled circuit with input/

output concurrency, a fault that occurs at the concurrent signals is not testable.

Example 10:

Consider the four-phase handshaking circuit in Figure 3.14. Figures 3.16(a) and
3.16(b) shows the K-maps for the equations presented in Figure 3.14(b). Assume that a
stuck-at-l fault occurs at the input, Aom, of Gate A2. The fault causes the K-maps for
(SRomRRom) to change as the one shown in Figure 3.16(c), where the boldfaced entries
indicate the faulty bits. As a result, the behavior described in the CFT (Figure 3.14(c)) for
the fault-free circuit is changed as that in Figure 3.16(d) for the faulty circuit. Comparing
both CFTs, (RinAmRoonm)= (1110) is the only entry to test the fault. However, a critical
race occurs in the entry, where the state is changed from (10) to (01). If Rom is changed
faster than A0,“, then it will stabilize at (00). Therefore, this fault is detectable. However,
if Aout is changed faster than Rom, the circuit will stabilize at (01) which is the same as
fault-free circuit. And, this fault is not detectable. Whether or not this fault is detectable is

dependent of the relative delays between Aom and Rom.

Since the intemal state variables in STG-modeled ASLCs are also the output
variables which are observable, testing of STG-modeled ASLCs is much easier than that of

Huffman-modeled ASLCs. However, if a STG-modeled ASLCs does not satisfy the

Unique State Coding (USC) property, it is necessary to add the some internal variables

77

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

SRoutRRout Rin Ain SAoutRAout Rin Am
00 01 11 10 00 01 11 10
ROBIAOUI ‘ RoutAout
00 00 00 00 (10 00 Km 00 00
oroofl-moo 0101010000
:3—
11 00 Q 0 00 11 (f 11 10 El
1000000000: 101113))101
(a) Q set input a”
(’ )Resetinput
SRoutRRout Rin Ain Rin Ain
()0 ()1 11 10 00 Ol 11 10
RoutAout RoutAout — I #1
oo 00 01111 11> °° 1°
01 00 01 01 00 01 00 00
__
11 00 0101 00 11 @01 01®
10 00 01 01 10 10 “ -- 01 11
(c) ((1)

Figure 3.16: Example 10 (a) Rout; (b) A0,“; (c) Map for Rout in the presence of a
stuck-at-l fault at the Amt-input of Gate A2; and (d) Equivalent con-

current flow table of (c).

78

which are not the output variables and thus not observable. If so, then the fault effects
presented in the previous sections for Huffman-modeled ASLCs will also occur in STG-
modeled ASLCs. Similarly, state oscillations in a ASLC can be observed from the output
variables if it does not contain any internal variables. However, they may occur in the STG-
modeled ASLCs with internal variables. Invalid-state redundant faults may occur in
Huffman-modeled ASLCs, but they will never occur in STG-modeled ASLCs. This is
simply because the state variables are generally encoded properly when the circuit is
synthesized.

Since the input/output concurrency is allowed in STG-modeled ASLCs, applying
appropriate test sequence becomes a very difficult problem because the test input must be
applied at the same time when the output changes. Obviously, predicting when the output
will be changed is not an easy task. Such a problem will not occur in Huffman-modeled
ASLCs with the fundamental mode operation. To avoid that problem, STG-modeled
ASLCs assume to be operated in the fundamental mode during testing. Note that, under
such assumption, the above mentioned fault is not testable due to the fact that the entry
(1110) will never be reached because the entry (1010) is an unstable state.

Recently, a design methodology for testable STG-modeled ASLCs has been
presented [19] which assumes (l) a wire stuck-at fault model; (2) the circuit is operated in
fundamental mode during testing; and (3) a AND gate with inverter(s) in the two-level logic
is treated as a gate. Under these assumptions, the STG-modeled circuits can be easily
tested. In practical, however, the assumptions are impractical. A gate stuck-at fault is
commonly assumed in digital testing instead of the wire stuck-at fault model. The AND
gate and inverters should be treated as separated gates. As demonstrated in Example 10, the
operation of fundamental mode cannot detect the faults relative to the input/output

concurrency.

79

3.4 Discussion

This chapter has presented the fault effects and testability synthesis properties for
Huffman-modeled ASLCs. The fault effects include sequential redundant faults and state
oscillations. This study shows that the STT state assignment does not create cycles for
avoiding critical races, but it implicitly creates cycles for non-critical races, i.e., it provides
multiple transition paths for the circuit to stabilize at the same state for the non-critical
races. As a result, the STT-generated ASLCs inherently generate the equivalent-state
redundant faults. On the other hand, since the race-free UDC state assignment provides
only one connected path for each state transition, the possible equivalent-state redundant
faults can be reduced. In addition, a fault in a UDC- generated ASLC can be easily identified
by tracing its connected paths. Thus, the UDC-generated ASLCs are better than the STT-
generated ASLCs as far as synthesizing testable circuits is concerned. As discussed in
Section 3.1, several nrles have been concluded for synthesizing state oscillation-free
circuits. Those rules assume the race-free faulty circuits. In practice. detecting race
conditions in the faulty circuits is not an easy task.

Section 3.3 concludes that testing STG-modeled ASLCs without internal variables
is much easier than Huffman-modeled ASLCs. If STG-modeled ASLCs have some internal
variables, then the fault effects result in Huffman-modeled ASLCs will also occur. The fault
effects include the equivalent-state redundant faults and state oscillations. STGs have a
special feature of input/output concurrency, but some faults related to this concurrency are
not testable without scan design structure even though the circuits assume to operate in
fundamental mode. This has motived the development of a scan design for STG-modeled

and Huffman-modeled ASLCs for achieving full testability for all single stuck-at faults.

Chapter 4

ASLCScan - A Scan Design for Asynchronous Sequential
Logic Circuits

 

Due to the lack of controllability and observability, testing of sequential circuits
has been recognized as a very difficult task. In order to reduce the complexity of the test
generation problem, scan designs [20-24] have been proposed and successfully
implemented for CSLCs. With scan structures, all state variables of a sequential circuit are
completely controllable and observable from primary inputs and outputs. Thus, the test
generation problem is reduced to one of just testing the combinational logic. This chapter
presents a scan design, ASLCScan, for ASLCs. The basic concept behind this
development is that, with the scan structure, an ASLC is Operated in an asynchronous way
during the normal operation mode, while it is synchronized with clock signals during the
test mode.

In the next section, some design issues on the scan design, LSSD, are addressed.
Section 4.2 describes the ASLCScan method including the scan structure and its
operation. In order to demonstrate the scan design for ASLCs, two examples with

ASLCScan method are illustrated in Section 4.3.

80

81

4.1 Level-Sensitive Scan Design

The scan design, LSSD, has been introduced for structural design for testability in
many IBM machines. This section discusses the design principle and hazard/race

problems.

Wills

There are two fundamental requirements for the LSSD technique. The first
requirement is that all changes to the state of the circuit are controlled by the level of a
clock control signal, rather than by the edge of the clock. Further, the steady-state response
to a change of value on a primary input is independent of the propagation delay of gates
and interconnect elements within the circuit. The response is also independent of the order
of input-value changes in the event of simultaneous multiple changes. This is the property
of “level-sensitivity”, designed to reduce the dependency of the circuit on its ac
parameters, such as degraded rise and fall times, degraded propagation delays, or other
faults that have the potential of introducing race and hazard conditions. Therefore, the
potential effect of the failure mechanisms that cause timing faults is reduced. In LSSD
design, this property is achieved by using master and slave latches which are controlled by
two non-overlapping clocks. The second requirement of LSSD circuits is that the circuit
should posses the scan-path property which is achieved by using a special purpose stored-

state device called polarity-hold Shift Register Latch (SRL).

WW

Let D and C be the data and clock input signals, respectively. In order to avoid
races/hazards, both signals must be designed under the following two constraints: (1) D
should outlast the ending edge of C sufficiently, i.e. the value of input datum must last for
enough time when the pulse of the storing signal returns to its inactive value; and (2) the
pulse width of C is larger than the minimum time for the regeneration in the feedback loop

to take over control and maintain the new state.

82

Consider a polarity-hold latch which is designed under these two constraints. The
hazard conditions exist only when a “1” is stored. More specifically, as indicated in its
Karnaugh-map (K-map), as shown in Figure 4.1 (a), a potential hazard occurs when the
signal C is changed from 1 to 0 or from 0 to l. A glitch caused by the latter case may not
cause any serious problem because the Q-output will finally stabilize at a “1”. Thus, the

following discussion will consider the former case only. Consider the case that Q=1, D=1,

 

 

‘1 ___—A11

00 0M0 3_S
C F

”CD-1U° EA?
1—

(a) (b)

 

 

 

 

 

 

 

 

 

 

Figure 4.1: Potential hazard condition in the case of storing
a “1” (a) K-map representation; and (b) Logic
implementation.

and C is changed from 1 to 0, denoted as 1—)0. This results in signal value changes at
nodes s and Q’ as indicated in Figure 4.1(b) as l-—>0 and 0-—>l, respectively. Let R21 and Fa
denote the rising and falling time of a gate a, respectively. Thus, a hazard occurs if FA] <
R1 + RA2- In general, the combined delay through two gates is usually larger than that
through one gate.

To avoid the hazards, numerous design techniques have been presented in [52,53].
Consider the latch design in Figure 4.2(a) [52], where the inverter is connected to the gate

A1 instead of A2 in Figure 4.1(b), and the signal C is applied. As a result, the hazard will

83

not occur if F1 + FAI > RA2- Figure 4.2(b) shows the NAND gate implementation of
Figure 4.2(a).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(b)

Figure 4.2: Polarity-hold latch in [52].

Enhamiflnlntlntflszldmmss

The polarity-hold latch in Figure 4.2(b) is referred to as the simple PH. To remove
the hazard condition for reliable operation, an enhancement can be made by adding the
hazard protection term, Dq, as shown in Figure 4.3(a). The corresponding NAND gate
implementation is shown in Figure 4.3(b) which is referred to as the enhanced PH. By
using the hazard protection term, both E and i will not be active at the same time, in this

case §='r'=0, therefore the hazard condition can be avoided.

84

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

CD00 01 11 10
q
0 0 0 m 0
1 CED 0 Q=DC+Cq+Dq
(a)
DA a m
__ N1
b
C N2 “
(b)

Figure 4.3: Polarity-hold latch with hazard protection (a) K-map
representation; and (b) Enhanced PH.

W
As discussed, both simple and enhanced PHs are hazard-free. The simple PH

avoids the hazard by defining the path delays where F1 + PM > RA21 while the enhanced
PH employs an extra NAND gate, N2, to become hazard-free. Therefore, the enhanced PH
is generally more reliable than the simple PH, but requires an extra NAND gate.

As shown in Figure 4.3, a hazard protection term, Dq, is added for reliable
operation. However, hazards and races may occur as a result of faults. Consider the latch
in Figure 4.3(b). The s/l faults at nodes “a” and “”,b referred to as faults Fa and Fb. cause
hazards. For example, the logic function of the latch becomes Q=DC+Cq in the presence

of fault Fb. This implies that the hazard protection term, Dq, disappears. On the other

85

hand, when the clock C is turned on and then off, the presence of Pb fault causes the

’9

contents of Q and Q to be shown as below, where nodes “m” and “n are indicated in

Figure 4.3(b).

p—i
O
O
|—I
p—A

l 0 1 1 ? ? (- Critical Race

When C=l, we obtain (m,n)=(0,0) and (Q,C)=(1,l). Then, when clock C turns off, i.e., C
changes from 1 to 0, (m,n) is changed from (0,0) to (1,1) which causes a race. If the
change of “m” is faster than that of “n”, then (Q,U)=(0,1). Otherwise, (Q,C)=(1,0). Thus,
the race is critical. Similarly, the existence of the fault Fa causes the logic function to
become Q=Dq+Cq+C, where a static hazard exists. As a result, a critical race occurs as D
is 0 and the clock C is turned off. This concludes that the latch in Figure 4.3(b) may not
operate properly due to the race caused by the Fa or Fb fault.

As a result, the enhanced PH is generally more reliable than the simple PH in the
fault-free circuit. But, enhanced PH becomes more unreliable when the Fb fault occurs in

the faulty circuit.

4.2 ASLCScan Method for ASLCs

This section describes a scan design, ASLCScan method, for ASLCs. The fault
model considered here is the single stuck-at fault at all the gate inputs and outputs. The
ASLC designed with ASLCScan method is operated in two modes: test mode and normal
mode. During the test mode, the scan structure is tested in a synchronous way, i.e., two
non-overlapping scan clock signals are used to shift the data out for testing. In that case,
the ASLC under test is operated in the fundamental mode. The clock rate of the scan
clocks and system clocks are determined by the worst case timing in the ASLC under test.

On the other hand, during the normal operation mode, there exists no clock signal and the

86

scan paths are disconnected. The scan structure and the ASLC are operated in an
asynchronous way.

In this section, we first describe the scan structure in the ASLCScan method using
SR-latches, and then discuss the generation of test pattern for achieving full testability for

all single stuck-at faults. Finally, the operation of the ASLCScan method is presented.

4.2.1 Basic Components

Consider the truth table of a regular SR-latch in Figure 3.8(a), where the outputs
(QQ) are undetermined when (S,R)=(l,1). Figures 3.8(b) and 3.8(c) show the NOR!
NAND gate implementations, respectively, where the outputs for (S,R)=(1,l) are
assigned. Figure 4.4(a) shows the K-map of a clocked SR—latch, or polarity-hold SR-latch,
where the entries of (M,S,R)=(-,l,l) denotes “-” for the undetermined values. In our
implementation, the undetermined values are assigned as shown in the K-map in Figure
4.4(b) and its next state equation is Y=My+Sy+Ry+MSR The realized circuit is referred
to as modified SR-latch (or MSR-latch) shown in Figure 4.4(c). Since the logic function of
the MSR-latch is prime and irredundant, the circuit is testable for all single stuck-at faults.
The important characteristic of this MSR-latch is that it is free of races and hazards in the
presence/absence of fault(s).

Consider the cross—coupled NAND latch in Figure 4.5(a), where (Q33) will never
be (0,0). This implies that when the inputs, S and R, are connected to the outputs, Q and C,
of the cross-coupled NAND latch, the entries of (-00) in Figure 4.4(b) should be don’t
cares, as indicated in Figure 4.5(b). Thus, the logic function becomes Y=My+Sy+MR and
the corresponding NAND implementation is shown in Figures 4.5(c). For simplicity, the

circuit is referred to as simplified MSR-latch, or SMSR-latch

87

 

 

 

 

 

 

 

 

 

 

 

 

MSR
000 001 011 010 110 111 101 100
C1
0 o o - 0 1 - o o
1 1 1 - 1 1 - o 1
(a)
MSR

000 001 011 010 110 111 101 100
0 0 0 0

 

Y=My+Sy+Ry+MSR

(b)

 

 

 

 

 

 

 

0|

8 30— (W
_>—

 

 

 

(C)

Figure 4.4: Clocked SR-latch (a) Truth table; (b) Truth table for
modified SR-latch; and (c) NAND gate realization.

88

 

 

 

a
MSR ()
y 000 001 011 010 110 111 101 100 Y
0 - 0
1

 

Y=My+Sy~1~MR

 

 

Ree-3::— °
}—

 

 

 

 

(C)

Figure 4.5: (a) Cross-coupled NAND latch; (b) Truth table with (MSR)=(-00)
specified as don’t cares; and (c) The corresponding NAND gate
implementation.

4.2.2 Scan Path

Figure 4.6(a) illustrates two concatenated NAND SMSR-latches. Since the value

of the node at “x” is the complement of that at y , the inverters can be absorbed by the

implementation shown in Figure 4.6(b). Note that races may occur in the circuit of Figure

89

4.6(b). As discussed in Section 2.2.3, the BF GO test, consisting of flush test and shift test,

 

 

 

 

 

Ll-latch L2-latch
. :>—
A ___—4.... Q2

 

 

 

 

 

 

 

 

 

 

Ll'latCh LZ‘latCh
S __1‘
43—5-
‘ 8
R 3‘ 7
A O 4 6 ‘

 

 

 

 

 

(b)

Figure 4.6: (a) Concatenated NAND SMSR-latches; and (b) Simplified
implementation of (a).

can be applied for fault detection. As the fault simulation results listed in Table 4.1 show,
the BFGO test detects most of faults in that circuit. In Table 4.1, FF means fault-free, a/0
(all) means a s/0 (s/ 1) fault occurs at the node a, and qi and qi, i=1 or 2, represent the
previous states of Qi and Q in the i-th latch, respectively. However, the BFGO test cannot
detect the stuck-at-l faults at the clock signals. Therefore, a clock test is developed and its
fault simulation results are also shown in Table 4.1, where “**” means the signal is

ignored as the fault has been detected. Fault simulation results show that the circuit in

90

Figure 4.6(b) achieves full testability for all single stuck-at faults. However, it should be
mentioned that the full testability is achieved based on the assumption that both nodes 29
and 30 are observable. Otherwise, the stuck-at-l faults at nodes 3 and 23 are not testable,
where node 29 has the same value for both fault-free and faulty circuits, as the flush test
shown in Table 4.1.

More specifically, in the presence of a stuck-at-l fault at node 3, a critical race
occurs during clock turn off as shown below, where Q1 and Clare the outputs of Ll-latch

and N5 and N6 represent the nodes 5 and 6, respectively.

S R A N5 N6 Q1 61

l 0 0 l l q] q]

l 0 1 0 0 l 1

1 0 0 1 1 ? ? (— Critical races

Therefore, it is necessary to have both nodes 29 and 30 be observable.

Figure 4.7(a) illustrates the scan structure in ASLCScan method, where only the
first stage needs one inverter, and the inverters in the following stages are absorbed. In
addition, two scan-out terminal +14 and L; are used. Thus, the scan path achieves a full
testability for all single stuck-at faults at the cost of requiring an extra scan-out terminal,
{4. In practice, if the pin-overhead, extra pins for test purposes, is prohibited, an
alternative scan structure, as show in Figure 4.7(b), is suggested, where the latch in Figure
4.2(b) is employed. As mentioned in Section 4.1, there exists a design trade-off between

their implementations.

4.2.3 Polarity-Hold Shift Register Latch

Figure 4.8 show the polarity-hold shift register latch (SRL) employed in
ASLCScan method. The SRL is comprised of an Ll-latch, an 1,2-latch, and two OR gates.
It differs from the SRL in Figure 2.11(b) for LSSD in its Ll-latch. For simplicity of this

91

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Table 4.1 Fault Simulation Results for Scan Path
Flush Test
(S,R,A,B)
(1,0,1,1) (0,1,1,1) Detected Faults
Q2 62 02 62
1 0 0 1 FF,0/1,2/1,4/1,7/l,8/1,20/1 ,22/1,24/l ,27/1 ,28/1
1 1 0 1 3/1,6/0,7/0,10/1,23/1,26/0,27/0,30/1
ql q] 0 l l/0,2/0,5/1,21/0,22l0,25/l
0 1 0 l 9/0,29/0
1 0 1 0 3/0,4/0,6/1,10/0,23/0,24/0,26/1,30/0
1 0 1 1 l/l,5/0,8/0,9/1,21/l,25/0,28/0,29/1
(12 62 (12 :12 0,0220“)
Shift Test
(S,R,A,B)
(0,1,1,0) (0,1,0,1) (1,0,l,0) (l,0,0,1) Detected Faults
Q2 752 02 Q2 Qz Q2 Qz Q2
0 1 0 l 0 1 1 0 FF,0/1,2/l,4/1,20/1,22/1,24/1
1 0 1 0 1 0 1 1/0,2/0,5/l,8/1,21/0,22/0,25/ 1,28/1
0 1 1 0 7/1
1 0 1 0 27/1
Clock Test
(SRAB) FF 0/1 2/1 4/1 (SRAB) FF 20/1 22/1 24/1
1010 10 10 10 10 1001 10 10 10 10
1001 10 10 10 10 0110 10 01 10 01
0101 10 01 10 01 0110 10 01 10 01
0110 10 ** 10 *"‘ - 0101 01 ** 01 **
0101 01 ** 01 ** 1010 01 ** 10 *"‘
1001 01 ** 10 ** 1010 01 ** 10 **

 

 

 

 

92'

Sean out 1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Scan in

 

 

 

 

?

 

 

 

(a)

Figure 4.7: (a) ASLCScan scan path; and (b) Alternative scan path.

Scan out

 

 

 

 

 

 

 

 

 

 

 

'1’ 43%?

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1%? Y“
4

Figure 4.7: (cont’d)

94

discussion, the two pairs of NAND gates in the first stage of the Ll-latch are referred to as
the upper pair and the lower pair. The path, referred to as the normal path, consisting of
the OR gates, the upper pair of NAND gates, the cross—coupled NAND latch, and the 112-
latch, is used for normal operation, while the scan path is comprised of the lower pair of
NAND gates, the cross-coupled NAND latch, and the Iq-latch. It has been shown that the
scan path is fully testable for all single stuck-at faults. The faults remained undetected so
far are the faults in the OR gates and the upper pairs of the NAND gates. Since the MSR-
latch is free of hazards and races in the presence/absence of fault(s). it can be tested by the
shift test. Also, the flush test and the clock test can detect the remaining faults. However,
since the scan design is generally applied for a large circuit, applying the flush test to the
normal path is equivalent to the test of a large asynchronous sequential circuit that
includes the combinational part and the scan paths for all state variables. The complexity

would be considerably high. In order to reduce the complexity, two additional tests are

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

introduced.
xSi S Ll-Latch ‘ +L
j > 3 ‘ 1
Xm ll %% .
__‘D 1i 0‘3 m} ' 1,2-Latch
M
H IS _3.._ l: :12

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

_Do—
ilk—“3° ___».30—1 '—

 

 

Figure 4.8: Modified polarity-hold SRL.

95

In Figure 4.8, the two OR gates are added for generating (S,R)=(l,1) to simplify
the test process. If the ASLC under test is synthesized such that (S,R)=( 1,1) can be
obtained, then the two OR gates can be eliminated. In this discussion, we assume that the
circuit may not generate such a pattern.

Table 4.2 shows the fault simulation results of the MSR-latch shown in Figure 4.9
with the assigned node numbers. Two tests are introduced: OI-test and IO-test. The 01-test
is to shift the pattern (01) into the Ll-latch to initialize the contents of Q1 and O], i.e.,
(Q1,Ol)=(01) and to check the change in these contents for fault detection. More
specifically, consider the presence of the 1/0 fault. The 01-test first initializes
(Q1,Ol)=(01) in the Ll-latch. With (S,R)=(1,0), (Qlfll) is unchanged if the fault presents,
otherwise, (Q1351) is changed from (01) to (10). Thus, after shifting the contents, the fault
is detected. On the other hand, for Types 2 and 3 faults, with (S,R)=(0,0) or (1,1), (QIQI)
is changed from (01) to (10) if the fault is present, otherwise, (Q1151) is unchanged.
Similarly, the 10-test initializes (Q1,Ol)=(1,0).

Table 4.2 shows that all single stuck-at faults in the MSR-latch are testable by both
the 01-test and the 10-test, where the faults in the cross-coupled NAND gates have been
tested during the scan test. However, the full fault coverage is achieved based on the
assumptions that (1) both 8- and R-inputs can be generated; and (2) the SI] fault at the
clock M has been tested.

Let X31 and XRi be the outputs of the combinational network for the state variable
Yi. Since both L1 and L2 latches are implemented by the MSR-latches and SMSR-latches,
respectively, the combinational network N should be synthesized with SR-latches. In
general, a irredundant combinational network with SR-implementation can always
generate the patterns (XRiXSi)=(00), (01), and (10), but not (11). In order to test Types 3
and 5 faults, two OR gates and an external control signal H are needed as shown in Figure
4.9. The signal XSi and H are ORed to produce the signal S, while R is the output of
ORing XRi and H. Thus, the pattern (11) can be generated by setting H to l regardless of

 

 

 

 

 

 

 

 

 

96

 

61

 

13

Figure 4.9: Node assignment for the MSR-latch.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Table 4.2 Fault Simulation Results for Modified SR-Latch
01-test
Type SRM FF Faulty Detected Faults
l 100 101 10 01 1/0,2/1,3/0,6/1,7/0,8/0,9/0,12/1
2 000 001 01 10 1/1,9/1
3 1 10 111 01 10 2/0,6/0,7/1
HXSiXRiM FF Faulty Detected Faults
OR- 0100 0101 10 01 h1/1,h3/l
gate 1100 l 101 01 10 h1/0,h3/0
10—test
Type SRM FF Faulty Detected Faults
4 010 011 01 10 4/1,5/0,10/0,1l/0,13/1
5 110 111 10 01 4/0,5/l
6 000 001 10 01 11/1
HXSiXRiM FF Faulty DCIBCth Faults
OR- 0010 0011 01 10 h2/1
gate 1010 1011 10 01 h2/0

 

 

 

 

 

 

97

the values of the signals X31 and XRi- As shown in Table 4.2, the OR gates are also
testable.

Consider the s/l fault at the clock M, i.e., s/l faults at nodes 3, 8, and 10. In this
implementation, H=1 and M=0 are set during the test of the scan path so that the
combinational network is isolated from the scan path. Since, with H=1 and M=0, the
presence of these faults is equivalent to the corresponding input to the NAND gate
disappearing, such a fault behavior will not effect the scan test, nor the test of the MSR-
latch. Note that, for a given redundant combinational circuit, there always exists a test
pattern for each fault. Consider the s/l faults at nodes 3 and 10. Suppose that a test pattern
TP causes the combinational network N to produce (XSi’XRj)=(O,l) in Yi. We first set H=1
and M=0 to initialize (Q1,Ol)=(l,0) in the Ll-latch for Yi, and apply the pattern TP, held
in L2-latches, to the combinational network N. Secondly, H is reset to 0, where M20, we
expect to obtain (XSi,XRi)=(0,1). This results in changing the contents of (QIQI) from the
initialized values (1,0) to (0,1) if such faults are present, otherwise, no change is made in
these contents. Thus, fault behavior can be distinguished. Finally, H is set to 1 to protect
the data held in Ll-latch so that the data can be reliably shifted out for fault detection.
Similarly, the s/l fault at node 8 is detected in the same manner, where a test pattern that
produces (XSi,XRi)=(1,0) at Yi is applied and the Ll-latch is initialized as (Q1,Ol)=(0,l).

Let (Qjfljh, j=1,2, and i=1,2,..,n, denote the data held in Lj-latch for Yi. Since the
shift signals A and B are used to synchronize the shift operation, (Q1,Ol)i is either the
same as (Q2,Oz)i or (Q2,Oz)i+1, or both, but cannot differ from both (Qzflzli and
(Q2.62)i+1 at the same time. If the test patterns in Table 4.2 require that (Q1,Ol)i should be
different from both (Q2,Oz)i and (Q2.62)i+1 at the same time, such a problem can be
resolved by either rearranging the scan path so that the SRL for Yi will not follow that for
Yi+1, i.e., SRLi+2—->SRLi—>SRLi+1—)SRLi,1, where SRLi denotes the SRL for Yi, or

adding an dummy SRL between SRLi and SRLM in the scan path, if necessary.

98

 

 

 

 

 

 

 

 

 

 

 

 

 

  
  

 

 

 

 

 

  

 

 

 

 

 

  
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Z
y >
x81 Ll-Latch
xx:
Yi\
“P
‘ \
\
3
3.:
X82 :3 t
33 g
t 3 .
33 I
xv as =
P 5: E
G I 2
9 I
I I"
u
3
3 ' Y
\ I
3.‘ F
. j \ 0 HE D
0 .
o 4: g 0 a5 0 a: o
o 3 : o o E o
5.iZIZIZZZZZZZIZZZZIZZIZZZ'.‘ LZZZZZZZIZZZZ‘.“"'3 ‘:
XS, {1 3 E E
: 31: :
\ :‘l I
Q ' I
\ ‘ ' I
9 \ 9 I I
Rn \ ‘ l u
:3! I
‘ 3 i :Y
ID ' ‘ : = n
l: \ '
II \ '
:I \ I
\I . /
H I:
M u ‘ ...
A shift 5E :: “ s» scan m“
Scan in ‘ ‘ “-- I\_ :1 ..... \\\ Scan out 2
B shift l‘

Figure 4.10: Double-latch ASLCScan design.

The double-latch ASLCScan design is shown in Figure 4.10 which generates no

critical races during normal operation and test modes.

4.2.4 Operation Modes

The design with ASLCScan method consists of two Operation modes: test mode

and normal operation mode. In the test mode, the operation is synchronized in the way

99

similar to the conventional LSSD [20,35] which can be divided into the following steps.

Step I : Apply flush test, shift test, and clock test to verify the scan path.

Step 2: Apply Ol-test and 10—test for the MSR-latch.

Step 3: Scan in the test vector for internal state variables via scan input pin by
applying pulses alternately to two non-overlapping clock A and B.

Step 4: Set the corresponding test pattern on primary inputs.

Step 5: Wait for the worst case delay for the combinational network to become
stable and check the values of primary outputs.

Step 6: Apply one clock pulse to M to latch the new internal state variable into the
corresponding Ll-latch.

Step 7: Scan out the internal state variable by applying non-overlapping clock
signals A and B.

In the normal mode operation, the ASLC is operated in an asynchronous way by

setting the clock signals A=0 and B=M=1.

4.3 Examples

In order to demonstrate the circuit design with ASLCScan method, two examples
are presented in this section. The first example is a STG-modeled ASLC, while the second
example is a Huffman-modeled ASLC.

WW

Consider a STG-modeled ASLC, converta.g, in sis benchmarks, where its
functional behavior is described by a signal transition graph shown in Figure 4.11(a).
Using the automated synthesis tool, astg, in sis developed by University of California at
Berkeley, the synthesized ASLC is shown in Figure 4.11(b), where the C-element is
similar to the MSR-latch. For simplicity, the combinational part in Figure 4.11(b) is
rearranged as shown in Figure 4.11(c). With the implementation of ASLCScan method,

each C-element is replaced by a SRL. Thus, three SRLs are needed in this implementation.

100

The detailed connection is similar to that in Figure 4.10. 6
WWW

Consider a Huffman-modeled ASLC, P-SLF, whose functional behavior is
described in Figure 4.12(a) [25], where A and B are its inputs and D and E are its outputs.
(The upper-case and lower-case letters denote the next state and the present state,
respectively.) The output lines change state only on the falling edge of B. Using the
automated synthesis system, MSUASLC, the flow tables and next-state and output
equations are generated as shown in Figures 4.12(b) and 4.12(c). With the two-level logic
implementation, the combinational part and the SR-latches are also shown in Figure
4.12(c). With the implementation of ASLCScan method, each SR-latch is replaced by a

SRL. Thus, this implementation requires three SRLs.

4.4 Discussion

Test generation is much more difficult for ASLCs than for CSLCs due to races,
hazards, and state oscillations. This chapter presents a scan design, ASLCScan method,
using SR-latches for ASLCs. Results show that the scan structure including the normal
path and scan path are fully testable for all single stuck-at faults without causing any
critical races. The ASLCScan method provides the following salient features: (1) the test
generation problem is reduced to one of just testing the combinational logic; (2) the faults
that are very difficult to test due to critical races, as discussed in Chapter 3, can be easily
identified by checking the scanned data; (3) the use of SR-latches in the scan structure is
perfectly implemented to the synthesized STG-modeled ASLCs and Huffman-modeled
ASLCs; and (4) the [q-latch is used to shift out the scanned data during the test mode and

it may also be used as a delay element to eliminate possible essential hazards.

101

 

 

 

i0): SR0 = KiIEi-X + X1_1-{ix 8x = AiEoRo
RAo = Fox RRo = AoX “‘on Rx = AiRiRo

a, n
r x (b)
A; An!
ombinational
(a) Network

      

 

 

 

Figure 4.11 Example 1 (a) STG representation; (b) Logic implementation; and (c)
Rearrange the combinational part and C-elements.

102

 

A DD==eA

 

 

Y Y Y Present Input (BA)
1 2 3\ 00 01 11 1_0_

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

«Flo om @ .0
Present Input (BA) "
00 01 11 10 001 011i. 000 00
loo 2 @w 1 .g -
@‘HIMOE’ 0:0- 01 5
>5
V I I a
32 3®100ta guloooououmg
a —‘ c: '— " '
§3@@4 4 01:; 2110@111115
t: r —— :1 8 —-
$4 1 5 ®@0l:§ 5111011110@-11
5 @®® 6 11 101 ~-
6 3 5 ® 11 100 --
(b)
Combinational
;' :DNBIWOIK D SYI = EAYZ-iB
2 —
Y2 E RY1=BY3
9:. Q Y1 SY2=§Y3
33 '. RY2=§KY1Y3
3, '- Q Y2 SY3 = BKYI + BA§2
g1 RY3=BAY2+BK§1
3 .- D=Y1Y2
l ’
Y3 B=Y2
3.. Q
i.- .
3, :-
(C)

 

Figure 4.12 Example 2 (a) Behavior description; and (b) Flow table and excitation
table; and (c) Logic implementation.

Chapter 5

Conclusions

 

Test generation is much more difficult for ASLCs than for CSLCs because of
races, hazards, and state oscillations. Often a designer does not know whether or not all
transitions in a circuit are free of races and hazards. The situation is even more uncertain if
a fault is present. Even though fault-free circuits can be designed to be free of races,
hazards, and state oscillations, they may occur as a result of faults. And even though the
fault-free circuit can be designed to change one state variable at a time during a state
transition to avoid races, the condition cannot be guaranteed in the presence of faults.
Based on the single stuck-at fault model, two major tasks were expected to be achieved in
this study: (1) to investigate the fault effects and synthesis properties of ASLCs; and (2) to
develop a scan design for ASLCs.

This chapter summarizes this research work and outlines the major contributions.
Finally, several interesting problems based on this research are identified for future

research.

5.1 Summary

Fault effects such as redundant faults and state oscillations for both Huffman—
modeled and STG-modeled ASLCs have been presented in Chapter 3. Redundancy is

sometimes desirable for hazard protections in ASLCs. However, it may also be introduced

103

104

unintentionally due in part to the implementation of an improper synthesis procedure, such
as improperly encoding state variables or assigning the don’t care terms. In Huffman-
modeled ASLCs, this study has shown that the STT state assignment does not create
cycles for avoiding critical races, but it implicitly provides multiple transition paths for the
circuit to stabilize at the same state. As a result, the STT-generated ASLCs inherently
generate the equivalent-state redundant faults. On the other hand, since the race-free UDC
state assignment provides only one connected path for each state transition, the possible
equivalent-state redundant faults can be reduced.

Due to the use of clock signals, state oscillations do not occur in CSLCs. However,
they may occur in ASLCs due to hazards and critical races. The state oscillations are
generally avoided by eliminating critical races. However, they may occur as a result of
faults. In Chapter 3, some rules and properties for synthesizing state oscillation-free
Huffman-modeled ASLCs have been presented. Since any fault-free UDC-generated
ASLC is race-free, the race conditions that occur in the presence of faults can be easily
identified by tracing the corresponding connected paths in the transition table. Thus, this
study concludes that UDC-generated ASLCs are better than STT-generated ASLCs as far
as testable ASLCs are concerned. Based on the observed fault effects, numerous synthesis
properties have also been presented in Chapter 3 for Huffman-modeled ASLCs with or
without SR-latches. These properties can be implemented to reduce the complexity of the
test generation process.

A STG-modeled ASLC without input/output concurrency can be viewed as a
special Huffman-modeled ASLC. A STG-modeled ASLC with output concurrency is
equivalent to a Huffman-modeled ASLC with the STT state assignment; a STG-modeled
ASLC with output variables which are changed one at a time is equivalent to the Huffman-
modeled ASLC with the UDC state assignment; and a STG-modeled ASLC with input
concurrency is equivalent to a Huffman-modeled ASLC with multiple input changes.

Since the state variables in a STG-modeled circuit are also its output variables which are

105

generally observable, the testing of STG-modeled ASLCs without having internal
variables is much easier than Huffman-modeled ASLCs. However, if a STG-modeled
ASLC has some internal variables, then its fault effects are similar to those in Huffman-
modeled circuits.

The input/output concurrency is a special feature in STG which resolves the
fundamental mode problem in Huffman model. Due to such salient feature, asynchronous
control circuits have been successfully designed and implemented using STGs. However,
with the input/output concurrency, a test input that must be applied at the same time when
the output changes is obvious not an easy task. The results show that the faults due to the
input/output concurrency cannot be tested without scan structure.

Due to the lack of controllability and observability of state variables, testing of
sequential circuits has been recognized as a very difficult task. Chapter 4 presents the
development of the ASLCScan method, a scan design for ASLCs. The scan structure is
free of races and hazards in both normal operation and test modes, and achieves full
testability for all single stuck-at faults. Mth the ASLCScan design, the test generation
problem of ASLCs is reduced to one of just testing the combinational logic and the
introduced races in the combinational circuit of ASLC can be identified easily. In addition,
the invalid states and entries in an assigned flow table are generally unreachable if the
circuit is fault-free. The fault behavior is unpredictable when these invalid states are
reached due to the fault. Such a problem can be easily resolved by using the ASLCScan
design.

Since SR-latches or C-elements are commonly used in STG-modeled ASLCs and
Huffman-modeled ASLCs, they also can be used as part of the Ll-latch to reduce the
hardware overhead. On the other hand, the propagation delay through the [Q'latCh can be
treated as a delay element during normal operation. The delay value for the IQ-latch may

be used to avoid the occurrence of hazards, especially for essential hazards.

106

5.2 Contributions

The major contributions and impacts of this study can be summarized as follows:

(I) explore fault effects in ASLCs;

(2) identify the similarities and differences between Huffman-modeled and

STG-modeled ASLCs;

(3) derive testability synthesis rules and properties; and

(4) develop a first-ever scan design for ASLCs.

This research has explored the fault effects in both Huffman-modeled ASLCs and
STG-modeled ASLCs. Based on the single stuck-at fault model, redundant faults and state
oscillations have been identified in ASLCs. The ways of identifying and eliminating
redundant faults have been presented in Chapter 3, while a set of synthesis rules that
generate state oscillation-free ASLCs is also derived. Thus, the test generation process can
be simplified considerably and the fault coverage can be increased significantly. The
developed scan design, ASLCScan method, further reduces the complexity of test
problem. As the examples presented in Chapter 4 have shown, testable design of ASLCs
can be achieved based on the developed scan design. In addition, this study has concluded
that, for Huffman-modeled ASLCs, the UDC state assignment is better than the STT state
assignment as far as testing is concerned. Also, the similarities between the Huffman—
modeled ASLCs and STG-modeled ASLCs are identified. Thus, the design, synthesis, and

test methodology developed for one model may be implemented for another model.

5.3 Future Research

This research has investigated the fault effects for STG-modeled ASLCs and
Huffman-modeled ASLCs. The fault effects are explored based on the single stuck-at fault
model. The fault model has identified the fault effects such as redundant faults and state

oscillations. Delay faults have been a research topic in CSLCs recently. It would be worth

107

investigating the fault effects for ASLCs with delay faults.

The fault effects and synthesis properties studied in this research are based on the
two-level logic implementation. Due to delay hazards, decomposing two-level logic to
multi-level logic is not straightforward. It is believed that the fault effects and synthesis
properties may have a significant difference when multi-level logic implementation is
concerned. This would be a very interesting problem for future investigation.

To achieve a fully testable ASLC design is not an easy task without using scan
structures. This thesis presents a scan design, ASLCScan method, for ASLCs to reduce the
complexity of the testing problem. Similar to LSSD in CSLCs, the hardware overhead and
speed degradation have always been the critical issues. In ASLCScan method, the SR-
latches or C-elements in ASLCs have been used as part of the SRLs in the scan structure
to reduce hardware overhead and performance degradation. Further, with a proper design
procedure, the L2-latches may be used as delay elements for avoiding hazards. Thus, it is
desirable to develop a design procedure which fully exploits the lq-latches as the delay
elements to simplify the synthesized ASLCs. In addition, in CSLCs, partial scan becomes
an effective way to enhance testability while still keeping lower hardware overhead and
performance degradation. Based on the fault effects, not all the state variables have to be
observed. Only those state variables which may cause critical races condition during
testing, need to be observed. Thus, it is necessary to develop a fault simulation tool that

can identify the necessarily observed state variables.

LIST OF REFERENCES

[1]

[2]

[3]
[4]

[5]

[6]

l7]

[8]

[9]

[10]

[11]

LIST OF REFERENCES

T. H.-Y. Meng, R. W. Broderson, and D. G. Messerchmitt, “Automatic Synthesis of
Asynchronous Circuits from High-Level Specifications,” IEEE Trans. on Computer-
aided Design, vol. 8, pp. 1185-1205, November 1989.

D. A. Huffman, “The Synthesis of Sequential Switching Circuits,” J. Franklin Insti-
tute, vol. 257, pp. 161-190, March 1954.

S. H. Unger., Asynchronous Sequential Switching Circuits, Wiley Interscience, 1969.

R. E. Miller., Switching Theory, volume II: Sequential Circuits and Machines, New
York, Wiley, 1965.

T. A. Chu, “Synthesis of Self-timed Control Circuits from Graphs: An Example,”
Proc. IEEE ICCD. pp. 565—571, October 1986.

T. A. Chu, Synthesis of Self-timed VLSI Circuits from Graph-Theoretic Specifica-
tions, Ph.D. dissertation, MIT, June 1987.

T. A. Chu, “On the Models for Designing VLSI Asynchronous Digital Systems,”
INTEGRATION, the VLSI journal 4, North-Holland, pp. 99-113, 1986.

G. K. Maki and D. H Sawin, “Real-Time Fault Detection and Fault-Tolerant Imple-
mentations for Sequential Circuits,” in Rational Fault Analysis, ed. by R. Saeks and
SR. Liberty, pp.32-51. Marcel Dekker, 1977.

A. D. Friedman, Fundamentals of Logic Design and Switching Theory, Computer Sci-
ence Press, Inc., Rockville, MD, 1986.

H.-K. T. Ma, S. Devadas, A. R. Newton, and A. Sangiovanni-Wncentelli, “Test Gen-
eration for Sequential Circuits,” IEEE Trans. on Computer-aided Design, vol. 7, pp.
1081-1093, October 1988.

S. Devadas, H.-K.T. Ma, A. R. Newton, and A. Sangiovanni-Vrncentelli, “A Synthe-
sis and Optimization Procedure for Fully and Easily Testable Sequential Machines,”
IEEE Trans. on Computer-aided Design, vol. 8, pp. 1100-1107, October 1989.

108

[12]

[13]

[14]

[15]

[16]

[17]

[13]

[19]

[20]

[21]

[22]

[23]

[24]

109

S. Devadas, H.-K. T. Ma, and AR. Newton, “Redundancies and Don’t Cares in
Sequential Logic Synthesis,” IEEE International Test Conference, pp. 491-500, 1989.

S. Devadas, H.-K. T. Ma, A. R. Newton, and A. Sangiovanni-Vrncelli, “Irredundant
Sequential Machines via Optimal Logic Synthesis,” IEEE Trans. on Computer-aided
Design, vol. 9, pp. 8-17, January 1990.

S. Devadas and K. Keutzer, “A Unified Approach to the Synthesis of Fully Testable
Sequential Machines,” IEEE Trans. on Computer-aided Design, vol. 10, pp. 39-50,
January 1991.

E. B. Eichelberger, “Hazard Detection in Combinational and Sequential Switching
Circuits,” IBM Journal of Research and Development, pp. 90—99, March 1965.

G. R. Putzolu and J. P. Roth, “A Heuristic Algorithm for the Testing of Asynchronous
Circuits,” IEEE Trans. on Computers, vol. C-20, pp. 639-647, June 1971.

M. A. Breuer, “The Effects of Races, Delays, and Delay Faults on Test Generation,”
IEEE Trans. on Computers, vol. C-23, pp. 1078-1092, October 1974.

K. Keutzer, L. Lavagno, and A. Sangiovanni-Vmcentelli, “Synthesis for Testability
Techniques for Asynchronous Circuit,” IEEE ICCAD Digest of Technical Paper, pp.
326-329, 1991.

P. A. Beerel and T. H.-Y. Meng, “Testability of Asynchronous Timed Control Cir-
cuits,” 28th ACM/IEEE Design Automation Conference, pp. 446-451, 1991.

E. B. Eichelberger and T. W. Williams, “A Logic Design Structure for LSI Testabil-
ity,” 14th ACM/IEEE Design Automation Conference, pp.462-468, 1977.

T. W. Williams and K. P. Parker, “Design for Testability - A Survey,” IEEE Trans. on
Computers, vol. C-31, pp. 2-15, January 1982.

T. W. Williams and J. B. Angel], “Enhancing Testability of Large Scale Integrated
Circuits with Test Points and Additional Logic,” IEEE Trans. on Computers, vol. C-
22. Pp. 46-60, January 1983.

S. DasGupta, P. Goel, R. G. Walther, and T. W. Williams, “A Variation of LSSD and
its Implications on Design and Test Pattern Generation in VLSI,” IEEE International
Test Conference, pp. 63-66, 1982.

K. K. Saluja, “An Enhancement of LSSD to Reduce Test Pattern Generation Effect
and Increase Fault Coverage,” 19th ACM/IEEE Design Automation Conference, pp.
489-494, 1982.

110

[25] S.-F. Wu and P. D. Fisher, “Automating the Design of Asynchronous Sequential Logic

126]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

Circuits,” IEEE Journal of Solid-State Circuits, pp. 364-370, March 1991.

P. D. Fisher and S.-F. Wu, “Race-Free State Assignments for Synthesizing Large-
Scale Asynchronous Sequential Logic Circuits,” accepted to appear in IEEE Trans.
on Computers.

B. Hazeltine, “Encoding of Asynchronous Sequential Circuits,” IEEE Trans. on Com-
puters, vol. EC-14, pp. 727-729, October 1965.

O. G. Langdon, Jr, “Delay-Free Asynchronous Circuits with Constraint Line Delays,”
IEEE Trans. on Computers, pp. 175-181, February 1969.

C. N. Liu, “A State Variable Assignment Method for Asynchronous Sequential
Switching Circuits,” J. ACM, vol. 10, pp. 209-216, 1963.

J. H. Tracy, “Internal State Assignments for Asynchronous Sequential Machines,”
IEEE Trans. on Electronic Computers, vol. EC-15, pp. 551-560, August 1966.

G. K. Maki and J. H. Tracy, “A State Assignment Procedure for Asynchronous
Sequential Circuits,” IEEE Trans. on Computers, vol. C-20, pp. 666-668, June 1971.

C. J. Tan, “State Assignments for Asynchronous Sequential Machines,” IEEE Trans.
on Computers, vol. C-20, pp. 382-391, April 1971.

R. J. Smith, “Generation of Internal State Assignment for Large Asynchronous
Sequential Machines,” IEEE Trans. on Computers, vol. C-23, pp. 924-932, Septem-
ber 1974.

D. H. Sawin, III and G. K. Maki, “Asynchronous Sequential Machines Designed for
Fault Detection,” IEEE Trans. on Computers, vol. C-23, pp. 239-248, March 1974.

E. J. McCluskey, Logic Design Principles with Emphasis on Testable Semicustom
Circuit, Prentice-Hall, New Jersey, 1986.

S. H. Unger, “Hazards and Delays in Asynchronous Sequential Switching Circuits,”
IRE Trans. on Circuit Theory, pp. 12-25, March 1959.

D. B. Armstrong, A. D. Friedman, and P. R. Menon, “Realization of Asynchronous
Sequential Circuits Without Inserted Delay Elements,” IEEE Trans. on Computers,
vol. C-l7. PP. 129-134, February 1968.

L. Lavagno, K. Keutzer, and A. Sangionvanni-Vincentelli, “Synthesis of Verifiably
Hazard-free Asynchronous Control Circuits,” Advanced Research in VLSI Confer-
ence, pp. 87-102, May 1991.

[39]

[40]

[41]

[42]

[43]

[44]

[45]

[46]

[47]

[48]

[49]

[50]

[51]
[52]

111

L. Lavagno, K. Keutzer, and A. Sangionvanni-Vmcentelli, “Algorithms for Synthesis
of Hazard-free Asynchronous Circuits,” 28th ACM/IEEE Design Automation Con-
ference, pp. 302-308, 1991.

K.-J. Lin and C.-S. Lin, “Automatic Synthesis of Asynchronous Circuits,” 28th
ACM/IEEE Design Automation Conference, pp. 296-301, 1991.

M.-L. Yu and P. A. Subrahmanyam, “A Path-Oriented Approach for Reducing Haz-
ards in Asynchronous Design,” 29th ACM/IEEE Design Automation Conference, pp.
239-244, 1992.

D. B. Armstrong, A. D. Friedman, and P. R. Menon, “Design of Asynchronous Circuit
Assuming Unbounded Gate Delays,” IEEE Trans. on Computers, vol. C-18, pp. 1110-
1120, December 1969.

C. L. Seitz, “System Timing,” in Introduction to VLSI System, C. Mead and L. Con-
way, Eds. Reading, MA. Addison-Wesley, 1980.

A. S. Wojcik and K.-Y. Fang, “On the Design of Three-Valued Asynchronous Mod-
ules,” IEEE Trans. on Computers, vol. C-29, pp. 889-898, October 1980.

1. David, R. Ginosar, and M.Yoe1i, “Implementing Sequential Machines as Self-
Timed Circuits,” IEEE Trans. on Computers, vol. 41, pp. 12-17, January 1992.

B. Gilchrist, et. al., “Fast Carry Logic for Digital Computers,” IRE Trans. on Electri-
cal Computers, vol. EC-4, pp. 133-136, December 1955.

A. D. Friedman and P. R. Menon, “Synthesis of Asynchronous Sequential Circuits
with Multiple-Inputs Changes,” IEEE Trans. on Computers, vol. C-17, pp. 559-565,
June 1968.

M.-D. Shieh, C.-L. Wey, and P. D. Fisher, “Model of Asynchronous Finite State
Machines and Their Pipelined Structure,” 35th Midwest Symposium on Circuits and
Systems, pp. 659-662, August 1992.

V. I. Varshavsky, Self-Timed Control of Concurrent Processes, Kluwer Academic
Publisher, 1990.

B. W. Johnson, Design and Analysis of Fault-Tolerant Digital Systems, Addison-
Wesley Publisher, 1989.

H. Fujiwara, Logic Testing and Design for Testability, Computer System Series, 1985.
F. F. Tsui, LSI/VLSI Testability Design, McGraw-Hill Publisher, 1988.

112
[53] E. B. Eichelberger, “Latch Design Using Level Sensitive Scan Design,” Dig. COM-
PCON, Spring 83, San Francisco, pp.395-398, 1983.

[54] P. S. Bottorff, R. E. Garges, and E. J. Orosz, “Test Generation for Large Logic Net-
work,” 14th ACM/IEEE Design Automation Conference, pp. 479-485, 1977.

[55] H. Ando, “Testing VLSI with Random Access Scan,” Dig. COMPCON, pp.50-52,
February, 1980.

I'd-cudmmmra

 

uormmsw murmoddo Imbamonov onwuuwv uv st nsw

 

 

 

-’
V

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

BEL—24439

|___ L_~_
# II_
II

3110 ELVCI ano ELVCI 30C] ELVCI

 

 

 

 

 

 

 

 

 

 

 

'WP 9339 910599 ’0 U0 W039! $33le OIOAV OJ.
'910991 100‘ W011 300499149 Wile/10“”! 03 X08 [180138 NI 30nd

___

f N
layman“

0193s Beams!”

l 18"!!!”

p J

fl.-

_—

 

 

 

   

nICHrceN STQTE UNIV. LIBRRRIES
llIllWIllIII!HI”WWII"WIWHIIHlIIHIIIHHHI
31293009141163