Module 10:Sequential Circuit Testing and Scan Chains

Lecture 1 :ATPG for Synchronous Sequential Circuits

1
2
3
4
5
6
7
8
9

1.Introduction
Till now we have been looking into VLSI testing, only from the context of combinational circuits. In
this module we will study ATPG for sequential circuits. In the first lecture we will see the variations
required in fault model, algebra and ATPG procedure in sequential circuits compared to
combinational ones. Also we will compare the ATPG complexity in both the cases and show that
testing sequential circuits is many folds more involved than testing combinational circuits. Following
that in the next lecture we will introduce a special scheme called scan chain which ``modifies a
sequential circuit into a virtual combinational one. So, test patterns for a sequential circuit with
scan chain can be generated with slight variation in ATPG algorithms for combinational circuits (Dalgorithm, for example).
In this lecture we will first discuss the difference between sequential and combinational circuits from
the context of ATPG and single stuck-at fault model. In this course we will concentrate only on
sequential synchronous circuits with a single clock.
2. ATPG and testing: Sequential versus combinational circuits
Let us first see the basic architecture of a sequential circuit in Figure 1. In the figure it may be noted
that there are three blocks, namely NSF, OFB and state flip-flop. The first two blocks are
combinational circuits and the state flip-flop has sequential elements. So ATPG procedure for the
NSF and OFB blocks should be similar to the ones already introduced in the previous lectures.
However, it may be noted that compared to a standard combinational circuit, in case of NSF some
inputs (state feedback) are not controllable and its outputs are not observable. Similarly, in case of
the OFB, some of its inputs are non-controllable. When a circuit powers up, the flip-flops can have
any value (0 or 1). So for ATPG of the combinational blocks in sequential circuits, we need to control
(indirectly) the values in the nets which are outputs of flip-flops and observe (indirectly) the nets
which are inputs to the flip-flops. Once indirect controllability and observability are achieved, ATPG
for these combinational blocks (in sequential circuits) can be done using D-algorithm (or any other
combinational APTG algorithm).

Figure 1. Basic architecture of a sequential circuit [1]

Before we illustrate how indirect controllability and observability can be achieved in these
combinational blocks, we will discuss some assumptions in ATPG for single clock sequential circuits.
In single clock sequential circuits, each flip-flop is treated as 1-bit memory element with ONE
common clock. For each primary input pattern and secondary input pattern (present state), the
resulting primary output and secondary output (next state) patterns are produced. After a clock
edge, the secondary output pattern (next state) is transferred to the output of the flip-flops (present
state), which become new secondary inputs. Also, the primary outputs are updated. This activity
occurs at each clock edge, and so it is called synchronous operation.
Single stuck at faults are assumed in the two combinational blocks namely, NSF and OFB. Internal
faults of flip-flops are not modeled; their output and input faults are modeled as faults on input and
output signals of the combinational blocks. In other words, flip-flops are treated as ideal memory
elements and no faults are considered in the clock signal. Most of the time, D-flip-flops are used in
VLSI designs. So in this course whenever we refer to a flip-flop we essentially mean a D-flip-flop.

Module 10:Sequential Circuit Testing and Scan Chains

Lecture 1 :ATPG for Synchronous Sequential Circuits

1
2
3
4
5
6
7
8

Figure 2. A simple sequential circuit with a stuck-at-0 fault

Let us consider a simple sequential circuit in Figure 2, with a s-a-0 fault at net a . If we compare this
circuit with the block diagram shown in Figure 1, it may be noted that gate-1 corresponds to the
OFB, gate-2 is for the NSF and D-flip flop is the memory element.

Figure 3. Problems in ATPG for the stuck-at-0 fault

To test the s-a-0 fault, simply, a=1 and f =0, which results in D being propagated to the primary
output. It may be noted that net f (secondary input) is driven by the output of the state flip-flop. As
netf is not directly controllable, we cannot make it 0 and test the fault. As discussed, after power up,
the flip-flop can have any signal value (marked as X). So testing the s-a-0 fault is not as simple as in
case of combinational circuits. This problem is shown in Figure 3.
For ATPG of the fault, we need to indirectly control the net f to 0. Following that, we can apply the
test pattern as a =1 and b =X, which propagates D to the primary output. From the circuit it may be
noted that to make f to 0, we first need to make net d=0, which is the input to the flip-flop;
following that a clock edge can transfer the value of d to f (in the next state). The process of making
f =0 in a indirect manner (by state change) is shown in Figure 4.

Figure 4. Indirect controlling of f to 0

