Multi-Level Logic Synthesis Based on Kronecker Decision Diagrams and Boolean Ternary Decision Diagrams for Incompletely Specified Functions

This paper introduces several new families of decision diagrams for multi-output Boolean functions. The introducedfamilies include several diagrams known from literature (BDDs, FDDs) as subsets. Due to this property, these diagrams canprovide a more compact representation of functions than either of the two decision diagrams. Kronecker Decision Diagrams(KDDs) with negated edges are based on three orthogonal expansions (Shannon, Positive Davio, Negative Davio) and arecreated here for incompletely specified Boolean functions as well. An improved efficient algorithm for the construction ofKDD is presented and applied in a mapping program to ATMEL 6000 fine-grain FPGAs. Four other new families offunctional decision diagrams are also presented: Pseudo KDDs, Free KDDs, Boolean Ternary DDs, and Boolean KroneckerTernary DDs. The last two families introduce nodes with three edges and require AND, OR and EXOR gates for circuitrealization. There are two variants of each of the last two families: canonical and non-canonical. While the canonicaldiagrams can be used as efficient general-purpose Boolean function representations, the non-canonical variants are alsoapplicable to incompletely specified functions and create don't cares in the process of the creation of the diagram.. They leadto even more compact circuits in logic synthesis and technology mapping