State Assignment of Finite-State Machines by Using the Values of Input Variables

Abstract

In this paper, we propose the method of FSM synthesis on field programmable gate arrays (FPGAs) when input variables are used for state assignment. For this purpose we offer a combined structural model of class A and class E FSMs. This paper also describes in detail the algorithms for synthesis a class AE FSM which consists of splitting of internal states for performance of necessary conditions for synthesis of the class E FSM and state assignment of the class AE FSM. It is shown that the proposed method reduces the area for all families of FPGAs by a factor of 1.19–1.39 on average and by a factor of three for certain families. Practical issues concerning the method and the specific features of its use are discussed, and possible directions of the elaboration of this approach are proposed.

1 Introduction

In the general case, a digital system can be represented by a set of combinational circuits and finite state machines (FSMs). FSMs are also widely used as individual units as controllers and control devices. Usually, when working on a project, the designer has to develop new FSMs each time. It is clear that the parameters of FSMs used in a digital system to a large extent determine the success of the whole project. For this reason, the issue of minimization of FSMs is very important. As the FSM optimization criteria, one typically uses area, delay, and power consumption. Presently, field programmable gate arrays (FPGAs) are widely used in digital systems; for this reason, many FSM optimization methods are designed for the implementation of FSMs based in FPGAs.

The idea of using the values of the input and output variables of the FSM for encoding its internal states was first proposed in [1]. Later, this approach was elaborated in [2], where various combinations of the input and output variables that can be used for encoding the internal states are considered. The choice of the minimum number of input and output variables for encoding is an NP-hard problem. In [3], it was proposed to use the values of the output variables of the Moor FSM as the codes of the internal states.

In [4], structural models of FSMs based on the architectural capabilities of FPGAs were proposed; these models make it possible to use the values of the FSM input and output variables as internal state codes. A new classification of structural models of FSMs is given. Here the class A and B FSMs are traditional of Mealy and Moore FSMs accordingly. In the class C (Mealy) and the class D (Moore) FSMs the value of an output vector completely coincides with the code of the present state of the FSM. In the class E (Mealy) and class F (Moore) FSMs the value of an input vector completely coincides with the code of the next state of the FSM.

In [5], the synthesis method of Mealy FSMs was proposed, where the values of output variables are used as the codes of FSM states. In this paper, we present the method of FSM synthesis which allows, unlike [5], to use the values of input variables as the codes of FSM states. For this purpose, the structural model of the class E FSM [4] is used.

2 Structural FSM Models

The most general model of the Mealy FSM can be described by means of following equations:

$$ \begin{aligned} a_{t + 1} & =\Phi (z_{t} ,a_{t} ); \\ w_{t} & =\Psi (z_{t} ,a_{t} ), \\ \end{aligned} $$

where Φ is the transition function, Ψ is the output function, a _t is the present state of the FSM at time $t\,\left( {t = 1, 2, 3, \ldots } \right),a_{t + 1}$ is the next state of the FSM, $z_{t}$ is a collection of values of the input variables (the input vector) on the FSM input at time $t,$ and $w_{t}$ is a collection of values of the output variables (the output vector) formed at time $t$.

The Mealy FSM in classification [4] received a title the class A FSM. The structural model of the Mealy FSM show on Fig. 1 a, where ${\text{CL}}_{\Phi }$ is the combinational circuit forming the values of the transition functions, ${\text{CL}}_{\Psi }$ is the combinational circuit forming the values of the output functions, and RG is the FSM’s memory.

Fig. 1.

The structural models of FSMs: a – the class A FSM; b – the class E FSM

In the class E FSM the value of the input vector z _t determines the code of the next state $a_{t + 1} ;$ therefore, the equations of functioning of the class E FSM have the following view:

$$ \begin{aligned} a_{t + 1} & = z_{t} ; \\ w_{t} & =\Psi (z_{t} ,a_{t} ), \\ \end{aligned} $$

