BOOLEAN COMPLEMENT METHOD BASED ON CONSTANT-WEIGHT CODE “1-OUT-OF-4” FOR FORMATION OF TOTALLY SELF-CHECKING CONCURRENT ERROR DETECTION SYSTEMS

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

Èlektron. model. 2017, 39(2):15-34
https://doi.org/10.15407/emodel.39.02.015

ABSTRACT

Authors offer the way of formalization of Boolean complement functions calculation rules in concurrent error detection systems based on constant-weight code “1-out-of-4”. Herewith the procedure of complement function values selection is excluded and the property of totally self-checking is provided – all the XOR gates in Boolean complement module and checker are checked by guarantee. The number of ways of completion of Boolean complement functions of “1-out-of-4” code with complement of three operational functions only is established as well as the minimum number of operational vectors needed for totally self-checking provision.

KEYWORDS

concurrent error detection system, Boolean complement, constant-weight code, “1-out-of-4” code, totally self-checking structure.

REFERENCES

1. Sogomonyan, E.S. and Slabakov, E.V. (1989), Samoproveryaemyye ustroystva i otkazoustoychivyye sistemy [Self-checking devices and fault-tolerant systems], Radio i svyaz, Moscow, USSR.
2. Drozd, A.V., Kharchenko, V.S., Antoshchuk, S.G. and et al. (2012), Rabocheye diagnostirovanie bezopasnykh informatsionno-upravlyayushchikh sistem [On-line testing for safe information-
control systems], N.E. Zhukovsky Natsionalny Aerokosmichesky Universistet «KhAI». Kharkov, Ukraine.
3. Kharchenko, V., Kondratenko, Yu., and Kacprzyk, J. (2017), Green IT engineering: concepts, models, complex systems architectures, Springer Book series: Studies in Systems, Decision and Control, DOI: 10.1007/978-3-319-44162-7.
https://doi.org/10.1007/978-3-319-44162-7
4. Mitra, S. and McCluskey, E.J. (2000), “Which concurrent error detection scheme to choose?”, Proceedings of International Test Conference 2000, Atlantic City, NJ, USA, October 03-05, 2000, pp. 985-994.
https://doi.org/10.1109/TEST.2000.894311
5. Slabakov, E.V. and Sogomonyan, E.S. (1980), “Formation of totally self-checking combinational devices with the use of constant-weight codes”, Avtomatika i telemekhanika, no. 9, pp. 173-181.
6. Slabakov, E.V. and Sogomonyan, E.S. (1981), “Self-checking computing devices and systems” (Review), Avtomatika i telemekhanika, no. 11, pp. 147-167.
7. Piestrak, S.J. (1995), Design of self-testing checkers for unidirectional error detecting codes, Oficyna Wydawnicza Politechniki Wrociavskiej, Wroc³aw, Poland.
8. Das, D. and Touba, N.A. (1999), “Synthesis of circuits with low-cost concurrent error detection based on Bose-Lin codes”, Journal of Electronic Testing: Theory and Applications, Vol. 15, iss. 1-2, pp. 145-155, DOI: 10.1023/A:1008344603814.
https://doi.org/10.1023/A:1008344603814
9. Nicolaidis, M., and Zorian, Y. (1998), “On-line testing for VLSI - a compendium of approaches”, Journal of Electronic Testing: Theory and Applications, no. 12, pp. 7-20.
https://doi.org/10.1023/A:1008244815697
10. Das, D. and Touba, N.A. (1999), “Weight-based codes and their application to concurrent error detection of multilevel circuits”, Proceedings of 17th IEEE Test Symposium, California, USA, pp. 370-376.
https://doi.org/10.1109/VTEST.1999.766691
11. Matrosova, A.Yu., Levin, I. and Ostanin, S.A. (2000), “Self-checking synchronous FSM network design with low overhead”, VLSI Design, Vol. 11, iss. 1, pp. 47-58, DOI:10.1155/2000/46578.
https://doi.org/10.1155/2000/46578
12. Das, D., Touba, N.A., Seuring, M. and Gossel, M. (2000), “Low cost concurrent error detection based on modulo weight-based codes”, Proceedings of IEEE 6th International On-Line Testing Workshop (IOLTW), Palma de Mallorca, Spain, July 3-5, 2000, pp. 171-176.
13. Matrosova, A., Levin, I. and Ostanin, S. (2001), “Survivable Self-Checking Sequential Circuits”, Proceedings of 2001 IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems (DFT 2001), CA, San Francisco, USA, October 24-26, 2001, pp. 395-402.
14. Blyudov, A.A., Efanov, D.V., Sapozhnikov, V.V. and Sapozhnikov, Vl.V. (2014), “On codes with summation of data bits in concurrent error detection systems”, Avtomatika i telemekhanika, no. 8, pp. 131-145.
https://doi.org/10.1134/S0005117914080098
15. Sapozhnikov, V.V. and et al. (2002), “Organization of functional checking of combinational circuits by the logic complementmethod”, Elektronnoe modelirovanie, Vol. 24, no. 6, pp. 52-66.
16. Parkhomenko, P.P. and Sogomonyan, E.S. (1981), Osnovy tekhnicheskoy diagnostiki (optimizatsiya algoritmov diagnostirovaniya, apparaturnyye sredstva) [Basics of technical diagnostics (optimization of diagnostic algorithms and equipment)], Energoatomizdat, Moscow, Russia.
17. Goessel, M., Morozov, A.V., Sapozhnikov, V.V. and Sapozhnikov, Vl.V. (2003), “Logic complement, a new method of checking the combinational circuits”, Avtomatika i telemekhanika, no. 1, pp. 167-176.
18. Goessel, M., Morozov, A.V., Sapozhnikov, V.V. and Sapozhnikov, Vl.V. (2005), “Checking combinational circuits by the method of logic complement”, Avtomatika i telemekhanika, no. 8, pp. 161-172.
https://doi.org/10.1007/s10513-005-0174-2
19. Berger, J.M. (1961), “À note on error detecting codes for asymmetric channels”, Information and Control, Vol. 4, iss. 1, pp. 68-73, DOI: 10.1016/S0019-9958(61)80037-5.
https://doi.org/10.1016/S0019-9958(61)80037-5
20. Bose, B. and Lin, D.J. (1985), “Systematic unidirectional error-detection codes”, IEEE Transactions on Computers, vol. C-34, pp. 1026-1032.
21. Sapozhnikov, V.V. and Sapozhnikov, Vl.V. (1992), “Self-checking checkers for constant-weight codes”, Avtomatika i telemekhanika, no. 3, pp. 3-35.
22. Göessel, M., Sapozhnikov, Vl., Sapozhnikov, V. and Dmitriev, A. (2000), “A new method for concurrent checking by use of a 1-out-of-4 code”, Proceedings of the 6th IEEE International On-line Testing Workshop, Palma de Mallorca, Spain, July 3-5, 2000, pp. 147-152.
https://doi.org/10.1109/OLT.2000.856627
23. Morozov, A., Sapozhnikov, V.V., Sapozhnikov, Vl.V. and Göessel, M. (2000), “New selfchecking circuits by use of Berger-codes”, Proceedings of the 6th IEEE International On-line Testing Workshop, Palma de Mallorca, Spain, July 3-5, 2000, pp. 171-176.
24. Sapozhnikov, V.V. and et al. (2004), “Design of totally self-checking combinational circuits by use of complementary circuits”, Proceedings of East-West Design and Test Workshop, Yalta, Ukraine, 2004, pp. 83-87.
25. Göessel, M., Ocheretny, V., Sogomonyan, E. and Marienfeld, D. (2008), New methods of concurrent checking: Edition 1, Springer Science+Business Media B.V., Dodrecht, Germany.
26. Sen, S.K. (2010), “A self-checking circuit for concurrent checking by 1-out-of-4 code with design optimization using constraint don’t cares”, Proceedings of National Conf. on Emerging
Trends and Advances in Electrical Engineering and Renewable Energy (NCEEERE 2010), December 22-24, 2010, Manipal Institute of Technology, Sikkim, India.
27. 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, September, 2012, Freiberg, Germany, pp. 33-40.
28. Sapozhnikov, V.V., Sapozhnikov, Vl.V. and Efanov, D.V. (2016), “Method of logical devices concurrent error detection system based on “2-out-of-4” code”, Izvestiya vuzov. Priborostroenie, Vol. 59, no. 7, pp. 524-533, DOI 10.17586/0021-3454-2016-59-7-524-533.
29. Efanov, D., Sapozhnikov, V. and Sapozhnikov, Vl. (2016), “Methods of organization of totally self-checking concurrent error detection system on the basis of constant-weight «1-outof-3»-code”, Proceedings of 14th IEEE East-WestDesign and Test Symposium (EWDTS’2016), October 14-17, 2016, Armenia, Yerevan, pp. 117-125, DOI: 10.1109/EWDTS.2016.7807622.
https://doi.org/10.1109/EWDTS.2016.7807622
30. 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”, Proceedings of 14th IEEE East-West Design and Test Symposium (EWDTS'2016). October 14-17, 2016, Yerevan, Armenia, pp. 126-133, DOI: 10.1109/EWDTS.2016.7807677.
https://doi.org/10.1109/EWDTS.2016.7807677
31. Sapozhnikov, V.V., Sapozhnikov, Vl.V. and Efanov, D.V. (2016), “Formation of totally self-checking structures of concurrent error detection systems with use of constant-weight code “1-out-of-3”, Elektronnoe modelirovanie, Vol. 38, no. 6, pp. 25-43.
https://doi.org/10.15407/emodel.38.06.025
32. Sapozhnikov, V.V., Sapozhnikov, Vl.V. and Efanov, D.V. (2017), “Design of self-checking concurrent error detection systems based on «2-out-of-4» constant-weight code”, Problemy upravleniya, iss. 1, pp. 57-64.
33. Sapozhnikov, V.V. and Sapozhnikov, Vl.V. (1992), Samoproveryaemye diskretnye ustroystva [Self-checking discrete devices], Energoatomizdat, St. Petersburg, Russia.
34. Carter, W.C., Duke, K.A. and Schneider, P.R. (1971), Self-checking error checker for two-rail coded data, United States Patent Office, filed July 25, 1968, ser. No. 747, 533, patented Jan. 26, N. Y., USA.
35. Huches, J.L.A., McCluskey, E.J. and Lu, D.J. (1984), “Design of totally self-checking comparators with an arbitrary number of inputs”, IEEE Transactions on Computers, Vol. C-33, no. 6, pp. 546-550.
https://doi.org/10.1109/TC.1984.1676478
36. Sapozhnikov, V.V. and Rabara, B. (1982), “Universal algorithm of 1/n-checkers synthesis”, Problemy peredachi informatsii, Vol. 18, iss. 3, pp. 62-73.
37. Aksyonova, G.P. (1979), “Necessary and sufficient conditions for the design of totally checking circuits of compression by modulo 2”, Avtomatika i telemekhanika, no. 9, pp. 126-135.
38. Aksyonova, G.P. (2008), “On functional diagnosis of discrete devices under imperfect data processing conditions”, Problemy upravleniya, iss. 5, pp. 62-66.
39. Collection of Digital Design Benchmarks [URL: http://ddd.fit.cvut.cz/prj/Benchmarks/].
40. Sentovich, E.M., Singh, K.J., Lavagno, L., Moon, C., Murgai, R., Saldanha, A., Savoj, H., Stephan, P.R., Brayton, R.K. and Sangiovanni-Vincentelli, A. (1992), SIS: A system for sequential circuit synthesis, Electronics Research Laboratory, Department of Electrical Engineering and Computer Science, University of California, Berkeley, USA.

Full text: PDF (in Russian)