A New Approach for Implementing Finite State Machines with Input Multiplexing

Citation: Garcia-Vargas, I.; Senhadji-Navarro, R. A New Approach for Implementing Finite State Machines with Input Multiplexing. Electronics 2023,12, 3763. https://doi.org/10.3390/ electronics12183763 Academic Editors: Dariusz Kania, Alexander Barkalov, Remigiusz Wi´sniewski and Larysa Titarenko Received: 28 July 2023 Revised: 1 September 2023 Accepted: 4 September 2023 Published: 6 September 2023 Copyright: © 2023 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https:// creativecommons.org/licenses/by/ 4.0/). electronics Article A New Approach for Implementing Finite State Machines with Input Multiplexing Ignacio Garcia-Vargas *,† and Raouf Senhadji-Navarro † Department of Computer Architecture and Technology, University of Seville, 41012 Seville, Spain; [email protected] *Correspondence: [email protected] †These authors contributed equally to this work. Abstract: The model called Finite State Machine with Input Multiplexing (FSMIM) was proposed as a mechanism for implementing Finite State Machines (FSMs) using ROM memory. This paper presents a novel approach for achieving more efficient FSMIM implementations in Field Programmable Gate Array (FPGA) devices. The aim of the proposed approach is to obtain further reductions in the use of Embedded Memory Blocks (EMBs). Unlike previous works, the proposed approach reduces the depth of the ROM by grouping states before simplifying the input selectors of the FSMIM. For this purpose, a new strategy for grouping states is proposed, and its optimality is proven. In addition, a new variant of the Minimum Maximal k -Partial Matching (MMKPM) problem and its corresponding Integer Linear Programming (ILP) formulation are proposed for simplifying input selectors. The proposed approach requires a significantly smaller number of EMBs than the approaches proposed previously . Keywords: Finite State Machine; Finite State Machine with input multiplexing; FPGA; Embedded Memory Block; ROM; Integer Linear Programming; Minimum Maximal k-Partial-Matching 1. Introduction Researchers have devoted significant attention to the optimization of Finite State Machine (FSM) implementations regarding area, speed, or power consumption over decades [ 1 – 8 ]. Current Field Programmable Gate Array (FPGA) devices include Embedded Memory Blocks (EMBs), which allow, among other elements, the implementation of ROM memory. Therefore, the output and transition functions of an FSM can be mapped into EMBs. The advantages of these implementations, called ROM-based FSM implementations, are the following: (1) if FSMs are mapped into non-used EMBs, the saved Lookup Tables (LUTs) can be used for implementing other components of the system [ 9 ]; (2) when the implementation of the function using LUTs requires a considerable number of logic levels, the speed can be increased by mapping the function on EMBs [ 10 , 11 ]; and (3) the EMBs used to implement the FSM can be disabled during the idle states, achieving a substantial reduction in power consumption [12]. However, when FSMs are mapped directly into ROM memory (we will refer to these implementations as conventional ROM-based FSM implementations), the size of the memory increases exponentially with the size of the ROM address, which is composed of the state encoding bits and the FSM inputs. Consequently, small FSMs may require more memory than that available in the FPGA device. Developing techniques that reduce memory usage without considerably increasing LUT usage is already a challenge. In the literature, various techniques have been proposed to reduce the number of required EMBs [ 4 , 9 – 11 , 13 ]. These techniques enable a more efficient utilization of the FPGA resources, striking an appropriate balance between EMB and LUT usage. Most of these techniques employ functional decomposition [ 4 , 9 , 13 ] or structural decomposition [ 11 , 14 ]. In this scope, the model called FSM with Input Multiplexing (FSMIM) was proposed to reduce the number of ROM words required to map the FSM transitions [ 10 ]. Depending Electronics 2023,12, 3763. https://doi.org/10.3390/electronics12183763 https://www.mdpi.com/journal/electronics Electronics 2023,12, 3763 2 of 17 on whether the focus is on reducing EMBs or LUTs, two distinct architectures have been proposed: FSMIM with transition-based input selection (FSMIM-T) and FSMIM with statebased input selection (FSMIM-S) [ 10 ]. Both types of implementation use a combinational circuit, called Input Selector Bank (ISB), to select a different subset of the FSM inputs for each state, allowing for reducing the ROM memory. The optimization process proposed in [ 15 ] consists of two stages. In the first one, called Input Selector Simplification (ISS), the ISB is simplified with the aim of saving LUTs (which can also allow it to increase its speed). The optimization process employed in the ISS stage is modeled as a variant of the Minimum Maximal k-Partial-Matching (MMKPM) problem [ 16 ] and solved using an Integer Linear Programming (ILP) formulation [ 15 ] or a greedy algorithm [ 16 ]. In the second stage, known as State Grouping (SG), the memory depth is further reduced beyond the capabilities of the ISB alone. Other researchers have recently used the FSMIM model in their work [17,18]. To summarize, the key contributions of this paper are as follows: • A new approach to generate FSMIMs from conventional FSMs is proposed with the aim of obtaining further reductions in EMB usage. • Unlike previous approaches [10,15], the SG stage is applied before the ISS stage. • A new strategy for the SG stage that obtains optimal solutions in terms of grouping states is proposed. • The ILP formulation proposed in [ 15 ] for the ISS stage is extended in order to maintain coherence with the results obtained by the SG stage. • We present a thorough experimental study comparing the new approach with the one proposed in [15]. The remaining sections of the paper are structured as follows: Backgrounds on ROM-based implementations and, particularly, FSMIM implementations are presented in Section 2. In Section 3, a new approach for generating FSMIMs from conventional FSMs is proposed. In Section 4, the experimental results are presented and analyzed. Finally, the main conclusions are highlighted in Section 5. 2. Background 2.1. Conventional ROM-Based Implementation The conventional architecture for implementing FSMs into ROM memory is shown in Figure 1a, where p , m , and n are the number of state encoding bits, the number of inputs, and the number of outputs, respectively. By supposing that Ns is the number of states, the number of encoding bits is calculated as p=dlog2Nse . Although there exists a specific architecture for Moore machines, in this work, we have considered a general architecture that allows to implementation of both Mealy and Moore machines [ 11 ]. Moreover, since current FPGAs include synchronous EMBs, FSM outputs are synchronized by the clock. Each word of the ROM block, which is implemented using EMBs, contains the next state and the FSM outputs of an FSM transition. Therefore, the ROM width is equal to n+p bits.The FSM inputs and the present state encoding bits form the ROM address. Thus, the maximum ROM depth is equal to 2 m+p words, i.e., the maximum ROM size increases exponentially with m and p . If all the states are encoded with codes in the interval [0, Ns) , then the ROM depth is equal to 2mNs≤2m+pwords. The exponential increase in the ROM depth not only has an impact on area but also on speed. The memory access time is degraded as the number of EMBs required to implement the ROM increases. The reasons for this behavior are the following: (1) the routing overhead and (2) the delay imposed by the LUTs used to connect the outputs of the EMBs whenever the ROM depth is greater than the maximum depth of the EMBs. Electronics 2023,12, 3763 3 of 17 GROUP ENCODER out ROM in m n p out m n r m' INPUT SELECTOR BANK in in ROM out INPUT SELECTOR BANK n m' (a) p' m p' p ROM (b) (c) Figure 1. ROM-based FSM architectures: (a) conventional, (b) FSMIM-T, and (c) FSMIM-S. 2.2. Finite State Machine with Input Multiplexing The FSMIM technique reduces the depth of the memory of conventional ROM-based FSM implementations by decreasing both the number of FSM inputs that address the ROM ( m ) and the number of states ( Ns ). The consequent reduction in the number of required EMBs is achieved at the expense of using LUTs. In FSMIM architectures (see Figure 1b,c), the ROM is addressed using, for each state, only the subset of FSM inputs that have an influence on its behavior (which are called effective inputs). In both architectures, the combinational circuit ISB selects the effective inputs of the present state. The ISB has m inputs (the FSM inputs) and m0 outputs (the selected inputs); then, the ROM depth can be reduced if m0<m . Obviously, the value of m0 is determined by the state with the greatest number of effective inputs. Given a state with e<m0 effective inputs, the m0−e inputs that are not effective can be considered as don’t care signals (which are referred to as Don’t Selected Inputs (DCSIs)). In FSMIM architectures, the DCSIs can be exploited to form groups of states that can share the same state code. Therefore, in the ROM address, the code of the present state can be replaced by the code of the group to which it belongs. As a consequence, the ROM depth is reduced to 2 m0Ng words, where Ng<Ns represents the number of groups. This allows a reduction in the ROM depth even in FSMs in which there exist states that respond to all FSM inputs (i.e., in which m0=m). By supposing that the groups can be codified with p0=dlog2Nge bits, the ROM address requires m0+p0 bits; therefore, the ROM depth is reduced with respect to conventional ROM-based implementations by Ns 2 m−Ng 2 m0 words, which not only reduces the memory requirement but also the memory access time of the ROM (despite the fact that speed is not considered as a goal of the FSMIM technique). There exist two different architectures for implementing FSMIMs, namely, FSMIM-T (see Figure 1b) and FSMIM-S (see Figure 1c). In both architectures, the selection of the effective inputs is performed by the called input selectors. In the FSMIM-T architecture (see Figure 1b), the ISB is composed of multiplexers, so its implementation can greatly benefit from the embedded multiplexers available in many FPGA devices [ 19 , 20 ]. For each transition, the ROM stores the bits that control the multiplexers (called selection bits), the FSM outputs, and, instead of the next state, the encoding bits of the next group. By supposing that the number of selection bits is r , the ROM width is (r+p0+n) bits, which is greater than the width of the conventional ROM-based implementations. In the FSMIM-S architecture (see Figure 1c), each ROM word contains the same information as in the conventional ROM-based implementations (i.e., contains the next state encoding bits and FSM outputs). Therefore, unlike FSMIM-T, FSMIM-S can reduce the depth of the ROM without increasing its width. However, the number of LUTs required by the corresponding implementation increases due to the following reasons. First, the multiplexers of FSMIM-T use the minimum number of selection bits. However, the ISB of Electronics 2023,12, 3763 4 of 17 FSMIM-S uses the present-state encoding bits as selection bits, increasing the complexity of the corresponding logic functions. Second, as the ROM of FSMIM-S stores the next state instead of the next group, the architecture requires an extra combinational component (called Group Encoder) to generate the present group from the present state, which has p inputs and p0outputs. In conclusion, we can say the FSMIM-T architecture should be used when the LUT usage and speed are critical, whereas FSMIM-S should be used when the number of available EMBs is limited [10]. 2.3. Generation of FSMIMs from FSMs An approach to generate FSMIMs from FSMs was presented in [ 15 ] with the objective of enabling efficient FSMIM implementations in terms of LUT and EMB usage. The Input Selection Matrix (ISM) [ 10 ], which can be considered an abstraction of the ISB, is used to describe the optimization problems arising in the generation of FSMIMs. In the ISM, rows and columns represent states and input selectors, respectively. The effective inputs of each state are represented by a different row, and each column represents the set of FSM inputs that can be selected by an input selector. More formally, let S={s1 , s2 , . . . , sq} be the set of states, X={x1 , x2 , . . . , xm} the set of FSM inputs, and k the maximum number of effective inputs. Then, an ISM is defined as a matrix, A= (ai,j)∈ Mq×k , where ai,j∈X∪ { 0, 1, −} is the input selected by the input selector, j , for the state, si . The selected input can be a constant value in addition to an FSM input or a don’t care. To indicate the correspondence between ISM rows and states, the ISM can include a supplementary column that specifies the state name associated with each row. Different ISMs, which determine different FSMIM implementations, can be obtained from the same FSM. For example, see the two ISMs shown in Figure 2a. A=           x3x4x1s1 −x6x3s2 x2x5−s3 −x1−s4 −x4−s5 x1− − s6 x5− − s7           AISS =           x1x4x3s1 x6−x3s2 x2x5−s3 x1− − s4 −x4−s5 x1− − s6 −x5−s7           (a) (b) ASG 1=           x1x4x3s1 x6−x3s2 x2x5−s3 x1− − s4 0x4−g57 x1− − s6 1x5−g57           ASG 2=           x1x4x3s1 x60x3g24 x2x5−s3 x11−g24 0x4−g57 x1− − s6 1x5−g57           ASG 3=           x1x4x3g1={s1} x60x3g24 x2x50g357 x11−g24 0x41g357 x1− − g6={s6} 1x51g357           (c) Figure 2. Example of FSMIM generation: ( a ) Input Selector Simplification, ( b ) second input selector for the FSMIM-T architecture (R1 2and R0 2are the selection bits), and (c) State Grouping. The approach presented in [ 15 ] is divided into two stages: the first one is the ISS stage, which is intended to simplify the ISB, and the second one is the SG stage, which groups the states to reduce the ROM depth. Given an FSM, the two stages process the corresponding ISM in sequence: the ISS stage permutes the elements of ISM rows; then, the SG stage assigns constant values. The ISM produced by the SG stage determines the implementation of the generated FSMIM. 2.3.1. ISS Stage The primary objective of the ISS stage is the reduction in LUT count by simplifying the ISB. Moreover, the critical path often includes the ISB, especially in FSMIM-T imple- Electronics 2023,12, 3763 5 of 17 mentations; therefore, reducing the complexity of the ISB can also improve the speed of the corresponding implementations. As the selectors with fewer inputs need generally fewer LUTs, the ISB complexity can be estimated as the total number of inputs of the selectors. This measure, which is called selection cost, is calculated as the sum of the number of distinct values in each column of the ISM. Since the complexity of the ISB in FSMIM-T is determined exclusively by the number of inputs of their selectors (i.e., their multiplexers), it correlates directly with the selection cost. However, in FSMIM-S, this correlation is weaker because the complexity of the involved logic functions depends on other factors in addition to input count (e.g., the states encoding). Given an FSMIM, permuting the elements within each row of the corresponding ISM defines an equivalent FSMIM, the transitions of which are allocated in different ROM words. This operation over an ISM is called a permutation. The ISS stage finds the permutation of the ISM that minimizes the selection cost (i.e., the sum of the input count of each selector of the ISB). In the example of Figure 2a, AISS is a permutation of A in which the input count of the ISB is reduced in the following way: from 4 to 3 for the first selector, from 4 to 2 for the second one, and from 2 to 1 for the last one (see columns 1, 2, and 3, respectively). In [ 15 ], the ISS stage is modeled as a problem called MMKPM with minimum selection cost, number of selection bits, and DCSI dispersion (MMKPM-SSD), which is a variant of the MMKPM problem [ 16 ]. MMKPM-SSD is described in terms of a bipartite graph obtained from an ISM without constant values (the constant values are added by the SG stage, which is applied after the ISS stage). Given an ISM A= (ai,j)∈ Mq×k , where ai,j∈X∪ {−} , a bipartite graph, G= (R∪X , E) , is defined in which the rows of A are represented by R={ 1, . . . , q} and the FSM inputs by X . Each edge of E⊆R×X maps a row of A to its effective inputs. A set of edges in G without common rows is referred to as a partial-matching, and a collection of k partial-matchings P={P1 , . . . , Pk} is referred to as k -partial-matching. A k -partial-matching is maximal if it defines a partition of E . Each partialmatching of a maximal k -partial-matching represents a different column of A because it selects one input from each row (or none if it is a DCSI). Therefore, any permutation of A can be represented by a maximal k -partial-matching, where Pi determines the inputs of column i . A low dispersion of DCSIs in the ISM columns (i.e., a high concentration of DCSIs in few columns) benefits the SG stage, which is applied after the ISS stage. The DCSI dispersion, in addition to the selection cost and the number of selection bits, can be calculated from a maximal k-partial-matching [15]. The objective of the MMKPM-SSD problem is to find a maximal k -partial-matching with minimum selection cost, minimum number of selection bits, and minimum DCSI dispersion (in that order of priority). An ILP formulation to solve the MMKPM-SSD problem was also proposed in [15]. 2.3.2. SG Stage Given an ISM, A= (ai,j)∈ Mq×k , and a state, s∈S , the domain of s , denoted by δ(s)⊆Bk , is defined as the set of values that the selected inputs of s can take. Obviously, if no constant values are selected for a state, then its domain is equal to Bk . For example, in the ISM AISS of Figure 2, δ(s4) = B3 . However, the assignment of constant values to the DCISs of a state reduces the cardinality of its domain. For example, if both DCSIs of s4 are assigned to 0, then δ(s4) = {(0, 0, 0),(1, 0, 0)} . The cardinality of the domain of a state, s , satisfies that 2ws≤ |δ(s)| ≤ 2k(1) where wsis the number of effective inputs of the state, s. The ROM address is formed by the present-state encoding bits and k input signals. Hence, each state code is associated with 2 k ROM words. However, the set of ROM addresses in which the state transitions are allocated is determined by the state encoding bits and their domain. Therefore, if the domains of a group of states are disjoint, then the states in the group can be encoded with the same code and share the 2 k addresses Electronics 2023,12, 3763 6 of 17 associated with such code, which allows for reducing the depth of the ROM (hereinafter, these groups of states will simply be called groups). The SG stage reduces the depth of the ROM by grouping states. For each group, the SG stage finds an assignment of constant values that ensures the domains of its states are disjoint. For example, in Figure 2, the group, g24 , in ASG 2 can be used to identify the states, s2 and s4 (see AISS 2 ), because their domains differ in the value of the second column. We will say that s2 and s4 are merged into the group g24 ={s2 , s4} . With this assignment of constant values, whenever the present state is g24 , the transitions of s2 or s4 can be addressed by selecting in the second input selector the values 0 or 1, respectively. Therefore, in the corresponding state transitions, the next state, s2 , must be substituted by g24 with input selection (x6 , 0, x3) , whereas s3 must be substituted by g24 with (x1 , 1, −) . For example, Figure 2b shows the multiplexer that implements the second input selector for FSMIM-T. The assignment of constant values may have a negative effect on the speed and area of FSMIM Implementations. In FSMIM-T, the number of selection bits grows, which increases the number of LUTS (due to the increase in the complexity of the multiplexers) and the number of EMBs (due to the increase in the width of the ROM). In FSMIM-S, the number of EMBs is not affected because the ROM width does not depend on the selection cost; however, the number of LUTs does increase due to the increased complexity of the logic functions that implement the ISB, which have fewer don’t care outputs. Consequently, the SG stage must stop forming groups when the number of EMBs can no longer be reduced. The algorithm presented in [ 15 ] for the SG stage is called a EMB-granularity-based SG algorithm (hereinafter, simply, SG algorithm (SGA)). It starts from an ISM without constant values, in which each state forms a separate group; therefore, the initial number of groups is equal to the number of states. The ISM columns are processed iteratively. At each step of the algorithm, two groups are merged by assigning constant values to the DCSIs of the processed column; then, the number of required EMBs is estimated from the resulting ISM. If the number of EMBs decreases, the ISM is selected as a candidate solution. The processing of the column continues until no more groups can be merged; then, the algorithm proceeds with the next column. After processing all columns, the final candidate solution is considered the best solution. That is, among all the solutions found with the smallest number of EMBs, the best one is the solution with the largest number of groups, as it has the least negative impact on speed and area. An example of the application of SGA is shown in Figure 2(where ASG l represents the result of processing column l by applying SGA to AISS ). First, s5 and s7 are merged into g57 ={s5 , s7} by setting the DCSIs of the first column (see ASG 1 ). Then, the algorithm processes the second column and merges s2 and s4 into g24 ={s2 , s4} (see ASG 2 ). Finally, during the processing of the third column, s3 and g57 are merged into g357 ={s3 , s5 , s7} by fixing the DCSI of s3 to 0 and all DCSIs of g57 to 1 (see ASG 3 ). This is possible because all rows of g57 and s3 have a DCSI in the third column. In contrast, although g24 has a DCSI in the third column, it also has an effective input; therefore, it cannot be merged with s6 . The final set of groups is G={g1 , g24 , g357 , g6}={{s1} , {s2 , s4} , {s3 , s5 , s7} , {s6}} ; then, the number of groups is reduced from 7 to 4. Note that the set of groups obtained by SGA is always a partition of S. 3. Proposed Approach to Generate FSMIMs from FSMs By applying the ISS stage before the SG stage, the approach proposed in [ 15 ] for generating FSMIM implementations gives priority to the simplification of the input selectors over state grouping. As a consequence, in general, the ROM depth (and, thus, the number of used EMBs) cannot be reduced as much as possible. With the aim of further reducing the number of EMBs, this paper presents a new approach that prioritizes state grouping, which requires, among other things, applying SG before ISS. Depending on the FSMIM architecture, the new approach consists of two or three stages. In FSMIM-S, the approach applies an initial SG stage followed by an ISS stage. However, FSMIM-T requires that an additional SG stage be applied after ISS. Electronics 2023,12, 3763 7 of 17 3.1. Proposed SG Stage The number of groups obtained by SGA depends on the positions of DCSIs in the ISM. However, the minimum number of groups only depends on the number of effective inputs of each state. Given an ISM, A= (ai,j)∈ Mq×k , the set of groups, G={g1 , . . . , gt} , obtained by SGA verifies that ∑s∈S2ws 2k≤ |G|(2) where wsis the number of effective inputs of s. Proof. Let us define the domain of a group, g⊆S , as ∆(g) = ∪s∈gδ(s)⊆Bk . By construction, the domains of any pair of states of a group, g∈G , are disjoint. Then, |∆(g)|=| ∪s∈gδ(s)|=∑s∈g|δ(s)|. Therefore, using (1), we have that ∑ s∈g 2ws≤ |∆(g)| ≤ 2k(3) Since Gis a partition of Sand (3) is satisfied, then ∑s∈S2ws 2k=&∑t i=1∑s∈gi2ws 2k'≤&∑t i=1|∆(gi)| 2k'≤t=|G| In the approach presented in [ 15 ], the SG stage starts from the ISM generated by the previous ISS stage. In general, the placement of the DCSIs in the ISM is not optimal due to the permutations performed by the ISS stage; therefore, the SG stage cannot reach the minimum number of groups. For example, in Figure 2c, the final number of groups obtained by the SG algorithm is 4 (see ASG 3 ); however, the minimum number of groups is l23+22+22+21+21+21+21 23m=3. Unlike previous work, the proposed method starts with an SG stage, which permutes the elements of each ISM row to find an optimal distribution of the DCSIs. This permutation, called initial SG permutation, moves the DCSIs to the last columns of each row. More formally, given an ISM, A= (ai,j)∈ Mq×k , the initial SG permutation arranges the elements of each row of A in such a way that all ai,j , ai,l∈A satisfy that j<l if ai,j is not a DCSI and ai,l is a DCSI. It can be proven that SGA reaches the minimum number of groups when it is applied to the resultant ISM of the initial SG permutation. Figure 3shows the application of the proposed initial SG stage to the FSMIM of Figure 2, where Aπ is obtained by applying the initial SG permutation to A. Aπ=           x3x4x1g1 x6x3−g2 x2x5−g3 x1− − g4 x4− − g5 x1− − g6 x5− − g7           where gi={si} Aπ 1=AπAπ 2=           x3x4x1g1 x6x3−g2 x2x5−g3 x10−g45 x41−g45 x10−g67 x51−g67           Aπ 3=           x3x4x1g1 x6x30g23 x2x51g23 x10 0 g4567 x41 0 g4567 x10 1 g4567 x51 1 g4567           Figure 3. Initial SG stage applied to the FSMIM example of Figure 2. Electronics 2023,12, 3763 8 of 17 Lemma 1. Let Aπ= (ai,j)∈ Mq×k be the ISM obtained by the initial SG permutation; Gπ 0={{s1}, . . . {sq}} be the initial set of groups; and Gπ l be the set of groups obtained by SGA after the l-th column of Aπis processed. For all 1≤l≤k, it holds that |Gπ l|=&cl+|Gπ l−1| 2'(4) where clis the number of effective inputs in column l. Proof. Let Aπ l−1= (ai,j)∈Mq×k be the ISM obtained after the column l− 1 is processed. Gπ l is obtained by assigning constant values to the l -th column of Aπ l−1 and by merging the groups of Gπ l−1 . For example, in Figure 3, Gπ 3 (see the last column of Aπ 3 ) is obtained by assigning constant values to column 3 of Aπ 2. Let us suppose that ai,l is an effective input (i.e., it is not a DCSI). Then, due to the initial SG permutation, ai,r is also an effective input for all r<l . This implies that the group, g∈Gπ l−1 , related to row i could not be merged with other groups during the processing of previous columns. Thus, it contains exclusively one state ( si ). In addition, it cannot be merged with other groups during the processing of column l . We will refer to these groups as isolated groups of Gπ l−1 . For example, in Figure 3, the unique isolated group of Gπ 2 is g1 because it has the unique effective input in the third column of Aπ 2 ; the remaining groups are non-isolated. The number of isolated groups of Gπ l−1 is equal to the number of effective inputs in column l (i.e., equal to cl ). Then, the number of non-isolated groups is |Gπ l−1| − cl . As the non-isolated groups have a DCSI in column l of each one of their rows, they can be merged by pairs during the processing of column l . Therefore, the final number of groups of Gπ l is |Gπ l|=cl+&|Gπ l−1| − cl 2'=&cl+|Gπ l−1| 2' Proposition 1. SGA reaches the minimum number of groups determined by (2) when it is applied to Aπ. Proof. Rewriting (2) in terms of ISM rows instead of states and taking into account that the final number of groups is that obtained after processing the last column (i.e., the k -th column), it must be proven that |Gπ k|=&∑q i=12wi 2k'(5) where wiis the number of effective inputs of state si. Let w(r) i be the number of effective inputs in the first r columns of row i of Aπ . Due to the initial SG permutation, for all r> 1, w(r) i is equal to either w(r−1) i (if ai,r is a DCSI) or w(r−1) i+ 1 (if ai,r is an effective input). Therefore, the number of effective inputs in column r, with r>1, can be calculated as cr=∑q i=1w(r) i−w(r−1) i. As wi=w(k) i, the proposition is proven if |Gπ r|=    ∑q i=12w(r) i 2r    (6) is satisfied for all r=1, . . . , k, which will be proven by induction. Electronics 2023,12, 3763 9 of 17 For r= 1, as c1 is the number of effective inputs in column 1, we have c1 rows with w(1) i= 1 and q−c1 rows with w(1) i= 0. Then, ∑q i=1 2 w(1) i= 2 1c1+ (q−c1) 2 0=c1+q= c1+|Gπ 0|. Therefore,     ∑q i=12w(1) i 2    =c1+|Gπ 0| 2 which is equal to |Gπ 1|using (4). For the inductive step, let us suppose that (6) is true for |Gπ r|. Using (4), |Gπ r+1|=cr+1+|Gπ r| 2 = d cr+1+ d ∑q i=12w(r) i 2r e 2 e = d d 2rcr+1+∑q i=12w(r) i 2r e 2 e = d 2rcr+1+∑q i=12w(r) i 2r+1 e = d 2r∑q i=1w(r+1) i−w(r) i+∑q i=12w(r) i 2r+1 e = d ∑q i=12rw(r+1) i−w(r) i+2w(r) i 2r+1 e Using the initial SG permutation, we have two possibilities for each row, i . If ai,r+1 is a DCSI, then w(r+1) i=w(r) i . Thus, 2 rw(r+1) i−w(r) i+ 2 w(r) i= 2 w(r) i= 2 w(r+1) i . If ai,r+1 is an effective input, then w(r) i=r and w(r+1) i=r+ 1. Hence, 2 rw(r+1) i−w(r) i+ 2 w(r) i= 2 r+ 2 r= 2 r+1= 2 w(r+1) i . In both cases, it holds that 2 rw(r+1) i−w(r) i+ 2 w(r) i= 2 w(r+1) i ; therefore, |Gπ r+1|=    ∑q i=12w(r+1) i 2r+1    Thus, the proposition is proven. By applying the initial SG stage to the ISM A of Figure 2, the set of groups obtained is Gπ 3={g1 , g23 , g4567}={{s1} , {s2 , s3} , {s4 , s5 , s6 , s7}} (see the last column of Aπ 3 in Figure 3); therefore, SGA reaches the minimum number of groups, which is 3, using (2). The optimization process for the FSMIM-S architecture is composed of two stages: the initial SG stage followed by the new ISS stage. As explained above, the initial SG stage first applies the initial SG permutation and then SGA, which takes into account the number of EMBs required by each candidate solution (see Section 2.3.2). Unlike the old ISS stage, which does not manage ISMs with constant values, the new one takes into account the existence of the previously created groups. Thus, only permutations that do not affect such groups are allowed. However, in FSMIM-T, the ROM width is overestimated during the initial SG stage due to the fact that the selection cost is not minimized until the subsequent ISS stage. As a consequence, SGA cannot carry out an accurate estimation of the number of EMBs. To solve this problem, the optimization process uses three stages: (1) the initial SG stage, in which SGA is applied with the EMB estimation disabled (thus, the algorithm obtains the Electronics 2023,12, 3763 16 of 17 5. Conclusions A new approach for generating FSMIMs from conventional FSMs, called SG-ISS, was proposed with the aim of obtaining further reductions in the number of required EMBs. Unlike previous approaches [ 10 , 15 ], the SG stage is applied before the ISS stage. For this, a new strategy for the SG stage that obtains optimal solutions in terms of grouping states was proposed. In addition, the ILP formulation proposed in [ 15 ] for the ISS stage was extended in order to maintain coherence with the results obtained in the SG stage. A comparison study between the new approach and that proposed in [15] was presented. The results show that the SG-ISS significantly reduces the number of EMBs without a considerable increase in the number of LUTs. Thus, the proposed SG-ISS approach can be an alternative to that proposed in [ 15 ] (called the ISS-SG approach) when saving EMBs is critical. We can, therefore, conclude that SG-ISS and ISS-SG can be considered complementary approaches, which, along with the two ISS strategies (ILP and Greedy) and the two FSMIM architectures (FSMIM-T and FSMIM-S), provide eight different design alternatives. These alternatives were evaluated by analyzing the average EMB reduction, LUT reduction, and speed increment in each design alternative with respect to the worst case. From this study, we can conclude that the SG-ISS approach and the FSMIM-S architecture should be used when reducing memory usage is a priority and the speed is not critical. On the other hand, the ISS-SG approach and the FSMIM-T architecture should be used when saving LUTs is the primary objective. With respect to the ISS strategy, the greedy algorithm provides a good trade-off between result quality and computation time (in addition to no solver being required). Therefore, it is a good choice when the design requirements are not very demanding. On the other hand, the ILP formulation could be used when the requirements are not met using the greedy algorithm. An Electronic Design Automation (EDA) tool incorporating the proposed design alternatives could select one of them, considering the design requirements and the effort level specified by the designer. Author Contributions: Conceptualization, R.S.-N. and I.G.-V.; Methodology, R.S.-N. and I.G.-V.; Software, R.S.-N. and I.G.-V.; Validation, R.S.-N. and I.G.-V.; Formal analysis, R.S.-N. and I.G.-V.; Investigation, R.S.-N. and I.G.-V.; Writing—original draft, R.S.-N. and I.G.-V.; Writing—review & editing, R.S.-N. and I.G.-V. All authors have read and agreed to the published version of the manuscript. Funding: This research received no external funding. Acknowledgments: We would like to thank Gurobi for providing us with a free academic license to carry out this research. Conflicts of Interest: The authors declare no conflict of interest. References 1. Barkalov, A.; Titarenko, L. Logic Synthesis for FSM-Based Control Units; Springer International Publishing: Cham, Switzerland, 2009; Volume 53. [CrossRef] 2. Klimowicz, A.S.; Solov’ev, V.V. Structural Models of Finite-State Machines for Their Implementation on Programmable Logic Devices and Systems on Chip. J. Comput. Syst. Sci. Int. 2015,54, 230–242. [CrossRef] 3. Kubica, M.; Kania, D. Technology Mapping of FSM Oriented to LUT-Based FPGA. Appl. Sci. 2020,10, 3926. [CrossRef] 4. Rawski, M.; Selvaraj, H.; Luba, T. An application of functional decomposition in ROM-based FSM implementation in FPGA devices. In Proceedings of the Euromicro Symposium on Digital System Design, Belek-Antalya, Turkey, 3–5 September 2003; pp. 104–110. 5. El-Maleh, A.; Sait, S.; Nawaz Khan, F. Finite state machine state assignment for area and power minimization. In Proceedings of the 2006 IEEE International Symposium on Circuits and Systems, ISCAS 2006, Kos, Greece, 21–24 May 2006. 6. Janarthanan, A.; Tiwari, A.; Tomko, K. Power-efficient FSM mapping in FPGAs through SEMB dormancy control. In Proceedings of the 50th Midwest Symposium on Circuits and Systems, MWSCAS 2007, Montreal, QC, Canada, 5–8 August 2007; pp. 502–505. 7. Mengibar, L.; Entrena, L.; Lorenz, M.; Millan, E. Partitioned state encoding for low power in FPGAs. Electron. Lett. 2005 , 41, 948–949. [CrossRef] 8. Sklyarov, V. Reconfigurable models of finite state machines and their implementation in FPGAs. J. Syst. Archit. 2002 ,47, 1043–1064. [CrossRef] Electronics 2023,12, 3763 17 of 17 9. Borowik, G.; Falkowski, B.; Luba, T. Cost-Efficient Synthesis for Sequential Circuits Implemented Using Embedded Memory Blocks of FPGA’s. In Proceedings of the IEEE Design and Diagnostics of Electronic Circuits and Systems, DDECS’07, Kraków, Poland, 11–13 April 2007; pp. 1–6. 10. Garcia-Vargas, I.; Senhadji-Navarro, R. Finite State Machines With Input Multiplexing: A Performance Study. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 2015,34, 867–871. [CrossRef] 11. Barkalov, A.; Titarenko, L.; Kolopienczyk, M.; Mielcarek, K.; Bazydlo, G. Design of EMB-Based Mealy FSMs; Springer International Publishing: Cham, Switzerland, 2016; pp. 193–237. 12. Tiwari, A.; Tomko, K. Saving power by mapping finite-state machines into embedded memory blocks in FPGAs. In Proceedings of the Design, Automation and Test in Europe Conference and Exhibition, Paris, France, 16–20 February 2004; Volume 2, pp. 916–921. 13. Selvaraj, H.; Rawski, M.; Luba, T. FSM implementation in embedded memory blocks of programmable logic devices using functional decomposition. In Proceedings of the International Conference on Information Technology: Coding and Computing, Las Vegas, NV, USA, 8–10 April 2002; pp. 355–360. [CrossRef] 14. Barkalov, A.; Titarenko, L.; Krzywicki, K. Structural Decomposition in FSM Design: Roots, Evolution, Current State—A Review. Electronics 2021,10, 1174. [CrossRef] 15. Garcia-Vargas, I.; Senhadji-Navarro, R. Optimization based on the minimum maximal k-partial-matching problem of finite states machines with input multiplexing. Des. Autom. Embed. Syst. 2022,26, 83–103. [CrossRef] 16. Garcia-Vargas, I.; Senhadji-Navarro, R. The minimum maximal k-partial-matching problem. Optim. Lett. 2013 ,7, 1959–1968. [CrossRef] 17. Das, N.; Priya, P.A. FPGA Implementation of an Improved Reconfigurable FSMIM Architecture Using Logarithmic Barrier Function Based Gradient Descent Approach. Int. J. Reconfigurable Comput. 2019,2019, 3727254. [CrossRef] 18. Mardani Kamali, H.; Zamiri Azar, K.; Homayoun, H.; Sasan, A. SCRAMBLE: The State, Connectivity and Routing Augmentation Model for Building Logic Encryption. In Proceedings of the 2020 IEEE Computer Society Annual Symposium on VLSI (ISVLSI), Limassol, Cyprus, 6–8 July 2020; pp. 153–159. 19. Xilinx. 7 Series FPGAs Configurable Logic Block: User Guide; Xilinx: San Jose, CA, USA , 2016. 20. Altera. Advanced Synthesis Cookbook; Altera: San Jose, CA, USA, 2011. 21. Gurobi Optimization. Gurobi Optimizer Reference Manual. 2020. Available online: http://www.gurobi.com (accessed on 1 September 2023). Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.