Russian University of Transport (MIIT) ("Automation, Remote Control and Communication on Railway Transport" Department, Professor)
«Scientific Research and Design Institute «Transport and Construction Safety» LLC (General Director Deputy on Scientific Research Work)
Tashkent State Transport University ("Automation and Remote Control" Department, Professor)
Russian Federation
Russian Federation
UDK 681.518.5 Системы автоматического контроля и технической диагностики
When synthesizing self-checking digital devices based on Boolean correction of signals, it is proposed to use weight-based Bose – Lin codes, the construction principles of which imply preliminary weighting of data symbols by natural numbers. Two “basic” structures are proposed for the synthesis of built-in control circuits for groups of six outputs of the diagnostic object. The structures are based on weight-based Bose – Lin codes with summation in the residue ring modulo M=4. There are 15 such noise-protected codes with the number of data symbols m=4, which allows to select the best option as a base code in the builtin control circuit according to various criteria, including achieving self-checking properties even in cases where this cannot be achieved using traditional approaches, including duplication. Two algorithms for the synthesis of built-in control circuits based on Boolean signal correction have been developed, allowing the use of correction of only two of the six functions in the basic structure. For basic structures, there are 720 ways to construct an integrated control circuit based on Boolean correction of signals using each weight-based Bose – Lin code, which makes it possible to choose the best way to implement a self-checking device, considering various indicators (structural redundancy, testability, etc.). The operation of the algorithms is demonstrated on simple examples. The results of experiments with test digital circuits from the MCNC Benchmars set confirming the efficiency of the developed algorithms are given. It is shown that with a large number of outputs, there is an astronomical number of ways to organize built-in control circuits, which makes it possible to build self-checking devices with various characteristics. The use of Boolean correction of signals using weight-based Bose – Lin codes can be used in the development and design of self-checking digital devices on various element bases.
testing of digital circuits, self-checking device, built-in control circuit, Boolean signal correction, weighted code with summation, weighted Bose – Lin code
1. Sogomonyan E. S., Slabakov E. V. Samoproveryaemye ustrojstva i otkazoustojchivye sistemy. - M.: Radio i svyaz’, 1989. - 208 s.
2. Mitra S., McCluskey E. J. Which Concurrent Error Detection Scheme to Shoose? // Proceedings of International Test Conference, 2000, USA, Atlantic City, NJ, 03-05 October 2000. - Pp. 985-994. - DOI: 10.1109/ TEST.2000.894311.
3. Stempkovskij A. L., Tel’puhov D. V., ZHukova T. D., Demeneva A. I., Nadolenko V. V., Gurov S. I. Sintez skhemy funkcional’nogo kontrolya na osnove spektral’nogo R-koda s razbieniem vyhodov na gruppy // Mikroelektronika. - 2019. - T. 48. - № 4. - S. 284-294.
4. Stempkovsky A. L., Zhukova T. D., Telpukhov D. V., Gurov S. I. CICADA: A New Tool to Design Circuits with Correction and Detection Abilities // International Siberian Conference on Control and Communications (SIBCON), 13-15 May 2021, Kazan, Russia. - Pp. 1-5. - DOI:https://doi.org/10.1109/SIBCON50419.2021.9438900.
5. Sapozhnikov V. V., Sapozhnikov Vl. V., Efanov D. V. Teoriya sinteza samoproveryaemyh cifrovyh sistem na osnove kodov s summirovaniem. - SPb.: Lan’, 2021. - 580 s.
6. Sapozhnikov V. V., Sapozhnikov Vl. V. Samoproveryaemye diskretnye ustrojstva. - SPb.: Energoatomizdat, 1992, 224 s.
7. Piestrak S. J. Design of Self-Testing Checkers for Unidirectional Error Detecting Codes. - Wrocław: Oficyna Wydawnicza Politechniki Wrocłavskiej, 1995. - 111 p.
8. Ostanin S. A., Matrosova A. YU., Butorina N. B., Grebnev A. O. Sintez monotonnyh detektorov dlya podmnozhestva ravnovesnyh kodov // Izvestiya vuzov. Fizika. - 2016. - T. 59. - № 8-2. - S. 79-81.
9. Butorina N., Burkatovskaya Yu., Pakhomova E. On the Self-Testing (m, n)-code Checker Design // IOP Conference Series: Materials Science and Engineering, Volume 1019, 14th International Forum on Strategic Technology (IFOST 2019) 14th-17th October 2019, Tomsk, Russian Federation. - Pp. 336-340. - DOI:https://doi.org/10.1088/1757-899X/1019/1/012098.
10. Sapozhnikov V. V., Sapozhnikov Vl. V., Dmitriev A. V., Morozov A. V., Gessel’ M. Organizaciya funkcional’nogo kontrolya kombinacionnyh skhem metodom logicheskogo dopolneniya // Elektronnoe modelirovanie. - 2002. - Tom 24. - № 6. - S. 52-66.
11. Gessel’ M., Morozov A. V., Sapozhnikov V. V., Sapozhnikov Vl. V. Logicheskoe dopolnenie - novyj metod kontrolya kombinacionnyh skhem // Avtomatika i telemekhanika. - 2003. - № 1. - S. 167-176.
12. Gessel’ M., Morozov A. V., Sapozhnikov V. V., Sapozhnikov Vl. V. Kontrol’ kombinacionnyh skhem metodom logicheskogo dopolneniya // Avtomatika i telemekhanika. - 2005. - № 8. - S. 161-172.
13. Göessel M., Ocheretny V., Sogomonyan E., Marienfeld D. New Methods of Concurrent Checking: Edition 1. - Dordrecht: Springer Science+Business Media B. V., 2008. - 184 p.
14. Morosow, A., Sapozhnikov V. V., Sapozhnikov Vl. V., Goessel M. Self-Checking Combinational Circuits with Unidirectionally Independent Outputs // VLSI Design. - 1998. - Vol. 5. - Issue 4. - Pp. 333-345. - DOI:https://doi.org/10.1155/1998/20389.
15. Efanov D. V., Sapozhnikov V. V., Sapozhnikov Vl. V. Usloviya obnaruzheniya neispravnosti logicheskogo elementa v kombinacionnom ustrojstve pri funkNAZVANIE
16. Efanov D. V., Sapozhnikov V. V., Sapozhnikov Vl. V. 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. - 2020. - Vol. 54. - Issue 4. - Pp. 279-290. - DOI: 10.3103/ S0146411620040045.
17. Efanov D. V., Sapozhnikov V. V., Sapozhnikov Vl. V. Modificirovannye kody s summirovaniem vzveshennyh perekhodov v sistemah funkcional’nogo kontrolya kombinacionnyh skhem // Trudy Instituta sistemnogo programmirovaniya RAN. - 2017. - Tom 29. - № 5. - S. 39-60. - DOI: 10.15514/ ISPRAS-2017-29(5)-3.
18. Das D. K., Roy S. S., Dmitiriev A., Morozov A., Gössel M. 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.
19. Pivovarov D. V. Postroenie sistem funkcional’nogo kontrolya mnogovyhodnyh kombinacionnyh skhem metodom logicheskogo dopolneniya po ravnovesnym kodam // Avto-matika na transporte. - 2018. - Tom 4. - № 1. - S. 131-149.
20. Saposhnikov Vl. V., Dmitriev A., Goessel M., Saposhnikov V. V. Self-Dual Parity Checking - a New Method for on Line Testing // Proceedings of 14th IEEE VLSI Test Symposium, USA, Princeton, 1996. - Pp. 162-168.
21. Gessel’ M., Dmitriev A. V., Sapozhnikov V. V., Sapozhnikov Vl. V. Samotestiruemaya struktura dlya funkcional’nogo obnaruzheniya otkazov v kombinacionnyh skhemah // Avtomatika i telemekhanika. - 1999. - № 11. - S. 162-174.
22. Morozov M., Saposhnikov V. V., Saposhnikov Vl. V., Goessel M. New Self-Checking Circuits by Use of Berger-codes // Proceedings of 6th IEEE International On-Line Testing Workshop, Palma De Mallorca, Spain, 3-5 July 2000. - Pp. 171-176.
23. Efanov D. V., Pogodina T. S. Issledovanie svojstv samodvojstvennyh kombinacionnyh ustrojstv s kontrolem vychislenij na osnove kodov Hemminga // Informatika i avtomatizaciya. - 2023. - Tom 22. - № 2. - C. 349-392. - DOI:https://doi.org/10.15622/ia.22.2.5.
24. Efanov D. V. Osobennosti realizacii samoproveryaemyh struktur na osnove metoda invertirovaniya dannyh i linejnyh kodov // Vestnik Tomskogo gosudarstvennogo universiteta. Upravlenie, vychislitel’naya tekhnika i informatika. - 2023. - № 65. - S. 126-138. - DOI:https://doi.org/10.17223/19988605/65/13.
25. Freiman C. V. Optimal Error Detection Codes for Completely Asymmetric Binary Channels // Information and Control. - 1962. - Vol. 5, issue 1. - Pp. 64-71. - DOI:https://doi.org/10.1016/S0019-9958(62)90223-1.
26. Efanov D. V., Sapozhnikov V. V., Sapozhnikov Vl. V., Pivovarov D. V. The Synthesis Conditions of Completely Self-Testing Embedded-Control Circuits Based on the Boolean Complement Method to the «1-out-of-m» Constant-Weight Code // Automatic Control and Computer Sciences. - 2020. - Vol. 54. - Issue 2. - Pp. 89-99. - DOI:https://doi.org/10.3103/S0146411620020042.
27. Berger J. M. A Note on Error Detection Codes for Asymmetric Channels // Information and Control. - 1961. - Vol. 4, Issue 1. - Pp. 68-73. - DOI:https://doi.org/10.1016/S0019-9958(61)80037-5.
28. Carter W. C., Duke K. A., Schneider P. R. Self-Checking Error Checker for Two-Rail Coded Data // United States Patent Office, filed July 25, 1968, ser. No. 747533, patented Jan. 26, 1971, N. Y., 10 p.
29. Efanov D., Osadchy G., Zueva M. Special Aspects of Errors Definition via Sum Codes within Embedded Control Schemas Being Realized by Means of Boolean Complement Method // Proceedings of 11th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (IDAACS’2021), Vol. 1, Cracow, Poland, September 22-25, 2021. - Pp. 424-431. - DOI:https://doi.org/10.1109/IDAACS53288.2021.9660837.
30. Efanov D. V., Sapozhnikov V. V., Sapozhnikov Vl. V. The Self-Checking Concurrent Error-Detection Systems Synthesis Based on the Boolean Complement to the Bose - Lin Codes with the Modulo Value M=4 // Electronic Modeling. - 2021. - Vol. 43. - Issue 1. - Pp. 28-45. - DOI:https://doi.org/10.15407/emodel. 43.01.028.
31. Efanov D., Osadchy G., Zueva M. Specifics of Error Detection with Modular Sum Codes in Concurrent Error-Detection Circuits Based on Boolean Complement Method // Proceedings of 19th IEEE East-West Design & Test Symposium (EWDTS’2021), Batumi, Georgia, September 10-13, 2021. - Pp. 59-69. - DOI:https://doi.org/10.1109/EWDTS52692.2021.9581036.
32. Bose B., Lin D. J. Systematic Unidirectional Error-Detection Codes // IEEE Transaction on Computers. - Vol. C-34, Nov. 1985. - Pp. 1026-1032.
33. Das D., Touba N. A., Seuring M., Gossel M. Low Cost Concurrent Error Detection Based on Modulo Weight-Based Codes // Proceedings of the IEEE 6th International On-Line Testing Workshop (IOLTW), Spain, Palma de Mallorca, July 3-5, 2000. - Pp. 171-176. - DOI:https://doi.org/10.1109/OLT.2000.856633.
34. Sapozhnikov V. V., Sapozhnikov Vl. V., Efanov D. V. Ob odnom klasse kodov, prigodnyh dlya sinteza sistem funkcional’nogo kontrolya logicheskih ustrojstv // Vestnik Rostovskogo gosudarstvennogo universiteta putej soobshcheniya. - 2014. - № 2. - S. 48-58.
35. Aksyonova G. P. Neobhodimye i dostatochnye usloviya postroeniya polnost’yu proveryaemyh skhem svertki po modulyu 2 // Avtomatika i telemekhanika. - 1979. - № 9. - S. 126-135.
36. Sentovich E. M., Singh K. J., Moon C., Savoj H., Brayton R. K., Sangiovanni-Vincentelli A. Sequential Circuit Design Using Synthesis and Optimization // Proceedings IEEE International Conference on Computer Design: VLSI in Computers & Processors, 11-14 October 1992, Cambridge, MA, USA. - Pp. 328-333. - DOI:https://doi.org/10.1109/ICCD.1992.276282.
37. SIS: A System for Sequential Circuit Synthesis / E. M. Sentovich, K. J. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanha, H. Savoj, P. R. Stephan, R. K. Brayton, A. Sangiovanni-Vincentelli // Electronics Research Laboratory, Department of Electrical Engineering and Computer Science, University of California, Berkeley, 4 May 1992, 45 p.
38. Zakrevskij A. D., Pottosin YU. V., CHeremisinova L. D. Logicheskie osnovy proektirovaniya diskretnyh ustrojstv. - M.: Fizmatlit, 2007. - 592 s.
39. Efanov D. V. Sintez samoproveryaemyh kombinacionnyh ustrojstv na osnove metoda logicheskoj korrekcii signalov s primeneniem kodov Bouza - Lina // Informacionnye tekhnologii. - 2023. - Tom 29. - № 10. - S. 503-511. - DOI:https://doi.org/10.17587/it.29.503-511.
40. McElvain K. IWLS’93 Benchmark Set: Version 4.0. - Distributed as a part of IWLS’93 benchmark set, May 1993.
41. Collection of Digital Design Benchmarks. [Elektronnyj resurs]. URL: https://ddd. fit.cvut.cz/www/prj/Benchmarks/ (data obnovleniya: 10.02.2024).
42. Efanov D. V., Yelina Y. I. Synthesis of Concurrent Error-Detection Circuits Based on Boolean Signals Correction Using Modular Weight-Based Sum Codes // Proceedings of the 2024 Conference of Young Researchers in Electrical and Electronic Engineering (EICon), 29-30 January 2024, St. Petersburg, Russia. - Pp. 350-355.
