Your browser does not support JavaScript!

access icon free 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.


    1. 1)
      • 9. Sagahyroon, A., Aloul, F.A., Sudnitson, A.: ‘Low power state assignment using ILP techniques’. 15th IEEE Mediterranean Electrotechnical Conf., 2010, pp. 850855.
    2. 2)
      • 21. Oughali, F.C., Sait, S.M., Arafeh, A.M.: ‘FSM state-encoding for area and power minimization using simulated evolution algorithm’, J. Appl. Res. Technol., 2012, 10, (6), pp. 845858.
    3. 3)
      • 26. Sait, S.M., Youssef, H.: ‘Iterative computer algorithms with applications in engineering: solving combinatorial optimization problems’ (IEEE Computer Society Press, CA, 1999).
    4. 4)
    5. 5)
    6. 6)
      • 24. Nedjah, N., de Macedo Mourelle, L.: ‘Evolutionary synthesis of synchronous finite state machines’. Int. Conf. on Computer Engineering and Systems, 2006, pp. 1924.
    7. 7)
      • 20. Khan, F.N.: ‘FSM state assignment for area, power and testability using non-deterministic evolutionary heuristics’. Master's thesis, KFUPM, Saudi Arabia, 2005.
    8. 8)
    9. 9)
    10. 10)
    11. 11)
      • 12. El-Maleh, A., Sait, S.M., Khan, F.N.: ‘Finite state machine state assignment for area and power minimization’. IEEE Int. Symp. on Circuits and Systems, 2006, pp. 53035306.
    12. 12)
      • 19. Yang, M.: ‘State assignment for finite state machine synthesis’, J. Comput., 2013, 8, (6), pp. 14061410.
    13. 13)
    14. 14)
    15. 15)
    16. 16)
      • 6. Lin, B., Newton, A.R.: ‘Synthesis of multiple-level logic from symbolic high-level description languages’. IFIP Int. Conf. on Very Large Scale Integration, 1989, pp. 187196.
    17. 17)
      • 8. Salauyou, V., Grzes, T.: ‘FSM state assignment methods for low-power design’. Sixth Int. Conf. on Computer Information Systems and Industrial Management Applications, 2007, pp. 345350.
    18. 18)
    19. 19)
      • 15. Pradhan, S.N., Kumar, M.T., Chattopadhyay, S.: ‘Integrated power-gating and state assignment for low power FSM synthesis’. IEEE Computer Society Annual Symp. on VLSI, April 2008, pp. 269274.
    20. 20)
      • 4. Villa, T., Sangiovanni-Vincentelli, A.: ‘Nova: state assignment of finite state machines for optimal two-level logic implementations’. 26th ACM/IEEE Conf. on Design Automation Conf., 1989, pp. 327332.
    21. 21)
      • 27. Available at
    22. 22)
      • 14. Chattopadhyay, S., Chetry, A., Biswas, S.: ‘State assignment and selection of types and polarities of flip-flops, for finite state machine synthesis’. IEEE INDICON, Kharagpur, India, December 2004, pp. 2730.
    23. 23)
    24. 24)
    25. 25)
    26. 26)
    27. 27)
      • 28. Sentovich, E.M., Singh, K.J., Lavagno, L., et al: ‘SIS: a system for sequential circuit synthesis’. EECS Department, University of California, Berkeley. Available at
    28. 28)
      • 23. Chyzy, M., Kosinski, W.: ‘Evolutionary algorithm for state assignment of finite machines’. Euromicro Symp. on Digital System Design, 2002, pp. 359362.
    29. 29)

Related content

This is a required field
Please enter a valid email address