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:

1. State minimization: As the name suggests, the number of states required to represent FSM is minimized. Various techniques and algorithms like implication tables, row matching, and successive partitioning identify and remove equivalent or redundant states.
2. State assignment or encoding involves choosing boolean representations of the internal states of FSM. In other words, it assigns a unique binary code to each state. Selection of the right encoding technique is critical, since a wrong decision may result in an FSM that uses too much logic area, is too slow, consumes too much power, or any combination of these.
3. Combinational logic minimization uses unassigned state-codes as don't-care states in order to reduce the combinational logic.

Existing encoding techniques

Following are some of the techniques which are widely used for state encoding:

• In one-hot encoding, only one of the bits of the state variable is "1" (hot) for any given state. All the other bits are "0". The Hamming distance of this technique is 2. One-hot encoding requires one flip-flop for every state in the FSM. As a result, the state machine is already "decoded," so the state of the machine is determined simply by finding out which flip-flop is active. This encoding technique reduces the width of the combinational logic, and as a result, the state machine requires fewer levels of logic between registers, reducing its complexity and increasing its speed.
• In binary encoding, the number of bits (b) per state depends on number of states (n). The relationship is defined by the equation b = log₂(n). In this technique, the states are assigned in a binary sequence where the states are numbered starting from 0 and up. 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 combinational logic is required to decode each state when compared to one-hot encoding. Binary encoding requires fewer flip-flops when compared to one-hot encoding, but Hamming distances can be as worse—up to the number of bits (b).

• In Gray encoding, also known as reflected binary encoding, states are assigned so that consecutive state codes differ by only one bit. In this encoding, the relationship between number of bits and the number of states is defined by b = log₂(n). The number of flips-flops used and the complexity of the decoding logic is the same as in binary encoding, but the Hamming distance in Gray encoding is always 1.

Other encoding techniques include output-based encoding, MUSTANG, and 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 encoding gives minimum switching activity, and thus is suitable for low-power designs. Gray encoding is best-suited to cases where state changes are sequential. In arbitrary state changes, FSM Gray code fail to be a low-power design. 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 assignments which minimize 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 a boolean matrix with rows corresponding to state codes and columns corresponding to state variables. One state variable is considered at a time, and the algorithm tries 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 this minimization technique is applied column-by-column this technique is called the column-based approach.

Multi-code state assignment

The multi-code state assignment technique implements priority encoding by restraining redundant states. Thus, a 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. The procedure is as follows:

1. FSM state profiling collects information about the dynamic behavior of the FSM for a relevant input data set.
2. A loop detector searches for loops in the state trace, and each loop is stored and counted to obtain the frequency of the loops.
3. State assignment assigns state variables to each state based on the data gathered in the first two steps in order to minimize the switching activity. There are three algorithm to assign state variables:

• Basic DFS state assignment algorithm
• Loop-based DFS state assignment algorithm
• Loop-based per-state heuristic state assignment algorithm

Other techniques

• Some techniques encode state transition graphs (STG) to produce two-level and multi-level implementations targeting low power.
• Re-encoding of existing logic-level sequential circuits for power optimizations has been proposed.
• Spanning-tree-based state encoding
• Depth-first methods
• Minimum distance methods
• 1-level methods
• 1-level-tree method, where focus is again on assigning state variables to the different states such that switching activity due to state transition is reduced
• Apart from just encoding states for low power, some techniques involve decomposition of FSM into two or more sub-machines such that only one is active most of the time. The other sub-machine can be either clock-gated or power-gated.

See also

• Bus encoding
• DFA minimization
• Logic synthesis
• Low-power electronics
• Register-transfer level