informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-803Research ArticleЛОГИЧЕСКОЕ ПРОЕКТИРОВАНИЕLOGICAL DESIGNСпособ построения семейства кодов с суммированием с наименьшим общим количеством необнаруживаемых ошибок в информационных векторахSum code family formation method with undetectable error minimum in data vectorsЕфановД. В.EfanovD. V.

доктор технических наук, доцент, руководитель направления систем мониторинга и диагностики, ООО «ЛокоТехСигнал»; профессор кафедры «Автоматика, телемеханика и связь на железнодорожном транспорте», Российский университет транспорта

SPIN-код: 1663-0900

D. Sci. (Eng.), Associate Professor, Head of the Direction of Monitoring and Diagnostic Systems, "LocoTech-Signal" LLC; Professor of "Automation, Remote Control and Communication on Railway Transport" Department, Russian University of Transport

tres-4b@yandex.ruСапожниковВ. В.SapozhnikovV. V.

доктор технических наук, профессор, профессор кафедры «Автоматика и телемеханика на железных дорогах»

D. Sci. (Eng.), Professor, Professor of "Automation and Remote Control on Railways" Department

port.at.pgups@gmail.comСапожниковВл. В.SapozhnikovVl. V.

доктор технических наук, профессор, профессор кафедры «Автоматика и телемеханика на железных дорогах»

D. Sci. (Eng.), Professor, Professor of "Automation and Remote Control on Railways" Department

at.pgups@gmail.comООО "ЛокоТех-Сигнал"; Российский университет транспорта (МИИТ)"LocoTech-Signal" LLC; Russian University of TransportПетербургский государственный университет путей сообщения Императора Александра IEmperor Alexander I St. Petersburg State Transport University201921062019163101118Copyright © Ефанов Д.В., Сапожников В.В., Сапожников В.В., 20192019Ефанов Д.В., Сапожников В.В., Сапожников В.В.Efanov D.V., Sapozhnikov V.V., Sapozhnikov V.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/803

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

The research results of the methods for formation of separable sum codes with the minimum number of undetectable errors in data vectors are presented. A formula for counting the number of undetectable errors in data vectors and codes family properties are given. A universal method for formation of such codes is shown, which makes it possible for each value of the data vector length to obtain a whole family of codes that also have different distributions of undetectable errors by type and multiplicity. An example of codes formation, methods for analyzing characteristics, code comparison are presented. A method for synthesizing coders of developed sum codes is suggested. 

