ISSN 0021-3454 (print version)
ISSN 2500-0381 (online version)
Menu

2
Issue
vol 67 / February, 2024
Article

DOI 10.17586/0021-3454-2023-66-2-85-99

UDC 004.052.32+681.518.5

SPECIAL PROPERTIES OF HAMMING CODES THAT APPEAR WHEN SYNTHESIZING SELF-CHECKING DIGITAL DEVICES

D. V. Ephanov
PSTU; Department of Automation and Telemechanics on the Railways


Read the full article 

Abstract. Several properties of classical Hamming codes associated with the features of detecting errors that occur simultaneously in both information and control bits of code words are revealed, which is relevant in many applications, for example, in the synthesis of self-checking and fault-tolerant digital computing devices and systems. It is shown that when the number of cases of information bits m tends to infinity, the number of undetectable errors that arrose simultaneously in the information and control bits of Hamming codes increases by 2k–1 times with k being the number of control bits, as compared to the number of undetectable errors that occur only in the information bits of their code words. It is also proved that for m→∞, the ratio of the number of undetectable errors that occur simultaneously in information and control bits to the number of undetectable errors appearing only in information bits for a Hamming code with k + q control bits increases by 2q times with respect to the ratio for the Hamming code with k control bits (here q is an arbitrary natural number). The established characteristics of Hamming codes should be taken into account when synthesizing self-checking digital devices. Examples are given of the synthesis of built-in control circuits using the Boolean complement method with consideration of the revealed properties of Hamming codes.
Keywords: Hamming code, controllable digital device, self-checking digital device, concurrent error-detection circuit, Boolean complement, undetectable error

