Built in Self-Test: 2. Testability Measuring 3. Design For Testability

Overview
1. Introduction
2. Testability measuring
3. Design for testability
4. Built in Self-Test
Technical University Tallinn, ESTONIA

Built-In Self-Test
Outline
• Motivation for BIST
• Testing SoC with BIST
• Test per Scan and Test per Clock
• HW and SW based BIST
• Hybrid BIST
• Pseudorandom test generation with LFSR
• Exhaustive and pseudoexhaustive test generation
• Response compaction methods
• Signature analyzers

Testing Challenges: SoC Test
Cores have to be tested on chip
Source: Intel
Source: Elcoteq

Built-In Self-Test
System-on-Chip •
Advances in microelectronics technology
have introduced a new paradigm in IC
design: System-on-Chip (SoC)
149. 1
• Many systems are nowadays designed by
S el f -t est
co n tro l
embedding predesigned and preverified
complex functional blocks (cores) into
UDL one single die
L eg acy
DS P
co re
co re
• Such a design style allows designers to
reuse previous designs and will lead to
shorter time-to-market and reduced cost
I n terf ace
Co n t ro l
SoC structure breakdown:
UDL • 10% UDL
Co p mp l ex
co re
E mb ed d • 75%
ed memory
DRAM
• 50% in-house cores
• 60-70% soft cores

Self-Test in Complex Digital Systems
Test architecture components:
SoC
SoC
Peripheral • Test pattern source & sink
SRAM Component SRAM
Interconnect • Test Access Mechanism
Test Access
Mechanism • Core test wrapper
Wrapper
ROM
Core
CPU Under Sink
Test Solutions:
• Off-chip solution
Source Test Access
Mechanism
– need for external ATE
• Combined solution
DRAM
MPEG UDL – mostly on-chip, ATE
needed for control
• On-chip solution
– BIST

Self-Test in Complex Digital Systems
Test architecture components:
SoC
SoC
Peripheral • Test pattern source & sink
SRAM Component SRAM
Interconnect • Test Access Mechanism
• Core test wrapper
Wrapper
ROM
Core
CPUSource Under Sink
Test Solutions:
• Off-chip solution
– need for external ATE
• Combined solution
DRAM
MPEG UDL – mostly on-chip, ATE
needed for control
• On-chip solution
– BIST

What is BIST
• On circuit
– Test pattern generation Test Pattern Generation (TPG)
– Response verification
Circuitry Under Test
• Random pattern
BIST
Control Unit
CUT
generation,
very long tests Test Response Analysis (TRA)
IC
• Response compression

SoC BIST
Optimization:
Embedded Tester - testing time 
Core 1 Core 2
- memory cost 
Test Test access - power consumption 
Controller BIST mechanism
- hardware cost 
BIST
- test quality 
Tester
Memory
BIST BIST BIST
Core 3 Core 4 Core 5
System on Chip

Built-In Self-Test
• Motivations for BIST:

– Need for a cost-efficient testing (general motivation)
– Doubts about the stuck-at fault model
– Increasing difficulties with TPG (Test Pattern Generation)
– Growing volume of test pattern data
– Cost of ATE (Automatic Test Equipment)
– Test application time
– Gap between tester and UUT (Unit Under Test) speeds
• Drawbacks of BIST:
– Additional pins and silicon area needed
– Decreased reliability due to increased silicon area
– Performance impact due to additional circuitry
– Additional design time and cost

Costly Test Problems Alleviated by BIST
• 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
• In-circuit testing no longer technically feasible
• Shortage of test engineers
• Circuit testing cannot be easily partitioned

BIST in Maintenance and Repair
• Useful for field test and diagnosis (less expensive

than a local automatic test equipment)
• Disadvantages of software tests for field test and
diagnosis (nonBIST):
– Low hardware fault coverage
– Low diagnostic resolution
– Slow to operate
• Hardware BIST benefits:
– Lower system test effort
– Improved system maintenance and repair
– Improved component repair
– Better diagnosis

Benefits and Costs of BIST with DFT
Level Design Fabri- Manuf. Maintenance Diagnosis Service

and test cation Test test and repair interruption
Chips +/- + -
Boards +/- + - -
System +/- + - - - -
+ Cost increase
- Cost saving
+/- Cost increase may balance cost reduction

Economics – BIST Costs
 Chip area overhead for:

• Test controller
• Hardware pattern generator
• Hardware response compacter
• 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 – happens when BIST
hardware is made testable

BIST Benefits
• Faults tested:
 Single 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

BIST Techniques
• BIST techniques are classified:
– on-line BIST - includes concurrent and nonconcurrent techniques
– off-line BIST - includes functional and structural approaches
• On-line BIST - testing occurs during normal functional operation
– Concurrent on-line BIST - testing occurs simultaneously with normal operation
mode, usually coding techniques or duplication and comparison are used
– Nonconcurrent on-line BIST - testing is carried out while a system is in an idle
state, often by executing diagnostic software or firmware routines
• Off-line BIST - system is not in its normal working mode, usually
– on-chip test generators and output response analyzers or microdiagnostic routines
– Functional off-line BIST is based on a functional description of the Component
Under Test (CUT) and uses functional high-level fault models
– Structural off-line BIST is based on the structure of the CUT and uses structural
fault models (e.g. SAF)

General Architecture of BIST
• BIST components:
– Test pattern generator
Test Pattern Generation (TPG)
(TPG)
– Test response
analyzer (TRA)
• TPG & TRA are usually
BIST implemented as linear
Control Unit feedback shift registers
CUT
(LFSR)
• Two widespread
Test Response Analysis (TRA) schemes:
– test-per-scan
– test-per-clock

Detailed BIST Architecture
Source: VLSI Test: Bushnell-Agrawal Technical University Tallinn, ESTONIA

Built-In Self-Test
Test pattern BIST Test response
generator Control analysator Test per Scan:
Scan Path
Initial test set:
CUT
Scan Path
T1: 1100
.
T2: 1010
.
. T3: 0101
Scan Path T4: 1001
Test application:
• Assumes existing scan
architecture 1100 T 1010 T 0101T 1001 T
• Drawback: Number of clocks = 4 x 4 + 4 = 20
– Long test application time

Scan-Path Design
IN OUT The complexity of testing is a function

Combinational of the number of feedback loops and
circuit their length
The longer a feedback loop, the more
Scan-IN clock cycles are needed to initialize
and sensitize patterns
q’ R q Scan-register is a aregister with both
shift and parallel-load capability
T = 0 - normal working mode T=1
Scan-OUT - scan mode
Normal mode : flip-flops are connected
q to the combinational circuit
&
Scan-IN 1 D T q’ Test mode: flip-flops are disconnected
& from the combinational circuit and
C connected to each other to form a shift
register
T Scan-OUT

Built-In Self-Test
Test per Clock:
• Initial test set:
• T1: 1100
Combinational Circuit • T2: 1010
• T3: 0101
Under Test • T4: 1001
• Test application:
Scan-Path Register • 1 10 0 1 0 1 0 01 01 1001

•
• T1 T4 T3 T2
• Number of clocks = 10

BILBO BIST Architecture
Working modes: B1
LFSR 1
B1 B2 B2
0 0 Reset
0 1 Flip-flop (normal)
CC1
1 0 Scan mode
1 1 Test mode
Testing modes: B1
LFSR 2
B2
CC1: LFSR 1 - TPG
LFSR 2 - SA
CC2
CC2: LFSR 2 - TPG
LFSR 1 - SA

BILBO BIST Architecture: Example
• Testing epoch I:
 LFSR1 generates tests for CUT1 and CUT2
 BILBO2 (LFSR3) compacts CUT1 (CUT2)
• Testing epoch II:
 BILBO2 generates test patterns for CUT3
 LFSR3 compacts CUT3 response

Pattern Generation
• Store in ROM – too expensive
• Exhaustive
• Pseudo-exhaustive
• Pseudo-random (LFSR) – Preferred method
• Binary counters – use more hardware than LFSR
• Modified counters
• Test pattern augmentation
 LFSR combined with a few patterns in ROM
 Hardware diffracter – generates pattern cluster in
neighborhood of pattern stored in ROM

Pattern Generation
Pseudorandom Test generation by LFSR:

...
• Using special LFSR registers
ho h1 hn
• Several proposals:
Xo X1 ... Xn – BILBO
– CSTP
LFSR
• Main characteristics of LFSR:
– polynomial
CUT – initial state
– test length
LFSR

Some Definitions
• LFSR – Linear feedback shift register, hardware that generates

pseudo-random pattern sequence
• 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
• Exhaustive testing – Apply all possible 2n patterns to a circuit with
n inputs
• Pseudo-exhaustive testing – Break circuit into small, overlapping
blocks and test each exhaustively
• Pseudo-random testing – Algorithmic pattern generator that
produces a subset of all possible tests with most of the properties of
randomly-generated patterns

More Definitions
• Irreducible polynomial – Boolean polynomial that cannot be factored

