{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T01:21:00Z","timestamp":1760059260102,"version":"build-2065373602"},"reference-count":63,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2025,6,5]],"date-time":"2025-06-05T00:00:00Z","timestamp":1749081600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Science Foundation Ireland (SFI)","award":["16\/IA\/4605"],"award-info":[{"award-number":["16\/IA\/4605"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Quickly designing digital circuits that are both correct and efficient poses significant challenges. Electronics, especially those incorporating sequential logic circuits, are complex to design and test. While Electronic Design Automation (EDA) tools aid designers, they do not fully automate the creation of synthesisable circuits that can be directly translated into hardware. This paper introduces a system that employs Grammatical Evolution (GE) to automatically generate synthesisable Hardware Description Language (HDL) code for the Finite State Machine (FSM) of a Multi-Sequence Detector (MSD). This MSD differs significantly from prior work as it can detect multiple sequences in contrast to the single-sequence detectors discussed in existing literature. Sequence Detectors (SDs) are essential in circuits that detect sequences of specific events to produce timely alerts. The proposed MSD applies to a real-time vending machine scenario, enabling customer selections upon successful payment. However, this technique can evolve any MSD, such as a traffic light control system or a robot navigation system. We examine two parent selection techniques, Tournament Selection (TS) and Lexicase Selection (LS), demonstrating that LS performs better than TS, although both techniques successfully produce synthesisable hardware solutions. Both hand-crafted \u201cGold\u201d and evolved circuits are synthesised using Generic Process Design Kit (GPDK) technologies at 45 nm, 90 nm, and 180 nm scales, demonstrating their efficacy.<\/jats:p>","DOI":"10.3390\/a18060345","type":"journal-article","created":{"date-parts":[[2025,6,5]],"date-time":"2025-06-05T08:34:32Z","timestamp":1749112472000},"page":"345","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Automatic Generation of Synthesisable Hardware Description Language Code of Multi-Sequence Detector Using Grammatical Evolution"],"prefix":"10.3390","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7528-275X","authenticated-orcid":false,"given":"Bilal","family":"Majeed","sequence":"first","affiliation":[{"name":"BDS Labs, Department of CSIS, University of Limerick, V94 T9PX Limerick, Ireland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5551-1006","authenticated-orcid":false,"given":"Rajkumar","family":"Sarma","sequence":"additional","affiliation":[{"name":"BDS Labs, Department of CSIS, University of Limerick, V94 T9PX Limerick, Ireland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6145-4071","authenticated-orcid":false,"given":"Ayman","family":"Youssef","sequence":"additional","affiliation":[{"name":"Department of Computers and Systems, Electronics Research Institute, Cairo 12622, Egypt"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Douglas Mota","family":"Dias","sequence":"additional","affiliation":[{"name":"Department of Computer Science & Applied Physics, Atlantic Technological University, H91 T8NW Galway, Ireland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7002-5815","authenticated-orcid":false,"given":"Conor","family":"Ryan","sequence":"additional","affiliation":[{"name":"BDS Labs, Department of CSIS, University of Limerick, V94 T9PX Limerick, Ireland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2025,6,5]]},"reference":[{"key":"ref_1","unstructured":"Farrahi, A., Hathaway, D., Wang, M., and Sarrafzadeh, M. (2000, January 20\u201322). Quality of EDA CAD tools: Definitions, metrics and directions. Proceedings of the IEEE 2000 First International Symposium on Quality Electronic Design (Cat. No. PR00525), San Jose, CA, USA."},{"key":"ref_2","unstructured":"Solido (2022, November 01). Solido Design Solutions. Available online: https:\/\/eda.sw.siemens.com\/en-US\/ic\/solido\/."},{"key":"ref_3","unstructured":"Eagle (2022, November 01). Eagle by Autodesk. Available online: https:\/\/www.autodesk.com\/products\/eagle\/overview."},{"key":"ref_4","unstructured":"Kicad (2022, November 01). KiCad Electronic Design Automation. Available online: https:\/\/www.kicad.org\/."},{"key":"ref_5","unstructured":"Ince, D.C. (1992). Mechanical Intelligence (Collected Works of A. M. Turing), North-Holland Publishing Co."},{"key":"ref_6","first-page":"44","article-title":"Analytic programming\u2013Symbolic regression by means of arbitrary evolutionary algorithms","volume":"6","author":"Zelinka","year":"2005","journal-title":"Int. J. Simul. Syst. Sci. Technol."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Nicosia, G., Rinaudo, S., and Sciacca, E. (2007). An evolutionary algorithm-based approach to robust analog circuit design using constrained multi-objective optimization. Research and Development in Intelligent Systems XXIV, Springer.","DOI":"10.1016\/j.knosys.2007.11.014"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Mirjalili, S. (2019). Genetic Algorithm. Evolutionary Algorithms and Neural Networks: Theory and Applications, Springer International Publishing.","DOI":"10.1007\/978-3-319-93025-1_4"},{"key":"ref_9","unstructured":"Koza, J.R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection, MIT Press."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Ryan, C., Collins, J.J., and Neill, M.O. (1998, January 14\u201315). Grammatical evolution: Evolving programs for an arbitrary language. Proceedings of the European Conference on Genetic Programming, Paris, France.","DOI":"10.1007\/BFb0055930"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Rudolph, G. (2012). Evolutionary Strategies. Handbook of Natural Computing, Springer.","DOI":"10.1007\/978-3-540-92910-9_22"},{"key":"ref_12","unstructured":"Zhang, Y., Smith, S., and Tyrrell, A. (2004, January 26). Digital circuit design using intrinsic evolvable hardware. Proceedings of the 2004 NASA\/DoD Conference on Evolvable Hardware, Seattle, WA, USA."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Poli, R., Banzhaf, W., Langdon, W.B., Miller, J., Nordin, P., and Fogarty, T.C. (2000, January 15\u201316). An Extrinsic Function-Level Evolvable Hardware Approach. Proceedings of the Genetic Programming, Edinburgh, UK.","DOI":"10.1007\/b75085"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Ali, M., Kshirsagar, M., Naredo, E., and Ryan, C. (2021, January 25\u201327). Towards Automatic Grammatical Evolution for Real-world Symbolic Regression. Proceedings of the 13th International Joint Conference on Computational Intelligence, Virtual.","DOI":"10.5220\/0010691500003063"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Murphy, A., Murphy, G., Amaral, J., Mota Dias, D., Naredo, E., and Ryan, C. (2021, January 7\u20139). Towards Incorporating Human Knowledge in Fuzzy Pattern Tree Evolution. Proceedings of the European Conference on Genetic Programming (Part of EvoStar), Virtual Event.","DOI":"10.1007\/978-3-030-72812-0_5"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Youssef, A., Majeed, B., and Ryan, C. (2021, January 23\u201325). Optimizing combinational logic circuits using Grammatical Evolution. Proceedings of the IEEE 2021 3rd Novel Intelligent and Leading Emerging Sciences Conference (NILES), Giza, Egypt.","DOI":"10.1109\/NILES53778.2021.9600092"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Majeed, B., Ryan, C., McEllin, J., Youssef, A., Dias, D., Murphy, A., and Carvalho, S. (2023, January 22\u201324). Evolving Behavioural Level Sequence Detectors in SystemVerilog Using Grammatical Evolution. Proceedings of the 15th International Conference on Agents and Artificial Intelligence, Set\u00fabal, Portugal.","DOI":"10.5220\/0011689100003393"},{"key":"ref_18","unstructured":"Mealy, B., and Tappero, F. (2018). Free Range VHDL, eBook."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Chu, P.P. (2008). Xilinx Spartan-3 Specific Memory. FPGA Prototyping by Verilog Examples, John Wiley and Sons, Ltd.. Chapter 12.","DOI":"10.1002\/9780470374283"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Ryan, C., Tetteh, M.K., and Dias, D.M. (2020, January 2\u20134). Behavioural Modelling of Digital Circuits in System Verilog using Grammatical Evolution. Proceedings of the 12th International Joint Conference on Computational Intelligence, Budapest, Hungary.","DOI":"10.5220\/0010066600280039"},{"key":"ref_21","first-page":"109","article-title":"Intelligent traffic light control system based on multi-agent systems","volume":"8","author":"Bak","year":"2011","journal-title":"Int. J. Comput. Sci. Issues (IJCSI)"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Yue, S., and Smith, R.K. (2021, January 5\u20137). Applying Context State Machines to Smart Elevators: Design, Implementation and Evaluation. Proceedings of the 2021 IEEE Symposium Series on Computational Intelligence (SSCI), Orlando, FL, USA.","DOI":"10.1109\/SSCI50451.2021.9659873"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Siciliano, B., and Khatib, O. (2016). Springer Handbook of Robotics, Springer.","DOI":"10.1007\/978-3-319-32552-1"},{"key":"ref_24","unstructured":"Stevens, W.R. (1994). TCP\/IP Illustrated, Volume 1: The Protocols, Addison-Wesley."},{"key":"ref_25","unstructured":"Navabi, Z. (2007). VHDL: Modular Design and Synthesis of Cores and Systems, McGraw-Hill."},{"key":"ref_26","unstructured":"Ciletti, M.D. (2010). Advanced Digital Design with the Verilog HDL, Prentice Hall Press. [2nd ed.]."},{"key":"ref_27","unstructured":"Spear, C. (2008). SystemVerilog for Verification, Second Edition: A Guide to Learning the Testbench Language Features, Springer. [2nd ed.]."},{"key":"ref_28","unstructured":"Cadence (2022, April 01). Cadence Design Systems. Available online: https:\/\/www.cadence.com\/."},{"key":"ref_29","unstructured":"Morris, M., and Ciletti, M.D. (2007). Digital Design, Pearson Prentice Hall."},{"key":"ref_30","unstructured":"Fourman, M.P. (1985, January 24\u201326). Compaction of Symbolic Layout Using Genetic Algorithms. Proceedings of the 1st International Conference on Genetic Algorithms, Pittsburgh, PA, USA."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"956","DOI":"10.1109\/TCAD.1987.1270337","article-title":"Genetic Placement","volume":"6","author":"Cohoon","year":"1987","journal-title":"IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1109\/43.21844","article-title":"ESp: Placement by simulated evolution","volume":"8","author":"Kling","year":"1989","journal-title":"IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Higuchi, T., Niwa, T., Tanaka, T., Iba, H., de Garis, H., and Furuya, T. (1993, January 9). Evolving Hardware with Genetic Learning: A First Step towards Building a Darwin Machine. Proceedings of the From Animals to Animats 2: Proceedings of the Second International Conference on Simulation of Adaptive Behavior, Honolulu, HI, USA.","DOI":"10.7551\/mitpress\/3116.003.0056"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1038\/330033a0","article-title":"The brain as a Darwin Machine","volume":"330","author":"Calvin","year":"1987","journal-title":"Nature"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"1024","DOI":"10.1109\/TSMCB.2006.872259","article-title":"Generalized disjunction decomposition for evolvable hardware","volume":"36","author":"Stomeo","year":"2006","journal-title":"IEEE Trans. Syst. Man Cybern. B Cybern."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Vasicek, Z., and Sekanina, L. (2008, January 26\u201328). Hardware Accelerators for Cartesian Genetic Programming. Proceedings of the Genetic Programming, Naples, Italy.","DOI":"10.1007\/978-3-540-78671-9_20"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1007\/s42979-022-01045-9","article-title":"Grammatical Evolution of Complex Digital Circuits in SystemVerilog","volume":"3","author":"Tetteh","year":"2022","journal-title":"SN Comput. Sci."},{"key":"ref_38","unstructured":"Hu, T., Louren\u00e7o, N., and Medvet, E. (2021, January 7\u20139). Evolution of Complex Combinational Logic Circuits Using Grammatical Evolution with SystemVerilog. Proceedings of the Genetic Programming, Virtual Event."},{"key":"ref_39","unstructured":"Ashlock, D., Wittrock, A., and Wen, T.J. (2002, January 12\u201317). Training finite state machines to improve PCR primer design. Proceedings of the 2002 Congress on Evolutionary Computation. CEC\u201902 (Cat. No.02TH8600), Honolulu, HI, USA."},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Klimowicz, A., and Salauyou, V. (2022). State Merging and Splitting Strategies for Finite State Machines Implemented in FPGA. Appl. Sci., 12.","DOI":"10.3390\/app12168134"},{"key":"ref_41","unstructured":"Pinto Ferraz Fabbri, S., Delamaro, M., Maldonado, J., and Masiero, P. (1994, January 6\u20139). Mutation analysis testing for finite state machines. Proceedings of the 1994 IEEE International Symposium on Software Reliability Engineering, Monterey, CA, USA."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Villa, T., Kam, T., Brayton, R.K., and Sangiovanni-Vincentelli, A.L. (1997). Synthesis of Finite State Machines: Logic Optimization, Springer Science & Business Media.","DOI":"10.1007\/978-1-4615-6155-2"},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Sanchez, E., and Tomassini, M. (1995, January 2\u20133). Development and evolution of hardware behaviors. Proceedings of the Towards Evolvable Hardware (TEH), Lausanne, Switzerland.","DOI":"10.1007\/3-540-61093-6"},{"key":"ref_44","unstructured":"Collet, P., Gardashova, L., El Zant, S., and Abdulkarimova, U. (2023, January 25\u201327). Performance Upgrade of Sequence Detector Evolution Using Grammatical Evolution and Lexicase Parent Selection Method. Proceedings of the Complex Computational Ecosystems, Baku, Azerbaijan."},{"key":"ref_45","unstructured":"Mizoguchi, J., Hemmi, H., and Shimohara, K. (1994, January 27\u201329). Production genetic algorithms for automated hardware design through an evolutionary process. Proceedings of the First IEEE Conference on Evolutionary Computation, IEEE World Congress on Computational Intelligence, Orlando, FL, USA."},{"key":"ref_46","unstructured":"Shanthi, A., Singaram, L., and Parthasarathi, R. (July, January 29). Evolution of asynchronous sequential circuits. Proceedings of the 2005 NASA\/DoD Conference on Evolvable Hardware (EH\u201905), Washington, DC, USA."},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Soleimani, P., Sabbaghi-Nadooshan, R., Mirzakuchaki, S., and Bagheri, M. (2011). Using Genetic Algorithm in the Evolutionary Design of Sequential Logic Circuits. arXiv.","DOI":"10.7763\/IJMO.2011.V1.41"},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1023\/B:GENP.0000017009.11392.e2","article-title":"Evolutionary Algorithms and Theirs Use in the Design of Sequential Logic Circuits","volume":"5","author":"Ali","year":"2004","journal-title":"Genet. Program. Evolvable Mach."},{"key":"ref_49","unstructured":"Popa, R., Aiord\u0103chioaie, D., and S\u00eerbu, G. (2005, January 2\u20134). Evolvable Hardware in Xilinx Spartan-3 FPGA. Proceedings of the 2005 WSEAS International Conference on Dynamical Systems and Control (ICDSC), Venice, Italy."},{"key":"ref_50","unstructured":"Yao, R., Wang, Y.r., Yu, S.l., and Gao, G.j. (2007, January 21\u201323). Research on the Online Evaluation Approach for the Digital Evolvable Hardware. Proceedings of the Evolvable Systems: From Biology to Hardware (ESFBH), Wuhan, China."},{"key":"ref_51","doi-asserted-by":"crossref","unstructured":"Xiong, F., and Rafla, N.I. (2009, January 2\u20135). On-chip intrinsic evolution methodology for sequential logic circuit design. Proceedings of the 2009 52nd IEEE International Midwest Symposium on Circuits and Systems, Cancun, Mexico.","DOI":"10.1109\/MWSCAS.2009.5236119"},{"key":"ref_52","first-page":"41","article-title":"An Evolutionary Circuit Model for Cardiovascular System: An FPGA Approach","volume":"5","author":"Xiong","year":"2011","journal-title":"Int. J. Comput. Inf. Technol. Eng."},{"key":"ref_53","unstructured":"Tao, Y., Cao, J., Zhang, Y., Lin, J., and Li, M. (2012, January 10\u201315). Using module-level Evolvable Hardware approach in design of sequential logic circuits. Proceedings of the 2012 IEEE Congress on Evolutionary Computation (CEC), Brisbane, QLD, Australia."},{"key":"ref_54","first-page":"60","article-title":"Design of vending machine through implementation of visual automata simulator and finite state machine","volume":"2","author":"Kumar","year":"2021","journal-title":"Int. J. Res. Circuits, Devices Syst."},{"key":"ref_55","first-page":"1467","article-title":"Application of the Finite State Automata Concept in Applications Fruit Vending Machine Simulation","volume":"6","author":"Kurniawan","year":"2022","journal-title":"J. Mantik"},{"key":"ref_56","doi-asserted-by":"crossref","unstructured":"Shivanand, N., L Rathod, M., and Chetan, S. (2023, January 30\u201331). FPGA based Vending Machine For Logical Gates. Proceedings of the 2023 3rd International Conference on Smart Data Intelligence (ICSMDI), Trichy, India.","DOI":"10.1109\/ICSMDI57622.2023.00059"},{"key":"ref_57","doi-asserted-by":"crossref","unstructured":"Sindhu, G., Thanusha, K., Ganesh, G.V., Reddy, K., and Pujitha, M. (2023, January 26\u201328). Design of Vending Machine Using Visual Automata Simulator And Finite State Machine. Proceedings of the 2023 International Conference on Communication, Circuits, and Systems (IC3S), Bhubaneswar, India.","DOI":"10.1109\/IC3S57698.2023.10169469"},{"key":"ref_58","first-page":"193","article-title":"Genetic Algorithms, Tournament Selection, and the Effects of Noise","volume":"9","author":"Miller","year":"1995","journal-title":"Complex Syst."},{"key":"ref_59","doi-asserted-by":"crossref","unstructured":"Spector, L. (2012, January 7\u201311). Assessment of Problem Modality by Differential Performance of Lexicase Selection in Genetic Programming: A Preliminary Report. Proceedings of the 14th Annual Conference Companion on Genetic and Evolutionary Computation (GECCO \u201912), Philadelphia, PA, USA.","DOI":"10.1145\/2330784.2330846"},{"key":"ref_60","doi-asserted-by":"crossref","unstructured":"Orzechowski, P., La Cava, W., and Moore, J.H. (2018, January 15\u201319). Where Are We Now? A Large Benchmark Study of Recent Symbolic Regression Methods. Proceedings of the Genetic and Evolutionary Computation Conference. Association for Computing Machinery, Kyoto, Japan.","DOI":"10.1145\/3205455.3205539"},{"key":"ref_61","doi-asserted-by":"crossref","unstructured":"La Cava, W., and Moore, J. (2018, January 23\u201327). Behavioral search drivers and the role of elitism in soft robotics. Proceedings of the ALIFE 2018: The 2018 Conference on Artificial Life, Tokyo, Japan.","DOI":"10.1162\/isal_a_00044"},{"key":"ref_62","doi-asserted-by":"crossref","unstructured":"Rodr\u00edguez, I., Rubio, D., and Rubio, F. (2023). Complexity of adaptive testing in scenarios defined extensionally. Front. Comput. Sci., 17.","DOI":"10.1007\/s11704-022-1673-9"},{"key":"ref_63","doi-asserted-by":"crossref","first-page":"642","DOI":"10.3390\/signals3030039","article-title":"GRAPE: Grammatical Algorithms in Python for Evolution","volume":"3","author":"Carvalho","year":"2022","journal-title":"Signals"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/6\/345\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T17:47:03Z","timestamp":1760032023000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/6\/345"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,5]]},"references-count":63,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2025,6]]}},"alternative-id":["a18060345"],"URL":"https:\/\/doi.org\/10.3390\/a18060345","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2025,6,5]]}}}