Контроль комбинационных схем по двум диагностическим признакам на основе логической коррекции сигналов с использованием свойств кодов Хэмминга

Описывается метод синтеза самопроверяемых цифровых устройств с улучшенными показателями контролепригодности, основанный на синтезе схем встроенного контроля путем логической коррекции сигналов и применении кода Хэмминга (7, 4) с контролем вычислений по двум диагностическим признакам. В качестве признаков используется принадлежность кодовых слов коду (7, 4) и самодвойственность каждой функции, описывающей информационные и проверочные символы кода. Представлены «базовая» структура организации схемы встроенного контроля для семивыходного комбинационного устройства, в которой используются типовые блоки (кроме блока вычисления функций логической коррекции) и алгоритм синтеза блока вычисления функций логической коррекции, отвечающего условиям обеспечения самодвойственности формируемых сигналов и принадлежности кодовых слов коду (7, 4). Исследованы особенности применения «базовой» структуры организации схем встроенного контроля при контроле вычислений устройствами с числом выходов n > 7. С ростом n показатели сложности технической реализации типовых компонентов отдельных схем встроенного контроля уменьшаются в сравнении с традиционным методом дублирования, однако за счет роста сложности компаратора общие показатели сложности их технической реализации, наоборот, растут. Это приводит к уменьшению роста «запаса эффективности по структурной избыточности» предлагаемого метода с ростом n. Эффективность применения представленного метода по сравнению с дублированием может быть достигнута при существенном уменьшении показателей сложности отдельных блоков вычисления функций логической коррекции (с учетом возможностей по совместной оптимизации их структур). Предварительная оценка позволяет рекомендовать использование разработанного метода для частных случаев объектов диагностирования с небольшим числом выходов (не более 30). В каждом конкретном случае, однако, нужно проводить оценку эффективности по сравнению с дублированием. В сравнении с дублированием по показателю контролепригодности метод оказывается более выигрышным, поскольку дает возможность более просто обеспечивать формирование тестов для элементов схемы встроенного контроля, чем при использовании дублирования и позволяет достигать их формирования даже в тех случаях, когда это невозможно при дублировании. Предложенный метод синтеза самопроверяемых устройств может рассматриваться при проектировании высоконадежных цифровых систем на современной элементной базе.

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/