A New Approach for Implementing Finite State Machines with Input Multiplexing
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. T...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-09-01
|
| Series: | Electronics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2079-9292/12/18/3763 |
| _version_ | 1797580467133743104 |
|---|---|
| author | Ignacio Garcia-Vargas Raouf Senhadji-Navarro |
| author_facet | Ignacio Garcia-Vargas Raouf Senhadji-Navarro |
| author_sort | Ignacio Garcia-Vargas |
| collection | DOAJ |
| description | 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 <i>k</i>-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. |
| first_indexed | 2024-03-10T22:51:22Z |
| format | Article |
| id | doaj.art-96d7fcff0e01489c94153f429fa1e833 |
| institution | Directory Open Access Journal |
| issn | 2079-9292 |
| language | English |
| last_indexed | 2024-03-10T22:51:22Z |
| publishDate | 2023-09-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Electronics |
| spelling | doaj.art-96d7fcff0e01489c94153f429fa1e8332023-11-19T10:21:01ZengMDPI AGElectronics2079-92922023-09-011218376310.3390/electronics12183763A New Approach for Implementing Finite State Machines with Input MultiplexingIgnacio Garcia-Vargas0Raouf Senhadji-Navarro1Department of Computer Architecture and Technology, University of Seville, 41012 Seville, SpainDepartment of Computer Architecture and Technology, University of Seville, 41012 Seville, SpainThe 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 <i>k</i>-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.https://www.mdpi.com/2079-9292/12/18/3763Finite State MachineFinite State Machine with Input MultiplexingFPGAEmbedded Memory BlockROMInteger Linear Programming |
| spellingShingle | Ignacio Garcia-Vargas Raouf Senhadji-Navarro A New Approach for Implementing Finite State Machines with Input Multiplexing Electronics Finite State Machine Finite State Machine with Input Multiplexing FPGA Embedded Memory Block ROM Integer Linear Programming |
| title | A New Approach for Implementing Finite State Machines with Input Multiplexing |
| title_full | A New Approach for Implementing Finite State Machines with Input Multiplexing |
| title_fullStr | A New Approach for Implementing Finite State Machines with Input Multiplexing |
| title_full_unstemmed | A New Approach for Implementing Finite State Machines with Input Multiplexing |
| title_short | A New Approach for Implementing Finite State Machines with Input Multiplexing |
| title_sort | new approach for implementing finite state machines with input multiplexing |
| topic | Finite State Machine Finite State Machine with Input Multiplexing FPGA Embedded Memory Block ROM Integer Linear Programming |
| url | https://www.mdpi.com/2079-9292/12/18/3763 |
| work_keys_str_mv | AT ignaciogarciavargas anewapproachforimplementingfinitestatemachineswithinputmultiplexing AT raoufsenhadjinavarro anewapproachforimplementingfinitestatemachineswithinputmultiplexing AT ignaciogarciavargas newapproachforimplementingfinitestatemachineswithinputmultiplexing AT raoufsenhadjinavarro newapproachforimplementingfinitestatemachineswithinputmultiplexing |