Built-in Self-Test (BIST)

Built-in self test.1 Built-in Self-Test (BIST) • Introduction • Test Pattern Generation • Test Response Analysis • BIST Architectures • Scan-Based BIS...

5 downloads 647 Views 259KB Size
Built-in Self-Test (BIST) • • • • •

Introduction Test Pattern Generation Test Response Analysis BIST Architectures Scan-Based BIST

Built-in self test.1

Built-in Self-Test (BIST) • •





Capability of a circuit to test itself On-line: – Concurrent : simultaneous with normal operation – Nonconcurrent : idle during normal operation Off-line: – Functional : diagnostic S/W or F/W – Structural : LFSR-based We deal primarily with structural off-line testing here. Built-in self test.2

Basic Architecture of BIST TPG Circuit Under Test (CUT) ORA • TPG: Test pattern generator • ORA Output response analyzer Built-in self test.3

Glossary of BIST • TPG - Test pattern generator • PRPG - pseudorandom pattern generator (Pseudorandom number generator) • SRSG – Shift register sequence generator (a single output PRPG) • ORA – Output response analyzer • SISR – Single-input signature register • MISR – Multiple-input signature register • BILBO – Built-in logic block observer Built-in self test.4

Built-in Self Testing • Test pattern generation – Exhaustive – Pseudoexhaustive – Pseudorandom • Test response compression – One’s count – Transition count – Parity checking – Syndrome checking – Signature analysis Built-in self test.5

Test Pattern Generation for BIST • Exhaustive testing • Pseudorandom testing – Weighted and Adaptive TG • Pseudoexhaustive testing – Syndrome driver counter – Constant-weight counter – Combined LFSR and shift register – Combined LFSR and XOR – Cyclic LFSR

Built-in self test.6

Exhaustive Testing • Apply all 2n input vectors, where n = # inputs to CUT • Impractical for large n • Detect all detectable faults that does not cause sequential behavior • In general not applicable to sequential circuits • Can use a counter or a LFSR for pattern generator

Built-in self test.7

Linear Feedback Shift Register (LFSR) • Example Z

Z

S1 S2 S1

F/F

F/F

1 0 1

0 1 0 :

Z=0101… 2 states

0 S1 S2 S3 S4 S5 S6 S7 = S0

0 1 0 1 1 1 0 :

1

1

0 0 1 0 1 1 1

1 0 0 1 0 1 1

Z=1100101… 7 states Built-in self test.8

Two Types of LFSRs • Type 1: External type

C

D

1

C2

C n-1

C

n

= 1

Q

• Type 2: Internal type

Cn

=1

Cn-1

Cn-2

C

1

D Q Q1

Q2

Qn

Built-in self test.9

Mathematical Operations over GF(2) • •

Multiplication (• )



Addition ( ⊕ or simply +)

0 1

0 0 0 1 0 1

⊕ 0 1 0 1

Example:

if then

  =   −  = 

  =   −  = 

0 1 1 0

 =  −  = 

  =  −  •  +  −  •   +  −  •    =  +  +  = 

Built-in self test.10

Analysis of LFSR using Polynomial Representation • A sequence of binary numbers can be represented using a generation function (polynomial) • The behavior of an LFSR is determined by its initial “seed” and its feedback coefficients, both can be represented by polynomials.

Built-in self test.11

Characteristic Polynomials •

       

: sequence of binary

numbers. • 



   =   +   +   +  +  +  = ∑ 

Generating function : Let





=

    =        

be output sequence of an LFSR of type1 

 = ∑     −   =

Built-in self test.12



• Let initial state be

 −   −   − 





    = ∑   = ∑ =



 −         ∑

=  =





 =

=



= ∑   ∑   −   − 



 =

=

= ∑    −   − +  +  −   − + ∑     



∴  

=

− −  − − + +                ∑  =



 + ∑    =

depends on initial state and feedback coefficients Built-in self test.13

Denominator     =  +    +      +  +      is called the characteristic polynomial of the LFSR Example:

 3

2

1

  = +  +  

0 

Built-in self test.14

LFSR Theory • Definition: If period p of sequence generated by an  LFSR is  −  , then it is a maximum length sequence • Definition: The characteristic polynomial associated with a maximum length sequence is a primitive polynomial • Theorem: # of primitive polynomials for an n-stage LFSR is given by

λ     = φ    −    where

φ   = 



 

  −   Built-in self test.15

Primitive Polynomial • # primitive polynomials of degree n

• Some primitive polynomials 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12:

0 1 1 1 2 1 1 6 4 3 2 7

0 0 0 0 0 0 5 0 0 0 4

1

0

3

0

13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24:

4 3 1 12 11 1 1 0 5 3 2 3 0 7 0 6 5 1 3 0 2 0 1 0 5 0 4 3 1

0 0 0

0

0

25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36:

N

λ   

1

1

2

1

4

2

8

16

16

2048

32

67108864