In contrast to the Mealy FSM, the structure of the class E FSM does not include the combinational circuit ${\text{CL}}_{\Phi }$ (Fig. 1 b) that allows to build FSMs of a low cost (an area) and a high-speed performance.

However in practice, the “pure” type of the class E FSM meets very rarely. Therefore, in the present work we offer the combined model of the class AE FSM. In the class AE FSM the codes of internal states are divided on two parts: one part is defined by the value of input variables, and the second part is formed the same as in the class A FSM, by means of combinational circuit ${\text{CL}}_{\Phi }$ (Fig. 2).

Fig. 2.

The structural model of the class AE FSM

The memory of the class AE FSM is presented by two registers RG_A and RG_E which correspond to the class A and the class E FSMs. The internal state a _t of the class AE FSM is defined by a concatenation of two states: $a_{t}^{{\prime }}$ and $a_{t}^{{\prime \prime }}$, i.e. $a_{t} = \left\{ {a_{t}^{{\prime }} ,a_{t}^{{\prime \prime }} } \right\}$ , where $a_{t}^{{\prime }}$ is the value on outputs of the register RG_E, and $a_{t}^{{\prime \prime }}$ is the value on outputs of the register RG_A. The code of the next state a _t+1 also is defined by the concatenation of two states: $a_{t + 1}^{{\prime }}$ and $a_{t + 1}^{{\prime \prime }}$, i.e. $a_{t + 1} = \left\{ {a_{t + 1}^{{\prime }} ,a_{t + 1}^{{\prime \prime }} } \right\}$. Here the code of the state $a_{t + 1}^{{\prime }}$ coincides with the value of the input vector z _t , and the code of the state $a_{t + 1}^{{\prime \prime }}$ is formed by the combinational circuit CL_Φ on the basis of the input vector z _t and the code of the state a _t . Functioning of the class AE FSM can be described by means of following equations:

$$ \begin{aligned} a_{t + 1}^{{\prime }} & = z_{t} ; \\ a_{t + 1}^{{\prime \prime }} & =\Phi (z_{t} ,a_{t} ); \\ w_{t} & =\Psi (z_{t} ,a_{t} ). \\ \end{aligned} $$

3 The Synthesis Method of the Class AE FSM

Let us present the class AE FSM by the structural diagram on Fig. 3 that consists of two registers RG_A and RG_E, and the combinational circuit CL. Here, in contrast to the structure on Fig. 2, the combinational circuits CL_Φ and CL_Ψ are united in one circuit CL. The combinational circuit CL receives the values of the input variables $X = \{ x_{1} , \ldots ,x_{L} \}$, the values of the variables $G = \{ g_{1} , \ldots ,g_{L} \}$, which define the state $a_{t}^{{\prime }}$ code, and the values of the feedback variables $E = \{ e_{1} , \ldots ,e_{R} \}$, which define the state $a_{t}^{{\prime \prime }}$ code. Based on FSM algorithm functioning and arriving the values of the variables, the combinational circuit CL forms values of the output functions $Y = \{ y_{1} , \ldots ,y_{N} \}$ and the transition functions $D = \{ d_{1} , \ldots ,d_{R} \}$ which define the state $a_{t + 1}^{{\prime \prime }}$ code.

Fig. 3.

The structural diagram of the class AE FSM

Let A is a set of internal states of the FSM. Let us denote by U(a _i ) the set of all the transition conditions in the state $a_{i} , \, a_{i} \, \in \,A$:

$$ U\left( {a_{i} } \right){\text{\;=\;}}\{ X\left( {a_{m} ,a_{i} } \right)\left| {a_{m} \, \in \,B\left( {a_{i} } \right)\}} \right. , $$

(1)

where X(a _m , a _i ) is a collection of values of the input variables (a transition condition or an input vector) that initiates the transition from the state a _m to the state a _i , B(a _i ) is the set of states, transitions from which terminate in the state a _i .