• Primitive polynomial – Boolean polynomial p(x) that can be used to
compute increasing powers n of xn modulo p(x) to obtain all possible
non-zero polynomials of degree less than p(x)
• Signature – Any statistical circuit property distinguishing between bad
and good circuits
• TPG – Hardware test pattern generator
• PRPG – Hardware Pseudo-Random Pattern Generator
• MISR – Multiple Input Response Analyzer

Pseudorandom Test Generation
LFSR – Linear Feedback Shift Register:
Standard LFSR
x x2 x3 x4
Modular LFSR
x x2 x3 x4
Polynomial: P(x) = x4 + x3 + 1

Theory of LFSR
c1 c2 c3 c4
y1 y2 y3 y4
x x2 x3 x4
y0
j n
y j (t )  y j 1 (t  1) for j j 0 y0 (t )   c j y j (t )
j 1
y j (t )  y0 (t  j )
j n
y j (t )  y0 (t ) x y0 (t )   c j y0 (t ) x j
j
j 1
where j represents the time
translation units
Theory of LFSR
c1 c2 c3 c4
y1 y2 y3 y4
x x2 x3 x4
y0
j n
j n y0 (t )( c j x j  1)  0
y0 (t )   c j y0 (t ) x j j 1
j 1
Polynomial:
j n
y0 (t )  y0 (t ) c j x j y0 (t ) Pn ( x)  0
j 1

Theory of LFSR
c1 c2 c3 c4
y1 y2 y3 y4
x x2 x3 x4
y0
Characteristic polynomial:
y0 (t ) Pn ( x)  0 For y0 (t )  0 Pn ( x)  0
j n
where Pn ( x)  1   c j x j
j 1

x x2 x3 x4

Matrix Equation for Standard LFSR
Xn (t + 1) 0 1 0 … 0 0 Xn (t)
Xn-1 (t + 1) 0 0 1 … 0 0 Xn-1 (t)
. . . . . . .
. . . . . . .
. = . . . . . .
X3 (t + 1) 0 0 0 … 1 0 X3 (t)
X2 (t + 1) 0 0 0 … 0 1 X2 (t)
X1 (t + 1) 1 hn-1 hn-2 … h2 h1 X1 (t)
X (t + 1) = Ts X (t) (Ts is companion matrix)
x x2 x3 x4

x x2 x3 x4
t x x2 x3 x4 t x x2 x3 x4
Polynomial: P(x) = x4 + x3 + 1 1 0 0 0 1 9 0 1 0 1
2 1 0 0 0 10 1 0 1 0
X4 (t + 1) 0 1 0 0 X4 (t) 3 0 1 0 0 11 1 1 0 1
X3 (t + 1) 0 0 1 0 X3 (t) 4 0 0 1 0 12 1 1 1 0
=
X2 (t + 1) 0 0 0 1 X2 (t) 5 1 0 0 1 13 1 1 1 1
X1 (t + 1) 1 h3 h2 h1 X1 (t) 6 1 1 0 0 14 0 1 1 1
7 0 1 1 0 15 0 0 1 1
8 1 0 1 1 16 0 0 0 1
1 0 0

Theory of LFSR: Primitive Polynomials
Properties of Polynomials:
• Irreducible polynomial – cannot be factored, is divisible

only by itself
• Irreducible polynomial of degree n is characterized by:
– An odd number of terms including 1 term
– Divisibility into 1 + xk, where k = 2n – 1
• Any polynomial with all even exponents can be factored and
hence is reducible
• An irreducible polynomial is primitive if it divides the
polynomial 1+xk for k = 2n – 1, but not for any smaller
positive integer k

Theory of LFSR: Examples
Polynomials of degree n=3 (examples): k = 2n – 1= 23 – 1=7

Primitive polynomials:
x3  x 2  1 The polynomials will divide evenly the polynomial x7 + 1,

but not any one of k<7, hence, they are primitive
x3  x  1 They are also reciprocal: coefficients are 1011 and 1101
Reducible polynomials (non-primitive):
x 3  1  ( x  1)( x 2  x  1) The polynomials don’t divide

evenly the polynomial x7 + 1
x 3  x 2  x  1  ( x  1)( x 2  1)

Comparison of test sequences generated:

Primitive polynomials Non-primitive polynomials
x3  x  1 x  x 1
3 2
x3  1 x3  x 2  x  1
100 100 100 100
110 010 010 110
111 101 001 011
011 110 100 001
101 111 010 100
010 011 001 110
001 001 100 011
100 100 010 001
Reducible polynomial (non-primitive):
x2  x 1
x3  1  ( x  1)( x 2  x  1) x2  x 1
x3  1 x 1 x2  x 1 Multiplication of
two primitive
x2  x 1
polynomials: x3  x2  x
100 1 x 4  x3  x2
x x2
010 0
001 1 x4  x2 1
01
100 10 Is
x4  x2 1
11
01 a primitive polynomial?
Primitive polynomial

Is x4  x2 1 a primitive polynimial? Divisibility check:
Irreducible polynomial of
x11  x 9  x 5  x 3
degree n is characterized by: x 4  x 2  1 x15  1
- An odd number of terms x15  x13  x11
including 1 term? x13  x11  1
Yes, it includes 3 terms x13  x11  x 9
-Divisibility into 1 + xk, x9  1
where k = 2n – 1 x9  x7  x5
No, there is remainder x3  1 x7  x5  1
x7  x5  x3
x4  x2 1 is non-primitive?
x3  1
Non-primitive polynomial Primitive polynomial
x4 + x2 + 1 x4 + x + 1
x x2 x3 x4 x x2 x3 x4
0001 1001 0110 0001 1011 1001

1000 1100 1011 1000 0101 0100
0100 1110 1101 1100 1010 0010
1010 1111 0110 1110 1101 0001
0101 0111 1111 0110
0010 0011 0111 0011
0001 1001

Primitive polynomial Zero generation:
x4 + x + 1
x x2 x3 x4
x x2 x3 x4
1
0001 1011 1001
1000 0101 0100 0000 1011 1001
1100 1010 0010 1000 0101 0100
1110 1101 0001 1100 1010 0010
1111 0110 1110 1101 0001
0111 0011 1111 0110 0000
0111 0011
Theory of LFSR: Reciprocal Polynomials
The reciprocal polynomial of P(X) is defined by:
(X) =XN PN (1/X) = XN {1 + Cj X-J}

(X) = XN + Cj XN-J for 1  i  N
Thus every coefficient Ci in P(X) is replaced by CN-I.
Example:
The reciprocal of polynomial P3(X) = 1 + X + X3
is P’3 (X) = 1 + X2 + X3
 The reciprocal of a primitive polynomial is also primitive

Table of primitive polynomials up to degree 31

Number of primitive
polynomials of N Primitive Polynomials
degree N 1,2,3,4,6,7,15,22 1 + X + Xn
5,11, 21, 29 1 + X2 + Xn
N No 10,17,20,25,28,31 1 + X3 + Xn
1 1 9 1 + X4 + Xn
2 1 23 1 + X5 + Xn
18 1 + X7 + Xn
4 2
8 1 + X2 + X3 + X4 + Xn
8 16 12 1 + X + X3 + X4 + Xn
16 2048 13 1 + X + X4 + X6 + Xn
32 67108864 14, 16 1 + X + X3 + X4 + Xn

Examples of PP (exponents of terms):
n other n other
Number of PP of
degree n 1 0 9 4 0
2 1 0 10 3 0
n No
3 1 0 11 2 0
1 1
4 1 0 12 7 4 3 0
2 1
5 2 0 13 4 3 1 0
4 2
6 1 0 14 12 11 1 0
8 16
7 1 0 15 1 0
16 2048
8 6 5 1 0 16 5 3 2 0
32 67108864
Deterministic Synthesis of LFSR
Generation of the polynomial and seed for the given test sequence
Creation of the Expected shortest

shortest bit-stream: LFSR sequence:
Given test 10010 1 01111 01111 (4)
sequence: Seed
10111
(1) 100x0 1
0 01011
(2) x1010
10101 (3)
(3) 10101
01010 (2)
(4) 01111
00101
10010 (1)

Expected shortest System of linear equations:
LFSR sequence:
01111 x1 1
01111 (4) 10111 x2 0
01011 x x3 = 1
1 0111
10101 x4 0
0 1011
01010 x5 0
1 0101 (3)
00101 1
0 1010 (2)
0 0101 We are looking for values of xi
1 0010 (1) : x1 x2 x3 x4
x5
x x2 x3 x4 x5

System of linear equations: Solving the equation by
Gaussian elimination:
1 01111 x1 1
2 10111 0 1,2,4,6 01000 x1 0
x2
3 01011 x x 1 4,6 10000 x2 1
3 = 00100 x x = 0
4 10101 0 1,3
x4 3
5 01010 0 2,4 00010 x4 0
x5
6 00101 1 1,2,3,4,6 00001 x5 1
00001 1
Polynomial: x5 + x + 1 Seed: 01111
x1 Solution: x1 x2 x3 x4 x5
x5 1 0 0 0 1
x x2 x3 x4 x5

Embedding deterministic test patterns into LFSR sequence:
Polynomial: x5 + x + 1 Seed: 01111

