Data processing: structural design – modeling – simulation – and em – Simulating electronic device or electrical system – Circuit simulation
Reexamination Certificate
1999-04-09
2003-03-25
Broda, Samuel (Department: 2123)
Data processing: structural design, modeling, simulation, and em
Simulating electronic device or electrical system
Circuit simulation
C703S002000, C703S022000, C716S030000
Reexamination Certificate
active
06539345
ABSTRACT:
BACKGROUND
1. Field of the Invention
This invention relates to computer aided design (CAD). In particular, the invention relates to hardware functional verification.
2. Description of Related Art
As technology in computer aided design becomes mature, design verification has become more and more important to ensure design correctness of circuits. In formal design verification, checking logic functionality is a major step.
Approaches to logic checking include functional methods based on Boolean representations, such as Binary Decisions Diagrams (BDDs), and structural methods. Using a symbolic representation of Boolean functions, a generalized form of a problem can be expressed. Solving the generalized form leads to solutions of many specific problem instances. For example, the BDDs provide an efficient method to represent Boolean functions. BDDs are a canonical form, i.e., every Boolean function is represented by only one BDD. In certain approaches, logic checking with BDDs can be reduced to comparing two BDDs, a simple check for equality.
However, traditional approaches using Boolean expressions suffer a major drawback in that the design complexity (in terms of number of hardware elements) can lead to an exponential growth in the size of the BDDs. In traditional symbolic simulation approaches, distinct Boolean variables are applied at each circuit input. The circuit is then simulated until the symbolic output expressions are produced. These expressions are then restricted according to the input constraint(s) expressed by some Boolean predicate. For example, the results of symbolically simulating a floating-point adder with arbitrary inputs could be restricted by the desired constraints on the input nodes (e.g., to prevent illegal inputs, output overflow, or denormalization). As the circuit complexity grows, as is often the case with current designs, traditional approaches become impractical. The design complexity requires that the circuit be simultaneously simulated for all possible inputs with fully calculated outputs.
Jain and Gopalakrishnan (in “Efficient symbolic simulation-based verification using the parametric form of Boolean expression”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 13, No. 8, August 1994, pp. 1005-1015) discusses the use of symbolic simulation and the parametric form. However, their technique does not work for an arbitrary predicate and does not apply parameterization in performing input space decomposition. Their technique applies only to designs that can be described recursively, and requires that the predicate be transformed to disjunctive normal form, which is impractical or impossible for the complex predicates encountered in industrial circuits.
Therefore, there is a need for a technology to provide a simple, flexible, and efficient method to decompose the input space and enhance the capacity of the verification.
SUMMARY
The present invention is a method and apparatus to verify a design which has an input space and a predicate. The input space is decomposed into a plurality of decompositions. The input space includes a plurality of node variables. The plurality of decompositions includes parametric variables. The decompositions are parameterized into vectors of parametric functions to satisfy the predicate.
REFERENCES:
patent: 5649165 (1997-07-01), Jain et al.
patent: 6026222 (2000-02-01), Gupta et al.
Jain et al, “Some Techniques for Efficient Symbolic Simulation-based Verification”, IEEE 1992 International Conference on Computer Design: VLSI in Computers and Processors, pp. 598-602 (Oct. 1992).*
Pandey et al, “Formal Verfication of Memory Arrays Using Symbolic Trajectory Evaluation”, IEEE Proceedings of the International Workshop on Memory Technology, Design and Testing, pp. 42-49 (Aug. 1997).*
“Efficient Symbolic Simulation-Based Verification Using the Parametric Form of Boolean Expressions,” Prabhat Jain et al., IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 13, No. 8, Aug. 1994, pp. 1005-1015.
Jones Robert B.
Seger Carl-Johan H.
Blakely , Sokoloff, Taylor & Zafman LLP
Broda Samuel
Intel Corporation
LandOfFree
Symbolic simulation using input space decomposition via... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Symbolic simulation using input space decomposition via..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Symbolic simulation using input space decomposition via... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3052721