# Improving Hardware in LUT-Based Mealy FSMs
## 2 Basics of LUT-Based Mealy FSM Design
\begin{table}
\begin{tabular}{l l} \hline \(A=\{a_{1},\ldots,a_{M}\}\) & The set of FSM internal states having M elements. \\ \hline \(B=\{b_{1},\ldots,b_{J}\}\) & The set of additional variables replacing FSM inputs having J elements where \(J\ll L\). \\ \hline \(I\) & The number of LUT inputs. \\ \hline \(K(a_{m})\) & The binary code of state \(a_{m}\in A\). \\ \hline \(K(Y_{q})\) & The binary code of collection of outputs \(Y_{q}\subseteq Y\) with \(R_{q}=\lceil log_{2}Q\rceil\) bits. \\ \hline \(NA(\phi_{k})\) & The number of literals in a function \(\phi_{k}\in\Phi\cup Y\). \\ \hline \(P_{g}=<Y_{i},Y_{j}>\) & A pair of collections of outputs replacing a pair \textless{}state, input\textgreater{}. \\ \hline \(\Phi=\{D_{1},\ldots,D_{R}\}\) & The set of FSM input memory functions having R elements. \\ \hline \(Q\) & The number of collections of outputs \(Y_{q}\subseteq Y\). \\ \hline \(R\) & The number of bits in the codes \(K(a_{m})\) determined as \(R=\lceil log_{2}M\rceil\). \\ \hline \(T=\{T_{1},\ldots,T_{R}\}\) & The set of state variables for creating the codes \(K(a_{m})\) with R bits. \\ \hline \(V=\{v_{1},\ldots,v_{RQ}\}\) & The set of additional variables encoding collections of outputs from the current cycle of FSM operation having RQ bits. \\ \hline \(X=\{x_{1},\ldots,x_{L}\}\) & The set of FSM inputs having L elements. \\ \hline \(Y=\{y_{1},\ldots,y_{N}\}\) & The set of FSM outputs having N elements. \\ \hline \(Z=\{z_{1},\ldots,z_{RQ}\}\) & The set of additional variables encoding collections of outputs from the previous cycle of FSM operation having RQ bits. \\ \hline \end{tabular}
\end{table} 
Table 1: The main notation used in the article. In Figure 1, the \(BlockY\Phi\) implements the SBFs (2) and (3). The \(RG\) includes R flip-flops. The pulse \(Res\) loads the code of the initial state \(a_{1}\in A\) into \(RG\). Very often, there are only zeros in the code \(K(a_{1})\)[18]. The synchronization pulse \(Clk\) allows loading state codes into \(RG\). Consider a transition between the states \(a_{3}\) and \(a_{5}\) of some Mealy FSM. Let it be the transition with \(h=6\). The transition is represented using fragments of three equivalent forms: an STG, an STT and a DST (Figure 2). As follows from Figure 2a, the transition \(<a_{3},a_{5}>\) is caused by the input signal \(X_{6}=x_{1}\overline{x_{2}}\). The transition is accompanied by the producing of a CO \(Y_{6}=\{y_{2},y_{4}\}\). Row 6 of the STT (Figure 2b) is a sequence of characters corresponding to the fragment of STG (Figure 2a). If, for example, there is \(M=7\), then using (1) gives \(R=3\) and two sets: \(T=\{T_{1},T_{2},T_{3}\}\) and \(\Phi=\{D_{1},D_{2},D_{3}\}\). For a trivial state assignment [5], there are the codes \(K(a_{3})=010\) and \(K(a_{5})=100\). These codes and IMF \(D_{1}\) are written in the sixth line of DST (Figure 2c). This line determines a product term \(F_{6}=\overline{T_{1}}T_{2}\overline{T_{3}}x_{1}\overline{x_{2}}\). This term is a part of the sum of products (SOPs) of Boolean functions \(D_{1}\in\Phi\) and \(y_{2},y_{4}\in Y\). All other terms of SOPs for (2) and (3) are obtained in the same way [5]. In this paper, we discuss a case of implementing SBFs (2) and (3) using configurable logic blocks (CLBs) and other internal resources of FPGA chips [19]. To form an FSM circuit, the CLBs are connected using a programmable routing matrix [17; 20]. In this paper, we consider CLBs, including LUTs, multiplexers and programmable flip-flops. Similar to the notation used in the paper [21], we use a symbol \(I\)-LUT to denote a single-output LUT having \(I\) inputs. Such a LUT can implement an arbitrary Boolean function having up to \(I\) arguments. The analysis of the FPGA market shows that AMD Xilinx dominates this market [19]. Due to it, we focus our current research on the solutions of Xilinx. These solutions are very popular at present for the implementation of various projects. This fact is confirmed by the analysis of the literature [22; 23; 24; 25; 26; 27; 28].