References:
  1. Hamming R.W. Bell System Technical Journal, 1950, no. 2(29), pp. 147–160.
  2. Peterson W.W. Error-Correcting Codes, NY, Massachusetts Institute of Technology and John Wiley & Sons, 1961, 285 p.
  3. MacWilliams F.J., Sloane N.J.A. The Theory of Error-Correcting Codes, Amsterdam, North-Holland, 1977, 785 p.
  4. Hamming R.W. Coding and Information Theory, NY, Prentice-Hall, 1986, 272 p.
  5. Sapozhnikov V.V., Sapozhnikov Vl.V., Efanov D.V. Kody Khemminga v sistemakh funktsional'nogo kontrolya logicheskikh ustroystv (Hamming Codes in Logic Devices Functional Control Systems), St. Petersburg, 2018, 151 р. (in Russ.)
  6. Lisenkov V.M., Bestem'yanov P.F., Leushin V.B., Lisenkov A.V., Van'shin A.E. Sistemy upravleniya dvizheniem poezdov na peregonakh (Control Systems of Train Service on Stages), Moscow, 2009, 324 р. (in Russ.)
  7. Nikitin D., Manakov A., Nikitin A., Popov P., Kotenko A. Proceedings of 15th IEEE East-West Design & Test Symposium (EWDTS’2017), Novi Sad, Serbia, September 29–October 2, 2017, pp. 332–336, DOI: 10.1109/EWDTS.2017.8110099.
  8. Tshagharyan G., Harutyunyan G., Shoukourian S., Zorian Y. Proceedings of 15th IEEE East-West Design & Test Symposium (EWDTS’2017), Novi Sad, Serbia, September 29–October 2, 2017, pp. 25–28, DOI: 10.1109/EWDTS.2017.8110065.
  9. Ojiganov A.A. Measurement Techniques, 2015, no. 5(58), pp. 512–519, DOI: 10.1007/s11018-015-0746-7.
  10. Sogomonyan E.S., Slabakov E.V. Samoproveryaemye ustroystva i otkazoustoychivye sistemy (The Self-Checked Devices and Failure-Safe Systems), Moscow, 1989, 208 р. (in Russ.)
  11. Telpukhov D.V., Zhukova T.D. Proceedings of 19th IEEE East-West Design & Test Symposium (EWDTS’2021), Batumi, Georgia, September 10–13, 2021, pp. 355–360, DOI: 10.1109/EWDTS52692.2021.9581027.
  12. Gavrilov S.V., Gurov S.I., Telpukhov D.V., Zhukova T.D. Taurida Journal of Computer Science Theory and Mathematics, 2018, no. 2(39), pp. 29–44. (in Russ.)
  13. Telpukhov D.V., Demeneva A.I., Zhukova T.D., Khrushchev N.S. Electronic Engineering. Series 3: Microelectronics, 2018, no. 1(169), pp. 15–22. (in Russ.)
  14. Sapozhnikov V.V., Sapozhnikov Vl.V., Gessel M. Samodvoystvennyye diskretnyye ustroystva (Self-Dual Discrete Devices), St. Petersburg, 2001, 331 р. (in Russ.)
  15. Efanov D.V. Information Science and Control Systems, 2011, no. 3, pp. 70–79. (in Russ.)
  16. Sapozhnikov V., Sapozhnikov Vl., Efanov D., Blyudov A. Proceedings of 11th IEEE East-West Design & Test Symposium (EWDTS’2013), Rostov-on-Don, Russia, September 27–30, 2013, pp. 200–207, DOI: 10.1109/EWDTS.2013.6673097.
  17. Sapozhnikov V.V., Sapozhnikov Vl.V., Efanov D.V. Journal of Instrument Engineering, 2018, no. 1(61), pp. 47–59, DOI: 10.17586/0021-3454-2018-61-1-47-59. (in Russ.)
  18. Gessel M., Morozov A.V., Sapozhnikov V.V., Sapozhnikov Vl.V. Automation and Remote Control, 2003, no. 1(64), pp. 153–161, DOI: https://doi.org/10.1023/A:1021884727370.
  19. Göessel M., Ocheretny V., Sogomonyan E., Marienfeld D. New Methods of Concurrent Checking, Dordrecht: Springer Science+Business Media B.V., 2008, 184 p.
  20. Efanov D., Osadchy G., Zueva M. 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.
  21. Efanov D., Osadchy G., Zueva M. 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.
  22. Sapozhnikov V.V., Sapozhnikov Vl.V., Efanov D.V. Kody s summirovaniyem dlya sistem tekhnicheskogo diagnostirovaniya. T. 1. Klassicheskiye kody Bergera i ikh modifikatsii (Summed Codes for Technical Diagnostic Systems. Vol. 1. Classical Berger Codes and Their Modifications), Moscow, 2020, 383 р. (in Russ.)
  23. Sapozhnikov V.V., Sapozhnikov Vl.V., Efanov D.V. Kody s summirovaniyem dlya sistem tekhnicheskogo diagnostirovaniya. T. 2. Vzveshennyye kody s summirovaniyem (Summed Codes for Technical Diagnostic Systems. Vol. 2. Weighted Codes with Summation), Moscow, 2021, 455 р. (in Russ.)
  24. Sapozhnikov V., Sapozhnikov Vl., Efanov D., Dmitriev V. 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.
  25. Morozov M., Saposhnikov V.V., Saposhnikov Vl.V., Goessel M. Proceedings of 6th IEEE International On-Line Testing Workshop, Palma de Mallorca, Spain, July 3–5, 2000, pp. 171–176.
  26. Efanov D.V., Sapozhnikov V.V., Sapozhnikov Vl.V. Electronic Modeling, 2021, no. 1(43), pp. 28–45, DOI: 10.15407/emodel.43.01.028.
  27. Nikolos D. Journal of Electronic Testing: Theory and Applications, 1998, no. 1–2(12), pp. 69–79, DOI: 10.1023/A:1008281822966.
  28. Lala P.K. Self-Checking and Fault-Tolerant Digital Design, San Francisco, Morgan Kaufmann Publishers, 2001, 216 p.
  29. Huches J.L.A., McCluskey E.J., Lu D.J. IEEE Transactions on Computers, 1984, no. 6(C-33), pp. 546–550.
  30. Drozd O., Sachenko A., Hiromoto R., Zashcholkin K., Drozd M. Proceedings of 11th IEEE International 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: 10.1109/IDAACS53288.2021.9660928.