This research applies the biologically inspired, artificial evolutionary processes of Genetic
Algorithms and Genetic Programming to digital hardware circuit synthesis and
minimization. In this new application, three approaches are taken to genetic hardware
development. First, as a method for logic synthesis, Genetic Programming is applied to the building of logic functions. Experimental results have shown the logic equations from this technique produce better than 88% coverage of the given truth-tables, but the method cannot guarantee complete (100%) coverage. Secondly, to better achieve complete function coverage, an XOR Correction Circuit Algorithm used in conjunction with the Genetic Logic Synthesis was developed. With this algorithm, the genetic logic synthesis can reiteratively attempt coverage by formulating its own selective "correction" functions, for input combinations where complete truth table coverage has not previously been achieved. With this technique, complete function coverage was synthesized in all experiments conducted. The third application of the paradigm is to the minimization of Reed-Muller Equations. In this application, a Genetic Algorithm is implemented only in the search space of all "correct", functionally equivalent equations, with only the task of finding reductions. With this limited search space the solutions have absolute guaranteed function coverage, as well as a better defined focus for the genetic evolutionary process.
In both the logic synthesis and minimization processes the genetic operators determine efficient circuit implementations and reductions. The results are often different from those of human designers. Because the genetic techniques incorporate logical testing into the design and build process, one can be assured that the circuit will function as derived on completion. For all three applications, the effects of a number of evolutionary parameters on the genetic operators' problem solving capability are examined. The resulting logic and logic minimizations are also compared with both arbitrarily defined functions and well known logic synthesis benchmarks. It has been shown that genetic operators applied to digital logic can effectively find good solutions for both logic synthesis and logic minimization. / Graduation date: 1997
| Identifer | oai:union.ndltd.org:ORGSU/oai:ir.library.oregonstate.edu:1957/34241 |
| Date | 21 June 1996 |
| Creators | Dill, Karen M. |
| Contributors | Herzog, James H. |
| Source Sets | Oregon State University |
| Language | en_US |
| Detected Language | English |
| Type | Thesis/Dissertation |
Page generated in 0.0019 seconds