5.8.3. Алгоритм декодирования Витерби

Для сверточных кодов разработаны алгоритмы синдромного, последовательного декодирования и декодирования по максимуму правдоподобия (алгоритм Витерби). На практике широко используется последний метод, что объясняется простотой реализации при небольших длинах кодового ограничения и получаемым выигрышем от кодирования.

Алгоритм Витерби является рекуррентной процедурой, направленной на поиск пути по кодовой решетке, ближайшего к принимаемой последовательности. Как уже указывалось, декодирование по минимуму расстояния является оптимальным в канале с независимыми ошибками. Основные операции алгоритма поясним при декодировании кода примера 5.15.

Пусть для простоты передается нулевое кодовое слово, а в канале произошла трехкратная ошибка, так что принятая последовательность имеет вид 10 10 00 00 10 00 ... 00 ... Результаты поиска ближайшего пути после приема 14 элементарных блоков показаны на рис. 5.12. Промежуточные этапы работы декодера при сделанных предположениях подробно рассмотрены в [3].

На правой части рисунка видны четыре пути, ведущие в каждый узел решетки. Рядом проставлены расстояния (меры расходимости) этих путей от принятой последовательности на отрезке из 14 блоков. Мера верхнего пути значительно меньше мер нижних. Поэтому можно предположить, что верхний путь наиболее вероятен. Однако декодер Витерби, не зная следующих фрагментов принимаемой последовательности, вынужден запомнить все четыре пути на время приема  элементарных блоков. Число  называется шириной окна декодирования. Понятно, что для уменьшения ошибки декодирования следует выбирать  достаточно большим, в несколько раз превышающим длину блока, что, естественно, усложняет декодер. В данном случае .

Отметим, что тактика выбора и последующего анализа только одного пути с наименьшим расстоянием составляет сущность более экономного последовательного декодирования [3, 26].

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

Левая часть рисунка демонстрирует возможную ситуацию неисправляемой ошибки. Существует два пути с одинаковыми мерами расходимости. Декодер может разрешить эту неопределенность двумя способами. Отметить этот участок как недостоверный или принять одно из двух решений: информационная последовательность равна 00000... или 10100.... Очевидно, расширение окна декодирования не позволяет исправить такую ошибку. Ее исправление возможно при использовании кода с большей корректирующей способностью.

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

1. Для каждого узла нового столбца вычисляются расстояния между принятым блоком и маркировкой ребер, ведущих в данный узел.

2. Полученные меры расходимости ребер суммируются с расстоянием путей, которые они продолжают.

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

В результате этих операций к каждому узлу нового столбца вновь ведет один путь. Например, пусть новый блок из канала равен 00. Рассмотрим продолжение пути к нижнему узлу решетки, в который можно попасть из состояния кодера 10 по ребру 01 или из состояния 11 по ребру 10 (рис. 5.11). В обоих случаях расстояние этих ребер от принятого блока 00 равно 1. Однако суммарное расстояние пути, продолженного из состояния 10, равно 6, а пути из состояния 11 равно 7. Поэтому второй путь будет отброшен вместе с ребром 01, которое входило в нижний узел на предыдущем шаге декодирования (рис. 5.12). Оценка информационного символа производится по левому ребру пути, находящемуся в окне декодирования. Согласно правилу построения кодовой решетки принимается, что информационный символ равен 0, если ребро верхнее, и равен 1, если ребро нижнее.