Please use this identifier to cite or link to this item: http://hdl.handle.net/10266/3488
Title: Implementation of evolutionary algorithm with effective use of crossover operators for BDD mapped circuits
Authors: Sharma, Rohit Kumar
Bansal, Manu (Guide)
Keywords: Genetic algorithm,;variable ordering;Binary Decision Diagrams;Shannon expansion;ece;electronics;electronics and communication
Issue Date: 4-Aug-2015
Abstract: Binary Decision Diagrams are Data structure for representation and manipulation of Boolean functions. It is a canonical representation based on recursive Shannon expansion. The size of the BDD is hugely depends upon the order of the input variables. In BDD’s calculations, the major problem deals with calculating the fine order of variables. Since in VLSI Design, area of the logic circuit should be minimal as much as possible to reduce the chip size. There are many approaches such as Static, Dynamic and Heuristic techniques exist for obtaining the optimum order of variables in BDDs. Basic genetic algorithm is an efficient technique to find solutions of such problem. Crossover operators used in genetic algorithm also play significant role in finding good result. So, a crossover operator used for a problem should choose wisely. The main idea of this article is based on the efficient use of various crossover operators in Genetic and Hybrid Genetic algorithm for optimizing the variable order in BDDs. The applied Hybridized Genetic Algorithm is combination of the Genetic Algorithm and the Branch and Bound Algorithm whose main purpose is to search for the best solution of an optimization problem efficiently. Genetic Algorithm is a computational model which is inspired by evolution. When there is no mathematical analysis of a problem is available then GA is very useful technique. Branch and Bound technique set the upper and lower limit of solutions of a given problem. The proposed technique is applied on the LGSynth93 benchmark circuits with an aim to reduce the node count. Hence, as a result, the proposed methods provide optimal results for most of the benchmark circuits. Up to 82.02% reduction in area is found in 8 bit adder circuit. Comparison tables have been presented to show the effectiveness of the proposed algorithm as compared to other previously implemented state-of-art techniques for variable ordering of BDDs.
Description: MTech (VLSI Design)
URI: http://hdl.handle.net/10266/3488
Appears in Collections:Masters Theses@ECED

Files in This Item:
File Description SizeFormat 
3488.pdf1.74 MBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.