The state $a_{i} , \, a_{i} \, \in \,A$, is a state of the class E FSM, i.e. $a_{i} \, \in \,A_{E} ,$ if next conditions are satisfied:

$$ \left| {U(a_{i} )} \right| = 1 $$

(2)

$$ U\left({a_{i} } \right) \cap U\left({a_{j}} \right) = \varnothing \,{\text{at}}\,i \ne j\,{\text{for}}\,{\text{all}}\,a_{j} \, \in \,A, $$

(3)

where |M| is the cardinality (the number of elements) of the set M, ∅ is an empty set.

A performance of the condition (2) guarantees that all transitions to the state a _i are carried out by the same transition condition (i.e. the state a_i has only one code), and a performance of the condition (3) provides a determinacy of a FSM behavior (i.e. the transition condition in some state a_i does not initiate passages to other FSM states).

The FSM is the class E FSM if all its states are states of the class E FSM, i.e. A _E  = A. In other words, the finite state machine is the class E FSM if for all its states conditions (2) and (3) are satisfied.

The satisfaction of the conditions (2) is carried out by splitting of FSM states. Let, for example, for some state $a_{i} , \, a_{i} \, \in \,A$, takes place |U(a _i )| = Q > 1. It is possible to split a state a _i on states $a_{{i_{\_}1}} , \ldots ,a_{{i_{\_}Q}}$ so that the transitions in each state a _{i_q} were defined only by one transition condition, i.e. was fulfilled |U(a _{i_q} )| = 1, $q = \overline{1,Q}$. Now instead of one state a_i, we have Q states for which conditions (2) are satisfied.

In case of violations of the conditions (3), the synthesis of the class E FSM is impossible, since the determinacy of the FSM behavior is broken. In this case, it is offered to use the combined model of the class AE FSM (Fig. 2). For this purpose, the second part of the code of the class A FSM is added to the code of each internal state of the class E FSM, which corresponds to the states $a_{t}^{{\prime \prime }}$ and $a_{t + 1}^{{\prime \prime }}$. The last is carried out by special state assignment of the FSM.

4 Splitting of Internal States for Performance of Necessary Conditions for Synthesis of the Class E FSM

Note that splitting the internal states is an equivalent transformation of the FSM and it does not change the operation algorithm of the FSM. Let M be the number of internal states of the FSM, P(a _i ) be the set of transitions of the FSM from the state $a_{i} , \, i = \overline{1,M}$, C(a _i ) be the set of transitions of the FSM that terminate in the state $a_{i} , \, a_{i} \, \in \,A$, and X(a _i ) be some a transition condition to the state a _i , X(a _i ) ∈ U(a _i ). Then the algorithm splitting of internal states for performance of necessary conditions for synthesis of the class E FSM has the following view.

Algorithm 1

• 1. For each internal state a _i , a _i ∈ A, according to (1) the set U(a _i ) is defined.

• 2. In the set A, find a state a _i for which condition (2) are not satisfied. If such a state is found, then go to Step 3; otherwise, go to Step 7.

• 3. Put Q: = |U(a _i )|. Introduce Q new states $a_{{i{\_}1}} , \ldots ,a_{{i{\_}Q}}$.

• 4. Determine the subsets $C(a_{{i{\_}1}} ), \ldots ,C(a_{{i{\_}Q}} )$ of transitions to the states $a_{{i{\_}1}} , \ldots ,a_{{i{\_}Q}}$. Each subset C(a _{i_q} ) is assigned transitions which is initiated by the condition X ^q (a _m , a _i ) ∈ U(a _i ), a _m ∈ B(a _i ), $q = \overline{1,Q}$.

• 5. The subsets $P(a_{{i{\_}1}} ), \ldots ,P(a_{{i{\_}Q}} )$ of transitions from the states $a_{{i{\_}1}} , \ldots ,a_{{i{\_}Q}}$ are determinated in the following way: P(a _{i_q} ) := P(a _i ) for all q = $\overline{1,Q}$.

