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

Материал из Википедии — свободной энциклопедии

В 1967 году Витерби разработал и проанализировал алгоритм, в котором, по сути, реализуется декодирование, основанное на принципе максимального правдоподобия; однако в нем уменьшается вычислительная нагрузка за счет использования особенностей структуры конкретной решетки кода. Преимущество декодирования Витерби, по сравнению с декодированием по методу "грубой силы", заключается в том, что сложность декодера Витерби не является функцией количества символов в последовательности кодовых слов. Алгоритм включает в себя вычисление меры подобия (или расстояния), между сигналом, полученным в момент времени $t I$ , и всеми путями решетки, входящими в каждое состояние в момент времени $t i$ . В алгоритме Витерби не рассматриваются те пути решетки, которые, согласно принципу максимального правдоподобия, заведомо не могут быть оптимальными. Если в одно и то же состояние входят два пути, выбирается тот, который имеет лучшую метрику; такой путь называется выживающим. Отбор выживающих путей выполняется для каждого состояния. Таким образом, декодер углубляется в решетку, принимая решения путем исключения менее вероятных путей. Предварительный отказ от маловероятных путей упрощает процесс декодирования. В 1969 году Омура (Omura) показал, что основу алгоритма Витерби составляет оценка максимума правдоподобия. Отметим, что задачу отбора оптимальных путей можно выразить как выбор кодового слова с максимальной метрикой правдоподобия или минимальной метрикой расстояния.

[править] Сущность метода

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

[править] Принцип работы декодера

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

[править] Пример

Схема кодера

Решетчатая диаграмма кодера

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

Процесс декодирования

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

На шаге i) степень различия метрик правильного и неправильного путей достаточно велика ( $d c o r r e c t = 2$ , $d e r r o r = 4$ ), то есть в данном случае можно было бы ограничить глубину декодирования величиной $b < = 6$ . Но иногда более длинный к данному сечению путь может оказаться в конечном итоге самым коротким, поэтому особенно увлекаться уменьшением размера окна декодирования b с целью упрощения работы декодера не стоит. На практике глубину декодирования обычно выбирают в диапазоне $n < b < n + l$ , где $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.
Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. — М.: Техносфера, 2005.
Скляр Б. Цифровая связь: теоретические основы и практическое применение (2-е изд) — М.: Вильямс, 2003.