# State Merging and Splitting Strategies for Finite State Machines Implemented in FPGA
## 2 Materials and Methods
### Estimation of Optimization Criteria
#### 2.2.1 Estimation of Power Consumption  
In most cases, the power dissipation in the digital circuits is a combination of the two components: static power--associated with the staying in some state (e.g., high level on the outputs); and the dynamic power--associated with alternating the state of the device. The dynamic power dissipation of the digital system depends on the frequency of switching the output registers. The static power (also called leakage power) is generally the result of the unwanted subthreshold current in the transistor channel when the transistor is turned off. It depends on the supply voltage, the switching threshold voltage, and the transistor size. All these parameters depend on the technological base, which is used for circuit implementation. Using equivalent transformations of the FSM and different state assignment methods at the stage of logic synthesis, we cannot change these parameters. To reduce the static power, the methods such as dynamic voltage and frequency scaling, multi-voltage threshold and power gating should be used additionally. A finite state machine is a tuple \(F=\{A,\,X,\,Y,\,\varphi,\,\psi,\,a_{\textit{reset}}\}\). In this notation, \(A\) is an \(M\)-element set of internal states \(A=\{a_{1},\,\ldots,\,a_{M}\}\), with one selected initial state (\(a_{\textit{reset}}\)). The set \(X\) is an \(L\)-element set of input values \(X=\{x_{1},\,\ldots,\,x_{L}\}\), and the set \(Y\) is an \(N\)-element set of output values \(Y=\{y_{1},\,\ldots,\,y_{N}\}\). There are also two functions describing the behavior of the FSM depending on the input vector: transition function \(\varphi\) and output function \(\psi\). Transition function \(\varphi:A\times X\to A\) defines the next FSM state, depending on the present FSM state and the input vector. Output function \(\psi:A\times X\to Y\) for Mealy FSM, or \(\psi:A\to Y\) for Moore FSM, defines the output vector for a current state and input vector (Mealy) or only for a current state (Moore). Additionally, for real implementations of FSMs in digital systems, the tuple \(F\) also contains a set of codes \(C=\{c_{1},\,\ldots,\,c_{M}\}\) whose cardinality is equal to the cardinality of a set \(A\) because each code \(c_{i}\) relates to the state \(a_{i}\). Each code can be saved as an \(R\)-bit vector, where \(R\in\langle\lceil log_{2}M\rceil\rangle,M\). \(R\) is also the number of memory elements needed to store the code of a present FSM state. Moreover, all codes of states should be orthogonal i.e., there must be no pairs of two identical codes. The method which was described in [35] can be used to compute the dynamic power consumption of an FSM. The method is based on the state assignment and the probability of a \"1\" (or \"0\") appearing on the input. Then, the power dissipation of an FSM can be described by the formula  
\[P_{\textit{total}}=\sum_{r=1}^{R}P_{r}, \tag{1}\]  
where \(P_{\textit{total}}\)--entire dynamic power dissipation of FSM; and \(P_{r}\)--dynamic power dissipation of \(r\)-th flip-flop (a state code memory element). The power consumption of each flip-flop is determined by the expression. \[P_{r}=\frac{1}{2}V_{dt}^{2}\times f\times C\times SA_{r}, \tag{2}\]  
where \(P_{r}\)--power dissipated by memory element \(r\); \(V_{dt}\)--supply voltage; \(f\)--operating frequency; C--output capacitance of each flip-flop; and \(SA_{r}\)--switching activity of \(r\)-th flip-flop, \(r\in<\)1, \(R>\). Let \(c_{i}\) be a binary vector used as a code of state \(a_{i}\). Assuming that the number of bits of code \(c_{i}\) is equal to \(R\), let \(V^{\prime\prime}(c_{i})\) represent the value of \(r\)-th bit of code \(c_{i}\) of state \(a_{i}\), \(r\in<\)1, \(R>\).