Mapping Outputs and States Encoding Bits to Outputs Using Multiplexers in Finite State Machine Implementations

Abstract

This paper proposes a new technique for implementing Finite State Machines (FSMs) in Field Programmable Gate Arrays (FPGAs). The proposed approach extends the called column compaction in two ways. First, it is applied to the state-encoding bits in addition to the outputs, allowing a reduction in the number of logic functions required both by the state transition function and by the output function. Second, the technique exploits the dedicated multiplexers usually included in FPGAs to increase the number of columns that can be compacted. Unlike conventional state-encoding techniques, the proposed approach reduces the number of logic functions instead of their complexity. An Integer Linear Programming (ILP) formulation that maximizes the number of compacted columns has been proposed. In order to evaluate the effectiveness of the proposed approach, experimental results using standard benchmarks are presented. In most cases, the proposed approach reduces the number of used Look-Up Tables (LUTs) with respect to the conventional FSM implementation.

1. Introduction

Finite State Machines (FSMs) are probably the most widely used component in digital design. They allow one to model any sequential circuit, particularly control units. Optimizing FSM implementations in terms of area, speed or power consumption is essential to meet the design constraints demanded by applications. For this reason, the synthesis of FSMs has received the attention of researchers, designers and EDA tool developers for decades [1,2,3,4]. One of the most active fields has been the encoding of the FSM states to achieve optimal implementations of the state transition and output functions [5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20].

Other techniques are focused on the optimal assignment of don’t care outputs, which are very usual because the values of some outputs do not matter in some states. The technique called column compaction exploits these don’t cares to reduce the number of logic functions that must be implemented [21,22,23,24,25]. The aim of this technique is to assign values of zero or one to the don’t cares in order to achieve that two or more outputs are equal to each other, and so only one logic function must be implemented for each group of equivalent outputs.

Our technique extends column compaction in two ways. First, it extends the concept of column compaction to the state-encoding bits. To the best knowledge of the authors’ knowledge, column compaction has never been applied to the state transition function. In addition to assign values to don’t cares to find equivalent outputs, our technique also encodes the states to achieve that some encoding bits are equal to some outputs. Therefore, it can be viewed as an extension of column compaction that is applied to the state transition function, in addition to the output function. This allows one to reduce the number of logic functions required to implement both functions. We will refer to the one-to-one correspondence between state-encoding bits and outputs as direct mapping of state-encoding bits. For analogy, column compaction will be referred to as direct mapping of outputs.

Second, the proposed technique exploits the dedicated 2:1 multiplexers usually included in Field Programmable Gate Arrays (FPGAs), which allow one to combine the outputs of two Look-Up Tables (LUTs) [26]. In order to reduce the number of LUTs used, the technique searches pairs of outputs that can be combined by means of dedicated multiplexers to generate the next state-encoding bits or other outputs. Therefore, the proposed technique also extends the concept of compaction to that of mapping via multiplexers. Each multiplexer is controlled by a bit of the present state. Due to the fact that the state-encoding bits are control inputs of the multiplexers and outputs of some of them, state encoding has a great influence on the results that can be obtained. Unlike conventional state-encoding techniques, the proposed approach reduces the number of logic functions instead of their complexity. Our technique is based on an Integer Linear Programming (ILP) formulation, which allows a solver to find the optimal mapping (or suboptimal, when the execution time is limited).

As a conclusion, the proposed technique uses three mechanisms to reduce the number of logic functions: direct mapping of outputs (i.e., column compaction), direct mapping of state-encoding bits and mapping via multiplexers, which are each modeled by a unique ILP formulation. Unlike the other two mechanisms, which are presented for the first time, column compaction is a classical technique. However, the novelty lies in the fact that it is based on a ILP formulation instead of heuristics [22], which allows one to obtain the optimal value, or in the worst case, to find a bound of the error corresponding to a non-optimal solution.

The remainder of this article is organized as follows. In Section 2, brief background about FSMs and FPGA devices is presented. Section 3 describes the fundamentals of the proposed technique and its architecture. Section 4 presents the proposed ILP formulation. Section 5 shows the obtained experimental results. Finally, conclusions are drawn in Section 6.

