Module : 4B

p S K
P r a dee
K IT:
PREPARED BY
PRADEEPKUMAR S K
ASSISTANT PROFESSOR, DEPARTMENT OF ECE
K I T , TIPTUR 572201
▪ As the size of circuits is growing, the complexity of test pattern generation also
increases.
▪ Hence manual test generation (being too cumbersome) is not a feasible method
anymore.
▪ Therefore, we need the help of automatic test pattern generation (ATPG).

S K
▪ But methods studied earlier in this DFT course like the path sensitization method is a

dee p
very intuitive approach and can’t be developed into an algorithm for computer

a
software.

IT: P r
▪ The D algorithm is just a derivative of the path sensitization method in a more

K
systematic approach that is suitable for computer acceleration.
▪ The D algorithm is a deterministic ATPG method for combinational circuits,
guaranteed to find a test vector if one exists for detecting a fault. It uses cubical
algebra for the automatic generation of tests.
▪ Three types of cubes are considered:
▪ Singular cube
▪ Propagation D-cube (PDC) or primitive
▪ Primitive D-cube of a fault (PDCF)
 Cubes
The D-algebra is a 5-value logic consisting of
logic: 1, 0, D, D', X. The D stands for Discrepancy, Singular Cover
as discussed in the path sensitization method. Singular Cover (SC) of any logic gate is the
Following algebraic rules are applicable compact form of truth-table. This is done
in D algorithm for intersection: using don’t cares (x). Following reduced truth
table is the singular cover of an AND gate.

p S K
P r a dee
K IT:
Note that intersection in D-algebra is quite different
Each row of a singular cover is termed as
to what we are familiar with sets and relations in
Singular Cube. The above singular cover of
mathematics. They do not follow properties like
the AND gate has three singular cubes.
commutativity or associativity.
▪ Propagation D-cubes (PDCs) of a gate causes the output of the gate to depend upon the minimum
number of its specified inputs. It is used to propagate D or D’ from a specified input to the output.
Propagation D-Cubes can be derived from the intersection of singular cubes of gates of opposite output
values.
▪ Example: Here’s the truth table of an OR gate. To generate the PDC, we find the singular cover for the
OR gate.
Now, we intersect the singular cubes of every possible combination(s)

K
with opposite output values. Intersecting the singular cubes of row2

p S
dee
and row1, also row3 and row1 serves the purpose. a b out
In this case, the intersection doesn’t need

P r a
IT:
{1, x, 1} ∩ {0, 0, 0} = {1 ∩ 0, x ∩ 0, 1 ∩ 0} = {D’, 0, D’}
D’ 0 D’
any specific order. If we intersect in the {x, 1, 1} ∩ {0, 0, 0} = {x ∩ 0, 1 ∩ 0, 1 ∩ 0} = {0, D’, D’}

K
other way, we obtain PDCs as {D, 0, D} and 0 D’ D’
{0, D, D}.

This is very similar to forward propagation we did in the path sensitization method.
But then why are we learning it? These D-cubes tend to be much more inconvenient and
tiresome for us as compared to path sensitization method. The answer is that we human
beings have IQ, and hence we can solve methods like path sensitization intuitively. A
computer doesn’t the necessary intelligence (yet). The D algorithm takes the creativity out of
test generation and allows a computer to do it.
 p S K
P r adee
KIT:
 p S K
P r adee
KIT:
▪ D-cubes represent the input-output behavior of the good and faulty circuits.
▪ Primitive D-cube of a Fault (PDCF) is used to specify the minimum input conditions required at
inputs of a gate to produce an error at its output.
▪ This is used for fault activation. PDCF can be derived from the intersection of singular covers of
gates in faulty and non-faulty conditions having different outputs.

Here is an AND gate with s-a-0 fault at the

p S K
dee
output. To generate the PDCF, we first draw

P r a
IT:
the truth table of the faulty and non-faulty

K
circuit. Next, we derive the singular cover for
faulty as well as non-faulty circuits.
▪ For PDCF we need to intersect only those columns for which output is different for non-
faulty and faulty circuits. Since for faulty circuits, we only have one singular cube {x, x, 0}; we
need to intersect it with a singular cube of the non-faulty circuit having the opposite output
value (i.e. logic-1). The singular cube {1, 1, 1} perfectly fits this criterion.

{1, 1, 1} ∩ {x, x, 0} = {1 ∩ x, 1 ∩ x, 1 ∩ 0} = {1, 1, D}

Notice the order in which the intersection is done! Always intersect as

K
⇒ singular-cube (non-faulty circuit) ∩ singular-cube (faulty circuit).
p S
P r a dee
K IT:
Finally, PDCF of this faulty AND gate is {a, b, out} = {1, 1, D}.
This is similar to fault excitation we did in the path
sensitization method, albeit in a more structured approach.

Here, D is interpreted as being logic-1 if the circuit is fault-

