Novel state minimization and state assignment in finite state machine design for low-power portable devices

In this paper, we present a comprehensive method consisting of efficient state minimization and a comprehensive method of state assignment techniques to synthesize finite state machines (FSMs) to optimize power, area, and delay for “next-state” logic network design. The goal is to reduce the number of gates and literals relevant to power and area, and simultaneously to shorten the critical-path delay in FSM optimization. In the first step, we try to reduce the complexity of state minimization by applying (i) compatible graph to target one of optimal solutions in efficiency, (ii) conflict graph to determine the lower bound of the number of states and possible optimal solutions, (iii) Boolean expression effects due to alternative ways of minimized states, such that the required number of flip-flops is minimum for completely (or incompletely) specified FSMs. Next, a comprehensive method of state assignment techniques consisting of (i) edge-covering algorithm, (ii) block-reordering algorithm, (iii) cost calculation, (iv) ping-pong Gray-codes assignment, and (iv) design space exploration, is developed to choose the best state assignment. Finally, Espresso is run to determine the Boolean expressions and choose the best state assignment with the minimal sum-of-product (SOP) terms and literals from those optimal solutions. At last, the performance metrics in power, area, and delay are calculated based on the developed cell libraries for those optimal solutions with same minimized terms and literals. Our solutions provide engineers and designers to choose the best state assignment having less power, area, and delay to meet their system specification. Again this paper provides a comprehensive method of FSM synthesis and optimization for large FSMs in terms of power, area, and delay. Our experiments show that the derived optimal state assignment results in less power, area, and delay in FSM MCNC benchmarks.