Conjunctive BDD building and variable quantification using...

Details Conjunctive BDD building and variable quantification using... Conjunctive BDD building and variable quantification using...

2007-05-10

2010-06-15

Do, Thuan (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000, C716S030000, C703S013000, C703S014000

Reexamination Certificate

active

07739635

ABSTRACT:
A method, apparatus and computer-readable medium for conjunctive binary decision diagram building and variable quantification using case-splitting are presented. A BDD building program builds a BDD for at least one node in a netlist graph representation of a circuit design. One or more variables are selected for case-splitting. The variable is set to a constant logical value and then the other. A BDD is built for each case. The program determines whether the variable is scheduled to be quantified out. If so, the program combines the BDDs for each case according to whether the quantification is existential or universal. If the variable is not scheduled to be quantified, the program combines the BDDs for each case so that the variable is introduced back into the resulting BDD, which has a reduced number of peak live nodes.

REFERENCES:
patent: 5502661 (1996-03-01), Glunz
patent: 5623418 (1997-04-01), Rostoker et al.
patent: 5910897 (1999-06-01), Dangelo et al.
patent: 5946472 (1999-08-01), Graves et al.
patent: 6052524 (2000-04-01), Pauna
patent: 6088821 (2000-07-01), Moriguchi et al.
patent: 6327687 (2001-12-01), Rajski et al.
patent: 6353806 (2002-03-01), Gehlot
patent: 6359345 (2002-03-01), Suzuki
patent: 6634012 (2003-10-01), Zhong et al.
patent: 6745160 (2004-06-01), Ashar et al.
patent: 6842750 (2005-01-01), Andreev et al.
patent: 7096138 (2006-08-01), Akli et al.
patent: 7340473 (2008-03-01), Paruthi et al.
patent: 7363603 (2008-04-01), Jacobi et al.
patent: 2002/0156540 (2002-10-01), Akli et al.
Peranandam et al.; “Transaction Level Verification and Coverage Metrics by Means of Symbolic Simulation”; Department of Computer Engineering; University of Tübingen, 2004, p. 260-269.
H. Andersen; “An Introduction Into Binary Decision Diagrams”; Technical University of Denmark; Oct. 1997.
R. Bryant; “Graph-Based Algorithms for Boolean Function Manipuation”; IEEE Transactions on Computers; C-35-8; pp. 667-691; Aug. 1986.
R. Rudell; Dynamic Variable Ordering for Ordered Binary Decision Diagrams; IEEE; 1993; pp. 42-47.
L. Turbak; “Depth-First Search and Related Graph Algorithms”; Wellesley College; Nov. 28, 2001.
Peranandam et al., “Transaction Level Verification and Coverage Metrics by Means of Symbolic Simulation”; Department of Computer Engineering, University of Tubingen; 2004; pp. 260-269.
Anderson, “An Introduction to Binary Decision Diagrams”; Lecture notes for 49285 Advanced Algorithms E97; Department of Information Technology, Technical University of Denmark; Oct. 1997; 37 pp.
Bryant, “Graph-Based Algorithms for Boolean Function Manipulation”; Abstract; Department of Computer Science, Carnegie-Mellon University, Pittsburgh, PA; IEEE Transactions on Computers (Update—Aug. 1986); 28 pp.
Rudell, “Dynamic Variable Ordering for Ordered Binary Decision Diagrams”; 1993 IEEE; 6 pp.
Turbak, “Depth-First Search and Related Graph Algorithms”; Handout #36, CS231 Algorithms, Wellesley College; Nov. 2001; 8 pp.

Affiliated with

Also associated with

Rating

Conjunctive BDD building and variable quantification using... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Conjunctive BDD building and variable quantification using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Conjunctive BDD building and variable quantification using... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4208153