Evolutionary algorithms for synthesis and optimisation of sequential logic circuits.
Belgasem Ali · Edinburgh Napier Research Repository (Edinburgh Napier University) · 2026
Considerable progress has been made recently in the understanding of combinational logic optimization. Consequently, a large number of university and industrial Electronic Computer-Aided Design (ECAD) programs are now available for optimal logic synthesis of combinational circuits. The progress with sequential logic synthesis and optimization, on the other hand, is considerably less mature. In recent years, evolutionary algorithms have been found to be a remarkably effective way of using computers for solving difficult problems. This thesis is, in large part, a concentrated effort to apply this philosophy to the synthesis and optimization of sequential circuits. A state assignment based on the use of a Genetic Algorithm (GA) for the optimal synthesis of sequential circuits is presented. The state assignment determines the structure of the sequential circuit realizing the state machine and therefore its area and performance. The synthesis based on the GA approach produced designs with the smallest area to date. Test results on standard finite state machine (FSM) benchmarks show that the GA could generate state assignments which required, on average, 15.44% fewer gates and 13.47% fewer literals compared with alternative techniques. Hardware evolution is performed through a succession of changes/reconfigurations of elementary components, inter-connectivity, and selection of the fittest configurations until the target functionality is reached. The thesis presents new approaches which combine both genetic algorithms for state assignment and extrinsic Evolvable Hardware (EHW) to design sequential logic circuits. The implemented evolutionary algorithms are able to design logic circuits with size and complexity which have not been demonstrated in published work. There are still plenty of opportunities to develop this new line of research for the synthesis, optimization, and testing of novel digital, analogue, and mixed circuits. This should lead to a new generation of Electronic Design Automation tools.