• 6. Put $A: = A\backslash \left\{ {a_{i} } \right\},A: = A \cup \left\{ { \, a_{{i{{{\_}1}}}} , \ldots ,a_{{i{\_}Q}} } \right\},$ and M := M + Q − 1; go to Step 2.

• 7. Stop.

5 State Assignment of the Class AE FSM

The main purpose of encoding the internal states when designing the class AE FSMs is to ensure the mutual orthogonality of these codes. To encode the internal states of a class AE FSM, a ternary matrix W is constructed in which the rows correspond to the internal states and the columns correspond to the variables of the set G. A unit is put on intersection of the row i and the column j of the matrix W, if the input variable x _j has the value 1 in the condition X(a _i ), a zero, if the input variable x _j has the value 0 in the condition X(a _i ), and an undetermined value (the dash), if the variable x _j does not influence on the transition condition X(a _i ). Later, the rows of the matrix W will determine the codes of the internal states of the class AE FSM.

To make the codes of internal states of the class AE FSM orthogonal it is necessary to solve the following task.

Task 1.

To add in matrix W the minimum number of the columns, which corresponding to the variables $e_{ 1} ,\ldots ,e_{R}$ , and to encode the rows of the matrix W by binary values of the variables $e_{ 1} ,\ldots ,e_{R}$ so that all the rows of the matrix W were mutually orthogonal.

In order to solve the Task 1 and to encode the internal state of the class AE FSM the following algorithm is offered.

Algorithm 2

• 1. The graph H for the orthogonalization of the rows of the matrix W is constructed. The vertices of H correspond to the rows of W (internal states of the FSM). Two vertices of H are connected by an edge if the corresponding rows of W are orthogonal.

• 2. The vertices connected to all other vertices (the rows of W corresponding to these vertices are orthogonal to all other rows) are removed from H.

• 3. The graph H is decomposed into the minimum number of complete subgraphs $H_{1} , \ldots ,H_{T}$ using Algorithm 3.

• 4. The subgraphs $H_{1} , \ldots ,H_{T}$ are encoded by binary codes of the minimum length R = intlog ₂ T using Algorithm 5.

• 5. R columns that correspond to the variables $e_{ 1} ,\ldots ,e_{R}$ of the codes of the subgraphs $H_{1} , \ldots ,H_{T}$ are added to the matrix W. In row i of W, the positions of the additional columns are filled by the code of the subgraph H _t , $t = \overline{1,T}$, containing the vertex a _i , $i = \overline{1,M}$. The other positions of the additional columns in W are filled by zeros.

• 6. The contents of the row i of W is used as the code of the internal state a _i , $i = \overline{1,M}$.

• 7. Stop.

The decomposition of the graph H into the minimum number of complete graphs $H_{1} , \ldots ,H_{T}$ (at Step 3 of Algorithm 2) is made by the following algorithm.

Algorithm 3

• 1. Set T := 0.

• 2. Set T := T + 1. In the graph H, find a complete graph H _T with the maximum number of vertices.

• 3. Remove the vertices of H _T from the graph H.

• 4. If the set of vertices of H is not empty, the go to Step 2; otherwise, go to Step 5.

• 5. Stop.

The maximal complete subgraph H _t , $t = \overline{1,T}$, at Step 2 of Algorithm 3 can be found using the following algorithm.

Algorithm 4

• 1. Find a vertex a _i in H with the greatest local degree.

• 2. Include a _i into the graph H _t .

• 3. Among all the vertices of H not included in H _t , find a node a _i connected to all the nodes of the subgraph H _t . If several such nodes are found, choose a node with the greatest local degree among them.

• 4. If a vertex connected to all the vertices of the subgraph H _t was found at Step 3, then go to Step 2; otherwise, go to Step 5.

