Lecture 25 Lecture 25 Built-In Self-Testing Built-In Self-Testing Pattern Generation Pattern Generation and Response and Response Compaction

Compaction s Motivation and economics

s s s s s s
April 6, 2001

Definitions Built-in self-testing (BIST) process BIST pattern generation (PG) BIST response compaction (RC) Aliasing probability Example VLSI Test: Bushnell-Agrawal/Lecture 25 Summary

BIST Motivation BIST Motivation

Useful for field test and diagnosis (less expensive than a local automatic test equipment) s Software tests for field test and diagnosis: Low hardware fault coverage Low diagnostic resolution Slow to operate s Hardware BIST benefits: Lower system test effort Improved system maintenance and repair Improved component repair April 6, 2001 Better diagnosis VLSI Test: Bushnell-Agrawal/Lecture 25
s

Costly Test Problems Costly Test Problems Alleviated by BIST Alleviated by BIST
s s s s s s

Increasing chip logic-to-pin ratio harder observability Increasingly dense devices and faster clocks Increasing test generation and application times Increasing size of test vectors stored in ATE Expensive ATE needed for 1 GHz clocking chips Hard testability insertion designers unfamiliar with gate-level logic, since they design at behavioral level April 6, 2001 VLSI Test: Bushnell-Agrawal/Lecture 25 3 In-circuit testing no longer technically

Typical Quality Typical Quality Requirements Requirements

s

98% single stuck-at fault coverage 100% interconnect fault coverage Reject ratio 1 in 100,000

April 6, 2001

VLSI Test: Bushnell-Agrawal/Lecture 25

Benefits Benefits BIST BIST

Level Chips Boards System + / + / + / + + + -

and Costs of and Costs of with DFT with DFT

Design Fabri- Manuf.Maintenance Diagnosis Service and test cation Test and repair interruption test

+ +/April 6, 2001

Cost increase Cost saving Cost increase may balance cost reduction
VLSI Test: Bushnell-Agrawal/Lecture 25 5

Economics BIST Costs Economics BIST Costs

area overhead for: s Test controller s Hardware pattern generator s Hardware response compacter s Testing of BIST hardware Pin overhead -- At least 1 pin needed to activate BIST operation Performance overhead extra path delays due to BIST Yield loss due to increased chip area or more chips In system because of BIST Reliability reduction due to increased area Increased BIST hardware complexity April 6, 2001 VLSI 6 happens when Test: Bushnell-Agrawal/Lecture 25 BIST hardware is made

Chip

Faults tested: Single combinational / sequential stuck-at faults Delay faults Single stuck-at faults in BIST hardware BIST benefits Reduced testing and maintenance cost Lower test generation cost Reduced storage / maintenance of test patterns Simpler and less expensive ATE Can test many units in parallel Shorter test application times Can test at functional system speed April 6, 2001 VLSI Test: Bushnell-Agrawal/Lecture 25 7

BIST Benefits BIST Benefits

Definitions Definitions
s

s s

BILBO Built-in logic block observer , extra hardware added to flip-flops so they can be reconfigured as an LFSR pattern generator or response compacter, a scan chain, or as flip-flops Concurrent testing Testing process that detects faults during normal system operation CUT Circuit-under-test

Exhaustive testing Apply all possible 2 n patterns to a circuit with n inputs s Irreducible polynomial Boolean polynomial that cannot be factored s LFSR Linear feedback shift register, April 6, 2001 VLSI Test: Bushnell-Agrawal/Lecture 25 hardware that generates pseudo-random

More Definitions More Definitions

Primitive polynomial Boolean polynomial p (x) that can be used to compute increasing powers n of x n modulo p (x) to obtain all possible nonzero polynomials of degree less than p (x) s Pseudo-exhaustive testing Break circuit into small, overlapping blocks and test each exhaustively s Pseudo-random testing Algorithmic pattern generator that produces a subset of all possible tests with most of the properties of randomly-generated patterns s Signature Any statistical circuit April 6, 2001 VLSI Test: Bushnell-Agrawal/Lecture 25 9 property distinguishing between bad
s

