Published In

VLSI Design

Document Type


Publication Date



Sequential machine theory, Switching theory, Logic programming (Computer science), Mappings (Mathematics)


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.


Originally appeared in VLSI Design, vol. 14, no. 1, published by Hindawi. May be found at

Persistent Identifier