Перейти до змісту
Електронне моделювання

ЗВАЖЕНІ КОДИ З ПЕРЕСТАНОВКАМИ — НОВИЙ КЛАС КОДІВ З ПІДСУМОВУВАННЯМ ДЛЯ ТЕХНІЧНОЇ ДІАГНОСТИКИ ДИСКРЕТНИХ СИСТЕМ

В.В. Сапожніков, Вол.В. Сапожніков, Д.М. Єфанов

Èlektron. model. 2018, 40(2):43-70
https://doi.org/10.15407/emodel.40.02.043

Повний текст (PDF)

English version

Анотація

Описано спосіб побудови коду з підсумовуванням, який ефективно виявляє помилки в області малої кратності. Спосіб базовано на зважуванні переходів між розрядами, займаючими сусідні позиції в інформаційних векторах, ваговими коефіцієнтами з натурального ряду чисел, подальшому обчисленні модифікованої ваги информаційного вектора, а також на застосуванні серії спеціальних перестановок підсумкових вагів між інформаційними векторами. Контрольні функції отримуваного «перестановочного» коду є лінійними і описуються тільки з використанням операції підсумовування по модулю два. Проанал
ізовано властивості виявлення помилок різних видів і кратностей новими кодами та проведено порівняння з відомими кодами, які виявляють кратні помилки. Встановлено, що новий код виявляє будь-які двократні помилки в інформаційних векторах при довжинах інформаційних векторів m < 10. Показано, що перестановочний код має перевагу перед будь-якими кодами виявлення двократних помилок при довжинах інформаційних векторів m = 8 і m = 9. Експерименти з контрольними комбінаційними схемами дозволили підтвердити теоретичні результати, а також оцінити ефективність застосування нового коду в системах функціонального контролю за показниками структурної надлишковості.

Ключові слова

технічна діагностика дискретних систем, код з підсумовуванням, код Бергера, код Хеммінга, модифікований зважений код, виявлення двократних помилок, структурна надлишковість

