# Basic Approaches for Reducing Power Consumption in Finite State Machine Circuits--A Review
## 5 Saving Power by State Assignment
In this case, there is an optimum solution shown in \[\omega_{m,s}=(1-\alpha)\omega_{m,s}^{area}+\alpha\omega_{m,s}^{power}. \tag{14}\]0  
\[\omega_{m,s}=(1-\alpha)\omega_{m,s}^{area}+\alpha\omega_{m,s}^{power}. \tag{14}\]1 Initial STG (a) and its transformation (b). The analysis of Figure 19 shows that the following relation holds: \(HD(a_{1},a_{3})=HD(a_{2},a_{3})=HD(a_{4},a_{3})=HD(a_{5},a_{3})=1\). The codes (Figure 19) provide the minimum power consumption for this part of the STG. But they add a power overhead since \(R=4\) instead of \(R=3\). It means that there is an additional flip-flop and additional loading for the clock tree. A method [108] based on this idea was tested using the benchmarks from [82]. The outcomes of this approach were compared with results obtained for NOVA, JEDI, and a column algorithm [85]. The experiments were conducted for the following conditions: \(V_{dd}=5\) V, \(f=5\) MHz, \(C_{par}=3\) pF. The approach from [108] allowed a reduction in the power consumption by a factor of 1.7 (NOVA), 1.36 (JEDI), and 1.12 (column algorithm). For example, in the case of benchmark \(tbl\), adding one to the minimum value of R diminished the power consumption by 34%. Of course, it is necessary to take into account the influence of increasing the number of state variables on both area and time characteristics of a resulting FSM circuit. All discussed methods of state assignment have the same specificity: a state code \(K(a_{m})\) is assigned to the state \(a_{m}\in A\) as an R-bit string during some step of the state assignment process. In [122], a method is proposed where each state assignment step gives only a single bit of state codes. The method [122] reduces the switching activity, \(\alpha\). But at the same time, it diminishes a chip area occupied by an FSM circuit. The decomposition strategy of the state assignment is proposed in [122]. The approach produces a binary tree whose leaves correspond to state codes. As presented in [122], we explain this approach using the benchmark \(dk27\)[82]. The benchmark's STG is shown in \[\omega_{m,s}=(1-\alpha)\omega_{m,s}^{area}+\alpha\omega_{m,s}^{power}. \tag{14}\]2  
The state assignment [122] starts by calculating the probabilities \(p_{m,s}\) of interstate transitions. To get the total probabilities of transitions \(P_{m,s}\), the product of probabilities \(P_{m}\) and \(p_{m,s}\) is calculated. The value of \(P_{m}\) determines a probability that the FSM is in the state \(a_{m}\in A\). For \(dk27\), the following values of \(P_{m}\) are used: \(P_{1}=P_{2}=0.19\), \(P_{3}=0.095\), \(P_{4}=0.095\), \(P_{5}=0.167\), \(P_{6}=0.214\), \(P_{7}=0.048\). \[\omega_{m,s}=(1-\alpha)\omega_{m,s}^{area}+\alpha\omega_{m,s}^{power}. \tag{14}\]3 Optimal codes for the STG from Figure 18a. \[\omega_{m,s}=(1-\alpha)\omega_{m,s}^{area}+\alpha\omega_{m,s}^{power}. \tag{14}\]4 State transition graph of benchmark dk27 [122]. The summation of the direct edges' probabilities for each pair of states produces an undirected graph with edge weights (Figure 21). Now, it is necessary to minimize the Hamming distance between the codes \(K(a_{m})\) and \(K(a_{s})\) with the high transition probability. Using the algorithm [122] gives the binary tree for dk27 (Figure 22). The values zero and one correspond to state code bits. To find the code, we should move from the leaves to the tree root. The resulting state codes are shown in the Karnaugh map (Figure 22b). R = 3 (this is the number of tree levels). For example, the following codes can be found: \(K(a_{1})=000\), \(K(a_{2})=001\), and so on. To optimize the power consumption, it is necessary to take into account dependencies between states at some level of the tree. The optimization can be performed by swapping the nodes on the same tree level. It results in changing values of bit codes. For example, swapping state codes \(a_{5}\) and \(a_{2}\) (Figure 22a) produces state codes \(K(a_{5})=001\) and \(K(a_{2})=101\). As shown in [122], the state assignment (Figure 22b) gives a sum of all Hamming distances equal to 16.