SATFAST: A statistical tool for fault simulation and test generation

With the advent of VLSI technology, test pattern generation (TG) for high fault coverage is regarded as one of the most difficult problems in the field of VLSI testing. It has been known for some time that the process of TG is NP-complete (17-21). TG can consume CPU time and memory at a rate that increases at least as the square of the number of gates in the circuit (17). For VLSI circuits, this is a serious limitation. As a result, testability analysis has become a prime issue. In the testability analysis of digital circuits, one is often faced with the task of computing the signal probabilities of each node of the circuit. However, it has been known that computing signal probabilities is #P-complete (23,51). This implies that the problem might be intractable even if P = NP. Thus, any practical method will only provide an estimate of such probabilities instead of computing the exact values.; Current algorithms for estimating signal probabilities could be classified into linear or polynomial algorithms. The accuracy of linear algorithms, such as the simple and the weighted averaging algorithms, is far from satisfactory while the complexity of polynomial algorithms is close to fault simulation and test generation.; This dissertation introduces a linear but effective algorithm based on a new set of inference rules for estimating signal probabilities, which we shall call the possibilistic algorithm. The proposed algorithm provides significantly better estimates of signal probabilities than the simple algorithm as well as the weighted averaging algorithm, and it is also linear in the product of circuit size and the number of primary inputs.; Based on this algorithm, a statistical tool, termed SATFAST (a StAtistical Tool for FAult Simulation and Test generation) is developed. The output of this tool provides an estimation of: signal probabilities, sensitization probabilities, and detection probabilities of stuck-at faults. Moreover, it calculates other statistical parameters such as expected test length, expected fault coverage evaluation, identification of hard-to-detect faults for a predetermined threshold of acceptability, and a good sample of faults that mirrors the total estimate of fault distribution (53).; It is also demonstrated that the computational complexity of SATFAST is linear in the product of the circuit size and the number of primary inputs. Experimental results using ISCAS benchmark circuits show the effectiveness of the tool. The correlation coefficients of the results are found to be extremely good, while the tool is demonstrated to be very fast.