Structural models of Mealy finite state machines detecting faults in control systems

Valery Salauyou

Abstract


The subject matter of this article is a control system for unmanned aerial vehicles (UAVs) whose mathematical model is a finite state machine (FSM). The goal is to develop FSM structural models that enable (1) detection of multiple faults of FSM elements caused by an electromagnetic pulse or laser beam, and (2) prevent negative impacts on the controlled object. The tasks to be solved are as follows: to develop FSM structural models to detect invalid input vector X for the whole FSM and in each state, to detect invalid output vector Y for the whole FSM, at each transition and in each state, invalid code of the present (current) state, invalid code of the next state, and invalid transition between states; to determine the possible causes of the faults, which can be the failure in the logic Φ of forming the code of the next state, the invalid input vector X, the failure in the feedback circuit, the failure in the logic Ψ of forming the output vector, the failure in the state register R, the failure in the wire between the FSM input and the input of the logic Ψ; development of a combined structural model for the detection of all listed faults with a minimum number of additional combinational circuits, as well as a structural model that combines all additional combinational circuits. The methods used are: the theory of finite state machines, structural models of FSMs, state encoding methods of FSMs, representation methods of FSMs, and Verilog hardware description language. The following results were obtained: (1) the Mealy FSM structural models were developed to detect all the above mentioned faults, (2) the combined FSM structural models were developed, and (3) the possible causes of faults detected by each FSM structural model were identified. Experimental studies have shown that for the presented FSM structural models, the area overhead averages 3-23%, for one-hot encoding of FSM states, and 2-8%, for binary encoding of FSM states. Conclusions. The scientific novelty of the obtained results consists in the following for the first time FSM faults that are not caused by radiation and cosmic rays but by an electromagnetic pulse affecting the control device are considered; the number of faults is not limited for the state codes as well as for the input and output vectors; the faults can be detected not only in the state register R but also in the input vector X, in the logic Φ of generating the next state code, in the logic Ψ of generating the output signals, and in the feedback circuit; the invalid transitions of FSMs and the transitions to invalid states are also detected; the proposed structural models not only detect FSM failures but also prevent their negative impact on the controlled object; combined structural models allow simultaneous detection of faults in all elements of the FSM. Future research will focus on developing structural models for correcting FSM failures.

Keywords


structural model; fault detection; finite state machine (FSM); area overhead; control system; unmanned aerial vehicles (UAVs); field programmable gate array (FPGA)

Full Text:

PDF

References


Fesenko, H. V., & Kharchenko, V. S. Determination of an optimal route for flight over of specified points of a potentially dangerous object territory by UAV fleet. Radioelectronic and Computer Systems, 2019, no. 3, pp. 63-72. DOI: 10.32620/reks.2019.3.07.

Naso, D., Pohudina, O., Pohudin, A., Yashin, S., & Bartolo, R. Autonomous flight insurance method of unmanned aerial vehicles Parot Mambo using semantic segmentation data. Radioelectronic and Computer Systems, 2023, no. 1, pp. 147-154. DOI: 10.32620/reks.2023.1.12.

Min, S. H., Jung, H., Kwon, O., Sattorov, M., Kim, S., Park, S. H., Hong, D., Kim, S., Park, C., Hong, B. H., Cho, I., Ma, S., Kim, M., Yoo, Y. J., Park, S. Y., & Park, G. S. Analysis of electromagnetic pulse effects under high-power microwave sources. IEEE Access, 2021, no. 9, pp. 136775-136791. DOI: 10.1109/ACCESS.2021.3117395.

Solov’ev, V. V. ASMD‒FSMD technique in designing signal processing devices on field programmable gate arrays. Journal of Communications Technology and Electronics, 2021, vol. 66, no. 12, pp. 1336-1345. DOI: 10.1134/S1064226921120184.

Salauyou, V., & Zabrocki, Ł. Coding Techniques in Verilog for Finite State Machine Designs in FPGA. IFIP International Conference on Computer Information Systems and Industrial Management (CISIM), Belgrade, Serbia, 2019, pp. 493-505. DOI: 10.1007/978-3-030-28957-7_41.

Lyons, R. E., & Vanderkulk, W. The use of triple-modular redundancy to improve computer reliability. IBM journal of research and development, 1962, vol. 6, no. 2, pp. 200-209. DOI: 10.1147/rd.62.0200.

Aviziens, A. Fault-tolerant systems. IEEE transactions on computers, 1976, vol. 100, no. 12, pp. 1304-1312. DOI: 10.1109/TC.1976.1674598.

Rochet, R., Leveugle, R., & Saucier, G. Analysis and comparison of fault tolerant FSM architecture based on SEC codes. IEEE International Workshop on Defect and Fault Tolerance in VLSI Systems, Venice, Italy, 1993, pp. 9-16. DOI: 10.1109/DFTVS.1993.595604.

Niranjan, S., & Frenzel, J. F. A comparison of fault-tolerant state machine architectures for space-borne electronics. IEEE Transactions on Reliability, 1996, vol. 45, no. 1, pp. 109-113. DOI: 10.1109/24.488925.

