Control of Combinational Circuits by Two Diagnostic Criteria Based on Boolean Signal Correction Using the Hamming Codes Properties

A method for synthesizing self-checking digital devices with improved testability indicators is described. The method is based on the concurrent error-detection circuit synthesis by signals Boolean correction and the Hamming code (7, 4) with control of calculations according to two diagnostic criteria. The attributes used are the belonging of code words to the code (7, 4) and the self-duality of each function describing the data and checking bits of the code. The concurrent error-detection circuit basic structure for a seven-output combinational device is giving. The structure uses standard blocks, apart from the Boolean correction function calculation block. An algorithm has been developed for the Boolean correction function calculation block synthesis that meets the conditions for ensuring the self-duality of the generated signals and the belonging of code words (7, 4) to code. The application features of the basic structure are studied. It is shown that as n increases, the technical implementation complexity of individual concurrent error-detection circuit standard components decreases in comparison with the traditional duplication method. However, due to the increase in the complexity of the comparator, the overall complexity indicators of their technical implementation are growing. This leads to a decrease in the growth of the “efficiency margin for structural redundancy” of the proposed method as n increases. Thus, the effectiveness of using the presented method compared to duplication can be achieved with a significant reduction in the complexity of individual Boolean correction function calculation blocks (considering the possibilities for joint optimization of their structures). A preliminary assessment allows to recommend the developed method for special cases of diagnostic objects with a small number of outputs (no more than 30). On a case-by-case basis, effectiveness versus duplication must be assessed. In comparison with duplication in terms of testability, the method turns out to be more advantageous, since it makes it possible to ensure the tests formation more easily for concurrent error-detection circuit elements than when using duplication and makes it possible to achieve their formation even in cases where this is impossible with duplication. The proposed method for synthesizing self-checking devices can be considered when designing highly reliable digital systems on a modern element base.

1. Hamming R.W. Error Detecting and Correcting Codes. Bell System Technical Journal, 1950, 29 (2), pp. 147-160, DOI: 10.1002/j.1538-7305.1950.tb00463.x.

2. Sridhar K.P., Agalya R., Narmatha D., Vignesh B., Saravanan S. Test Data Compression Using Hamming Encoder and Decoder for System on Chip (SOC) Testing. 2014 International Conference on Circuits, Power and Computing Technologies (ICCPCT-2014), 20-21 March 2014, Nagercoil, India, doi: 10.1109/ICCPCT.2014.7054876.

3. Mehta U.S., Parmar H. Improvement in Error Resilience for Compressed VLSI Test Data Using Hamming Code Based Technique. 2015 International Conference on VLSI Systems, Architecture, Technology and Applications (VLSI-SATA), 08-10 January 2015, Bengaluru, India, doi: 10.1109/VLSI-SATA.2015.7050494.

4. Tshagharyan G., Harutyunyan G., Shoukourian S., Zorian Y. Experimental Study on Hamming and Hsiao Codes in the Context of Embedded Applications. Proceedings of 15th IEEE East-West Design & Test Symposium (EWDTS’2017), Novi Sad, Serbia, September 29 – October 2, 2017, pp. 25-28, doi: 10.1109/EWDTS.2017.8110065.

5. 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 10.1109/SIBCON50419.2021.9438900.

6. Ефанов Д.В., Погодина Т.С. Исследование свойств самодвойственных комбинационных устройств с контролем вычислений на основе кодов Хэмминга. Информатика и автоматизация, 2023, Том 22, №2, C. 349-392, DOI: 10.15622/ia.22.2.5. Efanov D.V., Pogodina T.S. Issledovanie svojstv samodvojstvennyh kombinacionnyh ustrojstv s kontrolem vychislenij na osnove kodov Hemminga. Informatika i avtomatizaciya, 2023, tom 22, issue 2, pp. 349-392 (in Russian). DOI: 10.15622/ia.22.2.5.

7. Ефанов Д.В. Особые свойства кодов Хэмминга, проявляющиеся при синтезе самопроверяемых цифровых устройств. Известия высших учебных заведений. Приборостроение, 2023, Т. 66, №2, С. 85-99, DOI: 10.17586/0021-3454-2023-66-2-85-99. Efanov D.V. Special Properties of Hamming Codes that Appear when Synthesizing Self-Checking Digital Devices. Izvestiya vysshih uchebnyh zavedenij. Priborostroenie, 2023, vol. 66, issue 2, pp. 85-99 (in Russian). DOI: 10.17586/0021-3454-2023-66-2-85-99.

8. Ефанов Д.В., Зуева М.В., Пашуков А.В. Исследование характеристик обнаружения ошибок кодами Хэмминга, учет которых целесообразен при синтезе самопроверяемых устройств автоматики. Автоматика на транспорте, 2023, Том 9, №3, С. 283-297, DOI: 10.20295/2412-9186-2023-9-03-283-297. Efanov D.V., Zueva M.V., Pashukov A.V. Study of the Characteristics of Error Detection with Hamming Codes, the Consideration of Which is Appropriate for the Synthesis of Automatic Devices with Fault Detection. Avtomatika na Transporte, 2023, vol. 9, issue 3, pp. 283-297 (in Russian). DOI: 10.20295/2412-9186-2023-9-03-283-297.