Список літератури

  1. 1. Пархоменко П.П., Согомонян Е.С. Основы технической диагностики (оптимизация алгоритмов
  2. диагностирования, аппаратурные средства). М.: Энергоатомиздат, 1981, 320 с.
  3. 2. McCluskey E.J. Logic Design Principles: With Emphasis on Testable Semicustom Circuits.
  4. N.J.: Prentice Hall PTR, 1986, 549 p.
  5. 3. Согомонян Е.С., Слабаков Е.В. Самопроверяемые устройства и отказоустойчивые
  6. системы. М.: Радио и связь, 1989, 207 с.
  7. 4. Goessel M., Graf S. Error Detection Circuits. London: McGraw-Hill, 1994, 261 p.
  8. 5. Abramovici M., Breuer M.A., Friedman A.D. Digital System Testing and Testable Design.
  9. Computer Science Press, 1998, 652 p.
  10. 6. Fujiwara E. Code Design for Dependable Systems: Theory and Practical Applications. John
  11. Wiley & Sons, 2006, 720 p.
  12. 7. Freiman C.V. Optimal Error Detection Codes for Completely Asymmetric Binary Channels //
  13. Information and Control, 1962, Vol. 5, issue 1, p. 64—71. DOI: 10.1016/S0019-9958(62)
  14. 90223-1.
  15. 8. Berger J.M. A Note on Error Detection Codes for Asymmetric Channels // Information and
  16. Control, 1961, Vol. 4, Issue 1, p. 68—73. DOI: 10.16/S0019-9958(61)80037-5.
  17. 9. Borden J.M. Optimal Asymmetric Error Detecting Codes // Ibid, 1982, Vol. 53, Issue 1-2,
  18. p. 66—73, DOI: 10.1016/S0019-9958(82)91125-1.
  19. 10. Dong H. Modified Berger Codes for Detection of Unidirectional Errors // IEEE Transaction
  20. on Computers, 1984, Vol. C-33, June, p. 572—575.
  21. 11. Blaum M. On Systematic Burst Unidirectional Error Detecting Codes // Ibid, 1988, Vol. 37,
  22. Issue 4, p. 453—457. DOI 10.1109/12.2190.
  23. 12. Parhami B. New Class of Unidirectional Error-Detection Codes // Proc. of IEEE International
  24. Conf. on Computer Design: VLSI in Computers and Processors. 14-16 Oct 1991
  25. (ICCD’9). Cambridge, MA, p. 574—577.
  26. 13. Das D., Touba N.A. Weight-Based Codes and Their Application to Concurrent Error Detection
  27. of Multilevel Circuits // Proc. of 17th IEEE Test Symposium. USA, California, 1999,
  28. p. 370—376.
  29. 14. Göessel M., Ocheretny V., Sogomonyan E., Marienfeld D. New Methods of Concurrent
  30. Checking: Edition 1. Dordrecht: Springer Science+Business Media B.V., 2008, 184 p.
  31. 15. Согомонян Е.С. Построение самопроверяемых схем встроенного контроля для комбинационных
  32. устройств // Автоматика и телемеханика, 1974, № 2, c. 121—133.
  33. 16. Слабаков Е.В., Согомонян Е.С. Самопроверяемые вычислительные устройства и системы
  34. (обзор) // Там же, 1981, №11, c. 147—167.
  35. 17. Ghosh S., Basu S., Touba N.A. Synthesis of Low Power CED Circuits Based on Parity Codes //
  36. Proc. of 23rd IEEE VLSI Test Symposium (VTS’05), 2005, p. 315—320.
  37. 18. Аксенова Г.П. О функциональном диагностировании дискретных устройств в условиях
  38. работы с неточными данными // Проблемы управления, 2008, №5, с. 62—66.
  39. 19. Busaba F.Y., Lala P.K. Self-Checking Combinational Circuit Design for Single and Unidirectional
  40. Multibit Errors // Journal of Electronic Testing: Theory and Applications, 1994, Issue
  41. 1, p. 19—28. DOI: 10.1007/BF00971960.
  42. 20. Matrosova A.Yu., Levin I., Ostanin S.A. Self-Checking Synchronous FSM Network Design
  43. with Low Overhead // VLSI Design, 2000, Vol. 11, Issue 1, p. 47—58. DOI: 10.1155/
  44. 2000/46578.
  45. 21. Morosow A., Saposhnikov V.V., Saposhnikov Vl.V., Göessel M. Self-Checking Combinational
  46. Circuits with Unidirectionally Independent Outputs // VLSI Design, 1998, Vol. 5, Issue
  47. 4, p. 333—345. DOI: 10.1155/1998/20389.
  48. 22. Saposhnikov V.V., Morosov A., Saposhnikov Vl.V., Göessel M. A New Design Method for
  49. Self-Checking Unidirectional Combinational Circuits // Journal of Electronic Testing: Theory
  50. and Applications,1998, Vol. 12, Issue 1-2, p. 41—53. DOI: 10.1023/A:1008257118423.
  51. 23. Piestrak S.J. Design of Self-Testing Checkers for Unidirectional Error Detecting Codes.
  52. Wroclaw: Oficyna Wydawnicza Politechniki Wroclavskiej, 1995, 111 p.
  53. 24. Mitra S., McCluskey E.J. Which Concurrent Error Detection Scheme to Ñhoose? // Proc. of
  54. International Test Conf., 2000, USA, Atlantic City, NJ, 03-05 October 2000, p. 985—994,
  55. DOI: 10.1109/TEST.2000.894311 .
  56. 25. Sapozhnikov V., Sapozhnikov Vl., Efanov D., Dmitriev V. Method of Combinational Circuits
  57. Testing by Dividing its Outputs into Groups and Using Codes, that Effectively Detect Double
  58. Errors // Proc. of 15th IEEE East-West Design&Test Symposium (EWDTS`2017). Novi
  59. Sad, Serbia, September 29—October 2, 2017, p. 129—136. DOI: 10.1109/EWDTS. 2017.
  60. 8110123.
  61. 26. Ефанов Д.В., Сапожников В.В., Сапожников Вл.В. О свойствах кода с суммированием в
  62. схемах функционального контроля //Автоматика и телемеханика, 2010, №6, с. 155— 162.
  63. 27. Sapozhnikov V., Sapozhnikov Vl., Efanov D., Nikitin D. Combinational Circuits Checking on
  64. the Base of Sum Codes with One Weighted Data Bit // Proc. of 12th IEEE East-West Design
  65. & Test Symposium (EWDTS`2014). Kyiv, Ukraine, September 26-29, 2014, p. 126—136,
  66. DOI:10.1109/EWDTS.2014.7027064.
  67. 28. Hamming R.W. Error Detecting and Correcting Codes // Bell System Technical Journal,
  68. 1950, 29 (2), p. 147—160. MR0035935.
  69. 29. Mehov V., Saposhnikov V, Sapozhnikov Vl., Urganskov D. Concurrent Error Detection
  70. Based on New Code with Modulo Weighted Transitions between Information Bits // Proc. of
  71. 7th IEEE East-West Design & Test Workshop (EWDTW`2007). Erevan, Armenia, September
  72. 25-30, 2007, p. 21—26.
  73. 30. Мехов В.Б., Сапожников В.В., Сапожников Вл.В. Контроль комбинационных схем на
  74. основе модифицированных кодов с суммированием // Автоматика и телемеханика,
  75. 2008, №8, с. 153—165.
  76. 31. Сапожников В.В., Сапожников Вл.В., Ефанов Д.В., Дмитриев В.В. Новые структуры
  77. систем функционального контроля логических схем // Автоматика и телемеханика,
  78. 2017, №2, с. 127—143.
  79. 32. Sapozhnikov V., Sapozhnikov Vl., Efanov D., Dmitriev V. New Sum Code for Effective Detection
  80. of Double Errors in Data Vectors // Proc. of 13th IEEE East-West Design & Test
  81. Symposium (EWDTS`2015). Batumi, Georgia, September 26-29, 2015, p. 154—159. DOI:
  82. 10.1109/EWDTS.2015.7493123.
  83. 33. Сапожников В.В., Сапожников Вл.В., Ефанов Д.В., Дмитриев В.В. Об одной модификации
  84. кода с суммированием взвешенных переходов между разрядами информационных
  85. векторов // Изв. вузов. Физика, 2016, 59, №8/2, с. 89—92.
  86. 34. Сапожников В.В., Сапожников Вл.В., Ефанов Д.В. Классификация ошибок в информационных
  87. векторах систематических кодов // Изв. вузов. Приборостроение, 2015, 58,
  88. №5, с. 333—343. DOI:10.17586/0021-3454-2015-58-5-333-343.
  89. 35. Блюдов А.А., Ефанов Д.В., Сапожников В.В., Сапожников Вл.В. Построение модифицированного
  90. кода Бергера с минимальным числом необнаруживаемых ошибок информационных
  91. разрядов // Электрон. моделирование, 2012, 34, № 6, с. 17—29.
  92. 36. Sapozhnikov V., Sapozhnikov Vl., Efanov D., Dmitriev V. Weighted Sum Code Without Carries—
  93. is an Optimum Code with Detection of Any Double Errors in Data Vectors // Proc. of
  94. 14th IEEE East-West Design&Test Symposium (EWDTS`2016). Yerevan, Armenia, October
  95. 14-17, 2016, p. 134—141. DOI:10.1109/EWDTS.2016.7807686.
  96. 37. Collection of Digital Design Benchmarks. Ðåæèì äîñòóïà: http://ddd.fit.cvut.cz/prj/
  97. Benchmarks/.
  98. 38. SIS: A System for Sequential Circuit Synthesis / E.M. Sentovich, K.J. Singh, L. Lavagno et
  99. al. // Electronics Research Laboratory, Department of Electrical Engineering and Computer
  100. Science, University of California. Berkeley, 4 May, 1992, 45 p.
  101. САПОЖНИКОВ Валерий Владимирович, д-р техн. наук, профессор кафедры «Автоматика и телемеханика на железных дорогах» Петербургского госуниверситета путей сообщения Императора Александра I. В 1963 г. окончил Ленинградский ин-т инженеров железнодорожного транспорта. Область научных исследований — надежностный синтез дискретных устройств, синтез безопасных систем, синтез самопроверяемых схем, техническая диагностика дискретных систем.
  102. САПОЖНИКОВ Владимир Владимирович, д-р техн. наук, профессор кафедры «Автоматика и телемеханика на железных дорогах» Петербургского госуниверситета путей сообщения Императора Александра I. В 1963 г. окончил Ленинградский ин-т инженеров железнодорожного транспорта. Область научных исследований — надежностный синтез дискретных устройств, синтез безопасных систем, синтез самопроверяемых схем, техническая диагностика дискретных систем.
  103. ЕФАНОВ Дмитрий Викторович, канд. техн. наук, доцент кафедры «Автоматика и телемеханика на железных дорогах» Петербургского госуниверситета путей сообщения Императора Александра I. В 2007 г. окончил Петербургский государственный университет путей сообщения. Область научных исследований—дискретная математика, надежность и техническая диагностика дискретных систем.