Sponsor
This research has been supported in part by the NSF grant MIP-9629419.
Published In
VLSI Design
Document Type
Article
Publication Date
2002
Subjects
Sequential machine theory, Switching theory, Logic programming (Computer science), Mappings (Mathematics)
Abstract
A new kind of a decision diagrams are presented: its nodes correspond to all types of nonsingular expansions for groups of input variables, in particular pairs. The diagrams are called the Linearly Independent (LI) Decision Diagrams (LI DDs). There are 840 nonsigular expansions for a pair of variables, thus 840 different types of nodes in the tree. Therefore, the number of nodes in such (exact) diagrams is usually much smaller than the number of nodes in the well-known Kronecker diagrams (which have only single-variable Shannon, Positive Davio, and Negative Davio expansions in nodes). It is usually much smaller than 1/3 of the number of nodes in Kronecker diagrams. Similarly to Kronecker diagrams, the LI Diagrams are a starting point to a synthesis of multilevel AND/OR/EXOR circuits with regular structures. Other advantages of LI diagrams include: they generalize the well-known Pseudo-Kronecker Functional Decision Diagrams, and can be used to optimize the new type of PLAs called LI PLAs. Importantly, while the known decision diagrams used AND/EXOR or AND/OR bases, the new diagrams are AND/OR/EXOR-based. Thus, because of a larger design space, multi-level structures of higher regularity can be created with them. This paper presents both new concepts and new efficient synthesis algorithms.
Persistent Identifier
http://archives.pdx.edu/ds/psu/12830
Citation Details
Perkowski, Marek, Bogdan Falkowski, Malgorzata Chrzanowska-Jeske, and Rolf Drechsler. "Efficient algorithms for creation of Linearly-Independent Decision Diagrams and their mapping to regular layouts." VLSI Design 14, no. 1 (2002): 35-52.
Description
Originally appeared in VLSI Design, vol. 14, no. 1, published by Hindawi. May be found at http://www.hindawi.com/journals/vlsi/