Взвешенные коды с перестановками — новый класс кодов с суммированием для технической диагностики дискретных систем

В.В. Сапожников, д-р техн. наук, Вл.В. Сапожников, д-р техн. наук,
Д.В. Ефанов, канд. техн. наук
Петербургский госуниверситет путей сообщения Императора Александра I
(Российская Федерация, 190031, Санкт-Петербург, Московский пр., 9,
тел. (+7) 9117092164, (+7) (812) 4578579, e-mail: Этот адрес электронной почты защищён от спам-ботов. У вас должен быть включен JavaScript для просмотра.)

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

Полный текст: PDF