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

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

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

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

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

Гипотеза Б. Состояние декодера в момент tx описывается символами {0,1} (узел №3), а на его вход из демодулятора по прежнему поступает символ «0». Тогда в момент t2 состояние декодера будет определяться символами {0,0}, но на выходе регистра с учетом сдвига вправо появится символ «1»(поэтому узел №3 в момент tx и узел №1 в момент t2 связывает ветвь, помеченная пуктиром).

Рис. 2.32. Пример декодирования по алгоритму Витерби

Если предположить (в качестве примера), что метрики состояний узлов №1 и №3 в момент / соответственно равны 4.0 и 2.0, а значения оценок приращения метрик в упоминаемых ветвях равняются +1.5 и -1.5, то обновленное (в момент L) значение метрики узла №1 как максимальное из двух вычисленных составит 5.5 -см. рис. 2.32. Стрелки, соответствующие «выжившим» ветвям, отобранным декодером на рассматриваемом такте обработки, наведены жирной линиеи.

Из всех возможных выживших путей декодер в конечном счете должен вы­брать единственный наиболее правдоподобный – путь с наибольшей метрикой.

Однако в текущий момент времени, даже если один из путей более вероятен чем другие, декодер, не имея сведений о последующих фрагментах принимае­мой последовательности, «воздерживается» от окончательного решения и запо" минает все выжившие пути на время приема определенного числа последую- щих отсчетов.

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

opt

Рис. 2.33. Выживший путь, найденный декодером Витерби [3]

Очевидно, что при поспешном принятии решения (L < Lop) может возникать неоднозначность в выборе выжившего пути, в то время как при L » L имеет место неоправданная задержка в принятии решения. Оптимальное значение Lnpt является случайной величиной и не может быть вычислено заранее. На практи­ке при реализации декодера устанавливают некоторую фиксированную ширину окна (как правило, Z~5m).

Сложность декодера Витерби не зависит от длительности обрабатываемой последовательности символов, но экспоненциально возрастает с ростом длины кодового ограничения. В современных системах беспроводной связи наиболее часто применяются сверточные коды с скоростями 1/2, 1/3,2/3, 3/4, 5/6 при дли­не кодового ограничения 5, 7 или 9.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100