BDD Ordering and Minimization Using Various Crossover Operators in Genetic Algorithm

Abstract: Binary Decision Diagram (BDD) is a data structure which is extensively used for compact representation of Boolean functions. On a more abstract level, BDDs can be considered as a compressed representation of sets or relations. BDDs are extensively used in CAD software to synthesize circuits (logic synthesis) and in formal verification. Ordering of BDDs play a major role in reduction of nodes and hence the area. In this paper, genetic algorithm with three crossover operators namely order, cycle and partially mapped has been proposed for minimization of shared ordered BDDs .The results have been compared using these three operators for Multi-input Adder Benchmark Circuits.

Keywords: Genetic, Optimization, Variable Ordering, BDDs, Multi-input Adders.