Data processing: structural design – modeling – simulation – and em – Modeling by mathematical expression
Reexamination Certificate
1999-12-31
2004-11-09
Teska, Kevin J. (Department: 2128)
Data processing: structural design, modeling, simulation, and em
Modeling by mathematical expression
C703S006000, C703S013000, C703S023000, C700S012000, C714S037000, C714S724000
Reexamination Certificate
active
06816821
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a technique for deriving properties of a control system, and more especially to a technique for deriving properties of a hardware system using a model of the system.
DESCRIPTION OF THE PRIOR ART
When seeking to derive the properties of a system on the basis of known transition functions of the system and all of the possible starting states, it is known to use so-called “post-image” techniques to derive the reachable states of the system. A known set of initial states is selected and the post-image of that initial set is formed to provide a first reachable set. The first reachable set is compared to the known set of reachable states and, if the known set does not comprise the first reachable set, a new set of known reachable states is formed comprising the combination of the set of reachable states and the first reachable set. If however the known set of reachable states comprises the first reachable set, the set of reachable states is determined to be an invariant of the system, and computation ceases.
Where the system model is a set of transition functions, it would be considerably more efficient to produce the so-called “pre-image” of a set of states than it would be to produce the post-image. In simple terms, where each of several inputs to a system causes one of a set of outputs, a worst case for testing which input provided one particular output of interest would require all of the inputs to be applied in turn before it was possible to identify the input that gave rise to the particular output.
SUMMARY OF THE INVENTION
According to one aspect, the present invention derives transition functions for a reverse machine, i.e., a machine such that the post-image of the reverse machine will be the pre-image of the original system. The described novel technique has a large number of applications such as deriving properties of a control system using a model of the system, or deriving properties of a hardware system using a model of the system. The described novel technique may specifically be used for testing electronic circuits, testing logic circuits, including microprocessors.
According to another aspect, a method of calculating the post-image in a system includes forming a reverse model of the system, and calculating the pre-image in the reverse model, wherein the pre-image in the reverse model is equivalent to the post-image in the system. Preferably, the reverse model may be formed without knowing input states and the corresponding outputs states of the system. The formation of the reverse model may include transforming a transition function of the system into a constraint on the reverse model, and applying a parameterization of the constraint to all transitions of the reverse model.
According to yet another aspect, a method of synthesizing a reverse model of a system includes transforming a transition function of the system into a constraint on the reverse model, and applying a parameterization of the constraint to all transitions of the reverse model.
According to yet another aspect, a device for synthesizing a reverse model of a system includes a first store (a first memory), a second store (a second memory), and a processing system. The first store is constructed and arranged to store bits representative of transition functions of the system. The second store is constructed and arranged to store bits representative of an estimate of transition functions of the reverse model. The processing system includes logical device and a parameterization processor. The logical device is constructed and arranged to transform the transition functions of the system into constraints on the reverse model. The parameterization processor is arranged to apply a parameterization of the constraints to the estimate of transition functions of the reverse system to form transition functions of the reverse model.
According to yet another aspect, a device for synthesizing a reverse model of a system includes a first means for storing bits representative of transition functions of the system; a second means storing bits representative of an estimate of transition functions of the reverse model; and processing means. The processing means include a logical means for transforming the transition functions of the system into constraints on the reverse model; and a parameterization means for applying a parameterization of the constraints to the estimate of transition functions of the reverse system to form transition functions of the reverse model.
According to yet another aspect, a device for calculating the post-image in a system includes a third store (a third memory), a fourth store (a fourth memory), and a logical device. The third store is constructed and arranged to store bits representative of transition functions of a reverse model of the system. The fourth store is constructed and arranged to store bits representative of a set of states of the system. The logical device is constructed and arranged to substitute the state variables of the reverse model by the transition functions of the reverse model to provide a new set of states representing the pre-image of the reverse model, and thus provide the post-image in the system.
Preferably, the device of this aspect further comprises a first store constructed and arranged to store bits representative of transition functions of the system, and a second store constructed and arranged to store bits representative of an estimate of transition functions of the reverse model. The logical device is constructed and arranged to store transforming the transition functions of the system into constraints on the reverse models. The parameterization device is constructed and arranged to store applying a parameterization of the constraints to the estimate of transition functions of the reverse system to form transition functions of the reverse model.
Preferably, the estimate of transition functions of the reverse model comprises previous state variables of the system.
According to yet another aspect, a device for calculating the post-image in a system includes a third means for storing bits representative of transition functions of a reverse model of the system; a fourth means for storing bits representative of a set of states of the system; and logical means for substituting the state variables of the reverse model by the transition functions of the reverse model to provide a new set of states representing the pre-image of the reverse model, and thus provide the post-image in the system.
REFERENCES:
patent: 4200770 (1980-04-01), Hellman et al.
patent: 4376299 (1983-03-01), Rivest
patent: 5258919 (1993-11-01), Yamanouchi et al.
patent: 5272755 (1993-12-01), Miyaji et al.
patent: 5311521 (1994-05-01), Fitingof et al.
patent: 5325433 (1994-06-01), Torii et al.
patent: 5327544 (1994-07-01), Lee et al.
patent: 5331568 (1994-07-01), Pixley
patent: 5475388 (1995-12-01), Gormish et al.
patent: 5491639 (1996-02-01), Filkorn
patent: 5615137 (1997-03-01), Holzmann et al.
patent: 5625692 (1997-04-01), Herzberg et al.
patent: 5706473 (1998-01-01), Yu et al.
patent: 5831853 (1998-11-01), Bobrow et al.
patent: 6134512 (2000-10-01), Barrett
patent: 0 653 716 (1995-05-01), None
Pixley et al., “Exact Calculation of Synchronizing Sequences Based on Binary Decision Diagrams”, IEEE Transcations on Computer-Aided Design of Integrated Circuits and Systems, Aug. 1994, pp. 1024-1034.*
Cabodi et al., “Symbolic Exploration of Large Circuits with Enhanced Forward / Backward Traversals”, Proceedings of the Conference on European Design Automation Conference, 1994, pp. 22-27.*
Iwashita et al., “CTL Model Checking Based on Forward State Traversal”, Proceedings of the 1996 IEEE/ACM International Conference on Computer-Aided Design, Nov. 1996, pp. 82-87.*
Peng et al.,Reachability and Reverse Reachability Analysis of CFSMs,Computer Communications, vol. 19, No. 8, Jul. 1996, pp. 668-674.
Takahara et al.,A Higher Level Hardware Design Verification,Proceedings of the 1988 IEEE International Conference on Computer Design: VLSI in Computers an
Day Herng-der
Jorgenson Lisa K.
Morris James H.
STMicroelectronics Limited
Teska Kevin J.
LandOfFree
Post image techniques does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Post image techniques, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Post image techniques will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3298034