# Improving Hardware in LUT-Based Mealy FSMs
## 4 Main Idea of the Proposed Method  
The analysis of FSM \(U_{2}\) (Figure 4) allows finding its shortcomings. The main drawback of \(U_{2}\) is the need to form two systems of additional variables. One of them serves to replace the inputs \(x_{l}\in X\), and the second system is used to encode the collections of outputs. These systems are represented by SBFs (5) and (10), respectively. To implement these systems, it is necessary to use some internal resources of FPGA chip. The amount of resources used can be reduced by using the same additional variables to implement both input memory functions and FSM outputs. In our article, there is proposed such an approach. Our analysis  
Figure 4: Structural diagram of Mealy FSM \(U_{2}\). of the extensive literature shows that so far, there has been no such a method. Due to it, the proposed method has an undeniable scientific novelty. Our method is based on using the codes of collections of FSM outputs for generating IMFs \(D_{r}\in\Phi\). Consider Figure 5 where this idea is illustrated. A subgraph of some STG is shown in Figure 5. The generator of pulses _Clk_ sets the course of discrete time \(t(t=0,1,2,\ldots)\). Three instances of time are shown in Figure 5. In the instant of time \(t\), the FSM is in the state \(a(t)=a_{4}\). The transition from \(a_{3}\) into \(a_{4}\) is accompanied by producing a CO \(Y_{5}\). So, the following relation takes place: \(Y_{q}(t)=Y_{5}\). From STG (Figure 5), we can find that \(a(t+1)=a_{5}\) and \(Y_{q}(t+1)=Y_{3}\). So, the transition \(<a_{4},a_{5}>\) corresponds to a pair of COs \(<Y_{5},Y_{3}>\). This transition is caused by an input \(x_{2}\in X\). So, the pair \(<a_{4},x_{2}>\) also corresponds to a pair of COs \(<Y_{5},Y_{3}>\). This means that IMFs can be represented using only codes of COs. In FSM \(U_{2}\), the SOPs of functions \(D_{r}\in\Phi\) include product terms \(F_{h}\) determined as  
\[F_{h}=A_{m}\wedge B_{h}. \tag{11}\]  
In (11), the symbol \(A_{m}\) stands for a conjunction of the state variables corresponding to the code of a current state \(a_{m}\) written in the \(h\)-th row of DST; the symbol \(B_{h}\) stands for a conjunction of additional variables replacing the input signal \(X_{h}\) written in the \(h\)-th row of DST (\(h\in\{1,\ldots,H\}\)). If a pair \(<a_{m},X_{h}>\) determines the \(h\)-th transition of an FSM, then we propose to replace it by a pair of COs (as it follows from Figure 5). So, we propose to construct the SOPs of functions \(D_{r}\in\Phi\) using product terms formed by conjunctions corresponding to codes of COs replacing a pair \(<a_{m},X_{h}>\). To do it, we should use different sets of variables to encode COs \(Y(t)\) and \(Y(t+1)\). For example, we use the elements of the set \(Z=\{z_{1},\ldots,z_{RQ}\}\) to encode a CO \(Y(t+1)\) and the elements of a set \(V=\{v_{1},\ldots,v_{RQ}\}\) to encode a CO \(Y(t)\). Obviously, this actually doubles the number of variables encoding the collections of outputs compared to (6). To avoid doubling the resources used for the encoding, we propose using two interconnected registers for storing the codes of COs. This approach results in FSM \(U_{3}\) (Figure 6). In FSM \(U_{3}\), a block \(LZ\) implements SBF (7). There is a distributed register \(RZ\) inside of the block \(LZ\). The register keeps the codes of COs \(Y(t+1)\). This explains the presence of pulses _Clk_ and _Res_ entering \(LZ\). The variables \(z_{r}\in Z\) are inputs of both a block \(LY\) and a register \(RV\). The block \(LY\) implements SBF (8). The register \(RV\) de facto transforms the variables \(z_{r}\in Z\) into the variables \(v_{r}\in V\) representing the codes of COs \(Y(t)\). As follows  
Figure 5: Illustration of the main idea of proposed method. Figure 6: Structural diagram of LUT-based Mealy FSM \(U_{3}\). from Figure 6, the same pulses \(Clk\) and \(Res\) are used by both registers.