SYNTHESIS OF BUILT-IN CONTROL CIRCUITS FOR COMBINATIONAL DIGITAL DEVICES BASED ON BOOLEAN SIGNALS CORRECTION USING POLYNOMIAL CODES
Abstract and keywords
Abstract (English):
It is proposed to use Boolean correction of signals when synthesizing built-in control circuits in the structures of self-checking digital devices, taking into account the characteristics of error detection by polynomial codes. It is shown that the built-in control circuit can be organized by selecting subsets of convertible and non-convertible outputs. In this case, the number of transformation elements in the control circuit can be minimized and equal to the number of check symbols in the selected polynomial code. Conditions have been established for the synthesis of fully self-checking built-in control circuits based on Boolean signals correction using polynomial codes. Algorithms for the synthesis of built-in control circuits have been developed that allow solving the problem of their organization, taking into account the topology features of the diagnostic object itself and the characteristics of error detection in data symbols using polynomial codes. Also, when synthesizing embedded control circuits, the characteristics of error detection in the entire codeword by polynomial codes can be taken into account. Polynomial codes can be effectively used in the synthesis of built-in control circuits based on Boolean signals correction, which makes it possible to synthesize self-checking digital devices with the least complexity of technical implementation. The presented results should be taken into account in the development of devices and systems of critical application

Keywords:
self-checking digital devices, built-in control circuit, combination devices of automation and computer technology, Boolean signals correction, polynomial codes
Text
Publication text (PDF): Read Download
References

1. Sogomonyan E. S., Slabakov E. V. Samoproveryaemye ustrojstva i otkazoustojchivye sistemy. M.: Radio i svyaz’, 1989. 208 s. (In Russian)

2. Lala P. K. Self-Checking and Fault-Tolerant Digital Design. San Francisco: Morgan Kaufmann Publishers, 2001. 216 p.

3. Drozd A., Kharchenko V., Antoshchuk S., et al. Checkability of the Digital Components in Safety-Critical Systems: Problems and Solutions // Proceedings of 9th IEEE East-West Design & Test Symposium (EWDTS’2011), Sevastopol, Ukraine, 2011. P. 411–416, DOI:https://doi.org/10.1109/EWDTS.2011.6116606.

4. Drozd O., Perebeinos I., Martynyuk O., et al. Hidden Fault Analysis of FPGA Projects for Critical APlications // Proceedings of the IEEE International Conference on Advanced Trends in Radioelectronics, Telecommunications and Computer Engineering (TCSET), 25–29 February 2020, Lviv-Slavsko, Ukraine, P. 142, DOI:https://doi.org/10.1109/TCSET49122.2020.235591.

5. Kharchenko V., Tyurin S., Fesenko H., et al. The Fault Tolerant Černý Finite State Machine: A Concept and VHDL Models // Proceedings of 11th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and APlications (IDAACS’2021), Vol. 2, Cracow, Poland, September 22–25, 2021. P. 1163–1169, DOI:https://doi.org/10.1109/IDAACS53288.2021.9660925.

6. Sapozhnikov V. V., Sapozhnikov Vl. V., Dmitriev A. V., et al. Organizaciya funkcional’nogo kontrolya kombinacionnyh skhem metodom logicheskogo dopolneniya // Elektronnoe modelirovanie. 2002. T. 24. № 6. S. 52–66. (In Russian)

7. Gessel’ M., Morozov A. V., Sapozhnikov V. V., et al. Logicheskoe dopolnenie — novyj metod kontrolya kombinacionnyh skhem // Avtomatika i telemekhanika. 2003. № 1. S. 167–176. (In Russian)

8. 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.

9. Piestrak S. J. Design of Self-Testing Checkers for Unidirectional Error Detecting Codes. Wrocław: Oficyna Wydawnicza Politechniki Wrocłavskiej, 1995, 111 p.

10. Sapozhnikov V. V., Sapozhnikov Vl. V., Efanov D. V. Kody Hemminga v sistemah funkcional’nogo kontrolya logicheskih ustrojstv: monografiya. SPb.: Nauka, 2018. 151 s. (In Russian)

