Технические науки/6. Электротехника и радиоэлектроника

Бегимадова Т.Х.

ГВУЗ: «Национальный горный университет», Украина

Механизм детектирования и исправления ошибок с помощью расстояния Хемминга

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

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

Простейшим способом обнаружения ошибок является контроль по четности. Обычно контролируется передача блока данных (М бит). Этому блоку ставится в соответствие кодовое слово длиной N бит, причем N>M. Избыточность кода характеризуется величиной 1-M/N. Вероятность обнаружения ошибки определяется отношением M/N (чем меньше это отношение, тем выше вероятность обнаружения ошибки, но и выше избыточность).

Поясним идею проверки на четность на примере простейшего корректирующего кода, который так и называется кодом с проверкой на
четность или кодом с проверкой по паритету (равенству).
В таком коде к кодовым комбинациям безызбыточного первичного
двоичного k-разрядного кода добавляется один дополнительный разряд
(символ проверки на четность, называемый проверочным, или контрольным). Если число символов 1 исходной кодовой комбинации четное, то в дополнительном разряде формируют контрольный символ 0, а
если число символов 1 нечетное, то в дополнительном разряде формируют символ 1. В результате общее число символов 1 в любой передаваемой кодовой комбинации всегда будет четным. Таким образом, правило формирования проверочного символа сводится к следующему: r1 = i1 ⊕ i2 ⊕ ... ⊕ ik ,
где i – соответствующий информационный символ (0 или 1); k – общее
их число а под операцией "⊕" здесь и далее понимается сложение по
mod 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, можно усилить корректирующие свойства кода так, чтобы он позволял не только обнаруживать, но и исправлять ошибки. Таким образом, контроль по четности достаточно эффективен для выявления одиночных и множественных ошибок в условиях, когда они являются независимыми. Это и является основным преимуществом кодов Хемминга.

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

Код Хэмминга используется во многих прикладных программах в области хранения данных, особенно в RAID 2; кроме того, метод Хемминга давно применяется в памяти типа ECC и позволяет очень быстро исправлять однократные и обнаруживать двукратные ошибки.

Таким образом, в статье обоснованы преимущества использования кодов Хемминга, а именно: возможность не только находить ошибки, но и исправлять их, простота реализации, широкий спектр применения. Выявленные недостатки данного кода являются не существенными по сравнению с его преимуществами.

Литература:

1. Блейхут Р. Теория и практика кодов, контролирующих ошибки. — М.: Мир, 1986. — 576 с.

2. Лидовский В.И. Теория информации. – М.: Высшая школа, 2002 г. – 120 с.
3. Нефедов В.И., Халкин В.И., Федоров Е.В. Метрология и радиоизмерения в телекоммуникационных системах. – М.: Высшая школа, 2001 г. – 383 с.
4. Цапенко М.П. Измерительные информационные системы. – М.: Энергоатом , 2005 г. –440 с.