Коды с суммированием единичных и одного взвешенного разрядов с произвольными модулями счета

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

Èlektron. model. 2019, 41(4):49-72
https://doi.org/10.15407/emodel.41.04.049

АННОТАЦИЯ

Представлен новый класс кодов, ориентированных на обнаружение ошибок в информационных векторах. Принципы построения новых кодов основаны на взвешивании всех
разрядов информационных векторов, кроме одного, единичными весовыми коэффициентами и одного разряда — неединичным весовым коэффициентом с дальнейшим подсчетом наименьшего неотрицательного вычета суммарного веса единичных информационных разрядов по заранее установленному модулю. Описан данный класс кодов и приведена классификация семейств кодов в зависимости от длин контрольных векторов. Определена мощность множества модульных кодов с суммированием единичных и одного взвешенного разрядов для каждого значения длины информационного вектора. Рассмотрены некоторые особенности обнаружения ошибок в информационных векторах кодами рассматриваемого класса, что актуально при решении задач обнаружения неисправностей в аппаратных реализациях логических устройств систем автоматического управления.

КЛЮЧЕВЫЕ СЛОВА:

избыточные коды, коды с обнаружением ошибок, коды с суммированием, контролепригодные автоматические устройства, информационный вектор, техническая диагностика, отказоустойчивость.

СПИСОК ЛИТЕРАТУРЫ

