BIST Part1 - TPG

 Introduction
 Test Pattern Generation (TPG)
 Deterministic: ROM, Algorithm, Counter
 Pseudo Random
 Linear Feedback Shift Register, LFSR (1977)
 Two types of LFSR

 Design of LFSR

 How to find seed?

 What polynomial?
 All-zero pattern?
 What is LFSR degree?
Q: Given two LFSR of x4+x3+1, x4+x2+1. seed=1000. Fill in table. Lc=?
+ +
Q3 Q2 Q1 Q0 Q3 Q2 Q1 Q0

state Q3 Q2 Q1 Q0 state Q3 Q2 Q1 Q0
0 1 0 0 0 0 1 0 0 0
1 1 1 0 0 1 0 1 0 0
2 1 1 1 0 2 1 0 1 0
3 1 1 1 1 3 0 1 0 1
4 0 1 1 1 4 0 0 1 0
5 1 0 1 1 5 0 0 0 1
6 0 1 0 1 6 1 0 0 0
7 1 0 1 0 7
Lc=15 8 1 1 0 1 8
Lc=6! Lc=?
9 0 1 1 0 9
10 0 0 1 1 10
11 1 0 0 1 11
12 0 1 0 0 12
13 0 0 1 0 13
14 0 0 0 1 14
15 (=0) 1 0 0 0 15
 Polynomial and Lc
x4+x3+1 x4+x2+1

LC=6

LC=15
LC=6

LC=3

Larger Lc , Better TPG

 Primitive Polynomial
 Primitive polynomial (PP) generates
maximum-length sequence N primitive polynomial f (X)
1,2,3,4,6,7,15,22 1 + X + XN
 Lc = 2N-1, N=degree of PP
5,11,21,29 1 + X2 + XN
10,17,20,25,28,31 1 + X3 + XN
9 1 + X4 + XN
23 1 + X5 + XN
18 1 + X7 + XN
8 1 + X2 + X3 + X4 + XN
12 1 + X + X2 + X4 + XN
13 1 + X + X3 + X4 + XN
14,16 1 + X3 + X4 + X5 + XN
19,27 1 + X + X2 + X5 + XN
24 1 + X + X2 + X7 + XN
26 1 + X + X2 + X6 + XN
30 1 + X + X2 + X23 + XN
32 1 + X + X2 + X22 + XN

PP Often Used to Design TPG

Q: Compare two PP x4+x3+1, x4+x+1. Fill in table. Lc=?
+ +
Q3 Q2 Q1 Q0 Q3 Q2 Q1 Q0

state Q3 Q2 Q1 Q0 state Q3 Q2 Q1 Q0
0 1 0 0 0 0 1 0 0 0
1 1 1 0 0 1 0 1 0 0
2 1 1 1 0 2 0 0 1 0
3 1 1 1 1 3 1 0 0 1
4 0 1 1 1 4 1 1 0 0
5 1 0 1 1 5 0 1 1 0
6 0 1 0 1 6 1 0 1 1
7 1 0 1 0 7 0 1 0 1
Lc=15 8 1 1 0 1 8 1 0 1 0 Lc=?
9 0 1 1 0 9 1 1 0 1
10 0 0 1 1 10 1 1 1 0
11 1 0 0 1 11 1 1 1 1
12 0 1 0 0 12 0 1 1 1
13 0 0 1 0 13 0 0 1 1
14 0 0 0 1 14 0 0 0 1
15 (=0) 1 0 0 0 15 (=0) 1 0 0 0
 BIST Part1 - TPG
 Introduction
 Test Pattern Generation (TPG)
 Deterministic: ROM, Algorithm, Counter
 Pseudo Random
 Linear Feedback Shift Register, LFSR (1977)
 Two types of LFSR

 Design of LFSR

 How to find seed?

 What polynomial?
 All-zero pattern?
 What is LFSR degree?
 State Diagram

f(x) = x4 + x3 + 1 0000
1000 0001
1100
0010

1110 0100

1111
What if we want
1001
all-zero in cycle?
0111 0011

