Title :
On variable ordering and decomposition type choice in OKFDDs
Author :
Drechsler, Rolf ; Becker, Bernd ; Jahnke, Andrea
Author_Institution :
Inst. of Comput. Sci., Albert-Ludwigs-Univ., Freiburg, Germany
fDate :
12/1/1998 12:00:00 AM
Abstract :
We present methods for the construction of small ordered Kronecker Functional Decision Diagrams (OKFDDs). OKFDDs are a generalization of ordered binary decision diagrams (OBDDs) and ordered functional decision diagrams (OFDDs) as well. Starting with an upper bound for the size of an OKFDD representing a tree-like circuit, we develop different heuristics to find good variable orderings and decomposition types for OKFDDs representing two-level and multilevel circuits, respectively. Experimental results are presented to show the efficiency of our approaches
Keywords :
Boolean functions; binary decision diagrams; circuit complexity; OKFDDs; binary decision diagrams; decomposition type choice; ecision diagrams; multilevel circuits; ordered Kronecker Functional Decision Diagrams; tree-like circuit; upper bound; variable ordering; Boolean functions; Circuits; Data structures; Interleaved codes; Logic; Resumes; Upper bound;
Journal_Title :
Computers, IEEE Transactions on
