an Mine (forward line), bf-pairs are determined such that necessary conditions
for transition propagation in b-line and f-line contradict. Thus, a testable path
can not contain any bf-pair. If a path contains at least one bf-pair, it is not
testable; otherwise, the path is potentially testable.
To determine if a potentially testable path is testable or not, we can use any
ATPG tool to generate input vectors that test the path. In the simulations, we
have used TranGen [77] for the test generation. It is a fast ATPG algorithm
based on the SAT solvers.
4.5.2 Basis path set
In path selection, it is also important to select independent paths. Consider
following four paths in the circuit shown in Figure 4.7.
Pi- c-j-gι-e-g3-h-34-k
P5: b-gι-e-g3-h-g4-k
Pf>- c-j-gι-d-g2-3-g4-k
P7: b-gι-d-g2-3-g4-k
For the circuit, it is not hard to verify
dr(P4) + dr(P7) = dr(P5) + dr(Pg).
Thus, these four paths are not independent. Knowing delay of each three of them
leads to the delay of the fourth one.
57