State assignment for low power dissipation

We address the problem of reducing the power dissipated by synchronous sequential circuits. We target the reduction of the average switching activity of the input and output state variables by minimizing the number of bit changes during state transitions. Using a probabilistic description of the finite state machines, we propose a state assignment algorithm that minimizes the Boolean distance between the codes of the states with high transition probability. We formulate a general theoretic framework for the solution of the state assignment problem, and propose different algorithms trading off computational effort for quality. We then generalize our model to take into account the estimated area of a multilevel implementation during state assignment, in order to obtain final circuits where the total power dissipation is minimized. A heuristic algorithm has been implemented and applied to standard benchmarks, resulting in a 16% average reduction in switching activity