Multilevel logic synthesis for cellular FPGAs based on orthogonal expansions

The cellular ne grain architectures of new Field Programmable Gate Arrays FPGAs require spe cial logic synthesis tools Therefore this paper ad dresses multilevel logic synthesis methods based on or thogonal expansions for such kind of architectures First the concepts of the Binary Decision Diagrams BDDs their derivatives and the Functional De cision Diagrams FDDs which are applied to the technology mapping to Field Programmable Gate Ar rays FPGAs are generalized here to the Kronecker Functional Decision Diagram KFDD with negated edges Three other new types of functional decision diagrams are also introduced IfThenElse KFDDs Mixed KFDDs and Permuted KFDDs The intr