2. Home
  3. ARCHIVE
  4. 2020
  5. VOL 42, NO 3 (2020)
  6. pp. 27-52

THE METHOD OF THE CONCURRENT ERROR-DETECTION OF COMBINATIONAL LOGIC DEVICES BASED ON THE SELF-DUAL COMPLEMENT TO CONSTANT-WEIGHT CODE

D.V. Efanov, V.V. Sapozhnikov, Vl.V. Sapozhnikov, D.V. Pivovarov

Èlektron. model. 2020, 42(3):27-55
https://doi.org/10.15407/emodel.42.03.027

ABSTRACT

The article proposes a method of the organization of concurrent error-detection (CED) systems, which combines the checkout of the generated code words belonging to the pre-selected constant-weight code and the checkout of each function belonging to the class of self-dual functions. The described method of the CED systems organization allows to increase the detection ability in comparison with the checkout by the method of Boolean complement to the constant-weight codes or to the self-dual functions. The article shows that only constant-weight codes with the same number of zero and ones bits (the so-called «r-out-of-2r» codes, where r is the weight of the code word) can be used in the organization of the combinational logic devices control according to the developed method. The priority in the CED systems organization is given to the constant-weight «2-out-of-4» code. The article develops algorithms for the synthesis of CED systems, the structures of which are completely self-checking in relation to the single stuck-at faults of the outputs of the internal logic elements. The simulation results of the CED system operation on the example of an random combinational logic device showed the high efficiency of the developed method.

KEYWORDS

combinational logic device, concurrent error-detection system, technical state control, fault detection, self-dual complement, constant-weight codes, «2-out-of-4» code.

