# Technology Mapping of FSM Oriented to LUT-Based FPGA
## 2 Theoretical Background
It shall be noticed that in i-step, there is a necessity to choose one partition (one decomposition) that is  
Figure 1: The block scheme of FSM (finite state machine). Figure 2: The idea of serial decomposition. the essence of the best mapping of the analyzed function. In the process of choosing an appropriate decomposition, it is worth to take into account configurable abilities of logic blocks included in FPGA. Let us consider the choice of decomposition of the multi-output function in the block that may be configured as \(LUT\_5/1\) or \(LUT\_4/2\). Let us assume that while analyzing various partitions of variables, four different partitions were found. They are characterized by ordered pairs of numbers (\(card(X_{\rm b})\),\(p\)) that have the values (4,3), (4,2), (5,3), and (5,4), respectively. The question is, which partition of variables is the most efficient in the situation when we want to use the blocks \(LUT\_5/1\) or \(LUT\_4/2\). In order to limit the number of inputs to maximum in i-step of decomposition, it is advantageous to use the solution for which \(card(X_{\rm b})-p\) takes the maximum value. In this situation, it is better to choose one of two decompositions characterized by the ordered pair (\(card(X_{\rm b})\),\(p\)) equal (4,2) or (5,3). Assuming the possibility of configuration of LUTs to the form of \(LUT\_4/2\) or \(LUT\_5/1\), the most effective decomposition is (\(card(X_{\rm b})\),\(p\)) = (4,2) as it requires using only one \(LUT\_4/2\) block. Decomposition, for which (\(card(X_{\rm b})\),\(p\)) = (5,3) forces using up to three blocks \(LUT\_5/1\). The above considerations enable to form the rule of the choice of decomposition in i-step which is based on the choice of the solution for which the cofactor:  
\[\delta=Number\_of\_blocks-(card(X_{\rm b})-p), \tag{2}\]  
takes the maximum value. The values of the cofactor \(\delta\) directly depend on \(card(X_{\rm b})\), \(p\), and additionally configurable abilities of LUTs. The choice of configuration of a logic block should be carried out in the way to use minimum number of configurable logic blocks. In the process of searching for the best mapping, appears the problem of choosing an appropriate decomposition. The choice of an appropriate decomposition is based on the choice of the minimum value of the cofactor \(\delta\) whose values are included in separate cells of a triangle table (Figure 3) [48]. The values of the cofactor \(\delta\) are indicated in accordance with the dependency (2). Configurable abilities of LUTs to one of two forms \(LUT\_5/1\) or \(LUT\_4/2\) are taken into account. The process of choosing an appropriate decomposition in i-stage of mapping enables to create appropriate paths leading to very effective solutions taking area into account [47]. Ashenhurst-Curtis decomposition (often named as a simple serial decomposition) is the basis of more complex decomposition models such as iterative, multiple, and mixed decomposition [43; 46]. Implemented combinational circuits are usually multi-output. Thus, it is key to determine the effectiveness of mapping for a multi-output function.