Корректирующие коды Хемминга.
Построение кодов Хемминга базируется на принципе проверки на чётность веса W (числа единичных символов) в информационной группе кодового блока.
Поясним идею проверки на чётность на примере простейшего корректирующего кода, который так и называется кодом с проверкой на чётность или кодом с проверкой по паритету (равенству).
В таком коде к кодовым комбинациям безизбыточного первичного двоичного k - разрядного кода добавляется один дополнительный разряд (символ проверки на чётность, называемый проверочным, или контрольным). Если число символов “1” исходной кодовой комбинации чётное, то в дополнительном разряде формируют контрольный символ 0, а если число символов “1” нечётное, то в дополнительном разряде формируют символ 1. В результате общее число символов “1” в любой передаваемой кодовой комбинации всегда будет чётным.
Таким образом, правило формирования проверочного символа сводится к следующему:
где i - соответствующий информационный символ (0 или 1), k - общее их число, а под операцией "⊕" здесь и далее понимается сложение по mod2. Очевидно, что добавление дополнительного разряда увеличивает общее число возможных комбинаций вдвое по сравнению с числом комбинаций исходного первичного кода, а условие чётности разделяет все комбинации на разрешённые и неразрешённые. Код с проверкой на чётность позволяет обнаруживать одиночную ошибку при приёме кодовой комбинации, так как такая ошибка нарушает условие чётности, переводя разрешённую комбинацию в запрещённую.
Критерием правильности принятой комбинации является равенство нулю результата S суммирования по mod 2 всех n символов кода, включая проверочный символ r1. При наличии одиночной ошибки S принимает значение 1:
Этот код является (k +1, k) - кодом, или (n, n -1) - кодом. Минимальное расстояние кода равно двум (dmin = 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) информационных символах (i1, i2, i3, i4) будем полагать, что они сгруппированы в начале кодового слова, хотя это и не обязательно. Дополним эти информационные символы тремя проверочными символами (r = 3), задавая их следующими равенствами проверки на чётность, которые определяются соответствующими алгоритмами [3,5]:
где знак означает сложение по модулю 2.
В соответствии с этим алгоритмом определения значений проверочных символов ri ниже выписаны все возможные 16 кодовых слов (7,4) - кода Хемминга.
На рис. 3.3 приведена схема декодера для (7,4) - кода Хемминга, на вход которого поступает кодовое слово
V = ( i1', i2', i3', i4', r1', r2', r3')
Апостроф означает, что любой символ слова может быть искажён помехой в канале передачи.
В декодере в режиме исправления ошибок строится последовательность:
Трёхсимвольная последовательность ( s1, s2, s3 ) называется синдромом.
Термин "синдром" используется и в медицине, где он обозначает сочетание признаков, характерных для определённого заболевания. В данном случае синдром S = (s1, s2, s3 ) представляет собой сочетание результатов проверки на чётность соответствующих символов кодовой группы и характеризует определённую конфигурацию ошибок (шумовой вектор).