Research of Two-Modulus Weighted Codes with Summation Involving Arbitrary Partitions of Several Data Symbols

Dmitriy Efanov; Maksim Timoshenkov; Leonid Sivachenko; Igor' Leskovets

doi:10.20295/2412-9186-2023-9-04-377-389

UDC 681.518.5 UDC 004.052.32

2 more Collapse

RESEARCH OF TWO-MODULUS WEIGHTED CODES WITH SUMMATION INVOLVING ARBITRARY PARTITIONS OF SEVERAL DATA SYMBOLS Research of Two-Modulus Weighted Codes with Summation Involving Arbitrary Partitions of Several Data Symbols

АА Аа

Published in Transport automation research · Volume 9, Issue 4 · Pages 377–389 · Rubric: TECHNICAL DIAGNOSTICS AND CONTROLLABLE SYSTEMS

DOI: https://doi.org/10.20295/2412-9186-2023-9-04-377-389

Received: 10.12.2023 Accepted: 11.12.2023 Published: 11.12.2023

Authors

Dmitriy Efanov

Maksim Timoshenkov

Leonid Sivachenko

Igor' Leskovets

Dmitriy Efanov

Academic degree: doctor of technical sciences

Science rang: professor

Peter the Great Saint Petersburg Polytechnic University Professor · Higher School of Cyberphysical Systems & Control, Institute of Computer Science and Cybersecurity · Russian Federation

Peter the Great Saint Petersburg Polytechnic University Professor · Higher School of Transport, Mechanical Engineering, Material and Transport Institute · Russian Federation · Saint-Petersburg

Russian University of Transport (MIIT) Professor · Department of Automation, Remote Control and Communication on Railway Transport · Russian Federation · Moscow

Tashkent State Transport University Professor · Department of Automation and Remote Control · Uzbekistan · Tashkent

Institute of Transport Problems named after N. S. Solomenko of the Russian Academy of Sciences Leading Researcher · Laboratory of Problems of Organization of Transport Systems (Laboratory No. 5) · Russian Federation

Maksim Timoshenkov

Peter the Great Saint Petersburg Polytechnic University, Higher School of Transport, Mechanical Engineering, Material and Transport Institute Master’s Degree Student · Russian Federation

Leonid Sivachenko

Belarusian-Russian University Professor, Academician of the Belarusian Engineering Academy · Department of Transport and Technological Machines · Belarus · Mogilev

Igor' Leskovets

Academic degree: candidate of technical sciences

Belarusian-Russian University Associate Professor, Head of the Department · Department of Transport and Technological Machines · Belarus · Mogilev

ABSTRACT

A method has been proposed for constructing two-modulus sum codes that are suitable for solving the synthesis problems of self-checking digital computing devices and systems, as well as the technical means of their diagnostics. In the process of constructing a code, a set of data symbols is divided into two subsets, forming separate vectors for which the total weight is calculated according to a predetermined modulus. Beforehand, in each of the selected vectors, one of the data symbols is weighted with a coefficient from a natural series. Codes obtained with different values of weight coefficients and modulus for determining the total weight form a separate family of uniform binary codes with a fixed number of check symbols. The article provides an example of constructing a sum codes in the ring of residues modulus M = 4. Using this modulus enables the construction of a two-modulus code with k = 4 check symbols for any value of the m number of data symbols. As the value of m increases, the relationship between the number of data symbols and check symbols will change significantly, and the resulting code will have low redundancy. This is important when using the considered class of codes in the construction of digital devices. Previously unknown properties of the discussed class of sum codes have been identified, and taking these into account is beneficial when addressing problems related to the synthesis and technical diagnostics of digital devices.

KEYWORDS

controllable systems, self-checking systems, sum codes, Berger code, weight-based sum codes, errors detection in data vectors, undetectable error, detection of unidirectional errors, code properties

Text

Text (PDF)

Read Download

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

2. Berger J. M. A Note on Error Detection Codes for Asymmetric Channels / J. M. Berger // Information and Control. - 1961. - Vol. 4. - Iss. 1. - Pp. 68-73. - DOI:https://doi.org/10.1016/S0019-9958(61)80037-5.

3. Ryan W. E. Channel Codes: Classical and Modern / W. E. Ryan, S. Lin. - Cambridge University Press, 2009, 708 r.

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

