# Area and Performance Estimates of Finite State Machines in Reconfigurable Systems
## 2 Related Works
### Estimates of FSMs
#### 3.2.2 Performance Estimates  
The performance of an FSM is determined by the maximum operation frequency of the FSM circuit. At the logic synthesis level, performance is often associated with the critical path length (_cpl_). When FSMs are implemented in LUT-based FPGAs, the path length is determined by the number of LUTs through which signals pass from the input to the output of the circuit.  
There are two main ways of decomposing complex Boolean functions: sequential (Figure 2a) and parallel (Figure 2b).  
The number _pls_ of LUT levels in the case of the sequential decomposition of the Boolean function \(f\) is determined by expression (21):  
\[\mathit{pls}(f)=\begin{cases}1,&\mathit{rank}(f)\leq n;\\ \left\lceil\frac{\mathit{rank}(f)-n}{n-1}\right\rceil+1,&\mathit{rank}(f)>n; \end{cases} \tag{21}\]  
where _rank(f)_ is the number of arguments of function \(f\).  
The number _plp_ of LUT levels in the case of parallel decomposition of the Boolean function \(f\) is determined by expression (22):  
\[\mathit{plp}(f)=\left\lceil\log_{n}\left(\mathit{rank}(f)\right)\right\rceil =\left\lceil\frac{\log_{n}\mathit{rank}(f)}{\log_{n}n}\right\rceil. \tag{22}\]  
**The _seq_dec_ estimate**. The _seq_dec_ estimate determines the critical path length of FSM transition functions for the case of the sequential decomposition of Boolean functions when the signal path length is computed using expression (21). Let \(\mathit{pls}(d_{r})\) be the signal path length of a transition function \(d_{r}\), \(d_{r}\in D\). The computation of the critical path length _cpl_ of the _seq_dec_ estimate is described by Algorithm 5.  
```
INPUT: transition list.  OUTPUT: \(cpl\). \(cpl=0\); for all\(r=0\)to\(R-1\)do// loop by function \(d_{r}\);  Determine the set \(X(d_{r})\) as in Algorithm 1; \(rank(d_{r})=|X(d_{r})|+R_{i}\)// determine the rank of the function \(d_{r}\) if\(\text{rank}(d_{r})<=n\)then// calculate the path length \(pls(d_{r})\) of the function \(d_{r}\) \(pls(d_{r})=1\); else \(pls(d_{r})=\lceil(rang(d_{r})-n)/(n-1)\rceil\); endif if\(pls(d_{r})>cpl\)then// determine the length of the critical path \(cpl=pls(d_{r})\); endif endfor Return\(cpl\).
```  
**Algorithm 5** Calculation of the _seq_dec_ estimate.  
**The _par_dec_ estimate**. The _par_dec_ estimate determines the critical path length of the FSM functions for the case of parallel decomposition of Boolean functions when the signal path length is computed using expression (22). Let \(plp(d_{r})\) be the signal path length of a  
Figure 2: Generalized decomposition structures: (**a**) sequential; (**b**) parallel.  
transition function \(d_{r}\). The computation of the critical path length \(cpl\) of the _par_dec_ estimate is described by Algorithm 6.  
```
INPUT: transition list. OUTPUT: \(cpl\). \(cpl=0\); for all\(r=0\) to \(R-1\)do// loop by function \(d_{r}\)  Determine the set \(X(d_{r})\) as in Algorithm 1; \(rank(d_{r})=|X(d_{r})|+R\); // determine the rank of the function \(d_{r}\) \(plpl(d_{r})=\lfloor\log(range(d_{r}))/\log n\rceil\); // calculate the path length \(plp(d_{r})\) for \(d_{r}\) if (\(plp(d_{r})>cpl\))then// determine the length of the critical path \(cpl=plp(d_{r})\); endif endfor Return\(cpl\).
```  
**Algorithm 6** Calculation of the _par_dec_ estimate.  
The disadvantage of the _seq_dec_ and _par_dec_ estimates is that they do not take into account the number of transitions \(T\) and the number of states \(M\) of the FSMs.  
**The _avg_dec_ estimate**. The _avg_dec_ estimate is calculated as the arithmetic mean of the _seq_dec_ and _par_dec_ estimations according to Equation (23):  
\[avg\_dec=\lceil(seq\_dec+par\_dec)/2\rceil. \tag{23}\]