# Area and Performance Estimates of Finite State Machines in Reconfigurable Systems
## 2 Related Works  
The most common area and delay estimation is performed when mapping Boolean functions (design logic) into an FPGA structure [9; 10; 11]. The classical study [9] presents algorithms for multilevel synthesis and minimization of combinational logic in the case of its implementation on gates. In [9], the area (complexity) of a Boolean function was determined by the number of literals required to represent the function in factorized form. Here, a literal is a Boolean variable or its inverse. The delay in [9] is determined by the time taken for the signal to pass along the critical path. In [10], the area estimate \(a(f)\) and delay \(d(f)\) of a Boolean function \(f\) are defined by the same expression (1):  
\[a(f)=d(f)=\left\{\begin{aligned} & 1,& L\leq n;\\ & L-n+1,& L>n;\end{aligned}\right. \tag{1}\]  
where \(L\) is the number of arguments of the function \(f\); and \(n\) is the number of LUT inputs. In [11], the delay estimate is also calculated according to (1).  
Area and delay estimates are widely used in decomposition methods of Boolean functions [12; 13]. In [12], the area and delay estimates are defined by the same expression (1). In [13], the area is described by expression (2):  
\[a(f)=\lceil\log_{2}\mu\rceil+1, \tag{2}\]  
where \(\mu\) is the number of unique variables in the decomposition of the function \(f\); and \(\lceil A\rceil\) is the smallest integer greater than or equal to \(A\).  
Area and delay estimates are often used in synthesis methods of combinational and sequential circuits. For example, in the method [14] of symbolic RTL (register transfer level) synthesis in LUT-based FPGAs, a multilevel logic network of LUTs is constructed, the area of which is determined by expression (3):  
\[a(F)=\left\lceil\frac{L}{n}\right\rceil\cdot\left\lceil\frac{N}{m}\right\rceil, \tag{3}\]  
where \(L\) and \(N\) are the number of inputs and outputs of the Boolean function system F; and \(n\) and \(m\) are the number of inputs and outputs of the LUT.  
In [15; 16], the upper and lower bounds on the area and delay estimates of the Boolean function when implemented in an LUT-based FPGA are given. These estimates can be used in synthesis methods to determine the measure to which the resulting solution differs from the optimal solution. In [15], the lower bound on the number of LUTs is defined by inequality (4), and the upper bound is defined by inequality (5):  
\[a_{l}(f)\geq\left\lceil\frac{L-1}{n-1}\right\rceil, \tag{4}\]  
\[a_{u}(f)\leq 2^{L-n+1}, \tag{5}\]  
where \(L\) is the number of inputs of the function \(f\). In [15], the upper area bound of the function \(f\) represented in the sum-of-products (SOP) form is also given:  
\[a_{u}(f)\leq\left\lfloor\frac{l-1+(c+1)\cdot(n-2)}{n-1}\right\rfloor, \tag{6}\]  
where \(l\) is the number of literals; \(c\) is the number of cubes [9] in the SOP of the function \(f\); and \(\left\lfloor A\right\rfloor\) is the largest integer less than or equal to \(A\).  
In [16], the lower bound of the area is defined by inequality (7), and the upper bound of the area is defined by inequality (8):  
\[a_{l}(f)\geq\left\lfloor\frac{L+1}{n-1}\right\rfloor, \tag{7}\]  
\[a_{u}(f)\leq 2^{L-n+1}-1. \tag{8}\]  
In addition, in [16], the lower delay bound is defined by inequality (9), and the upper delay bound is defined by inequality (10):  
\[d_{l}(f)\geq\log_{n}\left(L\right), \tag{9}\]  
\[d_{u}(f)\leq\left\{\begin{matrix}1,&L\leq n;\\ L-n+1,&L>n;\end{matrix}\right. \tag{10}\]  
In [17], when implementing FSMs in LUT-based FPGAs, the state number minimization method uses area, delay, and power consumption estimates. Here, the area of function \(f\) is calculated using expression (11), and the delay is calculated using expression (12):  
\[a(f)=\left\lceil\frac{L}{n-1}\right\rceil+1, \tag{11}\]  
\[d(f)=\left\lceil\frac{L-n}{n-1}\right\rceil+1. \tag{12}\]  
Note that in the FSM synthesis method [18] in FPGAs, the Hamming distance between the state codes is taken into account in the area estimation.