Chapter 6

Design for Testability and

Built-In Self-Test

Jin-Fu Li
Advanced Reliable Systems (ARES) Lab.
Department of Electrical Engineering
National Central University
Jungli, Taiwan

Outline
Basics
Design-for-Testability (DFT) Techniques
Ad Hoc DFT
Structural Methods

Scan
Partial Scan
BIST
Boundary Scan
Syndrome-Testable Design
C-Testable Design

Built-In Self-Test (BIST) Techniques

Signature Analysis
Pseudorandom Pattern Generator (PRPG)
Built-In Logic Block Observer (BILBO)

Summary
Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

Definitions
Definition
A fault is testable if there exists a well-specified
procedure to expose it, which is implementable with
a reasonable cost using current technologies. A
circuit is testable with respect to a fault set
when each and every fault in this set is testable

Definition
Design for testability (DFT) refers to those
design techniques that make test generation and
test application cost-effective

Electronic systems contain three types of

components: (a) digital logic, (b) memory
blocks, and (c) analog or mixed-signal circuits
In this chapter, we discuss DFT techniques for
digital logic
Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

Ad Hoc DFT Guidelines

Partition large circuits into smaller subcircuits
to reduce test generation cost (using MUXed
and/or scan chains)

Mode

T1 T2

Normal
Test C1
Test C2

C1

C2

T1 T2

0
0
1

0
1
0

Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

Ad Hoc DFT Guidelines

Insert test points to enhance controllability &
observability
Test points: control points & observation points
OP
C1
0

CP1

C2

C2
CP2

Advanced Reliable Systems (ARES) Lab.

CP3

Jin-Fu Li, EE, NCU

CP4

Ad Hoc DFT Guidelines

Design circuits to be easily initializable
Provide logic to break global feedback paths
Partition large counter into smaller ones
Avoid the use of redundant logic
Keep analog and digital circuits physically
apart
Avoid the use of asynchronous logic
Consider tester requirements (pin limitation,
etc)
Etc

Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

Scan Design Approaches

They are effective for circuit partitioning
They provide controllability and observability
of internal state variables for testing
They turn the sequential test problem into a
combinational one
Four major approaches

Shift-register modification
Scan path
Level-sensitive scan design (LSSD)
Random access

Circuit is designed using pre-specified design

rules.
Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

Scan Design Approaches

Consider a representation of sequential circuits
(primary inputs)

(primary outputs)

Combinational Logic

Y (next state)

(present state) y

clk

state

To make elements of state vector controllable

and observable, we add

A
A
A
A

TEST mode pin (T)

SCAN-IN pin (SI)
SCAN-OUT pin (SO)
MUX (switch) in front of each FF (M)

Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

Adding Scan Structure

PI

PO
Combinational

SFF

logic

SFF

SCAN-OUT

SFF

T
SCAN-IN
Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

Scan Test Generation & Design Rules

Test pattern generation
Use combinational ATPG to obtain tests for all
testable faults in the combinational logic
Add shift register tests and convert ATPG tests into
scan sequences for use in manufacturing test

Scan design rules

Use only clocked D-type of flip-flops for all state
variables
At least one PI pin must be available for test; more
pins, if available, can be used
All clocks must be controlled from PIs
Clocks must not feed data inputs of flip-flops

Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

10

Correcting a Rule Violation

All clocks must be controlled from PIs
Comb.
logic D1
D2
CK

Q
FF

Comb.
logic

Comb.
logic
Q

D1
D2

FF

CK

Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

Comb.
logic
11

Correcting a Rule Violation

Adding a scan FF and a mux allows a feedback loop to

be opened for testing

FF
Test

CK

Freq. Divider

CK

Freq. Divider

Test

FF
Advanced Reliable Systems (ARES) Lab.

FF

CK

FF

Testing derived clocks requires the use of a mux to

bypass the division stages

Jin-Fu Li, EE, NCU

FF
12

Correcting a Rule Violation

The AND gates keep the bus drivers from
being activated by the normal logic during
testing

