MULTILEVEL 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 mu lti-output Boolean functions. The introduced families include several diagrams known from literature (BDDs, FDDs) as subsets. Due to this pr operty, these diagrams can provide a more compact representation of fu nctions than either of the two decision diagrams. Kronecker Decision D iagrams (KDDs) with negated edges are based on three orthogonal expans ions (Shannon, Positive Davio, Negative Davio) and are created here fo r incompletely specified Boolean functions as well. An improved effici ent algorithm for the construction of KDD is presented and applied in a mapping program to ATMEL 6000 fine-grain FPGAs. Four other new famil ies of functional decision diagrams are also presented: Pseudo KDDs, F ree KDDs, Boolean Ternary DDs, and Boolean Kronecker Ternary DDs. The last two families introduce nodes with three edges and require AND, OR and EXOR gates for circuit realization. There are two variants of eac h of the last two families: canonical and non-canonical. While the can onical diagrams can be used as efficient general-purpose Boolean funct ion representations, the non-canonical variants are also applicable to incompletely specified functions and create don't cares in the proces s of the creation of the diagram. They lead to even more compact circu its in logic synthesis and technology mapping.