LFSR sequence:
x1
x5 (1) 01111 (4)
x x2 x3 x4 x5
(2) 10111
(3) 01011
Given (1) 100x0 (4) 10101 (3)
deterministic (2) x1010 (5) 01010 (2)
test (3) 10101
sequence:
(6) 00101
(4) 01111 (7) 10010 (1)

BIST: Test Generation

breakpoint
Fault Coverage
Fault Coverage
Problems: Possible solutions
• Very long test • Weighted pattern PRPG
application time
• Combining pseudorandom
• Low fault coverage test with deterministic test
• Area overhead – Multiple seed
• Additional delay – Hybrid BIST
Time Time

BIST: Fault Coverage
Fault coverage is rapidly
growing: 1
100% 2 Combinational
circuit
0% under test
93,75% n
4. pat. 87,5%
Truth table:
Faulty
3. pattern
functions Patterns Functions
75%
covered by 1 00…000 01 01 01…101 2n-1
1. pattern
Faulty 2
functions 00…001 00 11 00…011
Number of tested
covered by 00…010 00 00 11…111
patterns
2. pattern 50%!
… …
2n 11…111 00 00 00…111
n
50% Number of functions 1 22

BIST: Fault Coverage

Motivation of using Reasons of the high initial efficiency:
LFSR: 2n
A circuit may implement 2 functions
- low generation cost
- high initial efeciency A test vector partitions the functions into 2 equal
sized equivalence classes (correct circuit in one of
them)
The second vector partitions into 4 classes etc.
After m patterns the fraction of functions
Fault Coverage
distinguished from the correct function is
m
1
2
2 2  1 i 1
n
2 n i
, 1  m  2n
Time

BIST: Different Techniques

Full identification is Pseudorandom testing of sequential circuits:
achieved only after 2n input The following rules suggested:
combinations have been
• clock-signals should not be random
tried out (exhaustive test)
m
• control signals such as reset, should be activated
1
2 2n
1
 2
i 1
2 n 1
, with low probability
• data signals may be chosen randomly
Microprocessor testing
1  m  2n
• A test generator picks randomly an instruction
A better fault model and generates random data patterns
(stuck-at-0/1) • By repeating this sequence a specified number of
may limit the number of times it will produce a test program which will
partitions necessary test the microprocessor by randomly excercising
its logic

BIST: Structural Approach to Test
1
Testing of structural faults: 2 Combinational
circuit
under test
n
Not tested
faults 3. patttern
4. pat.
2. pattern Fault coverage
100%
Faults
covered by
1. pattern
Number of
patterns

BIST: Two Approaches to Test
Testing of Testing of
100%
functions: faults:
0%
93,75% Not tested
faults 3. patttern
4. pat.
4. pat. 87,5% 2. pattern
Faults
Faulty
3. pattern covered by
functions
75% 1. pattern
covered by
Faulty
1. pattern 100%
functions
covered by
2. pattern
100% will be reached
Testing of
100% will be when all faults from
functions
reached only the fault list are
50% Testing of covered
after 2n test
patterns faults

BIST: Other test generation methods
Universal test sets
1. Exhaustive test (trivial test)
2. Pseudo-exhaustive test
Properties of exhaustive tests
1. Advantages (concerning the stuck at fault model):
- test pattern generation is not needed
- fault simulation is not needed
- no need for a fault model
- redundancy problem is eliminated
- single and multiple stuck-at fault coverage is 100%
- easily generated on-line by hardware
2. Shortcomings:
- long test length (2n patterns are needed, n - is the number of inputs)
- CMOS stuck-open fault problem

Pseudo-exhaustive test sets:
Output function verification
– Output function verification
• maximal parallel testability 4
• partial parallel testability
4
– Segment function verification
4
Segment function verification
Primitive 4
polynomials
1111 216 = 65536 >> 4x16 = 64 > 16

0011 &
F Exhaustive Pseudo- Pseudo-
0101
test exhaustive exhaustive
sequential parallel

Testing ripple-carry adder
Output function verification (maximum parallelity)
Exhaustive test generation for n-bit adder:
Good news: Bad news:
Bit number n - arbitrary The method is correct
Test length - always 8 (!) only for ripple-carry adder
c0 a0 b0 c1 a1 b1 c2 a2 b2 c3 …
1 0 0 0 0 0 0 0 0 0 0
2 0 0 1 0 0 1 0 0 1 0
3 0 1 0 0 1 0 0 1 0 0
4 0 1 1 1 0 0 0 1 1 1
5 1 0 0 0 1 1 1 0 0 0
6 1 0 1 1 0 1 1 0 1 1
7 1 1 0 1 1 0 1 1 0 1
8 1 1 1 1 1 1 1 1 1 1
0-bit testing 1-bit testing 2-bit testing 3-bit testing … etc

Testing carry-lookahead adder
General expressions:
Gi  ai bi Pi  ai bi  aibi Cn  Gn  PnCn1
Cn  Gn  Pn (Gn1  Pn1Cn2 )  Gn  PnGn1  Pn Pn1Cn2
n-bit carry-lookahead adder:
C1  G1  P1C0  a1b1  a1 b1C0  a1b1C0  f (a1 , b1 , C0 )

C3  G3  P3G2  P3 P2G1  P3 P2 P1C0
P3 P2 P1C0  (a3 b3  a3b3 )(a2 b2  a2b2 )(a1 b1  a1b1 )C0

Testing carry-lookahead adder
P3 P2 P1C0  (a3 b3  a3b3 )(a2 b2  a2b2 )(a1 b1  a1b1 )C0 R

1 1 0 0 1 1 0 0 1 1 0 0 1 1
Testing  0
0 0 1 1 0 0 1 1 0 0 1 1 1 1
1 0 0 1 1 1 1 1 1 0
Testing  1
0 1 1 0 1 1 1 1 1 0
1 1 0 1 1 0 1 1 1 0
1 1 1 0 0 1 1 1 1 0
1 1 1 1 0 1 1 0 1 0
1 1 1 1 1 0 0 1 1 0
1 1 1 1 1 1 0 0
For 3-bit carry lookahead adder for testing only this part of the circuit at least
9 test patterns are needed
Increase in the speed implies worse testability

Output function verification (partial parallelity)
F1 0011- - x1 F1(x1, x2)

0011- 0
F2(x1, x3)
010101 x2
F3 F3(x2, x3)
F2 010110 x3 F4(x2, x4)
F5(x1, x4)
F4 00-11- x4 F6(x3, x4)
F5 000111
Exhaustive testing - 16
Pseudo-exhaustive, full parallel - 4
Pseudo-exhaustive, partially parallel - 6

Problems with Pseudorandom Test
The main motivations of Problem: low fault coverage
using random patterns
are:
- high initial efeciency &
1
LFSR
Decoder
Counter
Fault Coverage
Reset
If Reset = 1 signal has probability 0,5 then

counter will not work and
Time
1 for AND gate may never be produced

Sequential BIST
A DFT technique of BIST for sequential circuits is proposed

The approach proposed is based on all-branches coverage metrics
which is known to be more powerful than all-statement coverage
S0 S0 S0
A=1 A=1 A=1

S1 S5 S1 S5 S1 S5
A= 0 A= 0 A= 0
S2 S2 S2
B=0 B=1 B=0 B=1 B=0 B=1
S3 S4 S3 S4 S3 S4

Sequential BIST
Digital System
• Status signals entering the
reset control part are made
FSM controllable
clock • In the test mode we can force
test/normal the UUT to traverse all the
control signals status
mode (TM) signals branches in the FSM state
transition graph
MUX
primary • The proposed idea of
inputs architecture requires small
Datapath device area overhead since a
masked simple controller can be
status bits
implemented to manipulate
observation the control signals
primary outputs points

BIST: Weighted pseudorandom test
Hardware implementation of weight generator
LFSR
& & &
1/16 1/8 1/4 1/2

Weight select MUX
Desired weighted value Scan-IN

Problem: random-pattern-resistant faults NDI - number of circuit inputs
for each gate to be the number
Solution: weighted pseudorandom
of PIs or SRLs in the backtrace
testing cone
The probabilities of pseudorandom signals PI - primary inputs
are weighted, the weights are determined by
SRL - scan register latch
circuit analysis
1 NCV NDI - relative measure of the
number of faults to be
Faults & detected through the gate
to be Propagated
tested faults I
NDII G
&
NCV – non-controlling value
NDIG
The more faults that must be tested
through a gate input, the more the other
inputs should be weighted to NCV

1 NCV R I = NDIG / NDII

Faults & R I - the desired ratio of the
to be Propagated NCV to the controlling value
tested faults for each gate input
NCV - noncontrolling value

I
The more faults that must be tested NDII G
through a gate input, the more the other &
inputs should be weighted to NCV
NDIG

Example:
R 1 = NDIG / NDII = 6/1 = 6

PI
R 2 = NDIG / NDII = 6/2 = 3
1
PI G R 3 = NDIG / NDII = 6/3 = 2
2
&
PI
3 More faults must be detected
PI through the third input than
PI through others
PI
This results in the other inputs
being weighted more heavily
towards NCV

