КОДЫ ХЭММИНГА В СИСТЕМАХ ФУНКЦИОНАЛЬНОГО КОНТРОЛЯ

HAMMING CODES IN FUNCTIONAL CONTROL SYSTEMS

Maxim Kravchina

student, department of hardware and software systems, Don State Technical University,

Russia, Rostov-on-Don

Alexandra Kravchina

student, department of hardware and software systems, Don State Technical University,

Russia, Rostov-on-Don

АННОТАЦИЯ

Статья посвящена изучению свойств обнаружения ошибок кодом Хэмминга в информационных разрядах, при условии безошибочности контрольных элементов. Для решения этой задачи необходимо использовать аппаратную или программную реализацию систем функционального контроля.

ABSTRACT

The article is devoted to the study of the Hamming code error detection properties in the information bits, provided that the control elements are error-free. To solve this problem, it is necessary to use hardware or software implementation of functional control systems.

Ключевые слова: код Хэмминга, вероятность, обнаруживаемая ошибка.

Keywords: Hamming code, probability, detectable error.

При создании систем функционального контроля было установлено новое свойство кода Хэмминга, которое может быть полезным при организации систем управления [1].

Когда в принятом коде производится проверка четности внутри контрольных групп, случай двойной ошибки ничем внешне не отличается от случая одиночной ошибки. Например, предположим теперь, что при передаче данного кодового слова 10001100101 произошли ошибки в 3-м и 6-м разрядах, так, что принято кодовое слово 10101000101. Рассмотрим ошибки в 5 разряде, таблица 1.

Таблица 1

Ошибки прошли в 5-м разряде

Вывод: ошибка произошла в 5-м разряде Истинное кодовое слово: 1 0 0 0 1 1 0 0 1 0 1 Ошибочное кодовое слово  : 1 0 1 0 1 0 0 0 1 0 1 Исправленное кодовое слово : 1 0 1 0 0 0 0 0 1 0 1 Результат получается ещё более отдаленным от правильного, чем принятый код. Исправление кода по общему правилу не только не улучшило, но даже ухудшило бы дело.

Также возможно создать код, который обнаруживает двойные ошибки и исправляет одиночные ошибки. Для этого дополнительный управляющий бит (двойной управляющий бит) должен быть назначен самокорректирующемуся коду, предназначенному для исправления отдельных ошибок. В этом случае общее количество битов кода будет m + k + 1. Цифра в бите двойной проверки устанавливается так, чтобы количество единиц во всех m + k + 1 цифрах кода было четным. Эта категория не входит в общую нумерацию и не входит ни в одну контрольную группу. Например, код Хэмминга с m=7 и k=4.  Пусть информационное кодовое слово – 0110101. Рассмотрим пример в таблице 2.

Таблица 2

Код Хемминга с m=7 и k=4

При этом могут быть следующие случаи. В принятом коде в целом и по всем контрольным группам количество единиц четно. Если тройные ошибки и ошибки в большем количестве разрядов исключаются, то первый случай соответствует безошибочному приему кода. В принятом коде в целом количество единиц нечетно, но во всех контрольных группах количество единиц четно. Раз получившаяся сумма не равна нулю, а контрольный бит указывает на ошибку передачи, то обнаруживаем двойную ошибку. Исправление двойных ошибок здесь, конечно, невозможно. Увеличивая дальше количество контрольных разрядов, можно было бы построить коды, рассчитанные на исправление двойных ошибок и обнаружение тройных и т.д. Однако методы построения этих кодов не вполне разработаны.

Построение кодов Хэмминга основано на принципе проверки четность веса W (количества единичных символов) в информационной группе сделать блок кода. Поясним идею проверки четности на примере простейшего ярлыка код декламации, который называется кодом с проверкой на четность или код четности (равенство). В таком коде кодовые комбинации не избыточного первичного k-битный двоичный код, добавляется дополнительная цифра (символ проверки четности, называемый проверкой четности, или ролик). Если количество символов равно 1, то исходное кодовое слово будет четным. Управляющий символ 0 формируется в дополнительном бите, и, если количество знаков 1 нечетное, то в качестве дополнительной цифры – символ 1. Следовательно, общее количество символов равно 1 в любой передаче входной пароль всегда будет четным. Таким образом, правило формирования контрольного символа переходит к следующему:

где       i – соответствующий информационный символ (0 или 1);

k – общий их количество и под операцией здесь и далее мы понимаем сложение mod 2.

Очевидно, что добавление дополнительной цифры увеличивает общее количество возможных комбинаций, вдвое превышающее число комбинации исходного первичного кода, а условие четности разделяет все комбинации разрешенных и запрещенных [2]. Код проверен на четность позволяет обнаружить единственную ошибку при получении кода комбинация, поскольку такая ошибка нарушает условие четности, изменение разрешенной комбинации на запрещенную. Критерием правильности принятой комбинации является равенство к нулю результата S mod 2 сумма всех n кодовых символов, включая чайный знак r1. В случае единственной ошибки S, значение 1 мигает: S = r1 ⊕ i1 ⊕ i2 ⊕ ... ⊕ ik 0 - нет ошибки, 1 - разовая ошибка. Этот код представляет собой код (k +1, k) или (n, n - 1) код. Минимум кодовое расстояние равно двум (dmin = 2), поэтому ошибок нет. Простой код четности может использоваться только для обнаружения (не ремонта) одного много ошибок. За счет увеличения количества дополнительных контрольных цифр и форм проверка по определенным правилам проверочных символов r равными 0 или 1, можно улучшить характеристики исправления кода. Коды Хемминга позволяют исправлять одиночную ошибку, с помощью непосредственного описания. Для каждого числа проверочных символов r = 3, 4, 5… существует классический код Хемминга с маркировкой в формуле

При других значениях числа информационных символов k получаются так называемые усеченные (укороченные) коды Хемминга. Так, для Международного телеграфного кода МТК-2, имеющего 5 информационных символов, потребуется использование корректирующего кода (9,5), являющегося усеченным от классического кода Хемминга (15,11), так как число символов в этом коде уменьшается (укорачивается) на 6.

Список литературы:

1. Сапожников, В. В. Коды Хэмминга в системах функционального контроля логических устройств / В. В. Сапожников, В. В. Сапожников, Д. В. Ефанов. – Санкт-Петербург : ФГУП "Академический научно-издательский, производственно-полиграфический и книгораспространительский центр "Наука", 2018. – 151 с.
2. Долгов, А.И. О применимости математического масштабирования и нормирования при решении прикладных задач / А.И. Долгов, Д.В. Маршаков // Вестник Донского государственного технического университета. –2018. – Т. 18. – № 4. – С. 92-101.