Test Pattern Generation - Organization

Types of Test Patterns

Counters

Finite State Machines

Linear Feedbak Shift Registers
 Primitive Polynomials
 Producing the All 0s Pattern
 Reciprocal Polynomial

Cellular Automata

Weighted Pseudo-
Pseudo-Random Test Patterns

Other TPGs

Comparing TPGs

C. Stroud 9/09 Test Pattern Generation 1

 Types of Test Patterns

Deterministic - specific to CUT developed via ATPG or fault
simulation

Algorithmic - used to test regular structures and specific fault
models

Exhaustive - all possible input test patterns
 Example: 2n patterns for n-input combinational logic circuit

Pseudo
Pseudo--exhaustive - each partitioned sub-
sub-circuit is exhaustively
tested

Pseudo
Pseudo--random - properties similar to random sequences but
repeatable

Weighted pseudo-
pseudo-random - specific bits produce more 1s or 0s

Random - true random patterns
C. Stroud 9/09 Test Pattern Generation 2
 Examples of Test Pattern Generators

Deterministic (limited applicability)
 ROM stores test patterns, counter addresses ROM

Algorithmic
 FSMs

Exhaustive (not practical for large n)
 n-bit counter produces all 2n test patterns

Pseudo
Pseudo--exhaustive
 counter, LFSR, or CA w/ MUXs for partitioning

Pseudo
Pseudo--random (most common in BIST)
 LFSR or CA with maximal-
maximal-length sequence

Weighted pseudo-
pseudo-random
 LFSR or CA with AND/OR gates for weighting

Random
 difficult to implement true random vectors
C. Stroud 9/09 Test Pattern Generation 3
 Counters

Generates all possible 2n patterns enable

Easy to implement out

Moderate area overhead enable Qi
 1 FF, 1 XOR, and 1 AND per bit in

Good for testing combinational logic

Not so good for testing sequential logic Q2 Q1 Q0
 Due to fixed, regular transitions 0 0 0
 LSB toggles every clock cycle 0 0 1
0 1 0
 MSB toggle half way through sequence
0 1 1
 Care in which bits are assigned to which inputs of CUT 1 0 0

Other types of counters to consider 1 0 1
 Gray code 1 1 0
 distance=1 for consecutive patterns (only 1 bit changes) 1 1 1
0 0 0
 N-out-
out-of-
of-M code (constant weight)
 example: 3 out of 8 bits are always 1s
C. Stroud 9/09 Test Pattern Generation 4
 Finite State Machines

Good for algorithmic test pattern generation
 Designed specifically for algorithm

Example: March Y test algorithm for RAM
 (w0); (r0, w1,r1); (r1, w0, r0); (r0);
 w0 = write 0
 r1 = read 1
 address up
 address down
 address either way

 Series of 4 march sequences

 Each march addresses through RAM

C. Stroud 9/09 Test Pattern Generation 5

 Linear Feedback Shift Registers (LFSRs)

Efficient design for TPGs and ORAs
 FFs plus a few XOR gates External Feedback LFSR
 better than counter
 fewer gates
D Q D Q D Q D Q
 higher clock frequency
CK CK CK CK

Two types of LFSRs
 External Feedback Internal Feedback LFSR
 Internal Feedback
 higher clock frequency D Q D Q D Q D Q

Characteristic polynomial CK CK CK CK

 defined by XOR positions

 P(x) = x4 + x3 + x + 1 in both examples
C. Stroud 9/09 Test Pattern Generation 6
 LFSRs (cont)
Characteristic polynomial of LFSR

n = # of FFs = degree of polynomial

XOR feedback connection to FF i coefficient of xi
 Coefficient = 0 if no connection
 Coefficient = 1 if connection
 Coefficients always included in characteristic polynomial:
 xn (degree of polynomial & primary feedback)
 x0 = 1 (principle input to shift register)

Note: state of the LFSR polynomial of degree n-1