FF

FF

FF

FF

Test

Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

13

Scan Test Procedure

Step 1: Switch to the shift-register mode and
check the SR operation by shifting in an
alternating sequence of 1s and 0s, e.g., 00110
(functional test)
Step 2: Initialize the SR---load the first
pattern
Step 3: Return to the normal mode and apply
the test pattern
Step 4: Switch to the SR mode and shift out
the final state while setting the starting state
for the next test. Go to Step 3

Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

14

Combining Test Vectors

PI

I1

I2

O2

Combinational

SCAN-IN
T
Presen
t
state

O1

SCAN-OUT

logic
S1

N1

S2

Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

PO

N2

Next
state

15

Combining Test Vectors

SCAN-IN
T

I2

I1

PI

S1

Dont care
or random
bits

S2

0000000 1 0000000 1 0000000

PO

O2

O1

SCAN-OUT

N1

N2

Sequence length = (ncomb + 1) nsff + ncomb clock periods

ncomb = number of combinational vectors
nsff = number of scan flip-flops

Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

16

Testing Scan Register

Scan register must be tested prior to
application of scan test sequences
A shift sequence 00110011 . . . of length
nsff+4 in scan mode (TC=0) produces 00, 01,
11 and 10 transitions in all flip-flops and
observes the result at SCAN-OUT output
Total scan test length:
(ncomb+2)nsff+ncomb+4 clock periods
Example: 2,000 scan flip-flops, 500 comb.
vectors, total scan test length ~ 106 clocks
Multiple scan registers reduce test length
Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

17

Multiple Scan Registers

Scan flip-flops can be distributed among any
number of shift registers, each having a
separate SCAN-IN and SCAN-OUT pin
Test sequence length is determined by the
longest scan shift register
Just one test control (TC) pin is essential
T
SCAN-IN1

Scan Register 1

SCAN-OUT1

SCAN-IN1

Scan Register 2

SCAN-OUT2

SCAN-INK

Scan Register 3

SCAN-OUTK

Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

18

Hierarchical Scan
Scan flip-flops are chained within subnetworks
before chaining subnetworks
Advantages:
Automatic scan insertion in netlist
Circuit hierarchy preserved helps in debugging
and design changes

Disadvantage: Non-optimum chip layout

Scanin

SFF4

SFF1

Scanout
Scanin

SFF1

SFF3
Scanout

SFF2

SFF3

SFF4

Hierarchical netlist
Advanced Reliable Systems (ARES) Lab.

SFF2

Flat layout
Jin-Fu Li, EE, NCU

19

Optimum Scan Layout

X

X
IO
pad

SFF
cell
SCANIN

Flipflop
cell

SCAN
OUT

Routing
channels
Interconnects
Active areas: XY and XY
Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

20

Automated Scan Design

Rule
violations

Behavior, RTL, and logic

Design and verification
Scan design
rule audits

Gate-level
netlist

Combinational
ATPG

Scan hardware
insertion

Scan
netlist

Combinational
vectors
Scan sequence
and test program
generation

Test program

Advanced Reliable Systems (ARES) Lab.

Scan chain order

Design and test
data for
manufacturing

Jin-Fu Li, EE, NCU

Chip layout: Scanchain optimization,

timing verification

Mask data

21

An Example of DFT Compiler Flow

compile -scan

HDL

check_test

insert_scan

check_test

Pre-Scan
DRC

Insert Scan

Post-Scan
DRC

ScanReady
Synthesis

Constraints:
Scan style,
speed, area

Technology
Library:
Gates, flip-flops,
scan equivalents

Preview
Coverage

Constraint-Based
Scan Synthesis:
Routing, balancing,
gate-level
optimization
Source: H.-J. Huang, CIC

Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

22

Shift Registers
Scan added:
SHFT_IN
SI

SHFT_OUT/ SO

DFF

DFF

DFF

CLK
SE

Revised:
SHIFT_OUT

SHIFT_IN

DFF

