Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-10-07
2002-05-07
Shah, Sanjiv (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C716S030000
Reexamination Certificate
active
06385617
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates generally to an improved data processing system and in particular to a method and apparatus for representing billing and functions. Still more particularly, the present invention relates to a method and apparatus for representing boolean functions using binary decision diagrams.
2. Description of Related Art
In designing circuits, many types of elements may be used in logic design and synthesis of circuits. Typically, these circuits include various components, such as, for example, gates and latches. In analyzing and manipulating these structures, the various elements are typically represented as nodes in a binary decision diagram (BDD). These BDD's are widely used as a data structure for representing boolean expressions in design automation tools. These BDD's have emerged as the representation of choice for many other applications, including digital circuit design. Many formal verification techniques, including model checking, equivalence checking, optimization of combinatorial circuits, and test pattern generation, have a fundamental reliance on BDD's and their implementations. These type of diagrams have a disadvantage in that they grow very large very quickly. For example, using a BDD to represent a 16-bit multiplexer takes one half of a gigabyte of memory. With these increasing trends towards increased design complexity, an even greater demand on improving memory requirements for BDD's is present. Generally, memory requirements for BDD's grow exponentially with the number of boolean variables. Numerous improvements have been made on BDD structures, such as the efficient BDD package by Randall Bryant as described in Graph-Based Algorithms for Boolean Function Manipulation, IEEE Transactions on Computers, C-35 August 1998, pgs. 677-691. Even with improvements, memory requirements still pose a limiting factor to the use of BDD's for large diagrams. For example, in model checking, the BDD memory requirements have made it impossible to verify a full chip of any significant function in its entirety.
In an effort to reduce the amount of memory used by a BDD representation of a chip, compression of these diagrams have been used. Compression presently used may yield anywhere from a 2× to 10× reduction in many practical cases, excluding those in which data is statistically uniformly distributed, which is a rare situation. Lossless compression, however, renders the data unusable for random access. As a result, such compression is typically used only towards keeping data compressed for archival purposes and not for use during computation as in the case of BDD data.
Therefore, it would be advantageous to have an improved method and apparatus for compressing and manipulating BDD data in a manner that random access of the BDD data is provided.
SUMMARY OF THE INVENTION
The present invention provides a method and apparatus in a data processing system for manipulating a set of binary decision diagrams. A plurality of segments is created from the set of binary decision diagrams. A group of compression codes is associated with the set of segments, wherein the group of compression codes form a compressed data structure representing the set of binary decision diagrams.
REFERENCES:
patent: 5469367 (1995-11-01), Puri et al.
Byrant, Randal E.; Graph-Based Algorithms for Boolean Function Manipulation; IEEE Transaction on Computers; vol C-35; No. 8, Aug. 1986; pp. 677-691.
International Business Machines - Corporation
McBurney Mark E.
Shah Sanjiv
Yee Duke W.
LandOfFree
Method and apparatus for creating and manipulating 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 Method and apparatus for creating and manipulating a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for creating and manipulating a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2901385