Week 5: Course Material

Lecture 22
 CONTEST [1989]
D Two-stage process
D 1st stage: aim to detect as many faults as
possible
• Fitness = a x #detected + b x #excited
D 2nd stage: aim to detect remaining hard faults
individually
• Fitness depends on if the target fault has
been excited, and how many fault effects are
in the circuit

82
EE141
 GATEST [1994]
D GA-based ATPG for seq ckts
D Tournament selection, uniform crossover
D 1st phase: initialize the seq ckts
D 2nd phase: detect & excite as many faults as
possible
D 3rd phase: similar to phase 2, but to monitor
fault-free and faulty ckt events
D 4th phase: individuals now become sequence
of vectors, aim to detect & excite as many
faults as possible

83
EE141
 Seeding the Initial Population
D Place non-random individuals in the initial
population
D This can reduce the number of generations
needed for the GA to obtain a good solution
D Aggressively used in STRATEGATE [1997]
• Target individual faults rather than groups of faults
• Seeding of propagation sequences
• Seeding of justification sequences

84
EE141
 Delay Testing
D Delay defects: class of defects that affects the
functionality only when the circuit is running at
a high speed
D Stuck-at fault model insufficient to model all
delay-related defects
D Delay fault models
• Path delay fault
• Transition fault
• Segment delay fault

96
EE141
 Path Delay Fault
D Models a combinational path in the circuit
• Considers the cumulative effect of the delay along the path
• On-inputs of a path
• Off-inputs of a path
D A transition is launched at the start of the path, and
a test must propagate the transition to the end of
the path
• Two faults associated with every path: rising and falling
transition at the start of the path
D Number of paths can be exponential to the number
of gates in the circuit
D Two vectors needed
• V1: initialization vector
• V2: launch and capture vector

108
EE141
Classification of Path Delay Faults
D Statically sensitizable: all off-inputs of a path
P can be assigned to non-controlling values
by some vector
D Single-path sensitizable: all off-inputs of a
path can be set to non-controlling values for
both vectors of a test
D False path: a transition cannot propagate
from the start to the end of path
• Not all necessary off-input values can be set
to non-controlling values simultaneously

109
EE141
 Statically Unsensitzable Path

110
EE141
 Robustly Testable Paths
D Single-path sensitization is too stringent
D May not need to set all off-inputs to non-
controlling values in V1 in order to propagate
a transition
• Highlighted path is robustly testable

111
EE141
 Robustly Testable (Cont.)
• D If a path is robustly testable, then the corresponding test
can verify the correctness of the path irrespective of other
delays in the circuit
• D Value criteria for robust testable path:
• When the corresponding on-input of P has a controlling to non-
controlling transition, the value in the first vector for the off-
input can be X with the value for the off-input as a non-
controlling value in the second vector.
• When the corresponding on-input of P has a non- controlling to
controlling transition, the values for
• the off-input must be a steady non-controlling value for both
vectors.
112
EE141
 Non-robustly Testable Path
D Not all paths are robustly testable
D Further relax requirements for V1
D Test is valid if circuit has no other delay faults
• Highlighted path is non-robustly testable

113
EE141
 Non-robust Path
(cont.)
D Non-robust test only valid if noother
delay fault is present in the circuit
D Value criteria for non-robust testing:
• Irrespective of the transition on the on-
input, the value in the first vector for the off-
input can be X, with the value for the off-
input as a non-controlling value in the
second vector.

114
EE141
 ATPG for Path-Delay Faults
D Can use new value algebra toconsider
both vectors simultaneously during
ATPG

115
EE141
 Boolean Operations

116
EE141
 RESIST [1994]
D Recursion-based path-delay-faultATPG
• Starts at a PI
• Depth-first-search through the circuit along
each path
• Generate a test for each path
• Takes advantage of many paths that share
common path-segments

117
EE141
 Transition Fault
Model
D Assumes a large/gross delay is present at a
circuit node
D Irrespective of which path the effect is
propagated, the gross delay defect will be late
arriving at an observable point
D Most commonly used in industry
• Simple and number of faults linear to circuit size
• Also needs 2 vectors to test
D Node x slow-to-rise (x-STR) can be modeled
simply as two stuck-at faults
• First time-frame: x/1 needs to be excited
• Second time-frame: x/0 needs to be excited and propagated

118
EE141
 Transition Fault
Properties
D Lemma: a transition fault may be launched
robustly, non-robustly, or neither
D Example: STR at output of OR gate

119
EE141
 Transition Fault Properties
