2. Home
  3. ARCHIVE
  4. 2021
  5. VOL 43, NO 5 (2021)
  6. pp. 21-42

Fault-tolerant structures of digital devices based on Boolean complement with the calculations checking by sum codes

D.V. Efanov, D. Sc. (Tech.)

Federal State Autonomous Educational Institution of Higher Education
“Russian University of Transport”
(Russian Federation, 127994, Moscow, Obraztsova str., build. 9/9)
contact phone number (+7) (911) 709-2164, e-mail: This email address is being protected from spambots. You need JavaScript enabled to view it.) 

Èlektron. model. 2021, 43(5):21-42
https://doi.org/10.15407/emodel.43.05.021

ABSTRACT

The article considers the construction of fault-tolerant digital devices and computing systems that does not use the principles of introducing modular redundancy. To correct the signals, a special distorted signal fixation unit, concurrent error-detection by the pre-selected redundant code circuit, as well as a signal correction block are used. The distorted signal fixation unit is implemented by the Boolean complement method, which makes it possible to design a large number of such blocks with different indicators of technical implementation complexity. When synthesizing a fault-tolerant device according to the proposed method, it is possible to organize a concurrent error-detection circuit for both the source device and the Boolean complement block in the structure of the distorted signal fixation unit. This makes it possible to choose among the variety of ways to implement fault-tolerant devices according to the proposed method, one that gives a device with the least structural redundancy. Various redundant codes can be used to organize concurrent error-detection circuits, including classical and modified sum codes. The author provides algorithms for the synthesis of distorted signal fixation unit and the Boolean complement block. The results of experimental researches with combinational benchmarks devices from the well-known LG’91 and MCNC Benchmarks sets are highlighted. The article presents the possibilities of the considered method for the organization of fault-tolerant digital devices and computing systems.

KEYWORDS

fault-tolerant digital device; calculations checking; Boolean complement; fault-tolerant structures; double modular redundancy.