1. Согомонян Е.С., Слабаков Е.В. Самопроверяемые устройства и отказоустойчивые системы. М.: Радио и связь, 1989, 208 с.
2. Сапожников В.В., Сапожников Вл.В., Христов Х.А., Гавзов Д.В. Методы построения безопасных микроэлектронных систем железнодорожной автоматики. – Под ред. Вл. В. Сапожникова. М.: Транспорт, 1995, 272 с.
3. Ubar R., Raik J., Vierhaus H.-T. Design and Test Technology for Dependable Systemson-Chip (Premier Reference Source). Information Science Reference. Hershey — New York, IGI Global, 2011, 578 p.
4. Дрозд А.В., Харченко В.С., Антощук С.Г. и др. Рабочее диагностирование безопасных информационно-управляющих систем. Под ред. А.В. Дрозда и В.С. Харченко. Харьков: Национальный аэрокосмический университет им. Н.Е. Жуковского «ХАИ», 2012, 614 с.
5. Kharchenko V., Kondratenko Yu., Kacprzyk J. Green IT Engineering: Concepts, Models, Complex Systems Architectures // Springer Book series “Studies in Systems, Decision and Control”, 2017, vol. 74, 305 p. DOI: 10.1007/978-3-319-44162-7.
6. Fujiwara E. Code Design for Dependable Systems: Theory and Practical Applications. John Wiley & Sons, 2006, 720 p.
7. Ryan W.E., Lin S. Channel Codes: Classical and Modern. Cambridge University Press, 2009, 708 р.
8. Сапожников В.В., Сапожников Вл.В. Самопроверяемые тестеры для равновесных кодов // Автоматика и телемеханика, 1992, № 3, с. 3—35.
9. Piestrak S.J. Design of Self-Testing Checkers for Unidirectional Error Detecting Codes. Wroclaw: Oficyna Wydawnicza Politechniki Wroclavskiej, 1995, 111 p.
10. Nicolaidis M., Zorian Y. On-Line Testing for VLSI – А Compendium of Approaches // Journal of Electronic Testing: Theory and Applications, 1998, № 12, p. 7—20. DOI: 10.1023/A:1008244815697.
11. Das D., Touba N.A. Synthesis of Circuits with Low-Cost Concurrent Error Detection Based on Bose-Lin Codes // Journal of Electronic Testing: Theory and Applications, 1999, vol. 15, issue 1-2, p. 145—155. DOI: 10.1023/A:1008344603814.
12. 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.
13. Kubalik P., Kubatova H. Parity Codes Used for On-Line Testing in FPGA // Acta Polytechnika,2005, vol. 45, No. 6, p. 53—59. 
14. 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.
15. Shah T., Singh V., Matrosova A. Test Pattern Generation to Detect Multiple Faults inROBDD Based Combinational Circuits // Proc. of 23rd IEEE On-Line Testing and RobustSystem Design (IOLTS`2017). Thessaloniki, Greece, 3—5 July 2017, p. 211—212. DOI:10.1109/IOLTS.2017.8046223.
16. Matrosova A., Ostanin S., Tretyakov D., Butorina N. Logic Circuit Design with Gates, LUTsand MUXs Oriented to Mask Faults // Proc. of 15th IEEE East-West Design & Test Symposium(EWDTS`2017). Novi Sad, Serbia, September 29 – October 2, 2017, p. 95—98. DOI:10.1109/EWDTS.2017.8110096.
17. Сапожников В.В., Сапожников Вл.В., Ефанов Д.В. Коды Хэмминга в системах функционального контроля логических устройств. СПб.: Наука, 2018, 151 с.
18. Ефанов Д.В. Функциональный контроль и мониторинг устройств железнодорожной автоматики и телемеханики. СПб.: ФГБОУ ВО ПГУПС, 2016, 171 с.
19. Гавзов Д.В., Дрейман О.К., Кононов В.А., Никитин А.Б. Системы диспетчерской централизации. – Под общей ред. проф. Вл.В. Сапожникова, М.: Маршрут, 2002, 407 с.
20. Сапожников В.В., Сапожников Вл.В., Ефанов Д.В. Основы теории надежности и технической диагностики. — Санкт-Петербург: Издательство «Лань», 2019, 588 с.
21. Ефанов Д.В., Блюдов А.А. Повышение надежности датчиков контроля положения железнодорожных стрелок // Изв. Петербургского университета путей сообщения,2014, №3, с. 69—77.
22. Ostanin S. Self-Checking Synchronous FSM Network Design for Path Delay Faults // Proc. of 15th IEEE East-West Design&Test Symposium (EWDTS`2017). Novi Sad, Serbia, September 29— October 2, 2017, p. 696—699. DOI: 10.1109/EWDTS.2017.8110129.
23. 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.1016/S0019-9958(61)80037-5.
24. Freiman C.V. Optimal Error Detection Codes for Completely Asymmetric Binary Channels // Ibid, 1962, vol. 5, issue 1, p. 64—71. DOI: 10.1016/S0019-9958(62)90223-1.
25. 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. DOI: 10.1109/VTEST.1999.766691.
26. Das D., Touba N.A., Seuring M., Gossel M. Low Cost Concurrent Error Detection Based on Modulo Weight-Based Codes // Proc. of the IEEE 6th International On-Line Testing Workshop (IOLTW). Spain, Palma de Mallorca, July 3—5, 2000, p. 171—176. DOI: 10.1109/OLT.2000.856633.
27. Мехов В.Б., Сапожников В.В., Сапожников Вл.В. Контроль комбинационных схем на основе модифицированных кодов с суммированием // Автоматика и телемеханика, 2008, №8, c. 153—165.
28. Сапожников В.В., Сапожников Вл.В., Ефанов Д.В. Взвешенные коды с суммированием для организации контроля логических устройств // Электрон. моделирование,2014, 36, № 1, c. 59—80.
29. Блюдов А.А., Ефанов Д.В., Сапожников В.В., Сапожников Вл.В. О кодах с суммированием единичных разрядов в системах функционального контроля // Автоматика и телемеханика, 2014, № 8, c. 131—145.
30. Ефанов Д.В., Сапожников В.В., Сапожников Вл.В. Применение модульных кодов с суммированием для построения систем функционального контроля комбинационных логических схем // Там же, 2015, № 10, с. 152—169.
31. Efanov D.V., Sapozhnikov V.V., Sapozhnikov Vl.V. Two-Modulus Codes with Summation ofOne-Data Bits for Technical Diagnostics of Discrete Systems // Automatic Control andComputer Sciences, 2018, vol. 52, issue 1, p. 1—12. DOI: 10.3103/S0146411618010029.
32. Efanov D., Sapozhnikov V., Sapozhnikov Vl. Generalized Algorithm of Building SummationCodes for the Tasks of Technical Diagnostics of Discrete Systems // Proc. of 15th IEEEEast-West Design & Test Symposium (EWDTS`2017). Novi Sad, Serbia, September 29 –October 2, 2017, p. 365—371. DOI: 10.1109/EWDTS.2017.8110126.
33. Сапожников В.В., Сапожников Вл.В., Ефанов Д.В. Построение кодов с суммированием с наименьшим количеством необнаруживаемых симметричных ошибок в информационных векторах // Радиоэлектроника и информатика, 2014, № 4, c. 46—55.
34. Сапожников В.В., Сапожников Вл.В., Ефанов Д.В. Контроль комбинационных схем на основе кодов с суммированием с одним взвешенным информационным разрядом // Автоматика на транспорте, 2016, 2, № 4, c. 564—597.
35. Efanov D., Sapozhnikov V., Sapozhnikov Vl. On Variety of Sum Codes with On-Data Bits and One Weighted Data Bit in Concurrent Error Detection Systems // Proc. of 2nd International Conference on Industrial Engineering, Applications and Manufacturing (ICIEAM).Chelyabinsk, Russia, 19, 20 May, 2016. DOI: 10.1109/ICIEAM.2016.7911684.
36. Efanov D., Sapozhnikov V., Sapozhnikov Vl. The Use of Codes with Fixed Multiplicities of Detected Unidirectional and Asymmetrical Errors in the Process of Organizing Combinational Circuit Testing // Proc. of 16th IEEE East-West Design&Test Symposium (EWDTS`2018). Kazan, Russia, September 14—17, 2018, p. 114—122. DOI:10.1109/EWDTS.2018.8524768.
37. Сапожников В.В., Сапожников Вл.В., Ургансков Д.И. Метод построения тестеров кодовых векторов // Электрон. моделирование, 2000, 22, № 6, c. 66—76.
38. Сапожников В.В., Сапожников Вл.В., Ургансков Д.И. Универсальные структуры двоичных счетчиков единиц по произвольному модулю счета // Там же, 2002, 24, № 4, с. 65—81.
39. Сапожников В.В., Сапожников Вл.В., Ургансков Д.И. Блочная структура двоичного счетчика единиц по произвольному модулю счета // Там же, 2005, 27,№4, с. 65—81.
40. Saposhnikov V.V., Saposhnikov Vl.V., Urganskov D.I. Composite Structure of Binary Counterof Ones Arbitrary Modulo // Proc. of East-West Design&Test Workshop (EWDTW`05),15—19 September 2005, Odessa, Ukraine, p. 102—106.
41. Saposhnikov V.V., Saposhnikov Vl.V., Urganskov D.I. Multistage Regular Structure of BinaryCounter of Ones Arbitrary Modulo // Proc. of East-West Design & Test Workshop(EWDTW`06). 15—19 September 2006. Sochi, Russia, p. 287—290.
42. Bibilo P.N., Gorodetskii D.A Automated Design of Modular Arithmetic Devices: MightCAD Replace an Engineer //Automatic Control and Computer Sciences, 2009, vol. 43, issue 2,p. 63—73. DOI: 10.3103/S0146411609020023.
43. Suprun V.P., Gorodetskii D.A. Synthesis of N-Operand Modulo-Three Adders // Ibid, 2010,vol. 44, issue 3, p. 171—177. DOI: 10.3103/S0146411610030089.
44. Suprun V.P., Gorodecky D.A. Realization of Addition and Multiplication Operations in UnitaryCodes // Ibid, 2010, vol. 44, issue 5, p. 292-301. DOI: 10.3103/S014641161005007X.
45. Suprun V.P. Single-Level Schematic Realization of Basic Operations of Modular Arithmeticin Unitary Codes // Ibid, 2011, vol. 45, issue 2, p. 70—79. DOI: 10.3103/S0146411611020088.
46. Сапожников В.В., Сапожников Вл.В., Ефанов Д.В. Классификация ошибок в информационных векторах систематических кодов // Изв. вузов. Приборостроение, 2015, 58, № 5, c. 333—343. DOI: 10.17586/0021-3454-2015-58-5-333-343.
47. Стемпковский А.Л., Тельпухов Д.В., Соловьев Р.А. и др. Разработка технологически независимых метрик для оценки маскирующих свойств логических схем // Вычислительные технологии, 2016, 21, № 2, с. 53—62.
48. Göessel M., Ocheretny V., Sogomonyan E., Marienfeld D. New Methods of ConcurrentChecking: Edition 1. Dordrecht: Springer Science+Business Media B.V., 2008, 184 p.49. Collection of Digital Design Benchmarks [http://ddd.fit.cvut.cz/prj/Benchmarks/].
50. Сапожников В.В., Сапожников Вл.В., Ефанов Д.В. Выбор модифицированного кода с суммированием единичных информационных разрядов для логических устройств с известной топологией // Автоматика на транспорте, 2017, 3, № 4, с. 578—604.
51. Sentovich E.M., Singh K.J., Moon C. et al. Sequential Circuit Design Using Synthesis andOptimization // Proc. IEEE International Conference on Computer Design: VLSI in Computers& Processors. 11—14 October 1992, Cambridge, MA, USA, USA, p. 328—333.DOI: 10.1109/ICCD.1992.276282.
52. Дмитриев В.В., Ефанов Д.В., Сапожников В.В., Сапожников Вл.В. Коды с суммированием с эффективным обнаружением двукратных ошибок для организации систем функционального контроля логических устройств // Автоматика и телемеханика, 2018, № 4, c. 105—122.
53. Ефанов Д.В. Синтез самопроверяемых комбинационных устройств на основе кодов с эффективным обнаружением симметричных ошибок // Труды СПИИРАН, 2018,№4, c. 62—91. DOI: 10.15622/SP.59.3.
54. Ефанов Д.В., Сапожников В.В., Сапожников Вл.В. Синтез самопроверяемых комбинационных устройств на основе выделения специальных групп выходов // Автоматика и телемеханика, 2018, № 9, c. 79—94.

ЕФАНОВ Дмитрий Викторович, д-р техн. наук, доцент, профессор кафедры «Автоматика,
телемеханика и связь на железнодорожном транспорте» Российского университета транспорта,
руководитель направления систем мониторинга и диагностики ООО «ЛокоТехСигнал
». В 2007 г. окончил Петербургский государственный университет путей сообщения.
Область научных исследований—дискретная математика, надежность и техническая диагностика
дискретных систем.

САПОЖНИКОВ Валерий Владимирович, д-р техн. наук, профессор, профессор кафедры «Автоматика
и телемеханика на железных дорогах» Петербургского государственного университета
путей сообщения Императора Александра I. В 1963 г. окончил Ленинградский ин-т
инженеров железнодорожного транспорта. Область научных исследований — надежностный
синтез дискретных устройств, синтез безопасных систем, синтез самопроверяемых
схем, техническая диагностика дискретных систем.

САПОЖНИКОВ Владимир Владимирович, д-р техн. наук, профессор, профессор кафедры
«Автоматика и телемеханика на железных дорогах» Петербургского государственного университета
путей сообщения Императора Александра I. В 1963 г. окончил Ленинградский ин-т
инженеров железнодорожного транспорта. Область научных исследований — надежностный
синтез дискретных устройств, синтез безопасных систем, синтез самопроверяемых
схем, техническая диагностика дискретных систем.

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