(cont.)
D Lemma: a transition fault may be
propagated robustly, non-robustly, or
neither
D Example: STF at output of gate‘a’

120
EE141
 Transition Fault Testing with
Stuck-At ATPG
D Simply treat each transition fault astwo
stuck-at faults
D Can test it with broadside,skewed-load,
or enhanced scan

121
EE141
Properties of Chaining Stuck-at
vectors
D Consider a sequence of 3 vectors: (vi,
vj, vk) forming two vector-pairs (vi, vj)
and (vj, vk)
D Theorem: Transition faults detected by
(vi,vj) and pattern (vj,vk) are mutually
exclusive.
D Why?

123
EE141
Lecture 23
 Bridging Fault
D Models shorts between two circuit nodes
D The bridge fault is not excited unless the two
circuit nodes have opposing logic values
D Faulty value depends on the bridge-fault type:
• AND bridge: faulty value is the AND of the two
involved nodes’ values
• OR bridge: faulty value is the OR of the two
involved nodes’ values
• X Dom y: value of x dominates
• X Dom1 y: x dominates y if x=1
• X Dom0 y: x dominates y if x=0
124
EE141
 Illustration of the Bridge
Fault Models

125
EE141
 Bridging Fault ATPG
D Modeled as a constrainedstuck-at
ATPG
D Consider AND-bridge(x,y), we can do
either:
• Detect x/0 with setting y=0
• Detect y/0 with setting x=0
D Conventional stuck-at ATPG can be
modified to handle bridge faults

126
EE141
Combinational Test Set Compaction
D Want to reduce the test set sizeto
reduce test data storage and test
application time
D Idea: find a minimal set of vectorsthat
can detect every fault
D First build a detection dictionary

127
EE141
 Test Set Compaction
(cont.)

D Essential vector: a vector that detects some

faults that no other vector can detect
• V4 is essential
D A set covering algorithm is applied to find a
min test set such that every fault is covered

128
EE141
 Test Set Compaction (cont.)
D If vectors are incompletely specified
• Some vectors may be compatible: 1X0X
and X100 are compatible. Just one vector
1100 is sufficient
D Reverse-ordersimulation
• Simulate the test set in reverse order,
some vectors may no longer be needed

129
EE141
 N-Detect ATPG
D Idea: detect every fault at least N times
• N vectors that detect a fault must be different
D Although the same fault coverage, can
significantly enhance the defect coverage
• If x/0 is detected 2 times, one with y=1, and the
other with y=0, then the AND-bridge fault of (x,y)
would have been detected by the second test
D ATPG can be modified to N-Detect ATPG

131
EE141
 Concluding Remarks
D Covered a number of topics
• Theoretical Foundations
• Combinational & sequential ATPG
• Untestable fault identification
• Simulation-based & hybrid ATPG
• Delay testing
• Bridging fault testing
• Compaction, N-Detect, FSM testing
D Challenges Ahead
• Fast untestable fault identification essential to
remove large numbers of stuck-at, bridge,
delay faults
• Sequential ATPG remains an open research area
133
EE141
Lecture 24
 Logic Built-In Self-Test

1
EE141
 Introduction
D What are the problems in today’s
semiconductor testing?
• Traditional test techniques become quite
expensive
• No longer provide sufficiently high fault
coverage
D Why do we need built-in self-test (BIST)?
• For mission-critical applications
• Detect un-modeled faults
• Provide remote diagnosis
3
EE141
 BIST Techniques
Categories
D OnlineBIST
• Concurrent online BIST
• Non Concurrent online BIST
D OfflineBIST
• Functional offline BIST
• Structural offline BIST

4
EE141
 A General Form of Logic
BIST
BIST

Offline Online
[Abramovici 1994]
Non-
Functiona Structural Concurrent concurren
l
t

Logic BIST Techniques

5
EE141
 A Typical Logic BIST System
Test Pattern Generator
(TPG)

Logic
BIST Circuit Under Test
Controller (CUT)

Output Response Analyzer

(ORA)

Structural off-line BIST

6
EE141
 BIST Design Rules
Logic BIST requires much more stringent design restrictions when
compared to conventional scan. Therefore, when designing a logic BIST
system, it is essential that the circuit under test meet all scan design rules
and BIST specific design rules, called BIST design rules.

7
EE141
 Typical X-bounding
Methods

Methods for blocking an unknown (X) source

8
EE141
 X-bounding Methods
Depending on the nature of each unknown (X) source, several
X-bounding methods can be appropriate for use.

Common problems:
(1) Increase the area of the design.
(2) Impact timing.

9
EE141
 Typical Unknown Sources