REFERENCES

  1. Shcherbakov, N.S. (1975), Samokorrektiruyushchiesya diskretnye ustrojstva [Self-correcting discrete devices], Mashinostroenie, Moscow, USSR.
  2. Sogomonyan, E.S. and Slabakov, E.V. (1989), Samoproverjaemyje ustrojstva i otkazoustojchivyje sistemy [Self-checking devices and failover systems], Radio i Svjaz, Moscow, USSR.
  3. Sapozhnikov, V.V. and Sapozhnikov, Vl.V. (1992), Samoproveryaemye diskretnye ustrojstva [Self-checking discrete devices], Energoatomizdat, St. Petersburg, Russia.
  4. Mikoni, S.V. (1992), Obshchie diagnosticheskie bazy znanij vychislitelnyh sistem [General Diagnostic Knowledge Base of Computing Systems], SPIIRAN, St. Petersburg, Russia.
  5. Abramovici, M., Breuer, M.A. and Friedman, A.D. (1998), Digital System Testing and Testable Design, IEEE Press, New Jersey, USA.
  6. Drozd, A.V., Kharchenko, V.S. and Antoshchuk, S.G. (2012), Rabochee diagnostirovanie bezopasnykh informatsionno-upravljayustchikh sistem [Objects and Methods of On-Line Testing for Safe Instrumentation and Control Systems], Natsionalnyy aerokosmicheskiy universitet «KhAI», Kharkov, Ukraine.
  7. Hahanov, V. (2018), Cyber Physical Computing for IoT-driven Services, Springer International Publishing AG, New York, USA.
    https://doi.org/10.1007/978-3-319-54825-8
  8. Gavzov, D.V., Sapozhnikov, V.V. and Sapozhnikov, Vl.V. (1994) “Methods for Providing Safety in Discrete Systems”, Automation and Remote Control, Vol. 55, no. 8, pp. 1085- 1122.
  9. Sklyar, V.V. and Kharchenko, V.S. (2002), “Fault-Tolerant Computer-Aided Control Systems with Multiversion-Threshold Adaptation: Adaptation Methods, Reliability Estimation, and Choice of an Architecture”, Automation and Remote Control, Vol. 63, no. 6, pp. 991-1003.
    https://doi.org/10.1023/A:1016130108770
  10. Bochkov, K.A., Harlap, S.N. and Sivko, B.V. (2016), “Development of fault-tolerant systems based on diversified bases”, Avtomatika na transporte, Vol. 2, no. 1, pp. 47—64.
  11. Fujiwara, E. (2006), Code Design for Dependable Systems: Theory and Practical Applications, John Wiley & Sons, New Your, USA.
    https://doi.org/10.1002/0471792748
  12. Sapozhnikov, V.V., Sapozhnikov, Vl.V. and Efanov, D.V. (2018), Kody Khemminga v sistemakh funktsionalnogo kontrolja [Hamming Сodes in Concurrent Error Detection Systems of Logic Devices], Nauka, St. Petersburg, Russia.
  13. Sapozhnikov, V.V., Sapozhnikov, Vl.V. and Efanov, D.V. (2020), Kody s summirovaniem dlya sistem tekhnicheskogo diagnostirovaniya. Tom 1: Klassicheskie kody Bergera i ih modifikacii [Sum Codes for Technical Diagnostics Systems. Volume 1: Classical Berger Codes and Their Modifications], Nauka, Moscow, Russia.
  14. Sapozhnikov, V.V., Sapozhnikov, Vl.V. and Efanov, D.V. (2021), Kody s summirovaniem dlya sistem tekhnicheskogo diagnostirovaniya. Tom 2: Vzveshennyje kody s summirovanijem [Sum Codes for Technical Diagnostics Systems. Volume 2: Weight-Based Sum Codes], Nauka, Moscow, Russia.
  15. Gavrilov, M.A., Ostianu, V.M. and Potekhin, A.I. (1970), “Reliability of discrete systems”, Itogi nauki i tekhniki. Ser. «Teoriya veroyatnostej. Matematicheskaya statistika. Teoreticheskaya kibernetika», pp. 7—104.
  16. Hamamatsu, M., Tsuchiya, T. and Kikuno, T. (2008), “Finding the Optimal Configuration of a Cascading TMR System”, 14th IEEE Pacific Rim International Symposium on Dependable Computing 14th IEEE Pacific Rim International Symposium on Dependable Computing, December 15-17, 2008, Taipei, Taiwan, pp. 329-350.
    https://doi.org/10.1109/PRDC.2008.12
  17. Matsumoto, K., Uehara, M. and Mori, H. (2010), “Evaluating the Fault Tolerance of Stateful TMR”, 13th International Conference on Network-Based Information Systems, September 14-16, 2010, Takayama, Japan, pp. 332-336.
    https://doi.org/10.1109/NBiS.2010.86
  18. Kubátová, H. and Kohlík, M. (2012), “Reduction of Complex Safety Models Based on Markov Chains”, 2012 IEEE 15th International Symposium on Design and Diagnostics of Electronic Circuits & Systems (DDECS), April 18-20, 2012, Tallinn, Estonia. DOI: 1109/DDECS.2012.6219050.
  19. Stempkovskij, A.L., Telpuhov, D.V., Zhukova, T.D., Gurov, S.I. and Solovyev, R.A. (2017), “Methods for the synthesis of fault-tolerant combinational CMOS circuits providing automatic error correction”, Izvestiya YUFU. Tekhnicheskie nauki, Vol. 7, no. 192, pp. 197-210. DOI 10.23683 / 2311-3103-2017-7-197-210.
  20. Borecký, J., Kohlík, M., Vít, P. and Kubátová, H. (2016), “Enhanced Duplication Method with TMR-Like Masking Abilities”, 2016 Euromicro Conference on Digital System Design (DSD), August 31 – September 2, 2016, Limassol, Cyprus.
    https://doi.org/10.1109/DSD.2016.91
  21. Sapozhnikov, V.V., Sapozhnikov, Vl.V. and Efanov, D.V. (2019), Osnovy teorii nadezhnosti i tekhnicheskoj diagnostiki [Fundamentals of the theory of reliability and technical diagnostics], Lan, St. Petersburg, Russia.
  22. Potemkin, I.S. (1988), Funkcionalnye uzly cifrovoj avtomatiki [Functional units of digital automation], Energoatomizdat, Moscow, USSR.
  23. Sapozhnikov, V., Sapozhnikov, Vl. and Efanov, D. (2020), “Typical Signal Correction Structures Based on Duplication with the Integrated Control Circuit”, Proceedings of 18th IEEE East-West Design & Test Symposium (EWDTS’2020), Varna, Bulgaria, September 4-7, 2020, pp. 78—87.
  24. Sapozhnikov, V.V., Sapozhnikov, Vl.V. and Efanov, D.V. (2020), “Structures of signal correction circuits based on double modular redundancy with computation control”, Izvestiya vuzov. Priborostroenie, Vol. 63, no. 8, pp. 687—701.
    https://doi.org/10.17586/0021-3454-2020-63-8-687-701
  25. Sapozhnikov, V.V., Sapozhnikov, Vl.V. and Efanov, D.V. (2020), “Signal Correction Circuit for Combinational Automation Devices on the Basis of Boolean Complement with Control of Calculations by Parity”, Informatika, Vol. 17, no. 2, pp. 71-85.
    https://doi.org/10.37661/1816-0301-2020-17-2-71-85
  26. Goessel, M., Morozov, A.V., Sapozhnikov, V.V. and Sapozhnikov, Vl.V. (2003) “Logic Complement, a New Method of Checking the Combinational Circuits”, Automation and Remote Control, Vol. 1, no. 1, pp. 153-161.
    https://doi.org/10.1023/A:1021884727370
  27. Göessel, M., Ocheretny, V., Sogomonyan, E. and Marienfeld, D. (2008), New Methods of Concurrent Checking: Edition 1., Springer Science+Business Media B.V., Dordrecht, Netherlands.
  28. Das, D.K., Roy, S.S., Dmitiriev, A., Morozov, A.,\ and Gössel, M. (2012), “Constraint Don’t Cares for Optimizing Designs for Concurrent Checking by 1-out-of-3 Codes”, Proceedings of the 10th International Workshops on Boolean Problems, Freiberg, Germany, September, 2012, pp. 33—40.
  29. Berger, J.M. (1961), “A Note on Error Detection Codes for Asymmetric Channels”, Information and Control, Vol. 4, no. 1, рp. 68—73.
    https://doi.org/10.1016/S0019-9958(61)80037-5
  30. Sapozhnikov, V.V., Sapozhnikov, Vl.V., Efanov, D.V. and Dmitriev, V.V. (2017), “New Structures of the Concurrent Error Detection Systems for Logic Circuits”, Automation and Remote Control, Vol. 78, no. 2, pp. 300-312.
    https://doi.org/10.1134/S0005117917020096
  31. Zakrevskij, A., Pottosin, Yu. and Cheremisinova, L. (2009), Optimization in Boolean Space, TUT Press, Tallinn, Estonia.
  32. Efanov, D.V., Sapozhnikov, V.V. and Sapozhnikov, Vl.V. (2020), “Typical Structure of a Duplicate Error Correction Scheme with Code Control with Summation of Weighted Transitions”, Elektronne modelyuvannya, Vol. 42, no. 5, рp. 38—50. 
    https://doi.org/10.15407/emodel.42.05.038
  33. Efanov, D.V., Sapozhnikov, V.V. and Sapozhnikov, Vl.V. (2017), “Conditions for Detecting a Logical Element Fault in a Combination Device under Concurrent Checking Based on Berger’s Code”, Automation and Remote Control, Vol. 78, no. 5, pp. 891-901.
    https://doi.org/10.1134/S0005117917050113
  34. Efanov, D.V., Sapozhnikov, V.V. and Sapozhnikov, Vl.V. (2020), “Organization of a Fully Self-Checking Structure of a Combinational Device Based on Searching for Groups of Symmetrically Independent Outputs”, Automatic Control and Computer Sciences, Vol. 54, no. 4, рp. 279-290.
    https://doi.org/10.3103/S0146411620040045
  35. Sentovich, E.M., Singh, K.J., Moon, C.,  Savoj, H.,  Brayton, R.K. and Sangiovanni-Vincentelli, A. (1992), “Sequential Circuit Design Using Synthesis and Optimization”, Proceedings IEEE International Conference on Computer Design: VLSI in Computers & Processors, October 11-14, 1992, Cambridge, MA, USA, USA pp. 328-333. DOI: 1109/ ICCD.1992.276282.
  36. M. Sentovich, K. J. Singh, L. Lavagno et al. (1992), SIS: A System for Sequential Circuit Synthesis, Electronics Research Laboratory, Department of Electrical Engineering and Computer Science, University of California, pp. 45.
  37. Drozd, A., Kharchenko, V., Antoshchuk, S., Sulima, J. and Drozd, M. (2011), “Checkabi­lity of the Digital Components in Safety-Critical Systems: Problems and Solutions”, Proceedings of 9th IEEE East-West Design & Test Symposium (EWDTS’2011), Sevastopol, Ukraine, pp. 411-416.
    https://doi.org/10.1109/EWDTS.2011.6116606
  38. Drozd, A., Drozd, M., Martynyuk, O. and Kuznietsov, M. (2017), “Improving of a Circuit Checkability and Trustworthiness of Data Processing Results in LUT-based FPGA Components of Safety-Related Systems”, CEUR Workshop Proceedings, Vol. 1844, pp. 654-661, available at: http://ceur-ws.org/Vol-1844/10000654.pdf.
  39. Drozd, O., Perebeinos, I., Martynyuk, O., Zashcholkin, K., Ivanova, O. and Drozd, M. (2020), “Hidden Fault Analysis of FPGA Projects for Critical Applications”, Proceedings of the IEEE International Conference on Advanced Trends in Radioelectronics, Telecommunications and Computer Engineering (TCSET), February 25-29, 2020, Lviv-Slavsko, Ukraine.
    https://doi.org/10.1109/TCSET49122.2020.235591

Full text: PDF