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