main| new issue| archive| editorial board| for the authors| publishing house|
Πσρρκθι
Main page
New issue
Archive of articles
Editorial board
For the authors
Publishing house

 

 


ABSTRACTS OF ARTICLES OF THE JOURNAL "INFORMATION TECHNOLOGIES".
No. 1. Vol. 29. 2023

DOI: 10.17587/it.29.12-22

D. V. Efanov, Dr. Sc., Professor,
Peter the Great St. Petersburg Polytechnic University, St. Petersburg, 195251, Russian Federation,
Russian University of Transport, Moscow, 127994, Russian Federation,
LLC Research and Design Institute for Transport and Construction Safety, St. Petersburg, 192102, Russian Federation,
M. V. Zueva, Programmer-Analyst, LLC IBS, St. Petersburg, 190000, Russian Federation

Modified Hamming Codes in Computing Devices Technical Diagnostic Systems

Previously unknown error detection characteristics by types and multiplicities in modified Hamming codes code words are established. The rules for constructing this modification of Hamming codes are described. Detailed characteristic tables of codes with data vectors lengths m = 4...16 are given. The considered code's error detection properties brief analysis is given. The results obtained in the study can be effectively used in the digital computing devices with controllable structures synthesis, as well as in the self-checking concurrent error-detection (CED) circuit synthesis using the Boolean complement method. The modified Hamming codes key property is the impossibility of 100 % double error detection in all code word bits when any single and double errors that occur only in data bits are detected. That is why it is recommended, when synthesizing a CED circuit using the Boolean complement method, to convert only those functions that describe the operating functions of the diagnostic object that will form the modified Hamming code control bits, and to separate the converted and non-convertible outputs into two groups of independent outputs. The experiment results with test combinational circuits presented in the article confirm the effectiveness of their use in the CED circuit synthesis by the Boolean complement method.
Keywords: self-checking concurrent error-detection circuit, modified Hamming code, weight-based sum code, Boolean
complement method for the built-in control circuits synthesis, error detection characteristics in code words

Acknowledgements: The presented article was written based on the results of research supported by grant No. MD-2533.2021.4 of the President of the Russian Federation.

P. 12–22

