Hardware Reference
In-Depth Information
!
B
be the Boolean
function of the CKT's i
th
output in absence of any fault. For each output i ,we
B
n
define function C
f;S;i
!
B
which describes the Boolean behavior of CKT
in presence of RBF f restricted to S . Information necessary to define C
f;S;i
is
contained in, e.g., hash tables discussed in the previous section.
Once C
f;S;i
has been defined, an assignment to Boolean variables x
1
;:::; x
n
satisfying the formula
C
1
.x
1
;:::;x
n
/
˚
C
f;S;1
.x
1
;:::;x
n
/
_
:::
_
C
p
.x
1
;:::;x
n
/
˚
C
f;S;p
.x
1
;:::;x
n
/
W
is sought. This is done by constructing the conjunctive normal form (CNF) of
the formula and passing it to a SAT solver. If the SAT solver finds a satisfying
assignment to x
1
;:::;x
n
, there must be at least one circuit output j for which
C
j
.x
1
;:::;x
n
/
˚
C
f;S;pj
.x
1
;:::;x
n
/
D
1or, equivalently, C
j
.x
1
;:::;x
n
/
¤
C
f;S;pj
.x
1
;:::;x
n
/. This means that the assignment found induces different val-
ues on at least one circuit output in presence and in absence of the fault, i.e., it
detects the fault.
The SAT solver may also report that there is no satisfying assignment. This is
the formal proof that fault f restricted to section S is undetectable. Recall that this
means that none of the defects with resistance from section S is detectable by any
test pattern.
4.4.2
ATPG Algorithm
Figure
4.5
outlines the overall ATPG algorithm. The algorithm keeps two ADIs for
each fault f in the fault list; G.f / and L
f
. G.f / is the range of bridge resistances
proved undetected so far. Whenever the call of procedure
gen test
fails, the corre-
sponding section is included in G.f / in Line (11). L
f
contains resistances left to
detect. Resistances in L
f
have neither been covered by test patterns generated so
far nor proven undetectable. A fault with an empty L
f
is dropped from the fault list
in Lines (13) and (20). Test patterns are generated in Line (9) and fault-simulated in
Line (18) until all faults are dropped.
The first fault in the fault list and the highest section of that fault undetected yet
are targeted first in Line (8). The highest section is taken because high-resistance de-
fects tend to be more difficult to detect than low-resistance defects, resulting in many
specific constraints. Hence, it is more likely that a test pattern generated for a higher
section will also cover lower sections of the same RBF than vice versa. However, it
cannot be ruled out that an RBF requires multiple vectors to cover the entire range
if not all sections of an RBF have been covered, the highest remaining section is
targeted next.
The fault simulation procedure called in Line (18) could be either interval-based
or sectioning-based. If interval-based simulation is used, procedure
RBF AT P G