SI
SE

DFF

DFF

CLK

Source: H.-J. Huang, CIC

Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

23

Lockup Latch Insertion

F1

F2

CLK_RTZ_1

F3

latch

tINV

CLK_RTZ_2

clk1

clk1

clk2

clk2

OK!

Big Problem !!
Rearrange clock domain or
insert lockup latch
Source: H.-J. Huang, CIC

Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

24

Random Access Scan

Uses addressable latches
Provides random access to FFs via
multiplexingaddress selection

C/L

C
SI
L

SO

Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

25

Random Access Scan

Random access scan cell
DI
CK1

C=CK1&CK2
Wire-AND

SI

+L

CK2
Addr

SO

Advantages
Fast; minimal impact on normal path
Fast for testingrandom access
Ability to watch a node in normal operation mode

Disadvantages
Hardware cost is large; more pins added
Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

26

Random Access Architecture

Combinational/Logic

clocks and controls

y-address

Y
decode
r

Si
Addressable
storage
..
.
elements

Sin
SCK
Sout

...
X decoder
x-address

During normal operation the storage cells operate in

their parallel-load mode
To scan in a bit, the appropriate cell is addressed,
the data are applied to sin
Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

27

Test Procedure
1. Set test input to all test points
[Link] the master reset signal to initialize all memory
elements
[Link] scan-in address and data, and then apply the scan
clock
[Link] step 3 until all internal test inputs are scanned
in
[Link] once for normal operation
[Link] states of the output points
[Link] the scan-out states of all memory elements by
applying appropriate X-Y signals
Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

28

Scan-Hold FFs (SHFFs)

HOLD=0Q & Q are fixed
SO
D

SI
TC

SFF
Q

CK

HOLD

The control input HOLD keeps the output

steady at previous state of flip-flop
Applications
Reduce power dissipation during scan, etc.
Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

29

Scan Enters the Nanometer Era

Trend in flip flop count with design size

[Source: EE Times]
Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

30

Scan Enters the Nanometer Era

Adaptive scan architecture

[Source: EE Times]
Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

31

Syndrome-Testable Design
Definition
S( f )

k( f )
2n

The syndrome of a Boolean function f is

,
where k is the number of 1s (minterms) in f and n
is the number of independent input variables
A typical syndrome testing set-up
(Counter)
Syndrome
register

CUT
Exhaustive
patterns

Comparator
Go/No-go
Reference
syndrome

0 S( f ) 1
A circuit is syndrome testable iff fault , S ( f ) S ( f )
Syndromes of logic gates
Gate

S
Advanced Reliable Systems (ARES) Lab.

ANDn
1 / 2n

ORn
1 (1 / 2 n )

XORn
1/2

Jin-Fu Li, EE, NCU

NOT
1/2
32

Syndrome Computation
Consider a circuit having 2 blocks, f and g,
with unshared inputs
O/P Gate

OR
S f Sg S f Sg

AND
XOR
NAND
S f S g S f S g 2 S f S g 1 S f Sg

NOR
1 S f Sg S f Sg

Example
Calculate the syndrome of the following circuit

S1
S2

S
S4

S3
Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

S1 = 1-1/4 = 3/4
S2 = 1-1/4 = 3/4
S3 = 1/8
S4 = 1- S2 - S3 + S2S3 = 7/32
S = S1S4 = 21/128

33

Syndrome-Testable Design
Consider the function f xz y z . The circuit is
syndrome untestable
S f 1/ 2
If the circuit has a fault z / 0 , then the
corresponding syndrome of the faulty circuit is S'f 1/ 2
Thus the circuit is syndrome untestable

A realization C of a function f is said to be

syndrome-testable if no single stuck-at fault
causes the circuit to have the same syndrome
as the fault-free circuit
Syndrome is a property of function, not of
implementation
Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

34

Syndrome-Testable Design
Definition
A logic function is unate in a variable xi if it can be
represented as an SOP or POS expression in which
the variable xi appears either only in an
uncomplemented form or only in a complemented
form
For example:

f ( x1 , x 2 ) x1 x 2 x1 x 2 no unate
f ( x1, x2 , x3 ) x1 x2 x2 x3 x1x3 unate in x2 , x3 , not unate

in x1

Theorem
A 2-level irredundant circuit realizing a unate
function in all its variables is syndrome testable
Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

35

Syndrome-Testable Design
Theorem
Any 2-level irredundant circuit can be made
syndrome-testable by adding control inputs to the
AND gates

For example
The function f xz y z is syndrome untestable
Now add a control input c f cxz y z , where
1
when in normal operation mode
C
normal i/p when in test mode
S 3 / 8, f y , and S 1 / 2 S Syndrome testable

Drawbacks
Only for combinational logic
Exhaustive; modification doubles test set size
Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

36

Introduction to Built-In Self-Test

Built-in self-test (BIST):
The capability of a circuit (chip/board/system) to
test itself

Advantages of BIST
Test patterns generated on-chip controllability
increased
(Compressed) response evaluated on-chip
observability increased
Test can be on-line (concurrent) or off-line
Test can run at circuit speed more realistic;
shorter test time; easier delay testing
External test equipment greatly simplified, or even
totally eliminated
Easily adopting to engineering changes
Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

37

Introduction to Built-In Self-Test

On-line BIST
Concurrent (EDAC, NMR, totally self-checking
checkers, etc.):
Coding or modular redundancy techniques (fault
tolerance)
Module 1
Module 2

Module N

Voter

Output

N-Modular Redundancy (NMR)

Instantaneous correction of errors caused by

temporary or permanent faults

Nonconcurrent (diagnostic routines):

Carried out while a system is in an idle state
Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

38

Introduction to Built-In Self-Test

Off-line BIST
A typical BIST architecture

PG

Functional Circuit
(Circuit Under Test)

RA

Go/No-Go

Controller
BIST

Test generation
Prestored TPG, e.g., ROM or shift register
Exhaustive TPG, e.g., binary counter
Pseudo-exhaustive TPG, e.g., constant-weight
counter, combined LFSR and SR
Pseudo-random pattern generator, e.g., LFSR
Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

39

Introduction to Built-In Self-Test

Response analysis

Check-sum
Ones counting
Transition counting
Parity checking
Syndrome analysis
Etc.

Linear feedback shift register (LFSR) can be

both the test generator and response analyzer
We need a gold unit to generate the good
signature or a simulator

Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

40

Signature Analysis
A compression technique based on the concept
of cyclic redundancy checking (CRC) and
realized in hardware using linear feedback
shift registers
Definition
A function f(x1,x2,,xn) is said to be linear if it can
be expressed in the form

f a 0 a1 x1 a 2 x 2 a n x n

where a i {0,1} i 0,1, , n

There are 2n+1 linear functions of n variables

Linear operations: modulo addition, module scalar
multiplication, & delay
Nonlinear operations: AND, OR, NAND, NOR, etc.
Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

41

Linear Feedback Shift Register

Definition
A linear feedback shift register is a shift
register with feedback paths which consist
only of unit delays and XOR operators

Let M=fault-free circuit response, B=faulty

circuit response, and E=error syndrome
(Hamming), where E=M Bthus M=B E
and B=M E
We need a circuit to take B as input and
compact it but still be able to tell if M!=B

LFSR is considered as a popular approach for

test response compaction
Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

42

Structures of LFSR
Two types of generic standard LFSRs

C1

D FF

C2

CN-1

D FF

D FF

D FF

Y1

Y2

C1

C2

YN-1

Advanced Reliable Systems (ARES) Lab.

YN

CN-1

D FF
Y1

CN

CN

D FF
YN-1

Y2
Jin-Fu Li, EE, NCU

YN
43

Mathematical Foundation of LFSR

As a function of time, Yj can be expressed as
Y j (t ) Y j 1 (t 1) for j 0
Hence Y j (t ) Y0 (t j )

