# Basic Approaches for Reducing Power Consumption in Finite State Machine Circuits--A Review
## 5 Saving Power by State Assignment
To minimize the chip area, some additional constraints are used. Additional metrics are used, similar to the ones proposed in [90]. One of them is a fan-out-oriented metric. It can be used for FSMs with a small number of inputs and a large number of outputs. The second metric is a fan-in-oriented metric. It can be used for FSMs with a large number of inputs and a small number of outputs. These area constraints are added as weights for an STG. To reach some trade-off for area-power, the parameter \(\alpha\leq 1\) is introduced in [85]. It shows what is more important for a given task. The weight \(\omega_{m,s}\) of an edge connecting states \(a_{m}\) and \(a_{s}\) is determined by  
\[\omega_{m,s}=(1-\alpha)\omega_{m,s}^{area}+\alpha\omega_{m,s}^{power}. \tag{14}\]  
The weights for area (\(\omega_{m,s}^{area}\)) are determined using the MUSTANG approach [90]. The weights for power (\(\omega_{m,s}^{power}\)) are determined by the heuristic algorithm from [85]. The results of experiments with the benchmarks from [82] show that the saving power increases with the growth in FSM complexity. If \(R=4\), then the maximum saving is up to 8%; if \(R=5\), the maximum saving is up to 16%; if \(R=6\), then the maximum saving is up to 25%. Thus, adding one to R improves the power consumption by approximately 8%. Also, the growth in the number of state variables, R, leads to reducing the area overhead. It means that applying similar approaches makes sense for rather complex FSMs. Using [85] allows the creation of the block diagram shown in Figure 15. In this algorithm, we assume that pairs \(P1,..,PI\) are created for FSM states. These pairs include states \(a_{m},a_{s}\in A\) such that there is at least a single transition between these states (either \(\langle a_{m},a_{s}\rangle\) or \(\langle a_{s},a_{m}\rangle\)). Each pair has a weight \(W(Pi)\). The block diagram is shown in Figure 15.  
In the beginning, it is necessary to organize a queue \(\gamma\) of pairs \(P1,...,P1\). The pairs are placed in the queue in the descending order of weights \(W(Pi)\). The algorithm has no more than \(I\) steps. Every step is connected with the following operations. The \(i\)th pair is selected from the queue \(\gamma\) (block 3). The pair includes some states \(a_{m}\) and \(a_{s}\). If state \(a_{m}\) has no code (the output \"No\" from block 4), then we check whether state \(a_{s}\) has a code (block 5). If there is a preliminary selected code \(K(a_{s})\) (the output \"Yes\" from block 5), then we should select the best possible code for state \(a_{m}\) (block 7). The best possible code is selected from still \"free\" state assignments. The best code should have a minimum possible Hamming distance (HD) with the code \(K(a_{s})\). Next, the value of \(i\) is increased by one (block 9). If the queue is not empty, then the selection process is repeated (the transition to block 3). Otherwise, the process is terminated. If there is still no code for state \(a_{s}\) (the output \"No\" from block 5), then the selection of the best codes for both states is executed. If \(K(a_{m})\) already exists (the output \"Yes\" from block 4), then we check for code \(K(a_{s})\) (block 6). If there is no code \(K(a_{s})\) (the output \"No\" from block 6), then a possible best code \(K(a_{s})\) is selected (block 8). Otherwise, no codes should be selected, and the process is repeated (go to block 9). Consider the following example. Consider the set \(A=\{a_{1},\ldots,a_{5}\}\) for some FSM \(S_{1}\). These states form the following I = 9 pairs: \(P1=\langle a_{3},a_{4}\rangle\), \(P2=\langle a_{2},a_{4}\rangle\), \(P3=\langle a_{3},a_{2}\rangle\), \(P4=\langle a_{1},a_{5}\rangle\), \(P5=\langle a_{1},a_{2}\rangle\), \(P6=\langle a_{4},a_{1}\rangle\), \(P7=\langle a_{2},a_{5}\rangle\), \(P8=\langle a_{3},a_{3}\rangle\), and \(P9=\langle a_{5},a_{4}\rangle\). R = 3 and \(K(a_{1})=000\).