Example: P(x) = x3 + x + 1 1x0 1x1 0x2 1x3

D Q D Q D Q
FF#1 FF#2 FF#3
CK CK CK

C. Stroud 9/09 Test Pattern Generation 7

 LSFRs (cont)

An LFSR generates periodic sequence
 Must start in a non-
non-zero state,
maximum-length of an LFSR sequence is 2n -1

The maximum-
 Does not generate all 0s pattern (gets stuck in that state)

The characteristic polynomial of an LFSR generating a
maximum--length sequence is a primitive polynomial
maximum

A maximum-
maximum-length sequence is pseudo
pseudo--random
random::
 Number of 1s = number of 0s + 1
 Same number of runs of consecutive 0s and 1s
 1/2 of the runs have length 1
 1/4 of the runs have length 2
 (as long as fractions result in integral numbers of runs)
C. Stroud 9/09 Test Pattern Generation 8
 LFSRs (cont)

Example: Characteristic polynomial is P(x) = x3 + x + 1

Beginning at all 1s state
 7 clock cycles to repeat 1x0 1x1 0x2 1x3
D Q D Q D Q
 Maximal length = 2n-1 FF1 FF2 FF3
CK CK CK
 Polynomial is primitive

Properties: 1 1 1 1
1 0 1 2
 Four 1s and three 0s 1 0 0 3
 4 runs: 0 1 0 4
0 0 1 5
 2 runs of length 1 (one 0 & one 1) 1 1 0 6
 1 run of length 2 (0s) 0 1 1 7
 1 run of length 3 (1s) 1 1 1

Note: external & internal LFSRs with same primitive polynomial do not
generate same sequence (only same length)

C. Stroud 9/09 Test Pattern Generation 9

 LFSRs (cont)

