DOI: https://doi.org/10.15588/1607-3274-2020-2-14

DESIGN TIMED FSM WITH VHDL MOORE PATTERN

M. A. Mіroshnyk, A. S. Shkil, E. N. Kulak, D. Y. Rakhlis, A. M. Mіroshnyk, N. V. Malahov

Abstract


Context. The relevance of the work consists in the development of computer-aided design methods for automatic real-time logic control devices by developing a single template in a synthesized subset of the hardware description language in the style of automatabased programming with implementation on the PLD hardware platform (FPGA, CPLD). Development of the description template for timed control finite state machines (FSM) in the hardware description language VHDL, automated synthesis and implementation of the model in PLD (FPGAs, CPLDs) using Xilinx ISE, subsequent analysis of the received circuit implementation for compliance with values of timing parameters of the circuit after implementation.

Objective. The aim of the work is to develop principles for constructing models of timed control FSM in the VHDL hardware description language. In this work, we solved the problem of constructing a pattern for describing models of timed control Moore FSM using VHDL, automated synthesis and implementation of the obtained VHDL model in PLDs (FPGA, CPLD) using Xilinx ISE and subsequent analysis of the resulting circuit implementation for compliance with values of timing parameters of the circuit after implementation.

Method. Realization of models’ parameters of timed FSM in logical control systems using VHDL statements. Development of VHDL language constructions of timed FSM models for timing parameters implementation that provide the correct automated synthesis and implementation of these models in PLDs (FPGA, CPLD) using CAD tools Xilinx ISE.

Results. Synthesis and implementation of proposed templates of VHDL-models of timed control Moore FSM in logic control systems by XILINX ISE CAD tools confirmed the receipt of not redundant circuits in PLD (FPGA, CPLD), and simulation after implementation showed the efficiency of such models.

Conclusions. The work solves the problem of computer-aided design of timed control FSM in real-time logic control systems. To solve this problem, VHDL-models of timed control Moore FSM were developed, which made it possible to implement control FSM with time constraints, timeouts and output delays. Automated synthesis and simulation of VHDL models based on the developed templates confirmed the efficiency and correctness of the proposed models.

The scientific novelty of the work consists in the further development of methods for constructing templates of HDL models of timed control Moore FSM, which made it possible to implement control FSM with time constraints, timeouts and output delays, as well as perform their correct automated synthesis and simulation.

The practical value of results is in the development of procedures for constructing VHDL models of timed Moore control FSM in real-time logic control systems, which made it possible to automate the synthesis of control FSM taking into account the possibility of processing external events and implementing arbitrary delays for output signals and to increase the flexibility and speed of designed systems. The developed procedures can be useful for designers of timed control FSM in Xilinx ISE. 


Keywords


Timed finite state machine, state diagram, hardware description language, automata-based pattern, simulation, synthesis, implementation, CAD, Xilinx ISE.

Full Text:

PDF

References


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.

Harel D. Statеchars: a Visual Formalism for complex systems, Science of Computer Programming, 1987, Vol. 8, pp. 231–274.

Alur R., Dill D. L. A theory of timed automata, Theoretical Computer Science, 1994, Vol. 126, No. 2, pp. 183–235.

Alur R. Timed automata, Proceedings of the 11th International Conference on Computer Aided Verification, CAV’99, Trento, Italy, July 6-10, 1999. Springer, 1999, pp. 8–22.

Merayo M. G., Núñez M., Rodríguez I. Formal testing from timed finite state machines, Computer Networks. – 2008. – Vol.52(2). – P. 432-460. DOI 10.1007/978-3-642-05031-2_5.

Merayo M. G., Núñez M., Rodríguez I. Extending efsms to specify and test timed systems with action durations and timeouts, IEEE Transactions on Computers, 2008, Vol. 57 (6), pp. 835–844. DOI 0018-9340/08/25.00

Zhigulin M., Yevtushenko N., Maag S., Cavalli A. R. FSMBased Test Derivation Strategies for Systems with Time-Outs, Proceedings of the 11th International Conference on Quality Software (QSIC 2011), Madrid, 2011, pp. 141–149. DOI:10.1109/QSIC.2011.30.

El-Fakih K., Yevtushenko N., Simão A. A practical approach for testing timed deterministic finite state machines with single clock, Science of Computer Programming. Elsevier, 2014, Vol. 80, pp. 343–355. DOI: 0.1016/j.scico.2013.09.008.

Bresolin D., El-Fakih K., Villa T., Yevtushenko N. Deterministic Timed Finite State Machines: Equivalence Checking and Expressive Power, Intern Conf. GANDALF, 2014, pp. 203–216. DOI: 10.4204/EPTCS.161.18.

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.

Adamski M., Barkalov Al., and Wegrzyn M. (Eds) Design of Digital Systems and Devices. Berlin, Springer-Verlag, 2011, 366 p. ISBN 978-3-642-17545-9.

Shamgunov N., Korneev G., Shalyto A. State Machine Design Pattern, Shot communication papers conference proceedings of 4-th International Conference .NET Technologies in Central Europe 2006, May 29 – June 1, 2006, Net Technologies University of West Bohemia, pp. 51–57. DOI: 10.1155/2018/4094951

Haskell R., Hanna D. Digital Design Using Digilent FPGA Boards – VHDL / Active-HDL Edition. LBE Books Rochester Hills, MI, 2009, 381 p. ISBN 10: 0980133785 / ISBN 13: 9780980133783.

