Method and system for building binary decision diagrams...

Details Method and system for building binary decision diagrams... Method and system for building binary decision diagrams...

2008-03-04

2008-03-04

Kim, Chong H (Department: 3682)

Data processing: database and file management or data structures

Database design

Data structure types

C716S030000

Reexamination Certificate

active

07340473

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: 2003/0123576 (2003-07-01), Cleveland et al.
H. Andersen, An Introduction to Binary Decision Diagrams, Technical University of Denmark, Oct. 1997.
R. Bryant, Graph-Based Algorithms for Boolean Function Manipulation.
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.

Affiliated with

Also associated with

Rating

Method and system for building binary decision diagrams... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and system for building binary decision diagrams..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for building binary decision diagrams... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2801153