1011 0110
0101 1101
1010
 Exhaustive Feedback Shift Register
 Exhaustive feedback Shift Register (aka. De Bruijn Counter)
 2N different states
 Example: N=4; 16 exhaustive states
 0001 0000 1000

+
Q3 Q2 Q1 Q0

 NOTE: This is NOT LFSR because AND is nonlinear

DB Counter Generates All-zero Patterns

 BIST Part1 - TPG
 Introduction
 Test Pattern Generation (TPG)
 Deterministic: ROM, Algorithm, Counter
 Pseudo Random
 Linear Feedback Shift Register, LFSR (1977)
 Two types of LFSR

 Design of LFSR

 How to find seed?

 What polynomial?
 All-zero pattern?
 What is LFSR degree?
 What is LFSR Degree? *not in exam

 Suppose N-degree LFSR, S care bits (i.e. specified bits)

 N variables, S equations
 What is minimum N to guarantee a solution (seed) can be found?

LFSR Degree N  (S + 20)

 Pros and Cons of LFSR
 Advantages state Q0 Q1 Q2 Q3
 Small area. 0 1 0 0 0
 Easy to design: PP  structure 1 0 1 0 0
2 0 0 1 0

3 0 0 0 1
 Disadvantages 4 1 1 0 0
 Not enough randomness 5 0 1 1 0
6 0 0 1 1
 Large LFSR has many tap points. too slow! 7 1 1 0 1
8 1 0 1 0
9 0 1 0 1
10 1 1 1 0
+ 11 0 1 1 1
Q7 Q6 Q5 Q4 Q3 Q2 Q1 Q0 12 1 1 1 1
13 1 0 1 1
f(x) = x8 +x4 + x3 + x2 + 1 14 1 0 0 1

1 1
LFSR Is Most Popular TPG
Logic Built-In Self Test (BIST)
Part 2: ORA, BIST Architecture*
 BIST Part 2
 Part 1
 Introduction
 Test Pattern Generation
 Part 2
 Output Response Analysis
 BIST Architecture
 Issues with BIST
 Conclusions
 Output Response Analyzer
 What is ORA?
Compress CUT output responses into a small signature
 Compare signature with gold signature to determine pass or fail
 ORA also called signature analyzer
 What is good ORA? (very difficult to meet all requirements)
 1. Signature as small as possible
 2. Correct Pass/Fail decision (i.e. low aliasing, see next slide)
 3. Small area
 4. Diagnosis support

output
Test responses signature Pass/fail
Pattern CUT ?
ORA =
Generator
Gold
signature
 Aliasing
 Aliasing occurs when
 signaturefaulty output = signaturegood output (gold signature)
 Aliasing  Fault coverage loss  Test escapes
 Defective circuits pass tests (Very bad!)

Many-to-one
Output Space mapping Signature Space
Faulty output

Faulty output

No aliasing Bad signatures

Faulty output

Good output Gold signature

Faulty output Aliasing

 Probability of Aliasing
 Aliasing depends on many factors:
 CUT, faults, test pattern, ORA structure
 Exact analysis of aliasing difficult
 Just probability analysis is good enough
 Probability of Aliasing (PAL)

number of faulty outputs that generate gold signature

PAL 
total number of faulty outputs

 PAL between 0 and 1. Lower is better.

Good ORA Requires Low PAL

Q1: We use XOR gate as ORA. Suppose good output is ’01’, what is
gold signature?
ANS:

Q2: What is PAL of this ORA? Suppose ‘00, 01 10, 11’ equally likely
number of faulty outputs that generate gold signature
PAL 
total number of faulty outputs
ANS:

CUT
1
 BIST Part 2
 Output Response Analysis
 Simple ORA
 Duplication, Reverse operation

 LFSR-based
 BIST Architecture
 Issues with BIST
 Conclusions
 Duplication
 Advantage: low aliasing; good for on-line BIST
 Disadvantages: too big in area

Courtesy of McCluskey, Stanford University

 Reverse Operation
 Advantages
 Applicable to both on-line and off-line BIST
 Low aliasing
 Disadvantages
 Not generally applicable to all CUT

output
test patterns
CUT
F

Good/faulty
=? F-1