Pedroni, V. A. Finite state machines in hardware : theory and design (with VHDL and SystemVerilog). Cambridge, MA: MIT Press., 2013, 338 p. ISBN: 0884174985574 .

ISE In-Depth Tutorial. UG695 (v14.1) April 24, 2012 [Electronic resource] / www.xilinx.com. Access mode: https://www.xilinx.com/support/documentation/sw_manuals/ xilinx14_1/ise_tutorial_ug695.pdf.

Mіrosсhnyk M. , Shkil A., Kulak E., Rakhlis D., Filippenko I., Hoha M., M. Malakhov, V. Serhiienko 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, P. 488–491. DOI: 10.1109/TCSII.2018.2875589.


GOST Style Citations


1. Shalyto A.A. Software Automation Design: Algorithmization and Programming of Problems of Logical Control / A.A. Shalyto // Journal of Computer and System Sciences International. – 2000. – Vol. 39, No. 6. – P. 899–916.

2. Harel D. Statеchars: a Visual Formalism for complex systems / D. Harel // Science of Computer Programming. – 1987. – Vol. 8. – P. 231–274.

3. Alur R. A theory of timed automata / R. Alur, D.L. Dill // Theoretical Computer Science. – 1994. – V.126. – N 2. – P. 183–235.

4. R Alur. Timed automata // Proceedings of the 11th International Conference on Computer Aided Verification, CAV’99, Trento, Italy, July 6–10, 1999. – Springer, 1999. – P. 8–22.

5. Merayo M. G., Núñez M., Rodríguez I. Formal testing from timed finite state machines. // Computer Networks. – 2008. – Vol. 52(2). – P. 432–460. DOI 10.1007/978-3-64205031-2_5.

6. Merayo M. G., Núñez M., Rodríguez I. Extending efsms to specify and test timed systems with action durations and timeouts. // IEEE Transactions on Computers. – 2008. – Vol.57(6). – P. 835–844. DOI 0018-9340/08/25.00

7. Zhigulin M. FSM-Based Test Derivation Strategies for Systems with Time-Outs / M. Zhigulin, N. Yevtushenko, S. Maag, A.R. Cavalli // Proceedings of the 11th International Conference on Quality Software (QSIC 2011), Madrid, 2011. – P. 141–149. DOI:10.1109/QSIC.2011.30.

8. El-Fakih K. A practical approach for testing timed deterministic finite state machines with single clock / K. El-Fakih, N. Yevtushenko, A. Simão // Science of Computer Programming. Elsevier. – 2014. – Vol. 80. – P. 343–355. DOI: 0.1016/j.scico.2013.09.008.

9. Bresolin D. Deterministic Timed Finite State Machines: Equivalence Checking and Expressive Power / D. Bresolin, K. El-Fakih, T. Villa, N. Yevtushenko // Intern Conf. GANDALF. – 2014. – P. 203–216. DOI: 10.4204/EPTCS.161.18.

10. Bresolin D. Minimizing Deterministic Timed Finite State Machines / D. Bresolin, A. Tvardovskii, N. Yevtushenko, T. Villa, M. Gromov // In 14th IFAC Workshop on Discrete Event Systems WODES 2018. – IFAC-PapersOnLine, 2018. – Vol. 51, issue 7. – P. 486–492.

11. Adamski M. Design of Digital Systems and Devices / Marian Adamski, Alexander Barkalov, and Marek Wegrzyn (Eds). – Berlin: Springer-Verlag, 2011. – 366 p. ISBN 978-3-642-17545-9.

12. Shamgunov N. State Machine Design Pattern / N. Shamgunov, G. Korneev, A. Shalyto // Shot communication papers conference proceedings of 4-th International Conference .NET Technologies in Central Europe 2006, May 29 – June 1 2006. – Net Technologies University of West Bohemia. – P. 51–57. DOI: 10.1155/2018/4094951

13. Haskell R. Digital Design Using Digilent FPGA Boards – VHDL / Active-HDL Edition / Richard E. Haskell, Darrin M. Hanna. – LBE Books Rochester Hills, MI, 2009. – 381 p. ISBN 10: 0980133785 / ISBN 13: 9780980133783.

14. Pedroni, V. A. Finite state machines in hardware : theory and design (with VHDL and SystemVerilog) / Volnei A. Pedroni. – Cambridge, MA : MIT Press, 2013. – 338 p. ISBN: 0884174985574 .

15. ISE In-Depth Tutorial. UG695 (v14.1) April 24, 2012 [Electronic resource] / www.xilinx.com – Access mode: https://www.xilinx.com/support/documentation/sw_manuals / xilinx14_1/ise_tutorial_ug695.pdf.

16. Design of real-time logic control system on FPGA / [M. Mіrosсhnyk, A. Shkil, E. Kulak et al] // Proceedings of 2019 IEEE East-West Design & Test Symposium (EWDTS’19), September 13–16, Batumi, Georgia, 2019. – P. 488–491. DOI: 10.1109/TCSII.2018.2875589.







Copyright (c) 2020 M. A. Mіroshnyk, A. S. Shkil, E. N. Kulak, D. Y. Rakhlis, A. M. Mіroshnyk, N. V. Malahov

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Address of the journal editorial office:
Editorial office of the journal «Radio Electronics, Computer Science, Control»,
National University "Zaporizhzhia Polytechnic", 
Zhukovskogo street, 64, Zaporizhzhia, 69063, Ukraine. 
Telephone: +38-061-769-82-96 – the Editing and Publishing Department.
E-mail: rvv@zntu.edu.ua

The reference to the journal is obligatory in the cases of complete or partial use of its materials.