Русская Википедия:Алгоритм свёрточного декодирования Витерби
Шаблон:Rq В 1967 году Эндрю Витерби разработал и проанализировал алгоритм декодирования, основанный на принципе максимального правдоподобия. Алгоритм оптимизирован за счёт использования особенностей структуры конкретной решётки кода. Преимущество декодирования Витерби по сравнению с декодированием по методу полного перебора заключается в том, что сложность декодера Витерби не является функцией количества символов в последовательности кодовых слов.
Алгоритм включает в себя вычисление меры подобия (или расстояния), между сигналом, полученным в момент времени <math>t_I</math>, и всеми путями решётки, входящими в каждое состояние в момент времени <math>t_i</math>. В алгоритме Витерби не рассматриваются те пути решётки, которые, согласно принципу максимального правдоподобия, заведомо не могут быть оптимальными. Если в одно и то же состояние входят два пути, выбирается тот, который имеет лучшую метрику; такой путь называется выживающим. Отбор выживающих путей выполняется для каждого состояния. Таким образом, декодер углубляется в решётку, принимая решения путём исключения менее вероятных путей. Предварительный отказ от маловероятных путей упрощает процесс декодирования. В 1969 году Джим Омура (англ.) показал, что основу алгоритма Витерби составляет оценка максимального правдоподобия. Отметим, что задачу отбора оптимальных путей можно выразить как выбор кодового слова с максимальной метрикой правдоподобия или минимальной метрикой расстояния.
Сущность метода
Наилучшей схемой декодирования корректирующих кодов является декодирование методом максимального правдоподобияШаблон:Нет АИ, когда декодер определяет набор условных вероятностей <math>P(r/U_i)</math>, соответствующих всем возможным кодовым векторам <math>U_i</math>, и решение принимает в пользу кодового слова, соответствующего максимальному <math>P(r/U_i)</math>. Для двоичного симметричного канала без памяти (канала, в котором вероятности передачи 0 и 1, а также вероятности ошибок вида 0 -> 1 и 1 -> 0 одинаковы, ошибки в j-м и i-м символах кода независимы) декодер максимального правдоподобия сводится к декодеру минимального хеммингова расстояния. Последний вычисляет расстояние Хемминга между принятой последовательностью r и всеми возможными кодовыми векторами <math>U_i</math> и выносит решение в пользу того вектора, который оказывается ближе к принятому. Естественно, что в общем случае такой декодер оказывается очень сложным и при больших размерах кодов <math>n</math> и <math>k</math> практически нереализуемым. Характерная структура сверточных кодов (повторяемость структуры за пределами окна длиной <math>n</math>) позволяет создать вполне приемлемый по сложности декодер максимального правдоподобия.
Принцип работы декодера
На вход декодера поступает сегмент последовательности <math>r</math> длиной <math>b</math>, превышающей кодовую длину блока <math>n</math>. Назовем <math>b</math> окном декодирования. Сравним все кодовые слова данного кода (в пределах сегмента длиной <math>b</math>) с принятым словом и выберем кодовое слово, ближайшее к принятому. Первый информационный кадр выбранного кодового слова принимается в качестве оценки информационного кадра декодированного слова. После этого в декодер вводится <math>n_0</math> новых символов, а введенные ранее самые старые <math>n_0</math> символов сбрасываются, и процесс повторяется для определения следующего информационного кадра. Таким образом, декодер Витерби последовательно обрабатывает кадр за кадром, двигаясь по решетке, аналогичной используемой кодером. В каждый момент времени декодер не знает, в каком узле находится кодер, и не пытается его декодировать. Вместо этого декодер по принятой последовательности определяет наиболее правдоподобный путь к каждому узлу и определяет расстояние между каждым таким путём и принятой последовательностью. Это расстояние называется мерой расходимости пути. В качестве оценки принятой последовательности выбирается сегмент, имеющий наименьшую меру расходимости. Путь с наименьшей мерой расходимости называется выжившим путём.
Пример
Рассмотрим работу декодера Витерби на простом примере. Полагаем, что кодирование производится с использованием сверточного (7,5)-кода. Пользуясь решетчатой диаграммой кодера, попытаемся, приняв некоторый сегмент <math>r</math>, проследить наиболее вероятный путь кодера. При этом для каждого сечения решетчатой диаграммы будем отмечать меру расходимости пути к каждому её узлу. Предположим, что передана кодовая последовательность U = (00000000…), а принятая последовательность имеет вид r = (10001000…), то есть в первом и в третьем кадрах кодового слова возникли ошибки. Как мы уже убедились, процедура и результат декодирования не зависят от передаваемого кодового слова и определяются только ошибкой, содержащейся в принятой последовательности. Поэтому проще всего считать, что передана нулевая последовательность, то есть U = (00000000…). Приняв первую пару символов (10), декодер определяет меру расходимости для первого сечения решетки, приняв следующую пару символов (00), — для второго сечения и т. д. При этом из входящих в каждый узел путей оставляем путь с меньшей расходимостью, поскольку путь с большей на данный момент расходимостью уже не сможет стать в дальнейшем короче. Заметим, что для рассматриваемого примера начиная с четвёртого уровня метрика (или мера расходимости) нулевого пути меньше любой другой метрики. Поскольку ошибок в канале больше не было, ясно, что в конце концов в качестве ответа будет выбран именно этот путь. Из этого примера также видно, что выжившие пути могут достаточно долго отличаться друг от друга. Однако на шестом-седьмом уровне первые семь ребер всех выживших путей совпадут друг с другом. В этот момент согласно алгоритму Витерби и принимается решение о переданных символах, так как все выжившие пути выходят из одной вершины, то есть соответствуют одному информационному символу.
Глубина, на которой происходит слияние выживших путей, не может быть вычислена заранее; она является случайной величиной, зависящей от кратности и вероятности возникающих в канале ошибок. Поэтому на практике обычно не ждут слияния путей, а устанавливают фиксированную глубину декодирования.
На шаге i) степень различия метрик правильного и неправильного путей достаточно велика (<math>d_{correct} = 2</math>, <math>d_{error} = 4</math>), то есть в данном случае можно было бы ограничить глубину декодирования величиной <math>b <= 6</math>. Но иногда более длинный к данному сечению путь может оказаться в конечном итоге самым коротким, поэтому особенно увлекаться уменьшением размера окна декодирования b с целью упрощения работы декодера не стоит. На практике глубину декодирования обычно выбирают в диапазоне <math>n < b < n + l</math>, где <math>l</math> — число исправляемых данным кодом ошибок. Несмотря на наличие в принятом фрагменте двух ошибок, его декодирование произошло без ошибки и в качестве ответа будет принята переданная нулевая последовательность.
См. также
Литература
- «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.
- Книга:Морелос-Сарагоса Р.: Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение
- Шаблон:Книга
