# Basic Approaches for Reducing Power Consumption in Finite State Machine Circuits--A Review
## 5 Saving Power by State Assignment
Of course, this is true only for the investigated benchmarks and that particular FPGA chip. The saving amount can be different for a different suite. It is interesting that the discussed methods do not use probabilities of interstate transitions. If we take them into account, we can reduce the switching activity, \(\alpha\). To do it, some special state assignment methods are used. One of the first algorithms decreasing the switching activity was proposed in [85]. It targets a state assignment that minimizes the switching activity and takes into account the issue of area. Due to this integral approach, both types of power consumption, static and dynamic, are optimized. The method is based on a probabilistic description of FSMs. The method uses an average switching activity to find the switching (transition) probability. This allows the obtainment of the probabilities of FSM interstate transitions. This information is used for executing the state assignment. But to do it, it is necessary to have the input switching probabilities. In [85], an STG is modeled as a Markov chain [114]. The Markov chain model describes an STG as a directed graph with weighted edges and a structure isomorphic to the initial STG. The STG is transformed into a weighted undirected graph. The weight of each edge is proportional to the total probability of a transition between FSM states \(a_{m},a_{s}\in A\) connected by this edge. This final STG is used as the initial information for the state assignment step. The main idea of [85] is \"to find a state assignment that minimizes the number of state variables that change their values when the FSM moves between two adjacent states\". In the best case, only a single state variable is changed, as it is for Gray codes. But \(M/2\) state variables are necessary for the Gray state assignment. The aim of [85] was to find the value of state code bits close to the minimum value defined by (4). A state encoding is represented by a Boolean matrix. Its rows correspond to state codes and columns to state variables. The required state assignment can be found by the solution of the integer linear programming problem formulated in [85]. For small FSMs, it is possible to find the exact solution. For complex FSMs, only a suboptimal solution can be found because the problem is NP-complete. Thus, there are a lot of heuristic algorithms for its solution [90; 91; 115]. In [85], the column-based approach \begin{table}
\begin{tabular}{l l l l l l l} \hline
**Characteristics** & **Method** & **bbara** & **dk512** & **ex4** & **kirkman** & **planet** \\ \hline Area (CLB + FF) & Binary & \(11+3\) & \(14+4\) & \(22+4\) & \(45+4\) & \(113+6\) \\  & One-hot & \(8+7\) & \(10+14\) & \(15+14\) & \(43+16\) & \(65+48\) \\  & JEDI & \(10+3\) & \(9+4\) & \(19+4\) & \(45+4\) & \(106+6\) \\  & Two-hot & \(15+4\) & \(16+5\) & \(18+5\) & \(57+5\) & \(99+10\) \\ \hline Delay (ns) & Binary & \(30.0\) & \(20.8\) & \(31.2\) & \(38.3\) & \(60.6\) \\  & One-hot & \(25.6\) & \(20.4\) & \(29.4\) & \(36.2\) & \(41.3\) \\  & JEDI & \(29.4\) & \(26.0\) & \(27.0\) & \(38.9\) & \(54.3\) \\  & Two-hot & \(31.2\) & \(23.9\) & \(27.2\) & \(36.6\) & \(61.1\) \\ \hline Power (mW/MHz) & Binary & \(1.39\) & \(2.46\) & \(2.51\) & \(4.14\) & \(14.4\) \\  & One-hot & \(1.38\) & \(1.54\) & \(1.66\) & \(4.00\) & \(6.23\) \\  & JEDI & \(1.87\) & \(1.85\) & \(2.10\) & \(3.73\) & \(13.2\) \\  & Two-hot & \(1.46\) & \(2.48\) & \(2.11\) & \(5.21\) & \(11.7\) \\ \hline L + N + M & \(4+2+7\) & \(1+3+15\) & \(6+9+14\) & \(12+6+16\) & \(7+19+48\) \\ \hline \end{tabular}
\end{table} 
Table 1: Results of experiments from [82]. is used. In this case, each state variable corresponds to a column. The method includes R iterations, when each state variable \(T_{r}\in T\) receives either zero or one. The assignment is done in a way that minimizes the switching activity. The algorithm tries to minimize the number of different values of state variables for states with the highest switching probabilities. The algorithm produces a semi-exact solution.