Сверточные коды. 4 Дисер с 15 СК и Мягкое дек с 55. Программноаппаратная реализация оптимального алгоритма декодирования каскадных кодов на базе кодов рида соломона в адаптивных системах обмена данными
 Скачать 5.5 Mb.
|
Декодирование сверточных кодов. Алгоритм Витерби.Как для блоковых, так и для сверточны кодов наименьшую вероятность ошибочного декодирования обеспечивает декодирование по максимуму правдоподобия. Алгоритм максимума правдоподобия для сверточного декодера заключается в поиске такого пути на решетчатой диаграмме (рисунок 1.4), чтобы его кодовое слово отличалось от принятого в наименьшем числе позиций. Другими словами, необходимо выбрать кратчайший (наименьшего веса) путь на треллисе. Для двоичного симметричного канала (ДСК) декодер, работающий по алгоритму минимума расстояния, вычисляет расстояние Хэмминга между принятым кодовым словом и принимает решение в пользу того кодового слова, которое окажется ближайшим к принятому. Реализация такого устройства связана с существенными затратами. Однако реализацию декодера можно значительно упростить за счет удаления некоторых характеристик. Среди таких упрощенных алгоритмов декодирования сверточных кодов алгоритм Витерби является наиболее эффективным. Суть алгоритма заключается в том, что на каждом этапе декодирования сверточных кодов, сравнивается n0 путей, входящих в один узел решетчатой диаграммы. При этом из них сохраняется только тот путь, вес которого наименьший (кратчайшее Хэмминговое расстояние). Эти пути называются выжившими, а остальные исключаются из рассмотрения. Для двоичных сверточных кодов n0 = 2. Продолжая пример, рассмотренный в параграфе 1.1.2, проследим процесс восстановления кодовой комбинации сверточного кода по алгоритму Витереби на приемной стороне. Предположим, что из канала связи была принята комбинация r 1110 11 00 0111 . Искажение комбинации произошло в шестом бите принятого блока, то есть в третьем узле решетки. Условимся, что прием осуществлялся по ДСК, тогда в качестве веса пути можно использовать Хэмминговое расстояние между принятой последовательностью и кодовыми словами решетки. Поэтапный процесс построения треллиса декодером показан на рисунках 1.10а-д. Десятичные цифры на рисунке, представленные в соответствующих узлах решетки, указывают расстояние Хэмминга, накопленное выжившим путем в этом узле. На каждом этапе декодер Витерби делает предположение о том, какой символ поступил из канала. В случае двоичного сверточного кода этим символом может быть либо 0, либо 1. Из текущего узла решетки декодер строит два возможных пути, при этом в каждый следующий узел приходят также два пути- кандидата, из которых выживет только один, который и будет сохранен в памяти декодера с накопленным им весом.
На первом этапе декодер начинает работу из состояния 00, поэтому строятся только два возможных пути, ведущих в состояние 00, если закодированный информационный символ был равен 0 и в состояние 10, если закодированный символ был равен 1. Автомат, описывающий эти переходы, был представлен на рисунке 1.2. Далее из этих узлов формируются новые пары путей (рисунок 1.10а). На следующих этапах процедура повторяется, вес текущего пути прибавляется к накопленному весу узла. На третьем этапе (рисунок 1.10б) декодер проходит кодовое ограничение K = 3. Начиная с этого момента, в каждый узел решетки приходит по два конкурирующих пути. Задача декодера заключается в том, чтобы выбрать из них путь с наименьшим весом и сохранить его для дальнейших этапов декодирования. На шестом такте (рисунок 1.10д) уже можно выделить путь минимальной длины. Если декодирование завершить на этом этапе и проследить весь этот путь от начала до конца, можно увидеть, что декодированная последовательность имеет вид u 110100, следовательно, ошибка в шестом разряде принятой комбинации была исправлена. Предположим, что в рассмотренном примере прием продолжается. Декодер безошибочно принимает нулевую комбинацию вида декодирующая решетка примет вид: r 00 00 00 , тогда
Выжившие пути можно отличать друг от друга на протяжении многих тактов. На рисунке 1.11 видно, что первые 7 тактов выживших путей совпадает, произошло так называемое слияние путей. В этот момент времени алгоритм Витерби принимает решение о переданных символах, так как выжившие пути приходят из одной вершины. Количество тактов, за которое происходит такое слияние, называется глубиной декодирования L. Глубина не может быть вычислена заранее, так как зависит от количества ошибок в канале. Поэтому при практической реализации необходимо устанавливать фиксированную глубину декодирования. Как правило, она выбирается равной 4 или 5 длинам кодового ограничения. |