В.В. Сапожніков, Вол.В. Сапожніков, Д.М. Єфанов
È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 г. окончил Петербургский государственный университет путей сообщения. Область научных исследований—дискретная математика, надежность и техническая диагностика дискретных систем.