# Basic Approaches for Reducing Power Consumption in Finite State Machine Circuits--A Review
## 5 Saving Power by State Assignment
The RPC can be achieved by adding states [95] or adding bits to state codes [108]. These additional states and bits can also be viewed as the power overhead. We start from the state splitting approach [95]. The approach takes its roots in 1963 [118]. This approach was used for optimizing FSMs [119] and minimizing the number of FSM states [120]. Also, it can improve the power consumption. Consider a part of an STG (Figure 18a) taken from [95]. The state codes are shown near the graph nodes. Figure 17: Explanation of power overhead for algorithm [85]. To reduce the switching activity, \(\alpha\), it is necessary to diminish the value of the Hamming distance. In the best case, HD = 1 for all pairs \(\langle a_{m},a_{s}\rangle\) existing in a particular STG. Obviously, each state code can have only R adjacent state codes with HD = 1. The state \(a_{3}\) (Figure 18a) is connected with R + 1 = 4 states. HD = 1 for the pairs \(\langle a_{1},a_{3}\rangle\), \(\langle a_{3},a_{4}\rangle\), and \(\langle a_{3},a_{5}\rangle\). But HD = 2 for the pair \(\langle a_{2},a_{3}\rangle\). It is possible to \"split\" the state \(a_{3}\) into two equivalent states \(a_{3}^{\mathrm{a}}\) and \(a_{3}^{\mathrm{a}}\). These states have the same transitions. Now, each of the new states (\(a_{3}^{\mathrm{a}}\) and \(a_{3}^{\mathrm{a}}\)) has exactly R adjacent states. If the state codes are the ones shown in Figure 18b, then HD = 1 for all existing adjacent state pairs (\(\langle a_{1},a_{3}^{\mathrm{a}}\rangle\), \(\langle a_{3}^{\mathrm{a}},a_{4}\rangle\), \(\langle a_{3}^{\mathrm{a}},a_{5}\rangle\), \(\langle a_{1},a_{3}^{\mathrm{a}}\rangle\),\(\langle a_{3}^{\mathrm{a}},a_{4}\rangle\), and \(\langle a_{3}^{\mathrm{a}},a_{5}\rangle\). Each state \(a_{m}\in A\) can be characterized by two sets. The set \(FI(a_{m})\) includes states \(a_{s}\in A\), such that there are transitions \(\langle a_{s},a_{m}\rangle\). The set \(FO(a_{m})\) includes states \(a_{s}\in A\), such that there are transitions \(\langle a_{m},a_{s}\rangle\). As follows from Figure 18a, the following sets can be formed: \(FI(a_{3})=\{a_{1},a_{2}\}\) and \(FO(a_{3})=\{a_{4},a_{5}\}\). The splitting state \(a_{3}\) makes sense because the following relations hold: \(|FI(a_{3})|=2\rangle 1\) and \(|FI(a_{3})|+|FO(a_{3})|=4>R=3\). This means that the splitting can be executed if  
\[(|FI(a_{m})|>1)\wedge(|FI(a_{m})|+|FO(a_{m})|>R)=1. \tag{15}\]  
For states of transitions, state codes \(K(a_{s})\) depend on the codes of previous states. As a result, there are a lot of splitting options. It is necessary to choose the option leading to the maximum RPC. In [95], two algorithms are proposed for the state splitting. In the first case, all possible splittings are investigated for states satisfying (15). This approach requires the extensive search of an optimal solution. In the second case, only two subsets are formed for \(FI(a_{m})\). One subset includes a state \(a_{s}\) having the maximum probability of transition into the state \(a_{m}\) to be split. The second subset includes states \(a_{i}\in FI(a_{m})/\{a_{s}\}\). This solution is a suboptimal one. In [95], experimental results are provided. They were obtained using the library [82] and the software package ZUBR [121]. The results show that a RPC takes place for 27 benchmarks (57.4% of all benchmarks). The results [95] show that the proposed approach reduces the power consumption by an average of 6.92%. At the same time, the maximum RPC is equal to 81.02% (for the benchmark _tma_). The simplified algorithm produces solutions very close to optimal. The average difference is around 0.08%. Consider Figure 18a. \(FI(a_{3})=\{a_{1},a_{2}\}\) and \(FO(a_{3})=\{a_{4},a_{5}\}\); \(R=3\). As follows from (15), it is impossible to assign adjacent codes to all states included into the set \(FI(a_{3})\cup FO(a_{3})\). If the number of state variables is greater than what is defined by (4), then the condition (15) is violated.