If we denote the translation operator as Xk,

where k is the time translation unit
Y j (t ) Y0 (t ) X j
On the other
hand, Y0(t) can be expressed as
N
Y0 (t ) C jY j (t )

Then

j 1

Y0 (t ) C jY0 (t ) X j for 1 j N
j 1

Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

44

Mathematical Foundation of LFSR

We can rewrite the Y0(t) as
N

Y0 (t ) Y0 (t ) C j X

j 1

j
Also, Y 0 ( t )( C j X 1) 0
j 1

We can rewrite this expression as Y0 (t ) PN ( X ) 0

For nontrivial solution, Y0 (t ) 0 , we must have
PN (X ) 0
N

where PN ( X ) 1 C j X j
j 1

PN (X ) is called the characteristic polynomial of

the LFSR

Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

45

LFSR for Signature Analysis

A serial input stream mn, mn-1,, m1, m0
entering the LFSR can be considered as the
coefficients of a polynomial
n
n 1
m
(
X
)

m
X

m
X
m1 X m0

n
n 1

C0

C1

D FF

C2

Cr-1

D FF

D FF

m(X)
s1

Cr

s2

sr-1

q(X)
sr

The LFSR is said to have a characteristic polynomial

defined as follows
c( X ) cr X r cr 1 X r 1 c1 X c0
Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

46

LFSR for Signature Analysis

Assume that the initial state of the LFSR is
Di=0, i=0,,r-1, then the LFSR effectively
divides any m(X) by c(X), i.e.,
m ( X ) q( X ) C ( X ) s( X )

The quotient q(X) appears serially at the

output of the SR. The remainder s(X) is in the
SR after n+1 shifts:
r
r 1
s ( X ) sr X sr 1 X s1 X s0

Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

47

An Example
The following LFSR divides any m(X) by
c(X)=X5+X4+X2+1

m(X)

D0

D1

D3

D2

D3

q(X)

Suppose m(x)=X7+X6+X5+X4+X2+1, then

q(X)=X2+1, and s(X)=X4+X2
I/P
10101111
101
10
1
Advanced Reliable Systems (ARES) Lab.

D0 D1 D2 D3 D4
0
0
0
0
0

0
1
0
0
0

0
1
0
0
1

0
1
1
0
0

0
1
0
1
1

Jin-Fu Li, EE, NCU

O/P
1
01
101
48

Signature Analysis
Let m(X) be the input polynomial of degree k-1, q(X)
the quotient, and s(X) the signature (remainder).
Then
m(X)=q(X)c(X)+s(X)
The error syndrome can be represented as a
polynomial e(X)
E.g., le m(X)=X4+X3+1(11001), and an erroneous
input b(X)=X3+X+1(01011), then the error
syndrome is 11001 01011=10010, and is
represented by e(X)=X4+X
In general, an erroneous input polynomial can be
represented by
B(X)=m(X)+e(X)

Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

49

Signature Analysis
Theorem1: Input streams m(X) and b(X) have the
same signature iff e(X) is a multiple of c(X)
Proof: an error is not detected when m(X) and b(X) have
the same signature, i.e., b(x)=q(X)c(X)+s(X). Since
m(X)=q(X)c(X)+s(X), we obtain
e(X)=m(X)+b(X)=c(X)(q(X)-q(X))

Theorem2: Undetected errors correspond to error

patterns which are multiples of c(X)
Theorem3: If c(X) has 2 or more nonzero
coefficientsi.e., at least 1 feedback termthen it
can detect all single-bit errors
Proof: all nonzero multiples of c(X) must have at least 2
nonzero coefficients. Therefore, any error with only 1
nonzero coefficient cannot be a multiple of c(X) and must
be detectable.
Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

50

