Improved computational methods and lazy evaluation of the Ordered Ternary Decision Diagram

Author

Lindgren, Per

Author_Institution

Div. of Comput. Eng., Lulea Inst. of Technol., Sweden

fYear

1995

fDate

29 Aug-1 Sep 1995

Firstpage

379

Lastpage

384

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;

fLanguage

English

Publisher

ieee

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

Type

conf

DOI

10.1109/ASPDAC.1995.486249

Filename

486249