Codes With Summation of Weight Coefficients of Data Vector Bits in the Ring of Residues Modulo an Arbitrary for Digital Computing Devices

Dmitriy Efanov; Artem Pashukov

doi:10.20295/2412-9186-2022-8-2-198-217

UDC

004.052.42 681.518.5

CODES WITH SUMMATION OF WEIGHT COEFFICIENTS OF DATA VECTOR BITS IN THE RING OF RESIDUES MODULO AN ARBITRARY FOR DIGITAL COMPUTING DEVICES Codes With Summation of Weight Coefficients of Data Vector Bits in the Ring of Residues Modulo an Arbitrary for Digital Computing Devices

АА Аа

Published in Transport automation research · Pages 198–217 · Rubric: TECHNICAL DIAGNOSTICS AND CONTROLLABLE SYSTEMS

DOI: https://doi.org/10.20295/2412-9186-2022-8-2-198-217

Received: 14.06.2022 Accepted: 14.06.2022 Published: 14.06.2022

Authors

Dmitriy Efanov

Artem Pashukov

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

Artem Pashukov

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

ABSTRACT

We consider the specificities of codes with the summation of weight coefficients of data vector bits in the ring of residues modulo an arbitrary. There’re established the characteristics of error detection by the given code class and some legitimacies related to the use of modules of particular values and of weight coefficients. It’s shown that the number of various weight-based sum codes is limited, nevertheless, large number of various ways of their formation exists for each value of bit number in data vectors. There’re given the algorithm to obtain bits of check vectors of being considered codes and the examples of their upbuilding; the way to calculate the number of not being revealed errors in data vectors is described. There’re defined the properties of weight-based sum codes of data vectors in the ring of residues modulo an arbitrary accounting for which may be useful while the settlement of technical diagnostics task, the synthesis of being selfchecking and fault-tolerant digital devices and devices with testability structures. The approach to the synthesis of coders of any weight-based sum codes on the base of binary number summators according to established module is described. There’re given some results of experiments on the analysis of revealing capacities of being considered codes in the circuits of inbuilt control of combinational benchmarks. Obtained in the work results are of universal character and not oriented to application just with one element base of being realized devices that make them useful not just at the moment but in the future.

KEYWORDS

fault-tolerant digital systems, testability devices, self-checking circuits of in-built control, sum code, weight-based sum codes, summation in the ring of residues with arbitrary modulo, error detection in data bits, properties of weightbades sum codes

1. Sapozhnikov V.V., Sapozhnikov Vl.V., Hristov H.A., Gavzov D.V. Metody postroeniya bezopasnyh mikroelektronnyh sistem zheleznodorozhnoy avtomatiki. - Pod red. Vl.V. Sapozhnikova. - M.: Transport, 1995, 272 s.

2. Ubar R., Raik J., Vierhaus H.-T. Design and Test Technology for Dependable Systems-on-Chip (Premier Reference Source). - Information Science Reference, Hershey - New York, IGI Global, 2011, 578 p.

3. Drozd O., Sachenko A., Hiromoto R., Zashcholkin K., Drozd M. Particularities of Sync Monitoring in FPGA Components of Safety-Related Systems // Proceedings of 11th IEEE Interna-tional Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (IDAACS’2021), Vol. 2, Cracow, Poland, September 22-25, 2021, pp. 979-983, doi: ???.

4. Hahanov V., Chumachenko S., Litviniva E., Khakhanova H. Vector Simulation of Logic Faults Based on XOR-Relations // Proceedings of 11th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applica-tions (IDAACS’2021), Vol. 2, Cracow, Poland, September 22-25, 2021, pp. 1041-1044, doi: ???.

5. Sapozhnikov Vl.V. Sintez sistem upravleniya dvizheniem poezdov na zheleznodorozhnyh stanciyah s isklyucheniem opasnyh otkazov. - M.: Nauka, 2021, 229 s.

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

7. Abramovici M., Breuer M.A., Friedman A.D. Digital System Testing and Testable Design. - Computer Science Press, 1998, 652 p.

8. Lala P.K. Self-Checking and Fault-Tolerant Digital Design. - San Francisco: Morgan Kaufmann Publishers, 2001, 216 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 Concur-rent Checking: Edition 1. - Dordrecht: Springer Science+Business Media B.V., 2008, 184 p.