D Analog Blocks
• Adding bypass logic.
• Adding control-only scan point
D Memories and Non-Scan Storage
Elements
• Bypass logic
• Initialization
D Combinational Feedback Loops
• Scan points

10
EE141
 Typical Unknown Sources
(cont’d)
D Asynchronous Set/Reset Signals
• using the existing scan enable (SE) signal to
protect each shift operation and adding a
set/reset clock point (SRCK) on each
set/reset signal to test the set/reset circuitry.

SRCK Set/Reset
Circuitry
SE

Functional R
[Abdel-Hafez 2004]
0
Logic D Q
1
Scan-In CK

11
EE141
 Typical Unknown Sources (cont’d)
D Asynchronous Set/Reset Signals

Shift Window Capture Window Shift Window Capture Window Shift Window
C1
CK … … …
C2
SRCK

SE

Timing control diagram for testing data and set/reset

faults
12
EE141
 Typical Unknown Sources
(cont’d)
D Tri-State Buses
• Re-synthesize each bus with
multiplexers.
• One-hot decoder

A one-hot decoder for testing a tri-state bus with 2

drivers
13
EE141
Lecture 25
 Typical Unknown Sources
(cont’d)
D False Paths
• 0-control point
• 1-control point
D Critical Paths
• Adding an extra input pin to a selected
combinational gate on the critical
path.

14
EE141
 Typical Unknown Sources
(cont’d)
D Multiple-Cycle Paths
• 0-control point
• 1-control point
• Holding certain scan cell output states
D Floating Ports
• PI or PO must have a proper connection to
Power (Vcc) or Ground (Vss).
• Floating inputs to any internal modules must
be avoided.

15
EE141
 Typical Unknown Sources
(cont’d)
D Bi-directional I/O Ports
• Fix the direction of each bi-directional I/O port
to either input or output mode.

EN
SE D IO
BIST_mode Z

Forcing a bi-directional port to output

mode
16
EE141
 Re-Timing