Calculation of signal weights:
W0, W1 - weights of the signals
R1=6
PI WV - the value to which the input is biased
R2=3 W01 = 1
W02 = 1 W11 = 6
1 WV = 0, if W0  W1 else WV = 1
W12 = 3
PI G
&
PI 2 Calculation of W0, W1
3
PI W0G = 1 Function WOI W1I
PI
W1G = 1 AND WOG RI  W1G
PI
NAND W1G RI  WOG
R3=2 OR RI  WOG W1G
W03 = 1 NOR RI  W1G WOG
W13 = 2

Calculation of signal weights:
R1=1 Backtracing from all the

W01 = 6 PI1 1 W01 = 1 outputs to all the inputs
W11 = 1 W11 = 6 of the given cone
1 Weights are calculated for
R1=2 PI2 G
W01 = 2 1 & all gates and PIs
W11 = 3 PI3 2
3
R1=3 PI4 W02 = 1 Function WOI W1I
W01 = 3 PI5 1 W12 = 3 OR RI  WOG W1G
W11 = 2 PI6
NOR RI  W1G WOG
W03 = 1
W13 = 2

Calculation of signal probabilities:
R1=1
W01 = 6 PI1 1 WF - weighting factor indicating the
W11 = 1
amount of biasing toward weighted
1 value
R1=2 PI2 G
W01 = 2 1 & WF = max {W0,W1} / min {W1,W0}
W11 = 3 PI3 2
3 Probability:
R1=3 PI4 P = WF / (WF + 1)
W01 = 3 PI5 1
W11 = 2 PI6
For PI1 : W0 = 6 W1 = 1 P1 = 1/7 = 0.15
For PI2 and PI3 : W0 = 2 W1 = 3 P1 = 3/5 = 0.6
For PI4 - PI6 : W0 = 3 W1 = 2 P1 = 2/5 = 0.4

Calculation of signal probabilities:
PI 1 Probability of detecting the fault 1

at the input 3 of the gate G:
1
PI 2 G 1) equal probabilities (p = 0.5):
1 &
PI P = 0.5  (0.25 + 0.25 + 0.25)  0.53 =
3 = 0.5  0.75  0.125 =
PI = 0.046
PI 1
PI 1 2) weighted probabilities:
P = 0.85 
 (0.6  0.4 + 0.4  0.6 + 0.62) 
For PI1 : P1 = 0.15  0.63 =
= 0.85  0.84  0.22 =
For PI2 and PI3 : P1 = 0.6
= 0.16
For PI4 - PI6 : P1 = 0.4

BIST: Response Compression
1. Parity checking Pi-1

m
P( R)  ( ri ) mod 2 Test
i 1 UUT T
2. One counting
ri
m
P ( R )   ri
i 1
3. Zero counting Test ri

m
UUT Counter
P ( R )   ri
i 1

BIST: Response Compression
4. Transition counting
ri
a) Transition 01 Test &

m UUT T
P ( R )   (ri 1ri ) ri-1
i2
b) Transition 10 ri
m
P ( R )   (ri 1 ri ) Test &
i 2 UUT T ri-1
5. Signature analysis

Standard LFSR
x x2 x3 x4
Modular LFSR
x x2 x3 x4

BIST: Signature Analysis
Signature analyzer:
Standard LFSR
1 x x2 x4
UUT
x3
Modular LFSR
Response
string 1 x x2 x4
x3
Response in compacted
by LFSR
The content of LFSR after Polynomial: P(x) = 1 + x3 + x4
test is called signature

Theory of LFSR
The principles of CRC (Cyclic Redundancy Coding) are used

in LFSR based test response compaction
Coding theory treats binary strings as polynomials:
R = rm-1 rm-2 … r1 r0 - m-bit binary sequence
R(x) = rm-1 xm-1 + rm-2 xm-2 + … + r1 x + r0 - polynomial in x
Example:
11001  R(x) = x4 + x3 + 1
Only the coefficients are of interest, not the actual value of x
However, for x = 2, R(x) is the decimal value of the bit string

Arithmetic of coefficients:
- linear algebra over the field of 0 and 1: all integers mapped into either 0 or 1
- mapping: representation of any integer n by the remainder resulting from
the division of n by 2:
n = 2m + r, r  { 0,1 } or r  n (modulo 2)
Linear - refers to the arithmetic unit (modulo-2 adder), used in CRC
generator (linear, since each bit has equal weight upon the output)
Examples:
x4 + x 3 + x + 1 x4 + x 3 + x + 1
+ x4 + x2 + x  x + 1
x3 + x2 + 1 x5 + x 4 + x2 + x
x4 + x 3 + x + 1
x5 + x3 + x2 + 1

Theory of LFSR
Characteristic Polynomials:

G ( x)  c0  c1 x  c2 x 2  ...  cm x m  ...   cm x m
m 0
x2  x 1
Multiplication of x2 1
polynomials x2  x 1
x 4  x3  x 2
x 4  x3  x 1

Theory of LFSR
Characteristic Polynomials:

G ( x)  c0  c1 x  c2 x 2  ...  cm x m  ...   cm x m
m 0
x2  x 1 Quotient
Divider x2 1 x 4  x3 1 Dividend
x4  x2
x3  x 2 1
Division of x3 x
polynomials x2  x 1
x2 1
x Remainder

Division of one polynomial P(x) by another

P( x) R( x)
G(x) produces a quotient polynomial Q(x),
and if the division is not exact, a remainder
 Q( x ) 
polynomial R(x)
G ( x) G ( x)
Example:
P( x ) x7  x3  x x 2
1
 5  x  x 1 5
3 2
G ( x) x  x  x  1
3
x  x3  x  1
Remainder R(x) is used as a check word in data transmission
The transmitted code consists of the unaltered message P(x) followed by the check
word R(x)
Upon receipt, the reverse process occurs: the message P(x) is divided by known
G(x), and a mismatch between R(x) and the remainder from the division indicates
an error

In signature testing we mean the use of CRC
encoding as the data compressor G(x) and
the use of the remainder R(x) as the signature P( x) R( x)
of the test response string P(x) from the UUT  Q( x ) 
Signature is the CRC code word
G ( x) G ( x)
Example:
G(x) 101 = Q(x) = x2 + 1
101011 10001010
101011 P(x)
P( x) x x x
7 3
 5 00100110
G ( x) x  x 3  x  1 101011
0 0 1 1 0 1 = R(x) = x3 + x2 + 1
Signature

G(x) The division process can
be mechanized using LFSR
x0 x1 x2 x3 x4
The divisor polynomial G(x)
is defined by the feedback
IN: 01 010001 Shifted into LFSR connections
Shift creates x5 which is
P(x) replaced by x5 = x3 + x + 1
Compressor
101
G(x) Response
101011 10001010
101011
P( x) x x x
7 3 P(x)
 5 x5
00100110
G ( x) x  x 3  x  1 101011
0 0 1 1 0 1 = R(x) = x3 + x2 + 1
Signature

Aliasing:
Response L - test length
UUT SA
N - number of stages in
L N Signature Analyzer
All possible responses All possible signatures
k  2N
k  2L Faulty
response
Correct
response
N << L
Aliasing:
Response L - test length
UUT SA
N - number of stages in
L N Signature Analyzer
k  2L - number of different possible responses
No aliasing is possible for those strings with L-N leading zeros since they are
represented by polynomials of degree N-1 that are not divisible by characteristic
polynomial of LFSR
000000000000000 ... 00000 XXXXX
2 LN  1 - aliasing is possible L N
2 L N  1 L  1 1
P N
Probability of aliasing: P L
2 1 2
Parallel Signature Analyzer:
Single Input Signature Analyser
x4 x2 x 1
UUT
x3
x4 x2 x 1
x3
Multiple Input Signature
UUT Analyser (MISR)

Signature calculating for multiple outputs:
LFSR - Test Pattern Generator LFSR - Test Pattern Generator
Combinational circuit Combinational circuit
Multiplexer Multiplexer
LFSR - Signature analyzer LFSR - Signature analyzer

BIST: Joining TPG and SA
LFSR
1 x x2 x3 x4
UUT FF FF FF FF
Response string for Test Pattern (when generating tests)

Signature Analysis Signature (when analyzing test responses)

BIST Architectures
General Architecture of BIST

• BIST components:
– Test pattern generator (TPG)
– Test response analyzer (TRA)
Test Pattern Generation (TPG) – BIST controller
• A part of a system (hardcore)
must be operational to execute a
self-test
BIST • At minimum the hardcore usually
Control Unit
CUT includes power, ground, and
clock circuitry
• Hardcore should be tested by
Test Response Analysis (TRA) – external test equipment or
– it should be designed self-
testable by using various forms of
redundancy

BIST Architectures
Test per Clock:
Joint TPG and SA:
Disjoint TPG and SA: CSTP - Circular Self-Test

BILBO Path:
LFSR - Test Pattern Generator LFSR - Test Pattern Generator

& Signature analyser
Combinational circuit
Combinational circuit
LFSR - Signature analyzer

BIST: Circular Self-Test Architecture
Circuit Under Test
FF FF FF