F-1 is reverse operation of F

 BIST Part 2
 Output Response Analysis
 Simple ORA
 LFSR-based ORA
 Serial : compress one bit at a time

 Parallel : compress multiple bits at a time

 BIST Architecture
 Issues with BIST
 Conclusions
 LFSR (Review)
 LFSR consist of FF and feedback XOR
 Two applications of LFSR:
 1. LFSR without external input
 Used for TPG

+
FF FF FF FF CUT

 2. LFSR with external input

 Used for ORA

+
CUT + FF FF FF FF
 LFSR as ORA
(from CUT) LFSR Output
LFSR Input 11001
011011011 Right bit first
9 bits, right bit first + Q0 Q1 Q2 + Q3
not used for BIST

cycle LFSR input Q0 Q1 Q2 Q3 LFSR output

0 011011011 0 0 0 0
1-3 …
4 01101 1 0 1 1
5 0110 0 1 0 0 1
6 011 0 0 1 0 01
7 01 1 0 0 1 001
8 0 0 1 0 1 1001
9 1 0 1 1 11001

signature not used

Q: Suppose CUT output is ‘001001’. (right bit first)
What is the signature after 6 cycles?
ANS:

LFSR Input
(from CUT)
001001 + Q0 Q1 Q2 + Q3

cycle LFSR input Q0 Q1 Q2 Q3 LFSR output

0 001001 0 0 0 0
1-3 …
4 00 1 0 0 1
5 0 1 1 0 1 1
6 1 1 1 1 11
 BIST Part 2
 Output Response Analysis
 Simple ORA
 LFSR-based ORA
 Serial : compress one bit at a time
 Parallel : compress multiple bits at a time
 MISR

 BIST Architecture
 Issues with BIST
 Conclusions
 Parallel ORA
 Serial ORA only compress one CUT output
 How about multiple CUT outputs?
 One LFSR for each CUT output? CUT LFSR
 Too much hardware overhead!

LFSR

LFSR
CUT
LFSR

LFSR

Any Better Idea?

Multiple Input Signature Register, MISR
 MISR has similar structure to LFSR, except
 Parallel inputs feed XOR between stages
 MISR characteristic polynomial same as LFSR
 Example: MISR with 4 parallel inputs
 Modified from type-2 LFSR
 f(x) = x4+x3+1
CUT + Q0 Q1 Q2 + Q3

CUT

+ Q0 + Q1 + Q2 + Q3
 What is MISR Signature?
010110 010111 010110 011011
Right bit first

+ Q0 + Q1 + Q2 + Q3

cycle Q0 Q1 Q2 Q3
0 0 0 0 0 initial state
1 0 1 0 1
2 0 1 0 0
3 1 1 0 0
4 0 1 1 1
5 0 1 0 1
6 1 0 1 1 signature

Too Slow!
 Equivalent LFSR
 Change MISR to equivalent LFSR
 Just phase shift and add many input bit streams

Right bit first

010110 010111 010110 011011

+ Q0 + Q1 + Q2 + Q3

f(x) = 1+x3+x4
MISR

011011
010110
010111
+ 010110
011011011 + Q0 Q1 Q2 + Q3

f(x) = 1+x3+x4

Equivalent LFSR
Q: Given same example. The first bit of rightmost ‘1’ is flipped to ‘0’
Find equivalent LFSR and associated input bit stream

010110 010111 010110 X

011011

+ Q0 + Q1 + Q2 + Q3

011011
010110
010111
+ 010110
011011011 + Q0 Q1 Q2 + Q3
x + x2 + x4 + x5 + x7+ x8

(x+x2+x4+x5+x7)  (1+x3+x4) = 1+x2+x3 ….. 1+x 1100

 BIST Part 2
 Output Response Analysis
 BIST Architecture
 Test Per Clock
 BILBO
 Test Per Scan
 STUMPS
 Issues with BIST
 Conclusions
 BIST Architectures
 Classified by hardware
 Separate BIST
 TPG/ORA outside of CUT
 Embedded BIST
 Reuse CUT’s FF/latches as TPG/ORA

 Classified by clocking scheme

 Test-per-Clock
 Apply a test every clock cycle
 Test-per-Scan
 Apply a test in between scan in/out
 Test Per Clock – Combinational CUT
 Separate BIST
 Test per clock
 At each clock: apply a test pattern, observe output

