Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital logic testing
Reexamination Certificate
1999-09-03
2002-04-23
Chung, Phung M. (Department: 2784)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital logic testing
C714S724000
Reexamination Certificate
active
06378096
ABSTRACT:
DESCRIPTION OF THE INVENTION
IA. Field of the Invention
The present invention is related to solving complex problems. Specifically, the present invention is related to a method of solving a test generation problem for sequential circuits. The present invention is embodied in methods for solving a problem; methods for solving a test generation problem for sequential circuits; a method for generating test vectors for testing sequential circuits; systems for generating test vectors; and a computer program product including a computer code for solving a test generation problem for sequential circuits.
IB. Background of the Invention
Complex problems are often defined by a large set of constraints. Test generation for testing a sequential circuit is an example of such a complex problem. For some problems, the only practical method of obtaining a solution may be an on-line method.
FIG. 20
shows a flowchart describing an on-line method. According to these on-line methods, a subset of constraints that correspond to a sub-problem of the main problem are first considered as shown in
20
.
1
and
20
.
2
. A solution is derived for this sub-problem
20
.
3
. Because such a solution for the sub-problem satisfies only a subset of constraints of the main problem, it is referred to as the partial solution. If no partial solution exists for the sub-problem, then it is clear that the main problem itself has no solution. In such a case a subset of constraints that prevent the existence of a solution is identified
20
.
4
.
A check is made to see if a partial solution additionally satisfies all constraints of the main problem
20
.
5
. In such a case, the partial solution itself is a complete solution to the main problem
20
.
6
. Otherwise, if the partial solution does not satisfy additional constraints that are not part of the constraints corresponding to the sub-problem, an on line method augments the subset of constraints for the sub-problem. This is done by including one or more of the additional constraints
20
.
7
. After augmentation, the on-line method derives another partial solution. This process is repeated, as shown in the loop of
FIG. 20
, until either a partial solution that satisfies all constraints is derived or a subset of constraints is identified that does not have a partial solution. Usually, either a solution is found or it is established that no solution is possible well before the final iteration that will have to consider all constraints.
An example of an on-line method is the conventional time-frame expansion method. Consider solving the sequential test generation problem using the conventional time-frame expansion method. The time frame expansion method is described in detail in the following references: G. R. Puzzle and J. P. Both, “A Heuristic Algorithm for the Testing of Asynchronous Circuits,”
IEEE Trans. on Computers
, pp. 639-647, June 1971; R. Marlene, “An Efficient Test Generation System for Sequential Circuits,” 23
Rd. Design Automation Conference
, June 1986, pp. 250-256; H-K. T. Ma, et. Al., “Test Generation for Sequential Circuits,”
IEEE Trans. on Computer-Aided Design
, Vol. 7, No. 10, pp. 1081-1093, October 1988; M. Scull and E. Auto, “ESSENTIAL: An Efficient Self-Learning Test Pattern Generation Algorithm For Sequential Circuits,” 1989
International Test Conference
, pp. 28-37; W. Chewing and T. Chakraborty, “Gentest—An Automatic Test Generation System for Sequential Circuits,”
IEEE Computer
pp. 43-49, April 1989, D. H. Lee and S. M. Reddy, “A New Test Generation Method for Sequential circuits,”
Proc. of International Conference on Computer Aided Design
, pp. 446-449, 1991; T. Niermann and J. Patel, “HITEC: A Test Generation Package for Sequential Circuits,”
European Conf. On Design Automation
1991, pp. 214-218 and T. Kelsey, K. Saluja, and S. Lee, “An Efficient Algorithm for Sequential Circuit Test Generation,”
IEEE Trans. on Computer
, vol. 42, pp. 1361-1371, November 1993.
In the time-frame expansion method, a test generation problem for sequential circuits is divided into sub-problems. A different sub-problem is identified with each time-frame. These sub-problems are not independent. The dependencies between sub-problems exist because, for any given time-frame, there are constraints on combination of values that can (or cannot) be assumed by state variable inputs. However, explicitly determining all constraints imposed on a time-frame by neighboring time-frames is also difficult. Further, such a determination may be as hard as solving the original test generation problem. This is because prohibitive computational resources may be required to determine all legal and illegal combination of state variable values. Furthermore, the number of sub-problems (time-frames) that will have to be considered for a target fault may not be known. Instead, a partial solution for a sub-problem (corresponding to a time-frame) is determined by ignoring constraints imposed by neighboring time-frames. Such a partial solution may not satisfy an ignored constraint (for example, the partial solution may require a present state that cannot be justified). Adding the unsatisfied constraints augments the initial constraints set for the sub-problem, and thus deriving a new partial solution. Clearly, the time-frame expansion technique employed by sequential test generators is an on-line method.
In other word, on-line methods derive a solution by solving a series of related problems P
1
. . . , P
n
where:
(1) the constraint set that defines problem P
i
(1≦i≦n−1) is a subset of the constraint set for problem P
i+1
, and
(2) constraints for problem P
i+1
are usually not known while deriving a solution for problem P
i
.
If an algorithm is available for finding a solution for P
1
, one can repeatedly use the same algorithm for deriving solutions for problems P
2
, . . . , P
n
by considering each P
i
(1≦i≦n) as independent problems. However, this typically is not an efficient way of finding a solution using on-line methods.
Many problems are often solved by recursively partitioning the problem into sub-problems. Partitioning implies that:
(1) sub-problems can be solved independently, and
(2) solutions to sub-problems can be put together to derive a solution for the original problem.
Sub-problems are independent if the search spaces that will have to be examined for finding sub-problem solutions are independent. However, it should be clear that mandating independence of sub-problems could result in a sub-problem that may be as large as the original problem.
Practitioners in this field know that using recursive partitioning for on-line methods presents additional complications. Even if manageable and independent partitions can be derived for problem P
i
, these partitions may not be independent for problem P
i+1
. This is because additional constraints included in problem P
i+1
can cause independent sub-problems in P
i
to now become dependent.
II. SUMMARY OF THE INVENTION
It is an object of the present invention to provide an improved on-line problem solving method without the above-mentioned problems. It is a specific objective of the present invention to provide an on-line method of solving a test generation problem for sequential circuit wherein partitioned sub-problems can be dependent. It is another specific objective of the present invention to provided an improved method of generating test vectors for testing a sequential circuit.
In order to meet the objects of the present invention there is provided a method of solving a test generation problem for sequential circuits comprising: recursively dividing an original test generation problem into smaller sub-problems, wherein said sub-problems may be dependent while one or more of said dependent sub-problems may have solution-specific independence; finding solutions for said sub-problems: reusing solutions for dependent sub-problems, whenever the dependent sub-problems enjoy solution-specific independence; and identifying a minimal subset of conflicting objectives if a sub-probl
Bommu Surendra K.
Chakradhar Srimat T.
Doreswamy Kiran B.
Lin Xijiang
Chung Phung M.
NEC USA Inc.
LandOfFree
On-line partitioning for sequential circuit test generation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with On-line partitioning for sequential circuit test generation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On-line partitioning for sequential circuit test generation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2823975