11. Sapozhnikov V. V., Sapozhnikov Vl. V., Efanov D. V. Kody s summirovaniem dlya sistem tekhnicheskogo diagnostirovaniya. T. 1: Klassicheskie kody Bergera i ih modifikacii. M.: Nauka, 2020. 383 s. (In Russian)

12. Sapozhnikov V. V., Sapozhnikov Vl. V., Efanov D. V. Kody s summirovaniem dlya sistem tekhnicheskogo diagnostirovaniya. T. 2: Vzveshennye kody s summirovaniem. M.: Nauka, 2021. 455 s. (In Russian)

13. Sapozhnikov V. V., Sapozhnikov Vl. V. Samoproveryaemye diskretnye ustrojstva. SPb: Energoatomizdat, 1992. 224 s. (In Russian)

14. Freiman C. V. Optimal Error Detection Codes for Completely Asymmetric Binary Channels // Information and Control. 1962. Vol. 5, iss. 1. P. 64–71. DOI: 10.1016/ S0019-9958(62)90223-1.

15. Borden J. M. Optimal Asymmetric Error Detecting Codes // Information and Control. 1982. Vol. 53, Issue 1–2. P. 66–73. DOI:https://doi.org/10.1016/S0019-9958(82)91125-1.

16. Berger J. M. A Note on Error Detection Codes for Asymmetric Channels // Information and Control. 1961. Vol. 4, iss. 1. P. 68–73. DOI: 10.1016/ S0019-9958(61)80037-5.

17. Hamming R. W. Error Detecting and Correcting Codes // Bell System Technical Journal. 1950. 29 (2). P. 147–160. DOI:https://doi.org/10.1002/j.1538-7305.1950. tb00463.x.

18. Saposhnikov V. V., Saposhnikov Vl. V., Morozov A., et al. Design of Totally Self-Checking Combinational Circuits by Use of Complementary Circuits // Proceedings of 2th IEEE East-West Design & Test Symposium (EWDTS’2004), Crimea, Ukraine, September 15–17, 2004. P. 83–87.

19. Göessel M., Ocheretny V., Sogomonyan E., et al. New Methods of Concurrent Checking: Edition 1. Dordrecht: Springer Science+Business Media B. V. 2008. 184 p.

20. Sen S. K. A Self-Checking Circuit for Concurrent Checking by 1‑out-of‑4 code with Design Optimization using Constraint Don’t Cares // National Conference on Emerging trends and advances in Electrical Engineering and Renewable Energy (NCEEERE 2010), Sikkim Manipal Institute of Technology, Sikkim, held during 22–24 December, 2010.

21. Das D. K., Roy S. S., Dmitiriev A., et al. 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. P. 33–40.

22. Morozov M., Saposhnikov V. V., Saposhnikov Vl. V., Goessel M. New Self-Checking Circuits by Use of Berger-Sodes // Proceedings of 6th IEEE International On-Line Testing Workshop, Palma de Mallorca, Spain, 3–5 July 2000. P. 171–176.

23. 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, iss. 1. P. 28–45. DOI:https://doi.org/10.15407/emodel.43.01.028.

24. Efanov D. V., Pivovarov D. V., Osadchij G. V., et al. Primenenie kodov s effektivnym obnaruzheniem oshibok v oblasti maloj kratnosti pri sinteze skhem vstroennogo kontrolya po metodu logicheskogo dopolneniya // Informacionnye tekhnologii. 2022. T. 28, № 6. S. 283–293. DOI:https://doi.org/10.17587/it.28.283- 293. (In Russian)

25. Sogomonyan E. S., Gössel M. Design of Self-Testing and On-Line Fault Detection Combinational Circuits with Weakly Independent Outputs // Journal of Electronic Testing: Theory and APlications. 1993. Vol. 4, iss. 4. P. 267–281. DOI:https://doi.org/10.1007/BF00971975.