2. Background

Let $\mathcal{F}=(S,t,o,S_0)$ be a FSM, where S represents the set of states; $t:S\times {\{0,1\}}^r\to S$, the state transition function; $o:S\times {\{0,1\}}^r\to {\{0,1,-\}}^m$, the output function; and $S_0$, the reset state. The parameters r and m represent the numbers of inputs and outputs, respectively.

The State Transition Diagram (STD) is commonly used to show the behavior of a FSM. Figure 1 shows an example of FSM, whose STD is shown in Figure 1a. For a proper description of the proposed technique, it is more convenient to represent the FSM in the form of a State Transition Table (STT). As Figure 1b,c show, a STT is a table whose rows represent the transitions of the FSM as the 4-tuple $(in,ps,ns,out)$, where $in$ represents the inputs; $ps$, the present state; $ns$, the next state; and $out$, the outputs. The symbol “–” represents a don’t care value. A symbolic STT shows the states as symbols (see Figure 1b), whereas a codified STT shows the states once they have been codified (see Figure 1c).

FPGAs are semiconductor devices that are based around a matrix of Configurable Logic Blocks (CLBs) connected via programmable interconnects. In current Xilinx FPGA devices, each CLB is composed by two slices, and each one of them includes four LUTs. In addition, each slice includes three dedicated 2:1 multiplexers: two called F7 and one called F8. Each F7 combines the outputs of two LUTs whereas F8 combines the outputs of two F7s. Dedicated multiplexers can be used to create general-purpose functions of up to 13 inputs in 2 LUTs or 27 inputs in 4 LUTs (i.e., in one slice) [26].

3. Mapping Outputs and States Encoding Bits to Outputs by Means of Multiplexers

The aim of the proposed technique is to generate FSM outputs or the next state-encoding bits from FSM outputs without using extra LUTs. Both direct mapping and mapping via multiplexers are applied for this purpose. Mapping via multiplexers benefits from dedicated multiplexers, avoiding the use of extra LUTs. The advantage of direct mapping is that it allows one to reduce the number logic levels (i.e., to remove the logic levels corresponding to the dedicated multiplexers) and to improve the routing; therefore, this mapping can increase the speed. To sum up, including mapping via multiplexer allows one to find solutions with a more mapped signals. However, the proposed ILP formulation gives priority to direct mapping.

By exploiting the usual strong relationship between the transition and output functions, the proposed technique codifies the states to achieve that the maximum number of signals (whether outputs or state-encoding bits) are mapped. In addition to encode the states, the proposed technique assigns values to the don’t care outputs to achieve its objective. There is a key difference between the proposed technique and the conventional state-encoding approaches [5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20] that justifies its novelty. State-encoding algorithms assign a different code to each FSM state with the purpose of simplifying the complexity of the transition and output functions. On the other hand, the proposed approach reduces the number of logic functions instead of its complexity. Compared with the conventional state-encoding approaches, assigning don’t care outputs and codifying states in a non-optimal way in terms of function complexity can result in an increase in the number of LUTs required by each logic function. However, a reduction in the number of logic functions achieved by the proposed technique can compensate for such an increase, resulting in a lesser overall LUT count.

Figure 2 shows the general architecture to implement the FSMs obtained from the proposed technique. For simplicity, the signals generated from a single output (i.e., by applying direct mapping) have been excluded from the figure. The combinational block implements the logic corresponding to the unmapped bits of the next state and the unmapped outputs, so it partially implements the state transition and output functions. The mapped signals are generated from unmapped outputs by means of multiplexers controlled by a bit of the present state (which is not necessarily different from those of other multiplexers). The larger the number of mapped signals, the simpler the combinational block. This is due to the fact that the number of logic functions is reduced.

