Корректирующие коды Хемминга.

Построение кодов Хемминга базируется на принципе проверки на чётность веса W (числа единичных символов) в информационной группе кодового блока.

Поясним идею проверки на чётность на примере простейшего корректирующего кода, который так и называется кодом с проверкой на чётность или кодом с проверкой по паритету (равенству).

В таком коде к кодовым комбинациям безизбыточного первичного двоичного k - разрядного кода добавляется один дополнительный разряд (символ проверки на чётность, называемый проверочным, или контрольным). Если число символов “1” исходной кодовой комбинации чётное, то в дополнительном разряде формируют контрольный символ 0, а если число символов “1” нечётное, то в дополнительном разряде формируют символ 1. В результате общее число символов “1” в любой передаваемой кодовой комбинации всегда будет чётным.

Таким образом, правило формирования проверочного символа сводится к следующему:

где i - соответствующий информационный символ (0 или 1), k - общее их число, а под операцией "⊕" здесь и далее понимается сложение по mod2. Очевидно, что добавление дополнительного разряда увеличивает общее число возможных комбинаций вдвое по сравнению с числом комбинаций исходного первичного кода, а условие чётности разделяет все комбинации на разрешённые и неразрешённые. Код с проверкой на чётность позволяет обнаруживать одиночную ошибку при приёме кодовой комбинации, так как такая ошибка нарушает условие чётности, переводя разрешённую комбинацию в запрещённую.

Критерием правильности принятой комбинации является равенство нулю результата S суммирования по mod 2 всех n символов кода, включая проверочный символ r₁. При наличии одиночной ошибки S принимает значение 1:

Этот код является (k +1, k) - кодом, или (n, n -1) - кодом. Минимальное расстояние кода равно двум (d_min = 2), и, следовательно, никакие ошибки не могут быть исправлены. Простой код с проверкой на чётность может использоваться только для обнаружения (но не исправления) однократных ошибок.

Увеличивая число дополнительных проверочных разрядов и формируя по определённым правилам проверочные символы r, равные 0 или 1, можно усилить корректирующие свойства кода так, чтобы он позволял не только обнаруживать, но и исправлять ошибки. На этом и основано построение кодов Хемминга.

Коды Хемминга. Рассмотрим эти коды, позволяющие исправлять одиночную ошибку, с помощью непосредственного описания. Для каждого числа проверочных символов r = 3,4,5… существует классический код Хемминга с маркировкой

(20)

т.е. - (7,4), (15,11), (31,26) …

При других значениях числа информационных символов k получаются так называемые усечённые (укороченные) коды Хемминга. Так, для международного телеграфного кода МТК-2 , имеющего 5 информационных символов, потребуется использование корректирующего кода (9,5), являющегося усечённым от классического кода Хемминга (15,11), так как число символов в этом коде уменьшается (укорачивается) на 6. Для примера рассмотрим классический код Хемминга (7,4), который можно сформировать и описать с помощью кодера, представленного на рис.3.2. В простейшем варианте при заданных четырёх (k=4) информационных символах (i₁, i₂, i₃, i₄) будем полагать, что они сгруппированы в начале кодового слова, хотя это и не обязательно. Дополним эти информационные символы тремя проверочными символами (r = 3), задавая их следующими равенствами проверки на чётность, которые определяются соответствующими алгоритмами [3,5]:

где знак Å означает сложение по модулю 2.

В соответствии с этим алгоритмом определения значений проверочных символов r_i ниже выписаны все возможные 16 кодовых слов (7,4) - кода Хемминга.

На рис. 3.3 приведена схема декодера для (7,4) - кода Хемминга, на вход которого поступает кодовое слово

V = ( i₁', i₂', i₃', i₄', r₁', r₂', r₃')

Апостроф означает, что любой символ слова может быть искажён помехой в канале передачи.

В декодере в режиме исправления ошибок строится последовательность:

Трёхсимвольная последовательность ( s₁, s₂, s₃ ) называется синдромом.

Термин "синдром" используется и в медицине, где он обозначает сочетание признаков, характерных для определённого заболевания. В данном случае синдром S = (s₁, s₂, s₃ ) представляет собой сочетание результатов проверки на чётность соответствующих символов кодовой группы и характеризует определённую конфигурацию ошибок (шумовой вектор).