Area and Performance Estimates of Finite State Machines in Reconfigurable Systems

Modern reconfigurable systems are typically implemented in field-programmable gate arrays (FPGAs) based on look-up tables (LUTs). Finite state machines (FSMs) perform the functions of control devices and are integral to reconfigurable systems. When designing reconfigurable systems, the problem of optimizing the area and performance of FSMs often arises. The FSM synthesis and state encoding methods generally use only one estimate of the FSM area or performance. However, regardless of the computational complexity of the FSM synthesis or state encoding method, if the estimate incorrectly reflects the optimization aim, the result is far from the optimal solution. This paper proposes several estimates of the area and performance of FSMs implemented in LUT-based FPGAs. The effectiveness of the proposed estimates was investigated using the sequential method for FSM state encoding. Experimental studies on benchmarks showed that the FSM area decreases on average from 3.8% to 6.5%, compared to known approaches (for some cases by 33.3%), while the performance increases on average from 3.5% to 7.3% (for some cases by 27.6%). Recommendations for the practical use of the proposed estimates are also provided. The Conclusions section highlights promising directions for future research.