Reciprocal polynomial, P*(
*(xx)
*(xx) = xn P(1/
 P*( (1/xx)
 Example: P(x) = x3 + x + 1
*(xx) = x3 (x-3 + x-1 +1) = 1 + x2 + x3 = x3 + x2 +1
 Then: P*(
 If P(x) is primitive, P*(
*(xx) is also primitive
 Same for non-
non-primitive polynomials

Polynomial arithmetic
 Modulo (xn + xn = xn - xn = 0)
Modulo--2 (x Division
x2 + x + 1
Multiplication x2 + 1 x4 + x3 + x + 1
Addition/Subtraction (x2 + x + 1) (x2 + 1) x4 + x2
(x5 + x2 + 1) + (x
(x4 + x2) x2 + x + 1 x3 + x2 + x + 1
x5 x2 1 x2 + 1 x3 +x
+ x4 x2 x2 + x + 1 x2 + 1
x5 x4 1 x4 + x3 + x2 x2 + 1
= x5 + x4 + 1 = x4 + x3 + x + 1 0
C. Stroud 9/09 Test Pattern Generation 10
 LFSRs (cont)
Non-primitive polynomials produce sequences < 2n-1

Non-
 Typically primitive polys desired for TPGs & ORAs

Example of non-
non-primitive polynomial
 P(x) = x3 + x2 + x + 1
External Feedback LFSR Internal Feedback LFSR

DQ DQ DQ
DQ DQ DQ
CK CK CK
CK CK CK

0 0 0 1 1 1 1 0 0 0 1 0 0 0 0 1 1 1 1 1 0 1 0 1
0 0 0 1 1 1 1 1 0 1 0 1 0 0 0 1 0 0 0 1 1 1 0 1
0 1 1 0 1 0 0 1 0 1 1 0
0 0 1 0 0 1
1 0 0 1 1 1

C. Stroud 9/09 Test Pattern Generation 11

 LFSRs (cont)

Primitive polynomials with minimum # of XORs
Degree (n
(n) Polynomial
2,3,4,6,7,15,22 xn + x + 1
5,11,21,29 xn + x2 + 1
8,19 xn + x6 + x5 + x + 1
9 xn + x4 + 1
10,17,20,25,28 xn + x3 + 1
12 xn + x7 + x4 + x3 + 1
13,24 xn + x4 + x3 + x + 1
14 xn + x12 + x11 + x + 1
16 xn + x5 + x3 + x2 + 1
18 xn + x7 + 1
23 xn + x5 + 1
26,27 xn + x8 + x7 + x + 1
30 xn + x16 + x15 + x + 1
C. Stroud 9/09 Test Pattern Generation 12
 Problems with LFSRs for TPGs

Some faults are random
random--pattern resistant
 Low detection probability - detected by only by a few vectors
 Non
Non--functional patterns applied to CUT may cause problems

How many vectors to apply?

Have we reached the desired fault coverage?

Methods to reduce or eliminate random-
random-pattern resistance:
 Weighted pseudo-
pseudo-random patterns
 Add filter between TPG and CUT to get desired pattern probabilities
 Combine ad-
ad-hoc DFT techniques
 Insert additional control points
 Insert additional observation points
Can use a parity tree to feed extra responses to ORA

C. Stroud 9/09 Test Pattern Generation 13

 Modifications to LFSRs

All 0s state can be included in the pseudo-
pseudo-random sequence
 Cost: 1 XOR and n- n-1 input NOR gate 1 1 1 1
1 0 1 2
1x0 1x1 0x2 1x3 1 0 0 3
D Q D Q D Q 0 1 0 4
1 2 3 0 0 1 5
CK CK CK 0 0 0 6
1 1 0 7
0 1 1 8
1 1 1

Weighted pseudo-
pseudo-random patterns
 Probability of a logic 1 p10.5 for each LFSR bit (p
(p00.5)
 Probability can be weighted using AND/OR gates
 N-input AND gate gives p10.5N
D Q D Q D Q
 N-input OR gate gives p00.5N 1 2 3
CK CK CK

C. Stroud 9/09 Test Pattern Generation p00.25 14

 Cellular Automata (CA) Registers

Similar to an LFSR
 Generates pseudo-
pseudo-random test patterns

Different from an LFSR
 Does not have obvious shift in patterns like LFSR
External Feedback LFSR Internal Feedback LFSR Cellular Automata Register
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 0 1 1 1 0 0 1 1 0 1 0 1 0 1 1
1 0 1 1 1 1 1 1 1 0 0 1 1 0 1 0 0 0 1 0 1 0 0 1
0 1 0 1 1 1 1 1 0 1 0 0 1 1 0 1 0 1 1 0 1 1 1 0
1 0 1 0 1 1 1 1 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1
0 1 0 1 0 1 1 1 0 1 1 1 0 0 0 0 1 1 1 0 0 0 1 0
0 0 1 0 1 0 1 1 0 0 1 1 1 0 0 0 1 0 0 1 0 1 1 1
0 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 0 1 1 0 0 1 1 1
0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 1 1 0 1 1 1 1 1
1 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 1 1 0 1 1 0 1 1
1 1 0 0 0 0 1 0 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 1
1 1 1 0 0 0 0 1 1 0 1 0 0 1 0 0 1 1 0 0 1 0 1 0
0 1 1 1 0 0 0 0 0 1 0 1 0 0 1 0 1 1 1 1 1 0 1 1
0 0 1 1 1 0 0 0 0 0 1 0 1 0 0 1 1 0 1 0 0 0 0 1
1 0 0 1 1 1 0 0 1 1 0 1 0 0 1 0 0 0 1 1 0 0 1 0
1 1 0 0 1 1 1 0 0 1 1 0 1 0 0 1 0 1 0 1 1 1 1 1
C. Stroud 9/09 Test Pattern Generation 15
 CA Registers (continued)

Next state for a CA register bit is a function of
 The CA register bit before it: xi-1(t)
 Itself: xi(t) x i -1 xi xi+1
 The CA register bit after it: xi+1(t)
 There are 8 possible values for:
 xi-1(t) xi(t) xi+1(t) (000,,111)
 This corresponds to values 0 through 7

A CA register is constructed from rules
 The are 256 possible combinations of binary values for
the 8 variations of xi-1(t) xi(t) xi+1(t)
 Each combination is a rule (0- (0-255)
 Only rules 90 and 150 are useful for CA- CA-based TPGs
C. Stroud 9/09 Test Pattern Generation 16
 CA Rules 90 and 150
7 6 5 4 3 2 1 0
xi-1(t) xi(t) xi+1(t)
111 110 101 100 011 010 001 000
Rule 90 26 24 23 21
64+16+8+2=90 (64) (16) (8) (2)
xi(t+1) 0 1 0 1 1 0 1 0
Rule 150 27 24 22 21
128+16+4+2=150 (128) (16) (4) (2)
xi(t+1) 1 0 0 1 0 1 1 0
xi(t) xi+1(t) xi(t) xi+1(t)
xi-1(t) 00 01 11 10 xi-1(t) 00 01 11 10
0 0
0 1 1 0 0 1 0 1
1 1 0 0 1 1 1 0 1 0
Rule 90: xi(t) = xi-1(t) xi+1(t) Rule 150: xi(t) = xi-1(t) xi(t) xi+1(t)

x i -1 xi xi+1 x i -1 xi xi+1

C. Stroud 9/09 Test Pattern Generation 17

 CA Register Construction

CA registers are constructed given a rule for each bit
 Combinations of rules determine maximal length
sequence (or not)
 Rules obtained from tables just like LFSR
 Just like primitive vs. non-
non-primitive polynomials in LFSRs

What about the ends of the register since there is no
adjacent bit?
 Two type of boundary conditions
 Null assume logic 0 for missing bit
Reduces number of XORs
 Cyclic assume wrap-
wrap-around of ends of register
 So far only Null boundary conditions have been found
that produce maximal length sequence

CA register area overhead: Nxor = Nff + R150 - 2
C. Stroud 9/09 Test Pattern Generation 18
 Example CA Register

6-bit CA constructed for rules: 150, 90, 90, 90, 90, 90
 Produces a maximal length sequence
 All 2n-1 possible non
non--0 values
 Just like LFSR
 Note that we lock up in the all 0s state
 Just like LFSR
 More XOR gates than LFSR

Rule 150 Rule 90 Rule 90 Rule 90 Rule 90 Rule 90

w/ null BC w/ null BC

C. Stroud 9/09 Test Pattern Generation 19

 Other TPGs

LFSR with shift register Example: +5
+5
0000 1 0
 Larger number of bits with small LFSR 0101 2 5
LFSR Shift Register 1010 3 10
1111 4 15
N M
0100 5 4

Accumulator with constant prime number 1001 6 9
 Generates all 2n patterns like counter 1110 7 14
0011 8 3
 More MSB transitions than counter 1000 9 8
 Does not have random properties of LFSR 1101 10 13
0010 11 2
 LSB still toggles constant 0111 12 7
 2 LSBs still count 1100 13 12
adder
0001 14 1
0110 15 6
Register 1011 16 11
0000 0
C. Stroud 9/09 Test Pattern Generation 20
 Comparison of TPGs
TPG #FFs #XORs #gates Gate I/O

Area and performance
LFSR 8 3 8 33
 LFSR most efficient WLFSR 13 3 15 51
 Internal feedback has CAR 8 9 8 51
higher performance Counter 8 8 15 69

How well does the TPG MarchY 9 9 19 94
test itself?
 Internal feedback
LFSR wins again,
but barely beats
CAR
 Note counter-
counter-based
TPGs achieve max
fault coverage when
MSB toggles
C. Stroud 9/09 Test Pattern Generation 21