# Area and Performance Estimates of Finite State Machines in Reconfigurable Systems
## 2 Related Works
### Estimates of FSMs
#### 3.2.3 Other Estimates for FSMs  
In addition to estimates directly aimed at determining the area or performance of the FSM being designed, other estimates can be proposed that are not directly aimed at computing the area or performance of the FSM. **The _diff_w_ estimate**. The _diff_w_ estimate is based on the following assumption: if all transition functions \(d_{r}\), \(d_{r}\in D\), have approximately the same complexity, which is determined by the weight \(w(d_{r})\), then the depth and possibly the area of the FSM will be minimized. Let the weight of function \(d_{r}\), \(d_{r}\in D\), be defined as the number of cubes [9] in the SOP of the function \(d_{r}\), i.e., using expression (24):  
\[w(d_{r})=\sum_{i=0}^{M-1}C(s_{i})\cdot K(s_{i},r), \tag{24}\]  
where \(C(s_{i})\) is the number of transitions ending in state \(s_{i}\), \(s_{i}\in S\). The value of the _diff_w_ estimate is determined by expression (25):  
\[diff\_w=\max_{d_{r}\in D}(w(d_{r}))-\min_{d_{r}\in D}(w(d_{r})```
for all\(r=0\)to\(R-1\)do// determine weights of functions \(d_{r}\) \(w(d_{r})=0\); for all\(i=0\)to\(M-1\)do// loop on the FSM states if\(K(\text{s}_{i},r)=1\)then// state code \(s_{i}\) has 1 in bit \(r\) \(w(d_{r})=w(d_{r})+C(s_{i})\); endif endfor endfor max\(\_\)w = \(-1\); min\(\_\)w = 10,000; // find the maximum and minimum values of weight for all\(r=0\)to\(R-1\)do// loop by weights of functions \(dr\) if\(w(d_{r})>\max\_\)w then\(\max\_\)w = \(w(d_{r})\) endif if\(w(d_{r})<\min\_\)w then\(\min\_\)w = \(w(d_{r})\) endif endfor Return(max\_\)w - min\(\_\)w);
```

**Algorithm 7**_Cont_.

**The _max_\(\_\)w_ estimate**. The _max_\(\_\)w_ estimate is based on the assumption that in order to increase the speed of FSMs, it is reasonable to minimize the length of the critical path, which is defined by the weight \(w(d_{r})\), \(d_{r}\in D\).

In the _max_\(\_\)w_ estimate, the result is the maximum weight value of all transition functions \(d_{r}\), \(d_{r}\in D\). Therefore, the value of _max_\(\_\)w_ estimate is determined by expression (26):

\[max\_\)w = \(\max_{d_{r}\in D}(w(d_{r})). \tag{26}\]

The computation of the _max_\(\_\)w_ estimate, according to (24) and (26), is described by Algorithm 8. ```
INPUT: transition list. OUTPUT: max(\(w(d_{r})\)). Determine the set of values \(C(s_{i})\), \(s_{i}\in S\), as in Algorithm 7; Determine the weights \(w(d_{r})\) of functions \(d_{r}\), \(d_{r}\in D\), as in Algorithm 7; max\(\_\)w = \(-1\); // find the maximum value of weight for all\(r=0\)to\(R-1\)do// loop by weights of functions \(d_{r}\) if\(w(dr)>\max\_\)w then \(\max\_\)w = \(w(dr)\); endif endfor Returnmax\(\_\)w.
```

**Algorithm 8** Calculation of the _max_\The _e_FPGA_, _e_CPLD_, _classic_, _diff_w_, and _max_w_ estimates were used in [8] to determine the implementation cost of the FSM; the _seq_dec_ and _par_dec_ estimates were used in [4] to determine the performance of the FSM; and the _terms_ and _avg_dec_ estimates are new. ### Example of Calculating FSM Evaluations

For example, consider the FSM whose transition list is presented in Table 1. Our FSM has 6 states s0,...,s5. Let the FSM states be encoded by a sequential binary code: s0--000, s1--001, s2--010, s3--011, s4--100, and s5--101. For convenience in demonstrating the computation of the considered estimates, the columns \(K(ps_{t})\) and \(K(ns_{t})\) with the codes of the initial and final states of the transitions have been added in Table 1.



For our simple example, the ranks of the transition functions differ only slightly. Therefore, the value of the estimates as well as the value of the critical path length match. Nevertheless, for large and complex FSMs, the _seq_dec_, _par_dec_, and _avg_dec_ estimates can be useful in the FSM state encoding. In computing the _diff_w_ and _max_w_ estimates, we have the following values for the weights of the transition functions: \(w(d_{0})=4\), \(w(d_{1})=2\), and \(w(d_{2})=5\). Therefore, _diff_w_ = 3 and _max_w_ = 5. The _diff_w_ and _max_w_ estimates are not computed for each transition function.