L M
F PIs CUT POs I
S Combinational Logic S
R R

How about Sequential CUT?

 Test Per Clock – Sequential CUT
 BILBO = Built-in Logic Block Observer
Serve as TPG and ORA
CUT
 When testing C1
 BILBO1 is TPG, BILBO2 is ORA BILBO1
 When testing C2
 BILBO2 is TPG, BILBO3 is ORA
C1

 When testing C3 BILBO2

 BILBO3 is TPG; BILBO1 is ORA
C2
 Embedded BIST BILBO3
 Reuse CUT’s FF as BILBO
C3

Yellow blocks are comb. logic

 Built-in Logic Block Observer, BILBO
 B1 B2 control four modes of operation
D1 D2 Dn-1 Dn

B1 ...
...
B2

...

D Q SO
SI MUX D Q D Q D Q
0 CLK CLK CLK CLK
1
Clock

... ...
Qn
Q1 Q2 Qn-1

B1 B2 operation mode
0 0 shift register (scan chain)
1 0 normal operation
1 1 MISR (ORA)
0 1 LFSR (TPG)
 Normal Operation Mode
 B1=1, B2=0

D1 D2 Dn-1 Dn

B1 ...
...
B2

...

D Q SO
SI MUX D Q D Q D Q
0 CLK CLK CLK CLK
1
Clock

... ...
Q1 Q2 Qn-1
 Scan Chain Mode
 B1=B2=0
D1 D2 Dn-1 Dn

B1 ...
...
B2

...

D Q SO
SI MUX D Q D Q D Q
0 CLK CLK CLK CLK
1
Clock

... ...
Qn
Q1 Q2 Qn-1
 LFSR Mode
 B1=0, B2=1
 Type 1 LFSR
D1 D2 Dn-1 Dn

B1 ...
...
B2

...

D Q SO
SI MUX D Q D Q D Q
0 CLK CLK CLK CLK
1
Clock

... ...
Qn
Q1 Q2 Qn-1
 MISR Mode
 B1=1, B2=1
D1 D2 Dn-1 Dn

B1 ...
...
B2

...

D Q SO
SI MUX D Q D Q D Q
0 CLK CLK CLK CLK
1
Clock

... ...
Qn
Q1 Q2 Qn-1
 Pros and Cons of BILBO
 Pro
 At-speed testing
 Cons
 Area too large
 Performance penalty

Not Really Useful due to Overhead

Q: BILBO belongs to separate BIST or embedded BIST?
ANS:

CUT

BILBO1

C1

BILBO2

C2

BILBO3

C3

Yellow blocks are comb. logic

 BIST Part 2
 Output Response Analysis
 BIST Architecture
 Test Per Clock
 BILBO
 Test Per Scan
 STUMPS
 Issues with BIST
 Conclusions
 Test Per Scan – Single Chain
 Test per Scan; Separate BIST
 Problem: not scalable.

CUT

L M
F PIs
Combinational Logic
POs I
S S
R R
SI SO
LFSR Scan Chain LFSR

How about Multiple Chains?

 STUMPS

SI1
CUT SO1
L 1 2 3 m M
SI2 SO2
F 1 2 3 m I
S S
R SIN SON
R
1 2 3 m

 Test per scan; separate BIST

 Small area, good for multiple chains
STUMPS: Self-Test Using a MISR and Parallel Shift Register

STUMPS is Very Popular Architecture

Suppose CUT has 50 scan chains. Each chains is 100 bit long. How
many total bits of LFSR do we need?
Q1: if we use one LFSR for each scan chain? Each LFSR 25 bits.
Q2: if we use STUMPS?

CUT SO1
LFSR 1 2 3 m
SO2
LFSR 1 2 3 m

SON
LFSR 1 2 3 m

CUT SO1
L 1 2 3 m
F SO2
S 1 2 3 m
R
SON
1 2 3 m
 Pros and Cons of STUMPS
 Advantages
 Low area overhead
 Simple control
 Disadvantages
Longer test time (than test per clock)