7.2. Методы последовательного декодирования

Последовательное декодирование было впервые введено Возенкрафтом [64], однако наиболее широко используемый в настоящее время алгоритм принадлежит Фано [74]. Здесь обсудим в основном алгоритм Фано, а затем проведем некоторые сравнения этого алгоритма со стек-алгоритмом последовательного декодирования [75, 76].

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

Этот подход может рассматриваться как метод проб и ошибок для поиска правильного пути на кодовом дереве. Такой поиск осуществляется последовательно, так что в каждый момент происходит обработка лишь одного пути. Однако декодер имеет возможность идти назад и менять предыдущие решения. Каждый раз при продвижении вперед осуществляется пробное решение. Для этого продолжается рассматриваемый путь добавлением к нему наиболее вероятного ребра. Если решение оказывается неправильным, то и последующие продолжения пути будут неправильными. В конце концов декодер сможет определить это, исследуя метрику пути. Однако вполне вероятно, что неправильный путь будет продолжен на несколько ребер. Если это произошло, то для восстановления правильного пути потребуется значительный объем вычислений. Декодер должен двигаться назад и пробовать различные пути до тех пор, пока не будет произведено правильного декодирования. Для быстрого обнаружения неправильного решения и быстрого восстановления правильного пути, что позволит уменьшить вычислительные сложности, нужно очень аккуратно выбирать параметры декодера. Основное достоинство метода последовательного декодирования состоит в том, что каждое правильное решение уменьшает объем последующих вычислений. В то же время значение метрики пути служит указанием на то, правильными ли были предыдущие решения.

Метрика ребра в вершине задается формулой

где переданный символ, принятый символ. (Предполагается, что речь идет о двоичном коде с содержащем символов на ребро.) Метрика пути в вершине

Параметр В является параметром смещения, и его смысл будет объяснен позже. Обычно его выбирают гак, чтобы значение метрики возрастало при принятии правильного решения и убывало при принятии неправильного решения. Типичное поведение метрики пути показано на рис. 7.12. Хотя метрика правильного пути может время от времени сильно уменьшаться из-за шума в канале, общей тенденцией на больших временных интервалах является возрастание. Вместе с тем при появлении сильного шума в канале метрика неправильного пути может возрасти, сделав этот путь похожим на хороший. Однако при уменьшении шума эта метрика обычно начинает уменьшаться. С помощью алгоритма последовательного декодирования нужно быстро обнаружить уменьшение метрики и найти путь с возрастающей метрикой. Для этого используется переменный порог который может быть увеличен или уменьшен на величину А. называемую приращением порога. Если метрика текущего пути становится меньше появляется указание на то, что рассматриваемый путь является плохим, и следует начать поиск хорошего пути.

Рис. 7.12. Типичное поведение метрик правильного и неправильного путей