3 0 8 7 1 0 8 7 1 0 3 0 2 0 16 15 1 0 3 0 28 27 1 0 13 0 15 14 1 0 2 0 11 0 Built-in self test.16

Primitive Polynomial (Cont.) • Characteristic of maximum-length sequence: – Pseudorandom though deterministic and periodic – # 1’s = # 0’s + 1 Can be used as a (pseudo)-random or exhaustive number generator.

Built-in self test.17

LFSR Example   

 3

2

1

  = +  +  



  −  = 

0



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

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

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

 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 (repeat)

“near” complete patterns are generated

Built-in self test.18

LFSR Example (Cont.) • To generate 2n patterns using LFSR  

3

2

1

0



• Sequence becomes:

   

   









   

   









   



Built-in self test.19

What to Do if 2n is too Large? •

Using “pseudorandom” e.g. generate 232 pattern only



Partitioning







Circuit under test (CUT)



Using pseudo-exhaustive Built-in self test.20

Constant Weight Patterns (for pseudoexhaustive testing) • T, set of binary n-tuples, exhaustively covers all k-subspaces if for all subsets of k bits positions, each of the 2k binary patterns appears at least once in T, where  ≤ • Example:       =    

=

                

 =   = 

T can be a pseudoexhaustive test for a (n,w)-CUT if  ≥  Built-in self test.21

Constant Weight Patterns (Cont.) • A binary n-tuple has weight k if it contains exactly k 1’s There are   binary n-tuples having weight k. • Theorem: Given n and k, T exhausitvely covers all binary k-subspaces if it contains all binary ntuples of weight(s) w such that w=c mod (n-k+1) for some integer c, where  ≤  ≤  − 

≤≤

Built-in self test.22

Compression Techniques • Bit-by-bit comparison is inefficient • Compress information into “signature” Response compacting or compressing Input test sequence T

Circuit under test (CUT)

Output response sequence R’

Data Compression unit

Signature S( R’)

Error indicator Correct Signature S( R0 )

Comparator

Built-in self test.23

Compression Techniques to be Discussed • • • • •

Ones Count Transition Count Parity Checking Syndrome Checking Signature Analysis

Built-in self test.24

Practical Compression Techniques • • • • •

Easy to implement, part of BIST logic Small performance degradation High degree of compaction No or small aliasing errors Problems: 1. Aliasing error: signature (faulty ckt) = signature (fault-free ckt) 2. Reference (good) signature calculation: !Simulation !Golden unit !Fault tolerant Built-in self test.25

Ones-count Compression • C: single-output circuit • R: output response  =    • 1C(R) = # ones in  = 

∑ 

s-a-0 fault f2 x1 11110000 11001100

x3

10101010

Input test pattern sequence T

10000000 = R2 11000000 = R1 10000000 = R0

s-a-1 fault f1

Raw output test response

z

Counter

x2

Signature (ones count)

     =     =       = 

Built-in self test.26

Transition-count Compression     =





 ⊕ 

+ 

=

Network







D Q

  − −    =  − 

Counter

T

10000000 = R2 11000000 = R1 10000000 = R0

Signature (transition count)

     =       =       = 

• Does not guarantee the detection of single-bit errors  −  • Prob. (single-bit error masked) =   − • Prob. (masking error) π    Built-in self test.27

Parity-check Compression Signature (parity)

00000000 = R2 11000000 = R1 10000000 = R0

T

D Q

Network

  =    =      = 

Clock

• Detect all single bit errors • All errors consisting of odd number of bit errors are detected • All errors consisting of even number of bit errors are masked • Prob. (error masked) ≈ 

Built-in self test.28

Syndrome Checking • Apply random patterns. • Count the probability of 1. • The property is similar to that of ones count. random test pattern

CUT

Clock

Syndrome counter Counter

/

Syndrome Built-in self test.29

Signature Analysis • Based on linear feedback shift register (LFSR) • A linear ckt. composed of ! unit delay or D FFs ! Modulo-2 scalar multipliers or adders +/-

0

1

*

0

1

0 1

0 1

1 0

0 1

0 0

0 1

• Linear ckt.: Response of linear combination of inputs = Linear combination of responses of individual inputs

 +   =

 +

 

Built-in self test.30

Use LFSR as Signature Analyzer • Single-input LFSR



• Initial state • Final state

 = 









Internal Type LFSR



= 

  +

 or 

 =



 +



  : The remainder, or the signature Built-in self test.31

Signature Analyzer (SA) Input sequence: 

1 1 1 1 0 1 0 1 (8 bits)

( ) = 1 +   +   + 

( ) =  +  +  +   +   + 1 Time

0 1 : 5 6 7 8

Input stream

10101111 1010111 : 101 10 1 Remainder

Register contents 12345 00000 10000 : 01111 00010 00001 00101

Remainder  (  ) =  + 

Output stream

Initial state

1 01 101 

Quotient

() = 1+  Built-in self test.32

Signature Analyzer (SA) (Cont.)   +  +  + 

×

  +   +  +  + 

=



 +

 =  +  +  +  +   +  =



