Browse Prior Art Database

Producing Minimal Multiple Fault Test Sets for Fanout Free Combinational Circuit

IP.com Disclosure Number: IPCOM000087862D
Original Publication Date: 1977-Mar-01
Included in the Prior Art Database: 2005-Mar-03
Document File: 3 page(s) / 30K

Publishing Venue

IBM

Related People

Markowsky, G: AUTHOR

Abstract

Given a circuit with n inputs, a procedure is described herein which very quickly returns a minimal test set for detecting all multiple stuck-at-faults in the given fanout-free circuit. The size of the set is bounded above by n + 1, and the method avoids all backtracking. It should be noted that for some circuits there is no way to detect all faults using fewer than n+ 1 tests.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Producing Minimal Multiple Fault Test Sets for Fanout Free Combinational Circuit

Given a circuit with n inputs, a procedure is described herein which very quickly returns a minimal test set for detecting all multiple stuck-at-faults in the given fanout-free circuit. The size of the set is bounded above by n + 1, and the method avoids all backtracking. It should be noted that for some circuits there is no way to detect all faults using fewer than n+ 1 tests.

The disclosed method is quite fast, and always produces a multiple fault test set of minimal size. It should be further noted that any other test set for this circuit must have certain structural similarities to the minimal one produced by the algorithm.

The problem of generating a test set for detecting all possible stuck-at-0 or stuck-at-1 faults in a combinational circuit is of very great practical interest and has attracted much attention. Additional references and all terms not defined herein are standard and may be found in reference [1] where they appear with additional information.

Throughout, "circuit" shall denote a fanout-free combinational circuit. Furthermore, it is assumed that the circuit in question has been correctly designed and assembled to generate the desired function and that the only faults which can occur are of the stuck-at variety. Circuits were considered which are designed to produce 0 or 1 to be fanout-free with 0 primary inputs. However, since these circuits are totally unnecessary in the synthesis of other functions, they will be ignored.

Definition: (a) By a test for a circuit or the corresponding function is meant a set of consistent value assignments to all the primary input lines of the circuit. Thus an input to a circuit having input lines x(1), x(2) and x(3) might look like {x(1) <-- 0, x(2) <-- 1, x(3) <-- 1}. (b) Let C be a fanout-free combinational circuit, F the set of all functions which can result from some set of faults (including the empty set) and f the function which C produces when there are no faults in C. A set of tests {a(1),...,a(n)} is said to be a test set for C or F if for all g Epsilon F - {f}, there exists i such that g(a(i)) Not = f(a(i)). (c) Let C and f be as in (b) above and let T be a test for C. We let T/z/ = {a Epsilon T Absolu...