UNIT BITS AND ONE WEIGHTED BIT SUM CODES WITH ARBITRARY COUNTING MODULES

D.V. Efanov, V.V. Sapozhnikov, V.V. Sapozhnikov

Èlektron. model. 2019, 41(4):48-72

ABSTRACT

A new codes class focused on the error detection in information vectors is presented. The newA new codes class focused on the error detection in information vectors is presented. The newcodes building principles are based on weighing all bits in the data vectors, except for one, withunit weights and one bit—non-unit weights with further calculation of the smallest non-negativededuction of the total on-bits weight in a predetermined module. The description of this codesclass and the classification of code families depending on the check vectors lengths are given.The power of modular codes set is determined with the unit bits and one weighted bit sum foreach value of the length of the data vector. Some error detection features in data vectors by codesfrom the considered class are considered, which is important when solving the detecting faultsproblem in hardware implementations of automatic control systems logic devices.

KEYWORDS

redundant code; error detection codes; sum codes; controllable automation devices;redundant code; error detection codes; sum codes; controllable automation devices;check vector; technical diagnostic; fault-tolerance.

REFERENCES

1. Sogomonyan, E.S., and Slabakov, E.V. (1989), Samoproverjaemyje ustrojstva i otkazoustojchivyje sistemy [Self-checking devices and failover systems], Radio & Svjaz, Moscow, USSR.
2. Sapozhnikov V.V., Sapozhnikov Vl.V., Hristov H.A., and Gavzov D.V. (1995), Metody postroeniya bezopasnyh mikroehlektronnyh sistem zheleznodorozhnoj avtomatiki [Methods for constructing safety microelectronic systems for railway automation], Transport, Moscow, Russia.
3. Ubar R., Raik J., Vierhaus H.-T. (2011), Design and Test Technology for Dependable Systems-on-Chip, IGI Global, New York, USA.
https://doi.org/10.4018/978-1-60960-212-3
4. Drozd, A.V., Kharchenko, V.S. and Antoshchuk, S.G. (2012), Rabochee diagnostirovanie bezopasnykh informatsionno-upravljayustchikh sistem [Objects and Methods of On-Line Testing for Safe Instrumentation and Control Systems], Natsional'nyy aerokosmicheskiy universitet im. N.Ye. Zhukovskogo «KHAI», Kharkov, Ukraine.
5. Kharchenko, V., Kondratenko, Yu., J. and Kacprzyk, J. (2017), “Green IT Engineering: Concepts, Models, Complex Systems Architectures”, Springer Book series “Studies in Systems, Decision and Control”, Vol. 74, DOI 10.1007/978-3-319-44162-7 (accessed July 17, 2019).
https://doi.org/10.1007/978-3-319-44162-7
6. Fujiwara, E. (2006), Code Design for Dependable Systems: Theory and Practical Applications, John Wiley & Sons, New Jersey, USA.
https://doi.org/10.1002/0471792748
7. Ryan, W.E. and Lin, S. (2009), Channel Codes: Classical and Modern, Cambridge University Press, UK.
https://doi.org/10.1017/CBO9780511803253
8. Sapozhnikov, V.V. and Sapozhnikov, Vl.V. (1992) “Self-Checking Constant-Weight Codes Checkers”, Avtomatika i telemekhanika, no. 3, pp. 3-35.
9. Piestrak, S.J. (1995), Design of Self-Testing Checkers for Unidirectional Error Detecting Codes, Oficyna Wydawnicza Politechniki Wroclavskiej, Wroclaw, Poland.
10. Nicolaidis, M. and Zorian, Y. (1998) “On-Line Testing for VLSI – A Compendium of Approaches”, Journal of Electronic Testing: Theory and Applications, no. 12, pp. 7-20, DOI: 10.1023/A:1008244815697 (accessed July 17, 2019).
https://doi.org/10.1007/978-1-4757-6069-9_1
11. Das, D. and Touba, N.A. “Synthesis of Circuits with Low-Cost Concurrent Error Detection Based on Bose-Lin Codes”, Journal of Electronic Testing: Theory and Applications, Vol. 15, Iss. 1-2, pp. 145-155, DOI: 10.1023/A:1008344603814 (accessed July 17, 2019).
https://doi.org/10.1023/A:1008344603814
12. Matrosova, A.Yu., Levin, I. and Ostanin, S.A. (2000), “Self-Checking Synchronous FSM Network Design with Low Overhead”, VLSI Design, Vol. 11, Iss. 1, pp. 47-58, DOI: 10.1155/2000/46578 (accessed July 17, 2019).
https://doi.org/10.1155/2000/46578
13. Kubalik, P., Kubatova, H. (2005), “Parity Codes Used for On-Line Testing in FPGA”, Acta Polytechnika, Vol. 45, no. 6, pp. 53-59.
14. Ghosh, S., Basu, S. and Touba, N.A. (2005), “Synthesis of Low Power CED Circuits Based on Parity Codes”, The Proceeding of 23rd IEEE VLSI Test Symposium (VTS'05), 2005, pp. 315-320.
15. Shah, T., Singh, V. and Matrosova, A. (2017), “Test Pattern Generation to Detect Multiple Faults in ROBDD Based Combinational Circuits”, The Proceeding of 23rd IEEE On-Line Testing and Robust System Design (IOLTS`2017), Thessaloniki, Greece, 3-5 July 2017, pp. 211-212, DOI: 10.1109/IOLTS.2017.8046223 (accessed July 17, 2019).
https://doi.org/10.1109/IOLTS.2017.8046223
16. Matrosova, A., Ostanin, S., Tretyakov, D. and Butorina, N. (2017) “Logic Circuit Design with Gates, LUTs and MUXs Oriented to Mask Faults”, The Proceeding of 15th IEEE East-West Design &Test Symposium (EWDTS`2017), Novi Sad, Serbia, September 29 - October 2, 2017, pp. 95-98, DOI: 10.1109/EWDTS.2017.8110096 (accessed July 17, 2019).
https://doi.org/10.1109/EWDTS.2017.8110096
17. Sapozhnikov, V.V., Sapozhnikov, Vl.V. and Efanov, D.V. (2018), Kody Hemminga v sistemah funkcional'nogo kontrolya logicheskih ustrojstv [Hamming codes in concurrent error detection systems of logic devices], Nauka, St. Petersburg, Russia.
18. Efanov, D.V. (2016), Funkcional'nyj kontrol' i monitoring ustrojstv zheleznodorozhnoj avtomatiki i telemekhaniki [Concurrent checking and monitoring of railway automation and remote control devices], FGBOU VO PGUPS, St. Petersburg, Russia.
19. Gavzov, D.V., Drejman, O.K., Kononov, V.A. and Nikitin, A.B. (2002), Sistemy dispetcherskoj centralizacii [Dispatch centralization systems], Marshrut, Moscow, Russia.
20. Sapozhnikov, V.V., Sapozhnikov, Vl.V. and Efanov D.V. (2019), Osnovy teorii nadezhnosti i tekhnicheskoj diagnostiki [Fundamentals of the theory of reliability and technical diagnostics], Lan', St. Petersburg, Moscow.
21. Efanov, D.V. and Blyudov, A.A. (2014), “Increasing the reliability of position sensors of railway points”, Izv. Peterburgskogo un-ta putey soobscheniya, no. 3, pp. 69-77.
22. Ostanin, S. (2017), “Self-Checking Synchronous FSM Network Design for Path Delay Faults”, The Proceeding of 15th IEEE East-West Design&Test Symposium (EWDTS`2017), Novi Sad, Serbia, 2017, September 29 - October 2, pp. 696-699, DOI: 10.1109/EWDTS. 2017.8110129 (accessed July 17, 2019).
23. Berger, J.M. (1961), “A Note on Error Detection Codes for Asymmetric Channels”, Information and Control, Vol. 4, Iss. 1, pp. 68-73, DOI: 10.1016/S0019-9958(61)80037-5 (accessed July 17, 2019).
https://doi.org/10.1016/S0019-9958(61)80037-5
24. Freiman, C.V. (1962), “Optimal Error Detection Codes for Completely Asymmetric Binary Channels”, Ibid, Vol. 5, Iss. 1, pp. 64-71, DOI: 10.1016/S0019-9958(62)90223-1 (accessed July 17, 2019).
https://doi.org/10.1016/S0019-9958(62)90223-1
25. Das, D. and Touba, N.A. (1999), “Weight-Based Codes and Their Application to Concurrent Error Detection of Multilevel Circuits”, The Proceeding of the 17th IEEE VLSI Test Symposium, USA, CA, Dana Point, April 25-29, 1999, p. 370-376.
26. Das, D., Touba, N.A., Seuring, M. and Gossel, M. (2000), “Low Cost Concurrent Error Detection Based on Modulo Weight-Based Codes”, The Proceeding of IEEE 6th International On-Line Testing Workshop (IOLTW), Spain, Palma de Mallorca, July 3-5, 2000, pp. 171-176, DOI: 10.1109/OLT.2000.856633 (accessed July 17, 2019).
https://doi.org/10.1109/OLT.2000.856633
27. Mekhov, V.B., Sapozhnikov, V.V. and Sapozhnikov, Vl.V. (2008), “Checking of Combinational Circuits Basing on Modification Sum Codes”, Avtomatika i telemekhanika, no. 8, pp. 153-165.
https://doi.org/10.1134/S0005117908080134
28. Sapozhnikov, V.V., Sapozhnikov, Vl.V., and Efanov, D.V. (2014), “Weight-based sum codes for organizing the logic devices checking”, ElektronnojeModelirovanije, Vol. 36, no. 1, pp. 59-80.
29. Blyudov, A.A., Efanov, D.V., Sapozhnikov, V.V. and Sapozhnikov Vl.V. (2014), “On Codes with Summation of Data Bits in Concurrent Error Detection Systems”, Avtomatika i telemekhanika, no. 8, pp. 131-145.
https://doi.org/10.1134/S0005117914080098
30. Efanov, D.V. Sapozhnikov, V.V. and Sapozhnikov, Vl.V. (2015), “Applications of Modular Summation Codes to Concurrent Error Detection Systems for Combinational Boolean Circuits”, Avtomatika i telemekhanika, no. 10, pp. 152-169.
https://doi.org/10.1134/S0005117915100112
31. Efanov, D.V., Sapozhnikov, V.V. and Sapozhnikov, Vl.V. (2018), “Two-Modulus Codes with Summation of One-Data Bits for Technical Diagnostics of Discrete Systems”, Automatic Control and Computer Sciences, Vol. 52, Iss. 1, pp. 1-12, DOI: 10.3103/S0146411618010029 (accessed July 17, 2019).
https://doi.org/10.3103/S0146411618010029
32. Efanov, D., Sapozhnikov, V. and Sapozhnikov, Vl. (2017), “Generalized Algorithm of Building Summation Codes for the Tasks of Technical Diagnostics of Discrete Systems”, The Proceeding of 15th IEEE East-West Design & Test Symposium (EWDTS`2017), Novi Sad, Serbia, September 29-October 2, 2017, pp. 365-371, DOI: 10.1109/EWDTS.2017. 8110126 (accessed July 17, 2019).
https://doi.org/10.1109/EWDTS.2017.8110126
33. Sapozhnikov, V.V., Sapozhnikov, Vl.V. and Efanov, D.V. (2014), “Formation of Codes with Summation with the Smallest Number of Undetectable Errors of Data Bits”, Radioelectronica i Informatika, no. 4, pp. 46-55.
34. Sapozhnikov, V.V., Sapozhnikov, Vl.V. and Efanov, D.V. (2016), “Checking of Combinational Circuits, Based on Sum Codes with One Weighted Data Bit”, Avtomatika na Transporte, Vol. 2, no. 4, pp. 564-597.
35. Efanov, D., Sapozhnikov, V. and Sapozhnikov, Vl. (2016), “On Variety of Sum Codes with On-Data Bits and One Weighted Data Bit in Concurrent Error Detection Systems”, The Proceeding of 2nd International Conference on Industrial Engineering, Applications and Manufacturing (ICIEAM), Chelyabinsk, Russia, 20 May, 2016, DOI: 10.1109/ICIEAM.2016. 7911684.
https://doi.org/10.1109/ICIEAM.2016.7911684
36. Efanov, D., Sapozhnikov, V. and Sapozhnikov, Vl. (2018), “The Use of Codes with Fixed Multiplicities of Detected Unidirectional and Asymmetrical Errors in the Process of Organizing Combinational Circuit Testing”, The Proceeding of 16th IEEE East-West Design & Test Symposium (EWDTS`2018), Kazan, Russia, September 14-17, 2018, pp. 114-122, DOI: 10.1109/EWDTS.2018.8524768.
https://doi.org/10.1109/EWDTS.2018.8524768
37. Sapozhnikov, V.V., Sapozhnikov, Vl.V. and Urganskov, D.I. (2000), “Method for constructing code vector checkers”, Elektronnoje Modelirovanije, Vol. 22, no. 6, pp. 66-76.
38. Sapozhnikov, V.V., Sapozhnikov, Vl.V., and Urganskov, D.I. (2002), “Universal structures of binary unit counters for an arbitrary invoice module”, Ibid, Vol. 24, no. 4, pp. 65-81.
39. Sapozhnikov, V.V., Sapozhnikov, Vl.V. and Urganskov, D.I. (2005), “Block structure of a binary unit counter for an arbitrary invoice module”, Ibid, 2005, Vol. 27, no. 4, pp. 65-81.
40. Saposhnikov, V.V., Saposhnikov, Vl.V. and Urganskov, D.I. (2005), “Composite Structure of Binary Counter of Ones Arbitrary Modulo”, The Proceeding of East-West Design & Test Workshop (EWDTW`05), 15-19 September 2005, Odessa, Ukraine, pp. 102-106.
41. Saposhnikov, V.V., Saposhnikov, Vl.V. and Urganskov, D.I. (2006), “Multistage Regular Structure of Binary Counter of Ones Arbitrary Modulo”, The Proceeding of East-West Design & Test Workshop (EWDTW`06), 15-19 September 2006. Sochi, Russia, pp. 287-290.
42. Bibilo, P.N. and Gorodetskii, D.A. (2009), “Automated Design of Modular Arithmetic Devices: Might CAD Replace an Engineer”, Automatic Control and Computer Sciences, Vol. 43, Iss. 2, pp. 63-73, DOI: 10.3103/S0146411609020023 (accessed July 17, 2019).
https://doi.org/10.3103/S0146411609020023

Full text: PDF