техническая диагностикаобнаружение неисправностейкод с суммированиемнеобнаруживаемая ошибкаминимальное количество необнаруживаемых ошибокмодифицированный код с суммированиемсемейство кодовtechnical diagnosticsfault detectorsum codeundetectable errorundetectable error minimummodified sum codecodes familyReferencesRahaman, H. Universal test set for detecting stuck-at and bridging faults in double fixed-polarity Reed-Muller programmable logic arrays / H. Rahaman, D. K. Das // Computers and Digital Techniques. – 2006. – Vol. 153, iss. 2. – P. 109–116.Rahaman H., Das D. K. Universal test set for detecting stuck-at and bridging faults in double fixed-polarity Reed-Muller programmable logic arrays. Computers and Digital Techniques, 2006, vol. 153, iss. 2, pp. 109–116. DOI: 10.1049/ip-cdt:20050079Concurrent error detection in Reed – Solomon encoders and decoders / G. C. Cardarilli [et al.] // IEEE Transactions on Very Large Scale Integration (VLSI) Systems. – 2007. – Vol. 15, iss. 7. – P. 842–846.Cardarilli G. C., Pontarelli S., Re M., Salsano A. Concurrent error detection in Reed – Solomon encodersOptimal testing of Reed-Muller codes / A. Bhattacharyya [et al.] // Proc. of IEEE 51st Annual Symp. on Foundations of Computer Science, Las Vegas, USA, 23–26 Oct. 2010. – Las Vegas, 2010. – P. 488–497.and decoders. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2007, vol. 15, iss. 7, pp. 842–846. DOI: 10.1109/TVLSI.2007.899241Experimental study on Hamming and Hsiao codes in the context of embedded applications / G. Tshagharyan [et al.] // Proc. of 15th IEEE East-West Design & Test Symposium (EWDTS’2017), Novi Sad, Serbia, 29 Sept. – 2 Oct. 2017. – Novi Sad, 2017. – P. 25–28.Bhattacharyya A., Kopparty S., Schoenebeck G., Sudan M., Zuckerman D. Optimal testing of Reed-Muller codes. Proceedings of IEEE 51st Annual Symposium on Foundations of Computer Science, Las Vegas, USA, 23–26 October 2010. Las Vegas, 2010, pp. 488–497. DOI: 10.1109/FOCS.2010.54R-code for concurrent error detection and correction in the logic circuits / A. Stempkovskiy [et al.] // IEEE Conf. of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus), 29 Jan. – 1 Febr. 2018, Moscow, Russia. – Moscow, 2018. – P. 1430–1433.Tshagharyan G., Harutyunyan G., Shoukourian S., Zorian Y. Experimental study on Hamming and Hsiao codes in the context of embedded applications. Proceedings of 15th IEEE East-West Design & Test Symposium (EWDTS’2017), Novi Sad, Serbia, 29 September – 2 October 2017. Novi Sad, 2017, pp. 25–28. DOI: 10.1109/EWDTS.2017.8110065Piestrak, S. J. Design of Self-Testing Checkers for Unidirectional Error Detecting Codes / S. J. Piestrak. – Wrocław : Oficyna Wydawnicza Politechniki Wrocłavskiej, 1995. – 111 p.Stempkovskiy A., Telpukhov D., Gurov S., Zhukova T., Demeneva A. R-code for concurrent error detection and correction in the logic circuits. IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus), 29 January – 1 February 2018, Moscow, Russia. Moscow, 2018,Fujiwara, E. Code Design for Dependable Systems: Theory and Practical Applications / E. Fujiwara. – John Wiley & Sons, 2006. – 720 p.pp. 1430–1433. DOI: 10.1109/EIConRus.2018.8317365New Methods of Concurrent Checking : 1st ed. / M. Göessel [et al.]. – Dordrecht : Springer Science + Business Media B.V., 2008. – 184 p.Piestrak S. J. Design of Self-Testing Checkers for Unidirectional Error Detecting Codes. Wrocław, Oficyna Wydawnicza Politechniki Wrocłavskiej, 1995, 111 p.Согомонян, Е. С. Самопроверяемые устройства и отказоустойчивые системы / Е. С. Согомонян, Е. В. Слабаков. – М. : Радио и связь, 1989. – 208 с.Fujiwara E. Code Design for Dependable Systems: Theory and Practical Applications. John Wiley & Sons, 2006, 720 p.Pradhan, D. K. Fault-Tolerant Computer System Design / D. K. Pradhan. – N. Y. : Prentice Hall, 1996. – 560 p.Göessel M., Ocheretny V., Sogomonyan E., Marienfeld D. New Methods of Concurrent Checking. Dordrecht, Springer Science+Business Media B.V., 2008, 184 p.Рабочее диагностирование безопасных информационно-управляющих систем / А. В. Дрозд [и др.] ; под ред. А. В. Дрозда, В. С. Харченко. – Харьков : Национальный аэрокосмический университет им. Н. Е. Жуковского «ХАИ», 2012. – 614 с.Sogomonyan E. S., Slabakov E. V. Samoproveryaemye ustrojstva i otkazoustojchivye sistemy. Self-Checking Devices and Fault-Tolerance Systems. Moscow, Radio i svyaz', 1989, 208 p. (in Russian).Kharchenko, V. Green IT engineering: concepts, models, complex systems architectures / V. Kharchenko, Yu. Kondratenko, J. Kacprzyk // Springer Book Series "Studies in Systems, Decision and Control". – Springer International Publishing Switzerland, 2017. – Vol. 74. – 305 p.Pradhan D. K. Fault-Tolerant Computer System Design. New York, Prentice Hall, 1996, 560 p.Efanov, D. Generalized algorithm of building summation codes for the tasks of technical diagnostics of discrete systems / D. Efanov, V. Sapozhnikov, Vl. Sapozhnikov // Proc. of 15th IEEE East-West Design & Test Symposium (EWDTS’2017), Novi Sad, Serbia, 29 Sept. – 2 Oct. 2017. – Novi Sad, 2017. – P. 365–371.Drozd A. V., Harchenko V. S., Antoshchuk S. G., Drozd Yu. V., Drozd M. A., Sulima Yu., eds. Drozd A. V., Kharchenko V. S. [Rabochee diagnostirovanie bezopasnyh informacionno-upravlyayushchih system. Objects and Methods of On-Line Testing for Safe Instrumentation and Control Systems. Kharkov, Nacional'nyj aehrokosmicheskij universitet im. N. E. Zhukovskogo «HAI», 2012, 614 p. (in Russian).Nicolaidis, M. On-line testing for VLSI – а compendium of approaches / M. Nicolaidis, Y. Zorian // J. of Electronic Testing: Theory and Applications. – 1998. – No. 12. – P. 7–20.Kharchenko V., Kondratenko Yu., Kacprzyk J. Green IT engineering: concepts, models, complex systems architectures. Springer Book Series "Studies in Systems, Decision and Control", Springer International Publishing Switzerland, 2017, vol. 74, 305 p.Das, D. Synthesis of circuits with low-cost concurrent error detection based on Bose-Lin codes / D. Das, N. A. Touba // J. of Electronic Testing: Theory and Applications. – 1999. – Vol. 15, iss. 1–2. – P. 145–155.Efanov D., Sapozhnikov V., Sapozhnikov Vl. Generalized algorithm of building summation codes forMitra, S. Which concurrent error detection scheme to сhoose? / S. Mitra, E. J. McCluskey // Proc. of Intern. Test Conf., Atlantic City, USA, 3–5 Oct. 2000. – Atlantic City, 2000. – P. 985–994.the tasks of technical diagnostics of discrete systems. Proceedings of 15th IEEE East-West Design & Test Symposium (EWDTS’2017), Novi Sad, Serbia, 29 September – 2 October 2017. Novi Sad, 2017, pp. 365–371. DOI: 10.1109/EWDTS.2017.8110126Bose, B. Systematic unidirectional error-detection codes / B. Bose, D. J. Lin // IEEE Transaction on Computers. – 1985. – Vol. C-34. – P. 1026–1032.Nicolaidis M., Zorian Y. On-line testing for VLSI – а compendium of approaches. Journal of Electronic Testing: Theory and Applications, 1998, no. 12, рp. 7–20. DOI: 10.1023/A:1008244815697Jha, N. K. A new class of symmetric error correcting/unidirectional error detecting codes / N. K. Jha // Computers and Mathematic with Application. – 1990. – Vol. 19, no. 5. – P. 95–104.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, iss. 1–2, рp. 145–155. DOI: 10.1023/A:1008344603814Efanov, D. The use of codes with fixed multiplicities of detected unidirectional and asymmetrical errors in the process of organizing combinational circuit testing / D. Efanov, V. Sapozhnikov, Vl. Sapozhnikov // Proc. of 16th IEEE East-West Design & Test Symposium (EWDTS’2018), Kazan, Russia, 14–17 Sept. 2018. – Kazan, 2018. – P. 114–122.Mitra S., McCluskey E. J. Which concurrent error detection scheme to сhoose? Proceedings of International Test Conference, Atlantic City, USA, 3–5 October 2000. Atlantic City, 2000, pp. 985–994. DOI: 10.1109/TEST.2000.894311Построение модифицированного кода Бергера с минимальным числом необнаруживаемых ошибок информационных разрядов / А. А. Блюдов [и др.] // Электронное моделирование. – 2012. – Т. 34, № 6. – С. 17–29.Bose B., Lin D. J. Systematic unidirectional error-detection codes. IEEE Transaction on Computers, 1985, vol. C-34, pp. 1026–1032.Модульные коды с суммированием взвешенных переходов с последовательностью весовых коэффициентов, образующей натуральный ряд чисел / В. В. Сапожников [и др.] // Труды СПИИРАН. – 2017. – № 1. – С. 137–164.Jha N. K. A new class of symmetric error correcting/unidirectional error detecting codes. Computers and Mathematic with Application, 1990, vol. 19, no. 5, pp. 95–104. DOI 10.1016/0898-1221(90)90105-SСапожников, В. В. Модульно-взвешенные коды с суммированием с наименьшим общим числом необнаруживаемых ошибок в информационных векторах / В. В. Сапожников, Вл. В. Сапожников, Д. В. Ефанов // Электронное моделирование. – 2017. – Т. 39, № 4. – С. 69–88.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. Proceedings of 16th IEEE East-West Design & Test Symposium (EWDTS’2018), Kazan, Russia, 14–17 September 2018. Kazan, 2018, pp. 114–122. DOI: 10.1109/EWDTS.2018.8524768Коды с суммированием с эффективным обнаружением двукратных ошибок для организации систем функционального контроля логических устройств / В. В. Дмитриев [и др.] // Автоматика и телемеханика. – 2018. – № 4. – С. 105–122.Blyudov A. A., Efanov D. V., Sapozhnikov V. V., Sapozhnikov Vl. V. Postroenie modificirovannogo koda Bergera s minimal'nym chislom neobnaruzhivaemyh oshibok informacionnyh razryadov [Formation of the Berger modified code with minimum number of undetectable errors of data bits]. Electronnoe modelirovanie [Electronic Modeling], 2012, vol. 34, no. 6, pp. 17–29 (in Russian).Ефанов, Д. В. О свойствах кода с суммированием в схемах функционального контроля / Д. В. Ефанов, В. В. Сапожников, Вл. В. Сапожников // Автоматика и телемеханика. – 2010. – № 6. – С. 155–162.Sapozhnikov V. V., Sapozhnikov Vl. V., Efanov D. V., Kotenko A. G. Modul'nye kody s summirovaniem vzveshennyh perekhodov s posledovatel'nost'yu vesovyh koehfficientov, obrazuyushchej natural'nyj ryad chisel [Modulo codes with summation of weighted transitions with natural number sequence of weights]. Trudy SPIIRAN [SPIIRAS Proceedings], 2017, no. 1, pp. 137–164. DOI: 10.15622/SP.50.6 (in Russian).О кодах с суммированием единичных разрядов в системах функционального контроля / А. А. Блюдов [и др.] // Автоматика и телемеханика. – 2014. – № 8. – С. 131–145.Sapozhnikov V. V., Sapozhnikov Vl. V., Efanov D. V. Modul'no-vzveshennye kody s summirovaniem s naimen'shim obshchim chislom neobnaruzhivaemyh oshibok v informacionnyh vektorah [Modulo weighted codes with summation with minimum number of undetectable errors in data vectors]. Electronnoe modelirovanie [Electronic Modeling], 2017, vol. 39, no. 4, pp. 69–88 (in Russian).Сапожников, В. В. Коды Хэмминга в системах функционального контроля логических устройств / В. В. Сапожников, Вл. В. Сапожников, Д. В. Ефанов. – СПб. : Наука, 2018. – 151 с.Dmitriev V. V., Efanov D. V., Sapozhnikov V. V., Sapozhnikov Vl. V. Kody s summirovaniem s ehffektivnym obnaruzheniem dvukratnyh oshibok dlya organizacii sistem funkcional'nogo kontrolya logicheskihExperimental studies of polynomial codes in concurrent error detection systems of combinational logical circuits / D. Efanov [et al.] // Proc. of 16th IEEE East-West Design & Test Symposium (EWDTS’2018), Kazan, Russia, 14–17 Sept. 2018. – Kazan, 2018. – P. 184–190.ustrojstv [Sum codes with efficient detection of twofold errors for organization of concurrent error detectionМехов, В. Б. Контроль комбинационных схем на основе модифицированных кодов с суммированием / В. Б. Мехов, В. В. Сапожников, Вл. В. Сапожников // Автоматика и телемеханика. – 2008. – № 8. – С. 153–165.systems of logical devices]. Avtomatika i telemekhanika [Automation and Remote Control], 2018, no. 4,Сапожников, В. В. Коды с суммированием с последовательностью весовых коэффициентов, образующей натуральный ряд чисел, в системах функционального контроля / В. В. Сапожников, Вл. В. Сапожников, Д. В. Ефанов // Электронное моделирование. – 2017. – Т. 39, № 5. – С. 37–58.pp. 105–122 (in Russian).Berger, J. M. A note on error detection codes for asymmetric channels / J. M. Berger // Information and Control. – 1961. – Vol. 4, iss. 1. – P. 68–73.Efanov D. V., Sapozhnikov V. V., Sapozhnikov Vl. V. O svojstvah koda s summirovaniem v skhemah funkcional'nogo kontrolya [On summation code properties in functional control circuits]. Avtomatika i telemekhanika [Automation and Remote Control], 2010, no. 6, pp. 155–162 (in Russian).Efanov, D. V. Two-modulus codes with summation of one-data bits for technical diagnostics of discrete systems / D. V. Efanov, V. V. Sapozhnikov, Vl. V. Sapozhnikov // Automatic Control and Computer Sciences. – 2018. – Vol. 52, iss. 1. – P. 1–12.Blyudov A. A., Efanov D. V., Sapozhnikov V. V., Sapozhnikov Vl. V. O kodah s summirovaniemHarris, D. M. Digital Design and Computer Architecture : 2nd ed. / D. M. Harris, S. L. Harris. – Morgan Kaufmann, 2012. – 712 p.edinichnyh razryadov v sistemah funkcional'nogo kontrolya [On codes with summation of unit bits in concurrentСапожников, В. В. Классификация ошибок в информационных векторах систематических кодов / В. В. Сапожников, Вл. В. Сапожников, Д. В. Ефанов // Известия вузов. Приборостроение. – 2015. – Т. 58, № 5. – С. 333–343.error detection systems]. Avtomatika i telemekhanika [Automation and Remote Control], 2014, no. 8, pp. 131–145 (in Russian).Sapozhnikov V. V., Sapozhnikov Vl. V., Efanov D. V. Kody Hehmminga v sistemah funkcional'nogo kontrolya logicheskih ustrojstv. Hamming Сodes in Concurrent Error Detection Systems of Logic Devices. Saint Petersburg, Nauka, 2018, 151 p. (in Russian).Sapozhnikov V. V., Sapozhnikov Vl. V., Efanov D. V. Kody Hehmminga v sistemah funkcional'nogo kontrolya logicheskih ustrojstv. Hamming Сodes in Concurrent Error Detection Systems of Logic Devices. Saint Petersburg, Nauka, 2018, 151 p. (in Russian).Efanov D., Plotnikov D., Sapozhnikov V., Sapozhnikov Vl., Abdullaev R. Experimental studies of polynomial codes in concurrent error detection systems of combinational logical circuits. Proceedings of 16th IEEE East-West Design & Test Symposium (EWDTS’2018), Kazan, Russia, 14–17 September 2018. Kazan, 2018, pp. 184–190. DOI: 10.1109/EWDTS.2018.8524684Efanov D., Plotnikov D., Sapozhnikov V., Sapozhnikov Vl., Abdullaev R. Experimental studies of polynomial codes in concurrent error detection systems of combinational logical circuits. Proceedings of 16th IEEE East-West Design & Test Symposium (EWDTS’2018), Kazan, Russia, 14–17 September 2018. Kazan, 2018, pp. 184–190. DOI: 10.1109/EWDTS.2018.8524684Mekhov V. B., Sapozhnikov V. V., Sapozhnikov Vl. V. Kontrol' kombinacionnyh skhem na osnove modificirovannyh kodov s summirovaniem [Checking of combinational circuits basing on modification sum codes]. Avtomatika i telemekhanika [Automation and Remote Control], 2008, no. 8, pp. 153–165 (in Russian).Mekhov V. B., Sapozhnikov V. V., Sapozhnikov Vl. V. Kontrol' kombinacionnyh skhem na osnove modificirovannyh kodov s summirovaniem [Checking of combinational circuits basing on modification sum codes]. Avtomatika i telemekhanika [Automation and Remote Control], 2008, no. 8, pp. 153–165 (in Russian).Sapozhnikov V. V., Sapozhnikov Vl. V., Efanov D. V. Kody s summirovaniem s posledovatel'nost'yu vesovyh koehfficientov, obrazuyushchej natural'nyj ryad chisel, v sistemah funkcional'nogo kontrolya [Codes with summation with a sequence of weight coefficients, forming a natural series of numbers, in concurrent error detection systems]. Electronnoe modelirovanie [Electronic Modeling], 2017, vol. 39, no. 5, pp. 37–58 (in Russian).Sapozhnikov V. V., Sapozhnikov Vl. V., Efanov D. V. Kody s summirovaniem s posledovatel'nost'yu vesovyh koehfficientov, obrazuyushchej natural'nyj ryad chisel, v sistemah funkcional'nogo kontrolya [Codes with summation with a sequence of weight coefficients, forming a natural series of numbers, in concurrent error detection systems]. Electronnoe modelirovanie [Electronic Modeling], 2017, vol. 39, no. 5, pp. 37–58 (in Russian).Berger J. M. A note on error detection codes for asymmetric channels. Information and Control, 1961, vol. 4, iss. 1, рp. 68–73. DOI: 10.1016/S0019-9958(61)80037-5Berger J. M. A note on error detection codes for asymmetric channels. Information and Control, 1961, vol. 4, iss. 1, рp. 68–73. DOI: 10.1016/S0019-9958(61)80037-5Efanov D. V., Sapozhnikov V. V., Sapozhnikov Vl. V. Two-modulus codes with summation of one-data bits for technical diagnostics of discrete systems. Automatic Control and Computer Sciences, 2018, vol. 52, iss. 1, pp. 1–12. DOI: 10.3103/S0146411618010029Efanov D. V., Sapozhnikov V. V., Sapozhnikov Vl. V. Two-modulus codes with summation of one-data bits for technical diagnostics of discrete systems. Automatic Control and Computer Sciences, 2018, vol. 52, iss. 1, pp. 1–12. DOI: 10.3103/S0146411618010029Harris D. M., Harris S. L. Digital Design and Computer Architecture. Morgan Kaufmann, 2012, 712 p.Harris D. M., Harris S. L. Digital Design and Computer Architecture. Morgan Kaufmann, 2012, 712 p.Sapozhnikov V. V., Sapozhnikov Vl. V., Efanov D. V. Klassifikaciya oshibok v informacionnyh vektorah sistematicheskih kodov [Errors classification in information vectors of systematic codes]. Izvestiya vuzov. Priborostroenie [Journal of Instrument Engineering], 2015, vol. 58, no. 5, pp. 333–343. DOI: 10.17586/0021-3454-2015-58-5-333-343 (in Russian).Sapozhnikov V. V., Sapozhnikov Vl. V., Efanov D. V. Klassifikaciya oshibok v informacionnyh vektorah sistematicheskih kodov [Errors classification in information vectors of systematic codes]. Izvestiya vuzov. Priborostroenie [Journal of Instrument Engineering], 2015, vol. 58, no. 5, pp. 333–343. DOI: 10.17586/0021-3454-2015-58-5-333-343 (in Russian).

The authors declare that there are no conflicts of interest present.