Title :
Genetic algorithm for ordering and reduction of BDDs for MIMO circuits
Author :
Bansal, Mayank ; Agarwal, Abhishek
Author_Institution :
Thapar Univ., Patiala, India
Abstract :
Boolean function manipulation is an important component of many logic synthesis algorithms including logic optimization and logic verification of combinational and sequential circuits. Digital integrated circuits, often represented as Boolean functions, can be best-manipulated graphically in the form of Binary Decision Diagrams (BDD). Reduced-ordered binary decision diagrams (ROBDDs) are data structures for representation and manipulation of Boolean functions. The variable ordering largely influences the size of the BDD, varying from linear to exponential. In this paper, an evolutionary algorithm named genetic algorithm has been proposed for minimization of shared ordered BDDs by finding the optimal input variable ordering that aims to minimize the node count using Genetic algorithm. The proposed algorithm gives upto 79% less nodes for LGSynth93 Benchmark Circuits.
Keywords :
MIMO systems; binary decision diagrams; genetic algorithms; BDDs; LGSynth93 Benchmark Circuits; MIMO circuits; genetic algorithm; minimization; optimal input variable ordering; reduced-ordered binary decision diagrams; Biological cells; Boolean functions; Data structures; Genetic algorithms; Minimization; Sociology; Statistics; BDDs; Genetic Algorithm; LGSynth93. MIMO; Optimization; Variable Ordering;
Conference_Titel :
Innovative Computing Technology (INTECH), 2013 Third International Conference on
Conference_Location :
London
Print_ISBN :
978-1-4799-0047-3
DOI :
10.1109/INTECH.2013.6653717