BIST Process BIST Process

April 6, 2001

Test controller Hardware that activates self-test simultaneously on all PCBs Each board controller activates parallel chip BIST Diagnosis effective only if very high fault coverage
VLSI Test: Bushnell-Agrawal/Lecture 25

10

BIST Architecture BIST Architecture

Note: BIST cannot test wires and transistors: From PI pins to Input MUX From POs to output pins
VLSI Test: Bushnell-Agrawal/Lecture 25 11

April 6, 2001

BILBO Works as BILBO Works as Both a PG and a RC Both a PG and a RC

Built-in Logic Block Observer (BILBO) -- 4 modes: 1. Flip-flop 2. LFSR pattern generator 3. LFSR response compacter 4. Scan chain VLSI Test: Bushnell-Agrawal/Lecture 25 for flip-flops April 6, 2001

12

Complex BIST Complex BIST Architecture Architecture

Testing epoch I: LFSR1 generates tests for CUT1 and CUT2 BILBO2 (LFSR3) compacts CUT1 (CUT2) s Testing epoch II: BILBO2 generates test patterns for April 6, 2001 VLSI Test: Bushnell-Agrawal/Lecture 25
s

13

Bus-Based BIST Bus-Based BIST Architecture Architecture

Self-test control broadcasts patterns to each CUT over bus parallel pattern generation s Awaits bus transactions showing CUTs responses to the patterns: serialized April 6, 2001 VLSI Test: Bushnell-Agrawal/Lecture 25
s

14

Pattern Generation Pattern Generation

Store in ROM too expensive s Exhaustive s Pseudo-exhaustive s Pseudo-random (LFSR) Preferred method s Binary counters use more hardware than LFSR s Modified counters s Test pattern augmentation LFSR combined with a few patterns in ROM Hardware diffracter generates pattern cluster in neighborhood of April 6, 2001 VLSI Test: in ROM 15 pattern stored Bushnell-Agrawal/Lecture 25
s

Exhaustive Pattern Exhaustive Pattern Generation Generation

Shows that every state and transition works

16

For n -input circuits, requires all 2 n April 6, 2001 VLSI Test: Bushnell-Agrawal/Lecture 25 vectors
s

Pseudo-Exhaustive Pseudo-Exhaustive Method Method

s

Partition large circuit into fanin cones Backtrace from each PO to PIs influencing it Test fanin cones in parallel Reduced # of tests from 2 8 = 256 to 2 5 x 2 = 64 Incomplete fault coverage
VLSI Test: Bushnell-Agrawal/Lecture 25 17

April 6, 2001

Pseudo-Exhaustive Pseudo-Exhaustive Pattern Generation Pattern Generation

April 6, 2001

VLSI Test: Bushnell-Agrawal/Lecture 25

18

Random Pattern Random Pattern Testing Testing

Bottom: RandomPattern Resistant circuit

April 6, 2001

VLSI Test: Bushnell-Agrawal/Lecture 25

19

Pseudo-Random Pseudo-Random Pattern Generation Pattern Generation

Standard Linear Feedback Shift Register (LFSR) Produces patterns algorithmically repeatable Has most of desirable random # properties VLSI Test: Bushnell-Agrawal/Lecture 25 April 6, 2001

20

Matrix Equation for Matrix Equation for Standard LFSR Standard LFSR
X 0 ( t + 1) X 1 ( t + 1) . = . . X n -3 ( t + 1) X n -2 ( t + 1)
0 0 . . . 0 0 1 1 0 . . . 0 0 0 1 . . . 0 0 0 0 . . . 1 0 0 0 . . . 0 1

X0 (t) X1 (t) . . . X n -3 ( t ) X n -2 ( t )

h1 h2

h n -2 h n -1

X n -1 ( t + 1) X ( t + 1) = T s X ( t )
April 6, 2001

X n -1 ( t ) ( T s is companion matrix )
21

VLSI Test: Bushnell-Agrawal/Lecture 25

