Метод декодирования по алгоритму Витерби

Метод представляет собой декодирование по максимуму правдоподобия. Идея алгоритма Витерби состоит в том, что в декодере воспроизводят все возможные пути последовательных изменений состояний сигнала, сопоставляя получаемые при этом кодовые символы с принятыми аналогами по каналу связи и на основе анализа ошибок между принятыми и требуемыми символами определяют оптимальный путь (оптимальной считается та последовательность, расстояние Хемминга которой от принятой последовательности минимально).

Декодирование по методу Витерби, по существу, представляет собой алгоритм поиска максимально правдоподобного пути на графе – решеточной диаграмме кода.

1. Декодирование в случае отсутствия ошибок при приеме

Продемонстрируем работу алгоритма на примере несистематического сверточного кода с маркировкой (2,1,3) с порождающими полиномами, задаваемыми выражением

;

,

Возьмем следующую последовательность информационных символов 10110. Этой последовательности соответствует выходная последовательность 1110000101.

Задача декодирования рассматривается как задача нахождения пути на решетчатой диаграмме. Пусть принята кодовая комбинация 1110000101 без ошибок.

Рассмотрим графическое отображение изменений состояния сигнала (рис. 8.34). Начальным всегда является состояние 00. В соответствии с диаграммой переходов состояний сигнала в первый тактовый момент возможны два перехода: 00 → 00 и 00 → 10.

Первому переходу соответствует на выходе кодера кодовая комбинация 00, второму – 11.

При приходе на вход декодера первой пары 11 первой ветви 00 →00 будут соответствовать две ошибки в приеме, а второй ветви 00 → 10 нуль ошибок. Ошибка по каждой ветви служит метрикой в смысле расстояния Хэмминга, т.е. соответствует числу отличающихся от требуемых принятых символов. Сравнение с принятыми символами 11 дает следующие метрики соответствующих ветвей : 00 → 00 = 2, 00 → 10 =0.

Эти метрики зафиксированы на диаграмме (рис. 8.34).

В момент времени 2 (второй такт) сигнал может принять 4 состояния, которые определяются двумя возможными переходами из 00 и двумя переходами из 10. Сравнение с принятыми символами 10 дает следующие метрики соответствующих ветвей : 00 → 00 = 1, 00 → 10 =1, 10 → 01 = 0, 10 → 11 = 2.

Суммарная метрика (метрика путей) по каждому из возможных путей определяется как сумма метрик составляющих его ветвей. Значения суммарных метрик (метрик путей) показаны на диаграмме рис. 8.34 в кружках. Для момента времени 3 следует анализировать уже 8 возможных путей и сравнивать 8 соответствующих им метрик .

Алгоритм Витерби выбирает путь с наименьшей суммарной метрикой (“штрафом”) и может отбрасывать по ходу продвижения во времени те пути, которые имеют штраф, превышающий минимальный “штраф” в данный момент времени на некоторую пороговую величину.

Для упрощения рис. 8.34 установлен пороговый уровень = 3 и не показываются ветви с большим значением . Оптимальным путем является путь с наименьшим “штрафом” (при отсутствии ошибок в канале передачи символов = 0). Последовательность бит на выходе декодера, соответствующая этому пути, отмеченному на рис. 8.34 жирной ветвью, совпадает с передаваемым информационным сигналом.

2. Декодирование в случае наличия ошибок при приеме

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

1 1 1 0 0 0 0 1 0 1

0 1 1 0 1 0 0 1 0 1.

01 10 10 01 01

Теперь метрики первой и третьей ветвей оптимального пути не равны нулю и суммарная метрика оптимального пути = 2. Однако как следует из рис. 8.35, оптимальный путь с наименьшей суммарной метрикой восстанавливает передачу последовательности информационных бит, т. е. использованный код исправляет ошибки.