# Area and Performance Estimates of Finite State Machines in Reconfigurable Systems
## 2 Related Works
### Estimates of FSMs
#### 3.2.1 Area Estimates  
When FSMs are implemented in FPGAs, the area is usually measured by the number of LUTs used in the FSM circuit. Let \(n\) be the number of LUT inputs; \(X(d_{r})\) be the set of input variables that are arguments of function \(d_{r}\), \(d_{r}\in D\); \(X(t,j)\) be the \(j\)-th bit of the input vector \(X^{t}\); \(K(s_{i})\) be the code of the state \(s_{i}\); \(K(s_{i},r)\) be the \(r\)-th bit of the code of the state \(s_{i}\); and \(X(p_{t})\) be the set of input variables affecting the \(t\)-th transition. **The \(e\_FPGA\) estimate**. The \(e\_FPGA\) estimate is often used when FSMs are implemented in FPGAs. For this estimate, the area of each transition function \(d_{r}\) is calculated using expression (13):  
\[area(d_{r})= \begin{cases}1,&rank(d_{r})\leq n;\\ \left\lceil\frac{rank(d_{r})-n}{n-1}\right\rceil+1,&rank(d_{r})>n;\end{cases}  \tag{13}\]  
where \(rank(d_{r})\) denotes the rank of the transition function \(d_{r}\), \(d_{r}\in D\). The rank \(rank(d_{r})\) is determined by the number of arguments of function \(d_{r}\) as follows:  
\[rank(d_{r})=\left\lvert X(d_{r})\right\rvert+R, \tag{14}\]  
where \(\left\lvert A\right\rvert\) denotes the cardinality of set \(A\). The \(e\_FPGA\) estimate according to (13) and (14) is calculated using Algorithm 1. ```
INPUT: transition list. OUTPUT: area. \(area=0\); for all\(r=0\)to\(R-1\)do// loop by transition functions of set \(D\)\(X(d_{r})=\mathcal{O}\);// define the set \(X(d_{r})\), \(\mathcal{O}\) is an empty set for all\(t=0\)to\(T-1\)do// loop by FSM transitions if\(K(ns,r)=1\)then// code \(k(ns,r)\) has one in bit \(r\) for all\(j=0\)to\(L-1\)do// loop by input variables if\(X(t,j)=1\)or\(X(t,j)=0\)then// \(x_{j}\) affects the transition \(t\)\(X(d_{r})=X(d_{r})\)U [\(x_{j}\)];// include \(x_{j}\) in the set \(X(d_{r})\) endif endfor endif endfor endfor
``` \begin{table}
\begin{tabular}{c c c c c} \hline \(t\) & \(ps_{t}\) & \(X^{t}\) & \(ns_{t}\) & \(Y^{t}\) \\ \hline
0 & s0 & \(\cdot\cdot\cdot\) & s1 & 001 \\
1 & s1 & \(\cdot\cdot\)0 & s2 & 110 \\
2 & s1 & \(\cdot\)01 & s3 & 101 \\
3 & s1 & 011 & s4 & 100 \\
4 & s1 & 111 & s5 & 010 \\
5 & s2 & 0\(\cdot\cdot\) & s4 & 100 \\
6 & s2 & 1\(\cdot\cdot\) & s5 & 010 \\
7 & s3 & \(\cdot\cdot\cdot\) & s0 & 100 \\
8 & s4 & \(\cdot\cdot\cdot\) & s0 & 000 \\
9 & s5 & \(\cdot\cdot\cdot\) & s0 & 000 \\ \hline \end{tabular}
\end{table} 
Table 1: Transition list of the FSM. The disadvantage of the \(e\_FPGA\) estimate is that it only considers the number of arguments of each transition function \(d_{r}\), and it does not consider the number of FSM transitions. Therefore, the \(e\_FPGA\) estimate can be considered a lower bound on the number of LUTs in the realization of FSM transition functions. **The \(e\_CPLD\) estimate**. For this estimate, the area of each transition function \(d_{r}\) is defined as the number of cubes (minterms) in the SOP of the function \(d_{r}\), \(d_{r}\in D\):  
\[d_{r}=m_{0}^{r}\ +\ldots+m_{Q-1}^{r}; \tag{15}\]  
where \(m_{q}^{r}\) is the q-th minterm of function \(d_{r}\); and \(Q\) is the number of minterms in the SOP of the function \(d_{r}\), \(d_{r}\in D\). In this case, the area of function \(d_{r}\) is defined as follows:  
\[\textit{area}(d_{r})=Q. \tag{16}\]  
The computation of the \(e\_CPLD\) estimate, according to (15) and (16), is described by Algorithm 2. ```
INPUT: transition list. OUTPUT: area. \(\textit{area}=0\); for all\(r=0\)to\(R-1\)do// loop by transition functions of the set \(D\) \(\textit{area}(d_{r})=0\); for all\(t=0\)to\(T-1\)do// loop by FSM transitions if\(K(\textit{area}_{t})=1\)then//\(\textit{area}_{t}\) state code contains 1 \(\textit{area}(d_{r})=\textit{area}(d_{r})+1\); // increase the area of the function \(d_{r}\) endif endfor \(\textit{area}=\textit{area}+\textit{area}(d_{r})\); // increasing the total area endfor Return (area). ```  
**Algorithm 2** Calculation of the \(e\_CPLD\) estimate.