References

  1. Sagalovich Yu. L. Code Protection of Computer RAM from Errors, Automation and Remote Control, 1991, no. 5, pp. 3—45 (in Russian).
  2. Fujiwara E. Code Design for Dependable Systems: Theory and Practical Applications, USA, New Jersey, John Wiley & Sons, 2006, 720 p.
  3. Drozd A. V., Kharchenko V. S., Antoshchuk S. G., Drozd Yu. V., Drozd M. A., Sulima Yu. Yu. On-line testing of the safe instrumentation and control systems. Eds. A. V. Drozd and V. S. Kharchenko, Kharkov, National Aerospace University. NOT. Zhukovsky "KhAI", 2012, 614 p. (in Russian).
  4. Lala P. K. Self-Checking and Fault-Tolerant Digital Design, San Francisco, Morgan Kaufmann Publishers, 2001, 216 p.
  5. Stempkovsky A. L., Gavrilov S. V., Gurov S. I., Ryzhova D. I. Methods of Designing of Fault Tolerance CMOS Combinational Circuits which Provides Automatic Correction of Errors, Informazionnye Tekhnologii, 2017, vol. 23, no. 10, pp. 728—735 (in Russian).
  6. Bestemyanov P. F. Methods for ensuring the safety of hardware for microprocessor-based train traffic control systems, Elektrotekhnika, 2020, no. 9, pp. 2—8 (in Russian).
  7. Sapozhnikov Vl. V. Synthesis of Train Traffic Control Systems at Railway Stations with the Exception of Dangerous Failures, Moscow, Publishing house "Nauka", 2021, 229 p. (in Russian).
  8. Zhukova G. N., Ulyanov M. V. Reconstruction of a Symbolic Periodic Sequence from a Sequence with Noise, Informazionnye Tekhnologii, 2021, vol. 27, no.10, pp. 531—541, doi: 10.17587/ it.27.531-541 (in Russian).
  9. Sogomonyan E. S., Slabakov E. V. Self-checking devices and fail-safe systems, Moscow, Radio and communication, 1989, 208 p. (in Russian).
  10. Goessel M., Ocheretny V., Sogomonyan E., Marienfeld D. New Methods of Concurrent Checking: Edition 1, Dordrecht: Springer Science + Business Media B. V., 2008, 184 p.
  11. Das D. K., Roy S. S., Dmitriev A., Morozov A., Gossel M. Constraint Don't Cares for Optimizing Designs for Concurrent Checking by 1-out-of-3 Codes, Proceedings of the 10th International Workshops on Boolean Problems, Freiberg, Germany, September, 2012, pp. 33—40.
  12. Efanov D., Sapozhnikov V., Sapozhnikov Vl. Generalized Algorithm of Building Summation Codes for the Tasks of Technical Diagnostics of Discrete Systems, Proceedings 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.
  13. Stempkovsky A. L., Zhukova T. D., Telpukhov D. V., Gurov S. I. CICADA: A New Tool to Design Circuits with Correction and Detection Abilities, International Siberian Conference on Control and Communications (SIBCON), 13-15 May 2021, Kazan, Russia, pp. 1—5, doi: 10.1109/SIBCON50419.2021.9438900.
  14. Telpuhov D. V., Zhukova T. D., Kretinina P. D. Analytical Method for Choosing the Most Efficient Algorithm for Fault-Tolerant Combinational Circuits Synthesis, Problems of Advanced Micro- and Nanoelectronic Systems Development (MES), 2021, no. 3, pp. 159—165, doi: 10.31114/2078-7707-2021-3-159-165 (in Russian).
  15. Sapozhnikov V. V., Sapozhnikov Vl. V., Efanov D. V. Hamming codes in functional control systems of logical devices, St. Petersburg, Nauka, 2018, 151 p. (in Russian).
  16. Sapozhnikov V. V., Sapozhnikov Vl. V., Efanov D. V. Sum codes for technical diagnostics systems. Volume 1: Classical Berger codes and their modifications, Moscow, Nauka, 2020, 383 p. (in Russian).
  17. Sapozhnikov V. V., Sapozhnikov Vl. V., Efanov D. V. Sum codes for technical diagnostic systems. Volume 2: Weighted codes with summation, Moscow, Nauka, 2021, 455 p. (in Russian).
  18. Aksenova G. P. A Method for Development of In-Built Monitoring Circuits for Automata with Memory, Automation and Remote Control, 1973, no. 2, pp. 109—116 (in Russian).
  19. Saposhnikov V. V., Morosov A., Saposhnikov Vl. V., Gossel M. A New Design Method for Self-Checking Unidirectional Combinational Circuits, Journal of Electronic Testing: Theory and Applications, 1998, vol. 12, iss. 1—2, pp. 41—53, doi: 10.1023/A:1008257118423.
  20. Efanov D. V. Uniform Redundant Codes Formation Principles for the Self-Checking Combinational Devices Synthesis Based on Structures Data, Informazionnye Tekhnologii, 2022, vol. 28, no. 9, pp. 489—496, doi: 10.17587/it.28.489-496 (in Russian).
  21. Efanov D. V., Zueva M. V. Boolean Complement to Modular Sum Codes for the Concurrent Error-Detection Systems Synthesis for Combinational Devices of Automation and Computer Technology, Problems of Advanced Micro- and Nanoelectronic Systems Development (MES), 2021, no. 1, pp. 52—60, doi: 10.31114/2078-7707-2021-1-52-60 (in Russian).
  22. Efanov D. V., Osadchy G. V., Zueva M. V. Berger Codes in Concurrent Error-Detection Systems, Implemented on the Basis of Boolean Complement Method, Information Science and Control Systems, 2021, no. 1, pp. 75—89, doi: 10.22250/isu.2021.67.75-89 (in Russian).
  23. Efanov D., Osadchy G., Zueva M. Specifics of Error Detection with Modular Sum Codes in Concurrent Error-Detection Circuits Based on Boolean Complement Method, Proceedings of 19th IEEE East-West Design & Test Symposium (EWDTS'2021), Batumi, Georgia, September 10—13, 2021, pp. 59—69, doi: 10.1109/EWDTS52692.2021.9581036.
  24. Efanov D., Osadchy G., Zueva M. Special Aspects of Errors Definition via Sum Codes within Embedded Control Schemas Being Realized by Means of Boolean Complement Method, Proceedings of 11th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (IDAACS'2021), vol. 1, Cracow, Poland, September 22-25, 2021, pp. 424—431, doi: 10.1109/IDAACS53288.2021.9660837.
  25. Berger J. M. ΐ Note on Error Detecting Codes for Asymmetric Channels, Information and Control, 1961, vol. 4, iss. 1, pp. 68—73, doi: 10.1016/S0019-9958(61)80037-5.
  26. Hamming R. W. Error Detecting and Correcting Codes, Bell System Technical Journal, 1950, vol. 29, no. 2, pp. 147—160.
  27. Sapozhnikov V., Sapozhnikov Vl., Efanov D., Dmitriev V. Weighted Sum Code Without Carries is an Optimum Code with Detection of Any Double Errors in Data Vectors, Proceedings of 14th IEEE East-West Design & Test Symposium (EWDTS'2016), Yerevan, Armenia, October 14—17, 2016, pp. 134—141, doi: 10.1109/EWDTS.2016.7807686.
  28. Sapozhnikov V. V., Sapozhnikov Vl. V., Efanov D. V. Weighted Code with Summation Without Carries for Solving the Problems of Technical Diagnostics of Discrete Systems, Journal of Instrument Engineering, 2018, vol. 61, no. 4, pp. 323—335, doi: 10.17586/0021-3454-2018-61-4-323-335 (in Russian).
  29. Efanov D. V., Sapozhnikov V. V., Sapozhnikov Vl. V. Synthesis of Self-Checking Combination Devices Based on Allocating Special Groups of Outputs, Automation and Remote Control, 2018, no. 9, pp. 79—94 (in Russian).
  30. Bliudov A., Nazarov I., Dmitriev V., Kovalyov K. Use of Systematic Code Based on Data Bits Weighing for Concurrent Error Detection Considering Error Structure Analysis, Proceedings of 16th IEEE East-West Design & Test Symposium (EWDTS'2018), Kazan, Russia, September 14—17, 2018, pp. 443—449, doi: 10.1109/EWDTS.2018.8524722.
  31. 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, iss. 1, pp. 19—28, doi: 10.1007/BF00971960.
  32. Matrosova A. Yu., Ostanin S. A. Self-Checking Synchronous Sequential Circuit Design for Unidirectional Error, Proceedings of the IEEE European Test Wokshop (ETW'98), 27—29 May 1998, Sitges, Barcelona, Spain.
  33. Efanov D. V., Sapozhnikov V. V., Sapozhnikov Vl. V. Conditions for Detecting a Logical Element Fault in a Combination Device under Concurrent Checking Based on Berger's Code, Automation and Remote Control, 2017, no. 5, pp. 152—165 (in Russian).
  34. Efanov D. V., Sapozhnikov V. V., Sapozhnikov Vl. V. Or­ganization 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, iss. 4, pp. 279—290, doi: 10.3103/S0146411620040045.
  35. Collection of Digital Design Benchmarks, available at: http:// ddd.fit.cvut.cz/www/prj/Benchmarks/.
  36. Sentovich E. M., Singh K. J., Moon C., Savoj H., Bray-ton R. K., Sangiovanni-Vincentelli A. Sequential Circuit Design Using Synthesis and Optimization, Proceedings IEEE International Conference on Computer Design: VLSI in Computers & Processors, 11—14 October 1992, Cambridge, MA, USA, pp. 328—333, doi: 10.1109/ICCD.1992.276282.
  37. Baghdadi A. A. A., Hahanov V. I., Litvinova E. I. Methods for analyzing and diagnosing digital devices (analytical review), Automated control systems and automation devices, 2014, no. 166, pp. 59—74 (in Russian).
  38. Dmitriev V. V., Efanov D. V., Sapozhnikov V. V., Sapozhnikov Vl. V. Sum Codes with Efficient Detection of Twofold Errors for Organization of Concurrent Error Detection Systems of Logical Devices, Automation and Remote Control, 2018, no. 4, pp. 105—122 (in Russian).

To the contents