Алгоритм свёрточного декодирования Витерби

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

Алгоритм включает в себя вычисление меры подобия (или расстояния), между сигналом, полученным в момент времени ${\displaystyle t_{I}}$, и всеми путями решётки, входящими в каждое состояние в момент времени ${\displaystyle t_{i}}$. В алгоритме Витерби не рассматриваются те пути решётки, которые, согласно принципу максимального правдоподобия, заведомо не могут быть оптимальными. Если в одно и то же состояние входят два пути, выбирается тот, который имеет лучшую метрику; такой путь называется выживающим. Отбор выживающих путей выполняется для каждого состояния. Таким образом, декодер углубляется в решётку, принимая решения путём исключения менее вероятных путей. Предварительный отказ от маловероятных путей упрощает процесс декодирования. В 1969 году Джим Омура (англ.) показал, что основу алгоритма Витерби составляет оценка максимального правдоподобия. Отметим, что задачу отбора оптимальных путей можно выразить как выбор кодового слова с максимальной метрикой правдоподобия или минимальной метрикой расстояния.

Наилучшей схемой декодирования корректирующих кодов является декодирование методом максимального правдоподобия^[], когда декодер определяет набор условных вероятностей ${\displaystyle P(r/U_{i})}$, соответствующих всем возможным кодовым векторам ${\displaystyle U_{i}}$, и решение принимает в пользу кодового слова, соответствующего максимальному ${\displaystyle P(r/U_{i})}$. Для двоичного симметричного канала без памяти (канала, в котором вероятности передачи 0 и 1, а также вероятности ошибок вида 0 -> 1 и 1 -> 0 одинаковы, ошибки в j-м и i-м символах кода независимы) декодер максимального правдоподобия сводится к декодеру минимального хеммингова расстояния. Последний вычисляет расстояние Хемминга между принятой последовательностью r и всеми возможными кодовыми векторами ${\displaystyle U_{i}}$ и выносит решение в пользу того вектора, который оказывается ближе к принятому. Естественно, что в общем случае такой декодер оказывается очень сложным и при больших размерах кодов ${\displaystyle n}$ и ${\displaystyle k}$ практически нереализуемым. Характерная структура сверточных кодов (повторяемость структуры за пределами окна длиной ${\displaystyle n}$) позволяет создать вполне приемлемый по сложности декодер максимального правдоподобия.

На вход декодера поступает сегмент последовательности ${\displaystyle r}$ длиной ${\displaystyle b}$, превышающей кодовую длину блока ${\displaystyle n}$. Назовем ${\displaystyle b}$ окном декодирования. Сравним все кодовые слова данного кода (в пределах сегмента длиной ${\displaystyle b}$) с принятым словом и выберем кодовое слово, ближайшее к принятому. Первый информационный кадр выбранного кодового слова принимается в качестве оценки информационного кадра декодированного слова. После этого в декодер вводится ${\displaystyle n_{0}}$ новых символов, а введенные ранее самые старые ${\displaystyle n_{0}}$ символов сбрасываются, и процесс повторяется для определения следующего информационного кадра. Таким образом, декодер Витерби последовательно обрабатывает кадр за кадром, двигаясь по решетке, аналогичной используемой кодером. В каждый момент времени декодер не знает, в каком узле находится кодер, и не пытается его декодировать. Вместо этого декодер по принятой последовательности определяет наиболее правдоподобный путь к каждому узлу и определяет расстояние между каждым таким путём и принятой последовательностью. Это расстояние называется мерой расходимости пути. В качестве оценки принятой последовательности выбирается сегмент, имеющий наименьшую меру расходимости. Путь с наименьшей мерой расходимости называется выжившим путём.

Рассмотрим работу декодера Витерби на простом примере. Полагаем, что кодирование производится с использованием сверточного (7,5)-кода. Пользуясь решетчатой диаграммой кодера, попытаемся, приняв некоторый сегмент ${\displaystyle r}$, проследить наиболее вероятный путь кодера. При этом для каждого сечения решетчатой диаграммы будем отмечать меру расходимости пути к каждому её узлу. Предположим, что передана кодовая последовательность U = (00000000…), а принятая последовательность имеет вид r = (10001000…), то есть в первом и в третьем кадрах кодового слова возникли ошибки. Как мы уже убедились, процедура и результат декодирования не зависят от передаваемого кодового слова и определяются только ошибкой, содержащейся в принятой последовательности. Поэтому проще всего считать, что передана нулевая последовательность, то есть U = (00000000…). Приняв первую пару символов (10), декодер определяет меру расходимости для первого сечения решетки, приняв следующую пару символов (00), — для второго сечения и т. д. При этом из входящих в каждый узел путей оставляем путь с меньшей расходимостью, поскольку путь с большей на данный момент расходимостью уже не сможет стать в дальнейшем короче. Заметим, что для рассматриваемого примера начиная с четвёртого уровня метрика (или мера расходимости) нулевого пути меньше любой другой метрики. Поскольку ошибок в канале больше не было, ясно, что в конце концов в качестве ответа будет выбран именно этот путь. Из этого примера также видно, что выжившие пути могут достаточно долго отличаться друг от друга. Однако на шестом-седьмом уровне первые семь ребер всех выживших путей совпадут друг с другом. В этот момент согласно алгоритму Витерби и принимается решение о переданных символах, так как все выжившие пути выходят из одной вершины, то есть соответствуют одному информационному символу.

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

На шаге i) степень различия метрик правильного и неправильного путей достаточно велика (${\displaystyle d_{correct}=2}$, ${\displaystyle d_{error}=4}$), то есть в данном случае можно было бы ограничить глубину декодирования величиной ${\displaystyle b<=6}$. Но иногда более длинный к данному сечению путь может оказаться в конечном итоге самым коротким, поэтому особенно увлекаться уменьшением размера окна декодирования b с целью упрощения работы декодера не стоит. На практике глубину декодирования обычно выбирают в диапазоне ${\displaystyle n<b<n+l}$, где ${\displaystyle l}$ — число исправляемых данным кодом ошибок. Несмотря на наличие в принятом фрагменте двух ошибок, его декодирование произошло без ошибки и в качестве ответа будет принята переданная нулевая последовательность.

• Алгоритм Витерби

• «Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm», IEEE Transactions on Information Theory, Volume IT-13, стр. 260—269, Апрель, 1967.
• Витерби А. Д., Омура Дж. К. Принципы цифровой связи и кодирования /Пер. с англ. под ред. К. Ш. Зигангирова. — М.: Радио и связь, 1982. — 536 с.
• Золотарёв В. В., Овечкин Г. В. Помехоустойчивое кодирование. Методы и алгоритмы: Справочник /Под. ред. чл.-кор. РАН Ю. Б. Зубарева. — М.: Горячая линия-Телеком, 2004.
• Карташевский В. Г., Мишин Д. В. Прием кодированных сигналов в каналах с памятью — Радио и связь, 2004.
• Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / пер. с англ. В. Б. Афанасьева. — М.: Техносфера, 2006. — 320 с. — (Мир связи). — 2000 экз. — ISBN 5-94836-035-0.
• Бернард Скляр. Цифровая связь. Теоретические основы и практическое применение = Digital Communications: Fundamentals and Applications. — 2 изд. — М.: «Вильямс», 2007. — С. 1104. — ISBN 0-13-084788-7.