5. Berger J. M. A Note on Burst Detection Sum Codes / J. M. Berger // Information and Control. - 1961. - Vol. 4. - Iss. 2-3. - Pp. 297-299. - DOI:https://doi.org/10.1016/S0019-9958(61)80024-7.

6. Das D. Weight-Based Codes and Their Application to Concurrent Error Detection of Mul-tilevel Circuits / D. Das, N. A. Touba // Proceedings of 17th IEEE Test Symposium, California. - USA, 1999. - Pp. 370-376. - DOI:https://doi.org/10.1109/VTEST.1999.766691.

7. Dmitriev V. V. O dvuh sposobah vzveshivaniya i ih vliyanii na svoystva kodov s summirovaniem vzveshennyh perehodov v sistemah funkcional'nogo kontrolya logicheskih shem / V. V. Dmitriev // Izvestiya Peterburgskogo universiteta putey soobscheniya. - 2015. - № 3. - S. 119-129.

8. Sapozhnikov V. V. Vzveshennye kody s summirovaniem dlya organizacii kontrolya logicheskih ustroystv / V. V. Sapozhnikov, Vl. V. Sapozhnikov, D. V. Efanov // Elektronnoe modelirovanie. - 2014. - T. 36. - № 1. - S. 59-80.

9. Efanov D. V. Using Codes with Summation of Weighted Bits to Organize Checking of Combinational Logical Devices / D. V. Efanov, V. V. Sapozhnikov, Vl. V. Sapozhnikov // Auto-matic Control and Computer Sciences. - 2019. - Vol. 53. - Iss. 1. - Pp. 1-11. - DOI:https://doi.org/10.3103/S0146411619010061.

10. Das D. Low Cost Concurrent Error Detection Based on Modulo Weight-Based Codes / D. Das, N. A. Touba, M. Seuring et al. // Proceedings of the IEEE 6th International On-Line Testing Workshop (IOLTW), Spain, Palma de Mallorca, July 3-5, 2000. - Pp. 171-176. - DOI:https://doi.org/10.1109/OLT.2000.856633.

11. Sapozhnikov V. V. Universal'nye struktury dvoichnyh schetchikov edinic po proizvol'nomu modulyu scheta / V. V. Sapozhnikov, Vl. V. Sapozhnikov, D. I. Urganskov // Elektronnoe modelirovanie. - 2002. - T. 24. - № 4. - S. 65-81.

12. Sapozhnikov V. V. Blochnaya struktura dvoichnogo schetchika edinic po proizvol'-nomu modulyu scheta / V. V. Sapozhnikov, Vl. V. Sapozhnikov, D. I. Urganskov // Elektronnoe modelirovanie. - 2005. - T. 27. - № 4. - S. 65-81.

13. Saposhnikov V. V. Composite Structure of Binary Counter of Ones Arbitrary Modulo / V. V. Saposhnikov, Vl. V. Saposhnikov, D. I. Urganskov // Proceedings of East-West Design & Test Workshop (EWDTWʼ05), 15-19 September 2005, Odessa, Ukraine. - Pp. 102-106.

14. Saposhnikov V. V. Multistage Regular Structure of Binary Counter of Ones Arbitrary Modulo / V. V. Saposhnikov, Vl. V. Saposhnikov, D. I. Urganskov // Proceedings of East-West De-sign & Test Workshop (EWDTWʼ06), 15-19 September 2006, Sochi, Russia. - Pp. 287-290.

15. Lin S.-H. VLSI Design of Diminished-One Modulo 2n + 1 Adder Using Circular Carry Selection / S.-H. Lin, M.-H. Sheu // IEEE Transactions on Circuits and Systems II: Express Briefs. - 2008. - Vol. 55. - Iss. 9. - Pp. 897-901. - DOI:https://doi.org/10.1109/TCSII.2008.923413.

16. Bibilo P. N. Automated Design of Modular Arithmetic Devices: Might CAD Replace an Engineer / P. N. Bibilo, D. A. Gorodetskii // Automatic Control and Computer Sciences. - 2009. - Vol. 43. - Iss. 2. - Pp. 63-73. - DOI:https://doi.org/10.3103/S0146411609020023.

17. Suprun V. P. Single-Level Schematic Realization of Basic Operations of Modular Arith-metic in Unitary Codes / V. P. Suprun // Automatic Control and Computer Sciences. - 2011. - Vol. 45. - Iss. 2. - Pp. 70-79. - DOI:https://doi.org/10.3103/S0146411611020088.

18. Tel'puhov D. V. Osobennosti proektirovaniya modulyarnyh umnozhiteley s pomo-sch'yu sovremennyh SAPR / D. V. Tel'puhov, R. A. Solov'ev, E. S. Balaka i dr. // Problemy razrabotki perspektivnyh mikro- i nanoelektronnyh sistem (MES). - 2016. - № 1. - S. 249-254.

19. Solov'ev R. A. Primenenie metodov modulyarnoy arifmetiki pri razrabotke ap-paratnyh realizaciy neyronnyh setey / R. A. Solov'ev, D. V. Tel'puhov, A. G. Kustov i dr. // Informacionnye tehnologii. - 2019. - T. 25. - № 12. - S. 747-756.

20. Telpukhov D. V. Hardware Implementation of Scaling in Residue Number System in Application to Convolutional Neural Networks / D. V. Telpukhov, R. A. Solovyev, I. A. Mkrtchan // Materials of the International Scientific-Rractical Conference “Infor-mation Innovative Technologies”, Prague, 20-24 April 2020. - Pp. 165-169.

21. Sapozhnikov V. V. Kody s summirovaniem dlya sistem tehnicheskogo diagnosti-rovaniya / V. V. Sapozhnikov, Vl. V. Sapozhnikov, D. V. Efanov. - T. 1: Klassi-cheskie kody Bergera i ih modifikacii. - M.: Nauka, 2020. - 383 s.

22. Sapozhnikov V. V. Kody s summirovaniem dlya sistem tehnicheskogo diagnostiro-vaniya / V. V. Sapozhnikov, Vl. V. Sapozhnikov, D. V. Efanov. - T. 2: Vzveshennye kody s summirovaniem. - M.: Nauka, 2021. - 455 s.

23. Sapozhnikov V. V. Modul'no-vzveshennye kody s summirovaniem s naimen'shim obschim chislom neobnaruzhivaemyh oshibok v informacionnyh vektorah / V. V. Sapozhni-kov, Vl. V. Sapozhnikov, D. V. Efanov // Elektronnoe modelirovanie. - 2017. - T. 39. - № 4. - S. 69-88.

24. Efanov D. V. Teoriya i metody funkcional'nogo diagnostirovaniya logicheskih ustroystv zheleznodorozhnoy avtomatiki i telemehaniki na osnove ispol'zova-niya pomehoustoychivyh kodov s summirovaniem: disc. … d-ra tehn. nauk / D. V. Efanov. - SPb., 2017. - V dvuh tomah: T. 1: Osnovnoe soderzhanie raboty. - 316 s. - T. 2: Prilozheniya. - 112 s.

25. Sogomonyan E. S. Design of Self-Testing and On-Line Fault Detection Combinational Circuits with Weakly Independent Outputs / E. S. Sogomonyan, M. Gössel // Journal of Electronic Testing: Theory and Applications. - 1993. - Vol. 4. - Iss. 4. - Pp. 267-281. - DOI:https://doi.org/10.1007/BF00971975.

26. Busaba F. Y. Self-Checking Combinational Circuit Design for Single and Unidirection-al Multibit Errors / F. Y. Busaba, P. K. Lala // Journal of Electronic Testing: Theory and Applications. - 1994. - Vol. 5. - Iss. 5. - Pp. 19-28. - DOI:https://doi.org/10.1007/BF00971960.

27. Morosow A. Self-Checking Combinational Circuits with Unidirectionally Independent Outputs / A. Morosow, V. V. Saposhnikov, Vl. V. Saposhnikov et al. // VLSI Design. - 1998. - Vol. 5. - Iss. 4. - Pp. 333-345. - DOI:https://doi.org/10.1155/1998/20389.

28. Göessel M. New Methods of Concurrent Checking: Edition 1 / M. Göessel, V. Ocheretny, E. Sogomonyan et al. - Dordrecht: Springer Science + Business Media B. V., 2008. - 184 p.

29. Matrosova A. Yu. Self-Checking Synchronous FSM Network Design with Low Over-head / A. Yu. Matrosova, I. Levin, S. A. Ostanin // VLSI Design. - 2000. - Vol. 11. - Iss. 1. - Pp. 47-58. - DOI:https://doi.org/10.1155/2000/46578.

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

