On Multiple Fault Detection in Combinational Logic Circuits

Alexander Birger

Intelligent Technologies Research Centre
Department of Engineering
Glasgow Caledonian University
Cowcaddens Road Glasgow G4 0BA
United Kingdom
Tel.: +44 141 331 3528
Fax: +44 141 331 3690
e-mail: abi@gcal.ac.uk

At the present time, ATPG methods for single stuck faults (SSF) are in common use. In general, multiple constant fault (MSF) model is more realistic. It has long been known that complete tests for SSFs do not always detect MSFs. A number of researches were dedicated to studying MSF model and developing methods for testing MSFs. It was found that methods based on an explicit enumeration of MSFs are unrealistic for practical use.

More perspective approach is presented in this paper, which deals with line enumeration and finding a line detection test (LDT) for each of them. Passing LDT guarantees that the corresponding line is fault-free independently of the possible presence faults on other lines of the circuit. It is easy to verify that a set of such LDTs for every line in the circuit is a full test for MSFs. It is proven that the minimum length of LDT is 2. The method and algorithms for finding an LDT of length 2 for the given line in a combinational circuit of an arbitrary basis are proposed. The algorithms use D-calculus with modified sense of its common symbols, and additional restrictive symbols. The first algorithm guarantees finding a LDT for given line in one-output circuit if at least one LDT of the length 2 for this line exists. The second algorithm eliminates restrictions on the number of circuit outputs. On the next step, more general concept of conditional LDTs (CLDT) is proposed. During the process of finding CLDTs, the information about LDTs and CLDTs being found earlier is used. Examples of using algorithms are given. The way of fault location for the case of using LDT and CLDT, and some other topics are discussing.