Figure 1c shows the STT of the FSM example (Figure 1b) after applying a mapping of state-encoding bits and outputs to outputs. After codifying the states and assigning some don’t care outputs, the next state-encoding bit $N_2$ can be mapped to outputs $O_1$ and $O_2$ by means of a multiplexer controlled by the present state-encoding bit $P_1$, which selects $O_1$ if $P_1=0$ and $O_2$ if $P_1=1$ (see Figure 1b,c). Note that Figure 1c shows in bold the don’t care outputs that have been assigned. Similarly, $O_5$ can be mapped to $O_3$ and $O_4$ by means of a multiplexer controlled by $P_2$, which selects $O_3$ if $P_2=0$ and $O_4$ if $P_2=1$. This mapping allows one to reduce the number of logic functions that must be implemented in LUTs from seven to five (see Figure 1d). By supposing LUTs of four inputs, the implementation obtained by the proposed technique requires five LUTs, whereas the conventional FSM implementation requires seven LUTs, independently of the state encoding used.

We define optimal mapping of outputs and state-encoding bits to outputs (OMOSEBO) as the problem of finding the mapping that maximizes the number of mapped signals (i.e., that minimizes the number of logic functions that are required to implement the output and state transition functions).

We have proposed an ILP formulation for this problem, which prioritizes direct mapping over mapping via multiplexers. Some constraints are imposed by the Xilinx FPGA architecture itself. As the output of each LUT is physically connected to a unique F7 multiplexer, routing the output of the LUT to a different multiplexer requires an additional LUT (called route-thru). F8 multiplexers present similar problems because the output of each F7 is physically connected to a unique F8 multiplexer. To prevent these situations, the ILP formulation must ensure that a FSM output cannot be used to generate more than one signal via multiplexer. However, although dedicated multiplexers F7 and F8 can be chained, allowing the multiplexing of up to four signals, we have limited our approach to a unique number of multiplexers to avoid increasing the complexity of the proposed ILP formulation. Therefore, the solver must exclude candidate solutions in which outputs mapped via multiplexers are inputs of other multiplexers.

4. Integer Linear Programming Formulation

Let $S=\{S_1,S_2,\dots ,S_e\}$ be the set of states of a FSM. Let us suppose that $O_i$ for $i=1,\dots ,m$ represents each output of the FSM. Let us consider the tuple $(T_1,T_2,\dots ,T_q)$, where $T_i\equiv (S_j,S_k)\in S\times S$, and $S_j$ and $S_k$ represent the present and next state, respectively, of the transition corresponding to i-th row of the STT. Let us consider that $P_i$ and $N_i$ represent the i-th encoding bit of the present and the next state, respectively. Let us suppose that $O_j^i\in \{0,1,-\}$ represents the value of the output $O_j$ for the transition corresponding to the i-th row of the STT.

The ILP formulation requires the following binary variables:

• $f_{i,j,k,r}$ for all $i,j,k,r$, which is equal to one if and only if $N_i$ can be generated from $O_j$ and $O_k$ via a multiplexer controlled by $P_r$ so that $N_i=O_j$ for all transitions in which $P_r=0$, and $N_i=O_k$ for the remaining ($N_i$ is therefore mapped to $O_j$ and $O_k$).
• $g_{i,j,k,r}$ for all $i,j,k,r$, which is equal to one if and only if $O_i$ can be generated from $O_j$ and $O_k$ via a multiplexer controlled by $P_r$ so that $O_i=O_j$ for all transitions in which $P_r=0$, and $O_i=O_k$ for the remaining ($O_i$ is therefore mapped to $O_j$ and $O_k$).
• $h_{i,j}$ for all $i,j$, which represents the value of the $O_j$ for the transition corresponding to the i-th row of the STT. Note that $h_{i,j}$ must be equal to $O_j^i$ for all $i,j$ such that $O_j^i\in \{0,1\}$ (i.e., $O_j^i$ is not a don’t care); however, the remainder values of $h_{i,j}$ will be determined by the solver.
• $c_{i,j}$ for all $i,j$, which represents the j-th bit of the encoding of $S_i$.
• $d_{i,j,k}$ for all $i,j,k$ such that $j<k$, which is equal to one if and only if i-th bit of the encoding of $S_j$ and that of $S_k$ are different.