Built-in self test.33

Multiple-input Signature Register (MISR) D

1

D

2

D

D

3

n

D Q Cn

Cn-1

• Implementation:

C

Cn-2

Original

1

Modified

N

N

R

R*

Built-in self test.34

Storage Cell of a SA …





Ci

i  i



D C I A

Q

D

Q 

B Normal: CK, B Shift: S/T=0, A, B MISR: S/T=1, A, B Built-in self test.35

Performance of Signature Analyzer • For a test bit stream of length m : # possible response = 2m, of which only one is correct The number of bit stream producing a specific signature is

 =   

−

Built-in self test.36

Performance of Signature Analyzer (Cont.) • Among these stream , only one is correct. 



−

−  ≅ −    =   −

• If n=16, then  − −     = of erroneous response are detected. (Note that this is not % of faults !)



Built-in self test.37

Generic Off-line BIST Architecture • Categories of architectures – Centralized or Distributed – Embedded or Separate BIST elements • Key elements in BIST architecture – Circuit under test (CUTs) – Test pattern generators (TPGs) – Output-response analyzers (ORAs) – Distribution system for data transmission between TPGs, CUTs and ORAs – BIST controllers Built-in self test.38

Centralized/ Separate BIST Chip, board, or system

TPG

D I S T

CUT

CUT

D I S T

ORA

BIST controller

Built-in self test.39

Distributed / Separate BIST

Chip, board, or system TPG

CUT

ORA

TPG

CUT

ORA

Built-in self test.40

Distributed / Embedded BIST Chip, board, or system TPG

ORA CUT

TPG

ORA Built-in self test.41

Factors Affecting the Choice of BIST • • • • • • • •

Degree of test parallelism Fault coverage Level of packaging Test time Complexity of replaceable unit Factory and field test-and-repair strategy Performance degradation Area overhead

Built-in self test.42

Specific BIST Architectures

• Ref. Book by Abramovici, Breuer and Friedman • • • • •

Centralized and Separate Board-Level BIST (CSBL) Built-in Evaluation and Self-Test (BEST) Random-Test Socket (RTS) LSSD On-Chip Self-Test (LOCST) Self-Testing Using MISR and Parallel SRSG (STUMPS)

Built-in self test.43

Specific BIST Architectures (Cont.) • Concurrent BIST (CBIST) • Centralized and Embedded BIST with Boundary Scan (CEBS) • Random Test Data (RTD) • Simultaneous Self-Test (SST) • Cyclic Analysis Testing System (CATS) • Circuit Self-Test Path (CSTP) • Built-In Logic-Block Observation (BILBO) Built-in self test.44

Built-In Logic Block Observation (BILBO)[1] • • • • • • •

Distributed Embedded Combinational “Kernels” Chip level “Clouding” of circuit Registers based description of circuit BILBO registers

• [1]. B. Konemann, et al., “Built-In Logic_Block Observation Technique,” Digest of papers 1979 Test Conf., pp.37-41, Oct., 1979 Built-in self test.45

BILBO Registers ...

B1

...

B2 0

MUX

Si

D Q

D Q

Q

Q

1

Q1

...

Q2

D Q

D Q

Q

Q

Qn-1

S0

Qn

...

B1 0 0 1 1

B2 0 1 0 1

BILBO shift register reset MISR (input ∗ constant ∗ LFSR) parallel load (normal operation) Built-in self test.46

Applications of BILBO • Bus-oriented structure

BUS R11 C1 R21

R1n …

Cn R2n Built-in self test.47

Applications of BILBO (Cont.) PIs … C1 BILBO C2 …

• Pipeline-oriented structure

BILBO Cn … POs

Built-in self test.48

Problems with BILBO R1

C C1 BILBO

R2

MISR or TPG ?

R2 ?

Using CBILBO Built-in self test.49

Transistor Level Implementation of CBILBO 

 



 





  +  +  





 



     

TPG mode: C1, A2, B=0 MISR mode: C1, A1, C2=0 (c) A simultaneous TPG/MISR S-Cell



Built-in self test.50

Combination of LFSR and Scan Path LFSR

Scan Path CUT

OR

SA LFSR

Scan Path

SA

CUT • Problem: Some hard-to-detect faults may never be exercised Built-in self test.51

Example 1 + 1

0

0

S-a-0 1

0

0

0

1

0

1

0

1

1

1

0

1

1

1

0

1

1

0

0

1

• The fault can never be detected Built-in self test.52

Example 2

32 bits …..

…..

S-a-0 Or S-a-1 S-a-0

• The faults are difficult to detect Built-in self test.53

Solutions: Exhausting testing Weighted random testing Mixed mode vector pattern generation • Pseudorandom vectors first • Deterministic tests followed Do not consider the fact that the test vectors are given in a form of testcubes with many unspecified inputs. 4. Reseeding • Change the seeds as needed 5. Reprogram the characteristic polynomial 6. Combination of two or more of the above methods • • •

Built-in self test.54