Сверточные коды. Формирование сверточного кода. Декодирование сверточных кодов, страница 2

Таким образом, имеется возможность представления кодового дерева сверточного кода в виде решетчатой структуры, как это показано на рис. 5.6. Как и на рис. 5.5, входной символ 0 соответствует выбору верхнего ребра, а символ 1 – нижнего. Важное значение решетчатой структуры состоит в том, что с ростом числа входных символов число вершин в решетке остается равным , где К – длина кодового ограничения. Начиная с третьего уровня в решетчатой структуре дерева вследствие периодичности изображение решетки повторяется. Тем не менее, всякая последовательность на входе, как и ранее, соответствует определенному пути по решетке. Например, входная последовательность 10110 дает, как и на рис. 5.6, выходную последовательность 1101001010.

Декодирование сверточных кодов

Для декодирования применяются алгебраические и вероятностные методы. К алгебраическим относится пороговое (мажоритарное) декодирование, к вероятностным – последовательное декодирование и декодирование по максимуму правдоподобия (алгоритм Витерби).

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

При пороговом декодировании для каждого блока  вычисляется синдром. Например

Метод последовательного декодирования предложен Возенкрафтом в 1957 г. и далее успешно развит Фано. Этот статистический метод фактически представляет собой метод проб и ошибок, так что время, требуемое для декодирования конкретного информационного символа, является случайной величиной.

Декодирование по максимум правдоподобия сводится к отождествлению принятой последовательности с одной из  возможных. Решение принимается в пользу той последовательности, которая в меньшем числе позиций отличается от принятой.

При больших  этот метод практически не реализуем из-за необходимости перебора  возможных кодовых последовательностей на каждом шаге (приеме очередного символа).

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

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

Витерби была предложена следующая простая итеративная процедура построения максимально правдоподобной оценки. Решение основано на вычислении метрики каждого пути на решетке. В случае использования демодулятора с жестким решением (либо 0, либо 1) в качестве метрики может служить расстояние Хемминга между принятой последовательностью и словами, появляющимися на выходе сверточного кодера. Алгоритм Витерби легко понять на рассматриваемом нами простом примере кода со скоростью R = 1/2 и кодовом ограничении к = 3. Заметим, что начиная с третьего уровня, в решетке имеется всего по два пути, ведущих в любую вершину. Согласно алгоритму Витерби сравниваются эти пути и сохраняется лишь тот из них, метрика которого лучше. Второй путь исключается из рассмотрения, поскольку при любых принятых впоследствии данных его правдоподобие не может превзойти правдоподобия оставшегося пути. Оставшиеся пути называются выжившими. Таким образом, начиная с третьего уровня появляется возможность исключить из рассмотрения такое число путей к каждой вершине решетчатой диаграммы, которое в точности уравновешивает число вновь порожденных путей. При этом остается сравнительно небольшой список выживших путей, который всегда будет содержать наиболее правдоподобный. Для кода с к = 3 на каждом этапе процедуры декодирования будет сохраняться не более четырех выживших путей. Для иллюстрации того, как с помощью алгоритма Витерби осуществляется исправление комбинации ошибок, предположим, что передавалась нулевая последовательность, а принята последовательность вида 10 00 10 00 00 .... Поскольку кодовое расстояние в этом примере равно 5, все двойные ошибки должны быть исправлены. На рис. 5.7 представлена последовательность решетчатых диаграмм с выжившими на разных уровнях путями. Числа в вершинах указывают расстояние Хемминга (метрику) выжившего пути. На диаграммах видно, что на уровне 5 метрика нулевого пути является наименьшей, и уже ясно, что в конечном итоге будет выбран правильный путь. Согласно алгоритму Витерби решение принимается на уровне 10, когда все выжившие пути исходят из одной вершины (т. е. соответствуют одному информационному символу).

Допустим теперь, что появилась неисправимая комбинация ошибок, например 11 01 00 00 . . .. Некоторая последовательность решетчатых диаграмм с выжившими путями для этого случая представлена на