Galois field (mathematical system): Multiplication by x same as right shift of LFSR Addition operator is XOR ( ) T s companion matrix: 1 st column 0, except n th element which is always 1 ( X 0 always feeds X n -1 )
Rest of row n feedback coefficients h i Rest is identity matrix I means a right shift Near-exhaustive (maximal length) LFSR
VLSI Test: Bushnell-Agrawal/Lecture 25

LFSR Implements a LFSR Implements a Galois Field Galois Field

April 6, 2001

22

Standard n -Stage Standard n -Stage LFSR Implementation LFSR Implementation

Autocorrelation any shifted sequence same as original in 2 n -1 1 bits, differs in

2 n -1 bits
VLSI Test: Bushnell-Agrawal/Lecture 25 23

April 6, 2001

LFSR Theory LFSR Theory

s s

Cannot initialize to all 0s hangs If X is initial state, progresses through states X , T s X , T s 2 X , T s 3 X ,

Matrix period :
Smallest k such that T s k = I k LFSR cycle length

Described by characteristic polynomial:

April 6, 2001

f (x) = |Ts I X |

VLSI Test: Bushnell-Agrawal/Lecture 25

24

Fault detection probability by a random number p ( x ) dx = fraction of detectable faults with detection probability between x and 1 x + dx p ( x ) dx 0 when 0 x 1 0

LFSR Fault Coverage LFSR Fault Coverage Projection Projection

p ( x ) dx = 1

s s

Exist p ( x ) dx faults with detection probability1 x Mean coverage of those faults n x p ( x ) dx is 0 Mean fault coverage y n oftotal faults 1 st n vectors:
VLSI Test: Bushnell-Agrawal/Lecture 25

April 6, 2001

25

LFSR Fault Coverage & LFSR Fault Coverage & Vector Length Vector Length Estimation s Random-fault-detection (RFD) variable: Estimation
s

Vector # at which fault first detected w i # faults with RFD variable i N 1 So p ( x ) = wi pi (x) i = 1 ns

ns size N sample simulated; N of vectors i = 1 w0 ns -

# test

s s

Method: Estimate random first detect variables w i from fault simulator using fault sampling April 6, 2001 VLSI Test: Bushnell-Agrawal/Lecture 25

wi

26

Example External Example External XOR LFSR XOR LFSR

Characteristic polynomial f ( x ) = 1 + x + x3 (read taps VLSI Test: Bushnell-Agrawal/Lecture 25 from right to left) April 6, 2001
s

27

External XOR LFSR External XOR LFSR

s

Pattern sequence (earlier): 1 0 X0 0 0 X1 0 1

for example LFSR 0 1 0 1 1 1 0 1 0 1 1 1 0 0 0 1 1 1 0 0 1

X2
s s