Note that if $f_{i,j,j,r}=1$, then there exits a direct mapping of $N_i$ to $O_j$ (so the value of r is not relevant). Similarly, if $g_{i,j,j,r}=1$, then there exists a direct mapping of $O_i$ to $O_j$.

The objective of the OMOSEBO problem is to find a mapping of outputs and state-encoding bits that maximize the following tuple in lexicographical order:

$$\begin{array}{c}\hfill (\sum _{u,v,t,r}{f}_{u,v,t,r}+\sum _{\{w,v,t,r|v\ne t\}}{g}_{w,v,t,r}+\sum _{\{w,v,r|v>w\}}{g}_{w,v,v,r},\sum _{u,v,r}{f}_{u,v,v,r}+\sum _{\{w,v,r|v>w\}}{g}_{w,v,v,r})\end{array}$$

(1)

The first element allows one to maximize the number of mapped signals; the second one prioritizes the direct mapping over the mapping via multiplexer. The terms $g_{w,v,v,r}$ include only the cases in which $v>w$ to avoid counting twice one output directly mapped to another (e.g., if $g_{w,v,v,r}=1$ and $g_{v,w,w,r^{\prime }}=1$, then only $O_v$ or $O_w$ can be removed in the corresponding implementation).

Encoding e states requires $d=\lceil {log}_{2}e\rceil$ bits; therefore, $z=d+m$ is the total number of signals (either outputs or state-encoding bits). As ${\sum }_{u,v,t,r}{f}_{u,v,t,r}+{\sum }_{\{w,v,t,r|v\ne t\}}{g}_{w,v,t,r}+{\sum }_{\{w,v,r|v>w\}}{g}_{w,v,v,r}$ represent the number of mapped signals, it is obvious that ${\sum }_{u,v,t,r}{f}_{u,v,t,r}+{\sum }_{\{w,v,t,r|v\ne t\}}{g}_{w,v,t,r}+{\sum }_{\{w,v,r|v>w\}}{g}_{w,v,v,r}<z$. We use this property to define the weight $\alpha =1+\frac{1}{z}$ for the terms corresponding to direct mapping in order to model the multi-objective function. The ILP formulation of the OMOSEBO problem can be expressed as follows:

Maximize

$$\begin{array}{c}\hfill \sum _{\{u,v,t,r|v\ne t\}}{f}_{u,v,t,r}+\alpha \sum _{u,v,r}{f}_{u,v,v,r}+\sum _{\{w,v,t,r|v\ne t\}}{g}_{w,v,t,r}+\alpha \sum _{\{w,v,r|v>w\}}{g}_{w,v,v,r}\end{array}$$

(2)

subject to

$$\begin{array}{c}\hfill -f_{u,v,t,r}+c_{i,r}-h_{j,v}+c_{k,u}\ge -1\forall u,v,t,r,T_j\equiv (S_i,S_k)\end{array}$$

(3)

$$\begin{array}{c}\hfill f_{u,v,t,r}-c_{i,r}-h_{j,v}+c_{k,u}\le 1\forall u,v,t,r,T_j\equiv (S_i,S_k)\end{array}$$

(4)

$$\begin{array}{c}\hfill -f_{u,v,t,r}-c_{i,r}-h_{j,t}+c_{k,u}\ge -2\forall u,v,t,r,T_j\equiv (S_i,S_k)\end{array}$$

(5)

$$\begin{array}{c}\hfill f_{u,v,t,r}+c_{i,r}-h_{j,t}+c_{k,u}\le 2\forall u,v,t,r,T_j\equiv (S_i,S_k)\end{array}$$

(6)

$$\begin{array}{c}\hfill -g_{w,v,t,r}+c_{i,r}-h_{j,v}+h_{i,j,w}\ge -1\forall w,v,t,r,T_j\equiv (S_i,S_k)\end{array}$$

(7)

$$\begin{array}{c}\hfill g_{w,v,t,r}-c_{i,r}-h_{j,v}+h_{i,j,w}\le 1\forall w,v,t,r,T_j\equiv (S_i,S_k)\end{array}$$

(8)

$$\begin{array}{c}\hfill -g_{w,v,t,r}-c_{i,r}-h_{j,t}+h_{i,j,w}\ge -2\forall w,v,t,r,T_j\equiv (S_i,S_k)\end{array}$$