REFERENCES

  1. Ubar, R., Raik, J., and Vierhaus, H.-T. (2011), Design and Test Technology for Dependable Systems-on-Chip (Premier Reference Source), Information Science Reference. Hershey – New York: IGI Global, USA.
    https://doi.org/10.4018/978-1-60960-212-3
  2. Drozd, A.V., Kharchenko, V.S., Antoshchuk, S.G., and etc. (2012) Rabochee diagnostirovanie bezopasnykh informatsionno-upravljayustchikh sistem [Objects and Methods of On-Line Testing for Safe Instrumentation and Control Systems]. Kharkov, National Aerospace University "KhAI", Ukraine.
  3. Kharchenko, V., Kondratenko, Yu., and Kacprzyk, J. Green IT Engineering: Concepts, Models, Complex Systems Architectures. Springer Book series "Studies in Systems, Decision and Control".  2017, Vol. 74, 305 p.
    https://doi.org/10.1007/978-3-319-44162-7
  4. Lala, P.K. (2001) “Self-Checking and Fault-Tolerant Digital Design”, San Francisco: Morgan Kaufmann Publishers, USA.
  5. Parkhomenko, P.P., and Sogomonyan, E.S. (1981) Osnovy tekhnicheskoj diagnostiki (optimizatsija algoritmov diagnostirovanija, apparaturnyje sredstva) [Basics of technical diagnostics (optimization of diagnostic algorithms and equipment)], Energoatomizdat, Moscow, USSR.
  6. Sogomonyan, E.S., and Slabakov, E.V. (1989) Samoproverjaemyje ustrojstva i otkazoustojchivyje sistemy [Self-checking devices and failover systems], Radio & Svjaz`, Moscow, USSR.
  7. Goessel, M., and Graf, S. (1994) “Error Detection Circuits”, London: McGraw-Hill, UK.
  8. Nicolaidis, M., and Zorian, Y. (1998) “On-Line Testing for VLSI – А Compendium of Approaches”, Journal of Electronic Testing: Theory and Applications, 1998, no. 12, pp. 7-20.
    https://doi.org/10.1023/A:1008244815697
  9. Mitra, S., and McCluskey, E.J. (2000) “Which Concurrent Error Detection Scheme to Сhoose?”, Proc. of International Test Conference, 2000. USA, Atlantic City, NJ, 3-5 October 2000, pp. 985—994. DOI: 1109/TEST.2000.894311.
  10. Gavrilov, S.V., Tel'puhov, D.V., Zhukova, T.D., and Gurov, S.I. (2018) “Ispol'zovanie informacionnoj izbytochnosti pri postroenii sboeustojchivyh kombinacionnyh skhem” [Synthesis of fault-tolerant combination schemes by introducing information redundancy], Tavricheskij vestnik informatiki i matematiki, 2018, Vol. 2, Issue 39, pp. 29—44.
  11. Bennetts, R.G. (1990) Proektirovanie testoprigodnyh logicheskih skhem [Design of Testable Logic Circuits]. Moscow, Radio & Svjaz`, Moscow, USSR.
  12. Ryan, W.E., and Lin, S. (2009) Channel Codes: Classical and Modern. Cambridge University Press, UK.
    https://doi.org/10.1017/CBO9780511803253
  13. Göessel, M., Ocheretny, V., Sogomonyan, E., and Marienfeld, D. (2008) New Methods of Concurrent Checking: Edition 1. – Dordrecht: Springer Science+Business Media B.V., Netherlands.
  14. Sapozhnikov, V.V., Sapozhnikov, Vl.V., Efanov, D.V., and Dmitriev, V.V. (2017) “Novye struktury sistem funkcional'nogo kontrolya logicheskih skhem” [New structures of the concurrent error detection systems for logic circuits], Avtomatika i telemekhanika, no. 2, pp. 127—143.
  15. Dong, H. (1984) “Modified Berger Codes for Detection of Unidirectional Errors”, IEEE Transaction on Computers, 1984, Vol. C-33, рp. 572—575.
    https://doi.org/10.1109/TC.1984.1676484
  16. Piestrak, S.J. (1995) Design of Self-Testing Checkers for Unidirectional Error Detecting Codes. – Wrocław: Oficyna Wydawnicza Politechniki Wrocłavskiej, Poland.
  17. Das, D., Touba, N.A., Seuring, M., and Gossel, M. (2000) “Low Cost Concurrent Error Detection Based on Modulo Weight-Based Codes”, Proc. of IEEE 6th International On-Line Testing Workshop (IOLTW). Spain, Palma de Mallorca, July 3-5, 2000, pр. 171—176. DOI: 1109/OLT.2000.856633.
  18. Gallager, R.G. (2008) “Principles of Digital Communication”, Cambridge University Press, UK.
    https://doi.org/10.1017/CBO9780511813498
  19. Piestrak, S.J., and Patronik, P. (2014) “Design of Fault-Secure Transposed FIR Filters Protected Using Residue Codes”, 17th Euromicro Conference on Digital System Design, 27-29 August 2014, Verona, Italy, pp. 575-582.
    https://doi.org/10.1109/DSD.2014.110
  20. Tel'puhov, D.V., Demeneva, A.I., Zhukova, T.D., and Hrushchev, N.S. (2018) “Issledovanie i razrabotka sistem avtomatizirovannogo proektirovaniya skhem funkcional'nogo kontrolya kombinacionnyh logicheskih ustrojstv” [The Research and Development of Automation Systems for the Concurrent Error Detection Combinational Circuits], Elektronnaya tekhnika. Seriya 3: Mikroelektronika, 2018, Issue 1, pp. 15—22.
  21. Stempkovskiy, A., Telpukhov, D., Gurov, S. et al. (2018) “R-code for concurrent error detection and correction in the logic circuits”, 2018 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus), 29 January – 1 February 2018, Moscow, Russia, pp. 1430-1433.
    https://doi.org/10.1109/EIConRus.2018.8317365
  22. Sapozhnikov, V.V., Sapozhnikov, Vl.V., and Efanov, D.V. (2018) “Kody Hemminga v sistemah funkcional'nogo kontrolya logicheskih ustrojstv” [Hamming codes in concurrent error detection systems of logic devices], St. Petersburg, Nauka, 2018, 151 p.
  23. Yablonskij, S.V. (2003) “Vvedenie v diskretnuyu matematiku: Ucheb. posobie dlya vuzov” [Introduction to Discrete Mathematics: Textbook], Pod red. V.A. Sadovnicheva, 4-e izd., ster. M.: «Vysshaya shkola», Russia.
  24. Sapozhnikov, V.V., Sapozhnikov, Vl.V., and Gossel', M. (2001) “Samodvojstvennye disk­retnye ustrojstva” [Self-Dual Discrete Devices], St. Petersburg: Energoatomizdat, Russia.
  25. Sapozhnikov, V.V., Sapozhnikov, Vl.V., and Valiev R.Sh. (2006) “Sintez samodvojst­ven­nyh diskretnyh sistem” [Synthesis of Self-Dual Discrete Systems], St. Petersburg, Elmor, Russia.
  26. Efanov, D., Sapozhnikov, V., Sapozhnikov, Vl. et al. (2019) “Self-Dual Complement Method up to Constant-Weight Codes for Arrangement of Combinational Logical Circuits Concurrent Error-Detection Systems”, Proc. of 17th IEEE East-West Design & Test Symposium (EWDTS`2019), Batumi. Georgia, September 13-16, 2019, pp. 136-143.
    https://doi.org/10.1109/EWDTS.2019.8884398
  27. Goessel M., Morozov A.V., Sapozhnikov V.V., and Sapozhnikov Vl.V. (2003) “Logicheskoe dopolnenie – novyj metod kontrolya kombinacionnyh skhem” [Logic Complement, a New Method of Checking the Combinational Circuits], Avtomatika i tele­mekhanika, [Automation and Remote Control], no. 1, pp. 167—176.
  28. Morozov, A., Gössel, М., Saposhnikov, V., Saposhnikov, Vl. (2004) “Complementary Circuits for On-Line Detection for 1-out-of-3 Codes”, ARCS 2004 – Organic and Pervasive Computing, Workshops Proceedings. March 26, 2004, Augsburg, Germany, pp. 76—83.
  29. Goessel M., Morozov A.V., Sapozhnikov V.V., and Sapozhnikov Vl.V. (2005) “Kontrol' kombinacionnyh skhem metodom logicheskogo dopolneniya” [Checking Combinational Circuits by the Method of Logic Complement], Avtomatika i telemekhanika, [Automation and remote Control], 2005, no. 8, pp. 161—172.
  30. Sen, S.K., and Roy, S.S. (2008) “An Optimized Concurrent Self-Checker Using Constraint-Don’t Cares and 1-out-of-4 Code”, National Conference (AECDISC-2008) in Asansol Engineering College, held during 1-2 August 2008.
  31. Das D.K., Roy S.S., Dmitiriev A. et al (2012) “Constraint Don’t Cares for Optimizing Designs for Concurrent Checking by 1-out-of-3 Codes”, Proc. of the 10th International Workshops on Boolean Problems. Freiberg, Germany, September, 2012, pp. 33—40.
  32. Sapozhnikov V., Sapozhnikov Vl., and Efanov D. (2016) “Postroenie polnost'yu samopro­veryaemyh struktur sistem funkcional'nogo kontrolya s ispol'zovaniem ravnovesnogo koda «1 iz 3»” [Formation of Totally Self-Checking Structures of Concurrent Error Detection Systems With Use of Constant-Weight Code “1-out-of-3”], Elektronnoe modelirovanie. 2016, vol. 38, no. 6, pp. 25—43.
  33. Sapozhnikov, V.V., Sapozhnikov, Vl.V., Efanov, D.V., and Pivovarov, D.V. (2017) “Metod logicheskogo dopolneniya na osnove ravnovesnogo koda «1 iz 4» dlya postroeniya polnost'yu samoproveryaemyh struktur sistem funkcional'nogo kontrolya” [Boolean Complement Method Based on Constant-Weight Code “1-out-of-4” for Formation of Totally Self-Checking Concurrent Error Detection Systems], Elektronnoe modelirovanie, 2017, 39, Issue 2, pp. 15—34.
  34. Sapozhnikov, V.V., Sapozhnikov, Vl.V., Efanov, D.V., and Pivovarov, D.V. (2017) “Sintez sistem funkcional'nogo kontrolya mnogovyhodnyh kombinacionnyh skhem na osnove metoda logicheskogo dopolneniya” [Synthesis of Concurrent Error Detection Systems of Multioutput Combinational Circuits Based on Boolean Complement Method], Vestnik Tomskogo gosudarstvennogo universiteta. Upravlenie, vychislitel'naya tekhnika i informatika, 2017, Issue 4, pp. 69—80.
    https://doi.org/10.17223/19988605/41/9
  35. Morozov A., Saposhnikov V.V., Saposhnikov Vl.V., and Goessel M. (2000) “New Self-Checking Circuits by Use of Berger-codes”, Proceedings of the 6th IEEE International On-line Testing Workshop, 3-5 July 2000, Palma de Mallorca, Spain, pp. 171—176.
    https://doi.org/10.1109/OLT.2000.856626
  36. Reynolds, D.A., and Meize, G. (1978) “Fault Detection Capabilities of Alternating Logic”, IEEE Transactions on Computers, 1978, Vol. C-27, Is. 12, рp. 1093—1098.
    https://doi.org/10.1109/TC.1978.1675011
  37. Gessel', M., Dmitriev, A.V, Sapozhnikov, V.V, and Sapozhnikov, Vl.V. (1999) “Samotes­tirue­maya struktura dlya funkcional'nogo obnaruzheniya otkazov v kombinacionnyh skhe­mah [A Functional Fault-Detection Self-Test for Combinational Circuits], Avtomatika i telemekhanika, 1999, Issue 11, pp. 162—174.\
  38. Carter, W.C., Duke, K.A., and Schneider, P.R. (1968) “Self-Checking Error Checker for Two-Rail Coded Data”, United States Patent Office, filed July 25, 1968, ser. No. 747533, patentedJan. 26, 1971, NY., 10 p.
  39. 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], St.Petersburg, Izd-vo «Lan'», Russia.
  40. Sapozhnikov V.V., and Sapozhnikov Vl.V. (1992) “Samoproveryaemye testery dlya ravnovesnyh kodov” [Self-Checking Constant-Weight Codes Checkers], Avtomatika i telemekhanika, 1992, no. 3, pp. 3―35.
  41. Sapozhnikov, V., Sapozhnikov, Vl., and Efanov, D. (2016) “Concurrent Error Detection of Combinational Circuits by the Method of Boolean Complement on the Base of «2-out-of-4» Code”, Proc. of 14th IEEE East-West Design & Test Symposium (EWDTS`2016). Yerevan, Armenia, October 14-17, 2016, pp. 126-133. 
    https://doi.org/10.1109/EWDTS.2016.7807677
  42. Aksjonova, G.P. (1979), “Neobkhodimije i dostatochnyje uslovija postroenija polnost`ju proverjaemykh shem svjortki po modulju 2” [Necessary and sufficient conditions for the design of totally checking circuits of compression by modulo 2], Avtomatika i Telemekhanika [Automation and Remote Control], 1979, no. 9, pp. 126-135.
  43. Sapozhnikov V.V., Sapozhnikov Vl.V., and Efanov D.V. (2015) “Klassifikatsija oshibok v informatsionnykh vektorakh sistematicheskikh kodov” [Errors Classification in Information Vectors of Systematic Codes], Izvestiya Vysshikh Uchebnykh Zavedeniy. Priborostroenie, 2015, vol. 58, no. 5, pp. 333—343. 
    https://doi.org/10.17586/0021-3454-2015-58-5-333-343

Full text: PDF