ISSN 0021-3454 (печатная версия)
ISSN 2500-0381 (онлайн версия)
Меню

3
Содержание
том 67 / Март, 2024
СТАТЬЯ

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

УДК 004.052.32+681.518.5

ОСОБЫЕ СВОЙСТВА КОДОВ ХЭММИНГА, ПРОЯВЛЯЮЩИЕСЯ ПРИ СИНТЕЗЕ САМОПРОВЕРЯЕМЫХ ЦИФРОВЫХ УСТРОЙСТВ

Ефанов Д. В.
ПГУПС; кафедра автоматики и телемеханики на железных дорогах


Читать статью полностью 

Аннотация. Выявлены свойства классических кодов Хэмминга, связанные с особенностями обнаружения ошибок, возникающих одновременно как в информационных, так и контрольных разрядах кодовых слов, что актуально во многих приложениях, например, при синтезе самопроверяемых и отказоустойчивых цифровых вычислительных устройств и систем. Доказано, что при устремлении числа информационных разрядов m к бесконечности число необнаруживаемых ошибок, возникающих в информационных и контрольных разрядах кодов Хэмминга одновременно, возрастает в 2k–1 раз (k — число контрольных разрядов), по сравнению с числом необнаруживаемых ошибок, возникающих только в информационных разрядах их кодовых слов. Также доказано, что при m→∞ показатель отношения числа необнаруживаемых ошибок, возникающих одновременно в информационных и контрольных разрядах, к числу необнаруживаемых ошибок, возникающих только в информационных разрядах, для кода Хэмминга с k+q контрольными разрядами увеличивается в 2q раз, по сравнению со значением для кода Хэмминга с k контрольными разрядами (здесь q — произвольное натуральное число). Установленные характеристики кодов Хэмминга целесообразно учитывать при синтезе самопроверяемых цифровых устройств. Приведены примеры учета установленных свойств кодов Хэмминга для синтеза схем встроенного контроля по методу логического дополнения.
Ключевые слова: код Хэмминга, контролепригодное цифровое устройство, самопроверяемое цифровое устройство, схема встроенного контроля, метод логического дополнения, необнаруживаемая ошибка

