priborИзвестия высших учебных заведений. ПриборостроениеJournal of Instrument Engineering0021-34542500-0381Национальный исследовательский университет ИТМО10.17586/0021-3454-2023-66-5-355-372pribor-112Research ArticleСИСТЕМНЫЙ АНАЛИЗ, УПРАВЛЕНИЕ И ОБРАБОТКА ИНФОРМАЦИИSYSTEM ANALYSIS, MANAGEMENT AND INFORMATION PROCESSINGСинтез самопроверяемых вычислительных устройств на основе полной системы особых групп выходов объекта диагностированияSynthesis of self-checking computing devices based on a complete system of special groups of the diagnostic object outputsЕфановД. В.EfanovD. V.

Ефанов Дмитрий Викторович — д-р техн. наук, профессор; кафедра автоматики, телемеханики и связи на железнодорожном транспорте, РУТ; Высшая школа транспорта Института машиностроения, материалов и транспорта, СПбПУ Петра Великого; профессор.

Москва; Санкт-Петербург

Dmitry V. Efanov — Dr. Sci., Professor; Russian University of Transport, Department of Automation, Remote Control, and Communications on Railway Transport; Peter the Great St. Petersburg Polytechnic University, Higher School of Transport, Institute of Mechanical Engineering, Materials, and Transport; Professor.

Moscow; St. Petersburg

TrES-4b@yandex.ruРоссийский университет транспорта; Санкт-Петербургский политехнический университет Петра ВеликогоRussian University of Transport; Peter the Great St. Petersburg Polytechnic University202326112024665355372Copyright © Национальный исследовательский университет ИТМО, 20242024Национальный исследовательский университет ИТМОНациональный исследовательский университет ИТМОhttps://pribor.ifmo.ru/jour/about/submissions#copyrightNoticehttps://pribor.ifmo.ru/jour/article/view/112

Обсуждаются особенности синтеза схем встроенного контроля устройств автоматики и вычислительной техники при известной структуре объекта диагностирования. Представлено полное множество особых групп выходов, которые характеризуются каким-либо диагностическим параметром. Выделение особых групп выходов позволяет осуществлять выбор кода для построения схемы встроенного контроля с учетом возможностей обнаружения ошибок конкретной кратностью и определенного вида. Представлен способ построения схемы встроенного контроля, подразумевающий анализ всех подмножеств выходов объекта диагностирования, классификацию их по принадлежности к какой-либо особой группе выходов, а также последующее покрытие всех выходов особыми группами с выбором наилучшего по критерию структурной избыточности способа покрытия с указанием конкретных кодов для контроля вычислений. Предложенный способ в ряде случаев может быть эффективен при организации схем встроенного контроля и позволяет синтезировать самопроверяемое устройство даже в случае, когда этого невозможно добиться применением метода дублирования.

Features of concurrent error-detection circuit synthesis for a known diagnostic object structure are discussed. A complete set of special groups of outputs that characterize them by some diagnostic parameter is presented. Separation of special groups of outputs allows to select a code for building an integrated control circuit, taking into account the possibility of detecting errors with a specific multiplicity and a certain type. A method for constructing an integrated control circuit is proposed, which involves an analysis of all subsets of the diagnostic object outputs, their classification by belonging to any special group of outputs, as well as the subsequent coverage of all outputs by special groups with the choice of the best coverage method by the criterion of structural redundancy, indicating specific codes to control the calculations. The proposed method is assumed to be effective in several cases of organizing built-in control circuits and to allow synthesizing a self-checking device even when this cannot be achieved by using the duplication method.

