Декодирование турбо-кодов

 

11.4.1. Правило максимума апостериорной вероятности (MAP).

 

Хотя турбо кодер является устройством с конечным числом состояний, наличие в нем перемежителя приводит к изменяющейся во времени решетчатой диаграммы, определяющей, в свою очередь, запредельную (при большой длине блока N) сложность оптимальной (максимально правдоподобной) процедуры декодирования, которая подразумевает нахождение кодового слова, ближайшего к принятому наблюдению (аналогично алгоритму Витерби с жесткими или мягкими решениями). Авторы открытия турбо-кодов предложили итеративную процедуру декодирования с мягкими решениями, которая позднее стала общепринятой для многих других кодов. В отличие от правила максимального правдоподобия (ML), состоящего в поиске кодового слова, минимизирующего вероятность перепутывания истинного кодового слова с некоторым другим, новый алгоритм декодирования направлен на минимизацию вероятности ошибки в каждом отдельном бите «чистой» информации. Эта цель может быть полностью достигнута на основе правила максимума апостериорной вероятности (MAP). Пусть – вектор принятого наблюдения, а – апостериорное (вычисленное после принятия ) распределение i –го информационного бита . Тогда согласно MAP правилу решение будет вынесено в пользу наиболее апостериорно вероятного значения :

, (11.1)

или

. (11.2)

 

11.4.2. Итеративная процедура декодирования.

 

Не существует практического метода точного вычисления апостериорной вероятности или, что эквивалентно, совместной вероятности для всего наблюдения , простирающегося на все слово турбо-кода. Процедура итеративного декодирования оперирует с аппроксимациями апостериорного распределения, постепенно уточняемыми в ходе итераций. Любая следующая итерация состоит из двух шагов, каждый из которых заключается в раздельном декодировании образующих кодов и использовании на втором шаге информации, извлеченной из первого образующего кода во время первого шага. После окончания k –й итерации (но не последней) ее результаты (k –я итерация апостериорного распределения) используются на следующей итерации в качестве априорной информации. Общее число итераций может быть установлено заранее или определено в ходе выполнения декодирования фиксацией момента стабилизации выходных данных (согласно стоп–критерию). После заключительной итерации решение принимается по правилу MAP (11.1) или (11.2). Основной принцип процедуры иллюстрирует схема, представленная на рис. 11.7.[3]

Первоначально первый образующий декодер принимает отсчеты наблюдения, отвечающие символам первого образующего кода, и выдает мягкие оценки бит данных. Эти мягкие решения используются вторым образующим декодером в качестве априорной информации совместно с отсчетами наблюдения, отвечающими второму образующему коду, для выработки первой аппроксимации решающих статистик . После этого вторая итерация начинает «раскодировку» первого образующего кода, но теперь с использованием в качестве обновленной априорной информации. Уточненное мягкое решение первого декодера используется вторым декодером, как априорная информация, выдавая на выходе вторую аппроксимацию и т.д. Данный цикл повторяется необходимое число раз, заканчиваясь принятием решения, как это было указано ранее. Сходимость этой процедуры не имеет точного теоретического обоснования, однако многочисленные эксперименты и моделирование показывают ее очень хорошее поведение.

Обращаясь к подробностям, отметим, что мягкие решения l –го образующего декодера на k –й итерации могут быть (что поясняется ниже) представлены в аддитивной форме:

, (11.3)

где первое слагаемое содержит априорную информацию об i – м бите данных , извлеченную из наблюдения в процессе обработки на предшествующих шагах, второе слагаемое охватывает «непосредственную» информацию, доставляемую систематическим отсчетом наблюдения (коэффициент q есть просто отношение SNR на кодовый символ), а последнее слагаемое представляет собой избыточную (extrinsic) информацию об , извлекаемую из отсчетов, отвечающих проверочным символам l –го образующего кода.

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

.

На первом шаге второй итерации избыточная информация второго декодирования на первой итерации используется как априорная:

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

 

11.4.3. Компонентное декодирование и прямой–обратный алгоритм.

 

Существуют различные возможные стратегии компонентного декодирования. Одним из вариантов служит алгоритм Витерби с мягкими решениями на входе и выходе (Soft-in-Soft-out Viterbi algorithm (SOVA)). Альтернативным путем является точное вычисление апостериорной вероятности для одиночного образующего кода с использование прямого–обратного алгоритма (иное наименование BCJR[4] или алгоритм Баля). Для определенности начнем с первого образующего кода половинной скорости, обозначив через вектор наблюдения, включающий только отсчеты, необходимые для первого декодирования: (см. рис. 11.6). Целью k –го шага итераций является вычисление

.

Введем совместную вероятность комбинации трех следующих событий: (1) к приходу i –го бита источника первый образующий кодер находится в состояние , (2) под воздействием он переходит в состояние и (3) вектор наблюдения принимает определенное значение . Суммирование по всем возможным парам состояний, связанным между собой через , очевидно даст , аналогично, суммирование по всем парам, связанным через , даст , так что

. (11.4)

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

, (11.5)

где

– совместная вероятность того, что текущим состоянием решетки является , а все отсчеты наблюдений, предшествующие текущему наблюдению , принимали значения ;

– вероятность того, что все отсчеты наблюдения после будут при условии, что следующим за текущим окажется состояние ;

– совместная условная вероятность того, что следующее состояние будет и текущее наблюдение – при условии, что текущим состоянием является .

Из трех вышеприведенных функций с самого начала известна , поскольку

,

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

(11.6)

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

Знание позволяет вычислить значения с помощью прямой рекурсии по i при начальной инициализации вида для , отвечающего начальному состоянию кодера, т.е. нулевому состоянию, и для всех остальных состояний :

. (11.7)

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

. (11.8)

Подстановка значений (11.5), найденных с помощью соотношений (11.6)–(11.8), в выражение (11.4) для совместно с переходной вероятностью гауссовского канала при BPSK входных сигналах и разложение на множители и , независящие от состояний решетки, приводят к предсказанному ранее результату (11.3)

,

с априорным компонентом

и избыточным компонентом

.

Функция в последнем соотношении представляет собой часть , зависящую лишь от проверочных символов компонентного кода, передаваемых в течение интервала, занимаемого i –м битом данных. Например, для образующего кода с половинной скоростью

,

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

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