# Basic Approaches for Reducing Power Consumption in Finite State Machine Circuits--A Review
## 5 Saving Power by State Assignment
Now, we should find the best state codes using the algorithm shown in Figure 15. The process of state assignment is shown in Figure 16.  
The start point of the state assignment process is shown in Figure 16a. The code 000 is assigned to the initial state \(a_{1}\in A\). All other cells of the Karnaugh map contain the asterisk signs. 1. The first pair of the queue is selected. This the pair \(P1=\langle a_{3},a_{4}\rangle\). To encode the states \(a_{3},a_{4}\in P1\), we should select codes with a minimum number of ones, and \(HD=1\). This means, the actions from block 11 are executed. The codes of \(a_{3},a_{4}\in P1\) are shown in Figure 16b. 2. Now, the pair \(P2=\langle a_{2},a_{4}\rangle\) is selected. Because the transition state \(a_{4}\in P2\) is already encoded, the action from block 7 is executed. The best possible solution is shown in Figure 16c. 3. The pair \(P3=\langle a_{3},a_{2}\rangle\) is selected. Both states from this pair are encoded. Thus, no new codes are assigned during this step. 4. The pair \(P4=\langle a_{1},a_{5}\rangle\) is selected. Now, the code for \(a_{5}\in A\) should be selected. This corresponds to block 8. The final solution is shown in Figure 16d. Figure 16: Process of state assignment for saving power. Figure 15: Block diagram of algorithm [85]. This algorithm belongs to the group of \"greedy\" algorithms. It makes the optimal choice at each step. The algorithm does not change already selected codes. As a result, such a solution is not optimal. It can be improved. Consider what causes the overhead for this algorithm. For example, an STG includes the subgraph shown in Figure 17a. If \(R=3\), then the algorithm [85] will select the codes \(K(a_{3})=001\) and \(K(a_{5})=011\). Because the code \(K(a_{5})\) is now fixed, there is a limited choice of possible codes for \(a_{4}\). To provide HD = 1, the algorithm can assign the code 010 to \(a_{4}\). These codes provide the best solution from the greedy algorithm's point of view. But this approach does not take into account LUT counts for the output logic. As follows from Figure 17a, \(y_{1}=A_{3}x_{1}\lor A_{4}x_{1}=\overline{T_{1}T_{2}}T_{3}x_{1}\lor\overline{T _{1}}T_{2}\overline{T_{3}}x_{1}\). If an FSM circuit is implemented with LUTs having three inputs, then two LUTs are necessary to implement the circuit for \(y_{1}\) (Figure 17b). This circuit has two levels of LUTs and six interconnections. If a JEDI-based style of state assignment is used, then the states \(a_{3}\) and \(a_{4}\) will have adjacent codes. If, for example, there is \(K(a_{3})=001\) and \(K(a_{4})=101\), then it gives the Boolean equation \(y_{1}=\overline{T_{2}}T_{3}x_{1}\). The corresponding circuit has only a single LUT, a single level of logic, and four interconnections (Figure 17c). Thus, for the discussed case, the JEDI-based circuit is faster and requires fewer LUTs. This is quite possible that the circuit from Figure 17c has better power characteristics than its equivalent shown in Figure 17b. The following conclusion can be made from this example. To find a desirable trade-off among power consumption, area, and performance, it is necessary to take into account the output logic too. There are special resynthesis methods [116] that can improve the overall quality of an FSM circuit. They are out the scope of this survey. Let us only point out that the resynthesis allows a reduction in the number of logic levels and simplifies the interconnection system. These two issues are very important in the LUT-based design [116]. As mentioned in [117], many systems of emerging computing and communications equipment are control-dominated. The controllers are mostly implemented as FSMs. Because many devices are mobile, then a RPC is a very important issue. In the case of controllers, it is very important to decrease the power consumption, because \"controllers are always active. As a result, a good amount of system power is consumed by the controllers\" [117]. This explains the necessity of RPC for FSMs.