# Basic Approaches for Reducing Power Consumption in Finite State Machine Circuits--A Review
## 2 FSMs and FPGAs: Background Information  
An FSM can be defined as a six-tuple \(S=\langle A,X,Y,\delta,\lambda,a_{1}\rangle\)[29], where \(A=\{a_{1},\ldots,a_{M}\}\) is a set of internal states, \(X=\{x_{1},\ldots,x_{L}\}\) is a set of inputs, \(Y=\{y_{1},\ldots,y_{N}\}\) is a set of outputs, \(\delta\) is a transition function, \(\lambda\) is a function of the output, and \(a_{1}\in A\) is an initial state. An FSM can be represented using various tools, such as state transition graphs (STGs) [4], state transition tables (STTs) [29], algorithmic state machines [30], binary decision diagrams [10; 31], and-inverter graphs [32], and graph-schemes of algorithms [29]. In this survey, we used either STGs or STT for the specification of FSMs. The FSM states are represented by the nodes of an STG. The arcs connecting the nodes define the interstate transitions determined by the input signals which are the conjunctions of inputs \(x_{l}\in X\) (or their complements). These conjunctions are written above the arcs together with the outputs generated during the transitions. To design an FSM circuit, an STG should be transformed into the corresponding STT. An STT includes the following columns [29]: \(a_{m}\) is a current state; \(a_{S}\) is a state of transition; \(X_{h}\) is an input signal determining a transition from \(a_{m}\) to \(a_{s}\); \(Y_{h}\) is a subset of the set \(Y\) generated during the particular transition. We name this subset a collection of outputs. The numbers of transitions (\(h\in\{1,\ldots,H\}\)) are shown in the last column of the STT. There are two main types of FSM, namely, Mealy [33] and Moore FSMs [34]. The first of them was proposed in 1955 by [PERSON]; the second was proposed in 1956 by [PERSON]. In both cases, the function \(\delta\) determines the states of transition as functions depending on the current states and inputs. Thus, it is the following function:  
\[\delta(A,X)=A. \tag{1}\]  
For Mealy FSMs, the function \(\lambda\) determines the outputs as functions depending on the current states and inputs. It gives the following function:  
\[\lambda(A,X)=Y. \tag{2}\]  
For Moore FSMs, the function \(\lambda\) determines the outputs with the following function:  
\[\lambda(A)=Y. \tag{3}\]  
In this article, we mostly analyze the reduced power consumption (RPC) methods for Mealy FSMs. Our choice is explained by the fact that these methods are widely represented in the open scientific and technical literature. In 1965, [PERSON] proved a theorem on the structural completeness of FSMs [35]. According to this theorem, an FSM circuit is represented as a composition of the combinational part and the memory. The memory is necessary to keep the history of the FSM operation. The history is represented by FSM internal states. This fundamental approach is still widely used for the synthesis of FSM circuits. An FSM logic circuit is represented by some systems of Boolean functions (SBFs) [29]. To find these SBFs for Mealy FSMs, it is necessary to [29]: (1) encode states \(a_{m}\in A\) by binary codes \(K(a_{m})\); (2) construct sets of state variables \(T=\{T_{1},\ldots,T_{R}\}\) and input memory functions (IMFs) \(\mathrm{D}=\{D_{1},\ldots,D_{R}\}\); and (3) transform an initial STT into a direct structure table (DST). States \(a_{m}\in A\) are encoded during the step of state assignment [4]. The minimum possible number of state variables \(R_{S}\) is determined by  
\[R_{S}=\ \lceil log_{2}M\rceil. \tag{4}\]  
The approach based on (4) defines so-called maximum binary codes [4]. This method is used, for example, in the well-known academic system SIS [36]. But the number of state variables can be different from (4). For example, the one-hot state codes with \(R=M\) are used in the academic system ABC [32; 37] of Berkeley. The maximum binary codes and one-hot codes define extreme points of the encoding space. There are other approaches for state assignment where the following relation holds: \(\lceil log_{2}M\rceil\leq R\leq M\). A state register (RG) keeps the state codes.