(9)

$$\begin{array}{c}\hfill g_{w,v,t,r}+c_{i,r}-h_{j,t}+h_{i,j,w}\le 2\forall w,v,t,r,T_j\equiv (S_i,S_k)\end{array}$$

(10)

$$\begin{array}{c}\hfill \sum _{v,t,r}{f}_{u,v,t,r}\le 1\forall u\end{array}$$

(11)

$$\begin{array}{c}\hfill \sum _{v,t,r}{g}_{w,v,t,r}\le 1\forall w\end{array}$$

(12)

$$\begin{array}{c}\hfill \sum _{\{u,t,r|t\ne v\}}{f}_{u,v,t,r}+\sum _{\{u,t,r|t\ne v\}}{f}_{u,t,v,r}+\sum _{\{w,t,r|t\ne v\}}{g}_{w,v,t,r}+\sum _{\{w,t,r|t\ne v\}}{g}_{w,t,v,r}\le 1\forall vs.\end{array}$$

(13)

$$\begin{array}{c}\hfill g_{w,w,t,r}=0\forall w,t,r\end{array}$$

(14)

$$\begin{array}{c}\hfill g_{w,t,w,r}=0\forall w,t,r\end{array}$$

(15)

$$\begin{array}{c}\hfill (g_{w,v,t,r}-1)m+\sum _{\{v^{\prime },t^{\prime },r^{\prime }|t^{\prime }\ne v^{\prime }\}}{g}_{v,v^{\prime },t^{\prime },r^{\prime }}\le 0\forall w,v,t\ne v,r\end{array}$$

(16)

$$\begin{array}{c}\hfill (g_{w,t,v,r}-1)m+\sum _{\{v^{\prime },t^{\prime },r^{\prime }|t^{\prime }\ne v^{\prime }\}}{g}_{v,v^{\prime },t^{\prime },r^{\prime }}\le 0\forall w,v,t\ne v,r\end{array}$$

(17)

$$\begin{array}{c}\hfill (f_{u,v,t,r}-1)m+\sum _{\{v^{\prime },t^{\prime },r^{\prime }|t^{\prime }\ne v^{\prime }\}}{g}_{v,v^{\prime },t^{\prime },r^{\prime }}\le 0\forall u,v,t\ne v,r\end{array}$$

(18)

$$\begin{array}{c}\hfill (f_{u,t,v,r}-1)m+\sum _{\{v^{\prime },t^{\prime },r^{\prime }|t^{\prime }\ne v^{\prime }\}}{g}_{v,v^{\prime },t^{\prime },r^{\prime }}\le 0\forall u,v,t\ne v,r\end{array}$$

(19)

$$\begin{array}{c}\hfill (g_{w,v,v,r}-1)z+\sum _{w^{\prime },v^{\prime },r^{\prime }}{g}_{w^{\prime },w,v^{\prime },r^{\prime }}+g_{w^{\prime },v^{\prime },w,r^{\prime }}+\sum _{u,v^{\prime },r^{\prime }}{f}_{u,w,v^{\prime },r^{\prime }}+f_{u,v^{\prime },w,r^{\prime }}\le 0\forall w,v,r\end{array}$$

(20)

$$\begin{array}{c}\hfill -d_{i,j,k}+c_{j,i}+c_{k,i}\ge 0\forall i,j,k\end{array}$$

(21)

$$\begin{array}{c}\hfill d_{i,j,k}+c_{j,i}+c_{k,i}\le 2\forall i,j,k\end{array}$$

(22)

$$\begin{array}{c}\hfill \sum _i{d}_{i,j,k}\ge 1\forall j,k\end{array}$$

(23)

$$\begin{array}{c}\hfill h_{i,j}=O_j^i\forall i,j|O_j^i\in \{0,1\}\end{array}$$

(24)

Constraints (3)–(6) ensure that the mapping is coherent with the transition function. Constraints (3) and (4) are the result of the linearization of the following constraint:

