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

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

Сущность метода

Наилучшей схемой декодирования корректирующих кодов является декодирование методом максимального правдоподобия ^{[ источник не указан 3938 дней ]} , когда декодер определяет набор условных вероятностей ${\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 .