Title :
Improved computational methods and lazy evaluation of the Ordered Ternary Decision Diagram
Author_Institution :
Div. of Comput. Eng., Lulea Inst. of Technol., Sweden
fDate :
29 Aug-1 Sep 1995
Abstract :
We investigate the properties of the Ordered Ternary Decision Diagram (OTDD) in order to develop an efficient general OTDD package. The OTDD is a three-branched three-terminal diagram based on Kleenean strong ternary logic. The OTDD can represent functions having nontrivial don´t-care sets in a single diagram and is capable of provably correct evaluation in the presence of unknown input values. We propose a number of improvements to both OTDD computational methods and data structures. Furthermore we introduce the purged form OTDD which unifies the abbreviated and full form OTDD into a single diagram. A package exploiting these OTDD specific properties is presented and we show the computational advantages of this improved package for LGSynth93 standard benchmarks
Keywords :
decision tables; logic CAD; ternary logic; Boolean functions; Ordered Ternary Decision Diagram; computational methods; data structures; don´t-care sets; lazy evaluation; standard benchmarks; ternary logic; three-terminal diagram; Application software; Benchmark testing; Boolean functions; Computational modeling; Computer applications; Logic testing; Multivalued logic; Packaging; Performance evaluation; Table lookup;
Conference_Titel :
Design Automation Conference, 1995. Proceedings of the ASP-DAC '95/CHDL '95/VLSI '95., IFIP International Conference on Hardware Description Languages. IFIP International Conference on Very Large Scal
Conference_Location :
Chiba
Print_ISBN :
4-930813-67-0
DOI :
10.1109/ASPDAC.1995.486249