11. Sapozhnikov V.V., Sapozhnikov Vl.V., Efanov D.V. Kody s summirovaniem dlya sistem tehnicheskogo diagnostirovaniya. Tom 1: Klassicheskie kody Bergera i ih modifikacii. - M.: Nauka, 2020, 383 s.

12. Sapozhnikov V.V., Sapozhnikov Vl.V., Efanov D.V. Kody s summirovaniem dlya sistem tehnicheskogo diagnostirovaniya. Tom 2: Vzveshennye kody s summirovaniem. - M.: Nauka, 2021, 455 s.

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

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

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

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

17. Sogomonyan E.S., Slabakov E.V. Samoproveryaemye ustroystva i otkazoustoychivye sistemy. - M.: Radio i svyaz', 1989, 208 s.

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

19. 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. - Vol. 5. - Issue 5. - Pp. 19-28. - DOI:https://doi.org/10.1007/BF00971960.

20. Morosow A, Saposhnikov V.V., Saposhnikov Vl.V., Goessel M. Self-Checking Com-binational Circuits with Unidirectionally Independent Outputs // VLSI Design. - 1998. - Vol. 5. - Issue 4. - Pp. 333-345. - DOI:https://doi.org/10.1155/1998/20389.

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

22. Efanov D.V., Sapozhnikov V.V., Sapozhnikov Vl.V. Organization of a Fully Self-Checking Structure of a Combinational Device Based on Searching for Groups of Symmetrically Independent Outputs // Automatic Control and Computer Sciences. - 2020. - Vol. 54. - Issue 4. - Pp. 279-290. - DOI:https://doi.org/10.3103/S0146411620040045.

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

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

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

26. Mehov V., Saposhnikov V., Sapozhnikov Vl., Urganskov D. Concurrent Error Detec-tion Based on New Code with Modulo Weighted Transitions between Information Bits // Proceed-ings of 7th IEEE East-West Design & Test Workshop (EWDTWʼ2007), Erevan, Armenia, Sep-tember 25-30, 2007, pp. 21-26.

27. Mehov V.B., Sapozhnikov V.V., Sapozhnikov Vl.V. Kontrol' kombinacionnyh shem na osnove modificirovannyh kodov s summirovaniem // Avtomatika i telemehanika. - 2008. - №8. - S. 153-165.

28. Efanov D., Sapozhnikov V., Sapozhnikov Vl. On One Method of Formation of Opti-mum Sum Code for Technical Diagnostics Systems // Proceedings of 14th IEEE East-West Design & Test Symposium (EWDTS’2016), Yerevan, Armenia, October 14-17, 2016, pp. 158-163, doi:https://doi.org/10.1109/EWDTS.2016.7807633.

29. Efanov D.V., Sapozhnikov V.V., Sapozhnikov Vl.V. Kody s summirovaniem s fiksirovannymi znacheniyami kratnostey, obnaruzhivaemyh monotonnyh i asimmetrichnyh oshibok dlya sistem tehnicheskogo diagnostirovaniya // Avtomatika i telemehanika. - 2019. - №6. - S. 121-141.

30. Efanov D.V., Pashukov A.V. The Weight-Based Sum Codes in the Residue Ring by Arbitrary Modulus for Synthesis of Self-Checking Digital Computing Systems // Proceedings of 19th IEEE East-West Design & Test Symposium (EWDTS’2021), Batumi, Georgia, September 10-13, 2021, pp. 170-179, doi:https://doi.org/10.1109/EWDTS52692.2021.9581032.

31. Zakrevskiy A.D. Pottosin Yu.V., Cheremisinova L.D. Logicheskie osnovy proektirovaniya diskretnyh ustroystv. - M.: Fizmatlit, 2007, 592 s.

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

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

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

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

36. Suprun V.P., Dorozhinskiy A.L. Summator po modulyu pyat'. - Avtorskoe svidetel'stvo SSSR № 1388850, SU 1803911 A1, 1986, 3 s.

37. Avgul' L.B. Summator po modulyu sem'. - Avtorskoe svidetel'stvo RF RU 2028660 C1, opublikovano 09.02.1995, podano 21.05.1992, 7 s.

38. Suprun V.P., Gorodecky D.A. Realization of Addition and Multiplication Operations in Unitary Codes // Automatic Control and Computer Sciences. - 2010. - Vol. 44. - Issue 5. - Pp. 292-301. - DOI:https://doi.org/10.3103/S014641161005007X.

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

