Low power state assignment and flipflop selection for finite state machine synthesis—a genetic algorithmic approach

Low power state assignment and flipflop selection for finite state machine synthesis—a genetic algorithmic approach

For access to this article, please select a purchase option:

Buy article PDF
(plus tax if applicable)
Buy Knowledge Pack
10 articles for $120.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Your details
Why are you recommending this title?
Select reason:
IEE Proceedings - Computers and Digital Techniques — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

Current renewed emphasis for more aggressive logic designs with lesser area, delay, and power demands exploration of alternative avenues that could lead to better designs, albeit at the higher cost of computation. The author explores the avenue of genetic algorithm for a holistic view for synthesis of finite state machine (FSM) targeting power reduction by incorporating both state assignment and sequential element selection. Exhaustive experimentation performed on a large suite of benchmarks has established the fact that this tool results in state encodings with on average 46.08% reduction in power requirement over NOVA, without any significant increase in the number of product terms. The effectiveness of judicious flipflop selection has been demonstrated by showing that the approach with all D-flipflops as the sequential element requires 33.78% more power than the approach with a choice of D and T flipflop types. Moreover, as compared to the technique presented in LPSA, the algorithm presented here requires 38.96% less power when using a mix of D and T flipflops. The quality of the solution obtained and the high rate of convergence have established the effectiveness of the genetic algorithm in solving this particular NP-complete problem. Further, the inherent parallelism of genetic algorithm makes the proposed scheme ideal for solving the problem in a multiprocessor environment.


    1. 1)
      • VILLA, T., VINCENTELLI, A.S.: `NOVA: state assignment of finite state machines for optimal two-level logic implementation', 26th Design Automation Conference, June 1989.
    2. 2)
      • DEVADAS, S., MA, H.K.T., NEWTON, A.R., VINCENTELLI, A.S.: `Mustang: state assignment of finite state machines for optimalmulti level logic implementations', Proc. of ICCAD, 1987.
    3. 3)
      • LIN, B, NEWTON, A.R.: `Synthesis of multiple level logic from symbolic high-level description languages', Proc. of VLSI Conference, August 1989.
    4. 4)
      • ROY, K., PRASAD, S.: `Syclop: synthesis of CMOS logic for low power applications', ICCD 92, 1992, p. 464–467.
    5. 5)
      • OLSON, E., KANG, S.: `Low-power state assignment for finite state machines search', International Workshop on Low power design, 1994, p. 63–68.
    6. 6)
      • L. Benini , G. De Micheli . State assignment for low power dissipation. IEEE J. Solid-State Circuits , 3 , 258 - 268
    7. 7)
      • HATCHEL, G., HERMIDA, M., PARDO, A., PONCINO, M., SOMENZI, F.: `Reencoding sequential circuits to reduce power dissipation', ICCAD, 1994, p. 70–73.
    8. 8)
      • KUMTHEKAR, B., MOON, I., SOMENZI, F.: `A symbolic algorithm for low-power sequential synthesis', Proc. Int. Symp. on Low-power electronics and design, 1997.
    9. 9)
      • C.-Y. TSUI , M. PEDRAM , A.M. DESPAIN . (1994) Low power state assignment targeting two- and multi-level logic implementations, ICCAD.
    10. 10)
      • SENTOVICH, E., SINGH, K., LAVAGNO, L., MOON, C., MURGAI, R., SALDANHA, A., SAVOJ, H., STEPHAN, P., BRAYTON, R., SANGIOVANNI-VINCENTALLI, A.: `SIS: a system for sequential circuit synthesis', Tech. Rep. M92/41, 1992.
    11. 11)
      • J.H. Holland . (1975) , Adaptation in natural and artificial systems.
    12. 12)
      • J. AMARAL , K. TUMER , J. GHOSH . Designing genetic algorithms for the state assignment problem. IEEE Trans. Syst., Man. Cyber. , 687 - 694
    13. 13)
      • CHATTOPADHYAY, S., CHAUDHURI, P.P.: `Genetic algorithm based approach for integrated state assignment and flipflop selection in finite state machine synthesis', Proc. of 11th International Conference on VLSI design, 1998.
    14. 14)
      • J. MONTEIRO , S. DEVADAS . (1999) , Computer-aided design techniques for low power sequential logic circuits.

Related content

This is a required field
Please enter a valid email address