самопроверяемое устройствосхема встроенного контроляконтроль вычисленийособая группа выходовкоды с обнаружением отдельных видов ошибокself-checking devicebuilt-in control circuitcalculation controlspecial group of outputscodes with certain type error detectionReferencesСогомонян Е. С., Слабаков Е. В. Самопроверяемые устройства и отказоустойчивые системы. М.: Радио и связь, 1989. 208 с.Sogomonyan E.S., Slabakov E.V. Samoproveryaemye ustroystva i otkazoustoychivye sistemy (The Self-Checked Devices and Failure-Safe Systems), Moscow, 1989, 208 р. (in Russ.)Микони С. В. Общие диагностические базы знаний вычислительных систем. СПб: СПИИРАН, 1992. 234 с.Mikoni S.V. Obshchiye diagnosticheskiye bazy znaniy vychislitel'nykh sistem (General Diagnostic Knowledge Bases of Computing Systems) St. Petersburg, 1992, 234 р. (in Russ.)Pradhan D. K. Fault-Tolerant Computer System Design. N. Y.: Prentice Hall, 1996. 560 p.Pradhan D.K. Fault-Tolerant Computer System Design, NY, Prentice Hall, 1996, 560 p.Lala P. K. Self-Checking and Fault-Tolerant Digital Design. San Francisco: Morgan Kaufmann Publ., 2001. 216 p.Lala P.K. Self-Checking and Fault-Tolerant Digital Design, San Francisco, Morgan Kaufmann Publishers, 2001, 216 p.Fujiwara E. Code Design for Dependable Systems: Theory and Practical Applications. John Wiley & Sons, 2006. 720 p.Fujiwara E. Code Design for Dependable Systems: Theory and Practical Applications, John Wiley & Sons, 2006, 720 p.Дрозд А. В., Харченко В. С., Антощук С. Г., Дрозд Ю. В., Дрозд М. А., Сулима Ю. Ю. Рабочее диагностирование безопасных информационно-управляющих систем / Под ред. А. В. Дрозда и В. С. Харченко. Харьков: НАУ им. Н. Е. Жуковского „ХАИ“, 2012. 614 с.Drozd A.V., Kharchenko V.S., Antoshchuk S.G., Drozd Yu.V., Drozd M.A., Sulima Yu.Yu. Rabocheye diagnostirovaniye bezopasnykh informatsionno-upravlyayushchikh sistem (Working Diagnostics of Safe Information and Control Systems), Khar’kov, 2012, 614 р. (in Russ.)Nikolos D. Self-Testing Embedded Two-Rail Checkers // Chapter 7 in On-Line Testing for VLSI. 1998. P. 69—79. DOI 10.1007/978-1-4757-60-69-9_7.Nikolos D. Chapter 7 in On-Line Testing for VLSI, 1998, pp. 69–79, DOI 10.1007/978-1-4757-60-69-9_7.Сапожников В. В., Сапожников Вл. В., Ефанов Д. В., Дмитриев В. В. Новые структуры систем функционального контроля логических схем // Автоматика и телемеханика. 2017. № 2. С. 127—143.Sapozhnikov V.V., Sapozhnikov Vl.V., Efanov D.V., Dmitriev V.V. Automation and Remote Control, 2017, no. 2(78), pp. 300–312, DOI: https://doi.org/10.1134/S0005117917020096.Сапожников В. В., Сапожников Вл. В., Ефанов Д. В. Коды с суммированием для систем технического диагностирования. Т. 1. Классические коды Бергера и их модификации. М.: Наука, 2020. 383 с.Sapozhnikov V.V., Sapozhnikov Vl.V., Efanov D.V. Kody s summirovaniyem dlya sistem tekhnicheskogo diagnostirovaniya. T. 1. Klassicheskiye kody Bergera i ikh modifikatsii (Summed Codes for Technical Diagnostic Systems. Vol. 1. Classical Berger Codes and Their Modifications), Moscow, 2020, 383 р. (in Russ.)Сапожников В. В., Сапожников Вл. В., Ефанов Д. В. Коды с суммированием для систем технического диагностирования. Т. 2. Взвешенные коды с суммированием. М.: Наука, 2021. 455 с.Sapozhnikov V.V., Sapozhnikov Vl.V., Efanov D.V. Kody s summirovaniyem dlya sistem tekhnicheskogo diagnostirovaniya. T. 2. Vzveshennyye kody s summirovaniyem (Summed Codes for Technical Diagnostic Systems. Vol. 2. Weighted Codes with Summation), Moscow, 2021, 455 р. (in Russ.)Кодирование информации (двоичные коды) / Н. Т. Березюк, А. Г. Андрущенко, С. С. Мощицкий, В. И. Глушков, М. М. Бенеша, В. А. Гаврилов; Под ред. Н. Т. Березюка. Харьков: Вища школа, 1978. 252 с.Berezyuk N.T., Andrushchenko A.G., Moshchitskiy S.S., Glushkov V.I., Benesha M.M., Gavrilov V.A. Kodirovaniye informatsii (dvoichnyye kody) (Information Coding (Binary Codes)), Khar'kov, 1978, 252 р. (in Russ.Багхдади А. А. А., Хаханов В. И., Литвинова Е. И. Методы анализа и диагностирования цифровых устройств (аналитический обзор) // Автоматизированные системы управления и приборы автоматики. 2014. № 166. С. 59—74.Baghdadi A.A.A., Hahanov V.I., Litvinova E.I. Management Information System and Devices, 2014, no. 166, pp. 59–74. (in Russ.)Carter W. C., Duke K. A., Schneider P. R. Self-Checking Error Checker for Two-Rail Coded Data. Pat. 747533, US, Jan. 26, 1971.Patent US 747533, Self-Checking Error Checker for Two-Rail Coded Data, W.C. Carter, K.A. Duke, P.R. Schneider, Priority July 25, 1968, Published Jan. 26, 1971.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 Applications. 1993. Vol. 4, iss. 4. P. 267—281. DOI: 10.1007/BF00971975.Sogomonyan E.S., Gössel M. Journal of Electronic Testing: Theory and Applications, 1993, no. 4(4), pp. 267–281, DOI: 10.1007/BF00971975.Busaba F. Y., Lala P.K. Self-Checking Combinational Circuit Design for Single and Unidirectional Multibit Errors // Journal of Electronic Testing: Theory and Applications. 1994. Iss. 1. P. 19—28. – DOI: 10.1007/BF00971960.Busaba F.Y., Lala P.K. Journal of Electronic Testing: Theory and Applications, 1994, no. 1, pp. 19–28, DOI: 10.1007/BF00971960.Matrosova A. Yu., Ostanin S. A. Self-Checking Synchronous Sequential Circuit Design for Unidirectional Error // Proc. of the IEEE European Test Workshop (ETW’98), Sitges, Barcelona, Spain, 27—29 May 1998.Matrosova A.Yu., Ostanin S.A. Proceedings of the IEEE European Test Workshop (ETW’98), May 27–29, 1998, Sitges, Barcelona, Spain.Berger J. M. А Note on Error Detecting Codes for Asymmetric Channels // Information and Control. 1961. Vol. 4, iss. 1. P. 68—73. DOI: 10.1016/S0019-9958(61)80037-5.Berger J.M. Information and Control, 1961, no. 1(4), pp. 68–73, DOI: 10.1016/S0019-9958(61)80037-5.Morosow A., Saposhnikov V. V., Saposhnikov Vl. V., Goessel M. Self-Checking Combinational Circuits with Unidirectionally Independent Outputs // VLSI Design. 1998. Vol. 5, iss. 4. P. 333—345. DOI: 10.1155/1998/20389.Morosow A, Saposhnikov V.V., Saposhnikov Vl.V., Goessel M. VLSI Design, 1998, no. 5(4), pp. 333–345, DOI: 10.1155/1998/20389.Saposhnikov V. V., Morosov A., Saposhnikov Vl. V., Göessel M. A New Design Method for Self-Checking Unidirectional Combinational Circuits // Journal of Electronic Testing: Theory and Applications. 1998. Vol. 12, iss. 1—2. P. 41—53. DOI: 10.1023/A:1008257118423.Saposhnikov V.V., Morosov A., Saposhnikov Vl.V., Göessel M. Journal of Electronic Testing: Theory and Applications, 1998, no. 1-2(12), pp. 41–53, DOI: 10.1023/A:1008257118423.Göessel M., Ocheretny V., Sogomonyan E., Marienfeld D. New Methods of Concurrent Checking. Dordrecht: Springer Science+Business Media B.V., 2008. 184 p.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.Сапожников В. В., Сапожников Вл. В., Ефанов Д. В. Классификация ошибок в информационных векторах систематических кодов // Изв. вузов. Приборостроение. 2015. Т. 58, № 5. С. 333—343. DOI: 10.17586/0021-3454-2015-58-5-333-343.Sapozhnikov V.V., Sapozhnikov Vl.V., Efanov D.V. Journal of Instrument Engineering, 2015, no. 5(58), pp. 333–343, DOI: 10.17586/0021-3454-2015-58-5-333-343. (in Russ.)Ефанов Д. В., Сапожников В. В., Сапожников Вл. В. Условия обнаружения неисправности логического элемента в комбинационном устройстве при функциональном контроле на основе кода Бергера // Автоматика и телемеханика. 2017. № 5. С. 152—165.Efanov D.V., Sapozhnikov V.V., Sapozhnikov Vl.V. Automation and Remote Control, 2017, no. 5(78), pp. 891–901, DOI: https://doi.org/10.1134/S0005117917050113.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, iss. 4. P. 279—290. – DOI: 10.3103/S0146411620040045.Efanov D.V., Sapozhnikov V.V., Sapozhnikov Vl.V. Automatic Control and Computer Sciences, 2020, no. 4(54), pp. 279–290, DOI: 10.3103/S0146411620040045.Ефанов Д. В., Сапожников В. В., Сапожников Вл. В. Синтез самопроверяемых комбинационных устройств на основе выделения специальных групп выходов // Автоматика и телемеханика. 2018. № 9. С. 79—94.Efanov D.V., Sapozhnikov V.V., Sapozhnikov Vl.V. Automation and Remote Control, 2018, no. 9(79), pp. 1609– 1620DOI: https://doi.org/10.1134/S0005117918090060.Аксенова Г. П. Метод синтеза схем встроенного контроля для автоматов с памятью // Автоматика и телемеханика. 1973. № 2. С. 109—116.Aksyonova G.P. Automation and Remote Control, 1973, no. 2(34), pp. 267–273.Hamming R. W. Error Detecting and Correcting Codes // Bell System Technical Journal. 1950. N 29 (2). P. 147—160.Hamming R.W. Bell System Technical Journal, 1950, no. 2(29), pp. 147–160, MR0035935.Sapozhnikov V., Sapozhnikov Vl., Efanov D., Dmitriev V. Weighted Sum Code Without Carries – is an Optimum Code with Detection of Any Double Errors in Data Vectors // Proc. of the 14th IEEE East-West Design & Test Symp. (EWDTS’2016), Yerevan, Armenia, Oct. 14—17, 2016. P. 134—141. DOI: 10.1109/EWDTS.2016.7807686.Sapozhnikov V., Sapozhnikov Vl., Efanov D., Dmitriev V. Proceedings of 14th IEEE East-West Design & Test Symposium (EWDTS’2016), Yerevan, Armenia, October 14–17, 2016, pp. 134–141, DOI: 10.1109/EWDTS.2016.7807686.Sapozhnikov V., Efanov D., Sapozhnikov Vl., Dmitriev V. New Sum Code for Effective Detection of Double Errors in Data Vectors // Proc. of the 13th IEEE East-West Design & Test Symp. (EWDTS’2015), Batumi, Georgia, Sept. 26—29, 2015. P. 154—159. DOI: 10.1109/EWDTS.2015.7493123.Sapozhnikov V., Efanov D., Sapozhnikov Vl., Dmitriev V. Proceedings of 13th IEEE East-West Design & Test Symposium (EWDTS’2015), Batumi, Georgia, September 26–29, 2015, pp. 154–159, DOI: 10.1109/EWDTS.2015.7493123.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.Freiman C.V. Information and Control, 1962, no. 1(5), pp. 64–71, DOI: 10.1016/S0019-9958(62)90223-1.Сапожников В. В., Сапожников Вл. В., Ефанов Д. В. Коды с суммированием, обнаруживающие любые симметричные ошибки // Электронное моделирование. 2017. Т. 39, № 3. С. 47—60.Sapozhnikov V.V., Sapozhnikov Vl.V., Efanov D.V. Electronic modeling, 2017, no. 3(39), pp. 37–60. (in Russ.)Ефанов Д. В., Сапожников В. В., Сапожников Вл. В. Модифицированные коды с суммированием взвешенных переходов в системах функционального контроля комбинационных схем // Тр. Института системного программирования РАН. 2017. Т. 29, № 5. С. 39—60. DOI: 10.15514/ISPRAS-2017-29(5)-3.Efanov D.V., Sapozhnikov V.V., Sapozhnikov Vl.V. Trudy SPIIRAN (SPIIRAS Proceedings), 2017, no. 5(29), рр. 39–60, DOI: 10.15514/ISPRAS-2017-29(5)-3. (in Russ.)Сапожников В. В., Сапожников Вл. В., Ефанов Д. В. Обнаружение неисправностей в комбинационных логических схемах на основе их контроля по группам симметрично независимых выходов // Электронное моделирование. 2020. Т. 42, № 2. С. 3—23. DOI: 10.15407/emodel.42.02.003.Sapozhnikov V.V., Sapozhnikov Vl.V., Efanov D.V. Electronic modeling, 2020, no. 2(42), pp. 3–23, DOI: 10.15407/emodel.42.02.003. (in Russ.)Закревский А. Д., Поттосин Ю. В., Черемисина Л. Д. Логические основы проектирования дискретных устройств. М.: Физматлит, 2007. 592 с.Zakrevskiy A.D., Pottosin Yu.V., Cheremisina L.D. Logicheskiye osnovy proyektirovaniya diskretnykh ustroystv (Logical Basis for Designing Discrete Devices), Moscow, 2007, 592 р. (in Russ.)Nicolaidis M., Zorian Y. On-Line Testing for VLSI – А Compendium of Approaches // Journal of Electronic Testing: Theory and Application. 1998. Vol. 12, iss. 1—2. P. 7—20. DOI: 10.1023/A:1008244815697.Nicolaidis M., Zorian Y. Journal of Electronic Testing: Theory and Application, 1998, no. 1–2(12), pp. 7–20, DOI: 10.1023/A:1008244815697.Mitra S., McCluskey E. J. Which Concurrent Error Detection Scheme to Сhoose? // Proc. of Intern. Test Conf., Atlantic City, NJ, USA, 03—05 Oct. 2000, P. 985—994. DOI: 10.1109/TEST.2000.894311.Mitra S., McCluskey E.J. Proceedings of International Test Conference, 2000, USA, Atlantic City, NJ, October 03–05, 2000, pp. 985–994, DOI: 10.1109/TEST.2000.894311.Сапожников В. В., Сапожников В. В. Самопроверяемые дискретные устройства. СПб: Энергоатомиздат, 1992. 224 с.Sapozhnikov V.V., Sapozhnikov Vl.V. Samoproveryaemye diskretnye ustroystva (The Self-Checked Discrete Devices), St. Petersburg, 1992, 224 p. (in Russ.)Piestrak S. J. Design of Self-Testing Checkers for Unidirectional Error Detecting Codes. Wrocław: Oficyna Wydawnicza Politechniki Wrocłavskiej, 1995. 111 p.Piestrak S.J. Design of Self-Testing Checkers for Unidirectional Error Detecting Codes, Wrocław, Oficyna Wydawnicza Politechniki Wrocłavskiej, 1995, 111 p.Гессель М., Морозов А. В., Сапожников В. В., Сапожников Вл. В. Логическое дополнение – новый метод контроля комбинационных схем // Автоматика и телемеханика. 2003. № 1. С. 167—176.Gessel M., Morozov A.V., Sapozhnikov V.V., Sapozhnikov Vl.V. Automation and Remote Control, 2003, no. 1(64), pp. 153–161, DOI: https://doi.org/10.1023/A:1021884727370.Гессель М., Морозов А. В., Сапожников В. В., Сапожников Вл. В. Контроль комбинационных схем методом логического дополнения // Автоматика и телемеханика. 2005. № 8. С. 161—172.Goessel M., Morozov A.V., Sapozhnikov V.V., Sapozhnikov Vl.V. Automation and Remote Control, 2005, no. 8, pp. 1336–1346.

The authors declare that there are no conflicts of interest present.