On the problem of modified codes with summation of weighted data bits with natural numbers sequence of weight indexes generators synthesis | Vestnik Tomskogo gosudarstvennogo universiteta. Upravlenie, vychislitelnaja tehnika i informatika – Tomsk State University Journal of Control and Computer Science. 2016. № 4(37). DOI: 10.17223/19988605/37/2

On the problem of modified codes with summation of weighted data bits with natural numbers sequence of weight indexes generators synthesis

Different codes with summation (most of which are Berger code modifications) are often used in reliable discrete devices design. Modified code with summation of weighted data bits refers to such modifications. It is systematic code (the same as Berger code) and has k = |~log₂ (m +1)| check bits (m - data vector length). This code formation involves attribution of natural numbers weight indexes, calculation of total active bits weight and its least nonnegative residue by modulo M = 2^ (+)^ . This value is placed in low bits of check vector. High bit is calculated as modulo two sum of data bits with even positions (that have even weight indexes). This code has better data bits error detection properties comparing with Berger code. Also it is the code with minimum total number of undetectable data bits errors for given length of data and check vectors. The paper describes the method of modified Berger code generator synthesis. Component base list contains standard circuits of modulo two, half and full adders. They compose functional blocks of M = 2^ (+)^ sum. Generator itself is formed by cascade connection of such blocks. Two structural diagrams of modified Berger code generators are given; also the generator synthesis algorithm is described that optimizes its structure by separation of weight indexes by groups of summed numbers without transfers. These numbers are sent on inputs of counters of M = 2 ^ (+)V sum. High bit of check vector is formed on the output of the block that calculate modulo two sum of data bits with even positions. The algorithm is illustrated on the example synthesis of the generator for modified Berger code with m = 8. -1 functional blocks of sum by M = 2^+' modulo and block of high bit formation that consists of The paper shows that of modified Berger code includes -1 modulo two adders. Dependence between complexity and data vector length is stated. It is shown that number of two-input gates in generator structure is calculated with the following expression: 7[log₂ (m +1)) m -1|-12 m m + 3 2 ) 2 _ 2 _ + 9 . The described way of generator synthesis is universal and could be used for the formation of generators for codes with summation of weighted data bits and for codes with summation of weighted transitions between adjacent bits as well.

Download file

Counter downloads: 196

Keywords

техническая диагностика, система функционального контроля, код Бергера, модифицированный код Бергера, взвешенный код с суммированием, наименьший неотрицательный вычет, модуль, генератор, полусумматор, полный сумматор, technical diagnostics, concurrent error detection system (CED system), Berger code, modified Berger code, weight-based sum code, least nonnegative residue, modulus, generator, half-adder, full-adder

Authors

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

Всего: 1

References

Слабаков Е.В. Построение полностью самопроверяемых комбинационных устройств с использованием остаточных кодов // Автоматика и телемеханика. 1979. № 10. C. 133-141.

Слабаков Е.В., Согомонян Е.С. Самопроверяемые вычислительные устройства и системы (обзор) // Автоматика и телемеха ника. 1981. № 11. С. 147-167.

McCluskey E.J. Logic Design Principles: With Emphasis on Testable Semicustom Circuits. N.J. : Prentice Hall PTR, 1986. 549 p.

Сагалович Ю.Л. Кодовая защита оперативной памяти ЭВМ от ошибок // Автоматика и телемеханика. 1991. № 5. С. 3-45.

Согомонян Е.С., Слабаков Е.В. Самопроверяемые устройства и отказоустойчивые системы. М. : Радио и связь, 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.

Pradhan D.K. Fault-Tolerant Computer System Design. New-York : Prentice Hall, 1996. 560 p.

Das D., Touba N.A. Synthesis of Circuits with Low-Cost Concurrent Error Detection Based on Bose-Lin Codes // Journal of Elec tronic Testing: Theory and Applications. 1999. V. 15, Issue 1-2. P. 145-155.

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. P. 171-176.

Matrosova A.Yu., Levin I., Ostanin S.A. Self-Checking Synchronous FSM Network Design with Low Overhead // VLSI Design. 2000. V. 11, Issue 1. P. 47-58.

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

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. P. 21-26.

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

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

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

Ефанов Д.В., Сапожников В.В., Сапожников Вл.В. Применение модульных кодов с суммированием для построения систем функционального контроля комбинационных логических схем // Автоматика и телемеханика. 2015. № 10. С. 152-169. Nicolaidis M., Zorian Y. On-Line Testing for VLSI - А Compendium of Approaches // Journal of Electronic Testing: Theory and Applications. 1998. Issue 12. P. 7-20

Mitra S., McClaskey E.J. Which Concurrent Error Detection Scheme to ^oose? // Proceedings of International Test Conference, 2000, USA, Atlantic City, NJ, 03-05 October 2000. P. 985-994

Ефанов Д.В., Грошев Г.М., Маликов О.Б. Способы организации систем функционального диагностирования логических схем без памяти // Электротехника. 2016. № 5. С. 53-56

Berger J.M. А Note on Error Detecting Codes for Asymmetric Channels // Information and Control. 1961. V. 4, Issue 1. P. 68-73. Сапожников В.В., Сапожников Вл.В., Ефанов Д.В. Классификация ошибок в информационных векторах систематических кодов // Известия вузов. Приборостроение. 2015. Т. 58, № 5. С. 333-343

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

