Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2007-12-21
2010-11-16
Doan, Nghia M (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C716S030000, C716S030000, C716S030000
Reexamination Certificate
active
07836413
ABSTRACT:
A method, system and computer program product for building decision diagrams efficiently in a structural network representation of a digital circuit using a dynamic resource constrained and interleaved depth-first-search and modified breadth-first-search schedule is disclosed. The method includes setting a first size limit for a first set of one or more m-ary decision representations describing a logic function and setting a second size limit for a second set of one or more m-ary decision representations describing a logic function. The first set of m-ary decision representations of the logic function is then built with one of the set of a depth-first technique or a breadth-first technique until the first size limit is reached, and a second set of m-ary decision representations of the logic function is built with the other technique until the second size limit is reached. In response to determining that a union of first set and the second set of m-ary decision representations do not describe the logic function, the first and second size limits are increased, and the steps of building the first and second set are repeated. In response to determining that the union of the first set of m-ary decision representations and the second set of m-ary decision representations describe the logic function, the union is reported.
REFERENCES:
patent: 5649165 (1997-07-01), Jain et al.
patent: 6473884 (2002-10-01), Ganai et al.
patent: 7290229 (2007-10-01), Baumgartner et al.
patent: 7340473 (2008-03-01), Paruthi
patent: 2003/0123576 (2003-07-01), Cleveland et al.
patent: 2006/0047680 (2006-03-01), Paruthi et al.
patent: 2006/0190868 (2006-08-01), Baumgartner et al.
patent: 2009/0164965 (2009-06-01), Paruthi et al.
Doan, N., Office Action dated Sep. 16, 2009; U.S. Appl. No. 11/963,267.
Anderson, H., “An Introduction to Binary Decision Diagrams,” Technical University of Denmark; Oct. 1997; 37 pp.
Bryant, R., “Graph-Based Algorithms for Boolean Function Manipulation,” IEEE Transactions on Computers, C-23-8′ pp. 677-691; Aug. 1986.
Rudell, R., “Dynamic Variable Ordering for Ordered binary Decision Diagrams,” IEEE; 1993; pp. 42-47.
Turbak, L., “Depth-First Search and Related Graph Algorithms,” Wellesley College, Handout #36; Nov. 28, 2001; 8 pp.
Doan, Nghia—Office Action dated Apr. 1, 2010; U.S. Appl. No. 11/963,267.
Jacobi Christian
Janssen Geert
Paruthi Viresh
Weber Kai Oliver
Xu Jiazhao
Dillon & Yudell LLP
Doan Nghia M
International Business Machines - Corporation
LandOfFree
Building binary decision diagrams efficiently in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Building binary decision diagrams efficiently in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Building binary decision diagrams efficiently in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4201730