Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2001-11-20
2003-09-09
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
Reexamination Certificate
active
06618841
ABSTRACT:
BACKGROUND
1. Field
The present invention relates generally to formal verification of circuit designs and, more particularly, to the support of non-assignable signal designations in a circuit design during formal verification.
2. Description of the Related Art
With the increasing complexity of integrated circuits (ICs), computer-aided design (CAD) and computer-aided engineering (CAE) tools are becoming increasingly important in assisting and enabling circuit designers produce the complicated ICs. An ongoing problem in the design of these complex circuit designs is verifying that the circuit design behaves in the manner intended by its designer. Formal verification is a generally accepted method of verifying the correctness of a circuit design.
Formal verification involves verifying or proving one or more properties of a circuit design. A property is some relation, either logical (Boolean) or temporal, between one or more signals in the circuit design. The property can be considered as a signal that is generated by the relation between the signals in the circuit design. Formal verification is used to verify that the circuit property holds for all combinations of input sequences over time. To verify that a property holds, conventional formal verification tools or methods search all the circuit state space and ensure that the property is not contradicted. The formal verification tool tries to show an instance of property NOT (e. g., assuming that the property is designated by P, the formal verification tool tries to find an instance of P NOT) to show an existence of a contradiction. If a contradiction exists, the property does not hold (i.e., the property is disproved).
Conventional formal verification tools check the circuit design and produce a counter-example to indicate an existence of a contradiction. A counter-example is typically a test sequence that disproves a property (e.g., the test sequence shows the existence of property NOT). A test sequence is a sequence of assignments on, for example, the primary input signals or certain internal signals in the circuit design.
In a typical formal verification process, if a counter-example is produced or generated, a designer checks to see what signals caused the counter-example. In checking the signals, the designer may determine that the counter-example was caused by or involved or included one or more non-assignable signals. A non-assignable signal is a signal that is not to be assigned to a value (i.e., a signal that that should not have an assignment to a value). For example, the signal may be associated with a portion of the circuit design that is incomplete and, thus, should not be assigned a value. If the counter-example includes a non-assignable signal, it is not a “true” counter-example, and the designer typically requests the formal verification tool to generate the next counter-example, if one exists.
A drawback with conventional formal verification tools is that it does not support non-assignable signals. Thus, the designer has to expend time and resources to check and verify that a generated counter-example is a true counter-example and not a counter-example that includes what the designer considers a non-assignable signal. What is needed is a formal verification tool or method that enables the designer to designate certain signals in the circuit design as non-assignable, and that verifies the circuit design by accounting for the designated non-assignable signals. Using a formal verification tool that supports the designation of non-assignable signals, the designer can be assured that any counter-example generated is a true counter-example.
SUMMARY
Embodiments of the present invention overcome many of the aforementioned disadvantages by providing a formal verification system and method that supports non-assignable signals. The formal verification system enables a user (e.g., a circuit designer) to specify one or more non-assignable signals in a circuit design. The signals are generally associated with circuit elements or variables, such as, by way of example, black-box pins, floating elements, unknown initial values from combinatorial circuits or loops, flip-flops, latches, unknown values due to bus contention, and the like.
In one embodiment, the formal verification system identifies or tags non-assignable signals by assigning a value to each non-assignable signal in a circuit design. The formal verification system ensures that non-assignable signals are not identified as decision signals during formal verification of the circuit design. The formal verification system utilizes a non-assignable truth table, which specifies propagation logic for the non-assignable signal, to propagate the non-assignable signals while performing logic implication during formal verification of the circuit design. Thus, the formal verification system ensures that any counter-example produced does not include a non-assignable signal.
In another embodiment, the formal verification system utilizes the non-assignable truth table to generate a function, such as, by way of example, a Binary Decision Diagram (BDD), for the property NOT (e.g., a function that shows a counter-example and that disproves the property). In particular, the formal verification system utilizes the propagation logic for the non-assignable signal specified in the non-assignable truth table to propagate the non-assignable signals while generating the function for the property NOT. Because the generated function accounts for the non-assignable signals, the formal verification system can ensure that that any counter-example produced does not include a non-assignable signal.
For purposes of summarizing the invention, certain aspects, advantages, and novel features of the invention have been described herein. It is to be understood that not necessarily all such advantages may be achieved in accordance with any one particular embodiment of the invention. Thus, the invention may be embodied or carried out in a manner that achieves or optimizes one advantage or group of advantages as taught herein without necessarily achieving other advantages as may be taught or suggested herein.
A technical advantage of the present invention includes providing a formal verification system and method that supports non-assignable signals in performing formal verification of a circuit design. A circuit designer can perform formal verification on an unfinished or incomplete circuit design by specifying or designating the signals associated with the incomplete portion of the circuit design as non-assignable. The formal verification system accounts for the non-assignable signals by ensuring that any counter-example produced does not include a non-assignable signal. Thus, the designer is able to perform formal verification in stages.
Anther technical advantage of the present invention includes providing a more efficient formal verification system and method. The designer is able to designate parts or sections of the circuit design that the formal verification system is not to verify. For example, the designer can designate certain parts or sections of the circuit design (e.g., incomplete parts of the circuit design, golden parts of the circuit design, etc.) that is not to be the cause of a counter-example. The formal verification system need not verify these designated sections (i.e., the designated non-assignable signals) and, thus, is more efficient in performing formal verification of the remaining parts or sections (i.e., non-designated or assignable signals) of the circuit design.
These and other embodiments of the present invention will also become readily apparent to those skilled in the art from the following detailed description of the embodiments having reference to the attached figures, the invention not being limited to any particular embodiment(s) disclosed.
REFERENCES:
patent: 5276897 (1994-01-01), Stalmarck
patent: 5572535 (1996-11-01), Pixley et al.
patent: 5862149 (1999-01-01), Carpenter et al.
patent: 5937183 (1999-08-01), Ashar et al.
patent: 6038392 (2000-03-01), Ashar et al.
pa
Liu Andrea
Suzue Kenta
Verplex Systems, Inc.
Wilson Sonsini Goodrich & Rosati
LandOfFree
Non-assignable signal support during formal verification of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Non-assignable signal support during formal verification of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Non-assignable signal support during formal verification of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3063416