$$\begin{array}{c}\hfill f_{u,v,t,r}=1\wedge c_{i,r}=0\Rightarrow c_{k,u}=h_{j,v}\forall u,v,t,r,T_j\equiv (S_i,S_k)\end{array}$$

(25)

For each transition $T_j\equiv (S_i,S_k)$, if $P_r=0$ (i.e., the r-th bit of the encoding of the present state, $S_i$, is equal to 0), then the multiplexer connects $O_v$ to $N_u$; therefore, the u-th bit of the coding of the next state, $S_k$, must be equal to the value of the output $O_v$. Similarly, for the cases in which $P_r$ = 1, (5) and (6) are obtained from the following constraint:

$$\begin{array}{c}\hfill f_{u,v,t,r}=1\wedge c_{i,r}=1\Rightarrow c_{k,u}=h_{j,t}\forall u,v,t,r,T_j\equiv (S_i,S_k)\end{array}$$

(26)

Constraints (7)–(10) guarantee the coherence with the output function. Constraints (7) and (8) are obtained by the linearization of the following constraint:

$$\begin{array}{c}\hfill g_{w,v,t,r}=1\wedge c_{i,r}=0\Rightarrow h_{j,w}=h_{j,v}\forall w,v,t,r,T_j\equiv (S_i,S_k)\end{array}$$

(27)

If $P_r=0$, then the multiplexer connects $O_v$ to $O_w$; therefore, they must be equal to each other. Similarly, for the cases in which $P_r=1$, (9) and (10) are obtained from the following constraint:

$$\begin{array}{c}\hfill g_{w,v,t,r}=1\wedge c_{i,r}=1\Rightarrow h_{j,w}=h_{j,t}\forall w,v,t,r,T_j\equiv (S_i,S_k)\end{array}$$

(28)

Constraints (11) and (12) ensure that the state-encoding bits and the outputs, respectively, are not mapped more than once (see Figure 3a,b). Constraint (13) guarantees that any output cannot be used to generate more than one signal by means of a multiplexer, whether a state-encoding bit or an output (see Figure 3c). Constraints (14) and (15) prevent that an output is mapped to itself (see Figure 3d).

Constraints (16) and (17) are the results of the linearization of the constraints

$$\begin{array}{c}\hfill g_{w,v,t,r}=1\Rightarrow \sum _{v^{\prime },t^{\prime }\ne v^{\prime },r^{\prime }}{g}_{v,v^{\prime },t^{\prime },r^{\prime }}=0\forall w,v,t\ne v,r\end{array}$$

(29)

and

$$\begin{array}{c}\hfill g_{w,t,v,r}=1\Rightarrow \sum _{v^{\prime },t^{\prime }\ne v^{\prime },r^{\prime }}{g}_{v,v^{\prime },t^{\prime },r^{\prime }}=0\forall w,v,t\ne v,r\end{array}$$

(30)

respectively. They prevent that an output generated from others via a multiplexer is used to map an output using a multiplexer (see Figure 4a). Similarly, (18) and (19) are obtained by linearization of the constraints

$$\begin{array}{c}\hfill f_{u,v,t,r}=1\Rightarrow \sum _{v^{\prime },t^{\prime }\ne v^{\prime },r^{\prime }}{g}_{v,v^{\prime },t^{\prime },r^{\prime }}=0\forall u,v,t\ne v,r\end{array}$$

(31)

and

$$\begin{array}{c}\hfill f_{u,t,v,r}=1\Rightarrow \sum _{v^{\prime },t^{\prime }\ne v^{\prime },r^{\prime }}{g}_{v,v^{\prime },t^{\prime },r^{\prime }}=0\forall u,v,t\ne v,r\end{array}$$

(32)

respectively. They prevent the mapping of a state-encoding bit in the circumstances described above (see Figure 4b).

Constraint (20) is obtained from constraint

$$\begin{array}{c}\hfill g_{w,v,v,r}=1\Rightarrow \sum _{w^{\prime },v^{\prime },r^{\prime }}{g}_{w^{\prime },w,v^{\prime },r^{\prime }}+g_{w^{\prime },v^{\prime },w,r^{\prime }}+\sum _{u,v^{\prime },r^{\prime }}{f}_{u,w,v^{\prime },r^{\prime }}+f_{u,v^{\prime },w,r^{\prime }}=0\forall w,v,r\end{array}$$

