4.2. Оптимальное посимвольное декодирование

В 1976 г. Хартман и Рудольф [20] предложили оптимальный алгоритм декодирования групповых кодов, минимизирующий среднюю вероятность ошибки символа. Этот алгоритм очень похож на АРР-алгоритм порогового декодирования; единственное различие состоит в том, что при вычислении решающей функции используются все возможные проверочные уравнения, а не только те, которые ортогональны по данному символу. Поэтому точная реализация этого правила декодирования возможна лишь для кодов с малым числом проверочных символов. Формальное описание алгоритма Хартмана — Рудольфа очень несложно. Пусть кодовое слово дуального кода и символ этого кодового слова. Определим отношение правдоподобия для принятого символа формулой

Наконец, положим

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

где при в остальных случаях. Символ означает сложение по модулю 2 и используется для того, чтобы отличать сложение по модулю 2 от обычного сложения.

В качестве примера рассмотрим циклический -код Хемминга, для которого матрица Н имеет вид

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

Таким образом, символ на позиции 6 полагается равным 0, если и равным 1, если Для декодирования остальных символов следует циклически сдвинуть принятое слово и заново вычислить