Majority-based evolution state assignment algorithm for area and power optimisation of sequential circuits

摘要

State assignment (SA) for finite state machines (FSMs) is one of the crucial synthesis steps in the design and optimisation of sequential circuits. In this study, we propose a majority-based evolution (MBE) SA algorithm that can be considered a variant of the well known differential evolution algorithm. Each individual is evolved based on selecting three random individuals, one of which is selected to be the best individual with a 50% probability. Then, for each state in the individual a selection is made with a 50% probability between keeping the current state or replacing it with a newly computed state. The bit values of the new state are determined based on the majority values of the state of the three selected individuals under a randomly generated probability within a predetermined range. The proposed algorithm is used for FSM state encoding targeting the optimisation of both area and power. Experimental results demonstrate the effectiveness of the proposed MBE SA algorithm in comparison with other evolutionary algorithms including genetic algorithm, binary particle swarm optimisation, Tabu search and simulated evolution.