# Transforming Group Codes in Mealy Finite State Machines with Composite State Codes
## 2 LUT-Based FSM Design  
There are a lot of approaches used for representing the behavior of a Mealy FSM [1]. The most common are state transition graphs (STGs) or state transition tables (STTs) [18]. We use both tools to represent transitions between the states from the set \(A=\{a_{1},\ldots,a_{M}\}\). The transitions depend on FSM inputs comprising the set \(X=\{x_{1},\ldots,x_{L}\}\). During the transitions, some FSM outputs are generated from the set \(Y=\{y_{1},\ldots,y_{N}\}\). As follows from these sets, an FSM has \(M\) internal states, \(L\) external inputs and \(N\) outputs. For each state, \(a_{m}\in A\), an STG (or an STT) shows which outputs are generated under the influence of FSM inputs [1]. There are \(H\) interstate transitions represented by either an STG or STT. The first step of FSM synthesis is a state assignment [19]. During the state assignment, the abstract states \(a_{m}\in A\) are represented by some physical objects. These objects are binary codes, \(BC(a_{m})\), having \(R\) bits. The state codes consist of bits corresponding to state variables combined into a set, \(T=\{T_{1},\ldots,T_{R}\}\). Using an STT, it is possible to derive systems of Boolean functions (SBFs) representing a combinational part of an FSM circuit. The state codes \(BC(a_{m})\) are stored in a state code register, \(RG\). The minimum width (the number of bits) is provided by so-called maximum binary codes. Their width (\(R\)) is determined as [1]  
\[R=\lceil log_{2}M\rceil. \tag{1}\]  
To change the content of the RG, three objects are used. These objects are input memory functions (IMFs), a pulse of initialization, \(Start\), and a pulse of synchronization, \(Clock\). As a rule, the RG consists of D flip-flops [1]. Due to this, the IMFs create a set, \(D=\{D_{1},\ldots,D_{R}\}\). If \(Start=1\), then a code for the initial state \(a_{1}\in A\) is loaded into the RG. If a certain edge of the pulse \(Clock\) arises, then the bits of the IMFs are repeated in the contents of the RG. Using an initial STT (or STG) and state codes, it is possible to derive the following SBFs [20]:  
\[D =D(T,X); \tag{2}\] \[Y =Y(T,X). \tag{3}\]  
These SBFs determine the combinational part of an FSM circuit. Systems (2) and (3) determine a so-called P FSM [14]. The combinational part is implemented using some logic elements. The peculiarities of these elements significantly influence the architecture of an FSM circuit [7]. This paper is devoted to the design of FPGA-based FSMs. Modern FPGAs include a lot of LUTs, which are parts of configurable logic blocks (CLBs) [21]. In this article, we target chips produced by AMD Xilinx [4]. The CLBs from this company consist of LUTs, dedicated multiplexers and programmable flip-flops. Using multiplexers, it is possible to obtain a super-LUT having more inputs than a basic LUT. For example, there are \(S_{L}=6\) inputs in the basic LUT from the Virtex-7 family of FPGAs [4,22]. To show the number of inputs, we denote an LUT as \(S_{L}\)-LUT. Inside a single CLB, either two seven-LUTs or one eight-LUT can be created with the help of multiplexers. These super-LUTs (SLUTs) have practically the same delay as their six-input counterparts [23]. If an SLUT must have an \(S_{L}\geq 9\), then the internal resources of several configurable blocks are used. But such big SLUTs are significantly slower than SLUTs created inside a single CLB [23]. In this paper, we use the symbol _LUTer_ to show that a logic block is implemented using LUTs and other internal CLB resources. Because there is a direct connection between the outputs of LUTs and the inputs of flip-flops, such blocks are implemented as registers inside CLBs. So, the state code register is a part of an LUTer. This preliminary information allows for the creation of a structural diagram of the FPGA-based FSM \(U_{1}\) (Figure 1). A block, \(LUTerD\), implements IMFs represented by the system (2). We show the state register RG as a separate block, but in reality, this block is a part of \(LUTerT\). The pulses \(Start\) and \(Clock\) enter \(LUTerT\).