# Reducing LUT Count for FPGA-Based Mealy FSMs
## 2 Specifics of FPGAs and Mealy FSMs  
The majority of modern FPGAs are organized using so called \"island-style\" architecture [16; 28; 30]. They include different configurable logic blocks (CLBs) and a matrix of programmable interconnections [10; 11; 12]. In this article, we consider CLBs consisting of LUTs and programmable flip-flops. To implement LUT-based circuits of sequential blocks, it is necessary to connect outputs of some LUTs with flip-flops [5]. An extremely small amount of LUT inputs leads to the necessity of functional decomposition [17] of functions representing combinational parts of FSMs. The functional decomposition produces multi-level circuits with irregular systems of interconnections. Such circuits resemble \"spaghetti-type\" programs [28]. Using terminology from programming, we can say that the functional decomposition produces LUT-based circuits with \"spaghetti-type\" interconnections. A Mealy FSM is defined as a vector \(<X,Y,A,\delta,\lambda,a_{1}>\)[5], where \(X=\{x_{1},\ldots,x_{L}\}\) is a set of inputs, \(Y=\{y_{1},\ldots,y_{N}\}\) is a set of outputs, \(A=\{a_{1},\ldots,a_{M}\}\) is a set of internal states, \(\delta\) is a function of transitions, \(\lambda\) is a function of output, and \(a_{1}\in A\) is an initial state. A Mealy FSM can be represented using different tools, such as: state transition graphs [3; 5], binary decision diagrams [31; 32], and-inverter graphs [33], graph-schemes of algorithms [5]. In this article, we use state transition tables (STTs) for this purpose. An STT includes the following columns [3; 5]: \(a_{m}\) is a current state; \(a_{s}\) is a state of transition (a next state); \(X_{h}\) is a conjunction of inputs (or their compliments) determined a transition from \(a_{m}\) to \(a_{s}\); \(Y_{h}\) is a collection of outputs generated during the transition from \(a_{m}\) to \(a_{s}\). The column \(h\) includes the numbers of transitions (\(h\in\{1,\ldots,H\}\)). For example, the STT (Table 1) represents some Mealy FSM \(S_{1}\). Using STT (Table 1), the following parameters of \(S_{1}\) can be found: the number of inputs \(L=8\), the number of outputs \(N=7\), the number of states \(M=6\), and the number of transitions \(H=15\). Furthermore, Table 1 uniquely defines the functions of transitions and output of FSM \(S_{1}\). To find SBFs representing an FSM circuit, it is necessary [5]: (1) to encode states \(a_{m}\in A\) by binary codes \(K(a_{m})\); (2) to construct sets of state variables \(T=\{T_{1},\ldots,T_{R}\}\) and input memory functions (IMFs) \(\Phi=\{D_{1},\ldots,D_{R}\}\) and (3) to transform an initial STT into a direct structure table (DST). States \(a_{m}\in A\) are encoded during the step of state assignment [3]. In this article, we use the state codes having the minimum possible number of state variables \(R\), where  
\[R=\lceil log_{2}M\rceil. \tag{1}\]  
This method is used, for example, in well-known academic system SIS [34]. There are other approaches for state encoding where the number of state variables differs from (1). For example, the academic system ABC [33] of Berkeley uses one-hot state assignment with \(R=M\). State codes are kept into a state register (\(RG\)). The \(RG\) consists of R flip-flops with mutual inputs of synchronization (_Clock_) and reset (_Start_). For LUT-based FSMs, D flip-flops are used to organize state registers [9]. The pulse _Clock_ allows the functions \(D_{r}\in\Phi\) to change the RG content. To find functions representing an FSM circuit, it is necessary to create a direct structure table. A DST is an expansion of an STT by the columns with codes of current and next states (\(K(a_{m})\) and \(K(a_{s})\), respectively). Furthermore, a DST includes a column \(\Phi_{h}\) with symbols \(D_{r}\in\Phi\) corresponding to 1's in the code \(\mathrm{K}(a_{s})\) from the row \(h\) of a DST (\(h\in\{1,\ldots,H\}\)). The following SBFs are derived from a DST:  
\[\Phi =\Phi(T,X); \tag{2}\] \[Y =Y(T,X). \tag{3}\]