# Basic Approaches for Reducing Power Consumption in Finite State Machine Circuits--A Review
## 4 Saving Power by Clock-Gating and FSM Decomposition
Based on a similar analysis, the model of a gated-clock FSM was proposed [76]. In [76], the waiting state is named a self-loop. If an FSM enters a self-loop, then a special logic makes the pulse Clock off. Therefore, in that case, the CL controls the state register RG (Figure 9). A comparison of Figures 8 and 9 shows that these approaches are very similar. They have the same positive and negative features. These methods can be used simultaneously. Mostly, these two methods are used together with FSM decomposition [77]. The first work devoted to FSM decomposition appeared in 1960 [78]. There are three known basic approaches of decomposition: parallel, cascade, and general [79]. These approaches are shown in Figure 10.  
Figure 8: Organization of clock gating. Figure 9: Organization of a clock-gating FSM [76]. Both methods of parallel (Figure 10a) and cascade (Figure 10b) decomposition have rather theoretical value [3]. But the general decomposition (Figure 10c) can be used for any FSM. This approach was used for implementing PLA-based FSMs [80; 81]. Let us discuss the FSM architecture based on the general decomposition. The FSM circuit includes three combinational blocks and two registers keeping the state codes of different FSMs (Figure 11). The set \(A\) is decomposed by two disjoint sets, \(A^{1}\) and \(A^{2}\). The states \(a_{m}\in A^{1}\) are encoded using \(R1\) state variables, which form a set \(T1\). The value of \(R1\) is determined by \(R1=\lceil log_{2}|A^{1}|\rceil\). The states \(a_{m}\in A^{2}\) are encoded using \(R2\) state variables, which form a set \(T2\). The value of \(R2\) is determined by \(R2=\lceil log_{2}|A^{2}|\rceil\). There are \(R1\) elements in the set of IMFs \(\Phi_{1}\); there are \(R2\) elements in the set of IMFs \(\Phi_{2}\). Both registers have the same pulses _Start_ and _Clock_. The set of FSM inputs is represented as \(X=X1\bigcup X2\). It is quite possible to have identical elements in these sets. As follows from Figure 11, the following SBFs should be implemented:  
\[ \begin{array}{rcl}\Phi_{1}&=&\Phi_{1}(T1,\,T2,\,X1);\\ \Phi_{2}&=&\Phi_{2}(T1,\,T2,\,X2);\\ Y_{1}&=&Y1(T1,\,T2,\,X1);\\ Y_{2}&=&Y2(T1,\,T2,\,X2);\\ Y&=&Y(Y1,\,Y2).\end{array}  \tag{12}\]  
For FSMs based on (12), the following design method is proposed in [3]:  
1. Select disjoint subsets \(A^{1}\) and \(A^{2}\). 2. Generate STGs for each sub-FSM. Add additional RESET states into each STG. 3. Copy all transitions from the initial STG in unmodified form into new STGs. 4. Replace the transitions \(\langle a_{m},\,\,a_{s}\rangle\) where \(a_{m}\in A^{1}\) and \(a_{s}\in A^{2}\) by the two following transitions: \(\langle a_{m},\,\,RESET2\rangle\) and \(\langle RESET2,\,\,a_{s}\rangle\). Figure 11: Structural diagram of an FSM based on general decomposition. Figure 10: Three approaches for FSM decomposition [79]. Replacing the transitions \(\langle a_{m},\ a_{s}\rangle\) where \(a_{m}\in A^{2}\) and \(a_{s}\in A^{1}\) by the two following transitions: \(\langle a_{m},\ RESET1\rangle\) and \(\langle RESET1,\ a_{s}\rangle\). In [3], this approach is combined with clock gating for both inputs and state registers. This combines approaches from [76; 77] with some new approach. The initial FSM is divided into two FSMs: FSM1 and FSM2. FSM1 is small; it includes states \(a_{m}\in A^{1}\) with very high probabilities of transitions \(\langle a_{m},\ a_{s}\rangle\) where \(a_{s}\in A^{1}\). This FSM corresponds to the famous 20% of operators determined by [75]. All other initial FSM states belong to the set \(A^{2}\). FSM1 is mostly active, and FSM2 is mostly idle. As a result, it is possible to disable the flip-flops of RG2 and RGX for FSM2. If FSM1 is idle, its state register RG1 can be disabled too.