After net f is made 0, then a =1 and b =X would propagate the fault effect (D) to the primary
output; this is shown in Figure 5.

Figure 5. Test pattern for the s-a-0 fault

So, it may be noted that ATPG for combinational blocks in sequential circuits require more than one
pattern. In this example, the first pattern is a =X, b =0 and clock edge followed by a =1 and b =X.
In such cases, final pattern is according to combinational ATPG (that sensitize the fault and
propagates the effect to a primary output) and all other initial patterns are to bring the secondary
inputs to their required value.
ATPG for a fault in the NSF block is more complex than the ones in the OFB. In case of a fault in the
NSF we need to indirectly control the secondary inputs and in addition, propagate the fault effect to
the primary output via OFB. This is illustrated using a s-a-1 fault at net c in the circuit (Figure 6).
First, primary input b =0 ( a =X) and a clock edge is applied; this makes e =0 (and also c =0) after
the edge. It may be noted that even in presence of the s-a-1 fault, b =0 and a clock edge makes c
=0; this sensitizes the fault ( D at c ). In the next step, b =1 ( a =X) and a clock edge would
propagate the fault effect ( D ) to the output of the flip-flop (i.e, secondary input of the OFB).
Finally, a =0 ( b =X) would propagate fault effect to the primary output. Above mentioned three
steps are shown in Figure 6.

Module 10:Sequential Circuit Testing and Scan Chains

Lecture 1 :ATPG for Synchronous Sequential Circuits

1
2
3
4
5
6
7
8
9

Figure 2. A simple sequential circuit with a stuck-at-0 fault

Let us consider a simple sequential circuit in Figure 2, with a s-a-0 fault at net a . If we compare this
circuit with the block diagram shown in Figure 1, it may be noted that gate-1 corresponds to the
OFB, gate-2 is for the NSF and D-flip flop is the memory element.

Figure 3. Problems in ATPG for the stuck-at-0 fault

To test the s-a-0 fault, simply, a=1 and f =0, which results in D being propagated to the primary
output. It may be noted that net f (secondary input) is driven by the output of the state flip-flop. As
netf is not directly controllable, we cannot make it 0 and test the fault. As discussed, after power up,
the flip-flop can have any signal value (marked as X). So testing the s-a-0 fault is not as simple as in
case of combinational circuits. This problem is shown in Figure 3.

For ATPG of the fault, we need to indirectly control the net f to 0. Following that, we can apply the
test pattern as a =1 and b =X, which propagates D to the primary output. From the circuit it may be
noted that to make f to 0, we first need to make net d=0, which is the input to the flip-flop;
following that a clock edge can transfer the value of d to f (in the next state). The process of making
f =0 in a indirect manner (by state change) is shown in Figure 4.

Figure 4. Indirect controlling of f to 0

After net f is made 0, then a =1 and b =X would propagate the fault effect (D) to the primary
output; this is shown in Figure 5.

Figure 5. Test pattern for the s-a-0 fault

So, it may be noted that ATPG for combinational blocks in sequential circuits require more than one
pattern. In this example, the first pattern is a =X, b =0 and clock edge followed by a =1 and b =X.
In such cases, final pattern is according to combinational ATPG (that sensitize the fault and
propagates the effect to a primary output) and all other initial patterns are to bring the secondary
inputs to their required value.
ATPG for a fault in the NSF block is more complex than the ones in the OFB. In case of a fault in the
NSF we need to indirectly control the secondary inputs and in addition, propagate the fault effect to
the primary output via OFB. This is illustrated using a s-a-1 fault at net c in the circuit (Figure 6).
First, primary input b =0 ( a =X) and a clock edge is applied; this makes e =0 (and also c =0) after
the edge. It may be noted that even in presence of the s-a-1 fault, b =0 and a clock edge makes c
=0; this sensitizes the fault ( D at c ). In the next step, b =1 ( a =X) and a clock edge would
propagate the fault effect ( D ) to the output of the flip-flop (i.e, secondary input of the OFB).

Finally, a =0 ( b =X) would propagate fault effect to the primary output. Above mentioned three
steps are shown in Figure 6.

Module 10:Sequential Circuit Testing and Scan Chains

Lecture 1 :ATPG for Synchronous Sequential Circuits

1
2
3
4
5
6
7
8
9