Races and hazards caused by clock skews may occur between the TPG
and the (scan chain) inputs of the CUT as well as between the (scan chain
outputs of the CUT and the ORA. To avoid these potential problems and
ease physical implementation, we recommend adding re-timing logic
between the TPG and the CUT and between the CUT and the ORA.

T D Q D Q D Q D Q O
P R
G CUT A
CK CK CK CK

CK1 CK2 CK3

Re-timing logic among the TPG, CUT, and ORA

17
EE141
 Test Pattern Generation
D Test pattern generators (TPGs) constructed
from linear feedback shift registers (LFSRs)
D TPG
• Exhaustive testing
• Pseudo-random testing
• Pseudo-exhaustive testing

18
EE141
Standard LFSR
D Consists of n D flip-flops and a
selected number of exclusive-OR
(XOR) gates

hn-1 hn-2 h2 h1
[Golomb 1982]
Si0 Si1 Sin-2 Sin-1

An n-stage (external-XOR) standard

LFSR
19
EE141
Modular LFSR
D Each XOR gate placed between two
adjacent D flip-flops

h1 h2 hn-2 hn-1

[Golomb 1982]
Si0 Si1 Sin-2 Sin-1

An n-stage (internal-XOR) modular

LFSR
20
EE141
 LFSR Properties
D The internal structure of the n-stage
LFSR can be described by a
characteristic polynomial of degree n,
f(x).

hi is either 1 or 0,depending on the feedback path

21
EE141
 LFSR Properties
D Let Si represent the contents of the n-
stage LFSR after iithshifts of the initial
contents,S0,of the LFSR, and Si(x) be
the polynomial representation of Si

If T is the smallest positive integer such that f(x) divides 1 xT ,then

the integer T is called the period of the LFSR.

22
EE141
 4-stage standard and modular
LFSRs
• 4-stage Standard LFSR
f x   1  x2  x 4

• 4-stage Modular LFSR

f x  1 x 2  x 4
f x   1  x  x 4

s
0
 x3

23
EE141
 Primitive polynomials list
Primitive polynomials of degree n up to
100

Note: “24 4 3 1 0” means p(x)  x24  x 4  x3  x1  x0

26
EE141
 Exhaustive Testing
D ExhaustiveTesting
• Applying 2n exhaustive patterns to an n-input
combinational circuit under test (CUT)
D Exhaustive patterngenerator
• Binary counter
• Complete LFSR => generates all zero also

27
EE141
 Binary counter

X4
X1 X2 X3

Example binary counter as EPG

28
EE141
 Complete LFSR
0 0 0 1 0 0 0 1

(a) 4-stage standard CFSR (b) 4-stage modular CFSR

0 0 0 1 1 0 0 0

(c) A minimized version of (a) (d) A minimized version of (b)

Example complete LFSRs as

EPG 29
EE141
Lecture 26
 Exhaustive Testing
performance
• D Exhaustive Testing guarantees all detectable,
combinational faults will be detected.
• D Test time maybe be prohibitively longif input
number is large than 20.

30
EE141
 Pseudo-Random Testing
D Pseudo-random patterngenerator
D Reduce test length but sacrifice the fault
coverage
D Difficult to determine the required test
length and fault coverage

31
EE141
 Pseudo-Random Testing
D Maximum-lengthLFSR
• RP-resistant problem
D Weighted LFSR
D CellularAutomata

32
EE141
 Weighted LFSR

1 0 0 1

X4
X3
X2
X1

Example weighted LFSR as

PRPG
33
EE141
 Pseudo-Exhaustive Testing
D Reduce test time while retaining many
advantages of exhaustive testing
D Guarantee 100% single-stuck fault coverage

• Verification test technique

• Segmentation test technique

38
EE141
 Verification Testing
Divide the CUT into m cones, backtracing from each output to
determine the inputs that drive the output. Each cone will receive
exhaustive test patterns and are tested concurrently.
[McCluskey 1984]
Pseudo-exhaustive pattern generators
x1 x2 x3 x4
PEPGs

y1 y2 y3 y4

An (n, w)=(4, 2) CUT

39
EE141
 Syndrome Driver Counter
Use SDC to generate test patterns. Check whether some inputs
can share the same test signal. If n-p Inputs can share test inputs with
other p inputs, then the circuit can be tested exhaustively with these
p inputs.
[Savir 1980]

X1 X2 X3
A 3-stage syndrome
driver counter
X4

40
EE141
 Constant-Weight Counter
Use CWCs to generate test patterns. Constant-Weight counters
are constructed using constant-weight code or M-out-of-N code.
The constant-weight test set is a minimum-length test set for many
circuits.

A 3-stage constant-weight
X1 X2 X3 counter

X4

41
EE141
 Combined LFSR/SR
Use a combination of an LFSR and a shift register (SR) for pattern
generation. The method is most effective when w is much less than n. In
general, this technique requires much more tests than other schemes
when w is greater than n/2.

A 4-stage combined
X1 X2 X3 X4 LFSR/SR

42
EE141
 Combined LFSR/PS
A combined LFSR/PS approach using a combination of an LFSR
and a linear phase shifter which includes a network of XOR gates to
generate test pattern. Similar to combined LFSR/SR, this technique
requires more tests than other schemes when w is greater than n/2.

X1 X2 X3

A 3-stage combined
X1 X2 X3
LFSR/PS

X4

43
EE141
 Segmentation Testing
D Usedwhen
• Test length using previous techniques is too long
or
• Output depends on all inputs.
D Divide the circuit intosegments
• Hardware partitioning
• Sensitized partitioning

49
EE141
 Output Response Analysis
D Ones counttesting
D Transition counttesting
D Signatureanalysis

51
EE141
 Ones Count Testing
Assume the CUT has one output and the output contains a
stream of L bits. Let the fault-free output response be

{r0 , r1, r2 ... r L  1 }

Ones count testing will need a counter to count the number of 1s

in the bit stream.

Aliasing probability

POC (m)  (C(L, m) 1) /(2L 1)

52
EE141
 One Count Testing

T Signature
CUT
Counter

CLK

One counter as ORA

53
EE141
 Transition Count Testing
Transition count testing is similar to that for ones count testing,
except the signature is defined as the number of 1-to-0 and
0-to-1 transitions.

Aliasing probability

PTC (m)  (2C(L 1, m) 1) /(2L 1)

54
EE141
 Transition Count Testing

ri
ri-1
T CUT Counter Signature
D Q

CLK

Transition counter as ORA

55
EE141
 Signature Analysis
Signature analysis is the most popular compaction technique
used today, based on cyclic redundancy checking.

Two signature analysis schemes

• Serial signature analysis
• Parallel signature analysis

56
EE141
 Serial Signature Analysis
An n-stage single-input signature
register
h1 h2 hn-2 hn-1

M r0 r1 rn-2 rn-1

Define L-bit output sequence M

M (x)  m 0  m 1x  m 2x ...  m L1
x L1

Let the polynomial of the modular be f(x)

Signature is the
IF M (x)  q(x) f (x)  r(x)
polynomial remainder, r(x)

57
EE141