40. Drozd A.V., Harchenko V.S., Antoschuk S.G., Drozd Yu.V., Drozd M.A., Sulima Yu.Yu. Rabochee diagnostirovanie bezopasnyh informacionno-upravlyayuschih sistem / Pod red. A.V. Drozda i V.S. Harchenko. - Har'kov: Nacional'nyy aerokosmicheskiy universitet im. N. E. Zhukovskogo «HAI», 2012, 614 s.

41. Balaka E.S., Gorodeckiy D.A., Ruhlov V.S., Schelokov A.N. Razrabotka vysokoskorostnyh summatorov po modulyu na baze kombinacionnyh summatorov s parallel'nym perenosom // Izvestiya YuFU. Tehnicheskie nauki. - 2016. - №6. - S. 158-169.

42. Intel® Quartus® Prime Download - Intel® Quartus® Prime Software. - Elektronnyy resurs. [Rezhim dostupa: https://www.intel.ru/content/www/ru/ru/software/programmable/quartus-prime/download. html, data obrascheniya: 08.11.2021].

43. Hahanov V.I., Litvinova E.I., Guz' O.A. Proektirovanie i testirovanie cifrovyh sistem na kristallah. - Har'kov: HNURE, 2009, 484 s.

44. Navabi Z. Digital System Test and Testable Design: Using HDL Models and Archi-tectures. - Springer Science+Business Media, LLC 2011, 435 p.

45. MAX II Device Handbook, Volume 1. - Altera Corporation, 2007, 107 p.

46. PLIS semeyctva MAX II. - Elektronnyy resurs. [Rezhim dostupa: http://altera.ru/plis-max-II.html, data obrascheniya: 08.11.2021].

47. Collection of Digital Design Benchmarks [http:// ddd.fit.cvut.cz/www/prj/Benchmarks/].

48. SIS: A System for Sequential Circuit Synthesis / E.M. Sentovich, K.J. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanha, H. Savoj, P.R. Stephan, R.K. Brayton, A. Sangiovanni-Vincentelli // Electronics Research Laboratory, Department of Electrical Engineer-ing and Computer Science, University of California, Berkeley, 4 May 1992, 45 p.

49. Drozd A., Kharchenko V., Antoshchuk S., Sulima J., Drozd M. Checkability of the Digital Components in Safety-Critical Systems: Problems and Solutions // 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.

50. Drozd O., Rucinski A., Zashcholkin K., Martynyuk O., Drozd J. Resilient Develop-ment of Models and Methods in Computing Space // Proceedings of 19th IEEE East-West Design & 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., Pashukov A. V. Codes With Summation of Weight Coefficients of Data Vector Bits in the Ring of Residues Modulo an Arbitrary for Digital Computing Devices // . 2022. pp. 198-217. DOI: https://doi.org/10.20295/2412-9186-2022-8-2-198-217. (Date of access 19.08.2026).

MLA

Dmitriy Efanov, Pashukov A. V.. "Codes With Summation of Weight Coefficients of Data Vector Bits in the Ring of Residues Modulo an Arbitrary for Digital Computing Devices." (2022): 198-217. DOI: https://doi.org/10.20295/2412-9186-2022-8-2-198-217.

APA

Efanov D. V., Pashukov A. V. (2022). Codes With Summation of Weight Coefficients of Data Vector Bits in the Ring of Residues Modulo an Arbitrary for Digital Computing Devices. , 198-217. https://doi.org/10.20295/2412-9186-2022-8-2-198-217

Chicago

Dmitriy Efanov, Pashukov A. V.. "Codes With Summation of Weight Coefficients of Data Vector Bits in the Ring of Residues Modulo an Arbitrary for Digital Computing Devices." , no. (2022): 198-217. https://doi.org/10.20295/2412-9186-2022-8-2-198-217.

WIKI

{{cite journal | author = Efanov D. V., Pashukov A. V. | title = Codes With Summation of Weight Coefficients of Data Vector Bits in the Ring of Residues Modulo an Arbitrary for Digital Computing Devices | journal = | year = 2022 | pages = 198-217 | doi = 10.20295/2412-9186-2022-8-2-198-217 }}

Copy

Export: BibTeX EndNote RefMan RusMARC

CODES WITH SUMMATION OF WEIGHT COEFFICIENTS OF DATA VECTOR BITS IN THE RING OF RESIDUES MODULO AN ARBITRARY FOR DIGITAL COMPUTING DEVICES Codes With Summation of Weight Coefficients of Data Vector Bits in the Ring of Residues Modulo an Arbitrary for Digital Computing Devices

Confirmation