2.3. Метод декодирования по алгоритму Витерби
Метод представляет собой декодирование по максимуму правдоподобия. Идея алгоритма Витерби состоит в том, что в декодере воспроизводят все возможные пути последовательных изменений состояний сигнала, сопоставляя получаемые при этом кодовые символы с принятыми аналогами по каналу связи и на основе анализа ошибок между принятыми и требуемыми символами определяют оптимальный путь (оптимальной считается та последовательность, расстояние Хемминга которой от принятой последовательности минимально).
Декодирование по методу Витерби, по существу, представляет собой алгоритм поиска наивыгоднейшего, максимально правдоподобного пути на графе – решеточной диаграмме кода.
2.3.1. Декодирование в случае отсутствия ошибок при приеме
Продемонстрируем работу алгоритма на примере несистематического сверточного кода с маркировкой (2, 1, 3) с порождающими полиномами, задаваемыми выражением (3.6), кодер которого показан на рис. 1.2, б. Возьмем следующую последовательность символов 10110 и будем полагать, что все символы приняты без ошибок.
Рис. 12. Диаграмма переходов состояний сигнала
Рассмотрим графическое отображение изменений состояния сигнала (рис. 2.5). Начальным всегда является состояние 00. В соответствии с диаграммой переходов состояний сигнала (рис. 12) в первый тактовый момент возможны два перехода: 00 → 00 и 00 → 10.
Первому переходу соответствует на выходе кодера кодовая комбинация 00, второму – 11.
При приходе на вход кодера первой информационной 1 первой ветви 00 →00 будут соответствовать две ошибки в приеме, а второй ветви 00 → 10 нуль ошибок. Ошибка по каждой ветви служит метрикой dH в смысле расстояния Хэмминга, т. е. соответствует числу отличающихся от требуемых принятых символов. Эти метрики зафиксированы в узлах диаграммы (рис. 13).
В момент времени 2 (второй такт) сигнал может принять 4 состояния, которые определяются двумя возможными переходами из 00 и двумя переходами из 10. Сравнение с принятыми символами 01 дает следующие метрики соответствующих ветвей dН: 00 → 00dH = 1, 00 → 10dH ==1, 10 → 01dH = 0, 10 → 11dH = 2.
Рис. 13. Декодирование на основе алгоритма Витерби в отсутствие ошибок при приеме
Суммарная метрика d∑Н по каждому из возможных путей определяется как сумма метрик составляющих его ветвей. Значения суммарных метрик показаны на диаграмме рис. 13. Для момента времени 3 следует анализировать уже 8 возможных путей и сравнивать 8 соответствующих им метрик d∑H.
Алгоритм Витерби выбирает путь с наименьшей суммарной метрикой (“штрафом”) и может отбрасывать по ходу продвижения во времени те пути, которые имеют штраф, превышающий минимальный “штраф” в данный момент времени на некоторую пороговую величину.
Для упрощения рис. 13 установлен пороговый уровень d∑H = 3 и не показываются ветви с большим значением dH. Оптимальным путем является путь с наименьшим “штрафом” ( при отсутствии ошибок в канале передачи символов d∑Н = 0). Последовательность бит на выходе декодера, соответствующая этому пути, отмеченному на рис. 13 утолщением ветвей, совпадает с передаваемым информационным сигналом.