# Area and Performance Estimates of Finite State Machines in Reconfigurable Systems
## 1 Introduction  
Currently, various reconfigurable systems are widely used in all spheres of human activity [1]. A distinctive feature of modern reconfigurable systems is the intensive use of field-programmable gate array (FPGA) based on a look-up table (LUT) [2]. When developing reconfigurable systems, there is often a need to improve the design parameters, such as the area (implementation cost), performance (speed), and power consumption. Because finite state machines (FSMs) are an integral part of most reconfigurable systems (FSMs act as controllers of digital devices and systems), it is important to reduce the number of LUTs [3], increase the performance [4], and reduce the power consumption [5] of FSMs. To solve these problems, it is vital to estimate the area, performance, and power consumption of FSMs with the highest accuracy. The power consumption estimates of the FSMs implemented in FPGAs are given in [6, 7]. However, it is much more difficult to estimate the area and performance of FSMs implemented in reconfigurable systems. The methods of minimization and decomposition of Boolean functions used by design tools are usually unknown to developers. In addition, design tools typically use various logical and physical synthesis techniques, for example, to satisfy timing constraints. Therefore, even exact estimates of the expected area and performance usually differ from the area and performance of the implemented FSM circuit. When implementing FSMs in an LUT-based FPGA, an area is measured by the number of LUTs in the FSM circuit. Performance is determined by the delay of signals in the critical (longest) signal path from input to output of the circuit, which is measured by the number of levels (depth) of LUTs in the FSM circuit. Both of these parameters (area and depth) are usually minimized in FSM synthesis methods for reconfigurable systems. This paper considers several estimates of the area and performance of FSMs, as well as other estimates that are not directly related to the computation of the area or performance of an FSM. The proposed estimates were investigated using the sequential method for FSM state encoding [8]. Note that the results of FSM synthesis or state encoding depend significantly on the estimates used (area, speed, or power consumption). Because (regardless of the computational complexity of the method) if the estimate does not correctly reflect the optimization aim, the synthesis results will not be optimal. Therefore, it is very important in FSM synthesis methods to use efficient estimates that contribute optimization and more exactly reflect the synthesis results. The main goal of this paper is to reduce the area and increase the performance of FSMs for reconfigurable systems by using the most efficient or exact estimates in synthesis methods or state encoding of FSMs. The main contribution of this paper is a new approach to synthesizing and state encoding FSMs for reconfigurable systems, when several different estimates, rather than one, are applied in determining the area and performance of the FSM. To this end:  
* Several area and performance estimates of FSMs, as well as estimates that are not directly related to the computation of the area or performance estimates of FSMs, are presented;
* For each estimate, and the expressions and algorithm for its computation are given;
* The efficiency of the estimates is verified on benchmarks of FSMs using the estimates in the sequential method of FSM state encoding [8];
* A comparison of different estimates was performed to determine their efficiency for optimizing the area and performance of FSMs;
* It has been shown that the use of the considered estimates in the method [8] allows to obtain solutions on average better in comparison with known methods;
* Recommendations on the practical use of the proposed estimates are given. The rest of the paper is organized as follows. Section 2 includes a short analysis of related works. Section 3 discusses essential information about the FSM representations and presented FSM estimations.