Модульные коды с суммированием взвешенных переходов с последовательностью весовых коэффициентов, образующей натуральный ряд чисел
Ключевые слова:
техническая диагностика, функциональный контроль, разделимый код, код Бергера, модульный код с суммированием, код с суммированием взвешенных переходов, необнаруживаемая ошибка, характеристики кодаАннотация
При построении надежных дискретных систем используются разделимые коды с простыми правилами построения и небольшой избыточностью. Часто применяются коды с суммированием с постоянным значением количества контрольных разрядов вне зависимости от длины информационного вектора. В статье показано, что характеристики обнаружения ошибок данными кодами могут быть улучшены за счет модификации правил вычисления значений разрядов контрольных векторов. Предложен алгоритм построения кода с суммированием, основанный на взвешивании переходов между разрядами, занимающими соседние позиции в информационных векторах, и подсчете суммарного веса информационного вектора по модулю, равному степени числа 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.
Modulo Codes with Summation of Weighted Transitions with Natural Number Sequence of Weights
Abstract
Systematic codes with simple formation rules and low redundancy are used in the reliable digital systems design. Codes with summation with a constant number of check bits, which does not depend on data vector length, are often applied. The paper shows that error detection properties of these codes could be improved by a modification of check bits calculation rules. The authors offer the algorithm of the formation of a code with summation based on weighing the transitions between bits on neighboring positions of data vectors and calculation of the total weight of the data vector by the modulo, which is degree of two. The paper contains a detailed analysis of properties of new codes compared with known ones. The authors state the conditions of the formation of error-tolerant modulo weight-based codes with summation with the maximum number of detected errors in data vectors. Improving of error detection characteristics in new codes, compared with classic ones, is achieved by the uniform distribution of data vectors among check vectors. This, in its turn, brings some part of monotonous and asymmetric errors to the class of undetectable in addition to symmetric ones. Modulo weight-based codes detect more symmetric errors than modulo codes with summation of ones, but asymmetric errors are the dominant sort of them for almost any length of data vector. Modulo codes with summation of weighted transitions are the perspective class of systematic codes to solve the tasks of digital systems technical diagnostics.
Опубликован
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).
