Weight-based Bose–Lin codes in concurrent error-detection circuit based on Boolean signals correction

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

The paper explores the possibilities of using weight-based Bose–Lin codes in the synthesis of concurrent error-detection circuit based on Boolean signals correction. The dependences of the number of weighing options in the construction of the considered class of codes on the number m of data symbols are established. It is shown that with an increase in the value of the number m, the number of weighing methods increases significantly, which makes it possible to build a large number of codes and, as a result, have greater variability in the construction of a self-checking device. The patterns that appear when the number of data symbols changes are established, linking the number of weighing options when building the code. It is shown that the number of ways to synthesize concurrent error-detection circuits based on Boolean signals correction using weight-based Bose–Lin codes factorially depends on the number of allocated data symbols among the data signals of the diagnostic object. The examples given in the paper demonstrate the effectiveness of using weight-based Bose–Lin codes in the synthesis of concurrent error-detection circuit compared to using the traditional method based on duplication. It is advisable to take the results of the study into account when developing self-checking digital devices, as well as when developing their computer-aided design systems.

Full Text

Restricted Access

About the authors

Y. I. Yelina

Peter the Great Saint Petersburg Polytechnic University

Author for correspondence.
Email: eseniya-elina@mail.ru
Russian Federation, St. Petersburg

D. V. Efanov

Peter the Great Saint Petersburg Polytechnic University; Russian University of Transport

Email: TrES-4b@yandex.ru
Russian Federation, St. Petersburg; Moscow

