6.2. Алгоритм декодирования Витерби

Другое возможное представление кодового дерева, изображенного на рис. 6.2, показано на рис. 6.3, Форни [51] назвал такое представление решетчатой структурой. Как и на рис. 6.2, входной символ 0 соответствует выбору верхнего ребра, нижнего. Как и ранее, всякая входная последовательность соответствует некоторому пути на решетке Например, входная последовательность 10 110, как легко видеть, дает выходную последовательность 1 10 10 0 10 10, что совпадает с результатом, полученным с помощью рис. 6.2.

Рис. 6.3. Решетка для сверточного кода с кодовым ограничением 3

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

Важное значение решетчатого представления состоит в том, что с ростом числа входных символов число вершин в решетке не растет, а остается равным где k - длина кодового ограничения (число ячеек в регистре сдвига, необходимом для кодирования). Это обусловлено, конечно, тем, что избыточные части кодового дерева отождествляются. Следствием такого отождествления является то, что если в некоторой точке был выбран неверный путь, то позднее он может слиться с верным путем (и для хороших кодов такое событие очень вероятно).

Поскольку с ростом длины последовательности число путей растет экспоненциально, то на первый взгляд задача фактического построения оценки последовательности по максимуму правдоподобия для сверточного кода кажется безнадежной. Удивительно, что фактически эта задача оказывается не только возможной, но и сравнительно простой. Метод построения такой оценки легко найти, пытаясь непосредственно вычислить метрику для каждого пути на решетке. Вначале число путей действительно растет экспоненциально с ростом длины последовательности. Однако вскоре появляется возможность исключить из рассмотрения такое число путей в каждой вершине, которое в точности уравновешивает число вновь порожденных путей. Таким образом, оказывается возможным иметь сравнительно небольшой список путей, который всегда будет содержать наиболее правдоподобный путь. Эта простая итеративная процедура называется алгоритмом Витерби. Хотя применительно к сверточным кодам она была впервые открыта Витерби в 1967 г. [52], аналогичные методы были уже известны к тому времени в исследовании операций [53] и некоторых разделах динамического программирования [54].

Алгоритм Витерби легче всего понять, рассматривая в качестве примера решетчатую диаграмму для кода с Заметим прежде всего, что в решетке имеется ровно по два пути, ведущих в каждую вершину уровня 3. Поскольку, начиная с этой вершины,

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

Пример. В качестве примера того, как с помощью алгоритма Витерби исправляется данная комбинация ошибок, рассмотрим следующую ситуацию. Предположим, что демодулятор выдает только жесткие решения. В этом случае в качестве метрики может служить расстояние Хемминга между принятой последовательностью и кодовыми словами. Предположим, что передавалась пулевая последовательность, а принятая последовательность имеет вид Поскольку кодовое расстояние рассматриваемого в этом примере кода равно 5, то все двойные ошибки должны исправляться. На рис. 6.4 показана серия неполных решетчатых диаграмм, иллюстрирующих состояние декодера после обработки каждой следующей ветви. Числа, поставленные в соответствие вершинам, указывают расстояние Хемминга, накопленное «выжившим» путем в этой вершине.

На уровне 2 решетки произошла только одна из двух ошибок в канале, к выжившие пути вместе с соответствующими метриками показаны на рис. 6.4, а. На уровне 3 (рис. 6.4, б) каждый из путей с уровня 2 раздваивается (так что общее число путей становится равным 8 — по два для каждого состояния). Затем сравниваются метрики для пар путей, ведущих в каждую вершину, и из каждой пары сохраняется лишь лучший путь (так общее число путей вновь становится равным 4). Этот процесс повторяется при каждом приеме нового ребра. Заметим, что на уровне 5 (рис. 6.4, в) метрика нулевого пути имеет лучшие метрики любого другого пути. Поскольку дальнейших ошибок в канале не происходит, ясно, что в конце концов будет выбран правильный путь. Из этого примера также ясно, что выживающие пути могут отличаться друг от друга в течение долгого времени. Однако на уровне 10 (рис. 6.4, в) первые восемь ребер всех выживших путей совпадают друг с другом. В этот момент согласно алгоритму Витерби принимается решение о переданных символах, так как все выжившие пути приходят из одной вершины (т. е. соответствуют одному информационному символу).

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

(кликните для просмотра скана)

Рис. 6.5. Иллюстрация примера декодирования неисправляемой комбинации ошибок с помощью алгоритма Витерби

Предположим теперь, что появилась неисправляемая комбинация ошибок, например 11 01 00 00 ... Несколько неполных решеточных диаграмм для этого случая показаны на рис. 6.5. Заметим, что на уровне 3 удаляется правильный путь, так что возникноьение ошибки неизбежно. Кроме того, все выжившие пути имеют одно и то же первое ребро. Затем на уровне 5 все выжившие пути имеют одинаковые первые два ребра. Наконец на уровне 11 у всех выживших путей совпадают первые девять ребер. Интересно, что, хотя при декодировании возникла ошибка, выбранный ошибочный путь отличается от правильного лишь на очень коротком отрезке (состоящем только из трех ребер). В действительности информационная последовательность, соответствующая этому пути, имеет вид 00 ..., так что лишь один символ декодирован ошибочно. Это показывает типичное поведение ошибочных последовательностей в сверточных кодах при использовании алгоритма сверточного декодирования Витерби: ошибки влияют на сравнительно небольшой участок (меньший нескольких длин кодового ограничения) и приводят к коротким пакетам ошибок символов.

Мягкое декодирование представляет собой простую модификацию только что изложенной процедуры. Нужно лишь заменить метрику Хемминга на метрику мягкого решения (см. подразд. 1.3.4). Все остальные этапы декодирования не меняются. Таким образом, как и можно было ожидать, сложность реализации декодера с мягким решением не сильно отличается от сложности реализации декодера с жестким решением. Это является одним из важных преимуществ алгоритма декодирования Витерби.

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