## 3 Analysis of Related Work  
Methods for improving spatial characteristics of FSM circuits are discussed in thousands of scientific works. For example, they can be found in [18; 19; 25; 30; 32; 33; 34; 35; 36; 37; 38]. To estimate the chip area required for a LUT-based circuit, the designers use the values of LUT counts [18]. Therefore, reducing the value of LUT count leads to a decrease in the area occupied by the circuit. This goal can be achieved using: 1. an optimal state assignment; 2. a functional decomposition (FD) of SBFs (2) and (3); and 3. a structural decomposition (SD) of the FSM logic circuit [19]. The optimal state assignment excludes some literals from sum-of-products (SOPs) of functions (2) and (3) [39]. In the best case, this exclusion allows for implementing a single-level Mealy FSM circuit. One of best state assignment methods is JEDI, which is distributed together with the CAD tool SIS [40]. In the work of [41], results of applying JEDI to FSMs from the library LGSynth93 are shown [42]. These results show that JEDI allows for excluding up to 3 literals from SOPs (2) and (3), representing the benchmark FSMs. Therefore, using JEDI can turn multi-level circuits into single-level ones only for rather simple FSMs [32]. Using either FD or SD leads to representing SBFs (2) and (3) by systems of partial Boolean functions [34; 43]. Each PBF should depend on no more than \(S_{L}\) arguments. In this case, each PBF will be represented by a single-LUT circuit. Applying any type of decomposition produces multi-level FSM circuits. However, there is a fundamental difference in the resulting interconnection system for different decomposition methods [19]. Applying the functional decomposition leads to FSM circuits with a \"spaghetti-type\" irregular interconnect system. In such a system, the same inputs and state variables may appear at any place on the circuit. Let us point out that the system of interconnections has a regular character for SD-based FSM circuits. An SD-based FSM circuit consists of large blocks [19]. Each block has its unique systems of input variables and output functions, which can differ from FSM inputs \(i_{l}\in I\) and state variables \(T_{r}\in SV\). Due to this, SD-based circuits have better quality than the equivalent FD-based circuits [19]. One such method is the encoding of FSM output collections (OCs) [19]. A collection \(O_{q}\subseteq O\) is a set of outputs \(o_{n}\in O\) that are generated simultaneously during the same interstate transition. If a particular STG has \(H\) interstate transitions, then the number of OCs, \(Q\), differs from 1 to H [19]. To encode \(Q\) OCs by maximum binary codes \(K(O_{q})\), R2 variables are enough:  
\[R2=\lceil\log_{2}Q\rceil. \tag{5}\]These variables create the set \(AV=\{a_{1},\ldots,a_{R2}\}\). There are two SBFs representing the system of FSM outputs [19]:  
\[AV=AV(SV,I); \tag{6}\]  
\[O=O(AV). \tag{7}\]  
Applying this approach turns \(P\) Mealy FSM into \(PY\) Mealy FSM (Figure 2). In the LUT-based \(PY\) Mealy FSM, the block \(LUTerSV\) implements SBF (2). The block \(LUTerAV\) generates the additional variables represented by SBF (6). The block \(LUTerOF\) produces the FSM outputs represented by SBF (7). As follows from the research [44], this approach allows for reducing the chip area necessary for generating FSM outputs compared to this parameter if the outputs are represented by SBF (3). However, this gain reduces the value of the maximum operating frequency compared to an equivalent \(P\) Mealy FSM. To optimize characteristics of \(PY\) Mealy FSMs, the encoding of OCs may be connected with a twofold state assignment [20], leading to \(P_{T}Y\) Mealy FSMs. We will discuss them a bit further. To execute the TSA, we should find a partition \(\pi_{S}\) of the set \(S\) by \(K\) classes. Each class includes compatible states.