9. Ефанов Д.В. Предельные свойства кода Хэмминга в схемах функционального диагностирования. Информатика и системы управления, 2011, №3, С. 70-79. Efanov D.V. The Hamming Code's Limit Properties in Functional Control Scheme. Informatika i sistemy upravleniya, 2011, issue 3, pp. 70-79 (in Russian).

10. Сапожников В.В., Сапожников Вл.В., Ефанов Д.В. Особенности применения кодов Хэмминга при организации самопроверяемых схем встроенного контроля. Известия высших учебных заведений. Приборостроение, 2018, Том 61, №1, С. 47-59, DOI: 10.17586/0021-3454-2018-61-1-47-59. Sapozhnikov V.V., Sapozhnikov Vl.V., Efanov D.V. Features of Hamming Codes Application in Self-Checking Test Circuit Organization. Izvestiya vysshih uchebnyh zavedenij. Priborostroenie, 2018, vol. 61, issue 1, pp. 47-59 (in Russian). DOI: 10.17586/0021-3454-2018-61-1-47-59.

11. Ефанов Д.В., Погодина Т.С. Самодвойственные цифровые устройства с контролем вычислений по кодам Сяо. Вестник Томского государственного университета. Управление, вычислительная техника и информатика, 2023, №63, С. 118-136, DOI: 10.17223/19988605/63/14. Efanov D.V., Pogodina T.S. Self-Dual Digital Devices with Calculations Testing by Hsiao Codes. Vestnik Tomskogo gosudarstvennogo universiteta. Upravlenie, vychislitel'naya tekhnika i informatika, 2023, issue 63, pp. 118-136 (in Russian). DOI: 10.17223/19988605/63/14.

12. Гессель М., Морозов А.В., Сапожников В.В., Сапожников Вл.В. Логическое дополнение – новый метод контроля комбинационных схем. Автоматика и телемеханика, 2003, №1, С. 167-176. Goessel M., Morozov A.V., Sapozhnikov V.V., Sapozhnikov Vl.V. Logic Complement, a New Method of Checking the Combinational Circuits. Avtomatika i Telemekhanika, 2003, issue 1, pp. 167-176. (in Russian).

13. Гессель М., Морозов А.В., Сапожников В.В., Сапожников Вл.В. Контроль комбинационных схем методом логического дополнения. Автоматика и телемеханика, 2005, №8, С. 161-172. Goessel M., Morozov A.V., Sapozhnikov V.V., Sapozhnikov Vl.V. Checking Combinational Circuits by the Method of Logic Complement. Avtomatika i Telemekhanika, 2005, issue 8, pp. 161-172. (in Russian).

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

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

16. Efanov D., Sapozhnikov V., Sapozhnikov Vl., Osadchy G., Pivovarov D. 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, pp. 136-143, doi: 10.1109/EWDTS.2019.8884398.

17. 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, pp. 200-206, doi: 10.1109/EWDTS52692.2021.9581019.

18. Согомонян Е.С., Слабаков Е.В. Самопроверяемые устройства и отказоустойчивые системы. М.: Радио и связь, 1989. 208 с. Sogomonyan E.S., Slabakov E.V. The Self-Checking Devices and Fault-Tolerant Systems. M.: Radio and Сommunications. 208 р. (in Russian).

19. Nicolaidis M., Zorian Y. On-Line Testing for VLSI – А Compendium of Approaches. Journal of Electronic Testing: Theory and Applications, 1998, №12, pp. 7-20, DOI: 10.1023/A:1008244815697.

20. Сапожников В.В., Сапожников Вл.В., Ефанов Д.В. Коды Хэмминга в системах функционального контроля логических устройств, СПб.: Наука, 2018, 151 с. Sapozhnikov V.V., Sapozhnikov Vl.V., Efanov D.V. Hamming Сodes in Concurrent Error Detection Systems of Logic Devices. – St. Petersburg: Nauka, 2018, 151 p. (in Russian).

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

22. Сапожников В.В., Сапожников Вл.В., Гессель М. Самодвойственные дискретные устройства, СПб: Энергоатомиздат (Санкт-Петербургское отделение), 2001. 331 с. Sapozhnikov V.V., Sapozhnikov Vl.V., Göessel M. Self-Dual Digital Devices. St. Petersburg: Energoatomizdat (St. Petersburg branch), 331 p. (in Russian).

23. Goessel M., Graf S. Error Detection Circuits, London: McGraw-Hill, 1994. 261 p.

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

25. 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: 10.1109/ICCD.1992.276282.

26. Dmitriev A., Saposhnikov V., Saposhnikov V., Goessel M. New Self-Dual Circuits for Error Detection and Testing // VLSI Design, 2000, Vol. 11, Issue 1, pp. 1-21, doi: 10.1155/2000/84720.

