Data processing: measuring – calibrating – or testing – Measurement system – Measured signal processing
Reexamination Certificate
2001-05-03
2003-06-17
Hoff, Marc S. (Department: 2857)
Data processing: measuring, calibrating, or testing
Measurement system
Measured signal processing
C702S085000, C702S117000, C702S189000, C703S002000, C703S013000, C703S026000, C712S221000, C712S300000, C716S030000, C716S030000, C716S030000
Reexamination Certificate
active
06581026
ABSTRACT:
BACKGROUND OF THE INVENTION
Field of the Invention
The invention relates to a method and a configuration for comparison of a first characteristic with predetermined characteristics of a technical system.
Model checking (MC) is a technique for verifying characteristics of a technical system using specific methods. In the past, a major complexity problem (state explosion problem) has occasionally arisen when this procedure was applied to the technical system. As a result of this, considerable efforts are being made to separate out a portion of a system that is to be verified, which is relevant for analysis and can be verified practically. Even then, the verification process often fails due to existing resource limits (computation performance, memory space).
As described by Kühlmann and Krohm, in “Equivalence Checking Using Cuts and Heaps”, 34
th
ACM/IEEE Design Automation Conference, 1997, pp.263-68, listed at [1] below, two circuits can be compared by means of binary decision diagrams (BDDs). In particular, this is aimed at highly complex digital circuits which are intended to be compared with one another, and for which structural similarities are determined (combinatorial circuit verification).
A first approach for combinatorial circuit verification attempts to produce functional implications by generating test patterns which are applied to the circuits to be compared (ATPG method). In this case, the object is to prove that an exclusive-or function between two output values to be compared cannot result in a logic “1”.
Another approach for combinatorial circuit verification is based on a canonic description of Boolean functions. Such a canonic description is represented by BDDs or specific variants of BDDs, for example by Reduced Ordered BDDs (ROBDDs). In this context, see [2] Jain, et al., “A Survey of Techniques for Formal Verification of Combinatorial Circuits”, Proc. Int. Conf. on Computer Design (ICCD), 1997, pp.445-54, listed at [2] below. One special problem of BDDs is that of their exponentially rising memory space requirement.
What is referred to as an SAT comparison method (also SAT comparator; SAT=“Satisfiability”) is known from J. P. M. Silva: “An Overview of Backtrack Search Satisfiability Algorithms,”, 5
th
Int. Symposium on Artificial Intelligence and Mathematics, 1998, listed at [3] below; Bayardo, Jr. and Schrag, “Using CSP Look-Back Techniques to Solve Real-World SAT-Instances”, Proc. of the National Conf. on Artificial Intelligence, pp.203-08, July 1997, listed at [4] below; and Davis and Putnam: “A Computing Procedure for Quantification Theory”, Journal of the Association for Computing Machinery, Vol. 7, Number 3, July 1960, pp.125-39, listed at [7] below. The SAT comparison method is distinguished by searching systematically for solutions for any given Boolean notations in the form
(k
1
k
2
)
(k
3
{overscore (k
5
)})
(k
2
{overscore (k
4
)}) (1)
If the entire search area is exhausted without any solution being found during the search, then the fundamental Boolean problem cannot be solved.
SUMMARY OF THE INVENTION
The object of the present invention is to provide a method and a device for comparing a first characteristic with a predetermined characteristics of a technical system which overcomes the above-noted deficiencies and disadvantages of the prior art devices and methods of this general kind, and which ensures automatic solution of the comparison problem.
With the above and other objects in view there is provided, in accordance with the invention, a method of comparing a first characteristic with predetermined characteristics of a technical system, which comprises:
defining at least two comparison methods, each capable of carrying out a comparison of a Boolean function of the first characteristic with Boolean functions of the predetermined characteristics of the technical system; and
processing the at least two comparison methods in a predetermined sequence until a result of the comparison is defined.
In order to achieve the object, a method is specified for comparison of a first characteristic with predetermined characteristics of a technical system, in which at least two comparison methods are provided, each of which can carry out a comparison of the first characteristic with the predetermined characteristics of the technical system. The at least two comparison methods are processed in a predetermined sequence until a result of the comparison is defined.
In this case, it is particularly advantageous for different comparison methods to be processed automatically.
One development is for the result of the comparison to be equality of or a difference between the first characteristic and the characteristics of the technical system.
In particular, the comparison process can be terminated as soon as a single difference is discovered.
Another development provides for the first characteristic to be verified by the technical system on the basis of equality.
The at least two comparison methods may, in particular, be two of the following comparison methods:
a) SAT comparison method;
b) simulation method;
c) BDD method;
d) ATPG method;
e) methods based on internal equivalence points.
In particular, the BDD method may be an ROBDD method. Furthermore, the ROBDD method may be carried out with respect to its leaves or with respect to the sectional planes.
The technical system may be a circuit, in particular a digital electrical circuit.
In accordance with an added feature of the invention, at least a portion of the comparison is carried out with an intermediate result reducing the complexity of the overall comparison process. Reducing the complexity in this way allows a result to be achieved by means of a comparison method which originally failed in the overall comparison process.
In accordance with an additional feature of the invention, the intermediate result of a comparison method which was not carried out to the end, is used in a further comparison method (utilization of side effects). For example, a terminated BDD comparison method offers an approach for representing the problem to be solved (in this case, the overall comparison). This is done using a different comparison method as the intermediate result, which results in computation time and/or memory space being saved.
If a comparison results in inequality, then diagnosis information is preferably represented, allowing a user to determine the cause of the inequality.
In the course of one development, the technical system is described as a finite automatically controlled device. Furthermore, the first characteristic may be represented as a Boolean function. In addition, the first characteristic can describe a behavior of the technical system over a predetermined time interval.
Digital circuits are becoming increasingly larger. Any test for correct behavior is thus becoming more complex, more time-consuming, and more expensive. MC for circuits of an actual size is thus a critical economic factor. The convenience of the technique for the user is considerably simplified by the method described above and the associated configuration. The approach described here is not limited to hardware design, but can also be used for verification of software, whose behavior can preferably be described by a finite automatically controlled device (for example SDL programs, protocols).
In the present approach, a hybrid verification process, that is to say a process using a number of comparison methods, can be used to solve a verification task. A hybrid verification process is a framework which contains a set of partial verification processes (individual comparison methods). The hybrid verification process coordinates the way in which the partial verification processes operate. The aim is to use different verification processes to solve verification tasks which no verification process would have solved on its own. If none of the partial verification processes can solve a given verification task, then this verification task is broken down. To do this
Lohse Joerg
Warkentin Peter
Desta Elias
Greenberg Laurence A.
Hoff Marc S.
Infineon - Technologies AG
Locher Ralph E.
LandOfFree
Method and configuration for comparing a first... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and configuration for comparing a first..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and configuration for comparing a first... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3095075