References

  1. Пархоменко П.П., Согомонян Е.С. Основы технической диагностики (оптимизация алгоритмов диагностирования, аппаратурные средства). М.: Энергоатомиздат, 1981, 320 с.
  2. Дрозд А.В., Харченко В.С., Антощук С.Г., Дрозд Ю.В., Дрозд М.А., Сулима Ю.Ю. Рабочее диагностирование безопасных информационно-управляющих систем / Под ред. А.В. Дрозда и В.С. Харченко. Харьков: Национальный аэрокосмический ун-т им. Н.Е. Жуковского “ХАИ”, 2012. 614 с.
  3. Kharchenko V., Kondratenko Yu., Kacprzyk J. Green IT Engineering: Concepts, Models, Complex Systems Architectures // Springer Book Series “Studies in Systems, Decision and Control”. 2017. V. 74. 305 p.; https://doi.org/10.1007/978-3-319-44162-7
  4. Mikoni S. Top Level Diagnostic Models of Complex Objects // Lecture Notes in Networks and Systems. 2022. V. 442. P. 238–249; https://doi.org/10.1007/978-3-030-98832-6_21
  5. Гавзов Д.В., Сапожников В.В., Сапожников Вл.В. Методы обеспечения безопасности дискретных систем // АиТ. 1994. № 8. С. 3–50.
  6. Согомонян Е.С., Слабаков Е.В. Самопроверяемые устройства и отказоустойчивые системы. М.: Радио и связь, 1989. 208 с.
  7. 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.
  8. Goessel M., Graf S. Error Detection Circuits. London: McGraw-Hill, 1994. 261 p.
  9. Аксёнова Г.П., Согомонян Е.С. Построение самопроверяемых схем встроенного контроля для автоматов с памятью // АиТ. 1975. № 7. С. 132–142.
  10. Гессель М., Морозов А.В., Сапожников В.В., Сапожников Вл.В. Контроль комбинационных схем методом логического дополнения // АиТ. 2005. № 8. С. 161–172.
  11. Гессель М., Согомонян Е.С. Построение самотестируемых и самопроверяемых комбинационных устройств со слабонезависимыми выходами // АиТ. 1992. № 8. С. 150–160.
  12. Sogomonyan E.S., Gössel M. Design of Self-Testing and On-Line Fault Detection Combinational Circuits with Weakly Independent Outputs // J. Electronic Testing: Theory and Applications. 1993. V. 4. Iss. 4. P. 267–281; https://doi.org/10.1007/BF00971975
  13. Saposhnikov Vl.V., Dmitriev A., Goessel M., Saposhnikov V.V. Self-Dual Parity Checking – A New Method for on Line Testing // Proc. 14th IEEE VLSI Test Sympos. USA, Princeton, 1996. P. 162–168.
  14. 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 // Proc. 19th IEEE East-West Design & Test Symposium (EWDTS’2021). Batumi, Georgia, 2021. P. 200–206; https://doi.org/10.1109/EWDTS52692.2021.9581019
  15. Ефанов Д.В., Погодина Т.С. Исследование свойств самодвойственных комбинационных устройств с контролем вычислений на основе кодов Хэмминга // Информатика и автоматизация. 2023. Т. 22. № 2. C. 349–392; https://doi.org/10.15622/ia.22.2.5
  16. Гессель М., Морозов А.В., Сапожников В.В., Сапожников Вл.В. Логическое дополнение новый метод контроля комбинационных схем // АиТ. 2003. № 1. С. 167–176.
  17. 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 Conf. on Emerging Trends and Advances in Electrical Engineering and Renewable Energy (NCEEERE 2010). Sikkim: Sikkim Manipal Institute of Technology, 2010.
  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 // Proc. 10th Intern. Workshops on Boolean Problems. Freiberg, Germany, 2012. P. 33–40.
  19. Пивоваров Д.В. Построение систем функционального контроля многовыходных комбинационных схем методом логического дополнения по равновесным кодам // Автоматика на транспорте. 2018. Т. 4. № 1. С. 131–149.
  20. Efanov D.V., Sapozhnikov V.V., Sapozhnikov Vl.V., Pivovarov D.V. Synthesis of Built-in Self-Test Control Circuits Based on the Method of Boolean Complement to Constant-Weight 1-out-of-n Codes // Automatic Control and Computer Sciences. 2019. V. 53. Iss. 6. P. 481–491; https://doi.org/10.3103/S014641161906004X
  21. Morozov M., Saposhnikov V.V., Saposhnikov Vl.V., Goessel M. New Self-Checking Circuits by Use of Berger-codes // Proc. IEEE Intern. On-Line Testing Workshop. Palma De Mallorca, Spain, 2000. P. 171–176.
  22. Berger J.M. A Note on Error Detection Codes for Asymmetric Channels // Information and Control. 1961. V. 4. Iss. 1. P. 68–73; https://doi.org/10.1016/S0019-9958(61)80037-5
  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. V. 43. Iss. 1. P. 28–45; https://doi.org/10.15407/emodel.43.01.028
  24. Слабаков Е.В. Построение полностью самопроверяемых комбинационных устройств с использованием остаточных кодов // АиТ. 1979. № 10. C. 133–141.
  25. Слабаков Е.В., Согомонян Е.С. Самопроверяемые вычислительные устройства и системы (обзор) // АиТ. 1981. № 11. С. 147–167.
  26. Piestrak S.J. Design of Self-Testing Checkers for Unidirectional Error Detecting Codes. Wrocław: Oficyna Wydawnicza Politechniki Wrocłavskiej, 1995. 111 p.
  27. Das D., Touba N.A. Synthesis of Circuits with Low-Cost Concurrent Error Detection Based on Bose-Lin Codes // J. Electronic Testing: Theory and Applications. 1999. V. 15. Iss. 1–2. P. 145–155; https://doi.org/10.1023/A:1008344603814
  28. Ефанов Д.В., Сапожников В.В., Сапожников Вл.В. Применение модульных кодов с суммированием для построения систем функционального контроля комбинационных логических схем // АиТ. 2015. № 10. С. 152–169.
  29. Сапожников В.В., Сапожников Вл.В., Ефанов Д.В., Черепанова М.Р. Модульные коды с суммированием в системах функционального контроля. I. Свойства обнаружения ошибок кодами в информационных векторах // Электронное моделирование. 2016. Т. 38. № 2. С. 27–48.
  30. Сапожников В.В., Сапожников Вл.В., Ефанов Д.В., Черепанова М.Р. Модульные коды с суммированием в системах функционального контроля. II. Уменьшение структурной избыточности систем функционального контроля // Электронное моделирование. 2016. Т. 38. № 3. С. 47–61.
  31. Ефанов Д.В., Осадчий Г.В., Зуева М.В. Особенности обнаружения ошибок кодами с суммированием единичных информационных разрядов в кольце вычетов по заданному модулю в схемах встроенного контроля, синтезированных на основе метода логического дополнения // Автоматика на транспорте. 2021. Т. 7. № 2. С. 284–314; https://doi.org/10.20295/2412-9186-2021-7-2-284-314
  32. Efanov D., Osadchy G., Zueva M. Specifics of Error Detection with Modular Sum Codes in Concurrent Error-Detection Circuits Based on Boolean Complement Method // Proc. IEEE East-West Design & Test Sympos. (EWDTS’2021). Batumi, Georgia, 2021. P. 59–69; https://doi.org/10.1109/EWDTS52692.2021.9581036
  33. Сапожников В.В., Сапожников Вл.В., Ефанов Д.В. Коды с суммированием для систем технического диагностирования. Т. 1. Классические коды Бергера и их модификации. М.: Наука, 2020. 383 с.
  34. Сапожников В.В., Сапожников Вл.В., Ефанов Д.В. Коды с суммированием для систем технического диагностирования. Т. 2. Взвешенные коды с суммированием. М.: Наука, 2021. 455 с.
  35. The On-Line Encyclopedia of Integer Sequences электронный ресурс (режим доступа: https://oeis.org/, 14.04.2024 г.).
  36. Грэхем Р.Л., Кнут Д.Э., Паташник О. Конкретная математика. Математические основы информатики, 2-е изд. / Пер. с англ. М.: ООО “И.Д. Вильямс”, 2017. 784 с.
  37. Ефанов Д.В. Синтез самопроверяемых комбинационных устройств на основе метода логической коррекции сигналов с применением кодов Боуза–Лина // Информационные технологии. 2023. Т. 29. № 10. С. 503–511; https://doi.org/10.17587/it.29.503-511
  38. 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. 747533, patented Jan. 26. N. Y., 1971, 10 p.
  39. Harris D.M., Harris S.L. Digital Design and Computer Architecture. Morgan Kaufmann, 2012. 569 p.
  40. Аксёнова Г.П. Необходимые и достаточные условия построения полностью проверяемых схем свертки по модулю 2 // АиТ. 1979. № 9. С. 126–135.
  41. Сапожников В.В., Сапожников Вл.В. Самопроверяемые дискретные устройства. СПб.: Энергоатомиздат, 1992. 224 с.
  42. Закревский А.Д., Поттосин Ю.В., Черемисинова Л.Д. Логические основы проектирования дискретных устройств. М.: Физматлит, 2007. 592 с.
  43. Sentovich E.M., Singh K.J., Moon C., Savoj H., Brayton R.K., Sangiovanni-Vincentelli A. Sequential Circuit Design Using Synthesis and Optimization // Proc. IEEE Intern. Conf. on Computer Design: VLSI in Computers & Processors. Cambridge, MA, USA, 1992. P. 328–333; https://doi.org/10.1109/ICCD.1992.276282
  44. Sentovich E.M., Singh K.J., Lavagno L., Moon C., Murgai R., Saldanha A. et al. SIS: A System for Sequential Circuit Synthesis. Electronics Research Laboratory, Department of Electrical Engineering and Computer Science, Berkeley: University of California, 1992, 45 p.
  45. Collection of Digital Design Benchmarks электронный ресурс (режим доступа: https://ddd.fit.cvut.cz/www/prj/Benchmarks/, 14.04.2024 г.).
  46. McElvain K. IWLS’93 Benchmark Set: Version 4.0. Distributed as a Part of IWLS’93 Benchmark Set, 1993.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download
2. Fig. 1. Weighing options for constructing WS(m, 2, 4) codes

Download (47KB)
Indexing metadata
3. Fig. 2. The number of ways to construct WS(m, 2, 4) and WS(m, 3, 8) codes

Download (167KB)
Indexing metadata
4. Fig. 3. Weighing options for constructing WS(m, 3, 8) codes

Download (41KB)
Indexing metadata
5. Fig. 4. The structure of the organization of the SVC based on the LKS

Download (143KB)
Indexing metadata
6. Fig. 5. The structure of the organization of the SVC based on the LCS for an 8-output device using the WS(6, 2, 4) code

Download (206KB)
Indexing metadata
7. Fig. 6. WS(6, 2, 4) code encoder: a – construction diagram, b – structure

Download (107KB)
Indexing metadata
8. Fig. 7. The structure of the organization of the SVC based on the LCS for an 8-output device using the WS(5, 3, 8) code

Download (196KB)
Indexing metadata
9. Fig. 8. WS(5, 3, 8) code encoder with an array of weight coefficients [1, 1, 2, 2, 2]: a – construction diagram, b – structure

Download (119KB)
Indexing metadata
10. Fig. 9. Encoder WS(5, 3, 8) code with an array of weight coefficients [2, 3, 4, 4, 2]: a – construction diagram, b – structure

Download (117KB)
Indexing metadata

Copyright (c) 2025 Russian Academy of Sciences