free and logic-0 if the fault is present.
Example: Consider 3 input Nand Gate with inputs ABC and output as D. Find the Singular Cover.
Find the Primitive D Cubes ,if line ‘B’ is s-a-1.

SC (NAND) SC (NAND)
GOOD FAULTY
A B C D A B C D
0 X X 1 0 X X 1
X 0 X 1 X X 0 1

K
X X 0 1 1 X 1 0

p S
dee
1 1 1 0

P r a
K IT:
 p S K
P r adee
KIT:
FRONTIERS
In the D algorithm, we have two essential components:
D-frontier: A set of gates whose output value is currently
unknown, but have one or more D (or D’) at their inputs.
J-frontier: A set of gates whose output value is assigned, but
input values have not been decided yet.
Check out this part of a combinational circuit for which ATPG
is to be performed. The blue gates are D-frontier while green
gates are J-frontier.

p S K
P r a dee
K IT:
▪ The test generation process consists of the following three steps:

▪ Step 1: Generate a PDCF for the given fault. In this way, we create D-frontier. This is also
known as fault activation.

p S K
▪ Step 2: Drive the D (or D’) from the output of the gate under test to an output of the circuit by

dee
successively intersecting the current test cube with the propagation D-cubes of successive

r a
gates. The intersection of a test cube with the propagation D-cube of a successor gate results in

IT: P
another test cube. This process is also known as D-drive or forward propagation.

K
▪ Step 3: Justify the internal line values by driving back towards the inputs of the circuit,
assigning input values to the gates so that a consistent set of circuit input values may be
obtained. This process is known as justification of J-frontiers or backpropagation.

▪ Step 4: Backtrack to previous steps if any conflict occurs in justification.

Application of the D algorithm by deriving a test for detecting the g→s-a-0 fault in
the following circuit.

p S K
P r a dee
K IT:
 p S K
dee
a b c d e f g h i j x y

P r a
IT:
Activation 1 1 D

K
D 0 D
Drive
1 D D
1 X 1
Backtrace
1 1 0
Finish 1 1 1 1 X X D 0 1 D D X

The test vector for finding the g→s-a-0 fault is: {a, b, c, d, e, f} = {1, 1, 1, 1, x, x}
 1 2 3 4 5 6 7 8 9
Activation

Drive

Backtrace

S K
Finish

dee p
P r a
IT:
1 2 3 4 5 6 7 8 9

K
Activation X 0 D
0 D’
Drive
1 D
X 0 1
Backtrace
1 0 0
Finish 1 0 X 0 0 D 1 D’ D
 1 2 3 4 5 6 7 8 9
Activation

Drive

Backtrace

S K
Finish

dee p
P r a
KIT:
1 2 3 4 5 6 7 8 9
Activation 1 X D’
1 D’ D
Drive
D 1 D
D’ 1 1
Backtrace
0 1
Finish 1 X 0 1 D’ 1 D 1 D
Determine a suitable test cube for a stuck-at-0 fault at node 9 using D-Algorithm

p S K
P r a dee
IT:
1 2 3 4 5 6 7 8 9 10 11 12 13
Activation 1 0
K 1 0 1 X D
D 1 D
Drive
D 0 D
X 0 0
Backtrace

Finish 1 0 X 0 1 0 1 X D 1 D 0 D
 P O DE M
• PODEM is an improved version of D-ALG
• PODEM starts at the PIs instead of at faulty
line like D-ALG.
• PODEM finds a logic gate with D or D’ on its
inputs that is closest to a PO.
• The X-PATH-CHECK routine indicates that a

K
path exists with unassigned signals from that

p S
gate to a PO then:

dee
• For propagating D, it would set the gate objective of

r a
obtaining a 1 on that gate output if it is an AND or OR

IT: P
or 0 if NAND or NOR.
• For propagating D’, the objective would be 0 for

K
AND/OR and 1 for NAND/NOR.
• Next, backtracing occurred from the objective to
the PIs.
• If all inputs had to be set, PODEM backtraced through
the hardest-to-control input first.
• If only one had to be set, it backtraced through the
easier-to-control input.
• This input became the next objective and the
process is repeated
Example:
• Select path s-Y (level distance 1 instead of path s-u-
v-Z with 2).
• X-PATH-CHECK determines that there is an X path
along path s-Y.
• Therefore, initial objective is to set r to 1.
• Since both input to XOR gate r need to be set,
PODEM picks the hardest-to-control input n with

K
objective of setting it to 0.

p S
dee
• Backward implications: set m = 0 and set g = 0 leads

r a
to A = 0.

IT: P
• Forward implications: d = 0 and X = 1.

K
• r is still not set.
• Backward implications: set m = 0 and set k = 1 leads
to B = 1.
• Forward implications: k = 1, m = 0, r = 1, q = 1, Y = 1, s
= D, u = D, v = D, Z = 1.
• X-PATH-CHECK finds the D-frontier is empty, i.e., no
X path from s to Y or Z.
• Backtracking sets B = 0 and then A = 1, B = 0 (fault not
sensitized).
• Finally, A = 1, B = 1 results in success.
 p S K