• 5. Stop.

To encode the subgraphs $H_{1} , \ldots ,H_{T}$ (Step 4 of Algorithm 2) the following algorithm is used to minimize the area of implementing the transition functions.

Algorithm 5

• 1. Calculate the length R of the codes of the subgraphs $H_{1} , \ldots ,H_{T}$: R = intlog ₂ T.

• 2. Form the set K of binary codes of length R.

• 3. The subgraph containing the initial state a ₁ is encoded by the zero code from K.

• 4. If all the subgraphs $H_{1} , \ldots ,H_{T}$ are encoded, then go to Step 5; otherwise, find among the not yet encoded subgraphs $H_{1} , \ldots ,H_{T}$ a subgraph H _t for which ∑|C(a _i )| = max for all a _i ∈ H _t .

  To encode the subgraph H _t , the code with the minimum number of unities is chosen in the set K. Go to Step 4.

• 5. Stop.

Example.

Let us apply the proposed method for designing the FSM described by the state diagram shown in Fig. 4. The vertices correspond to the internal states $a_{1} , \ldots ,a_{5}$ of this FSM, and the arcs correspond to the FSM transitions. Beside each arc, the value of the input vector that initiates the transition and, separated by a slash, the value of the output vector that formed on this transition are indicated. In this example, the FSM has five states, three input variables, and two output variables.

Fig. 4.

The state diagram of the initial FSM

In this example, conditions (2) are violated for the state a ₂ because U(a ₂ ) = {01-,--1}, i.e. |U(a ₂ )| = 2, therefore, a ₂ is split into two states a _{2_1} and a _{2_2}. The state diagram of the FSM obtained upon splitting the state a ₂ is shown in Fig. 5.

Fig. 5.

The state diagram of the FSM after splitting the state a ₂

The encoding of the internal states begins with constructing the matrix W (Table 1). Figure 6 shows the orthogonality graph H of the rows of W. The graph H is decomposed into two complete subgraphs H ₁ and H ₂. As the number of subgraphs T is equal 2, then one variable e ₁ has enough for coding of two subgraphs. According to Step 4 of algorithm 5, the subgraph H ₁ is encoded by binary code “1”, and the subgraph H ₂ is encoded by the code “0”. The matrix W with an additional column e ₁ for orthogonalization of rows is resulted in Table 2.

Table 1. The matrix W for state assignment of a class AE FSM

Fig. 6.

The graph H for orthogonality of rows of the matrix W

Table 2. The matrix W after orthogonalization of rows

The logical equations implemented by combinative circuit CL (Fig. 3) for our example have the following view:

$$ \begin{aligned} d_{1} & = g_{1} g_{2} \overline{e}_{1} ; \\ y_{1} & = \overline{g}_{3} e_{1} \overline{x}_{1} \overline{x}_{2} + \overline{g}_{1} g_{2} \overline{e}_{1} x_{1} \overline{x}_{2} + g_{3} e_{1} x_{1} \overline{x}_{2} ; \\ y_{2} & = \overline{g}_{3} e_{1} \overline{x}_{1} x_{2} + \overline{g}_{1} g_{2} \overline{e}_{1} \overline{x}_{1} \overline{x}_{2} + g_{3} e_{1} \overline{x}_{1} \overline{x}_{2} + g_{1} g{}_{2}\overline{e}_{1} x_{3} . \\ \end{aligned} $$

As it is possible to see from the resulted equations, the transition functions for the class AE FSM are very simple. The implementation cost of the given system of Boolean functions (it is traditionally defined as the number of inputs of the necessary for implementation gates) is equal 40, while at traditional implementation of the class A FSM, the implementation cost is equal 74. Thus, for the considered example usage of structural model of the class AE FSM, in comparison with the traditional approach, allowed to reduce the implementation cost by a factor of 1.85 or by 54%.

