Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-02-24
2002-01-15
Niebling, John F. (Department: 2812)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
Reexamination Certificate
active
06339837
ABSTRACT:
CROSS-REFERENCE TO RELATED APPLICATIONS
Not Applicable.
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
Not Applicable.
REFERENCE TO A MICROFICHE APPENDIX
Not Applicable.
BACKGROUND OF THE INVENTION
This invention relates to verification methods for electronic circuit designs' functional correctness using a computer program.
A digital circuit includes gates, registers and wires connecting the gates and registers. When people make a large digital circuit design, they write the design in a hardware description language. IEEE standards 1076 and 1364 are 2 well-known hardware description languages. For the purpose of avoiding erroneous chips, they have to verify that the design is functionally correct before transforming the design into a format used for fabricating the chip. As chips growing larger and larger, the existing verification methods are no longer able to guarantee their function correctness.
A method to verify functional correctness is to use a simulator. The simulator reads the circuit design and a set of stimulus values for the inputs of the circuit design. The simulator then computes the circuit design's response behavior. The circuit design's functional correctness is decided by comparing the computed response behavior with the expected behavior. These stimulus values are usually supplied in test benches. After the simulator is started, it can read only one test bench, and each test bench supplies only one stimulus value for any input of the circuit design unless the simulator advances the time. The simulator has to be started again before using a different test bench. Each run can only handle only one case while the circuit is designed to handle numerous different cases. This method can handle nearly all practical cases but it is not efficient because too many simulation runs are required for a large design and a lot of computation in the simulator is repeated too many times.
Another method to verify functional correctness is to use a model checker. The model checker reads the circuit design and a statement written in a temporal logic language. The model checker determines whether the statement exactly describes a property of the circuit design. It does this by first computing the state space and then verifying the property against the state space. The circuit design is functionally correct if the model checker gives a positive answer. This method is efficient but it does not work for large circuit designs because its memory requirement for the executing computer is often exponentially proportional to the circuit design's size, and this problem often happens in the step of computing the state space.
Some symbolic simulation methods also exist. They propagate expressions through gates and registers. These expressions can easily become too large for any computer to handle. These big expressions may not all be needed because often some outputs are not compared against the expectation.
Some hardware methods also exist for functional verification. They are much more expensive than the above software methods, and their efficiency is limited due to the limitation of hardware complexities.
Minimization methods for sequential machines were invented to reduce the size of a digital circuit design during synthesis process without changing the circuit's behavior, but they were not applied to functional verification before because (1) synthesis and functional verification have different minimization goals and (2) they traditionally use different subsets of hardware description languages.
Automatic test pattern generation (ATPG) methods for non-scan sequential machines were invented known to generate test sequences for detecting stuck-at-1 and stuck-at-0 faults that can happen after the digital circuits are fabricated, but they were not applied to functional verification before.
Changing digital circuits to combinatorial circuits using unrolling techniques was known and it was applied to a different context of traditional simulation in U.S. Pat. No. 5,752,000 to McGeer et al (1998). The unrolling techniques are well known to those skilled in the art for limited applications in ATPG, but they are generally not used for synthesis because the equivalence between the digital circuits and the combinational circuits is true only if the number of clock cycles being considered is below a given limit.
Equivalence checking between combinatorial circuits was known, and it was applied to a different and restricted form of digital circuit verification in U.S. Pat. No. 5,754,454 to Pixley et al (1998), where the complete equivalence between two digital circuits were to be proven. ATPG techniques for combinational circuits are known to be useful within this kind of equivalence checking.
BRIEF SUMMARY OF THE INVENTION
The present invention provides a method for verifying a digital circuit design in a hardware description language, using a verification structure and a verification engine. The verification structure is constructed by including a design under test and additional statements in the hardware description language so that the functional verification problem becomes whether the verification structure is equivalent to a predetermined constant. These additional statements are provided to describe input constraints and behavioral expectations, and they effectively describe a test bench with a group of test cases. The verification engine automatically gives a conclusion after analyzing the verification structure as a digital circuit design. The functional correctness of the design can be completely verified using a number of verification structures.
The objects and advantages of this invention are to provide functional verification methods that
(a) are efficient due to high coverage in each run,
(b) work well for large circuit designs because of avoiding a big bottleneck step, and
(c) do not require any language in addition to a hardware description language.
Further objects and advantages of this invention will become apparent from a consideration of the drawings and ensuing description.
REFERENCES:
patent: 5331568 (1994-07-01), Pixley
patent: 5465216 (1995-11-01), Rotem et al.
patent: 5481717 (1996-01-01), Gaboury
patent: 5491639 (1996-02-01), Filkorn
patent: 5493508 (1996-02-01), Dangelo et al.
patent: 5513122 (1996-04-01), Cheng et al.
patent: 5528165 (1996-06-01), Simovich et al.
patent: 5594656 (1997-01-01), Tamisler
patent: 5615137 (1997-03-01), Holzmann et al.
patent: 5752000 (1998-05-01), McGeer et al.
patent: 5754454 (1998-05-01), Pixley et al.
patent: 6083269 (2000-07-01), Graef
patent: 6141630 (2000-10-01), McNamara
Pixley, Carl, “Commercial Design Verification: Methodology and Tools”,1996 pp. 839-848.*
Kumar, “Designing a custom DSP Circuit Using VHDL”, Oct. 1990, pp. 46-52.*
Carl Pixley et al “Commercial Design Verification: Methodology and Tools” Proceedings of IEEE International Test Conference, 1996, pp. 839-848, IEEE, USA.
Abhijit Ghosh et al “Test Generation and Verification for Highly Sequential Circuits” IEEE Transaction on Computer-Aided Design, Vol. 10, No. 5, May 1991, pp. 652-667, IEEE, Piscataway, NJ, USA.
Srinivas Devadas “Approaches to Multi-Level Sequential Logic Synthesis” 26th ACM/IEEE Design Automation Conference, 1989, pp. 270-276, Association for Computing Machinery, New York, NY, USA.
J. Lawrence Carter et al “Restricted Symbolic Evaluation is Fast and Useful” Proceedings of International Conference on Computer-Aided Design, 1989, IEEE, USA.
Nagendra C.E. Srinivas et al “Formal Verification of Digital Circuit Using Hybrid Simulation” IEEE Circuits and Devices Magazine, Jan. 1988, pp. 19-27 The Institute of Electrical and Electronics Engineers, Inc. Piscataway, NJ, USA.
Niebling John F.
Whitmore Stacy
LandOfFree
Hybrid method for design verification does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hybrid method for design verification, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hybrid method for design verification will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2855394