Sum code family formation method with undetectable error minimum in data vectors
Abstract
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.
About the Authors
D. V. Efanov
"LocoTech-Signal" LLC;
Russian University of Transport
Russian Federation
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
Russian Federation
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
V. V. Sapozhnikov
Emperor Alexander I St. Petersburg State Transport University
Russian Federation
D. Sci. (Eng.), Professor, Professor of "Automation and Remote Control on Railways" Department
Russian Federation
D. Sci. (Eng.), Professor, Professor of "Automation and Remote Control on Railways" Department
Vl. V. Sapozhnikov
Emperor Alexander I St. Petersburg State Transport University
Russian Federation
D. Sci. (Eng.), Professor, Professor of "Automation and Remote Control on Railways" Department
Russian Federation
D. Sci. (Eng.), Professor, Professor of "Automation and Remote Control on Railways" Department
References
1. 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:20050079
2. Cardarilli G. C., Pontarelli S., Re M., Salsano A. Concurrent error detection in Reed – Solomon encoders
3. and decoders. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2007, vol. 15, iss. 7, pp. 842–846. DOI: 10.1109/TVLSI.2007.899241
4. 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.54
5. 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.8110065
6. 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,
7. pp. 1430–1433. DOI: 10.1109/EIConRus.2018.8317365
8. Piestrak S. J. Design of Self-Testing Checkers for Unidirectional Error Detecting Codes. Wrocław, Oficyna Wydawnicza Politechniki Wrocłavskiej, 1995, 111 p.
9. Fujiwara E. Code Design for Dependable Systems: Theory and Practical Applications. John Wiley & Sons, 2006, 720 p.
10. Göessel M., Ocheretny V., Sogomonyan E., Marienfeld D. New Methods of Concurrent Checking. Dordrecht, Springer Science+Business Media B.V., 2008, 184 p.
11. 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).
12. Pradhan D. K. Fault-Tolerant Computer System Design. New York, Prentice Hall, 1996, 560 p.
13. 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).
14. 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.
15. Efanov D., Sapozhnikov V., Sapozhnikov Vl. Generalized algorithm of building summation codes for
16. 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.8110126
17. 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:1008244815697
18. 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:1008344603814
19. 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
20. Bose B., Lin D. J. Systematic unidirectional error-detection codes. IEEE Transaction on Computers, 1985, vol. C-34, pp. 1026–1032.
21. 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
22. 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
23. 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).
24. 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).
25. 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).
26. 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 logicheskih
27. ustrojstv [Sum codes with efficient detection of twofold errors for organization of concurrent error detection
28. systems of logical devices]. Avtomatika i telemekhanika [Automation and Remote Control], 2018, no. 4,
29. pp. 105–122 (in Russian).
30. 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).
31. Blyudov A. A., Efanov D. V., Sapozhnikov V. V., Sapozhnikov Vl. V. O kodah s summirovaniem
32. edinichnyh razryadov v sistemah funkcional'nogo kontrolya [On codes with summation of unit bits in concurrent
33. error detection systems]. Avtomatika i telemekhanika [Automation and Remote Control], 2014, no. 8, pp. 131–145 (in Russian).
34. 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).
35. 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.8524684
36. 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).
37. 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).
38. 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-5
39. Efanov 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/S0146411618010029
40. Harris D. M., Harris S. L. Digital Design and Computer Architecture. Morgan Kaufmann, 2012, 712 p.
41. 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).
Review
For citations:
Efanov D.V., Sapozhnikov V.V., Sapozhnikov V.V. Sum code family formation method with undetectable error minimum in data vectors. Informatics. 2019;16(3):101-118. (In Russ.)
Views: 1070
Email this article 