# Technology Mapping of FSM Oriented to LUT-Based FPGA
## 2 Theoretical Background  
FSM is an abstract mathematical model of a sequential circuit. This model is a five-tuple: {_X,Y,S,S_0,\(\delta\),\(\lambda\)}, where \(X\) is a set of input vectors, _S_--the set of internal states, \(S\)0--initial state, and _Y_--the set of output vectors. The relations between these elements are determined by a transition function, usually marked with the symbol \(\delta\), and an output function (\(\lambda\)) describing the values of output signals. A general structure of FSM is shown in Figure 1. Transition and output functions are associated with combinational blocks marked \(\delta\) and \(\lambda\), respectively. A memory block was symbolically marked as DFF (D-type flip-flop) in Figure 1.  
In accordance with the designations, included in Figure 1, a transition function is determined by \(\delta\): \(B^{N+K}\to B^{K}\), where \(B\) = {0,1}. Depending on a type of automaton \(\lambda\): \(B^{K}\to B^{M}\) ([PERSON]'s automaton) or \(\lambda\): \(B^{N+K}\to B^{M}\) ([PERSON]'s automaton). In the process of coding states, each internal state of an automaton is associated with K-bit vector of a state. The number of a state vector's bits depends on the accepted method of coding internal states and fulfills the inequality \([f_{\beta 2}(card(S))]\leq K\leq card(S)\)[13]. Logic blocks, included in FPGAs, contain necessary resources needed to carry out FSM. A memory block includes D flip-flops placed in logic blocks. The number of flip-flops depends on the state assignment. The transition and output blocks are carried out using LUTs whose outputs may be directly joined to the inputs of D flip-flops. One vital feature of LUTs is the fact that they enable to carry out any function that has a limited (usually low) number of variables. A low number of inputs of LUTs requires a multilevel carrying out of a combinational logic in the form of the net of LUTs. Decomposition is a mathematical model of a partition that is a basis of mapping of a logic function into LUT-based FPGAs. A decomposition model, which is the basis of the series of synthesis strategies, relies on the theorem by [PERSON] [45; 46]. Let \(f\) be \(n\)-input and \(m\)-output logic function reflecting \(B^{n}\) set into \(B^{m}\) set i.e., \(f\): \(B^{n}\to B^{m}\), where \(B=\{0,1\}\). Function \(f\): \(B^{n}\to B^{m}\) may be presented as \(Y=\{y_{m-1},\ldots,y_{1},y_{0}\}=f(I_{n-1},\ldots,I_{1},I_{0})\). Function \(f\): \(B^{n}\to B^{m}\) is subjected to decomposition i.e. :  
\[f(X_{\text{f}},X_{\text{b}})=F[g_{1}(X_{\text{b}}),g_{2}(X_{\text{b}}),\ldots, g_{\text{p}}(X_{\text{b}}),X_{\text{f}}], \tag{1}\]  
if and only if column multiplicity of Karnaugh map \(\
u(X_{\text{f}}\,|\,X_{\text{b}})\leq 2^{p}\). The sets \(X_{\text{b}}\) and \(X_{\text{f}}\) are called a bound and a free set, respectively, where \(X_{\text{b}}\cup X_{\text{f}}=\{I_{n-1},\ldots,I_{1},I_{0}\}\) and \(X_{\text{b}}\cap X_{\text{f}}=\Phi\). The above theorem is a mathematical model of technology mapping of a function \(f\): \(B^{n}\to B^{m}\) in two LUTs: \(LUT\_card(X_{\text{b}})\psi\) and \(LUT\_card(X_{\text{f}})+p/m\), where \(LUT\_a/\psi\) is the block that is a-inputs and b-outputs (Figure 2). The partition of a circuit is implied from the partition of variables. One part of n-input variables is the set of variables for p bound functions carried out in a bound block. The rest of the part of the variables creates a free set. From technology mapping of multi-output function point of view, it is key for \(LUT\_kx\) blocks that \(card(X_{\text{b}})\leq k\) and \(card(X_{\text{f}})+p\leq k\), where \(k\) indicates the number of inputs of LUT. The choice of an appropriate partition of variables is not so simple. It is directly connected with the choice of a decomposition path. In the process of searching for decomposition, various partitions are considered for which column multiplicity of a partitions' matrix is determined. Using binary decision diagrams, column multiplicity may be determined by defining so called number of cut nodes [47].