Сапожников В. В., Сапожников Вл. В., Ефанов Д. В. Предельные свойства кода с суммированием // Известия Петербургского университета путей сообщения. 2010. № 3. С. 290-299

Сапожников В.В., Сапожников Вл.В., Ефанов Д.В., Черепанова М.Р. Модульные коды с суммированием в системах функционального контроля. I. Свойства обнаружения ошибок кодами в информационных векторах // Электронное моделирование. 2016. Т. 38, № 2. С. 27-48

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

Гессель М., Морозов А. А., Сапожников В. В., Сапожников Вл. В. Построение комбинационных самопроверяемых устройств с монотонно независимыми выходами // Автоматика и телемеханика. 1994. № 7. С. 148-160

Гессель М., Морозов А. А., Сапожников В. В., Сапожников Вл. В. Исследование комбинационных самопроверяемых устройств с независимыми и монотонно независимыми выходами // Автоматика и телемеханика. 1997. № 2. С. 180-193. Morosow A., Sapozhnikov V.V., Sapozhnikov Vl.V., Goessel M. Self-Checking Combinational Circuits with Unidirectionally Independent Outputs // VLSI Design. 1998. V. 5, Issue 4. P. 333-345

Saposhnikov V.V., Morosov A., Saposhnikov Vl.V., Goessel M. A New Design Method for Self-Checking Unidirectional Combinational Circuits // Journal of Electronic Testing: Theory and Applications. 1998. V. 12, Issue 1-2. P. 41-53

Matrosova A., Levin I., Ostanin S. Survivable Self-Checking Sequential Circuits // Proceedings of 2001 IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems (DFT 2001). October 24-26, San Francisco, CA, 2001. P. 395-402. Блюдов А.А., Ефанов Д.В., Сапожников В.В., Сапожников Вл.В. Построение модифицированного кода Бергера с минимальным числом необнаруживаемых ошибок информационных разрядов // Электронное моделирование. 2012. Т. 34, № 6. С. 17-29

Efanov D., Sapozhnikov V., Sapozhnikov Vl., Nikitin D. Sum Code Formation with Minimum Total Number of Undetectable Errors in Data Vectors // Proceedings of 13th IEEE East-West Design & Test Symposium (EWDTS'2015), Batumi, Georgia, September 26-29. 2015. P. 141-148

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

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

Сапожников В.В., Сапожников Вл.В., Ефанов Д.В. Взвешенные коды с суммированием для организации контроля логических устройств // Электронное моделирование. 2014. Т. 36, № 1. С. 59-80

Marouf M.A., Friedman A.D. Design of Self-Checking Checkers for Berger Codes // Proceedings of 8th Annual International Conference on Fault-Tolerant Computing, Toulouse, France, 1978. P. 179-183. Lala P.K. Principles of Modern Digital Design. New Jersey : John Wiley & Sons, 2007. 436 p

Blyudov A.A. On the Synthesis of Test Equipment for Modulo Codes with Summation // Proceedings of Petersburg Transport University. 2013. Issue 1. P. 53-58

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

Favalli M., Metra C. Optimization of Error Detecting Codes for the Detection of Crosstalk Originated Errors // Design, Automation and Test in Europe (DATE), March 13-16, 2001. P. 290-296

Ghosh S., Lai K.W., Jone W.B., Chang S.C. Scan Chain Fault Identification Using Weight-Based Codes for SoC Circuits // Proceedings of 13th Asian Test Symposium, 15-17 November. 2004. P. 210-215

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. DOI 10.1109/EWDTS.2014.7027064

Сапожников В.В., Сапожников Вл.В., Ефанов Д.В., Никитин Д.А. Модульно взвешенный код с суммированием для систем технического диагностирования // Информатика и системы управления. 2015. № 3. С. 53-62

Saposhnikov V., Saposhnikov Vl. New Code for Fault Detection in Logic Circuits // Proceedings of 4th International conference on Unconventional Electromechanical and Electrical Systems, St. Petersburg, Russia, June 21-24. 1999. P. 693-696

Сапожников В.В., Сапожников Вл.В., Ефанов Д.В., Дмитриев В.В. Свойства кодов с суммированием взвешенных переходов с прямой последовательностью весовых коэффициентов // Информатика и системы управления. 2014. № 4. С. 77-88

Sapozhnikov V., Sapozhnikov Vl., Efanov D., Dmitriev V., Cherepanova M. Optimum Sum Codes, That Effectively Detect the Errors of Low Multiplicities // RadioElectronics & Informatics. 2015. No. 1. P. 17-22.

Дмитриев В.В. О двух способах взвешивания и их влиянии на свойства кодов с суммированием взвешенных переходов в системах функционального контроля логических схем // Известия Петербургского университета путей сообщения. 2015. № 3. С. 119-129.

Сапожников В.В., Сапожников Вл.В., Ефанов Д.В., Дмитриев В.В., Черепанова М.Р. Способ построения кода с суммированием с улучшенными показателями обнаружения ошибок в информационных векторах // Автоматика на транспорте. 2016. Т. 2, № 1. С. 95-123.