Now, we will see an interesting thing. If we use higher order algebra, then only one pattern can test
the fault. Let us see the case if b =0 ( a =X). Fault is sensitized as D and e=f = D. Now as the
secondary input ( c ) is not controlled, c =X. By 5 value algebra, d =X and so fault effect cannot be
propagated to the output. However, if we observe carefully at net d, we will note that if the fault is
there then d =X (as value is determined by the flip-flop at start up of circuit). However, if fault is not
there then d =0 (as e =0). So we can mark d as 0/X. Now, f = D, which in turn makes g= D;
D(=0/1) OR 0/X = 0/1 (= D). So fault can be detected using a single pattern b =0 ( a =X). All these
steps are shown in Figure 9.

Figure 9. ATPG for s-a-1 fault using higher order algebra

The following points are to be noted
In the example, higher order algebra is used, as a net is marked as 0/X, which is not available in
5 value algebra.
Higher order algebra improves efficiency of ATPG of sequential circuits. As higher order algebra
reduces the number of input (primary and secondary) lines to be controlled, there is reduction in the
number of steps (in terms of clock edges and test patters) to control the secondary inputs (or make
the NSF block outputs observable via OFB). However, it does not guarantee that ATPG will not

require controlling the secondary inputs and propagating the fault effect to the primary output via
OFB. This example was a special case where controlling the secondary inputs were not required.
Higher order algebra will also reduce the number of lines to be controlled in ATPG of a
combinational circuit. However, it is not applied as computational complexity rises with increase in
order of the algebra and inputs are easily controllable in combinational circuits.
Table 1 illustrates a 9 value algebra which is used for ATPG of combinational blocks in sequential
circuits.
Table 1. Nine value algebra
Symbol
0
1
X
D
D
G0
G1
F0
F1

Implication
(0/0)
(1/1)
(X/X)
(1/0)
(0/1)
(0/X)
(1/X)
(X/0)
(X/1)

Normal Circuit
0
1
X
1
0
0
1
X
X

Faulty Circuit
0
1
X
0
1
X
X
0
1

Module 10:Sequential Circuit Testing and Scan Chains

Lecture 1 :ATPG for Synchronous Sequential Circuits

1
2
3
4
5
6
7
8
9

3. ATPG of sequential circuits: Time frame expansion method

ATPG for (combinational blocks in) sequential circuits involves the following two broad steps:

1. Replace all the flip-flops by nets. Perform D-algorithm on the virtual combinational circuit and
find the values of primary and secondary inputs.
2. Using multiple steps (primary inputs, secondary inputs and clock pulses) to apply the required
signals to the secondary inputs (determined in Step 1).
The circuit shown in Figure 10 will be used to illustrate ATPG for sequential circuits using the time
frame expansion approach.

Figure 10. Sequential circuits with a s-a-0 fault

In the circuit we may note that nets a,b,c are primary inputs and nets d,i are secondary inputs. So if
we replace the flip-flops with nets we get the circuit shown in Figure 11; such replaced nets are
marked by doubled sided arrows. Also in the same figure we determine the test pattern to detect
the s-a-0 fault as: a =1, b =1, c =1, d =1, i =1 and output is D. a =1, b =1, c =1 can be obtained
by directly controlling the primary inputs. However, d =1, i =1 corresponds to secondary inputs
which need to be achieved by setting primary inputs appropriately and clock edges, in steps
previous to applying the final primary input as a =1, b =1, c =1.

Figure 11. Sequential circuit of Figure 10 with flip-flops replaced by nets

Before we study in detail the ATPG for the circuit given in Figure 10, we disuses the following
definitions and conditions.
Definition 1: Sequential depth of a flip-flop:

If the output of a flip-flop can be controlled by only primary inputs (and a clock pulse) it has
sequential depth of 1. In the circuit of Figure 10, flip-flop F1 has sequential depth of 1 as it is
controllable by primary input(s) c . A flip-flop has a sequential dept of dseq if its output is dependent
on
primary
inputs
and
at
least
one
flip-flop
of
depth
dseq-1. In the example, flip-flop F2 is dependent on primary input b and output of flip-flop F1 (via net
e ); so sequential depth of F2 is 2.
Definiation2: Non-cyclic Circuit
A sequential circuit is non-cyclic if there is no flip-flop whose input is dependent on its output. For
example, in the circuit of Figure 10, input of F1 is dependent on only primary inputs. On the other
hand, input of F2 is dependent on primary inputs (net b ) as well as the output of F1 (net d ). So the
circuit non-cyclic. An example of a cyclic sequential circuit is given in Figure 12. In this case input of
F1 is dependent on its own output (and primary input). It may be noted that in cyclic circuits we
may not be able to control the secondary inputs; this concept will be elaborated in an exercise
problem. A flip-flop whose input is dependent on its own output is called a cyclic flip-flop.

1
2
3
4
5
6
7
8
9