BIST: Circular Self-Test Path
CSTP CSTP
CC CC
CSTP
CC
R R
CC CC
CSTP CSTP

BIST Embedding Example
LFSR1 LFSR2
CSTP
M1 M2 M4
M3
MUX M5 BILBO
Concurrent
testing: MISR1
MUX M6
LFSR, CSTP  M2  MISR1
M2  M5  MISR2 (Functional BIST)
CSTP  M3  CSTP MISR2
LFSR2  M4  BILBO
BIST Architectures
STUMPS: LOCST: LSSD On-Chip Self-Test
Self-Testing Unit Using MISR
and Parallel Shift Register Scan Path
Sequence Generator
BS BS
Test Pattern Generator
CUT
Scan chain
Scan chain
CUT CUT
TPG SA
...
Test
SI SO
Controller
MISR Error
IC

Scan-Based BIST Architecture
PS – Phase shifter
Scan-Forest
Scan-Trees
Scan-Segments (SC)
Weighted scan-
enables for SS
Compactor - EXORs
Copyright: D.Xiang 2003

Software BIST
Software based test generation: To reduce the hardware
overhead cost in the BIST
SoC CPU Core ROM
applications the hardware LFSR
LFSR1: 001010010101010011
load (LFSRj); N1: 275 can be replaced by software
for (i=0; i<Nj; i++)
... LFSR2: 110101011010110101
end; N2: 900
...
Software BIST is especially
attractive to test SoCs,
because of the availability of
Core j+... computing resources
Core j Core j+1
directly in the system (a
typical SoC usually contains
at least one processor core)
The TPG software is the same for all cores and is stored as a single copy
All characteristics of the LFSR are specific to each core and stored in the ROM
They will be loaded upon request.
For each additional core, only the BIST characteristics for this core have to be stored

Problems with BIST
The main motivations of Problems:
using random patterns • Very long test
are: application time
- low generation cost • Low fault
- high initial efeciency coverage
• Area overhead
• Additional delay
Fault Coverage
Possible solutions
• Weighted
Fault Coverage
pseudorandom test
• Combining
pseudorandom test
with deterministic test
– Multiple seed Time
– Bit flipping
Time
• Hybrid BIST

Problems with BIST: Hard to Test Faults
The main motivations
of using random Problem: Low fault coverage
patterns are:
Pseudorandom
Patterns from LFSR: test window:
- high initial efeciency
1 2n-1
Hard
to test
faults
Fault Coverage
Dream solution: Find LFSR such that:

1 2n-1
Hard
to test
Time faults

Hybrid Built-In Self-Test
Deterministic patterns
Pseudorandom
SoC
ROM
patterns Hybrid test set contains
... ... pseudorandom and
PRPG
Core
deterministic vectors
...
. . . Pseudorandom test is improved

...
by a stored test set which is
specially generated to target the
BIST Controller
CORE UNDER
TEST random resistant faults
MISR Optimization problem:

Where should be this breakpoint?
Pseudorandom Test Determ. Test

Optimization of Hybrid BIST
Cost of BIST: CTOTAL =  k +  t(k) PR test
# faults
# tests
not
length needed
FAST estimation Total Cost detected
Number of remaining CTOTAL
faults after applying k k rDET(k) rNOT(k) FC(k) t(k)
pseudorandom test 1 155 839 15.6%
patterns rNOT(k) 104
2 76 763 23.2% 104
# faults Cost of 3 65 698 29.8% 100
k pseudorandom test 4 90 608 38.8% 101
patterns CGEN 5 44 564 43.3% 99
10 104 421 57.6% 95
20 44 311 68.7% 87
Cost of stored
50 51 218 78.1% 74
SLOW analysis test CMEM 100 16 145 85.4% 52
# tests  t(k) 200 18 114 88.5% 41
411 31 70 93.0% 26
PR test length k 954 18 28 97.2% 12
1560 8 16 98.4% 7
Number of pseudorandom 2153 11 5 99.5% 3
test patterns applied, k 3449 2 3 99.7% 2
min CTOTAL 4519 2 1 99.9% 1
4520 1 0 100.0% 0
Figure 2: Cost calculation for hybrid BIST
Pseudorandom Test Det. Test

Deterministic Test Length Estimation
Deterministic test (DT)
Fault coverage Pseudorandom test (PT)
Fast estimation for the
length of deterministic test:
F
100%
For each PT length i* we
F D k(i) FP Ek(i) determine
F* - PT fault coverage F*, and
- the imaginable part of DT
FDk(i) to be used for the
same fault coverage
Then the remaining part of DT
TDEk(i) will be the estimation of
ji i* T D Fk i
the DT length
T D Ek(i)
Pseudorandom
test length
Deterministic test length estimation

Calculation of the Deterministic Test Cost
Two possibilities to find the length of deterministic data for each

possible breakpoint in the pseudorandom test sequence:
ATPG based: Fault table based:
ATPG based approach
For each breakpoint of P- ATPG ATPG
sequence, ATPG is used
Fault table based approach
Detected Fault table
A deterministic test set with fault update
Faults
table is calculated
For each breakpoint of
P-sequence, the fault table is All PR patterns? All PR patterns?
updated for not yet detected
faults No Yes No Yes
End Next PR End
Next PR
FAST estimation pattern pattern
Only fault coverage is calculated
ATPG based approach
For each breakpoint of P-sequence, ATPG is used
ATPG based:
R1 R2 Rk Rk+1 Rk+2 Rn
ATPG T1 Faults Faults to be
T2 detected detected
Task for . by
Detected fault . by
Faults pseudo-
simulator . random deterministic
. patterns patterns
Tn
All PR patterns?
Tn+1
No Yes Task for New detected
Next PR End ATPG Tp faults
pattern

Fault table based approach
A deterministic test set with fault table is calculated
For each breakpoint of P-sequence, the fault table is updated
Fault table based: R1 R2 Rk Rk+1 Rk+2 Rn
ATPG T1
T2 Faults
detected Fault table
Task for .
By for full
Fault table fault .
deterministic
update simulator . pseudo- test
. random
Tn patterns
All PR patterns? Tn+1
Updated To be detected
No Yes fault Tp faults
Next PR End tabel
pattern

Experimental Data: HBIST Optimization
Finding optimal brakepoint in the pseudorandom sequence:

LOPT SOPT
LMAX SMAX
Optimized hybrid test process: Pseudorandom Test Det. Test
Circuit LMAX LOPT SMAX SOPT Bk CTOTAL

C432 780 91 80 21 4 186
C499 2036 78 132 60 6 386
C880 5589 121 77 48 8 481
C1355 1522 121 126 52 6 388
C1908 5803 105 143 123 5 612
C2670 6581 444 155 77 30 26867
C3540 8734 297 211 110 7 889
C5315 2318 711 171 12 23 985
C6288 210 20 45 20 4 100
C7552 18704 583 267 61 51 2161

Hybrid BIST with Reseeding
The motivation of using Problem: low fault coverage  long PR test
random patterns is:
Pseudorandom
- high initial efeciency
test:
1 2n-1
Hard
to test
faults
Fault Coverage
Pseudorandom
Solution: many seeds: test:
1 2n-1
Time

Store-and-Generate Test Architecture
Seeds
ROM TPG UUT
RD
ADR Pseudorandom test windows
# seeds Window
Counter 2 Counter 1 CL
Seeds
• ROM contains test patterns for hard-to-test faults
• Each pattern Pk in ROM serves as an initial state of the LFSR for test pattern
generation (TPG) - seeds
• Counter 1 counts the number of pseudorandom patterns generated starting
from Pk - width of the windows
• After finishing the cycle for Counter 2 is incremented for reading the next
pattern Pk+1 – beginning of the new window

HBIST Optimization Problem
Pseudorandom test: Pseudo-

Using many seeds: random
Seed 1
1 2n-1 sequences:
L
Seed 2
Block
size:
Problems: Deterministic
How to calculate the test (seeds): 100% FC
number and size of Seed 1
M
blocks? Seed 2
Constraints
Which deterministic Seed n
patterns should be the Seed n
seeds for the blocks?
Minimize L at given M and 100% FC

Hybrid BIST Optimization Algorithm 1
D-patterns are ranked
Pseudorandom
Algorithm is based on
ATPG patterns sequence D-patterns ranking
Deterministic test patterns
Pattern selection
PRi with 100% quality are
generated by ATPG
The best pattern is selected
FC(PRi) as a seed
Detected faults subtraction,
optimization of ATPG patterns
A pseudorandom block is
Modified produced and the fault table
ATPG pattern of ATPG patterns is updated
table
The procedure ends when
100% fault coverage is
achieved