Always have 1 and x n terms in polynomial Never repeat an LFSR pattern more than 1 time Repeats 1) 0 1 0 X 0 ( t + same error vector, ) cancels X0 (t fault effect = 0 0 1 X 1 ( t + 1) X1 (t) 1 1 0
April 6, 2001

X 2 ( t + VLSI Test: Bushnell-Agrawal/Lecture 25 2 ( t ) 1) X

28

Generic Modular Generic Modular LFSR LFSR

April 6, 2001

VLSI Test: Bushnell-Agrawal/Lecture 25

29

Modular Internal XOR Modular Internal XOR LFSR LFSR

s
T

Described by companion matrix T m = T s Internal XOR LFSR XOR gates in between D flip-flops Equivalent to standard External XOR LFSR With a different state assignment Faster usually does not matter Same amount of hardware

s s

s s

X ( t + 1) = T m x X (t) f (x) = | Tm I X |
n

April 6, 2001

= 1 + h 1 x + h 2 x 2 + + h n -1 x n -1 + VLSI Test: Bushnell-Agrawal/Lecture 25

30

Modular LFSR Matrix Modular LFSR Matrix

X 0 ( t + 1) X 1 ( t + 1) X 2 ( t + 1) = . . . X n -3 ( t + 1) X n -2 ( t + 1) X n -1 ( t + 1)
April 6, 2001 VLSI Test: Bushnell-Agrawal/Lecture 25

0 1 0 . . . 0 0 0

0 0 1 . . . 0 0 0

0 0 0 . . . 0 0 0

0 0 0 . . . 0 1 0

1 0 0 h1 0 h2 . . . . . . 0 h n -3 0 h n -2 1 h n -1

X0 (t) X1 (t) X2 (t) . . . X n -3 ( t ) X n -2 ( t ) X n -1 ( t )

31

Example Modular Example Modular LFSR LFSR

s s

f (x) = 1 + x2 + x7 + x8 Read LFSR tap coefficients from left to right

VLSI Test: Bushnell-Agrawal/Lecture 25 32

April 6, 2001

Want LFSR to generate all possible 2 n 1 patterns (except the all-0 pattern) Conditions for this must have a primitive polynomial :

Primitive Primitive Polynomials Polynomials

Monic coefficient of x n term must be 1

s Modular

LFSR all D FFs must right

shift through XORs from X 0 through

X 1 , , through X n -1 , which must feed

back directly to X 0
s Standard
April 6, 2001

LFSR all D FFs must right

33

shift directly Bushnell-Agrawal/Lecture 25 VLSI Test: from X n -1 through X n -2 ,

Characteristic polynomial must

Primitive Primitive Polynomials Polynomials (continued) (continued)

2 n 1, but not for any smaller k value See Appendix B of book for tables of primitive polynomials s If p ( error ) = 0.5, no difference between behavior of primitive & nonprimitive polynomial s But p ( error ) is rarely = 0.5 In that case, non-primitive polynomial LFSR takes muchVLSI Test: Bushnell-Agrawal/Lecture 25 longer to stabilize with April 6, 2001

divide the polynomial 1 + x k for k =

34

Weighted PseudoWeighted PseudoRandom Pattern Random Pattern Generation Generation s-a-0

F f If p (1) at all PIs is 0.5, p F (1) = 0.5 = 256 1 255 p F (0) = 1 256 =256 s Will need enormous # of random patterns to test a stuck-at 0 fault on F -- LFSR p (1) = 0.5 We must not use an ordinary LFSR to test this s IBM holds patents on weighted pseudoApril 6, 2001 VLSI Test: Bushnell-Agrawal/Lecture 25 35 random pattern generator in ATE
s

1 8

Weighted PseudoWeighted PseudoRandom Pattern Random Pattern Generator Generator

s s

LFSR p (1) = 0.5 Solution: Add programmable weight selection and complement LFSR bits to get p (1)s other than 0.5 Need 2-3 weight sets for a typical circuit Weighted pattern generator drastically shortens pattern length for pseudorandom patterns
VLSI Test: Bushnell-Agrawal/Lecture 25 36

April 6, 2001

Weighted Pattern Weighted Pattern Gen. Gen.

w 1 w 2 Inv . p ( output ) w 1 w 2 Inv p ( output ) . 0 1/8 0 0 1 0 0 1 7/8 0 0 1 0 0 1 1/16 0 1 1 1 0 1 3/4 15/16 0 1 1 April 6, 2001 1 VLSI Test: Bushnell-Agrawal/Lecture 25 37 1

Cellular Automata Cellular Automata (CA) (CA) Superior to LFSR even more random

No shift-induced bit value correlation Can make LFSR more random with linear phase shifter Regular connections each cell only connects to local neighbors Gives CA cell connections 110 101 100 011 010 1 0 1 1 0

x c -1 ( t ) x c ( t ) x c +1 ( t )

001 000
s

111

x c ( t + 1) 0 1 0
April 6, 2001

VLSI Test: Bushnell-Agrawal/Lecture 25

38

Cellular Automaton Cellular Automaton

s s

Five-stage hybrid cellular automaton Rule 150: x c ( t + 1) = x c -1t ) ( x c +1 ( t )

VLSI Test: Bushnell-Agrawal/Lecture 25

xc (t)

Alternate Rule 90 and Rule 150 CA

39

April 6, 2001

SAF coverage Add a small ROM with missing test patterns Add extra circuit mode to Input MUX shift to ROM patterns after LFSR done Important to compact extra test patterns s Use diffracter : Generates cluster of patterns in neighborhood of stored ROM pattern s Transform LFSR patterns into new vector set s Put LFSR and transformation hardware April 6, 2001 VLSI Test: Bushnell-Agrawal/Lecture 25 40 in full-scan chain

Test Pattern Test Pattern Augmentation Augmentation 100% Secondary ROM to get LFSR to

Response Response Compaction Compaction

s

Severe amounts of data in CUT response to LFSR patterns example: Generate 5 million random patterns CUT has 200 outputs Leads to: 5 million x 200 = 1 billion bits response Uneconomical to store and check all of these responses on chip Responses must be compacted

April 6, 2001

VLSI Test: Bushnell-Agrawal/Lecture 25

41

Definitions Definitions
Aliasing Due to information loss, signatures of good and some bad machines match s Compaction Drastically reduce # bits in original circuit response lose information s Compression Reduce # bits in original circuit response no information loss fully invertible (can get back original response) s Signature analysis Compact good machine response into good machine signature . Actual signature generated during testing, and compared with good machine signature April 6, 2001 VLSI Test: Bushnell-Agrawal/Lecture 25
s

42

Transition Counting Transition Counting

April 6, 2001

VLSI Test: Bushnell-Agrawal/Lecture 25

43

Transition Counting Transition Counting Details Details

s

Transition count:
m

C (R) = i
outputs
s

= 1

(r
i

r i -1 ) for all m primary

To maximize fault coverage: Make C ( R 0) good machine transition count as large or as small as possible
VLSI Test: Bushnell-Agrawal/Lecture 25 44

April 6, 2001

Use cyclic redundancy check code (CRCC) generator (LFSR) for response compacter s Treat data bits from circuit POs to be compacted as a decreasing order coefficient polynomial s CRCC divides the PO polynomial by its characteristic polynomial Leaves remainder of division in LFSR Must initialize LFSR to seed value (usually 0) before testing s After testing compare signature in LFSR to known good machine signature VLSI Test: Bushnell-Agrawal/Lecture 45 s April 6, 2001 Critical: Must compute good25 machine
s

LFSR for Response LFSR for Response Compaction Compaction

Example Modular Example Modular LFSR Response LFSR Response Compacter Compacter

s
April 6, 2001

LFSR seed value is 00000

VLSI Test: Bushnell-Agrawal/Lecture 25 46

Polynomial Division Polynomial Division

Inputs X0 Initial State 0 1 1 0 0 0 Logic 0 0 Simulation: 0 1 1 0 1 1 1 0 1

X1 0 0 1 0 0 0 0 1 0

X2 0 0 0 1 0 0 0 0 1

X3 0 0 0 0 1 0 1 0 1

X4 0 0 0 0 0 1 0 1 0

Logic simulation: Remainder = 1 + x 2 + x 3 0 . 1 0 1 .0 0. 0 1 . . . . . 0 x0 + 1 x1 + 0 x2 + 1 x3 + 0 x4 + 0 x5 +

April 6, 2001 6

0 x

+ 1 x7

VLSI Test: Bushnell-Agrawal/Lecture 25

47

Symbolic Polynomial Symbolic Polynomial Division Division

x5 + x3 + x + 1 x2 + 1 x
7

x7 remainder

+ x5 + x3 + x2

+ x3

+ x + x + x+ 1 + 1

x5 x5 + x3
3

+ x2

+ x2 x Remainder matches that from logic simulation of the response compacter!

April 6, 2001 VLSI Test: Bushnell-Agrawal/Lecture 25 48

compacter: Too much hardware if one of these is put on each primary output (PO) s Solution: MISR compacts all outputs into one LFSR Works because LFSR is linear obeys superposition principle Superimpose all responses in one LFSR final remainder is XOR sum of remainders of polynomial divisions of each PO by the characteristic April 6, 2001 49 polynomial VLSI Test: Bushnell-Agrawal/Lecture 25

Multiple-Input Multiple-Input Signature Register Signature Register (MISR) (MISR) response Problem with ordinary LFSR

MISR Matrix Equation MISR Matrix Equation

s

d i ( t ) output response on PO i at time t

0 1 0 0 0 0 . . . . . . . . . 0 0 1 0 0 0 1 h1 h 0 0 . . . 0 1

X 0 ( t + 1) X 1 ( t + 1) . . = . X n -3 ( t + 1) X n -2 ( t + 1) X n -1 ( t + 1)
April 6, 2001

X0 (t)

d0 (t)

n -2

h n -1

X1 (t) d1 (t) . . . . . . + X n -3 ( t ) d n -3 ( t ) X n -2 ( t ) X n -1 ( t ) d n -2 ( t ) d n -1 ( t )
50

VLSI Test: Bushnell-Agrawal/Lecture 25

Modular MISR Modular MISR Example Example

X 0 ( t + 1) X 1 ( t + 1)
April 6, 2001

0 0 1 1 0 1 0 1 0

X0 (t) X1 (t) X2 (t)

d0 (t) d1 (t) d2 (t)

51

X 2 ( t + 1)

VLSI Test: Bushnell-Agrawal/Lecture 25

Use 2 different testing epochs: 1 st with MISR with 1 polynomial 2 nd with MISR with different polynomial Reduces probability of aliasing Very unlikely that both polynomials will alias for the same fault Low hardware cost: A few XOR gates for the 2 nd MISR polynomial A 2-1 MUX to select between two feedback polynomials
VLSI Test: Bushnell-Agrawal/Lecture 25 52

Multiple Signature Multiple Signature Checking Checking

April 6, 2001

Aliasing Probability Aliasing Probability

s s

Aliasing when bad machine signature equals good machine signature Consider error vector e ( n ) at POs Set to a 1 when good and faulty machines differ at the PO at time t

s s s

P al

p probability of 1 in e ( n ) Aliasing limits:

0 < p

aliasing probability

, 1,

P al

(1 p ) k

April 6, 2001

VLSI Test: Bushnell-Agrawal/Lecture 25

(1 p ) k

P al

pk

53

Aliasing Probability Aliasing Probability Graph Graph

April 6, 2001

VLSI Test: Bushnell-Agrawal/Lecture 25

54

Additional MISR Additional MISR Aliasing Aliasing

s

MISR has more aliasing than LFSR on single PO Error in CUT output d j at t i , followed by error in output d j+h at t i+h , eliminates any signature error if no feedback tap in MISR between bits Q j and Q j+h .

April 6, 2001

VLSI Test: Bushnell-Agrawal/Lecture 25

55

Aliasing Theorems Aliasing Theorems

s

Theorem 15.1 : Assuming that each circuit

PO d ij has probability p of being in error, and that all outputs d ij are independent, in a k -bit MISR, true in practice.

P al = 1/(2 k ), regardless of
Not exactly true

initial condition of MISR.

Theorem 15.2 : Assuming that each PO d ij

has probability p j of being in error, where
April 6, 2001

the p probabilities are independent, and

VLSI Test: Bushnell-Agrawal/Lecture 25

56

Experiment Hardware Experiment Hardware

3 bit exhaustive binary counter for pattern generator VLSI Test: Bushnell-Agrawal/Lecture 25 April 6, 2001
s

57

Transition Counting vs. Transition Counting vs. LFSR LFSR s LFSR aliases for f sa1, transition
counter for a sa1

Responses Good a sa1 f sa1 b sa1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 Signatures 0 1 3 Transition Count 3 001 001 010 101 LFSR Pattern abc 000 001 010 011 100 101 110 111
April 6, 2001 VLSI Test: Bushnell-Agrawal/Lecture 25 58

Summary Summary
LFSR pattern generator and MISR response compacter preferred BIST methods s BIST has overheads: test controller, extra circuit delay, Input MUX, pattern generator, response compacter, DFT to initialize circuit & test the test hardware s BIST benefits: At-speed testing for delay & stuck-at faults Drastic ATE cost reduction Field test capability Faster diagnosis during system test Less effort to design testing process Shorter test application times April 6, 2001 VLSI Test: Bushnell-Agrawal/Lecture 25 59
s