# Technology Mapping of FSM Oriented to LUT-Based FPGA
## 1 Introduction  
Logic synthesis algorithms targeted at programmable logic devices are extremely important. Their effectiveness leads to obtaining solutions: faster, cheaper, whose power consumption has been significantly reduced. This is particularly important in the case of sequential circuits where FSM (finite state machine) plays a key role. The process of carrying out FSM in programmable logic devices is associated with the problem of an efficient technology mapping. The state assignment has a substantial influence on technology mapping. Technology mapping is usually oriented at precisely described project limitations. The goal of optimization may be the area [1, 2], the speed [3], and minimization of the power consumption [4, 5] or testability of a circuit [6]. The state assignment is the most important element of FSMs synthesis. Despite the fact that advanced methods of state assignment [7, 8] are often regarded as optimal, more effective methods of carrying out FSM have been still searched for [9, 10, 11, 12, 13, 14]. The problem of state assignment is often reduced to i.e., input and output coding [15]. Some known methods are based on dichotomies [16], adjacency analysis [17], or dominance graphs [18]. In recent years, the problem of the synthesis of low-power circuits has been the matter of the main interest. Classic methods of coding directed at minimization of the power consumption are based on minimization of the switching activity. The codes with minimum code distance are assigned to the states and transitions occur between them [19, 20, 21] (minimum weighted hamming distance method). There are also well-known coding methods that are based on integer linear programming [19] and those that use genetic algorithms [22, 23]. However, the most popular state coding methods include those using heuristic methods [24, 25]. A series of methods of carrying out FSM are also very well-known and the essence lies in the usage of various solutions enablingto limit the power consumption by local lowering of both power supply as well as clock frequency signals. In many cases, the main idea of FSM logic synthesis is based on decomposition. Different kinds of decomposition are considered such as structural decomposition of FSMs [11; 26; 27; 28], functional decomposition [29; 30; 31], or general decomposition [22]. The decomposition-based logic synthesis is especially crucial in the case of LUT-based (look-up table) FPGAs (field-programmable gate array). The complexity of synthesis led to searching for new forms of FSM specification. The most promising are binary decision diagrams (BDD) [32; 33] and and-inverter graphs (AIG) [34]. Binary decision diagrams as well as and-inverter graphs, implemented in the tool ABC [35], may be used in the synthesis of FSMs. The process of synthesis can be also directed at using inbuilt memory blocks [36]. A special place is dedicated to the methods enabling to carry out circuits in the form of asynchronous circuits [37] or GALS structures (globally asynchronous locally synchronous) [38]. A logic synthesis is also especially essential from the point of view of designing cyber-physical systems [39; 40; 41; 42]. It should be mentioned that skillful coding of states does not solve all the problems enabling for effective mapping of FSM in a programmable structure. It is also worth to mention that in commercial tools, the most basic methods of coding the states such as 'one-hot' encoding or binary encoding are used. The solutions, obtained this way, are usually far from optimal. In the case of carrying out FSM in LUT-based FPGAs, decomposition is an especially crucial element of the logic synthesis. It is a theoretical basis of mapping of logic functions into LUTs [43]. A series of various decomposition strategies are known [44]. In the process of decomposition, multi-output functions decomposition should be considered as it gives the possibility to search for shared LUTs.