Title :
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
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;
Conference_Titel :
Information, Communications and Signal Processing, 1997. ICICS., Proceedings of 1997 International Conference on
Print_ISBN :
0-7803-3676-3
DOI :
10.1109/ICICS.1997.647099
