ISSN 0021-3454 (печатная версия)
ISSN 2500-0381 (онлайн версия)
Меню

8
Содержание
том 61 / АВГУСТ, 2018
СТАТЬЯ

DOI 10.17586/0021-3454-2018-61-4-323-335

УДК 681.518.5:004.052.32

ВЗВЕШЕННЫЙ КОД С СУММИРОВАНИЕМ БЕЗ ОПЕРАЦИИ ПЕРЕНОСА ДЛЯ РЕШЕНИЯ ЗАДАЧ ТЕХНИЧЕСКОЙ ДИАГНОСТИКИ ДИСКРЕТНЫХ СИСТЕМ

Сапожников В. В.
ПГУПС; профессор, кафедра автоматики и телемеханики на железных дорогах


Сапожников В. В.
ПГУПС; профессор, кафедра автоматики и телемеханики на железных дорогах


Ефанов Д. В.
ПГУПС; кафедра автоматики и телемеханики на железных дорогах


Аннотация. Проанализированы характеристики взвешенного кода с суммированием без операции переноса переполняемого разряда по обнаружению ошибок в самопроверяемых схемах встроенного контроля логических устройств автоматики и вычислительной техники. Показано, что описываемый код при использовании последовательности весовых коэффициентов, образующей натуральный ряд чисел, обеспечивает обнаружение любых однократных и двукратных ошибок в информационных векторах. По этому показателю предлагаемый код сравним с классическими кодами Хэмминга, однако имеет более простые функции вычисления значений контрольных разрядов. При некоторых значениях числа информационных разрядов код имеет меньшее на единицу число контрольных разрядов. Это обстоятельство позволяет организовывать самопроверяемые схемы встроенного контроля логических устройств с уменьшенной структурной избыточностью как по сравнению с дублированием, так и по сравнению с использованием для этих целей кода Хэмминга. У кодов Хэмминга лучшие характеристики обнаружения ошибок различного вида (монотонная, симметричная или асимметричная) и кратности, что определяет и большее число идентифицируемых на выходах логических устройств ошибок, чем при использовании предлагаемого взвешенного кода. Эксперименты с системами контрольных комбинационных схем LGSynth`89 и MCNC Benchmarks подтверждают теоретически полученные закономерности.
Ключевые слова: техническая диагностика, самопроверяемая схема встроенного контроля, обнаружение неисправностей, информационный вектор, ошибка, код Хэмминга, взвешенный код с суммированием без переносов, контрольная комбинационная схема, структурная избыточность

Список литературы:
  1. McCluskey E. J. Logic Design Principles: With Emphasis on Testable Semicustom Circuits. New Jersey: Prentice Hall PTR, 1986. 549 p.
  2. Rao T. R., Fujiwara E. Error Control Coding for Computer Systems. NY: Prentice Hall, 1989. 584 p.
  3. Pradhan D. K. Fault-Tolerant Computer System Design. NY: Prentice Hall, 1996. 560 p.
  4. Abramovici M., Breuer M. A., Friedman A. D. Digital System Testing and Testable Design. Computer Science Press, 1998. 652 p.
  5. Fujiwara E. Code Design for Dependable Systems: Theory and Practical Applications. New Jersey: John Wiley & Sons, 2006. 720 p.
  6. Пархоменко П. П., Согомонян Е. С. Основы технической диагностики (оптимизация алгоритмов диагностирования, аппаратурные средства). М.: Энергоатомиздат, 1981. 320 с.
  7. Согомонян Е. С., Слабаков Е. В. Самопроверяемые устройства и отказоустойчивые системы. М.: Радио и связь, 1989. 208 с.
  8. Сапожников В. В., Сапожников Вл. В. Самопроверяемые дискретные устройства. СПб: Энергоатомиздат, 1992. 224 с.
  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. Гавзов Д. В., Сапожников В. В., Сапожников Вл. В. Методы обеспечения безопасности дискретных систем // Автоматика и телемеханика. 1994. № 8. С. 3—50.
  11. Дрозд А. В., Харченко В. С., Антощук С. Г., Дрозд Ю. В., Дрозд М. А., Сулима Ю. Ю. Рабочее диагностирование безопасных информационно-управляющих систем. Харьков: Национальный аэрокосмический университет им. Н.Е. Жуковского „ХАИ“, 2012. 614 с.
  12. Kharchenko V., Kondratenko Yu., Kacprzyk J. Green IT Engineering: Concepts, Models, Complex Systems Architectures. Book series "Studies in Systems, Decision and Control". Springer, 2017. Vol. 74. 305 p. DOI: 10.1007/978-3-319-44162-7.
  13. Nicolaidis M., Zorian Y. On-Line Testing for VLSI — А Compendium of Approaches // J. of Electronic Testing: Theory and Application. 1998. Vol. 12, Is. 1—2. P. 7—20. DOI: 10.1023/A:1008244815697.
  14. Zeng C., McCluskey E. J. Finite State Machine Synthesis with Concurrent Error Detection // Intern. Test Conf. Atlantic City, NJ, 1999. P. 672—679. DOI: 10.1109/TEST.1999.805795.
  15. Mitra S., McCluskey E. J. Which Concurrent Error Detection Scheme to Choose? // Proc. of Intern. Test Conf. Atlantic City, NJ, 03—05 October 2000. P. 985—994, DOI: 10.1109/TEST.2000.894311.
  16. Das D., Touba N. A. Weight-Based Codes and Their Application to Concurrent Error Detection of Multilevel Circuits // Proc. of 17th IEEE Test Symposium. California, USA, 1999. P. 370—376. 
  17. Ефанов Д. В., Сапожников В. В., Сапожников Вл. В. Условия обнаружения неисправности логического элемента в комбинационном устройстве при функциональном контроле на основе кода Бергера // Автоматика и телемеханика. 2017. № 5. С. 152—165.
  18. Сапожников В. В., Сапожников Вл. В., Ефанов Д. В. Взвешенные коды с суммированием для организации контроля логических устройств // Электронное моделирование. 2014. Т. 36, № 1. С. 59—80.
  19. Huches J. L. A., McCluskey E. J., Lu D. J. Design of Totally Self-Checking Comparators with an Arbitrary Number of Inputs // IEEE Transact. on Computers. 1984. Vol. C-33, N 6. P. 546—550.
  20. Morosow A., Sapozhnikov V. V., Sapozhnikov Vl. V., Goessel M. Self-Checking Combinational Circuits with Unidirectionally Independent Outputs // VLSI Design. 1998. Vol. 5, Is. 4. P. 333—345. DOI: 10.1155/1998/20389.
  21. Hamming R. W. Error Detecting and Correcting Codes // Bell System Technical J. 1950. Vol. 29, N 2. P. 147—160.
  22. Ефанов Д. В. Предельные свойства кода Хэмминга в схемах функционального диагностирования // Информатика и системы управления. 2011. № 3. С. 70—79.
  23. Ефанов Д. В., Блюдов А. А. Коды Хэмминга и их обнаруживающие способности в схемах функционального контроля // Информатика и системы управления. 2012. № 2. С. 100—111.
  24. Sapozhnikov V., Sapozhnikov Vl., Efanov D., Blyudov A. Analysis of Error-Detection Possibilities of CED Circuits Based on Hamming and Berger Codes // Proc. of 11th IEEE East-West Design & Test Symposium (EWDTS`2013). Rostov-on-Don, Russia, 27—30 September 2013. P. 200—207. DOI: 10.1109/EWDTS.2013.6673097.
  25. Сапожников В. В., Сапожников Вл. В., Ефанов Д. В. Исследование свойств кодов Хэмминга и их модификаций в системах функционального контроля // Автоматика на транспорте. 2015. Т. 1, № 3. С. 311—337.
  26. Сапожников В. В., Сапожников Вл. В., Ефанов Д. В. Особенности применения кодов Хэмминга при организации самопроверяемых схем встроенного контроля // Изв. вузов. Приборостроение. 2018. Т. 61, № 1. С. 47—59.
  27. 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 14th IEEE East-West Design & Test Symposium (EWDTS`2016). Yerevan, Armenia, 14—17 October 2016. P. 134—141. DOI: 10.1109/EWDTS.2016.7807686.
  28. Сапожников Вал. В., Сапожников Вл. В., Ефанов Д. В., Дмитриев В. В. Код с суммированием взвешенных информационных разрядов без переносов в системах функционального контроля // Автоматика на транспорте. 2017. Т. 3, № 3. С. 414—433.
  29. Berger J. M. А Note on Error Detecting Codes for Asymmetric Channels // Information and Control. 1961. Vol. 4, Is. 1. P. 68—73. DOI:10.1016/S0019-9958(61)80037-5.
  30. Блюдов А. А., Ефанов Д. В., Сапожников В. В., Сапожников Вл. В. Построение модифицированного кода Бергера с минимальным числом необнаруживаемых ошибок информационных разрядов // Электронное моделирование. 2012. Т. 34, № 6. С. 17—29.
  31. Сапожников В. В., Сапожников Вл. В., Ефанов Д. В. Классификация ошибок в информационных векторах систематических кодов // Изв. вузов. Приборостроение. 2015. Т. 58, № 5. С. 333—343. DOI: 10.17586/0021-3454-2015-58-5-333-343.
  32. Collection of Digital Design Benchmarks [Электронный ресурс]: http://ddd.fit.cvut.cz/prj/Benchmarks/.
  33. 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.