27. Гессель М., Мошанин В.И., Сапожников В.В., Сапожников Вл.В. Обнаружение неисправностей в самопроверяемых комбинационных схемах с использованием свойств самодвойственных функций. Автоматика и телемеханика, 1997, №12, С. 193-200. Göessel M., Moshanin V.I., Sapozhnikov V.V., Sapozhnikov Vl.V. Fault Detection in Self-Test Combination Circuits Using the Properties of Self-Dual Functions. Avtomatika i Telemekhanika, 1997, issue 12, pp. 193-200 (in Russian).

28. Ефанов Д.В. Синтез самопроверяемых комбинационных устройств на основе метода логической коррекции сигналов с применением кодов Боуза – Лина. Информационные технологии, 2023, Том 29, №10, С. 503-511, DOI: 10.17587/it.29.503-511. Efanov D.V. Self-Checking Combinational Devices Synthesis Based on the Boolean Signal Correction Method Using Bose-Lin Codes. Information Technologies, 2023, Vol. 29, issue 10, pp. 503-511 (in Russian). DOI: 10.17587/it.29.503-511.

29. Аксенова Г.П. Необходимые и достаточные условия построения полностью проверяемых схем свертки по модулю 2. Автоматика и телемеханика, 1979, №9, С. 126-135. Necessary and Sufficient Aksenova G.P. Conditions for Design of Completely Checkable Modulo 2 Convolution Circuits. Avtomatika i Telemekhanika, 1979, issue 9, pp. 126-135 (in Russian).

30. Сапожников В.В., Сапожников Вл.В., Ефанов Д.В. Метод функционального контроля комбинационных логических устройств на основе кода «2 из 4». Известия высших учебных заведений. Приборостроение, 2016, Том 59, №7, С. 524-533, DOI: 10.17586/0021-3454-2016-59-7-524-533. Sapozhnikov V.V., Sapozhnikov Vl.V., Efanov D.V. Method of Operation Control Over Combinatory Logic Device Based on 2-out-of-4 Code. Izvestiya vysshih uchebnyh zavedenij. Priborostroenie, 2016, vol. 59, issue 7, pp. 524-533 (in Russian). DOI: 10.17586/0021-3454-2016-59-7-524-533.

31. Закревский А.Д., Поттосин Ю.В., Черемисинова Л.Д. Логические основы проектирования дискретных устройств, М.: Физматлит, 2007. 592 с. Zakrevsky A.D., Pottosin Yu.V., Cheremisinova L.D. Logical Foundations of Designing Discrete Devices, M.: Fizmatlit, 2007. 592 p. (in Russian).

32. Коршунов А.Д. Сложность вычислений булевых функций. Успехи математических наук, 2012, Том 67, №1 (403), С. 97-168, DOI: 10.4213/rm9459. Korshunov A.D. Computational complexity of Boolean functions. Uspekhi matematicheskih nauk, 2012, vol. 67, issue 1 (403), pp. 97-168 (in Russian). DOI: 10.4213/rm9459.

33. Drozd A., Kharchenko V., Antoshchuk S., Sulima J., Drozd M. 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, pp. 411- 416, doi: 10.1109/EWDTS.2011.6116606.

34. Дрозд А.В., Харченко В.С., Антощук С.Г., Дрозд Ю.В., Дрозд М.А., Сулима Ю.Ю. Рабочее диагностирование безопасных информационно-управляющих систем. Под ред. А.В. Дрозда и В.С. Харченко, Харьков: Национальный аэрокосмический университет им. Н.Е. Жуковского «ХАИ», 2012, 614 с. Drozd A.V., Kharchenko V.S., Antoshchuk S.G., Drozd Yu.V., Drozd M.A., Sulima Yu.Yu. (2012) Working Diagnostics of Safe Information and Control Systems. Edited by A.V. Drozd and V.S. Kharchenko. Khar’kov: N.E. Zhukovsky National Aerospace University «KAI». 614 р. (in Russian).

35. Сапожников Вл.В. Синтез систем управления движением поездов на железнодорожных станциях с исключением опасных отказов, М.: Наука, 2021. 229 с. Sapozhnikov Vl.V. Synthesis of Train Traffic Control Systems at Railway Stations with the Exception of Dangerous Failures. M. Nauka. 229 p. (in Russian).

36. Багхдади А.А.А., Хаханов В.И., Литвинова Е.И. Методы анализа и диагностирования цифровых устройств (аналитический обзор) // Автоматизированные системы управления и приборы автоматики, 2014, № 166, с. 59-74. Baghdadi A.A.A., Hahanov V.I., Litvinova E.I. Metody analiza i diagnostirovaniya cifrovyh ustrojstv (analiticheskij obzor) // Avtomatizirovannye sistemy upravleniya i pribory avtomatiki, 2014, № 166, s. 59-74 (in Russian).

37. Collection of Digital Design Benchmarks: https://ddd.fit.cvut.cz/www/prj/Benchmarks/