Data processing: structural design – modeling – simulation – and em – Modeling by mathematical expression
Reexamination Certificate
2006-12-12
2006-12-12
Rodriguez, Paul L. (Department: 2123)
Data processing: structural design, modeling, simulation, and em
Modeling by mathematical expression
C716S030000
Reexamination Certificate
active
07149663
ABSTRACT:
A method for selecting an order in which to sift variables in a binary decision diagram. The method includes an act of arranging the variables of the binary decision diagram on nodes of a graph, with the nodes of the graph being labeled with the variables of the system such that a set of functions labeling the leaves reachable from a node correspond to the set of functions which depend on the variables labeling the node. The method further includes an act of traversing the graph in a depth first manner to produce a list of the labels in the selected order.
REFERENCES:
patent: 5243538 (1993-09-01), Okuzawa et al.
patent: 5469367 (1995-11-01), Puri et al.
patent: 5477474 (1995-12-01), Southgate et al.
patent: 5522063 (1996-05-01), Ashar et al.
patent: 5640328 (1997-06-01), Lam
patent: 5649165 (1997-07-01), Jain et al.
patent: 5668732 (1997-09-01), Khouja et al.
patent: 5748486 (1998-05-01), Ashar et al.
patent: 5937183 (1999-08-01), Ashar et al.
patent: 6035107 (2000-03-01), Kuehlmann et al.
patent: 6086626 (2000-07-01), Jain et al.
patent: 6389374 (2002-05-01), Jain et al.
“Dynamic Minimization of OKFDDs”, Drechsler et al., IEEE 1995.
“Representation of Switching Circuits by Binay-Decision Programs”, Lee, The Bell System Technical Journal, Jul. 1959.
“Binary Decision Digrams”, IEEE 1978.
“Graph-Based Algorithms for Boolean Function Manipulation”, Bryant, IEEE 1986.
“The Size of Reduced OBDD's and Optimal REad-One Branching Programs for Almost All Boolean Functions”, Wegener, IEEE 1994.
“Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams”, Bryant, ACM 1992.
“Efficient Implementation of a BDD Package”, Brace et al., IEEE 1990.
“On the Complexity of VLSI Implementations and Graph Representations of Boolean Functions with Application to Integer Multiplication”, Bryant, IEEE 1991.
“Logic Verification using Binary Decision Diagrams in a Logic Synthesis Environment”, Malik et al., IEEE 1988.
“Evaluation and improvement of Boolean comparison method based on binary decision diagrams”, Fujita et al., IEEE 1988.
“On Variable Ordering of Binary Decision Diagrams for the Application of Multi-level Logic Synthesis”, Fujita et al., IEEE 1991.
“Interleaving Based Variable Ordering Methods for Ordered Binary Decision Diagrams”, Fujii et al., IEEE 1993.
“Breadth-First Manipulation of Very Large Binary-Decision Diagrams”, Ochi et al., IEEE 1993.
“Novel Verification Framework Combining Structural and OBDD Methods in a Synthesis Environment”, Reddy et al., ACM/IEEE 1995.
“Minimizing ROBDD sizes of incompletely specified Boolean functions by exploiting strong symmetries”, Scholl et al. IEEE Mar. 1997.
“Linear Sifting of Decision Diagrams”, Meinel et al., IEEE Jun. 1997.
Panda et al., Who Are the Variables in Your Neighborhood, ACM 1995.
Miller et al., Negation and Duality in Reduced Order Binary Decision Diagrams, IEEE Mar. 1997.
Chiodo et al., Synthesis of Software Programs for Embedded Control Applications, ACM 1995.
Panda et al., Symmetry Detection and Dynamic Variable Ordering of Decision Diagrams, ACM 1994.
Kimura-S., “Residue BDD and Its Application to the Verification of Arithmetic Circuits” 1995 ACM, p. 1-4.
Cockett et al., “Decision Tree Reduction” 1990 ACM p. 815-842.
Standard Search Report issued by the European Patent Office on Feb. 17, 1998.
Rudell R.: “Dynamic Variable Ordering For Ordered Binary Decision Diagrams”, IEEE/ACM International Conference On Computer Aided Design Digest Of Technical Papers (ICCAD), Santa Clara, Nov. 7-11, 1993, Conf. 11, Nov. 7, 1993, Institute Of Electrical And Electronics Engineers, pp. 42-47.
Fujii H.: “Implementation Techniques For Fast OBDD Dynamic Variable Reordering” IEICE Transactions On Fundamentals Of Electronics, Communications and Computer Sciences, vol. E78-A, No. 12, Dec. 1, 1995, pp. 1729-1734.
Bryant R.E.: “Binary Decision Diagrams And Beyond; Enabling Technologies For Formal Verification” 1995 IEEE/ACM International Conference On Computer-Aided Design (ICCAD), San Jose, Nov. 5-9, 1995, pp. 236-243.
Butler K.M., et al.: “Heuristics To Compute Variable Orderings For Efficient Manipulation Of Ordered Binary Decision Diagrams” Proceedings Of The ACM/IEEE Design Automation Conference, San Francisco Jun. 17-21, 1991, Conf. 28, Institute Of Electrical and Electronics Engineers, pp. 417-420.
Examination Report from corresponding European Application No. 98307486.5, dated Dec. 1, 2004.
Rudell, R.,Dynamic Variable Ordering for Ordered Binary Decision Diagrams, IEEE/ACM International Conference on Computer Aided Design Digest of Technical Papers (ICCAD), Santa Clara, Nov. 7-11, 1993, No. Conf. 11, Nov. 7, 1993, pp. 42-47, Institute of Electrical and Electronics Engineers, XP000462999.
Bryant R.E.,Binary Decision Diagrams and Beyond; Enabling Technologies for Formal Verification, 1995 IEEE/ACM International Conference on Computer Aided Design Digest of Technical Papers (ICCAD), San Jose, Nov. 5-9, 1995, pp. 236-243, Institute of Electrical and Electronics Engineers, XP000620913.
Jorgenson Lisa K.
McLoughlin Daniel P.
Rodriguez Paul L.
SGS-Thomson Microelectronics Limited
Stevens Tom
LandOfFree
Method and apparatus for restructuring a binary decision... 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 restructuring a binary decision..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for restructuring a binary decision... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3714613