State encoding for low power

State encoding assigns a unique pattern of ones and zeros to each defined state of a finite-state machine (FSM). Traditionally, design criteria for FSM synthesis were speed, area or both. Following Moore's law, with technology advancement, density and speed of integrated circuits have increased exponentially. With this, power dissipation per area has inevitably increased, which has forced designers for portable computing devices and high-speed processors to consider power dissipation as a critical parameter during design consideration.
Background.
Synthesis of FSM involves three major steps:
Existing encoding techniques.
Following are some of the techniques which are widely used for state encoding:
 b = log2(n)
In this technique, the states are assigned in binary sequence where the states are numbered starting from binary 0 and up. Clearly, the number of flip-flops used is equal to the number bits(b). Since Binary encoding uses the minimum number of bits (flip-flops) to encode a machine the flip-flops are maximally utilized. As a result, more combinatorial logic is required to decode each state when compared to One Hot. Requires fewer flip-flops when compared to One hot but hamming distance can be as worse as number of bits(b).
In Gray code, also known as reflected binary code, state are assigned such that consecutive state codes differ by only one bit. In this encoding also the relationship between number of bits and the number of states is defined by
 b = log2(n)
Number of flips-flops used and the complexity of the decoding logic is same as Binary encoding. But the hamming distance in Gray code is always 1.
Output based encoding, MUSTANG, NOVA,
Motivation.
The main idea in the design of state encoding for low power is to minimize the Hamming distance of the most probable state transitions, which reduces switching activity. Thus, a cost model for minimizing power consumption is to have a minimum-weighted Hamming distance(MWHD).
For counters, Gray coding gives minimum switching activity, and thus is suitable for low-power designs. Gray encoding suits best when state change are sequential. In arbitrary state changing, FSM Gray code fails for low-power designs. For such FSM, one-hot encoding guarantees switching of two bits for every state change. But since the number of state variables needed is equal to the number of states, as states increase, one-hot encoding becomes an impractical solution, mainly because with an increased number of inputs and outputs to the circuit, complexity and capacitive load increase. Binary coding is worst for low power since the maximum Hamming distance is equal to the number of state variables.
The need to have a solution for arbitrary state changing FSM has led to several state encoding techniques which focus on reducing the switching activity during state transitions.
Techniques.
Column-based approach for low-power state assignment.
This approach aims to reduce power dissipation by sequential circuits by choosing state assignment which minimizes the switching activity between state transitions. Thus the combinational part of FSM has lower input transition probability and is more like to give low power dissipation when synthesized. This algorithm uses boolean matrix with rows corresponding to state codes and column corresponding to state variables. Single state variable is considered at a time and try to assign its value to each state in FSM, in a way which is likely to minimize the switching activity for the complete assignment. This procedure is repeated for the next variable. Since minimization technique is applied column by column this technique is called as Column based.
Multi-code state assignment.
Multi-code state assignment technique implements priority encoding by restraining redundant states. Thus state can be encoded using fewer state variables (bits). Further, flip-flops corresponding to those absent state variables can be clock-gated.
Profiling-based state assignment.
This technique utilizes dynamic loop information extracted from FSM profiling data for state assignment in-order to reduce switching activity. Following are the steps this technique uses: