Analysis of formation methods of sum codes with improved characteristics of detection of symmetrical errors in data vectors | Vestnik Tomskogo gosudarstvennogo universiteta. Upravlenie, vychislitelnaja tehnika i informatika – Tomsk State University Journal of Control and Computer Science. 2015. № 4(33).

Analysis of formation methods of sum codes with improved characteristics of detection of symmetrical errors in data vectors

The principles of noise-resistant coding are widely used for transmitting the information and synthesis of reliable management systems. Quite often, the sum codes are used for the purposes specified. Sum codes are systematic codes that allow to detect some error rate in data vectors. Sum codes have simple rules of formation and relatively low redundancy that determines the priority in its selection, in comparison with error correction codes. Thus, using of the sum codes in systems of technical diagnostics results in a small hardware redundancy for providing the error detection characteristics. Classic sum codes or Berger codes do not detect 100% of multidirectional errors with even multiplicity containing {0 ^ 1, 1 ^ 0} distortion groups (100% of so-called symmetric errors). However, Berger codes detect 100% of monotonous distortions in data vectors that is used to transfer the information and to build the discrete devices with a 100% detection of single faults. Analysis of the characteristics of Berger codes shows, that they often use the check bits inefficiently. For example, all possible check vectors are formed for Berger code only in special cases when data vector length is m = 2 -1 (t e {1,2,...J). In all other cases, a number of check vectors does not used at all. There is a problem of providing the modified Berger code which has all the characteristics of the classic Berger code. The article presents the algorithms for formation of modified Berger codes which detect almost twice as many symmetrical errors in data vectors, as classic Berger codes. The article also covers the conditions under which there is no need to increase the number of check bits in the code. It also highlights the schematics particularities of synthesis of generators (encoders) of new codes. The experiment with making use of a set of test cases LGSynth'89 confirmed theoretical results. Note that the modified Berger code is promising in solving the problems of technical diagnostics.

Download file

Counter downloads: 265

Keywords

техническая диагностика, система функционального контроля, код Бергера, модифицированный код с суммированием, информационный вектор, необнаруживаемая ошибка, симметричная ошибка, свойства обнаружения ошибок, technical diagnostics, concurrent error detection (CED), Berger code, modified sum code, data bits, undetectable error, symmetric error, detection ability properties

Authors

Name	Organization	E-mail
Efanov Dmitry V.	Petersburg State Transport University	TrES-4b@yandex.ru

Всего: 1

References

Сапожников В.В., Сапожников Вл.В., Христов Х.А., Гавзов Д.В. Методы построения безопасных микроэлектронных систем железнодорожной автоматики. М. : Транспорт, 1995. 272 с.

Микропроцессорные системы централизации / Вл.В. Сапожников, В.А. Кононов, С.А. Куренков, А.А. Лыков, О.А. Наседкин, А.Б. Никитин, А.А. Прокофьев, М.С. Трясов ; под ред. Вл.В. Сапожникова. М. : Учебно-методический центр по образованию на железнодорожном транспорте, 2008. 398 с.

Ubar R., Raik J., Vierhaus H.-T. Design and Test Technology for Dependable Systems-on-Chip (Premier Reference Source) // Infor mation Science Reference. Hershey ; New York : IGI Global, 2011. 578 p.

Рабочее диагностирование безопасных информационно-управляющих систем / А.В. Дрозд, В.С. Харченко, С.Г. Антощук, Ю.В. Дрозд, М.А. Дрозд, Ю.Ю. Сулима ; под ред. А.В. Дрозда и В.С. Харченко. Харьков : Национальный аэрокосмический университет им. Н.Е. Жуковского «ХАИ», 2012. 614 с.

Кравцов Ю.А., Архипов Е.В., Бакин М.Е. Перспективные способы кодирования рельсовых цепей тональной частоты // Авто матика на транспорте. 2015. Т. 1, № 2. С. 119-126.

Ходаковский В.А., Ходаковский Т.В. Мера сходства узкополосных сигналов // Автоматика на транспорте. 2015. Т. 1, № 2. С. 180-194.

Шаманов В.И. Управление процессом модернизации комплексов систем железнодорожной автоматики и телемеханики // Автоматика на транспорте. 2015. Т. 1, № 3. С. 237-250.

Согомонян Е.С., Слабаков Е.В. Самопроверяемые устройства и отказоустойчивые системы. М. : Радио и связь, 1989. 208 с.

Сапожников В.В., Сапожников Вл.В. Самопроверяемые дискретные устройства. СПб. : Энергоатомиздат, 1992. 224 с.

Piestrak S.J. Design of Self-Testing Checkers for Unidirectional Error Detecting Codes. Wroclaw : Oficyna Wydawnicza Politechniki Wroclavskiej, 1995. 111 p.

Fujiwara E. Code Design for Dependable Systems: Theory and Practical Applications. John Wiley & Sons, 2006. 720 p.

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.

LalaP.K. Self-Checking and Fault-Tolerant Digital Design. San Francisco : Morgan Kaufmann Publishers, 2001. 216 p.

Matrosova A., Levin I., Ostanin S. Survivable Self-Checking Sequential Circuits // Proc. of 2001 IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems (DFT 2001). Oct. 24-26. San Francisco, CA, 2001. Р. 395-402.

Abdulhadi A.H., Maamar A.H. Self Checking Register File Using Berger Code // 6th WSEAS International Conference on Circuits, systems, control & signal processing. 2007. Cairo, Egypt. December 29-31. P. 62-68.

Cheremisinov D., Cheremisinova L. Low-Power Design of Combinational CMOS Networks // Proceedings of 11th IEEE East-West Design & Test Symposium (EWDTS'2013). Rostov-on-Don, Russia, September 27-30, 2013. Р. 208-211.

Berger J.M. А Note on Error Detecting Codes for Asymmetric Channels // Information and Control. 1961. Vol. 4, Issue 1. P. 68-73.

Das D., Touba N.A. Weight-Based Codes and Their Application to Concurrent Error Detection of Multilevel Circuits // Proc. 17th IEEE Test Symposium. USA, California, 1999. Р. 370-376.

Das D., Touba N.A., Seuring M., Gossel M. Low Cost Concurrent Error Detection Based on Modulo Weight-Based Codes // Proceedings of IEEE 6th International On-Line Testing Workshop (IOLTW), Spain, Palma de Mallorca, July 3-5, 2000. Р. 171-176.

Mehov V., Saposhnikov V., Sapozhnikov Vl., Urganskov D. Concurrent Error Detection Based on New Code with Modulo Weighted Transitions between Information Bits // Proceedings of 7th IEEE East-West Design & Test Workshop (EWDTW'2007). Erevan, Armenia, September 25-30, 2007. Р. 21-26.

Мехов В.Б., Сапожников В.В., Сапожников Вл.В. Контроль комбинационных схем на основе модифицированных кодов с суммированием // Автоматика и телемеханика. 2008. № 8. С. 153-165.

Блюдов А.А., Сапожников В.В., Сапожников Вл.В. Модифицированный код с суммированием для организации контроля комбинационных схем // Автоматика и телемеханика. 2012. № 1. С. 169-77.

Блюдов А.А., Ефанов Д.В., Сапожников В.В., Сапожников Вл.В. Коды с суммированием для организации контроля комбинационных схем // Автоматика и телемеханика. 2013. № 6. С. 153-164.

Блюдов А.А., Ефанов Д.В., Сапожников В.В., Сапожников Вл.В. О кодах с суммированием единичных разрядов в системах функционального контроля // Автоматика и телемеханика. 2014. № 8. С. 131-145.

Сапожников В.В., Сапожников Вл.В., Ефанов Д.В. Классификация ошибок в информационных векторах систематических кодов // Известия вузов. Приборостроение. 2015. Т. 58, № 5. С. 333-343.

Ефанов Д.В., Сапожников В.В., Сапожников Вл.В. О свойствах кода с суммированием в схемах функционального контроля // Автоматика и телемеханика. 2010. № 6. С. 155-162.

Черкасова Т.Х. Обнаружение ошибок в системах автоматики и вычислительной техники с помощью кодов Бергера и его модификаций // Проблемы безопасности и надежности микропроцессорных комплексов : сб. тр. науч.-практ. конф. / под ред. Вал.В. Сапожникова. СПб. : ПГУПС, 2015.

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 5. P. 19-28.

Morosow A., Sapozhnikov V.V., Sapozhnikov Vl.V., Goessel M. Self-Checking Combinational Circuits with Unidirectionally Independent Outputs // VLSI Design. 1998. Vol. 5, Issue 4. P. 333-345.

Блюдов А.А., Ефанов Д.В., Сапожников В.В., Сапожников Вл.В. Построение модифицированного кода Бергера с минимальным числом необнаруживаемых ошибок информационных разрядов // Электронное моделирование. 2012. Т. 34, № 6. С. 17-29.

Сапожников В.В., Сапожников Вл.В., Ефанов Д.В. Об использовании свойств кодов с суммированием по обнаружению монотонных ошибок в системах функционального контроля комбинационных схем // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2014. № 3. С. 76-88.

Сапожников В.В., Сапожников Вл.В., Ефанов Д.В. Применение кодов с суммированием при синтезе систем железнодорожной автоматики и телемеханики на программируемых логических интегральных схемах // Автоматика на транспорте. 2015. Т. 1, № 1. С. 84-107.

Sapozhnikov V., Sapozhnikov Vl., Efanov D., Nikitin D. Combinational Circuits Checking on the Base of Sum Codes with One Weighted Data Bit // Proceedings of 12th IEEE East-West Design & Test Symposium (EWDTS'2014). Kyev, Ukraine, September 26-29, 2014. P. 126-136.

Сапожников В.В., Сапожников Вл.В., Ефанов Д.В. Построение кодов с суммированием с наименьшим количеством необнару-живаемых симметричных ошибок в информационных векторах // Радиоэлектроника и информатика. 2014. № 4. С. 46-55.

Мельников А.Г., Сапожников В.В., Сапожников Вл.В. Синтез самопроверяющихся тестеров для кодов с суммированием // Проблемы передачи информации. 1986. Т. 22, № 2. С. 85-97.

Сапожников В.В., Сапожников Вл.В., Ефанов Д.В., Никитин Д.А. Метод построения кода Бергера с повышенной эффективностью обнаружения ошибок в информационных разрядах // Электронное моделирование. 2013. Т. 35, № 4. С. 21-34.

Сапожников В.В., Сапожников Вл.В., Ефанов Д.В., Никитин Д.А. Исследование свойств кодов с суммированием с одним взвешенным информационным разрядом в системах функционального контроля // Электронное моделирование. 2015. Т. 37, № 1. С. 25-48.

Collection of Digital Design Benchmarks. URL: http://ddd.fit.cvut.cz/prj/Benchmarks

Sentovich E.M., Singh K.J., Lavagno L., Moon C., Murgai R., Saldanha A., Savoj H., Stephan P.R., Brayton R.K., Sangiovanni-Vincentelli A. SIS: A System for Sequential Circuit Synthesis // Electronics Research Laboratory, Department of Electrical Engineering and Computer Science. University of California, Berkeley, 4 May 1992. 45 p.

Сапожников В.В., Сапожников Вл.В., Ефанов Д.В. Обнаружение опасных ошибок на рабочих выходах комбинационных логических схем // Автоматика на транспорте. 2015. Т. 1, № 2. С. 195-211.