# Area and Performance Estimates of Finite State Machines in Reconfigurable Systems
## 2 Related Works
### Estimates of FSMs
#### 3.2.1 Area Estimates
The \(e\_CPLD\) estimate has the following disadvantages: the number of arguments of function \(d_{r}\) is not considered; the complexity of each minterm is not considered; and the LUT parameters are not considered. However, despite these disadvantages, the \(e\_CPLD\) estimate has shown high efficiency in the implementation of FSMs in CPLDs [19], so it is called \(e\_CPLD\). **The _classic_ estimate**. Most of the \(e\_CPLD\) estimate disadvantages were absent in the _classic_ estimate. The _classic_ estimate corresponds to the number of gate inputs when function \(f\) is realized on elements of small and medium degrees of integration. The SOP of each transition function \(d_{r}\), \(d_{r}\in D\), can be represented as follows:  
\[d_{r}=\sum_{t=0}^{T-1}X^{t}\cdot E^{t}\cdot flag(r,t), \tag{17}\]  
where \(X^{t}\) is the conjunction of input variables initiating the \(t\)-th transition; \(E^{t}\) is the conjunction of feedback variables defining the state code \(p_{\textit{st}}\); and \(flag(r,t)=1\) if the mintermis included in the SOP of the function \(d_{r}\), otherwise \(flag(r,t)=0\). It follows from (17) that the number of literals in each minterm is equal to  
\[\left|X^{t}\right|+R. \tag{18}\]  
The computation of the _classic_ estimate, based on (17) and (18), is described by Algorithm 3. ```
INPUT: transition list. OUTPUT: area. \(area=0\); for all\(r=0\)to\(R\)\(-1\)do// loop on transition functions of the set \(D\) \(area(d_{r})=0\); // determine the estimate of the function \(d_{r}\) for all\(t=0\)to\(T-1\)do// loop by transitions of a finite automaton if\(K(uts_{i,r})=1\)then// state code \(uts_{t}\) contains \(1\) \(area(d_{r})=area(d_{r})+1\); // count the number of minterms \(X(p_{t})=\mathcal{O}\); // define the set \(X(p_{t})\) for all\(j=0\)to\(L-1\)do if\(X(t_{j})=1\)or\(X(t_{j})=0\)then// \(x_{j}\) affects the transition \(t\) \(X(p_{t})=X(p_{t})\) U \(\left\{x_{j}\right\}\); // \(x_{j}\) is included in \(X(p_{t})\) endif endfor \(area(d_{r})=area(d_{r})+1\)\(X(p_{t})\)\(\mid\)\(+R\); // increase \(area(d_{r})\) endif \(area=area+area(d_{r})\); // increase the total area endfor Return area. ```  
**Algorithm 3**Calculation of the _classic_ estimate. Note that the _classic_ estimate does not consider the LUT parameters. **The _terms_ estimate**. The _terms_ estimate assumes that each minterm of transition functions is implemented in the FPGA as a separate Boolean function. The _terms_ estimate assumes, in advance, the use of a redundant number of LUTs, but it takes into account more properties of the transition functions. In the _terms_ estimate, the area is computed as the sum of the areas of all the minterms of each transition function \(d_{r},d_{r}\in D\):  
\[area(d_{r})=\sum_{q=0}^{Q-1}area(m_{q}^{r}), \tag{19}\]  
where \(area(m_{q}^{r})\) is the area of the minterm \(m_{q}^{r}\) of the function \(d_{r},d_{r}\in D\). The value of area \(area(m_{q}^{r})\) of minterm \(m_{q}^{r}\) is determined by expression (13), only instead of the rank \(rank(d_{r})\) of function \(d_{r}\) the rank \(rank(m_{q}^{r})\) of minterm \(m_{q}^{r}\) is used, which is calculated by expression (20):  
\[rank(m_{q}^{r})=\left|X(m_{q}^{r})\right|+R, \tag{20}\]  
where \(X(m_{q}^{r})\) is the set of input variables that are arguments of the minterm \(m_{q}^{r}\). The computation of the _terms_ estimate, according to (13), (19), and (20), is described by Algorithm 4. ```
INPUT: transition list. OUTPUT: area. \(area=0\); for all\(r=0\)to\(R\)\(-1\)do// loop on transition functions of the set \(D\) \(area(d_{r})=0\); // determine the estimate of the function \(d_{r}\)
```  
**Algorithm 4**Calculation of the _terms_ estimate. A special feature of the _terms_ estimate is that it considers the area of each minterm of each transition function. Despite the redundancy of the _terms_ estimate, in an FSM encoding and synthesis methods, this redundancy is an advantage over other estimates because it takes into account more properties of the transition functions.