: P r a dee
KIT
A B C d e f g h k l m n p q r s u v X Y Z
1 x x x x x x x x x x x x x x x x x x x x
1 0 x 0 0 0 0 0 0 0 1 1 1 0 0 1 1 0 1 1 x
1 1 x 1 1 1 1 1 1 1 1 1 1 0 1 0(D’) D’ D’ 0 D’
1 1 x
 p S K
P r adee
KIT:
 Find Test vectors using PODEM , α s-a-0

1 2 3 4 5 6 7 8 9 10 11 12

p S K
P r a dee
KIT:
Fujiwara and Shimono introduced several novel concepts to further limit the ATPG search space and accelerate backtracing:
Immediate Implications: PODEM misses opportunities to immediately assign value that are uniquely determined to signals.

p S K
P r a dee
IT:
• Given objective L = 0, PODEM would backtrace and assign k=1, g=0 and B=0.

K
• This is unfortunate since B=1 => h=1 and j=0 which prevents objective.
 Unique Sensitization: There are other opportunities to find
signals that are uniquely determined.

In this example, there is only one path over which the fault
can propagate -- might as well set the off-path inputs
immediately, i.e., c=1, G=1, A=1 and L=1.

p S K
dee
Headlines: Defined as the "cut point" in a circuit that separates

P r a a cone of logic driven by PIs from the rest of the circuit.

K IT:

Multiple Backtrace: FAN uses a breadth-first multiple backtrace

procedure.
 Derive a test for Z➔ s-a-0 using FAN Algorithm

p S K
: P r a dee
Intialize➔
A
x K
B
x IT x x
C
x
D E F
x
G
x
H
x
I
x
J
x
K
x
L
x
M N
1 1
Z
D
BackTrace multiple path➔ x x x x x x 1 x 1 x x x 1 1 D
BackTrace multiple path➔ 1 1 x x 1 1 1 x 1 x x x 1 1 D
▪ A Delay fault in a combinational circuit can be detected only by applying a sequence of two
test pattern.
▪ First, initialization pattern, sets up initial condition in a circuit so that the fault slow-to-rise(s-a-
0) or slow-to-fall (s-a-1) at the input or output of a gate can affect an output of circuit.
▪ Second, transition or propagation pattern, propagates the effect of the activated transition to a

K
primary output of the circuit.

p S
dee
▪ Ex: For Slow-to-rise (s-a-0) in figure ; First pattern ABC=001; Second pattern ABC=101;

P r a
IT:
▪ Slow –to-fall(s-a-1) in figure; First pattern ABC=101; Second pattern ABC=001;

K
 ▪ The initialization pattern first loaded into the input
latches.
▪ Once circuit stabilized, transition pattern is clocked into
the latches by C1.
▪ Output pattern is loaded into the output latches by C2
clock at logic 1 for required time for output pattern to
stabilize.
▪ Delay fault is confirmed if the output value is different
from expected value.

K
• Delay Tests are classified into : (i) Non-Robust (ii) Robust

p S
• Non-Robust detects fault in a path provided no other paths have delay Fault.

dee
• Robust detects fault in a path independent of any other delay faults in other paths.

P r a
K IT:
Non-Robust: (111,101) detects Slow-to-rise at ‘e’ Robust: (01,11)detects slow-to-fall at ‘d’ in path
only if b-d-f path doesn’t have delay fault a-c-d-f independent of any faults in other paths
▪ Designing multiple fault detection tests for a logic network is difficult since large number of faults
are to be considered. Hence we reduce the number of faults that need to be tested in a network.
▪ Few reduction methods are Fault collapsing , Fault folding and Prime faults.

▪ Fault collapsing:
▪ While creating Fault site list, if tool identifies fault which are dependent to each other then consider them as
equivalent faults. Ex: If Pattern of Fault-A finds Fault-B then we say they are equivalent.
▪ If 4 faults are equivalent, then we(tool) mark one of them as real fault and rest three are marked as collapsed to

S K
the real fault. This concept is called Fault Collapsing.

dee p
▪ Fault folding is the process of applying test equivalent or test implied relations from a primary output

P r a
towards the connected primary inputs in order to find a reduced set of faults that cover the set of

IT:
faults on the intervening network.

K
▪ For non-reconvergent fan-out circuits, this folding operation produces minimal classes consisting only of stuck-at
faults on primary inputs whose tests detect all faults in the circuit.
▪ For reconvergent fan-out circuits, the set of faults at the primary inputs, fan-out origins, and fan-out branches is
sufficient to derive a complete set of tests that will detect all detectable faults in the circuit.

▪ Fault-A is said to be prime fault if every fault that is dominated by fault=A is also equivalent to Fault-A.

▪ Representative Set of Prime Fault (RSPF)

▪ A set that consists of exactly one prime fault from each equivalence class of prime faults
▪ True minimal RSPF is difficult to find.
 p S K
P r adee
KIT: