Automatic Test Pattern Generation:Path Delay Fault Simulation

Path Delay Fault Simulation

The exact number of PDFs detected by a given set of pair of test patterns is an intractable problem. This is independent of the sensitization criterion used (robust, nonrobust, and functional). The only way to ensure exact implicit PDF coverage is to use canonical data structures that store compactly PDFs and allow for their quick identification. An exact PDF simulation tool stores and manipulates PDFs on a data structure called the path status graph [20]. The drawback of the approach is that it may require expo- nential space for many benchmarks. As was described earlier, ZBDD is a promising data structure for storing a very large number of PDFs. An implicit and exact fault coverage method has been introduced and it has been shown that exact fault coverage can be obtained on any existing benchmark and any test set [21]. The method is fast and the memory requirement is not prohibitive.

To further accelerate the fault coverage process or if the memory requirements do not allow for the use of exact methods the number of PDFs that are covered (tested) by a set of pair of test patterns must be approximated. The remaining of this section describes methods CAD for obtaining lower bounds on the number of detected PDFs by a given set of n pairs of patterns. These approaches apply to any type of PDF sensitization and are referred to as fault estimation schemes.

In Ref. [22], every time a pair of patterns is applied, the CAD tool examines whether there exists at least one line where either a rising or falling transition has not been encountered by the previously applied pairs of test patterns. Let Ei denote the set of lines for which either a rising or a falling transition occurs for the first time when the pair of patterns Pi is applied.

When |Ei| is greater than zero, a new set of PDFs is detected by pattern Pi. These are the paths that

contain lines in Ei. A simple topological search of the combinational circuit suffices to detect their number. If for some Pi we have |Ei| = 0, the approach does not detect any PDF. The approach in Ref. [22] is nonenumerative but returns a conservative lower bound to the number of detected paths.

Figure 69.8 illustrates a case where a PDF may not be counted. Assume that the PDFs in all three patterns start with a rising transition. Furthermore, assume that the first pair of patterns detects PDFs along all the paths of the subcircuit which is covered by thick edges. Let the second pair of patterns detect PDFs on all the paths of the subcircuit covered by dotted edges, and let the dashed path indicate a PDF detected by the third pair of patterns. Clearly, the latter PDF cannot be detected by the approach in Ref. [22].

For this reason, Ref. [22] suggests that fault simulation is done by virtually partitioning the circuit into subcircuits. The subcircuits should contain disjoint paths. One implementation for such a parti- tioning scheme is to consider lines that are independent in the sense that there is no physical path in the circuit that contains any two selected lines. Once a line is selected, we form a subcircuit that consists of all lines that depend on the selected line. In addition, the selected lines must form a cut separating the inputs from the outputs so that every physical path contains one selected line. This way, every PDF belongs to exactly one subcircuit. Figure 69.9 shows three selected lines (the thick lines) of the circuit in Figure 69.8 that are independent and also separate the inputs from the outputs.