26. Busaba F. Y., Lala P. K. Self-Checking Combinational Circuit Design for Single and Uni-directional Multibit Errors // Journal of Electronic Testing: Theory and APlications. 1994. Vol. 5, Issue 1. P. 19–28. DOI:https://doi.org/10.1007/BF00971960.

27. Saposhnikov V. V., Morosov A., Saposhnikov Vl. V., et al. A New Design Method for Self-Checking Unidirectional Combinational Circuits // Journal of Electronic Testing: Theory and APlications. 1998. Vol. 12, iss. 1–2. P. 41–53. DOI:https://doi.org/10.1023/A:1008257118423.

28. Morosow A., Saposhnikov V. V., Saposhnikov Vl. V., et al. Self-Checking Combinational Circuits with Unidirectionally Independent Outputs // VLSI Design. 1998. Vol. 5, iss. 4. P. 333–345. DOI:https://doi.org/10.1155/1998/20389.

29. Matrosova A. Yu., Levin I., Ostanin S. A. Self-Checking Synchronous FSM Network Design with Low Overhead // VLSI Design. 2000. Vol. 11, iss. 1. P. 47– 58. DOI:https://doi.org/10.1155/2000/46578.

30. Sellers F. F., Hsiao M.-Y., Bearnson L. W. Error Detecting Logic for Digital Computers. New York: McGraw-Hill, 1968. 295 p.

31. Ryan W. E., Lin S. Channel Codes: Classical and Modern, Cambridge University Press, 2009. 692 p.

32. Sagalovich Yu. L. Vvedenie v algebraicheskie kody. — In-t problem peredachi informacii im. A. A. Harkevicha Rossijskoj akademii nauk. 2‑e izd., pererab. i dop. M.: IPI RAN, 2010. 302 s. (In Russian)

33. Efanov D. V., Cherepanova M. R. Primenenie polinomial’nyh kodov pri organizacii sistem funkcional’nogo kontrolya kombinacionnyh skhem // Materialy XIV mezhdunarodnoj konferencii imeni A. F. Terpugova “Informacionnye tekhnologii i matematicheskoe modelirovanie (ITMM‑2015)” (18–22 noyabrya 2015 g.). Tomsk: Izd-vo Tom. un-ta, 2015: Ch. 2, s. 133–138. (In Russian)

34. Gavrilov S. V., Zhukova T. D., Ryzhova D. I. Metody optimizacii skhem kodirovaniya na osnove diagramm dvoichnyh reshenij dlya sinteza otkazoustojchivyh mikro- i nanoelektronnyh skhem // Problemy razrabotki perspektivnyh mikroi nanoelektronnyh sistem (MES). 2016. № 4. S. 158–165. (In Russian)

35. Borchert C., Schirmeier H., Spinczyk O. Generic Soft-Error Detection and Correction for Concurrent Data Structures // IEEE Transactions on Dependable and Secure Computing. 2017. Vol. 14, iss. 1. P. 22–36. DOI: 10.1109/ TDSC.2015.2427832.

36. Li J., Liu S., Reviriego P., et al. Scheme for Periodical Concurrent Fault Detection in Parallel CRC Circuits // IET Computers & Digital Techniques. 2020. Vol. 14, Issue 2. P. 80–85. DOI:https://doi.org/10.1049/iet-cdt.2018.5183.

37. Abdullaev R. B., Efanov D. V., Sapozhnikov V. V., et al. Polynomial Code with Detecting the Symmetric and Asymmetric Errors in the Data Vectors // Proceedings of 17th IEEE East-West Design & Test Symposium (EWDTS’2019), Batumi, Georgia, September 13–16, 2019. P. 157–161. DOI: 10.1109/ EWDTS.2019.8884451.

38. Abdullaev R., Efanov D. Polynomial Codes Properties APlication in Concurrent Systems of Combinational Logic Devices // Proceedings of 19th IEEE East-West Design & Test Symposium (EWDTS’2021), Batumi, Georgia, September 10–13, 2021. P. 40–46. DOI: 10.1109/ EWDTS52692.2021.9580992.