Aliasing Probability
Theorem4: for a k-bit response sequence, if all
possible error patterns are equally likely, then the
probability of failing to detect an error (i.e., the
aliasing probability) by the LFSR of length r is
2k r 1
Pal k
2 1
Proof: For a k-bit response, deg(m(X))=k-1, and
deg(e(X))<=k-1. Therefore, the number of possible
error polynomial is represented by e(X)=c(X)p(X)
for some nonzero p(X). Since deg(c(X))=r, the
number of possible p(X)s is 2k-r-1. Thus
2k r 1
Pal k
2 1

For a long sequence, k>>rPal~1/2r

Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

51

Multiple-Input Signature Register

The structure of multiple-input signature register
(MISR)

D FF

Cr

Dr-2

D1

D0

Dr-1

D FF

Cr-1

D FF

C2

C1

The mathematical theory is a direct extension of the

results shown above
For equally likely error patterns and long data
streams, the aliasing probability for an MISR of r
stages also is P 1/ 2r.
al

Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

52

Response Compaction
Usually, we think of data compression as a process
that preserves data integrity. This is why we given
more attention here to data compaction, which may
result in some losses
There are several compaction testing techniques
Parity testing
One counting
Transition counting
Syndrome calculation
Signature analysis

Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

53

Parity Testing
This is the simplest of all techniques but also the
most lossy
The parity of responses to the test patterns is
calculated as
iL
P i 1 ri , where L is the length of the test and ri is
the response for the ith test pattern
The response of the circuit under test (CUT) to
pattern i and the partial product Pi-1 is illustrated as
below

Test
Patterns
Advanced Reliable Systems (ARES) Lab.

CUT

ri

Pi 1

Jin-Fu Li, EE, NCU

D FF
54

One Counting
The number of 1s in the response stream is
calculated and compared to the number of 1s in the
fault-free responses
Consider the circuit shown below
a
b

11110000

11000000

11001100
11101010

10101010

If we have a test of length L and the fault-free count

is m, the possibility of aliasing is [C(L,m)-1] patterns
out of a total number of possible strings of length L,
(2L-1)

Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

55

Transition Counting
In transition counting compaction, it is only the
number of transition 01 and 10 that are counted.
Thus the signature is given by
i L1
i 1 ri ri 1 , where the summation is ordinary
addition and is XOR operation
The compaction scheme is shown below

ri
Test
Patterns

Advanced Reliable Systems (ARES) Lab.

CUT

D FF

Jin-Fu Li, EE, NCU

ri 1

56

Pseudorandom Pattern Generator

Logic BIST uses mostly pseudorandom (PR) tests.
They are usually much longer than deterministic
tests, but are definitely less costly to generate
PR tests are generated using a LFSR or cellular
automata
By means of a simple circuit called an autonomous
linear feedback shift register (ALFSR)
Definition: an ALFSR is a LFSR with no external
inputs
Faults that are hard to detect with PR tests are
called random pattern resistant faults

Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

57

Pseudorandom Pattern Generator (PRPG)

Example: the following ALFSR generates the
pseudorandom sequence shown in the table below

Q1

Q2

Q3

output

Q4

State 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15=0
Q1
Q2
Q3
Q4

1
0
0
0

1
1
0
0

1
1
1
0

1
1
1
1

0
1
1
1

1
0
1
1

0
1
0
1

1
0
1
0

1
1
0
1

0
1
1
0

0
0
1
1

1
0
0
1

0
1
0
0

0
0
1
0

0
0
0
1

1
0
0
0

The output sequence is 000111101011001, which repeats after

15(2n-1) clocks
Max period for an n-stage ALFSR=2n-1
All-0 state of the register cannot occur in the max-length cycle

Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

58

Mathematical Foundation of PRPG

A generic structure of ALFSR

C1

am

Q1

am 1

C2

Q2

Cn-2

Cn-1

Qn-1

am 2

amn1

Cn

Qn

am n

A sequence of bits {am}=a0,a1,,am, can be associated

with a polynomialits generation function:

G ( X ) a0 a1 X am X m 0 am X m
m

In the above figure, assume that the current state of Qi is

am-i, i=1,2,,n, and the initial state of Qi is a-i=0,
n
i=1,2,,n, but a-n=1, then am i 1 ci ami
Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

