Ordered and shared, linearly-independent, variable-pair decision diagrams

Author

Perkowski, Marek ; Jozwiak, Lech ; Drechsler, Rolf ; Falkowski, Bogdan

Author_Institution

Dept. of Electr. Eng., Portland State Univ., OR, USA

Volume

1

fYear

1997

fDate

9-12 Sep 1997

Firstpage

261

Abstract

The paper presents a new kind of decision tree: it is based on nonsingular expansions for pairs of variables. Such trees are used to create linearly independent (LI) decision diagrams (LI DDs). There are 840 nonsingular expansions for a pair of variables, so the number of nodes in such (exact) diagrams is never larger than that of trees with single-variable Shannon, positive Davio, and negative Davio expansions. The LI diagrams are a starting point in a synthesis of multilevel AND/OR/EXOR circuits and can potentially achieve better results than the well-known pseudo-Kronecker functional decision diagrams. They also introduce other gates than AND and EXOR to the synthesis process

Keywords

diagrams; logic design; logic gates; multivalued logic circuits; network synthesis; trees (mathematics); AND gates; EXOR gates; decision tree; linearly-independent decision diagrams; multilevel AND/OR/EXOR circuit synthesis; negative Davio expansion; nonsingular expansions; ordered decision diagrams; positive Davio expansion; pseudo-Kronecker functional decision diagrams; shared decision diagrams; single-variable Shannon expansion; variable-pair decision diagrams; variables; Circuit synthesis; Decision trees; Logic circuits;

fLanguage

English

Publisher

ieee

Conference_Titel

Information, Communications and Signal Processing, 1997. ICICS., Proceedings of 1997 International Conference on

Print_ISBN

0-7803-3676-3

Type

conf

DOI

10.1109/ICICS.1997.647099

Filename

647099