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