59

Mathematical Foundation of PRPG

G(X )

m 0

i 1

i 1

ci X [a i X
i

ci X [a i X

i 1

ci X i [a i X

a 1 X
a 1 X

a 1 X

i 1

ci X G ( X )

n
i 1

Advanced Reliable Systems (ARES) Lab.

i 1

ci X

a m i X

m 0
m i

a m i X

m 0

am X

G ( X )]
i

a 1 X

ci X i ( a i X

a 1 X

i
n

a 1 X

c X
i 1 i

m i

ci X i ( a i X

ci X i ( a i X
1

m i

i 1

ci X G ( X )
i

i 1

cia m i ) X
1

G(X )

m 0

i 1

i 1

am X

Jin-Fu Li, EE, NCU

60

Mathematical Foundation of PRPG

Now c( X ) 1 i 1 ci X i is the characteristic polynomial of
the LFSR as defined above. Since a-1=0, i=1,2,,n-1,
and a-n=1, we have
n

1
G(X )

c( X )

m 0

The sequence {am} is cyclic, with the period assumed

to be p
G(X )

1
( a 0 a 1 X a p 1 X p 1 )
c( X )
X p ( a 0 a 1 X a p 1 X
X

2p

( a 0 a 1 X a p 1 X

( a 0 a 1 X a p 1 X

p 1

( a 0 a 1 X a p 1 X

p 1

1 X

1 X p

a 0 a 1 X a p 1 X
c( X )
Advanced Reliable Systems (ARES) Lab.

p 1

p 1

p 1

)( 1 X

)
p

2p

i.e., c(X) evenly divides into 1-Xp

Jin-Fu Li, EE, NCU

61

Theorems
Theorem: If the initial state of an n-stage LFSR is a-i=0,
i=1,2,,n-1, and a-n=1, then the LFSR sequence {am}
is periodic with a period that is the smallest integer p
for which c(X) divides 1-Xp
The period p<=2n-1
For a given n, we want to find a c(X) that maximizes p

Definition: The sequences produced by max-length

LFSRs are called pseudorandom sequences or msequences. The characteristic polynomial associated
with an m-sequence is called a primitive polynomial.
An irreducible polynomial is one that cannot be
factored
Pseudorandom sequences (or m-sequences) are not
really random since they are produced by a fixed circuit.

Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

62

Theorems
Theorem: An irreducible polynomial c(X) satisfies the
following 2 conditions:
It has an odd number of terms including the constant
term
If its degree n>3, then c(X) must divide 1+Xp, where
p=2n-1

Theorem: A primitive polynomial is irreducible if the

smallest positive integer p that allows the polynomial
to divide evenly into 1+Xp occurs for p=2n-1, where n
is the degree of the polynomial

Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

63

Built-In-Logic-Block-Observer (BILBO)
A BILBO is a multi-purpose test module which serves
as a test generator or a signature analyzer. It is
composed of a row of FFs and some additional gates
for shift and feedback operation
Z1

Z2

Z3

Z4

B1
B2
SI
0

B1 B2

Function

0
1
0
1

All FFs are reset

Behaves as separate latchesnormal mode
A linear shift registerSR mode
MISR/PRPGtest mode

1
1
0
0

Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

64

STUMPS Architecture
Logic BIST with STUMPS architecture
PRPG

PIs
CUT
BSR

Test
control
signal

POs

MISR

Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

65

Summary
Design-for-testability techniques

Ad-hoc techniques
Scan
LSSD
Random access scan
Syndrome-testable
C-testability

Scan is a popular DFT technique in modern IC

design
DFT can increase the controllability and
observability of the circuit under test

Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

66

Summary
Built-in self-test methodology is more and
more important for deep submicron designs
Two key components of BIST
Test pattern generator
E.g., LFSR

Response evaluator
E.g., BILBO

Advanced Reliable Systems (ARES) Lab.

Jin-Fu Li, EE, NCU

67