# Improving Hardware in LUT-Based Mealy FSMs
## 2 Basics of LUT-Based Mealy FSM Design  
In this section, we show the basics of designing FSMs circuits using internal resources of FPGAs. Here, we introduce the main notation used in the rest of the text and show the features of the logic elements used. At last, we introduce the simplest structural diagram of a Mealy FSM circuit implemented with LUTs and programmable flip-flops. For a better understanding of the material of the article by readers, we introduce Table 1. This table shows the main sets of variables and the notation adopted in our article. To start the designing process, it is necessary to set the law of the FSM behavior. For this, various mathematical apparatuses can be used [1]. Two methods are most commonly used for this purpose: (1) a state transition graph (STG) and (2) a state transition table (STT) [16]. We use both forms in this article. These forms are used to derive systems of Boolean functions (SBFs) defining dependencies between FSM outputs and input memory functions on the one hand, and FSM inputs and state variables on the other hand. These SBFs are used to design FSM logic circuits [16]. The FSM inputs create a set \(X=\{x_{1},\ldots,x_{L}\}\), the FSM outputs form a set \(Y=\{y_{1},\ldots,y_{N}\}\). The inputs determine transitions between FSM states combined into a set \(A=\{a_{1},\ldots,a_{M}\}\). To synthesize an FSM circuit, the states \(a_{m}\in A\) are represented by binary codes \(K(a_{m})\) having \(R\) bits. The states are encoded using state variables from the set \(T=\{T_{1},\ldots,T_{R}\}\). The \(r\)-th bit of a state code is represented by an internal state variable \(T_{r}\in T\). The minimum value of \(R\) is calculated using the following formula:  
\[R=\lceil log_{2}M\rceil. \tag{1}\]  
The formula (1) determines so-called maximum state codes [17]. A special register \(RG\) is entered into the FSM circuit as a memory of the state codes [5]. In the case of FPGA-basedFSMs, the \(RG\) is implemented using D flip-flops [17; 18]. The content of \(RG\) is determined by the input memory functions combined into a set \(\Phi=\{D_{1},\ldots,D_{R}\}\). The IMFs are inputs of \(RG\) showing a direction of a particular interstate transition. The SBFs that make it possible to synthesize an FSM circuit can be formed using a direct structure table (DST) [5]. A DST is constructed on the base of either the initial STT or STG. An STT includes the following columns [16]: a current state \(a_{m}\) (a state for the current instant); a state of transition \(a_{T}\) (a state for the next instant); an input signal \(X_{h}\) determining the transition from \(a_{m}\) into \(a_{T}\) (it is a certain conjunction of inputs); a collection of outputs (CO) \(Y_{h}\) formed during the transition \(<a_{m},a_{T}>\); and the numbers of transitions are shown in the column \(h\). There are \(H\) lines in an STT. A DST includes all these columns and three additional columns. These additional columns are [5] the current state code \(K(a_{m})\), the next state code \(K(a_{T})\), and IMFs \(\Phi_{h}\subseteq\Phi\), which allows loading the next state code into \(RG\). Using a DST, the following SBFs are constructed:  
\[\Phi=\Phi(T,X); \tag{2}\]  
\[Y=Y(T,X). \tag{3}\]  
The SBF (2) corresponds to the FSM transition function [5] that specifies the dependence of the states of transition on the current states and input variables. The SBF (2) represents rules of generating IMFs necessary to load a next state code into the \(RG\). The SBF (3) corresponds to the FSM output function [5] that specifies the dependence of the FSM outputs on the current states and input variables. The SBF (3) represents rules of generating FSM outputs during each interstate transition. The SBFs (2) and (3) are the basis for the synthesis of FSM \(U_{1}\), whose structural diagram is shown in Figure 1.