# Transforming Group Codes in Mealy Finite State Machines with Composite State Codes
## 2 LUT-Based FSM Design
The FSM outputs (3) are produced by the LUTs of the block \(LUTerY\). These outputs are used by the other blocks of a digital system. So, it makes sense to reduce the delay between the arrival of FSM inputs, \(x_{l}\in X\), and the production of FSM outputs, \(y_{n}\in Y\). A serious drawback is inherent in modern FPGAs: the number of basic LUT inputs (\(S_{L}\)) is really small [8]. This significantly affects the number of LUTs and their levels in the FSM circuit. If the sum of product (SOP) of a Boolean function, \(f_{i}\in D\cup Y\), includes \(NL_{i}\) literals, then the corresponding LUT-based circuit is multi-level if  
\[NL_{i}>S_{L}. \tag{4}\]  
To construct the SOPs of functions \(f_{i}\in D\cup Y\), it is necessary to create a direct structure table (DST) [20]. Both STGs and STTs could be used for constructing a DST [18]. In our paper, we start synthesis using an STG. An STG includes \(M\) vertices corresponding to FSM states. The vertices are connected by arcs determining interstate transitions. There are \(H\) arcs in an STG. The arc number \(h\in\{1,\ldots,H\}\) is determined by the values of \(X_{h}\) and \(Y_{h}\). The conjunction of inputs \(X_{h}\) is an input signal determining a particular transition. The symbol \(Y_{h}\) stands for a collection of outputs (CO) generated during a particular transition. To create a DST, it is necessary to transform an STG into the equivalent STT. An STT includes the following columns: \(a_{m}\) (the current state), \(a_{S}\) (a state of transition), \(X_{h}\) (an input signal), \(Y_{h}\) (a collection of outputs), and \(h\) (the number of interstate transitions). The first column includes the current state, the second column contains a state of transition, the third column contains an input signal determining the transition from the current state into the next state, and a CO generated during the transition, \(Y_{h}\), is written in the fourth column. A DST is an extension of the original STT with three additional columns. Two of the additional columns contain binary codes, \(BC(a_{m})\) and \(BC(a_{S})\). The third column includes a collection of IMFs, \(D_{h}\subseteq D\), determining the code \(BC(a_{S})\)[20]. Of course, there are the same number of rows in the equivalent STT and DST. Two types of codes are typical for FSMs: maximum binary codes and one-hot codes [24]. These approaches have both positive and negative aspects. Using MBCs leads to the minimum possible number of flip-flops into the RG, but this leads to really complex SOPs for functions (2) and (3). As a result, an FSM circuit may include a lot of LUT levels and a very sophisticated system of interconnections [7]. One-hot codes are characterized by having the maximum number of bits (\(R_{OH}=M\)). This leads to the use of many more flip-flops than in the case of MBC-based FSMs, but the SOPs of the IMFs and FSM outputs are rather simple. A comparison of FSMs based on MBCs and OHCs was executed in article [25]. This comparison showed that using OHCs provides better results for FSMs with \(M>16\). As  
Figure 1: Architecture of FPGA-based FSM \(U_{1}\). was shown in [3], both LUT counts and power consumption depend significantly on the value of \(L\). The following conclusion can be made from an analysis of the experiments conducted by the authors of paper [26]: MBC-based FSMs have better characteristics (as compared with OHC-based FSMs) if the following condition holds: \(L>10\). If condition (4) is true for a function, \(f_{i}\in D\cup Y\), then this function should be decomposed. In this case, such a function is represented by a collection of partial Boolean functions (PBFs). To find such a representation, methods of functional decomposition (FD) [27] could be applied. To be represented by a single-LUT circuit, any partial function should depend on no more than \(S_{L}\) arguments. Next, all LUTs generating partial Boolean functions representing the same function, \(f_{i}\in D\cup Y\), should be combined into a multi-level circuit.