31. Mehov V. B. Kontrol' kombinacionnyh shem na osnove modificirovannyh ko-dov s summirovaniem / V. B. Mehov, V. V. Sapozhnikov, Vl. V. Sapozhnikov // Av-tomatika i telemehanika. - 2008. - № 8. - S. 153-165.

32. Efanov D. Generalized Algorithm of Building Summation Codes for the Tasks of Technical Diagnostics of Discrete Systems / D. Efanov, V. Sapozhnikov, Vl. Sapozhni-kov // Proceedings of 15th IEEE East-West Design & Test Symposium (EWDTS’2017), Novi Sad, Serbia, September 29 - October 2, 2017. - Pp. 365-371. - DOI:https://doi.org/10.1109/EWDTS.2017.8110126.

33. Efanov D. V. Dvuhmodul'nye vzveshennye kody s summirovaniem v kol'ce vy-chetov po modulyu M = 4 / D. V. Efanov, V. V. Sapozhnikov, Vl. V. Sapozhnikov // Trudy SPIIRAN. - 2020. - T. 19. - № 3. - S. 674-713. - DOI:https://doi.org/10.15622/sp.2020.19.3.8.

34. 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. Sapozhni-kov // Automatic Control and Computer Sciences. - 2018. - Vol. 52. - Iss. 1. - Pp. 1-12. - DOI:https://doi.org/10.3103/S0146411618010029.

35. Drozd A. Checkability of the Digital Components in Safety-Critical Systems: Problems and Solutions / A. Drozd, V. Kharchenko, S. Antoshchuk et al. // Proceedings of 9th IEEE East-West Design & Test Symposium (EWDTS’2011), Sevastopol, Ukraine, 2011. - Pp. 411-416. - DOI:https://doi.org/10.1109/EWDTS.2011.6116606.

36. Drozd O. Resilient Development of Models and Methods in Computing Space / O. Drozd, A. Rucinski, K. Zashcholkin et al. // Proceedings of 19th IEEE East-West De-sign & Test Symposium (EWDTS’2021), Batumi, Georgia, September 10-13, 2021. - Pp. 70-75. - DOI:https://doi.org/10.1109/EWDTS52692.2021.9581002.

GOST

Efanov D. V., Timoshenkov M. V., Sivachenko L. A., Leskovets I. V. Research of Two-Modulus Weighted Codes with Summation Involving Arbitrary Partitions of Several Data Symbols // Transport automation research. 2023. no. 4. pp. 377-389. DOI: https://doi.org/10.20295/2412-9186-2023-9-04-377-389. (Date of access 08.10.2026).

MLA

Dmitriy Efanov, Timoshenkov M. V., Sivachenko L. A., Leskovets I. V.. "Research of Two-Modulus Weighted Codes with Summation Involving Arbitrary Partitions of Several Data Symbols." Transport automation research 9.4 (2023): 377-389. DOI: https://doi.org/10.20295/2412-9186-2023-9-04-377-389.

APA

Efanov D. V., Timoshenkov M. V., Sivachenko L. A., Leskovets I. V. (2023). Research of Two-Modulus Weighted Codes with Summation Involving Arbitrary Partitions of Several Data Symbols. Transport automation research, 9(4), 377-389. https://doi.org/10.20295/2412-9186-2023-9-04-377-389

Chicago

Dmitriy Efanov, Timoshenkov M. V., Sivachenko L. A., Leskovets I. V.. "Research of Two-Modulus Weighted Codes with Summation Involving Arbitrary Partitions of Several Data Symbols." Transport automation research 9, no. 4 (2023): 377-389. https://doi.org/10.20295/2412-9186-2023-9-04-377-389.

WIKI

{{cite journal | author = Efanov D. V., Timoshenkov M. V., Sivachenko L. A., Leskovets I. V. | title = Research of Two-Modulus Weighted Codes with Summation Involving Arbitrary Partitions of Several Data Symbols | journal = Transport automation research | year = 2023 | volume = 9 | issue = 4 | pages = 377-389 | doi = 10.20295/2412-9186-2023-9-04-377-389 }}

Copy

Export: BibTeX EndNote RefMan RusMARC

RESEARCH OF TWO-MODULUS WEIGHTED CODES WITH SUMMATION INVOLVING ARBITRARY PARTITIONS OF SEVERAL DATA SYMBOLS Research of Two-Modulus Weighted Codes with Summation Involving Arbitrary Partitions of Several Data Symbols

Confirmation