Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital logic testing
Reexamination Certificate
1998-07-10
2001-04-24
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital logic testing
C714S735000
Reexamination Certificate
active
06223316
ABSTRACT:
I. DESCRIPTION OF THE INVENTION
IA. Field of the Invention
This invention relates to a method for restoring test vectors that are used to detect faults in large industrial design systems. Specifically, this invention relates to a method for restoring a minimal subsequence of vectors that detects a chosen set of faults. This invention is embodied in a method for two-step vector restoration and a method for accelerated two-step vector restoration that improve run-times of fault diagnosis for large designs.
IB. Background of the Invention
A vector is a set of inputs to a system. A test set is a set of vectors that identify faults in the system. Target fault list is a list of a subset of faults that are identified by a given test set. Given a test set, and a set of target fault list that is known to be detected by the test set, vector restoration techniques identify a minimal subsequence that detects all faults in the target fault list. See R. Guo, I. Pomeranz, and S. M. Reddy, “Procedures for static compaction of test sequences for synchronous sequential circuits based on vector restoration,”
Technical Report
8.3.1997, Electrical and Computer Engineering Department, University of Iowa, 1997.
Restoration techniques are useful in static test sequence compaction or fault diagnosis methods. Known static test sequence compaction methods are described in the following references: T. M. Niermann, R. K. Roy, J. H. Patel, and J. A. Abraham, “Test compaction for sequential circuits,”
IEEE Trans. Computer-Aided Design
, vol. 11, no. 2, pp. 260-267, February 1992; B. So, “Time-efficient automatic test pattern generation system,” Ph.D. Thesis, EE Dept., Univ. of Wisconsin at Madison, 1994; I. Pomeranz and S. M. Reddy, “On static compaction of test sequences for synchronous sequential circuits,”
Proc. Design Automation Conf
., pp. 215-220, June 1996; M. S. Hsiao, E. M. Rudnick, and J. H. Patel, “Fast algorithms for static compaction of sequential circuit test vectors,”
Proc. IEEE VLSI Test Symp
., pp. 188-195, April 1995; S. T. Chakradhar, and M. S. Hsiao, “Partitioning and Reordering Techniques for Static Test Sequence Compaction of Sequential Circuits,”
Technical Report
1997, Computers & Communications Research Lab, NEC USA Inc.
Compaction techniques based on vector restoration are described in I. Pomeranz, and S. M. Reddy, “Vector Restoration Based Static Compaction of Test Sequences for Synchronous Sequential circuits.”
Proceedings Int. Conf. on Computer Design
, pp. 360-365, 1997, University of Iowa, August 1997; and A. Raghunathan and S. T. Chakradhar, “Acceleration techniques for dynamic vector compaction,”
Proc. Int. Conf. Computer
-
Aided Design
, pp. 310-317, August 1995.
IB1. Review of vector restoration
A test set is an ordered sequence of vectors v
1
, . . . , v
n
. The test set detects faults f
1
, . . . , f
z
that form the fault set F. If a fault f is detected at vector v
i
of the test set, then the detection time D[f] of the fault is i. The information on the detection times can be obtained easily using a pre-processing phase that involves fault simulation. Fault dropping is a conventional way of performing such a fault simulation.
For example, the test set in
FIG. 1
has 20 vectors v
1
, . . . , v
20
. This test set detects five faults f
1
, . . . , f
5
. Fault f
5
is detected at vector v
20
. Therefore, D[f
5
]=20. Detection times for other faults are as shown in the FIG.
1
. For any given fault f with D[f]=t, there exists a sequence of vectors v
i
, . . . , v
t
(1≦i≦t) that detects the fault assuming an unknown initial state. For example, f
4
is detected at vector v
16
and there exists a subsequence v
1
, . . . , v
16
that detects the fault. It is also possible that a shorter sequence of vectors v
i
, . . . , v
t
(1<i≦t) detects the fault.
A conventional method called linear vector restoration method determines the subsequence by first considering only vector v
t
. If one or more target faults are not detected, then the subsequence v
t-1
, v
t
is proposed. If this sequence also does not detect all target faults, then additional vectors v
t-2
, . . . , v
1
(in that order) are considered until all target faults are detected. Such a procedure is clearly complex. More details about the complexity of this technique will be provided below.
The linear vector restoration technique is illustrated by subsequence restoration for faults f
4
and f
5
which constitute target faults in the example of FIG.
1
. Since f
5
is detected at v
20
, the first subsequence considered by the linear vector restoration method is v
20
. The fault f
5
is not detected by this first subsequence. Therefore, the subsequence is updated to include vector v
19
. The new subsequence is v
19
,v
20
. This subsequence also does not detect the fault f
5
. Therefore, additional vectors are restored until the restored subsequence includes v
17
. As shown in
FIG. 1
, this subsequence detects fault f
5
. Therefore, vector restoration for fault f
5
is complete.
The next step is to verify if f
4
is also detected by the restored vector set. For this example, the sequence v
17
, . . . , v
20
also detects f
4
, This completes the restoration process for the target faults f
4
and f
5
.
IB2. An application of vector restoration
Static compaction method using vector restoration is disclosed in detail in U.S. patent application Ser. No. 09/135,561, filed on May 27, 1998 by Bommu, et al., now U.S. Pat. No. 5,987,636 which is incorporated herein by reference.
Static compaction methods based on vector restoration share the framework described in FIG.
2
. Given a test set, fault set, and detection time for every fault, these methods produce a shorter test set that detects at least as many faults as the original test set. The input data includes a set of test vectors, a list of faults to be detected, and the detection times for the faults, Block 2.01 in FIG.
2
. First, a set of faults is chosen as the target faults in Block 2.02. These faults can have the same or different detection times.
If the latest detection time of any fault in the target list is t, then the restoration process Block 2.05 finds a subsequence v
i
, . . . , v
t
(1≦i≦t) that (1) detects all faults in the target fault list, and (2) if the subsequence is pre-pended to the restored subsequence for earlier target faults, then all earlier target faults are still detected. The next set of target faults is chosen from faults that remain undetected by restored vectors in Block 2.02. This process is continued in Blocks 2.03 and 2.04 until all target faults are detected.
The problem of compacting the test set of
FIG. 1
can be used as an illustration of the vector restoration method. Vector restoration for faults f
4
and f
5
results in the restored sequence v
17
, . . . , v
20
. However, fault f
3
is still undetected. Therefore, the next target fault chosen is f
3
. The process continues with restoration for fault f
3
. The detection time of f
3
is 12. Therefore, restoration of f
3
starts from the vector v
12
instead of vector v
17
. The first sequence proposed for f
3
is v
12
, v
17
, . . . , v
20
. This is because it is possible that a sequence starting from v
12
and ending at any of the vectors in the already restored vectors v
17
, . . . , v
20
could detect f
3
. Therefore, while restoring a vector sequence for f
3
, the already restored vectors v
17
, . . . , v
20
are also simulated. Restoration process continues until all faults are detected. For this example, the compacted vector set is v
1
, . . . , v
12
, v
17
, . . . , v
20
.
The conventional linear vector restoration techniques have a major problem that limit their usage. They require prohibitively large run-times for systems in large industrial designs.
II. SUMMARY OF THE INVENTION
It is therefore an objective of this invention to provide improved vector restoration techniques that require significantly less run-times than conventional methods.
Specifically it is an object of this invention to provide a metho
Bommu Surendra K.
Chakradhar Srimat T.
Doreswamy Kiran B.
De'cady Albert
NEC USA Inc.
Sughrue Mion Zinn Macpeak & Seas, PLLC
Ton David
LandOfFree
Vector restoration using accelerated validation and refinement does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Vector restoration using accelerated validation and refinement, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Vector restoration using accelerated validation and refinement will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2482013