39. Efanov D. V., Abdullaev R. B., Leskovec I. V. Primenenie polinomial’nyh kodov pri sinteze skhem vstroennogo kontrolya dlya kombinacionnyh cifrovyh ustrojstv po metodu logicheskogo dopolneniya // Izvestiya vysshih uchebnyh zavedenij. Priborostroenie. 2022. T. 65. № 1. S. 5–18. DOI:https://doi.org/10.17586/0021- 3454-2022-65-1-5-18. (In Russian)

40. Efanov D. V., Abdullaev R. B. Boolean Complement Method to Polynomial Codes for Combinational Circuits Testing // IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus), 25–28 January 2022, St. Petersburg, Russia. P. 139–144. DOI:https://doi.org/10.1109/ElCon‑ Rus54750.2022.9755602.

41. 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:https://doi.org/10.15514/ISPRAS‑2017-29(5)-3. (In Russian)

42. 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.

43. Efanov D. V. Sintez samoproveryaemyh vychislitel’nyh ustrojstv na osnove polnoj sistemy osobyh grup vyhodov ob”ekta diagnostirovaniya // Izvestiya vysshih uchebnyh zavedenij. Priborostroenie. 2023. T. 66, № 5. S. 355–372. DOI:https://doi.org/10.17586/0021-3454-2023-66-5-355-372. (In Russian)

44. Zakrevskij A. D., Pottosin Yu. V., Cheremisinova L. D. Logicheskie osnovy proektirovaniya diskretnyh ustrojstv. M.: Fizmatlit, 2007, 592 s. (In Russian)

45. Sentovich E. M., Singh K. J., Moon C., et al. 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. P. 328–333. DOI:https://doi.org/10.1109/ICCD.1992.276282.

46. SIS: A System for Sequential Circuit Synthesis / E. M. Sentovich, K. J. Singh, L. Lavagno, et al. // Electronics Research Laboratory, Department of Electrical Engineering and Computer Science, University of California, Berkeley, 4 May 1992. 45 p.

47. Efanov D. V., Sapozhnikov V. V., Sapozhnikov Vl. V. Organization of Testing of Combinational Devices Based on Boolean Complement to Constant-Weight “1‑out-of‑4” Code with Signal Compression // Automatic Control and Computer Sciences. 2021. Vol. 55, Issue 2. P. 113–124. DOI:https://doi.org/10.3103/S014641162102005X.

48. Saposhnikov Vl. V., Dmitriev A., Goessel M., et al. Self-Dual Parity Checking — a New Method for on Line Testing // Proceedings of 14th IEEE VLSI Test Symposium, USA, Princeton, 1996. P. 162–168.

49. Efanov D., Sapozhnikov V., Sapozhnikov Vl., et al. Self-Dual Complement Method up to Constant-Weight Codes for Arrangement of Combinational Logical Circuits Concurrent Error-Detection Systems // Proceedings of 17th IEEE East-West Design & Test Symposium (EWDTS’2019), Batumi, Georgia, September 13–16, 2019. P. 136–143. DOI:https://doi.org/10.1109/EWDTS.2019.8884398.

50. Efanov D. V., Pivovarov D. V. The Hybrid Structure of a Self-Dual Built-In Control Circuit for Combinational Devices with Pre-Compression of Signals and Checking of Calculations by Two Diagnostic Parameters // Proceedings of 19th IEEE East-West Design & Test Symposium (EWDTS’2021), Batumi, Georgia, September 10–13, 2021. P. 200–206. DOI:https://doi.org/10.1109/EWDTS52692.2021.9581019.

51. 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: Technolog and APlications (IDAACS’2021), Vol. 1, Cracow, Poland, September 22–25, 2021. P. 424–431. DOI:https://doi.org/10.1109/IDAACS53288.2021.9660837.

52. 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. (In Russian)

Login or Create
* Forgot password?