Главная > Помехоустойчивое кодирование > Кодирование с исправлением ошибок в системах цифровой связи
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

4.2.1. Вывод алгоритма Хартмана-Рудольфа

Вывод правила декодирования Хартмана — Рудольфа состоит из трех этапов. Прежде всего следует записать в виде

Далее, применяя формулу Байеса и перечисляя все случаи, в которых можно показать, что

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

Наконец, следует использовать такой результат из теории конечного преобразования Фурье. Пусть -произвольная функция, заданная на множестве всех -мерных двоичных векторов, и -конечное преобразование Фурье определяемое равенством

Тогда можно показать, что

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

кода С, ее сумма по всем кодовым векторам пропорциональна сумме значений преобразования Фурье на множестве всех кодовых слов дуального слова. Используя этот результат с учетом определения сразу получаем (4.19). Детали доказательства оставляются читателю в качестве упражнения (см. задачи).

<< Предыдущий параграф Следующий параграф >>
Оглавление