Модульные коды с суммированием взвешенных переходов с последовательностью весовых коэффициентов, образующей натуральный ряд чисел
Ключевые слова:
техническая диагностика, функциональный контроль, разделимый код, код Бергера, модульный код с суммированием, код с суммированием взвешенных переходов, необнаруживаемая ошибка, характеристики кодаАннотация
При построении надежных дискретных систем используются разделимые коды с простыми правилами построения и небольшой избыточностью. Часто применяются коды с суммированием с постоянным значением количества контрольных разрядов вне зависимости от длины информационного вектора. В статье показано, что характеристики обнаружения ошибок данными кодами могут быть улучшены за счет модификации правил вычисления значений разрядов контрольных векторов. Предложен алгоритм построения кода с суммированием, основанный на взвешивании переходов между разрядами, занимающими соседние позиции в информационных векторах, и подсчете суммарного веса информационного вектора по модулю, равному степени числа 2. В статье детально анализируются свойства новых кодов с суммированием в сравнении с известными кодами. Установлены условия построения помехоустойчивых модульных взвешенных кодов с суммированием с максимальным количеством обнаруживаемых ошибок в информационных векторах. Улучшение характеристик обнаружения ошибок в новых кодах по сравнению с классическими кодами с суммированием достигается за счет равномерного распределения информационных векторов между всеми контрольными векторами, что, в свою очередь, вносит в класс необнаруживаемых помимо симметричных, некоторую долю монотонных и асимметричных ошибок. В отличие от модульных кодов с суммированием единичных разрядов модульные взвешенные коды обнаруживают большее количество симметричных ошибок, однако доминирующим их видом практически при любой длине информационного вектора являются асимметричные ошибки. Модульные коды с суммированием взвешенных переходов являются перспективным классом разделимых кодов для решения задач технической диагностики дискретных систем.Литература
1. Кравцов Ю.А., Архипов Е.В., Бакин М.Е. Перспективные способы кодирования рельсовых цепей тональной частоты // Автоматика на транспорте. 2015. Том 1. № 2. С. 119–126.
2. Шаманов В.И. Обобщенная математическая модель процесса эксплуатации систем автоматики и телемеханики // Автоматика на транспорте. 2016. Том 2. № 2. С. 163–179.
3. Ubar R., Raik J., Vierhaus H.-T. Design and Test Technology for Dependable Systems-on-Chip (Premier Reference Source) // Information Science Reference. Hershey– New York. IGI Global. 2011. 578 p.
4. Fujiwara E. Code Design for Dependable Systems: Theory and Practical Applications // New Jersey: John Wiley & Sons. 2006. 720 p.
5. Nicolaidis M., ZorianY. On-Line Testing for VLSI – А Compendium of Approaches // Journal of Electronic Testing: Theory and Application. 1998. vol. 12. Issue 1-2. pp. 7–20.
6. Дрозд А.В. и др. Рабочее диагностирование безопасных информационно-управляющих систем / Под ред. А.В. Дрозда и В.С. Харченко // Харьков: Национальный аэрокосмический университет им. Н.Е. Жуковского «ХАИ». 2012. 614 с.
7. Drozd A.et al. Objects and Methods of On-Line Testing: Main Requirements and Perspectives of Development // Proceedings of 14th IEEE East-West Design & Test Symposium (EWDTS`2016). 2016. pp. 72–76.
8. 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.
9. Mitra S., McCluskey E.J. Which Concurrent Error Detection Scheme to Choose? // Proceedings of International Test Conference. USA. 2000. pp. 985–994.
10. Blyudov A.A. On the Synthesis of Test Equipment for Modulo Codes with Summation // Proceedings of Petersburg Transport University. 2013. vol. 1. pp. 53–58.
11. Пархоменко П.П., Согомонян Е.С. Основы технической диагностики (оптимизация алгоритмов диагностирования, аппаратурные средства) // М.: Энергоатомиздат. 1981. 320 с.
12. Matrosova A.Yu., Ostanin S.A., Kirienko I.E. All Stuck-at Fault Test Patterns and Incompletely Specified Boolean Functions // Proceeding of the 11th International Workshop on Boolean Problems. Freiberg. Germany. 2014. pp. 165–170.
13. Черкасова Т.Х. Об обнаружении ошибок в системах автоматики и вычислительной техники с помощью кодов Бергера и его модификаций // Сборник трудов научно-практической конференции Проблемы безопасности и надежности микропроцессорных комплексов. СПб: ПГУПС. 2015. С. 167–172.
14. Berger J.M. А Note on Error Detecting Codes for Asymmetric Channels // Information and Control. 1961. vol. 4. Issue 1. pp. 68–73.
15. Согомонян Е.С., Слабаков Е.В. Самопроверяемые устройства и отказоустойчивые системы // М.: Радио и связь. 1989. 207 с.
16. 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. vol. 5. no. 1. pp. 19–28.
17. 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.
18. Ефанов Д.В., Сапожников В.В., Сапожников Вл.В. О свойствах кода с суммированием в схемах функционального контроля // Автоматика и телемеханика. 2010. № 6. С. 155–162.
19. Bose B., Lin D.J. Systematic Unidirectional Error-Detection Codes // IEEE Transactions on Computers. 1985. vol. C-34. pp. 1026–1032.
20. 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. no. 1-2. pp. 145–155.
21. Sapozhnikov V., Sapozhnikov Vl., Efanov D. Modular Sum Code in Building Testable Discrete Systems // Proceedings of 13th IEEE East-West Design & Test Symposium (EWDTS`2015). 2015. pp. 181–187.
22. Ефанов Д.В., Сапожников В.В., Сапожников Вл.В. Применение модульных кодов с суммированием для построения систем функционального контроля комбинационных логических схем // Автоматика и телемеханика. 2015. № 10. С. 152–169.
23. Черепанова М.Р. Исследование влияния значения модуля кода с суммированием на структурную избыточность систем функционального контроля // Известия Петербургского университета путей сообщения. 2016. № 2. С. 279–288.
24. Piestrak S.J. Design of Self-Testing Checkers for Unidirectional Error Detecting Codes // Wrocław: Oficyna Wydawnicza Politechniki Wrocłavskiej, 1995. 111 p.
25. Das D., Touba N.A. Weight-Based Codes and Their Application to Concurrent Error Detection of Multilevel Circuits // Proceedings of 17th IEEE Test Symposium. 1999. pp. 370–376.
26. Das D., Touba N.A., Seuring M., Gossel M. Low Cost Concurrent Error Detection Based on Modulo Weight-Based Codes // Proceedings of the 6th IEEE International On-Line Testing Workshop (IOLTW). Spain. 2000. pp. 171–176.
27. Sapozhnikov V. et al. Optimum Sum Codes, that Effectively Detect the Errors of Low Multiplicities // Radioelectronics & Informatics. 2015. Issue 1. pp. 17–22.
28. Сапожников В.В., Сапожников Вл.В., Ефанов Д.В., Никитин Д.А. Модульно взвешенный код с суммированием для систем технического диагностирования // Информатика и системы управления. 2015. № 3. С. 53–62.
29. Дмитриев В.В. О двух способах взвешивания и их влиянии на свойства кодов с суммированием взвешенных переходов в системах функционального контроля логических схем // Известия Петербургского университета путей сообщения. 2015. № 3. С. 119–129.
30. Блюдов А.А., Ефанов Д.В., Сапожников В.В., Сапожников Вл.В. Построение модифицированного кода Бергера с минимальным числом необнаруживаемых ошибок информационных разрядов // Электронное моделирование. 2012. Том 34. № 6. С. 17–29.
2. Шаманов В.И. Обобщенная математическая модель процесса эксплуатации систем автоматики и телемеханики // Автоматика на транспорте. 2016. Том 2. № 2. С. 163–179.
3. Ubar R., Raik J., Vierhaus H.-T. Design and Test Technology for Dependable Systems-on-Chip (Premier Reference Source) // Information Science Reference. Hershey– New York. IGI Global. 2011. 578 p.
4. Fujiwara E. Code Design for Dependable Systems: Theory and Practical Applications // New Jersey: John Wiley & Sons. 2006. 720 p.
5. Nicolaidis M., ZorianY. On-Line Testing for VLSI – А Compendium of Approaches // Journal of Electronic Testing: Theory and Application. 1998. vol. 12. Issue 1-2. pp. 7–20.
6. Дрозд А.В. и др. Рабочее диагностирование безопасных информационно-управляющих систем / Под ред. А.В. Дрозда и В.С. Харченко // Харьков: Национальный аэрокосмический университет им. Н.Е. Жуковского «ХАИ». 2012. 614 с.
7. Drozd A.et al. Objects and Methods of On-Line Testing: Main Requirements and Perspectives of Development // Proceedings of 14th IEEE East-West Design & Test Symposium (EWDTS`2016). 2016. pp. 72–76.
8. 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.
9. Mitra S., McCluskey E.J. Which Concurrent Error Detection Scheme to Choose? // Proceedings of International Test Conference. USA. 2000. pp. 985–994.
10. Blyudov A.A. On the Synthesis of Test Equipment for Modulo Codes with Summation // Proceedings of Petersburg Transport University. 2013. vol. 1. pp. 53–58.
11. Пархоменко П.П., Согомонян Е.С. Основы технической диагностики (оптимизация алгоритмов диагностирования, аппаратурные средства) // М.: Энергоатомиздат. 1981. 320 с.
12. Matrosova A.Yu., Ostanin S.A., Kirienko I.E. All Stuck-at Fault Test Patterns and Incompletely Specified Boolean Functions // Proceeding of the 11th International Workshop on Boolean Problems. Freiberg. Germany. 2014. pp. 165–170.
13. Черкасова Т.Х. Об обнаружении ошибок в системах автоматики и вычислительной техники с помощью кодов Бергера и его модификаций // Сборник трудов научно-практической конференции Проблемы безопасности и надежности микропроцессорных комплексов. СПб: ПГУПС. 2015. С. 167–172.
14. Berger J.M. А Note on Error Detecting Codes for Asymmetric Channels // Information and Control. 1961. vol. 4. Issue 1. pp. 68–73.
15. Согомонян Е.С., Слабаков Е.В. Самопроверяемые устройства и отказоустойчивые системы // М.: Радио и связь. 1989. 207 с.
16. 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. vol. 5. no. 1. pp. 19–28.
17. 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.
18. Ефанов Д.В., Сапожников В.В., Сапожников Вл.В. О свойствах кода с суммированием в схемах функционального контроля // Автоматика и телемеханика. 2010. № 6. С. 155–162.
19. Bose B., Lin D.J. Systematic Unidirectional Error-Detection Codes // IEEE Transactions on Computers. 1985. vol. C-34. pp. 1026–1032.
20. 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. no. 1-2. pp. 145–155.
21. Sapozhnikov V., Sapozhnikov Vl., Efanov D. Modular Sum Code in Building Testable Discrete Systems // Proceedings of 13th IEEE East-West Design & Test Symposium (EWDTS`2015). 2015. pp. 181–187.
22. Ефанов Д.В., Сапожников В.В., Сапожников Вл.В. Применение модульных кодов с суммированием для построения систем функционального контроля комбинационных логических схем // Автоматика и телемеханика. 2015. № 10. С. 152–169.
23. Черепанова М.Р. Исследование влияния значения модуля кода с суммированием на структурную избыточность систем функционального контроля // Известия Петербургского университета путей сообщения. 2016. № 2. С. 279–288.
24. Piestrak S.J. Design of Self-Testing Checkers for Unidirectional Error Detecting Codes // Wrocław: Oficyna Wydawnicza Politechniki Wrocłavskiej, 1995. 111 p.
25. Das D., Touba N.A. Weight-Based Codes and Their Application to Concurrent Error Detection of Multilevel Circuits // Proceedings of 17th IEEE Test Symposium. 1999. pp. 370–376.
26. Das D., Touba N.A., Seuring M., Gossel M. Low Cost Concurrent Error Detection Based on Modulo Weight-Based Codes // Proceedings of the 6th IEEE International On-Line Testing Workshop (IOLTW). Spain. 2000. pp. 171–176.
27. Sapozhnikov V. et al. Optimum Sum Codes, that Effectively Detect the Errors of Low Multiplicities // Radioelectronics & Informatics. 2015. Issue 1. pp. 17–22.
28. Сапожников В.В., Сапожников Вл.В., Ефанов Д.В., Никитин Д.А. Модульно взвешенный код с суммированием для систем технического диагностирования // Информатика и системы управления. 2015. № 3. С. 53–62.
29. Дмитриев В.В. О двух способах взвешивания и их влиянии на свойства кодов с суммированием взвешенных переходов в системах функционального контроля логических схем // Известия Петербургского университета путей сообщения. 2015. № 3. С. 119–129.
30. Блюдов А.А., Ефанов Д.В., Сапожников В.В., Сапожников Вл.В. Построение модифицированного кода Бергера с минимальным числом необнаруживаемых ошибок информационных разрядов // Электронное моделирование. 2012. Том 34. № 6. С. 17–29.
Опубликован
2017-02-02
Как цитировать
Сапожников, В. В., Сапожников, В. В., Ефанов, Д. В., & Котенко, А. Г. (2017). Модульные коды с суммированием взвешенных переходов с последовательностью весовых коэффициентов, образующей натуральный ряд чисел. Труды СПИИРАН, 1(50), 137-164. https://doi.org/10.15622/sp.50.6
Раздел
Методы управления и обработки информации
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями:
Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале.
Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале.
Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).
