Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital logic testing
Reexamination Certificate
2001-01-05
2004-09-07
Moise, Emmanuel L. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital logic testing
C326S041000
Reexamination Certificate
active
06789222
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to electrical computers and digital processing systems, and more particularly to test pattern generators.
BACKGROUND OF THE INVENTION
Known automatic test pattern generation (“ATPG”) methods activate a fault at a site, attempt to propagate the fault to an output, then work backward through the circuit in an effort to “justify” signal levels needed to activate and propagate the fault (see for example Roth, J. P., “Diagnosis of automata failures: A calculus and a method,” IBM J. Res.Dev. 10:278-281, 1966).
The U.S. Pat. No. 4,204,633 to Goel, issued May 27, 1980, teaches a method that avoids the need for backward justification. However, when signal assignment conflicts arise, previous decisions are systematically reversed until an input combination is found that makes the fault detectable at an output. When a fault has no test or few tests, considerable time may be consumed in a sometimes-fruitless search for a conflict-free input assignment.
SUMMARY OF THE INVENTION
A preferred embodiment of the present invention defines a method for generating all tests for all detectable faults during a single pass through a sorted definition of a combinational circuit. Such a method avoids the conditional behavior of many currently used methods.
The method provides a netlist defining a combinational circuit in terms of interconnected primary inputs, logic elements, and primary outputs. The netlist is sorted into an ascending circuit-level order commencing at the level of the primary inputs. Data structures are defined for a fault, a fault-propagation function, and a path-enabling function. A library of Boolean function combining rules is provided for each of the logic element types present in the circuit definition. Initial data structures are created for each of the primary inputs.
The rules are applied to the data structures that form the inputs to each circuit level to create and store data structures that will form the inputs to the next circuit level, commencing at the level of the primary inputs, and progressing through the circuit definition circuit-level-by-circuit-level.
In the preferred embodiment an attempt is made to activate and propagate all faults to primary outputs during a single pass through the circuit definition. Each fault reaching a primary output is a detectable fault. The fault-propagation function for each detectable fault defines all primary input assignments that permit the fault to be activated and propagated to the primary output. These input assignments define all tests for the detectable fault.
The computational effort of creating the path-enabling functions is shared among all faults during the single pass, thus reducing the overall effort. The preferred path-enabling function is the 1-set.
In another embodiment, the invention defines methods that release no-longer-needed data structure storage, permitting the handling of larger circuits. In yet another embodiment, the invention defines methods that stop propagating faults once they reach a primary output, thereby reducing overall computational effort.
REFERENCES:
patent: 4204633 (1980-05-01), Goel
patent: 4779273 (1988-10-01), Beucler et al.
patent: 5390193 (1995-02-01), Millman et al.
patent: 5657240 (1997-08-01), Chakradhar et al.
patent: 5726996 (1998-03-01), Chakradhar et al.
patent: 5831996 (1998-11-01), Abramovici et al.
patent: 5862149 (1999-01-01), Carpenter et al.
patent: 5896401 (1999-04-01), Abramovici et al.
patent: 6215327 (2001-04-01), Lyke
patent: 6442722 (2002-08-01), Nadeau-Dostie et al.
patent: 6463560 (2002-10-01), Bhawmik et al.
patent: 6467058 (2002-10-01), Chakradhar et al.
patent: 6477684 (2002-11-01), Sanghani
patent: 6611933 (2003-08-01), Koenemann et al.
Theory and application of GF(2p) cellular automata as on-chip test pattern generator Sikdar et al. VLSI Design, 2000. Thirteent International Conference on , Jan. 3-7, 2000 pp.: 556-561.*
TDB:ACC-NO: NN910470 Disclosure Title: Deterministic Test Generation for Transition Faults. Publication-Data: IBM Technical Disclosure Bulletin, Apr. 1991, US vol. No.: 33 Issue No.: 11 Page No.: 70-71.*
Disclosure Title: Single-Pass Three-State Driver Testing□□Publication-Data: IBM Technical Disclosure Bulletin, May 1983, US vol. No.: 25 Issue No.: 12 Page No.: 6617-6620 Publication-Date: May 1, 1983.*
TDB-ACC-No: NN83056586 Disclosure Title: Simulation Algorithm Publication-Data: IBM Technical Disclosure Bulletin, May 1983, US vol. No.: 25 Issue No.: 12 Page No.: 6586-6587 Publication-Date: Ma 1, 1983□□.*
Roth, J.P., et al., “Programmed Algorithms to Compute Tests to Detect and Distinguish Between Failures in Logic Circuits” IEEE Trans. on Elec. Comp., vol. EC-16, No. 5, Oct. 1967, pp. 567-580.
Underwood B., et al., “The Parallel-Test-Detect Fault Simulation Algorithm,” 1989 Int'l Test Confr., 1989 IEEE.
Goel, P., “An Implicit Enumeration Algorithm to Generate Tests for Combinatorial Logic Circuits,” IEEE Trans. on Comp., vol. C-30, No. 3, Mar. 1981, pp. 215-222.
Abramovici, M., et al., “Digital Systems Testing and Testable Design,” Computer Science Press, N.Y. 1990, pp. 94-95.
Buckley Robert
Butt Cynthia
Moise Emmanuel L.
Yardstick Research, L.L.C.
LandOfFree
Single-pass methods for generating test patterns for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Single-pass methods for generating test patterns for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Single-pass methods for generating test patterns for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3241333