Hybrid BIST Optimization Algorithm 2
P-blocks are ranked
Algorithm is based on
P-blocks ranking
Deterministic test patterns
PT* with 100% quality are
generated by ATPG
PTmin
All P-blocks are generated
… for all D-patterns and
ranked
The best P-block is selected
includeed into sequence
… and updated
The procedure ends when
Deterministic test vector (seed) DTi 100% fault coverage is
Pseudorandom test sequence PRi
Pseudorandom sequence removed with the
achieved
block length optimization
Cost Curves for Hybrid BIST with Reseeding
Two possibilities for reseeding:
Constant block length (less HW overhead)
Dynamic block length (more HW overhead)
C1908
Test length L Memory cost M
10000 140
9000
L1(b) 120
8000
7000 100
6000
80
5000
L2(b)
60
4000
3000 40
2000
20
1000
M(b)
0 0
0 500 1000 1500 2000 2500 3000
Block size
b
Functional Self-Test
• Traditional BIST solutions use special hardware for pattern

generation on chip, this may introduce area overhead and
performance degradation
• New methods have been proposed which exploit specific functional
units like arithmetic blocks or processor cores for on-chip test
generation
• It has been shown that adders can be used as test generators for
pseudorandom and deterministic patterns
• Today, there is no general method how to use arbitrary functional
units for built-in test generation

Functional BIST Quality
Fault coverage of FBIST compared to Functional test
Functional testing Functional BIST Traditional
Data Functional
B1 B2 Total B1 B2 Total
FBIST
4/2 13.21 15.09 14.15 35.14 40.57 29.72 test
7/2 21.23 16.98 19.10 38.44 47.64 29.25 HW
6/3 19.34 31.6 25.47 41.04 39.62 42.45 overhead
UUT UUT
8/2 25.47 10.38 17.92 32.07 40.57 25.00
9/4 8.96 5.66 7.31 36.56 47.64 25.47
9/3 32.55 26.89 29.72 43.63 46.07 40.57 Result Result Signature
12/6 13.44 8.02 18.87 36.08 39.62 32.55
14/2 18.16 25.00 11.32 37.50 49.06 25.94
 
15/3 29.48 31.13 27.83 47.88 50.00 45.75 Go/NoGo Go/NoGo
2/4 7.8 7.55 8.02 29.01 20.75 33.02
Aver. 18.96 17.83 17.97 37.74 42.15 32.97 Reference Reference
Gain 1.0 1.0 1.0 2.0 2.4 1.8
FBIST: collection and analysis of samples during the working mode

Fault coverage is better, however, still very low (ranging from 42% to 70%)
Example: Functional BIST
Functional BIST quality analysis
Samples from N=120 cycles
SB=105 K*N
Fault
simulator
Register
block Functional
ALU test
Control Data Fault
compression: coverage
DB=64 N*SB / DB = 197

Test patterns (samples) are
Signature analyser produced on-line
K during the working mode
Data

Hybrid Functional BIST
• To improve the quality of FBIST we introduce the

method of Hybrid FBIST
• The idea of Hybrid FBIST consists in using for test
purposes the mixture of
– functional patterns produced by the microprogram (no
additional HW is needed), and
– additional stored deterministic test patterns to improve the total
fault coverage (HW overhead: MUX-es, Memory)
• Tradeoff should be found between
– the testing time and
– the HW/SW overhead cost

Functional Hybrid Self-Test
Functional BIST implementation
MUX
Automatic
M Test Pattern
Generator
Register ALU Deterministic

block test set
Random
resistant
faults
Test patterns are

Signature analyser stored in the
K memory
Data
Cost Functions for Hybrid Functional BIST
Cost
Total cost:
CTotal = CFB_Total +CD_Total
CTotal = CFB_Total +CD_Total
Opt.
The cost of functional test part: cost
CFB_Total = CFB_Const + CFB_T + CFB_M
CFB_T + CFB_M
The cost of deterministic test part: CD_T + CD_M
CD_Total = CD_Const + CD_T + CD_M CD_Const
Length of
CFB_Const FBIST
CFB_Const, CD_Const - HW/SW overhead Opt. length

CFB_T, CD_T - testing time cost
,  - weights of time and
memory expenses
Problem: minimize CTotal

Functional Self-Test with DFT
Example: N-bit multiplier Improving T
controllability
N cycles
MUX
F
Register ALU
block
Improving
EXOR observability
Signature analyser
K
Data

Hybrid BIST for Multiple Cores
Embedded tester for testing multiple cores
Embedded Tester
C2670 C3540
Test Test access

Controller BIST mechanism BIST
Tester
Memory
BIST BIST BIST
C1908 C880 C1355
SoC

Hybrid BIST for Multiple Cores
How to pack
knapsack?
How to
compress the
test sequence?
Pseudorandom test (PT)

Multi-Core Hybrid BIST Optimization
Cost of BIST: CTOTAL =  k +  t(k)

FAST estimation Total Cost
Number of remaining CTOTAL
faults after applying k
pseudorandom test
patterns rNOT(k)
# faults Cost of
k pseudorandom test
patterns CGEN Two problems:
1) Calculation of DT cost is
Cost of stored
SLOW analysis test CMEM difficult
# tests  t(k) 2) We have to optimize n (!)
processes
PR test length k
Number of pseudorandom How to avoid the calculation of
test patterns applied, k
min CTOTAL the very expensive full DT cost
Figure 2: Cost calculation for hybrid BIST curve?

Deterministic Test Length Estimation
Fault coverage Pseudorandom test (PT)
Solution of the first
problem:
F
100%
For each PT length i* we
F D k(i) FP Ek(i) determine
F* - PT fault coverage F*, and
- the imaginable part of DT
FDk(i) to be used for the
same fault coverage
Then the remaining part of DT
TDEk(i) will be the estimation of
ji i* T D Fk i
the DT length
T D Ek(i)
Pseudorandom
test length
Deterministic test length estimation for a single core

Deterministic Test Cost Estimation
Total cost calculation of core costs:
8000
DT cost Memory usage: 5357 bits
Core name: Memory usage: Deterministic

time:
Mem ory Constraint c499 1353 33
8
6000
Constraint c880
c1355
480
1025 25
c1908 363 11
c5315 2136 12
5500 c6288 0 0
c432 0 0
4000
Real cost
Estimated Cost
Memory (bits)
Real Cost
Core costs
Cost Estimates
for Individual Cores
2000
Estimated cost
Total
test
0
500 542 1000 Total Test Lenght (clocks) 1500
length
Solution
Total Test Cost Estimation
Using total cost solution

we find the PT length:
COST
E
COST T,k Using PT length, we calculate
DT cost Total cost
the test processes for all cores:
Total cost
E* c432 4 205
COST
solution
T
Deterministic
Pseudorandom
Solution c6288 4 2 203
c880 6 13 190 Total Test
PT costE Pseudorandom test c1908 19 21 169
COST D,k (PT) length

COSTP,k c5315 40 46 123
c1355 86 50 73
j c499 136 48 25
jmin j*k 0 50 100 150 200
PT length solution
Multi-Core Hybrid BIST Optimization
Iterative optimization process:
1 - First estimation
1* - Real cost calculation
2 - Correction of the estimation
2* - Real cost calculation
3 - Correction of the estimation
3* - Final real cost

Optimized Multi-Core Hybrid BIST
Pseudorandom test is carried out in parallel,
deterministic test - sequentially

Test-per-Scan Hybrid BIST
Every core’s BIST logic is capable to produce a set of independent pseudorandom test
The pseudorandom test sets for all the cores can be carried out simultaneously
s3271 s298
Deterministic
Scan Path Scan Path
tests can only
Em bedded Tester Scan Path Scan Path
be carried out
LFSR
LFSR
LFSR
LFSR
Scan Path Scan Path
Test Scan Path Scan Path TAM for one core at a
C ontroller
time
Only one test
Tester
Mem ory access bus at
the system level
Scan Path Scan Path is needed.
LFSR
LFSR
LFSR
LFSR
Scan Path Scan Path
Scan Path Scan Path
Scan Path Scan Path
s1423 s838
SoC

Bus-Based BIST Architecture
• Self-test control broadcasts patterns to each CUT over bus –

parallel pattern generation
• Awaits bus transactions showing CUT’s responses to the
patterns: serialized compaction
Broadcasting Test Patterns in BIST
Concept of test pattern sharing via novel scan structure – to
reduce the test application time:
... ... ... ...

CUT 1 CUT 2 CUT 1 CUT 2
Traditional single scan design Broadcast test architecture
While one module is tested by its test patterns, the same test
patterns can be applied simultaneously to other modules in the
manner of pseudorandom testing

Examples of connection possibilities in Broadcasting BIST:
CUT 1 CUT 2 CUT 1 CUT 2
j-to-j connections Random connections

Scan configurations in Broadcasting BIST:
Scan-In Scan-In
... ... ... ...

CUT 1 ... CUT n CUT 1 CUT n
... ... ... ...

MISR MISR 1 MISR n
Scan-Out Scan-Out
Common MISR Individual and multiple MISRs

Fault-Model Free Fault Diagnosis
Combined cause-effect and Effect
effect-cause diagnosis
Effect Faulty
area
Cause
Faulty
Faulty 2) Effect-Cause block
area Fault Diagnosis
Cause
Faulty block is located in the
suspected faulty area
Faulty system
Fault
1) Cause-Effect
3) Fault Reasoning
Fault Diagnosis
Failing test patterns are mapped
Suspected faulty area is Failing
into the suspected defect or into a
located test
set of suspected defects in the Test patterns
faulty block
Embedded BIST Based Fault Diagnosis
Pseudorandom test
BISD scheme:
sequence:
Test Pattern Generator
(TPG) BISD
Control Unit
......
Circuit Under Diagnosis

