# Technology Mapping of FSM Oriented to LUT-Based FPGA
## 5 The Method of Carrying out FSM Using Sharing of Logic Resources  
In the process of a simultaneous synthesis of the whole combinational logic, the efficiency of the technology mapping should be improved. In this case, it is possible to search for common logic resources used to carry out both a transition block as well as an output block. The essence of sharing is presented in the form of block schemes in Figure 8.  
A block scheme of FSM, shown in Figure 8a,b, may be presented in the form in which separated blocks \(\delta\) and \(\lambda\) were replaced with one block that is symbolically marked as \(\delta+\lambda\) (Figure 8c). This block is described by a multi-output function \(\delta+\lambda\): \(B^{N+K}\to B^{M+K}\). The synthesis of a multi-output function \(\delta+\lambda\): \(B^{N+K}\to B^{M+K}\) gives a possibility to make the process of decomposition more effective in relation to conducting the process of decomposition separately for a transition function \(\delta\): \(B^{N+K}\to B^{K}\) and an output function \(\lambda\): \(B^{N+K}\to B^{M}\). It is possible to search for a shared block that is symbolically presented in Figure 8d. The synthesis process of FSM consists of the process of state assignment that results in the possibility of determining the function \(\delta+\lambda\): \(B^{N+K}\to B^{M+K}\) describing the whole combinational logic. Next, decomposition of multi-output function is carried out and its essence is based on mapping of a  
Figure 8: The idea of carrying out FSM using sharing of logic resources: (**a,b**) FSM form in which both combination blocks are shown separately, (**c**) FSM form in which both combination blocks are presented together, (**d**) FSM form in which the combined block has a shared block. Figure 7: The result of the synthesis of FSM directed at mapping of a function into _LUT_4/1_: (**a**) carrying out of a transition block; (**b**) carrying out of an output block. synthesized function in LUTs that have a precisely determined number of inputs. A part of outputs of an obtained structure is associated with the signals that are joined to information inputs of DFFs. The rest of the part constitutes output signals of FSM. Let us consider it as a previous mapping of multi-output function \(\delta+\lambda\): \(B^{5}\to B^{5}\) in the _LUT_4/1_. In the process of searching for mapping of the function \(\delta+\lambda\), appropriately conducted decomposition plays a key role. Now, multi-output function with more number of outputs is synthetized. While simultaneous decomposing of the multi-output function \(\delta+\lambda\): \(B^{5}\to B^{5}\), it is possible to find a more effective solution. It is usually more efficient than decomposition of a transition and an output function or searching for decomposition separately for each single-output function \((\delta+\lambda)_{i}\): \(B^{5}\to B^{1}\), \(i=1,\,2,\,\ldots,\,5\). However, it is more difficult to find decomposition of a multi-output function. When it is found, it gives better solutions, taking LUT use into consideration. In the analyzed case, which used the DECOMP system in the process of decomposition, it turned out that it was impossible to decompose the function \(\delta+\lambda\): \(B^{5}\to B^{5}\), but it was possible to find a very advantageous solution while partitioning of the multi-output function \(\delta+\lambda\): \(B^{5}\to B^{5}\) into two functions \((\delta+\lambda)_{1}\): \(B^{5}\to B^{2}\) i.e., output Q1, y0, and \((\delta+\lambda)_{2}\): \(B^{5}\to B^{3}\) i.e., output Q0, y2, y1. The next stages of decomposition are carried out in the DECOMP system and lead to mapping of a combinational block in the form of the blocks _LUT_4/1_ presented in Figure 9.  
It turns out that the circuit, presented in Figure 9, may be simplified using the method of unicoding [50; 51]. The essence of unicoding is also based on specific sharing of resources. The sharing takes place on a lower level as it is based on such a coding of column patterns that leads to determining common bound functions.