Декодирование сверточных кодов. – ЧАСТЬ 1

Алгоритм Витерби. По сути, декодирование в соответствии с принципом максимума правдоподобия сводится к задаче отождествления принятой последовательности с одной из 2" разрешен­ных последовательностей. Решение принимается в пользу наиболее вероятной из них – той, которая в наименьшей степени отличается от принятой.

При передаче последовательности и = (их,и2,…,ип)в двоичном гауссов- ском канале с аддитивным белым шумом Щ), плотность условной вероятности /?(г|и) появления на выходе канала последовательности отсчетов смеси сигнала и шума г = (г,, г2,…, гп), где r(t)=u(t)+ 4(0, имеет вид

Здесь p(r.| iij) — плотность распределения принятого сигнала г. при усло­вии, что был передан сигнал и. Легко видеть, чтоp(r|u) получена произведени­ем функций плотности вероятности п независимых, распределенных по Гауссу случайных величин с математическим ожиданием, равным уровню сигнального отсчета и дисперсией, равной спектральной плотности шума NJ2.

Декодирование в соответствии с принципом максимального правдоподобия сводится к выбору такой кодовой последовательности и’, которая максимизиру­ет функцию правдоподобия:

Поскольку выражение (2.38) можно привести к виду

поиск максимума (2.39), как правило, сводится к максимизации логарифмиче­ской функции правдоподобия

Максимум (2.40) достигается при минимальном значении выражения NT(r.-W() 2 , представляющего собой квадрат Евклидова расстояния между

оценкой принятой последовательностью и соответствующей разрешенной.

Поэтому декодирование по критерию максимального правдоподобия , валентно поиску разрешенной последовательности с минимГьной !^ ": расстояния по Евклиду относительно принятой последовательГсГ ^^

Первое и второе слагаемое в выражении (2.41)

при использовании алфавита с равномощными сигналами являются константами так что минимизация dE сводится к максимизации скалярного произведения

Однако перебор 2" всевозможных последовательностей при больших п не реализуем практически. Фундаментальное упрощение процедуры декодирова­ния по максимуму правдоподобия в 1967 г. было предложено А. Витерби [27]. Новый алгоритм впоследствии получил имя автора. В соответствии с этим ал­горитмом, декодирование по принципу максимума правдоподобия реализуется в форме рекуррентного поиска на кодовой решетке пути, ближайшего к принятой последовательности (см. рис. 2.31).

Витерби показал существование простого и вместе с тем оптимального ре­шения задачи декодирования по принципу максимального правдоподобия с ли­нейной (от п) сложностью. Все многообразие путей декодирования так или иначе проходит через 2 т узлов (состояний) в любом поперечном сечении кодовой ре­шетки. Доказательство Витерби основывалось на наблюдении о том, что путь с наименьшей метрикой, входящий в узел и сливающийся в нем с некоторым иным путем, уже никогда в будущем не превосходит последний в смысле накопленной суммарной метрики. Поэтому из двух слившихся в узле путей путь с меньшей метрикой всегда можно исключить. Идея, по сути, состояла в том, чтобы взамен вычисления и отслеживания метрик путей, количество которых в геометрической прогрессии возрастает с ростом п, определять, запоминать и отслеживать метрики состояний (узлов), число которых постоянно и равняется 2 к

В принципе, алгоритм Витерби может быть описан следующим образом. Для каждого из 2 т возможных состояний (узлов) устройство вычисления метрик по принятой выборке демодулятора г. вычисляет текущую оценку приращения метрики (2.42). В случае двоичного канала число состояний декодера на каждом такте удваивается, поскольку указанная оценка вычисляется с учетом двух гипо­тез о принятом символе – «О» и «1» (соответствующих приему сигналов 1 и h Уже начиная с третьего такта, количество путей становится равным 8. иди декодер сравнивает метрики пар путей, ведущих в каждый узел, и из ка л пары оставляет один путь, выживший с наибольшей метрикой (^ ысТдс- ваегся) – поскольку, как отмечалось выше, все последующие модулятора выборки не могут качественно изменить отношения правдох^ путей. Э™т процесс повторяется всякий раз с

нового символа. В результате число обрабатываемых путей не превыше

Для уменьшения объема памяти декодирующего устройства сведения об отброшенных путях и соответствующих им накопленных метриках стираются Для этого метрики состояний периодически усекаются на одну и ту же величину (из накопленных каждым из узлов метрик периодически вычитается минималь­ная из них).

Например, в момент времени t2 первый сверху узел (на рис. 2.32 – узел №1) соответствует состоянию декодера, описываемого парой символов . В это состояние декодер приходит при двух разных гипотезах.

Гипотеза А. Состояние декодера в момент времени tx соответствует нали­чию в его регистре символов , на вход декодера из демодулятора поступает символ «0». С учетом сдвига содержимого регистра вправо, новое состояние в момент t2 по-прежнему определяется символами , а на выходе регистра появляется символ «0» (декодер остается в состоянии №1, и соответствующие узлы в моменты t