The efficiency of the proposed method for designing the class AE FSMs was tested by implementing the FSM described in the example above in the FPGAs manufactured by Altera using the CAD tools Quartus Prime version 16.0. It is the synthesis parameters by default of CAD Quartus were used. The initial FSM of class A and the synthesized FSM of class AE have been described in language Verilog.

Table 3 show the results of experiments for various FPGA families manufactured by the companies Altera, where LE _A and LE _AE are the numbers of the logical elements (functional generators LUT — look-up table) used in the implementation of the class A FSM and the class AE FSM, F _maxA and F _maxAE are the maximum operation frequencies (in MHz) of these FSMs, LE _A /LE _AE and F _maxAE /F _maxA are the ratio of the corresponding parameters, and mid is the mean value of the parameter. The data in Table 3 show that the proposed method for designing the class AE FSM reduced the implementation area of the FSM from the example on the Altera FPGAs by a factor of 1.35 on average and by a factor of 3.00 for the Arria II family. Thus the maximum operation frequency of the class AE FSM concedes to the maximum operation frequency of the class A FSM a little.

Table 3. Results of experimental researches at implementation on FPGA of the FSMs from the considered example

6 Experimental Study

The synthesis method of the class AE FSM was researched at implementation on FPGA for the FSM benchmarks MCNC [6]. For this purpose to each benchmark of the FSM the considered synthesis method was applied. Both finite state machines, the initial class A FSM and synthesized the class AE FSM, were described in language Verilog. Then standard implementation on FPGA of FSMs by means of CAD Quartus II version 13.1 was fulfilled. It is the synthesis parameters by default of CAD Quartus were used. As criteria of optimization the implementation cost (C), defined by the number of used logical elements LUT, and the maximum operation frequency (F) was considered.

In Tables 4 and 5, the parameter relations are presented for eleven FSM benchmarks for which usage of the synthesis method of the class AE FSM is the most effective. Here relation C _A /C _AE shows in how many time the synthesis method of the class AE FSM, in comparison with the class A FSM, improves the implementation cost; F _AE /F _A – the frequency.

Table 4. Results of experimental researches of the synthesis method of the class AE FSM for families Arria GX and Cyclone

Table 5. Results of experimental researches of the synthesis method of the class AE FSM for families MAX II and Stratix

The analysis of Tables 4 and 5 shows that the synthesis method of the class AE FSM allows to reduce a implementation cost by a factor of 3.00 for the benchmark shiftreg for all FPGA families, a time delay by a factor of 1.60 for the benchmark lion for family Cyclone, and an operation frequency by a factor of 2.93 for the benchmark train4 for family Stratix.

An average improving is of a cost by a factor from 1.19 (Cyclone, Stratix) to 1.39 (Arria, Stratix II, (III)), of a time delay – from 0.97 (Cyclone II) to 1.05 (Cyclone), of a frequency – from 1.92 (Cyclone II) to 1.10 (Stratix).

7 Conclusions

The considered method of synthesis of the class AE FSM showed the high efficiency at minimization of implementation cost of FSMs for various FPGA families, by a factor of 1.19–1.39 on average and by a factor of 3.00 for certain families. Besides, in certain cases the method allows to increase the FSM performance (by a factor of 2.93 for benchmark train4 for family Sratix). An application of the given method is the most effective for FSMs with the many of input variables, especially when the transitions in the various states are initiated by different transition conditions.

The proposed method for the minimization of FSMs based on the use of the structural model of the class AE FSM is universal because it is applicable to Mealy FSMs (i.e., to arbitrary FSMs), does not change the operational algorithm of the FSM, and is efficient for all FPGA families. Therefore, this method can be recommended for inclusion in industrial CAD tools in order to minimize the area of implementation. The given method can be used not only at implementation of FSMs on FPGA, but also on other an element basis, for example on ASIC (Application Specific Integrated Circuit). We see perspective a direction of the further researches when values of input and output variables of the FSM are shared for states assignment.