Slide 45 of 173
Notes:
This slide is an example of the application of the D algorithm on a target fault, namely, J s-a-1. The process begins by picking all of the possible PDCFs for J s-a-1. This choice, like all in algorithmic ATPG, can be arbitrarily made or made with the assistance of some heuristic (testability measures). After the PDCF is selected and applied, other circuit values that are implied by the values specified in the PDCF are noted. For example, the value of "1"on G requires a "1"on both A and B. After implication of the PDCF, the process of propagating the fault effect to a primary output using the PDCs is begun. The PDC of an OR gate is used to propagate the value on J to the output L. Implication of the value from the PDC on K is then done. This results in the requirement of a "0"on H. This value on H must be justified by setting either C or D to a “0”, which results in a complete test.
The second example shows what would happen if the alternate PDCF for J s-a-1 is selected. No test would be possible with this selection, and another solution (namely the first) would have to be tried.
The D algorithm is a “branch-and-bound” algorithm in that at certain points in the algorithm choices as to the solution to be attempted must be made. To make the algorithm complete, each and every choice must be tried. This example illustrates part of the problem with the D algorithm in that choices may be possible at each internal circuit node and the number of solutions to be searched is exponential with the number of circuit nodes.