(CUD) Test patterns
Pattern Signature Faults
............ ............. .......
............ ............. .......
...... ............ ............. ....... Diagnostic Points (DPs) –
............ ............. .......
............ ............. ....... patterns that detect new faults
Output Response
Analyser
............ .........
............. .......
.... .......
Further minimization of DPs –
(ORA) ............ ............. .......
............ ............. ....... as a tradeoff with diagnostic
resolution

May 11-14, 2008 26th International Conference on Microelectronics, Niš, Serbia 4/20
Built-In Fault Diagnosis
Diagnosis procedure:
Test Pattern Generator 1. test 2. test 3. test
(TPG) BIST
Control Unit
...... Faulty
signature
Circuit Under Test

(CUT) Test patterns 3. test
Number Signature Faults
............ ............. ....... Correct
...... ............
............
.............
.............
.......
....... signature
............ ............. .......
............ ............. .......
Output Response ............ ............. .......
Analyser (ORA) ............ ............. .......
............ ............. .......
Faulty signature

Pseudorandom test fault Binary search with

simulation bisectioning of test patterns
№ All faults New faults Coverage 5

1 5 5 16.67%
2 15 10 50.00% 2 8
3 16 1 53.33%
4 17 1 56.67% 1 3 6 9
5 20 3 66.67%
6 21 1 70.00% 1 4 1 7 3 10
5 10
7 25 4 83.33%
1 3 4 1 1
8 26 1 86.67%
9 29 3 96.67%
10 30 1 100.00% Average number of test sessions: 3,3
Average number of clocks: 8,67

Pseudorandom test fault Binary search with

simulation bisectioning of faults
№ All faults New faults Coverage 2

1 5 5 16.67%
2 15 10 50.00% 1 6
3 16 1 53.33% 5
5 10 8
4 17 1 56.67%
5 20 3 66.67% 4 1 7 9
6 21 1 70.00%
7 25 4 83.33% 3 3 4 1 10
3
8 26 1 86.67%
9 29 3 96.67% 1 1 1
10 30 1 100.00%
Average number of test sessions: 3,06
Average number of clocks: 6,43

Diagnosis with multiple signatures:
SA1
Test pattern generator
SA2
D3
Fault D2
D1
CUD
D7
D5 D6
SA3
D4
SA1 SA2 SA3

Diagnosis with multiple signatures:
No Codeword Diagnosis
Diagnostic tree
h 0 0 1 R1
R1’’’
i 0 0 1 R1’’’ R1’, R2’, R3’

h R1
F/001
j F/001
0 1 1 R2 P
i
v
F/011
k 0 1 1 R1’’, R2’’ P
F/111 j R2
k
F/011
l 1 1 1 R3
P
l R3
F/111
R1’’, R2’’
v 1 1 1 R1’, R2’, R3’

BIST with multiple Faulty
signature analyzers signature
Test pattern generator Intersection

using tests Correct
signature
Fault
CUD Faulty signature
SA1
SA2
D3
D1 D2
SA1 SA2 SA3 Intersection D7

using SA-s D5 D6
SA3
Optimization of the interface between D4
CUD and SA-s

1 SA Resolution 5 SA Resolution 10 SA Resolution
1 SA Test length 5 SA Test length 10 SA Test length
240.0 65.0
230.0
220.0 60.0 Diagnosis with multiple
210.0
200.0 55.0 signatures:
190.0
180.0 Gain in 50.0
170.0 speed of
160.0 diagnosis 45.0
150.0
Average test length

Average resolution
140.0 40.0 Measured:

130.0
120.0 35.0 - average resolution
110.0 Optimal
100.0 30.0
- average test length
number of
90.0
80.0
failed 25.0
70.0 patterns Compared: 1SA, 5SA, 10SA
60.0 20.0
50.0
40.0 15.0
30.0 Gain in test length: 6 times
20.0 10.0
10.0
0.0 5.0
1 2 3 4 5 6 7 8 9 10 ALL
Failed patterns

Extended Fault Models
Extensions of the parallel critical path tracing for two large

general fault classes for modeling physical defects:
Multiple
fault
Resistive bridge fault
0
Defect
1
0
1
SAF
X-fault
Conditional fault Byzantine fault
Pattern fault Bridges
Constrained SAF Stuck-opens
Single faulty signal Multiple faulty signal
Diagnosis of Fault Model Free Defects
Real test
experiment Simulation
Circuit Under Faulty machine

Diagnosis FM(f) Fault evidence:
t for test pattern t
t e(f,t) = (t , t, lt, t)

f
t = min (t, lt)
lt Fault for full test T (sum)
e(f,T) = ( , , l, )
Test pattern t
Copyright: H.J.Wunderlich 2007

Real test
experiment Simulation Different classical fault cases
Circuit Under Faulty machine lt t t

Classic model
Diagnosis FM(f)
t Single SAF 0 0 0
t f Multiple SAF 0 >0 0
Single conditional SAF >0 0 0
lt Fault
Multiple cond. SAF >0 >0 0
Delay fault >0 0 >0
General case >0 >0 >0
Test pattern t

Real test Ranking

Simulation
experiment (on the top the most Example:
Circuit Under Faulty machine suspicious faults):
Diagnosis FM(f) SAF T T lT
(1) By increasing T
t f1 0 42 0
(single SAF on top)
t f
(2) If T are equal then
f2 30 42 15
f3 30 42 25
lt Fault by decreasing T
f4 30 42 30
(3) If T and T are
f5 30 36 38
equal then by
Test pattern t
increasing lT f6 38 23 22
f7 38 23 23
t = min (t, lt)

Fault Diagnosis Without Fault Models
RT Level
Logic level
R1
Transistor level M1
& & +
Reverse & M3 R2
& 1 M2
defect &
IN *
mapping &
x1 x4
System level
x2 Defect
x3 x5 dy
Wd Defective
area
Error
Logic level detection
Error (defective area) diagnosis

Fault Model Free Fault Diagnosis
System network graph Diagnostic table
1 2 3 4
Test response:
1 0 1 0 No match 1 1
2 1
S1 S2 S3 S4
3 1
4 1
Because of the
S5 S6 S7 unidirectional 5 1 1 0
“distortions” of test
6 1
responses,
rectification is 7 1
S8 S9 S10 possible
8 1 1 0
9 1
S11
10 1 1
Diagnosis: s11 Rectified code 11 1 1 1 0
1 ESTONIA
Technical University Tallinn, 0 1 0
Fault Tolerance: Error Detecting Codes
System
Checker Not eligible code
Parity bit
Examples:
Decimal digits: Parity check: 00 0 0 1
01 1 3 2
10 1 5 4
Eligible: 0,1,2,..., 9 11 0 6 7
Not eligible: 10,11,..., 15
Eligible
Not
eligible
Error Detecting/Correcting Codes
Minimal number of bits
Hamming distance between codes: how two codes differ
from each other
d
Eligible
codes Parity bit
110
100 Parity check: 00 0 0 1
01 1 3 2
101 111 011
d=2 10 1 5 4
Eligible 001 11 0 6 7
codes 000
010
Eligible
Not
eligible
Not eligible codes

Error Detecting/Correcting Codes
Error detecting codes: Error correcting codes:

Error correction is
d=2 Error possible: direction
Eligible
detection: is known
codes
direction
d=3
unknown
Eligible
codes
Eligible
codes
Detection
not possible
Correction
Not eligible codes not possible

Fault Tolerance: Error Correcting Codes
d = 2e + 1 - 2e - error detection
e - error correction
One error correction code: 2c  q + c + 1

Check bits
Error free
q c
For addressing of the
Information bits erroneous bit

Fault Tolerance: One Error Correcting Code
One error correction code: 2c  q + c + 1
Calculation of check sums:
bc+q b2 b1  bk  0, i  1,..., c
kPi
7 6 5 4 3 2 1 Pi – number of bits where bi = 1
P1 = b1  b3  b5  b7 = 0
Check bits
P2 = b2  b3  b6  b7 = 0
b2i, i = 0,1,,...,c-1 P3 = b4  b5  b6  b7 = 0

Fault Tolerance: One Error Correcting Code
Analogy with fault diagnosis
Location of erroneous bit: by using fault table:
1 0 1 0 1 0 0 Initial code
7 6 5 4 3 2 1
1 0 1 1 1 0 0 Received code
Check bits Test
b2i, i = 1,...,c 7 6 5 4 3 2 1 0
P1 1 1 1 1 0
P1 = b1  b3  b5  b7 = 0 P2 1 1 1 1 0
P2 = b2  b3  b6  b7 = 0 P3 1 1 1 1 1
P3 = b4  b5  b6  b7 = 0
Check bits have to be independently assigned Diagnosis

Fault Tolerant Communication System
Initial code
Error
indication
Check-bits
generator Sender Receiver Checker
Error
Error
correction correction
code (restoring)
Received
correct code

