Genetic Programming Based Research On The Digital Circuit Design Automation

In the demanding of integrate circuit and computer technology, Electronics Design Automation (EDA) was developed as a kind of electronics design automation tool, which is very advanced, rapid, and effective. EDA is the developing trend of electronics design, and it can help the designers to complete most of the design work. EDA technology revolutionized the design of electronics systems. At the same time, more complex circuit behaviors are demanded, then consequently a bottleneck is developing at the point of circuit design. Evolvable Hardware (EHW) is a reconfigure hardware, which is based on the Programmable Logic Device (PLD). Whenever the environment is changed, EHW can automatically alter its own structure to fit the surroundings. The function specification is not necessary any more. Through the evolutionary computing, the variation of hardware structure could be self-organizing, self-learning, and self-adapting.One of the research focuses of EHW is the representation of the hardware circuit, which is also so-called circuit-coding method. Genetic Programming (GP) has nature competencies in the representation of hardware circuits, especially the digital circuits. GP is a new searching algorithm developed from Genetic Algorithm (GA), and normally tree structure is adopted as the individual representation. Before using GP, the terminators set and functions set should be defined. This is quite different from the binary string or real number coding method of GA. Therefore higher requirements to the genetic operations are demanded by GP. It's necessary for the genetic operators to keep the semantics of the tree structure chromosome, and relative mechanism should be used to ensure that the chromosome composed by tree nodes includes some problem space information.In this thesis, we used GP to evolve digital circuits, and made GP as the main evolution method of EHW. For accelerating the algorithm convergence, the conquer-and-divide theory was introduced into the evolution of circuits. A hierarchical coding method was adopted. The starting point of evolution is based on embryo-circuit included elementary information of the circuit. In the construction of the embryo-circuit, manual design combined with random generation ensured the determinacy and diversity of the circuits. The circuit was divided into several small and function independent modules, then through connecting the directed graphs, those small modules were combined into an integrated circuit again. So the evolution process was divided into two parts, one is the evolutionary based on GP inside the modules, and another is the evolutionary of the connected directed graphs. Based on this idea, a software-hardware co-design platform WU-EHW was developed. Here the genetic operators, evolving rules, population strategies, and fitness evaluating & distributing were studied. In the end of this thesis, with an example of pseudo random number generator circuit, the hierarchical parallel evolving strategy showed a good performance that it, not only improved the evolving speed, but also got a relative satisfying circuit.