(33)

which prevents an output directly mapped to another being used to generate a third signal (either an output or a state-encoding bit). Figure 4c,d show the cases of outputs and state-encoding bits, respectively. The aim of these constraints is to prevent that a direct mapping leads to the situations shown in Figure 4e, despite constraints from (16) to (19). It might be thought that (20) prevents some valid solutions. For example, supposing that $O_v$ is not a mapped output, the implementation shown on the left of Figure 4c could be valid if it is not prevented by (20), allowing that $O_w$ and $O_{w^{\prime }}$ are mapped outputs. However, the solver will find the following equivalent solution (which do is allowed): $O_v$ and $O_v^{\prime }$ generate $O_w^{\prime }$ via the multiplexer, and $O_v$ also generates $O_w$.

Finally, (21)–(23) guarantee the code assigned to each state is different from the other ones. Constraints (21) and (22) ensure that the i-th bit of the encoding of $S_j$ is different from the i-th bit of the encoding of $S_k$ if $d_{i,j,k}=1$; that is,

$$\begin{array}{c}\hfill d_{i,j,k}=1\Rightarrow c_{j,i}\ne c_{k,i}\forall i,j,k\end{array}$$

(34)

Constraint (23) guaranties that any pair of states, $S_j$ and $S_k$, differ at least in one bit.

Constraint (24) assigns the values of the outputs that are not don’t care values, and thus they cannot be determined by the solver.

5. Experimental Results

OMOSEBO has been evaluated using FSMs of the MCNC benchmark set [27]. The number of states of these FSMs were previously minimized by STAMINA [28]. All designs were synthesized and implemented using Xilinx Vivado Design Suite 2022.1 in a Spartan-7 FPGA (xc7s6cpga196-2). Therefore, the results include the delay of the placement-and-routing stage. In order to evaluate the effectiveness of OMOSEBO, the implementations obtained using this technique were compared to the corresponding conventional FSM implementations (which will be called CONV). CONV implementations were generated using the template for FSMs of Vivado (see Figure 5, which shows the VHDL code for implementing the FSM example using the FSM template). The proposed ILP formulation was implemented using the API of Gurobi [29] for Python and solved with a time limit of 4 hours. The optimization was carried out on an Intel i7-10700K at 3.80 GHz with 16 GB of RAM. The HDL description generated after the optimization process uses a modified version of the FSM template that included a standard description of multiplexors (see Figure 6, which shows the VHDL code for implementing the FSM example by applying OMOSEBO). As the aim of OMOSEBO is to improve the area, Vivado was configured for area optimization using the preconfigured strategies Flow_AreaOptimized_high and Area_Explore for synthesis and implementation, respectively.

Table 1. Implementation results.

	CONV		OMOSEBO		Comparison
FSM	# LUTs	Freq.	# LUTs	Freq.	LUT Red.	Freq. Inc.
		(MHz)		(MHz)	(%)	(%)
s1	78	358	32	430	59	20
mark1	26	443	15	592	42	34
s27	7	649	5	693	29	7
planet	104	406	85	438	18	8
opus	17	567	14	665	18	17
s510	58	461	50	440	14	−5
s820	77	389	68	396	12	2
ex1	70	415	63	407	10	−2
ex6	20	643	18	627	10	−2
styr	103	376	95	348	8	−7
ex4	15	742	14	716	7	−4
cse	41	426	41	472	0	11
s832	76	379	85	382	−12	1
keyb	40	357	46	348	−15	−3
mc	3	907	4	851	−33	−6
Mean	49	501	42	520	11	5

shows the number of LUTs and the maximum clock frequency (in MHz) obtained by CONV and OMOSEBO. In addition, the columns “LUT Red.” and “Freq. Inc.” show the area reduction and the speed increment, respectively, obtained by OMOSEBO with respect to CONV; thus, positive values correspond to the cases in which the proposed approach was successful (in column “LUT Red.”, these values are shown in bold).

