Evolutionary algorithms for synthesis and optimisation of sequential logic circuits.

Ali, Belgasem

Abstract

Considerable progress has been made recently 1n the understanding of
combinational logic optimization. Consequently a large number of university
and industrial Electric Computing 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 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 performances. The synthesis based on the GA
approach produced designs with the smallest area to date. Test results on
standard fmite state machine (FS:M) 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 succeSSlOn 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 algorithm
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 test of novel digital, analogue and mixed
circuits. This should lead to a new generation of Electronic Design
Automation tools.

• Thesis Type: Thesis
• Deposit Date: Apr 14, 2011
• Peer Reviewed: Not Peer Reviewed
• Keywords: Combinational logic optimisation; Electric Computing Aided Design; evolutionary algorithms; synthesis; sequential circuits; genetic algorithms
• Public URL: http://researchrepository.napier.ac.uk/id/eprint/4338
• Contract Date: Apr 14, 2011
• Award Date: 2003-05