{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,24]],"date-time":"2025-07-24T11:53:33Z","timestamp":1753358013491,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,6,1]],"date-time":"2022-06-01T00:00:00Z","timestamp":1654041600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,6,2]],"date-time":"2022-06-02T00:00:00Z","timestamp":1654128000000},"content-version":"vor","delay-in-days":1,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100009042","name":"Universidad de Sevilla","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100009042","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Des Autom Embed Syst"],"published-print":{"date-parts":[[2022,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Finite State Machines with Input Multiplexing (FSMIMs) were proposed in previous work as a technique for efficient mapping Finite State Machines (FSMs) into ROM memory. In this paper, we present new contributions to the optimization process involved in the implementation of FSMIMs in Field Programmable Gate Array (FPGA) devices. This process consists of two stages: (1) the simplification of the bank of input selectors of the FSMIM, and (2) the reduction of the depth of the ROM. This has a significant impact both on the number of used Look-Up Tables (LUTs) and on the number of the Embedded Memory Blocks (EMBs) required by the ROM. For the first stage, we present two approaches to optimize FSMIM implementations based on the Minimum Maximal <jats:italic>k<\/jats:italic>-Partial Matching (MMKPM) problem: one of them applies the greedy algorithm for the MMKPM problem, and the other based on a new multiobjetive variant of the MMKPM and its corresponding Integer Linear Programing formulation. We also propose a modification of the second stage, in which the characteristics of EMBs are taken into account to improve implementation results. The new optimization process significantly reduces the number of used FPGA resources with respect to the previous one. In addition, the proposed approaches achieve an adequate trade-off between the usage of EMBs and LUTs with respect to conventional FSM implementations based on ROM and to those based on LUT.\n<\/jats:p>","DOI":"10.1007\/s10617-022-09259-z","type":"journal-article","created":{"date-parts":[[2022,6,2]],"date-time":"2022-06-02T19:02:16Z","timestamp":1654196536000},"page":"83-103","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Optimization based on the minimum maximal k-partial-matching problem of finite states machines with input multiplexing"],"prefix":"10.1007","volume":"26","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8420-8770","authenticated-orcid":false,"given":"Ignacio","family":"Garcia-Vargas","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2838-9367","authenticated-orcid":false,"given":"Raouf","family":"Senhadji-Navarro","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,6,2]]},"reference":[{"key":"9259_CR1","doi-asserted-by":"crossref","unstructured":"Barkalov A, Titarenko L (2009) Logic synthesis for FSM-based control units, vol 53. Springer, Heidelberg, Berlin","DOI":"10.1007\/978-3-642-04309-3_3"},{"issue":"2","key":"9259_CR2","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1134\/S1064230715010074","volume":"54","author":"AS Klimowicz","year":"2015","unstructured":"Klimowicz AS, Solov\u2019ev VV (2015) Structural models of finite-state machines for their implementation on programmable logic devices and systems on chip. J Comput Syst Sci Int 54(2):230\u2013242. https:\/\/doi.org\/10.1134\/S1064230715010074","journal-title":"J Comput Syst Sci Int"},{"issue":"11","key":"9259_CR3","doi-asserted-by":"publisher","first-page":"3926","DOI":"10.3390\/app10113926","volume":"10","author":"M Kubica","year":"2020","unstructured":"Kubica M, Kania D (2020) Technology mapping of FSM oriented to LUT-based FPGA. Appl Sci 10(11):3926. https:\/\/doi.org\/10.3390\/app10113926","journal-title":"Appl Sci"},{"key":"9259_CR4","unstructured":"Rawski M, Selvaraj H, Luba T (2003) Digital system design, 2003. In: Proceedings. Euromicro Symposium on (2003), pp 104\u2013110"},{"key":"9259_CR5","unstructured":"El-Maleh A, Sait S, Nawaz Khan F (2006) Circuits and systems, 2006. In: ISCAS 2006. Proceedings. 2006 IEEE international symposium on (2006), p 4"},{"key":"9259_CR6","doi-asserted-by":"crossref","unstructured":"Janarthanan A, Tiwari A, Tomko K (2007) Circuits and systems, 2007. In: MWSCAS 2007. 50th midwest symposium on (2007) pp 502\u2013505","DOI":"10.1109\/MWSCAS.2007.4488635"},{"issue":"17","key":"9259_CR7","doi-asserted-by":"publisher","first-page":"948","DOI":"10.1049\/el:20052307","volume":"41","author":"L Mengibar","year":"2005","unstructured":"Mengibar L, Entrena L, Lorenz M, Millan E (2005) Partitioned state encoding for low power in FPGAs. Electron Lett 41(17):948\u2013949. https:\/\/doi.org\/10.1049\/el:20052307","journal-title":"Electron Lett"},{"key":"9259_CR8","doi-asserted-by":"publisher","first-page":"1043","DOI":"10.1016\/S1383-7621(02)00067-X","volume":"47","author":"V Sklyarov","year":"2002","unstructured":"Sklyarov V (2002) Reconfigurable models of finite state machines and their implementation in FPGAs. J Syst Archit 47:1043\u20131064","journal-title":"J Syst Archit"},{"key":"9259_CR9","unstructured":"Borowik G, Falkowski B, Luba T (2007) Design and diagnostics of electronic circuits and systems, 2007. DDECS \u201907. IEEE, pp 1\u20136"},{"key":"9259_CR10","unstructured":"Garcia-Vargas I, Senhadji-Navarro R, Jimenez-Moreno G, Civit-Balcells A, Guerra-Gutierrez P (2007) Industrial electronics, 2007. In: ISIE 2007. IEEE international symposium on (2007), pp 2342\u20132347"},{"key":"9259_CR11","doi-asserted-by":"crossref","unstructured":"Barkalov A, Titarenko L, Kolopienczyk M, Mielcarek K, Bazydlo G (2016) Design of EMB-based Mealy FSMs. Springer, Heidelberg, Berlin, pp 193\u2013237","DOI":"10.1007\/978-3-319-24202-6_7"},{"key":"9259_CR12","unstructured":"Tiwari A, Tomko K (2004) Design, automation and test in Europe conference and exhibition, 2004. Proceedings, vol\u00a02, pp 916\u2013921"},{"issue":"20","key":"9259_CR13","doi-asserted-by":"publisher","first-page":"1249","DOI":"10.1049\/el:20046007","volume":"40","author":"R Senhadji-Navarro","year":"2004","unstructured":"Senhadji-Navarro R, Garcia-Vargas I, Jimenez-Moreno G, Civit-Ballcels A (2004) ROM-based FSM implementation using input multiplexing in FPGA devices. Electron Lett 40(20):1249\u20131251","journal-title":"Electron Lett"},{"issue":"5","key":"9259_CR14","doi-asserted-by":"publisher","first-page":"867","DOI":"10.1109\/TCAD.2015.2406859","volume":"34","author":"I Garcia-Vargas","year":"2015","unstructured":"Garcia-Vargas I, Senhadji-Navarro R (2015) Finite state machines with input multiplexing: a performance study. IEEE Trans Comput Aided Des Integr Circuits Syst 34(5):867\u2013871. https:\/\/doi.org\/10.1109\/TCAD.2015.2406859","journal-title":"IEEE Trans Comput Aided Des Integr Circuits Syst"},{"key":"9259_CR15","doi-asserted-by":"publisher","unstructured":"Selvaraj H, Rawski M, Luba T(2002) Proceedings. International conference on information technology: coding and computing, pp 355\u2013360. https:\/\/doi.org\/10.1109\/ITCC.2002.1000415","DOI":"10.1109\/ITCC.2002.1000415"},{"key":"9259_CR16","doi-asserted-by":"publisher","DOI":"10.3390\/electronics10101174","author":"A Barkalov","year":"2021","unstructured":"Barkalov A, Titarenko L, Krzywicki K (2021) Structural decomposition in FSM design: roots, evolution, current state-a review. Electronics. https:\/\/doi.org\/10.3390\/electronics10101174","journal-title":"Electronics"},{"key":"9259_CR17","doi-asserted-by":"publisher","DOI":"10.1155\/2019\/3727254","author":"N Das","year":"2019","unstructured":"Das N, Priya PA (2019) FPGA implementation of an improved reconfigurable FSMIM architecture using logarithmic barrier function based gradient descent approach. Int J Reconfigurable Comput. https:\/\/doi.org\/10.1155\/2019\/3727254","journal-title":"Int J Reconfigurable Comput"},{"key":"9259_CR18","unstructured":"Mardani Kamali H, Zamiri Azar K, Homayoun H, Sasan A (2020) 2020 IEEE computer society annual symposium on VLSI (ISVLSI)"},{"issue":"8","key":"9259_CR19","doi-asserted-by":"publisher","first-page":"1959","DOI":"10.1007\/s11590-012-0531-3","volume":"7","author":"I Garcia-Vargas","year":"2013","unstructured":"Garcia-Vargas I, Senhadji-Navarro R (2013) The minimum maximal k-partial-matching problem. Optim Lett 7(8):1959\u20131968. https:\/\/doi.org\/10.1007\/s11590-012-0531-3","journal-title":"Optim Lett"},{"key":"9259_CR20","unstructured":"Senhadji-Navarro R, Garcia-Vargas I, Guisado J (2012) Electronics, circuits and systems (ICECS). In: 2012 19th IEEE international conference on (2012), pp 225\u2013228"},{"key":"9259_CR21","unstructured":"Xilinx (2016) 7 series FPGAs configurable logic block: user guide"},{"key":"9259_CR22","unstructured":"Altera (2011) Advanced synthesis cookbook"},{"key":"9259_CR23","first-page":"2864","volume":"43","author":"T Yamada","year":"2002","unstructured":"Yamada T, Kataoka S, Watanabe K (2002) Heuristic and exact algorithms for the disjunctively constrained knapsack problem. Inf Process Soc Jpn J 43:2864\u20132870","journal-title":"Inf Process Soc Jpn J"},{"issue":"2","key":"9259_CR24","doi-asserted-by":"publisher","first-page":"233","DOI":"10.7155\/jgaa.00186","volume":"13","author":"U Pferschy","year":"2009","unstructured":"Pferschy U, Schauer J (2009) The knapsack problem with conflict graphs. J Gr Algorithms Appl 13(2):233\u2013249","journal-title":"J Gr Algorithms Appl"},{"key":"9259_CR25","doi-asserted-by":"crossref","unstructured":"Kellerer H, Pferschy U, Pisinger D (2004) Knapsack problems. Springer, Berlin","DOI":"10.1007\/978-3-540-24777-7"},{"key":"9259_CR26","unstructured":"Yang S (1991) Logic synthesis and optimization benchmarks user guide. version 3.0"},{"key":"9259_CR27","doi-asserted-by":"publisher","unstructured":"Jozwiak L, Gawlowski D, Slusarczyk A (2004) Digital system design, 2004. In: DSD 2004. Euromicro symposium on (2004), pp 160 \u2013 167. https:\/\/doi.org\/10.1109\/DSD.2004.1333272","DOI":"10.1109\/DSD.2004.1333272"},{"key":"9259_CR28","unstructured":"Garcia-Vargas I (2013) FSMIM-Gen. http:\/\/personal.us.es\/iggv\/en\/material.html"}],"container-title":["Design Automation for Embedded Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10617-022-09259-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10617-022-09259-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10617-022-09259-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,30]],"date-time":"2022-06-30T16:28:05Z","timestamp":1656606485000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10617-022-09259-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["9259"],"URL":"https:\/\/doi.org\/10.1007\/s10617-022-09259-z","relation":{},"ISSN":["0929-5585","1572-8080"],"issn-type":[{"type":"print","value":"0929-5585"},{"type":"electronic","value":"1572-8080"}],"subject":[],"published":{"date-parts":[[2022,6]]},"assertion":[{"value":"12 July 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 April 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 June 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}