Error Detection in Arithmetic Operations
Check bits
Residue codes
Information bits
N – information bits
C = (N) mod m - check bits I2 I1 I0 I c c1 c0
m – residue of the code 0 0 0 0 0 0 0
p = log2 m  – number of check bits 0 0 1 1 1 0 1
0 1 0 2 2 1 0
Example 0 1 1 3 0 0 0
Information bits: I2, I1, I0 1 0 0 4 1 0 1
m = 3, p = 2 1 0 1 5 2 1 0
Check bits: c1, c0
1 1 0 6 0 0 0
1 1 1 7 1 0 1

Addition: Multiplication:
Information bits Check bits Information bits Check bits
0 0 1 0 1 0 2.2 0 0 1 0 1 0 2.2
0 1 0 0 0 1 4.1 0 1 0 0 0 1 4.1
0 1 1 0 1 1 6.3 1 0 0 0 1 0 8.2
(6)mod3 = 0 (3)mod3 = 0 (8)mod3 = 2 (2)mod3 = 2
Information bits Check bits Information bits Check bits

0 0 1 0 1 0 2.2 0 0 1 0 1 0 2.2
0 1 0 0 0 1 4.1 0 1 0 0 0 1 4.1
0 1 0 0 1 1 4.3 1 0 0 1 1 0 9.2
(4)mod3 = 1 (3)mod3 = 0 (9)mod3 = 0 (2)mod3 = 2
Error! Error!
Check
A B bit C(A) C(B)
generator
Adder Adder mod m
A+B (C(A) + C(B)) mod m
Residue Error
Comparator
calculator C(A + B) indicator

Summary
• LFSR pattern generator and MISR response
compactor – preferred BIST methods
• BIST has overheads: test controller, extra circuit
delay, Input MUX, pattern generator, response
compactor, DFT to initialize circuit & test the test
hardware
• 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

Testing of Networks-on-Chip (NoC)
• Consider a mesh-like topology of NoC consisting of

– switches (routers),
– wire connections between them and
– slots for SoC resources, also referred to as tiles.
• Other types of topological architectures, e.g. honeycomb and
torus may be implemented and their choice depends on the
constraints for low-power, area, speed, testability
• The resource can be a processor, memory, ASIC core etc.
• The network switch contains buffers, or queues, for the incoming
data and the selection logic to determine the output direction,
where the data is passed (upward, downward, leftward and
rightward neighbours)

Testing of Networks-on-Chip
• Useful knowledge for testing NoC network structures can be obtained from
the interconnect testing of other regular topological structures
• The test of wires and switches is to some extent analogous to testing of
interconnects of an FPGA
• a switch in a mesh-like communication structure can be tested by using only
three different configurations

Concatenated bus • Arbitrary short and open in an

concept n-bit bus can be tested by
log2(n) test patterns
• When testing the NoC
interconnects we can regard
mxm different paths through the
matrix interconnect structures as
one single concatenated bus
• Assuming we have a NoC,
whose mesh consists of
m x m switches, we can
view the test paths through
the matrix as a wide bus of
2m buses
2mn wires

Concatenated bus • The stuck-at-0 and stuck-at-1

concept faults are modeled as shorts
to Vdd and ground
• Thus we need two extra
wires, which makes the total
bitwidth of the bus
mxm
matrix 2mn + 2 wires.
• From the above facts we can
find that
3[log2(2mn+2)]
test patterns are needed in
order to test the switches and
the wiring in the NoC
2m buses

3[log2(2mn+2)] Bus Test Detected faults

test patterns
needed 0 000 Stuck-at-1
1 001
2 010
All
6 wires 3 011 opens
tested and
4 100
shorts
5 101
6 110
7 111 Stuck-at-0

IEEE P1500 standard for core test
• The following components are generally required to
test embedded cores
– Source for application of test stimuli and a sink for observing
the responces
– Test Access Mechanisms (TAM) to move the test data from
the source to the core inputs and from the core outputs to the
sink
– Wrapper around the embedded core
test test
embedded
pattern TAM TAM responces’
source core sink
wrapper

• The two most important components of the P1500
standard are
– Core test language (CTL) and
– Scalable core test architecture
• Core Test Language
– The purpose of it is to standardize the core test knowledge
transfer
– The CTL file of a core must be supplied by the core provider
– This file contains information on how to
• instanciate a wrapper,
• map core ports to wrapper ports,
• and reuse core test data

Core test architecture
• It standardizes only the wrapper and the interface between the
wrapper and TAM, called Wrapper Interface Port or (WIP)
• The P1500 TAM interface and wrapper can be viewed as an
extension to IEEE Std. 1149.1, since
– the 1149.1 TAP controller is a P1500-compliant TAM interface,
– and the boundary-scan register is a P1500-compliant wrapper
• Wrapper contains
– an instruction register (WIR),
– a wrapper boundary register consisting of wrapper cells,
– a bypass register and some additional logic.
• Wrapper has to allow normal functional operation of the core
plus it has to include a 1-bit serial TAM.
• In addition to the serial test access, parallel TAMs may be used.

Off-chip or
Source/Sink
(Stimuli/Responses) On-chip
User-defined test access mechanism (TAM) On-chip
WPI WPO WPI WPO

Functional Functional
P1500 wrapper inputs/ P1500 wrapper
inputs/
outputs outputs
Core 1 Core n
WSI WSO WSI WSO

WIR WIR
P1500 Wrapper interface port (WIP)

System chip

Theory of LFSR: Galois Field
LFSR as a Galois field:

 Galois field (mathematical system) G(pn):
 Multiplication by x same as right shift of LFSR
 Addition operator is XOR (  )
 Ts companion matrix:
 1st column 0, except n-th element which is always 1
(X0 always feeds Xn-1)
 Rest of row n – feedback coefficients hi
 Rest is identity matrix I – means a right shift
• Near-exhaustive (maximal length) LFSR
 Cycles through 2n – 1 states (excluding all-0)
 one pattern of n 1’s, two of n-1 consecutive 0’s

Built in Self-Test: 2. Testability Measuring 3. Design For Testability

Uploaded by

Copyright:

Available Formats

Built in Self-Test: 2. Testability Measuring 3. Design For Testability

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Built in Self-Test: 2. Testability Measuring 3. Design For Testability

Uploaded by

Copyright:

Available Formats

Overview

Technical University Tallinn, ESTONIA

Technical University Tallinn, ESTONIA

Technical University Tallinn, ESTONIA

Technical University Tallinn, ESTONIA

Technical University Tallinn, ESTONIA

Technical University Tallinn, ESTONIA

Technical University Tallinn, ESTONIA

Core 3 Core 4 Core 5

Technical University Tallinn, ESTONIA

• Motivations for BIST:

Technical University Tallinn, ESTONIA

• Increasing chip logic-to-pin ratio – harder observability

Technical University Tallinn, ESTONIA

• Useful for field test and diagnosis (less expensive

Technical University Tallinn, ESTONIA

Level Design Fabri- Manuf. Maintenance Diagnosis Service

Technical University Tallinn, ESTONIA

 Chip area overhead for:

Technical University Tallinn, ESTONIA

Technical University Tallinn, ESTONIA

Technical University Tallinn, ESTONIA

Technical University Tallinn, ESTONIA

Source: VLSI Test: Bushnell-Agrawal Technical University Tallinn, ESTONIA

Technical University Tallinn, ESTONIA

IN OUT The complexity of testing is a function

Technical University Tallinn, ESTONIA

Scan-Path Register • 1 10 0 1 0 1 0 01 01 1001

Technical University Tallinn, ESTONIA

Technical University Tallinn, ESTONIA

Source: VLSI Test: Bushnell-Agrawal Technical University Tallinn, ESTONIA

Technical University Tallinn, ESTONIA

Pseudorandom Test generation by LFSR:

Technical University Tallinn, ESTONIA

• LFSR – Linear feedback shift register, hardware that generates

Technical University Tallinn, ESTONIA

• Irreducible polynomial – Boolean polynomial that cannot be factored

Technical University Tallinn, ESTONIA

Technical University Tallinn, ESTONIA

Technical University Tallinn, ESTONIA

Technical University Tallinn, ESTONIA

LFSR – Linear Feedback Shift Register:

Technical University Tallinn, ESTONIA

X (t + 1) = Ts X (t) (Ts is companion matrix)

Technical University Tallinn, ESTONIA

Technical University Tallinn, ESTONIA

• Irreducible polynomial – cannot be factored, is divisible

Technical University Tallinn, ESTONIA

Polynomials of degree n=3 (examples): k = 2n – 1= 23 – 1=7

x3  x 2  1 The polynomials will divide evenly the polynomial x7 + 1,

Reducible polynomials (non-primitive):

x 3  1  ( x  1)( x 2  x  1) The polynomials don’t divide

Technical University Tallinn, ESTONIA

Comparison of test sequences generated:

Technical University Tallinn, ESTONIA

Is x4  x2 1 a primitive polynimial? Divisibility check:

0001 1001 0110 0001 1011 1001

Technical University Tallinn, ESTONIA