# Reducing LUT Count for FPGA-Based Mealy FSMs
## 1 Introduction  
One of the features of our time is a wide application of digital systems in various spheres of human activity [1; 2]. Modern digital systems include different combinational and sequential blocks [3; 4]. The behaviour of a sequential block can be represented using the model of finite state machine (FSM) [5; 6]. To improve characteristics of a digital system, it is necessary to improve such characteristics of FSMs as internal occupied resources, performance and power consumption. This necessity explains the continuous interest in developing methods aimed at optimizing these characteristics of FSM circuits. As a rule, the less internal occupied resources are used by an FSM circuit, the less power it consumes [7]. So, it is very important to reduce internal occupied resources consumed by an FSM circuit. A sequential block can be represented as either Mealy or Moore FSM [5; 6]. There are thousands of monographs and articles devoted to problems of FSM circuits design. The vast majority of these works are devoted to Mealy FSMs. Based on this analysis, we have chosen Mealy FSM as the object of research in our current article. To diminish the required internal occupied resources, it is necessary to take into account specifics of logic elements implementing FSM circuits [8; 9]. Nowadays, field programmable gate arrays (FPGAs) [10; 11; 12] are widely used in the implementation of digital systems [9; 13; 14; 15]. Due to it,we choose FPGA-based FSMs as a research object in the given article. In this article, we consider a case when look-up table (LUT) elements are used to implement logic circuits of Mealy FSMs. A LUT is a block having \(S_{L}\) inputs and a single output [10; 12]. A single LUT allows implementing an arbitrary Boolean function having up to \(S_{L}\) arguments [16; 17]. However, the number of LUT inputs is rather small [10; 12]. This feature leads to the need of functional decomposition of systems of Boolean functions (SBFs) representing FSM circuits [17; 18]. In turn, this leads to multi-level FSM circuits with complex systems of interconnections [9]. One of the most crucial steps in the LUT-based design flow is the technology mapping [19; 20; 21; 22; 23; 24; 25]. During this step, an FSM circuit is converted into a network of interconnected LUTs. The outcome of technology mapping determines resulting characteristics of an FSM circuit. These characteristics are strongly interrelated. The internal occupied resources consumed by a LUT-based FSM circuit include LUTs, flip-flops, interconnections, circuit of synchronization, input-output blocks. Obviously, to reduce the amount of required resources, it is very important to reduce the LUT count in a circuit. As follows from [26], the more LUTs are included into an FSM circuit, the more static power it consumes. Now, process technology has scaled considerably, with current design activity at 14 and 7 nm. Due to it, interconnection delay now dominates logic delay [26]. As noted in [16; 27], the interconnections are responsible for the consuming up to 70% on power. So, it is very important to reduce the amount of interconnections to improve the characteristics of FSM circuits. As shown in [26; 28], the value \(S_{L}=6\) provides an optimal trade-off for the occupied chip area, performance, and power consumption of a LUT. However, the complexity of FPGA-based projects is constantly growing [9]. To overcome this contradiction, it is necessary to develop the methods of technology mapping that take into account rather small value of LUT's inputs. The main contribution of this paper is a novel design method aimed at reducing the number of LUTs in circuits of FPGA-based Mealy FSMs. The proposed approach is based on joint usage of two known methods of structural decomposition (replacement of inputs and encoding of collections of outputs). The method leads to FSM circuits having three levels of logic and regular system of interconnections.