Основы теории передачи информации


Декодирование сверточных кодов Алгоритм Витерби


Наилучшей схемой декодирования корректирующих кодов, как уже отмечалось, является декодирование методом максимального правдоподобия, когда декодер определяет набор условных вероятностей Р(r/Ui), соответствующих всем возможным кодовым векторам Ui , и решение принимает  в  пользу  кодового  слова,  соответствующего  максимальному Р( r/Ui ).

Для двоичного симметричного канала без памяти

(канала, в котором вероятности передачи   и  1,  а   также  вероятности   ошибок  вида  0 ® 1  и  1 ® 0 одинаковы, ошибки в j-м и i-м символах кода независимы) декодер максимального правдоподобия сводится к декодеру минимального хеммингова расстояния. Последний вычисляет расстояние Хемминга между принятой последовательностью  r  и всеми возможными кодовыми векторами Ui и выносит решение в пользу того вектора, который оказывается ближе к принятому.

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

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

Впервые идея такого декодера была предложена Витерби.

Работает он следующим образом.

Предположим, на вход декодера поступил сегмент последовательности r длиной b, превышающей кодовую длину блока n. Назовем b окном декодирования. Сравним все кодовые слова данного кода (в пределах сегмента длиной b) с принятым словом и выберем кодовое слово, ближайшее к принятому. Первый информационный кадр выбранного кодового слова примем в качестве оценки информационного кадра декодированного слова.

После этого в декодер вводится  n0  новых символов, а введенные ранее самые старые  n0

символов сбрасываются, и процесс повторяется для определения следующего информационного кадра. 

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


Начало  Назад  Вперед



Книжный магазин