Engineering Commons^™

Efficient Algorithms For Creation Of Linearly-Independent Decision Diagrams And Their Mapping To Regular Layouts, Marek Perkowski, Bogdan Jaroslaw Falkowski, Malgorzata Chrzanowska-Jeske, Rolf Dreschler

Electrical and Computer Engineering Faculty Publications and Presentations

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 …