TEMPORAL EVENTS PROCESSING MODELS IN FINITE STATE MACHINES
DOI:
https://doi.org/10.15588/1607-3274-2023-4-5Keywords:
FSM pattern, HDL, real time devices, temporal events, electronic design automationAbstract
Context. The issue of a synthesizable finite state machine with temporal events processing using hardware description language pattern. The object of this study is external event processing in real-time systems.
Objective. The goal of this work is to introduce methods to express external temporal events on finite state machine state diagrams and corresponding HDL patterns of such events processing in control systems.
Method. The classification of external events in real-time systems is analyzed. A device class that changes its internal state depending on the temporal external events is introduced. A method to express these events on the temporal state diagram is introduced. Possible model behavior scenarios based on the external event duration are analyzed. A Verilog HDL external event processing pattern is introduced. The efficiency of the proposed model is proved by developing, verifying, and synthesis of a powersaving module in Xilinx ISE. The results and testing showed the model’s correctness.
Results. External temporal events processing methods in real-time device models are proposed. The corresponding HDL pattern for the proposed model implementation is presented.
Conclusions. The real-time systems with external temporal events automated synthesis problem has been solved. To solve this problem, a finite state machine model-based device using the Verilog language was developed and tested. The scientific novelty lies in the introduction a method to express temporal events on the state diagram of the finite state machine as well as in a HDL when implementing the proposed model on CPLD and FPGA.
References
Baranov S. Logic and System Design of Digital Systems. – Tallinn, TUT Press, 2008, 267 p. doi.org/10.1016/B978-07506-8397-5.00005-2.
Pedroni V. A. Finite state machines in hardware: theory and design (with VHDL and SystemVerilog). Cambridge, MA: MIT Press, 2013, 338 p. doi.org/10.7551/mitpress/9657.001.0001
Mіrosсhnyk M., Shkil A., Kulak E., Rakhlis D., Filippenko I., Hoha M., Malakhov M., Serhiienko V. Design of real-time logic control system on FPGA, Proceedings of 2019 IEEE East-West Design & Test Symposium (EWDTS’19), September 13–16. Batumi, Georgia, 2019, pp. 488–491. doi.org/10.1109/ewdts.2019.8884387
Shalyto A. A. Software Automation Design: Algorithmization and Programming of Problems of Logical Control, Journal of Computer and System Sciences International, 2000, Vol. 39, No. 6, pp. 899–916. doi.org/10.1023/a:1012392927006
Alur R., Dill D. L. A theory of timed automata, Theoretical Computer Science, 1994, Vol. 126, No. 2, pp. 183–235. doi.org/10.1016/0304-3975(94)90010-8
Zhigulin M., Yevtushenko N., Maag S., Cavalli A. R. FSMBased Test Derivation Strategies for Systems with TimeOuts, Proceedings of the 11th International Conference on Quality Software (QSIC 2011). Madrid, 2011, pp. 141–149. doi.org/10.1109/qsic.2011.30
Solov’ev V. V., Klimowicz A. S., Structural models of finite-state machines for their implementation on programmable logic devices and systems on chip, Journal of Computer and Systems Sciences International, 2015, Vol. 54, № 2, pp. 230–242. doi.org/10.1134/s1064230715010074
Shkil A. S., Mіrosсhnyk M. A., Kulak E. N., Rakhlis D. Y., Mіroshnyk A. M., Malahov N. V. Design timed FSM with VHDL Moore pattern, Radio Electronics, Computer Science, Control, 2020, № 2(53), pp. 137–148. /doi.org/10.15588/1607-3274-2020-2-14
Bresolin D., Tvardovskii A., Yevtushenko N., Villa T., Gromov M. Minimizing Deterministic Timed Finite State Machines, In 14th IFAC Workshop on Discrete Event Systems WODES 2018. – IFAC-PapersOnLine, 2018, Vol. 51, Issue 7, pp. 486–492. /doi.org/10.1016/j.ifacol.2018.06.344
Bresolin D., El-Fakih K., Villa T., Yevtushenko N. Equivalence checking and intersection of deterministic timed finite state machines, Formal Methods in System Design, 2022, № 7, pp. 1–26. doi.org/10.1007/s10703-02200396-6
Tvardovskii A. S., Yevtushenko N. V. Deriving homing sequences for finite state machines with timed guard, Automatic Control and Computer Sciences, 2021, Vol. 55, № 7, pp. 738–750. doi.org/10.3103/s0146411621070154
André Etienne, Lime Didier, Ramparison Mathias TCTL Model Checking Lower/Upper-Bound Parametric Timed Automata Without Invariants, Proc.International Conference Formal Modeling and Analysis of Timed Systems FORMATS 2018, September 4–6. Biejing, China, 2018, pp. 37–52. doi.org/10.1007/978-3-030-00151-3_3
Wagner G. An abstract state machine semantics for discrete event simulation, Proc. of the 2017 Winter Simulation Conference (WSC), 3–6 Dec. 2017. Las Vegas, USA, 12 p. [Electronic resource] / IEEE Xplore Digital Library. Access mode: www / URL: https://ieeexplore.ieee.org/ document/8247830. /doi.org/10.1109/wsc.2017.8247830
Shkil A., Mіrosсhnyk M., Kulak E., Rakhlis D., Filippenko I., Malakhov M. Hardware implementation of timed logical control FSM, Proc. of 2020 IEEE East-West Design & Test Symposium (EWDTS'20), Sept. 4–7. Varna, Bulgaria, 2020.– 6 p. [Electronic resource] / IEEE Xplore Digital Library – Access mode: www / URL: https://ieeexplore. ieee.org/document/ 9225129. /doi.org/10.1109/ewdts50664.2020.9225129
Lamperti G. Zanella M., Zhao Xiangfu Introduction to Diagnosis of Active Systems. Springer, 2018, 353 p. /doi.org/10.1007/978-3-319-92733-6
André Etienne, Lime Didier, Ramparison Mathias TCTL Model Checking Lower/Upper-Bound Parametric Timed Automata Without Invariants, Proc.International Conference Formal Modeling and Analysis of Timed Systems FORMATS 2018, September 4–6. Biejing, China, 2018, pp. 37–52. doi.org/10.1007/978-3-030-00151-3_3
Stéphane Lafortune. Discrete Event Systems: Modeling, Observation, and Control, Annual Review of Control, Robotics, and Autonomous Systems, 2019, No. 2:1, pp. 141– 159. doi.org/10.1146/annurev-control-053018-023659
Sabah Al-Fedaghi. Modeling Physical / Digital Systems: Formal Event-B vs. Diagrammatic Thinging Machine, International Journal of Computer Science and Network Security, 2020, No. 20 (4), pp. 208–220. hal-02614504 , version 1 (20-05-2020)
Karl Wiegers, Beatty Joy Software Requirements (Developer Best Practices) 3rd Edition, Developer Best Practices, 2013, 672 p. /doi.org/10.1109/9781118156629.ch3
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 М. А. Мірошник, С. І. Шматков, О. С. Шкіль, А. М. Мірошник, К. Ю. Пшеничний
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Creative Commons Licensing Notifications in the Copyright Notices
The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.
The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.
The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.
Authors who publish with this journal agree to the following terms:
-
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
-
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
-
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