In 53% of cases, the time limit was reached. In half of these cases, the gap (i.e., the measure that indicates how long the obtained solution is from the optimal) was more than 50%. Therefore, the results could be improved using more time.

OMOSEBO required a lesser number of LUTs than CONV in 73% of cases. The average LUT reduction was 11%; however, if only the successful cases are taken into account, this value increases to 21%. Although OMOSEBO reduced the number of logic functions in all cases, there were three FSMs (20% of the sample) in which the number of used LUTs was greater than that obtained by CONV. This is due to the fact that OMOSEBO encodes the states to reduce the number of logic functions, whereas CONV encodes the states to simplify the logic functions, and so there may be cases in which the increase in complexity of the logic functions does not compensate for fewer functions. In addition, the don’t care outputs assigned by OMOSEBO may make the simplification process performed by Vivado more difficult.

Regarding the maximum clock frequency, the results do not show a clear correlation between LUT reduction and speed increment (the correlation coefficient is 0.69). Nevertheless, although the goal of the proposed technique is to reduce the area, in the 55% of cases in which the OMOSEBO reduced the area, it also increased the speed, obtaining an average speed increment of 15% for such cases. In order to study the relationship between speed increment and area reduction, we obtained the regression line (see Figure 7). Although area and speed usually are conflicting goals, in general terms, the area reduction obtained by OMOSEBO was achieved without degrading the speed; in fact, the regression line shows that the area reduction has a positive impact on the increase in speed.

In order to show the improvement that OMOSEBO represents with respect to conventional column compaction [22], we applied that technique to all studied FSMs. For that, we added the following constraints to the proposed ILP formulation:

$$\begin{array}{cc}\hfill f_{u,v,t,r}& =0\forall u,v,t,r\hfill \end{array}$$

(35)

$$\begin{array}{cc}\hfill g_{w,v,t,r}& =0\forall w,v,t,r|t\ne vs.\hfill \end{array}$$

(36)

The constraint (35) prevents the mapping of state bits to outputs. Similarly, (36) prevents the mapping of outputs to outputs via multiplexers. Therefore, only direct mapping of outputs (i.e., column compaction) is allowed.

The impact of column compaction with respect to the solutions found by OMOSEBO, which also includes direct mapping of next state bits and mapping via multiplexers, is very limited. Although the optimal value was reached in all cases, column compaction reduced the number logic functions only in four cases. In the remaining 11 cases, the reduction was due exclusively to direct mapping of next state bits and/or to mapping via multiplexers. Even in those four cases, the number of logic functions obtained by OMOSEBO was less than that of column compaction for two of them (a 17% and a 27% less for keyb and mark1, respectively), and equal for the two others (s820 and s832).

6. Conclusions

In this paper, OMOSEBO, a new technique for implementing FSMs in FPGAs, has been presented. It can be viewed as an extension of column compaction that is applied to the state transition function in addition to the output function. Moreover, OMOSEBO also extends the concept of compaction to that of mapping via multiplexers. Therefore, the proposed technique uses three mechanisms to reduce the number of logic functions: direct mapping of outputs (i.e., column compaction), direct mapping of state-encoding bits and mapping via multiplexers, which are modeled by a unique ILP formulation. Unlike conventional state-encoding techniques, in which states are encoded to simplify the state transition and output functions, OMOSEBO reduces the number of required logic functions.

In order to evaluate the effectiveness of OMOSEBO, experimental results using standard benchmarks have been presented. Regarding column compaction, unlike other similar approaches, the proposed ILP formulation allows one to find optimal solutions. Despite that, in 11 of the 15 studied cases, the reduction in the number of logic functions is due exclusively to direct mapping of next state bits and/or mapping via multiplexers, whereas only in 2 of the studied cases, the reduction is due exclusively to column compaction. In conclusion, OMOSEBO represents a significant improvement over column compaction.

The FSM implementations obtained by applying OMOSEBO have been compared to conventional FSM implementations. The results show that OMOSEBO reduces the number of used LUTs with respect to the conventional implementation in 73% of cases.