Carmichael, C. Triple module redundancy design techniques for Virtex FPGAs. Xilinx Application Note XAPP197, v.1.0.1, 2006. 37 p. Available at: https://www.amd.com/en/search/site-search.html#q=XAPP197. (accessed 11 August 2023).

Pontarelli, S., Cardarilli, G. C., Malvoni, A., Ottavi, M., Re, M., & Salsano, A. System-on-chip oriented fault-tolerant sequential systems implementation methodology. IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems, Los Alamitos, USA, 2001, pp. 455-460. DOI: 10.1109/DFTVS.2001.966799.

Lima, F., Carro, L., & Reis, R. Designing fault tolerant systems into SRAM-based FPGAs. 40th annual Design Automation Conference (DAC), Anaheim, USA, 2003, pp. 650-655. DOI: 10.1145/775832.775997.

Burke, G. R., & Taft, S. Fault tolerant state machines, 2004. 10 p. Available at: https://dataverse.jpl.nasa.gov/api/access/datafile/9953?gbrecs=true. (accessed 11 August 2023).

Berg, M. A Simplified Approach to Fault Tolerant State Machine Design for Single Event Upsets. Mentor Graphics Users’ Group User2User Conference. 2004.

Tiwari, A., & Tomko, K. A. Enhanced reliability of finite-state machines in FPGA through efficient fault detection and correction. IEEE Transactions on Reliability, 2005, vol. 54, no. 3, pp. 459-467. DOI: 10.1109/TR.2005.853438.

Cassel, M., & Lima, F. Evaluating one-hot encoding finite state machines for SEU reliability in SRAM-based FPGAs. 12th IEEE International On-Line Testing Symposium (IOLTS). Lake Como, Italy, 2006, pp. 1-6. DOI: 10.1109/IOLTS.2006.32.

Frigerio, L., & Salice, F. RAM-based fault tolerant state machines for FPGAs. 22nd IEEE International Symposium on Defect and Fault-Tolerance in VLSI Systems (DFT), Rome, Italy, 2007, pp. 312-320. DOI: 10.1109/DFT.2007.33.

Azambuja, J. R., Sousa, F., Rosa, L., & Kastensmidt, F. L. Evaluating large grain TMR and selective partial reconfiguration for soft error mitigation in SRAM-based FPGAs. 15th IEEE International On-Line Testing Symposium, Lisbon, Portugal, 2009, pp. 101-106. DOI: 10.1109/IOLTS.2009.5195990.

El-Maleh, A. H., & Al-Qahtani, A. S. A finite state machine based fault tolerance technique for sequential circuits. Microelectronics Reliability, 2014, vol. 54, no. 3, pp. 654-661. DOI: 10.1016/j.microrel.2013.10.022.

Sooraj, S., Manasy, M., & Bhakthavatchalu, R. Fault tolerant FSM on FPGA using SEC-DED code algorithm. International Conference on Technological Advancements in Power and Energy (TAP Energy), Kollam, India, 2017, pp. 1-6. DOI: 10.1109/TAPENERGY.2017.8397309.

Nidhin, T. S., Bhattacharyya, A., Behera, R. P., Jayanthi, T., & Velusamy, K. Verification of fault tolerant techniques in finite state machines using simulation based fault injection targeted at FPGAs for SEU mitigation. 4th International Conference on Electronics and Communication Systems (ICECS), Coimbatore, India, 2017, pp. 153-157. DOI: 10.1109/ECS.2017.8067859.

Choi, S., Park, J., & Yoo, H. Area-Efficient Fault Tolerant Design for Finite State Machines. International Conference on Electronics, Information, and Communication (ICEIC), Barcelona, Spain, 2020, pp. 1-2. DOI: 10.1109/ICEIC49074.2020.9051122.

Verducci, O., Oliveira, D. L., & Batista, G. Fault-Tolerant Finite State Machine Quasi Delay Insensitive in Commercial FPGA Devices. 13th Latin America Symposium on Circuits and System (LASCAS), Santiago, Chile, 2022, pp. 1-4. DOI: 10.1109/LASCAS53948.2022.9789092.

Klimowicz, A. S., & Solov’ev, V. V. 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, no. 2, pp. 230-242. DOI: 10.1134/S1064230715010074.

Salauyou, V. Structural models for fault detection of Moore finite state machines. International Conference on Dependability and Complex Systems (DepCoS), Springer, Cham, 2023, pp. 214-223. DOI: 10.1007/978-3-031-37719-8.

Salauyou, V. Fault Detection of Moore Finite State Machines by Structural Models. International Conference on Computer Information Systems and Industrial Management (CISIM), Springer, Cham, 2023, pp. 1-16. DOI: 10.1007/978-3-031-42823-4_29.

Yang, S. Logic synthesis and optimization benchmarks user guide: version 3.0. Research Triangle Park, NC, USA: Microelectronics Center of North Carolina (MCNC), 1991. 45 p. Available at: https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=4a86519e41bb8dbaa8d2c9ba434030f48de85ce7. (accessed 11 August 2023).




DOI: https://doi.org/10.32620/reks.2023.3.14

Refbacks

  • There are currently no refbacks.