Investigation of Solution Space of Trees and DAGs for Realization of Combinational Logic in AT 6000 series FPGAs

Various tree and Directed Acyclic Graph structures have been used for representation and manipulation of switching functions. Among these structures the Binary Decision DiagramJilave been the most widely used in logic synthesis. A BDD is a binary tree graph that represents the recursive execution of Shannon\u27s expansion. A FDD is a directed function graph that represents the recursive execution of Reed Muller expansion. A family of decision diagrams for representation of Boolean function is introduced in this thesis. This family of Kronecker Functional Decision Diagrams (KFDD) includes the Binary Decision Diagrams (BDD) and Functional Decision Diagrams (FDD) as subsets. Due to this property, KFDDs can provide a more compact representation of the functions than either of the two above-mentioned decision diagrams. The new notion of permuted KFDD is introduced to generate a compact circuit in FPGAs to represent a switching function. A permuted tree search is a free search method which is not limited by the order of variable and the expansion tree as in the cases of KFDD, BDD and FDD. A family of decision diagrams and the theory developed for them are presented in this thesis. The family of permuted Kronecker Functional Decision Diagrams includes BODs and FDDs as subsets is incorporated into program RESPER. Due to this property, permuted KFDD can provide a more compact circuit realization in the multilevel circuit. The circuit obtained can be realized directly with FPGAs like AT 6000 series from Atmel. This algorithm is implemented on several MCNC benchmarks, the results compared with previous programs, TECHMAP and REMIT, are very encouraging. The main achievement of this thesis is the creation of the algorithm which applies a permuted tree search method combined with Davio Expansion and generates Directed Acyclic Graph which is next mapped to a compact circuit realization