Список литературы:
  1. Hamming R. W. Error Detecting and Correcting Codes // Bell System Technical Journal. 1950. Vol. 29, N 2. Р. 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. Сапожников В. В., Сапожников Вл. В., Ефанов Д. В. Коды Хэмминга в системах функционального контроля логических устройств. СПб: Наука, 2018. 151 с.
  6. Лисенков В. М., Бестемьянов П. Ф., Леушин В. Б., Лисенков А. В., Ваньшин А. Е. Системы управления движением поездов на перегонах: учеб. для вузов ж.-д. транспорта в 3 ч. Ч. 2. М.: Учебно-методический центр по образованию на железнодорожном транспорте, 2009. 324 с.
  7. Nikitin D., Manakov A., Nikitin A., Popov P., Kotenko A. Automatic Locomotive Signalization System Modification with Weight-Based Sum Codes // Proc. of 15th IEEE East-West Design & Test Symp. (EWDTS’2017). Novi Sad, Serbia, 29 September—2 October 2017. P. 332—336. DOI: 10.1109/EWDTS.2017.8110099.
  8. Tshagharyan G., Harutyunyan G., Shoukourian S., Zorian Y. Experimental Study on Hamming and Hsiao Codes in the Context of Embedded Applications // Proc. of 15th IEEE East-West Design & Test Symp. (EWDTS’2017). Novi Sad, Serbia, 29 September—2 October 2017. P. 25—28. DOI: 10.1109/EWDTS.2017.8110065.
  9. Ojiganov A. A. The Use of Hamming Codes in Digital Angle Converters Based on Pseudo-Random Code Scales // Measurement Techniques. 2015. Vol. 58, is. 5. P. 512—519. DOI: 10.1007/s11018-015-0746-7.
  10. Согомонян Е. С., Слабаков Е. В. Самопроверяемые устройства и отказоустойчивые системы. М.: Радио и связь, 1989. 208 с.
  11. Telpukhov D. V., Zhukova T. D. New Metric for Evaluating the Effectiveness of Redundancy in Fault-Tolerant Logic Circuits // Proc. of 19th IEEE East-West Design & Test Symp. (EWDTS’2021). Batumi, Georgia, 10—13 September 2021. P. 355—360. DOI: 10.1109/EWDTS52692.2021.9581027.
  12. Гаврилов С. В., Гуров С. И., Тельпухов Д. В., Жукова Т. Д. Использование информационной избыточности при построении сбоеустойчивых комбинационных схем // Таврический вестник информатики и математики. 2018. № 2(39). С. 29—44.
  13. Тельпухов Д. В., Деменева А. И., Жукова Т. Д., Хрущев Н. С. Исследование и разработка систем автоматизированного проектирования схем функционального контроля комбинационных логических устройств // Электронная техника. Сер. 3. Микроэлектроника. 2018. № 1(169). С. 15—22.
  14. Сапожников В. В., Сапожников Вл. В., Гессель М. Самодвойственные дискретные устройства. СПб: Энергоатомиздат, 2001. 331 с.
  15. Ефанов Д. В. Предельные свойства кода Хэмминга в схемах функционального диагностирования // Информатика и системы управления. 2011. № 3. С. 70—79.
  16. Sapozhnikov V., Sapozhnikov Vl., Efanov D., Blyudov A. Analysis of Error-Detection Possibilities of CED Circuits Based on Hamming and Berger Codes // Proc. of 11th IEEE East-West Design & Test Symp. (EWDTS’2013). Rostov-on-Don, Russia, 27—30 September 2013. P. 200—207. DOI: 10.1109/EWDTS.2013.6673097.
  17. Сапожников В. В., Сапожников Вл. В., Ефанов Д. В. Особенности применения кодов Хэмминга при организации самопроверяемых схем встроенного контроля // Изв. вузов. Приборостроение. 2018. Т. 61, № 1. С. 47—59. DOI: 10.17586/0021-3454-2018-61-1-47-59.
  18. Гессель М., Морозов А. В., Сапожников В. В., Сапожников Вл. В. Логическое дополнение — новый метод контроля комбинационных схем // Автоматика и телемеханика. 2003. № 1. С. 167—176.
  19. Göessel M., Ocheretny V., Sogomonyan E., Marienfeld D. New Methods of Concurrent Checking: Edition 1. Dordrecht: Springer Science+Business Media B.V., 2008. 184 p.
  20. Efanov D., Osadchy G., Zueva M. Specifics of Error Detection with Modular Sum Codes in Concurrent Error-Detection Circuits Based on Boolean Complement Method // Proc. of 19th IEEE East-West Design & Test Symp. (EWDTS’2021). Batumi, Georgia, 10—13 September 2021. P. 59—69. DOI: 10.1109/EWDTS52692.2021.9581036.
  21. 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 // Proc. of 11th IEEE Intern. Conf. on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (IDAACS’2021). Vol. 1. Cracow, Poland, 22—25 September 2021. P. 424—431. DOI: 10.1109/IDAACS53288.2021.9660837.
  22. Сапожников В. В., Сапожников Вл. В., Ефанов Д. В. Коды с суммированием для систем технического диагностирования. Т. 1. Классические коды Бергера и их модификации. М.: Наука, 2020. 383 с.
  23. Сапожников В. В., Сапожников Вл. В., Ефанов Д. В. Коды с суммированием для систем технического диагностирования. Т. 2. Взвешенные коды с суммированием. М.: Наука, 2021. 455 с.
  24. 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 // Proc. of 14th IEEE East-West Design & Test Symp. (EWDTS’2016). Yerevan, Armenia, 14—17 October 2016. P. 134—141. DOI: 10.1109/EWDTS.2016.7807686.
  25. Morozov M., Saposhnikov V. V., Saposhnikov Vl. V., Goessel M. New Self-Checking Circuits by Use of Berger-Сodes // Proc. of 6th IEEE Intern. On-Line Testing Workshop. Palma de Mallorca, Spain, 3—5 July 2000. P. 171—176.
  26. Efanov D. V., Sapozhnikov V. V., Sapozhnikov Vl. V. The Self-Checking Concurrent Error-Detection Systems Synthesis Based on the Boolean Complement to the Bose-Lin Codes with the Modulo Value M=4 // Electronic Modeling. 2021. Vol. 43, is. 1. P. 28—45. DOI: 10.15407/emodel.43.01.028.
  27. Nikolos D. Self-Testing Embedded Two-Rail Checkers // J. of Electronic Testing: Theory and Applications. 1998. Vol. 12, is. 1-2. P. 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. Design of Totally Self-Checking Comparators with an Arbitrary Number of Inputs // IEEE Transactions on Computers. 1984. Vol. C-33, N 6. P. 546—550.
  30. Drozd O., Sachenko A., Hiromoto R., Zashcholkin K., Drozd M. Particularities of Sync Monitoring in FPGA Components of Safety-Related Systems // Proc. of 11th IEEE Intern. Conf. on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (IDAACS’2021). Vol. 2. Cracow, Poland, 22—25 September 2021. P. 979—983. DOI: 10.1109/IDAACS53288.2021.9660928.